Grammatiche

Grammatica

Una grammatica è una quartupla G = (N,Σ,R,S)

Simboli non terminali

N insieme dei simboli non terminali, o metasimboli, cioè che non possono comparire negli enunciati del linguaggio ma che ci servono per denotare elementi di un enunciato.

Esempio <soggetto>, <verbo>, <frase>

N ∩ Σ = ∅, quindi sono disgiunti.

Alfabeto del linguaggio

Σ alfabeto del linguaggio costituito da simboli terminali (token), quindi compaiono effettivamente nelle stringhe. Nella teoria dei linguaggi formali, l'alfabeto non contiene solo simboli, ma anche "parole" come "if" che vengono trattate come tutti gli altri token. Servono a semplificare la grammatica.

Simbolo iniziale

S simbolo non terminale speciale (S ∈ N) ed è il punto di partenza che denota un enunciato valido. Da qui si comincia a costruire la frase.

Regole di produzione

R: insieme finito di regole di produzione nella forma:

α→β

α è una stringa di non terminali (N) di lunghezza ≥ 1, cioè α∈N∗∖{ϵ}

β è una stringa di terminali e/o non terminali, di qualsiasi lunghezza, anche 0: β∈(N∪Σ)∗

Applicando la regola, un'istanza di α viene sostituita da un'istanza di β.

Esempio

Ingredienti:

N={<frase>,<soggetto>,<verbo>}

Σ={"il gatto","dorme"}

S=<frase>

R:

1. <frase>→<soggetto> <verbo>
2. <soggetto>→"il gatto"
3. <verbo>→"dorme"

→Stringa iniziale: <frase>

→Cerco <frase> nella stringa → c'è!

→Sostituisco con <soggetto> <verbo> (regola 1).

→Ora ho: <soggetto> <verbo>

→Cerco <soggetto> → c'è!

→Sostituisco con "il gatto" (regola 2).

→Ora ho:

→"il gatto" <verbo>

→Cerco <verbo> → c'è!

→Sostituisco con "dorme" (regola 3).

→Ora ho:

→"il gatto" "dorme"

Relazioni tra le stringhe

Per spiegare le relazioni tra le stringhe usiamo delle regole.

La regola di produzione

Innanzitutto la regola di produzione, che può essere considerata come una ricetta.

Si scrive così:

⇒_G⊆(N∪Σ)∗×(N∪Σ)∗: γ⇒_Gδ se e solo se δ si ottiene da γ mediante l’applicazione di una singola regola di produzione di R nella grammatica G.

Scomponiamo l'espressione

⇒_G rappresenta la relazione di produzione immediata.

→ La produzione implica l'utilizzo di una sola regola, che possiamo esplicitare tramite l'espressione "immediata".

Si legge "produce immediatamente in G" (produce immediatamente nella grammatica G).

In questo caso leggiamo "la relazione di produzione immediata" ⊆ È sottoins