• accettazione per pila vuota: una stringa e' accettata da un automa a pila M se e
solo se al termine della scansione della stringa la pila e' vuota N(M) = {x|
|*}
• accettazione per stato finale: una stringa e' accettata da un automa a pila M se
e solo se al termine della scansione della stringa M si trova in uno stato finale
L(M) = {x||*,q∈F,γ∈Γ*}
Per consentire un’efficiente e corretta analisi sintattica i linguaggi di
programmazione devono essere linguaggi CF
- non ambigui (ogni stringa deve essere generabile con un solo albero di
derivazione)
- analizzabili in modo deterministico in tempo lineare (linguaggi LL(k),LR(K),
LALR(k) ecc.)
La forma di Backus-Naur(BNF)
Per descrivere in maniera compatta le grammatiche si usa la BNF(Backus-Naur
form). I terminali e i nonterminali vengono descritti da parole; per poterli
distinguere, i terminali vengono scritti in grassetto. Una regola BNF è data da
un nonterminale e da un'espressione(anziché una semplice sequenza di
terminali e nonterminali).
Ogni terminale ed ogni nonterminale è un'espressione BFN; una regola
contenente solo un terminale o un nonterminale corrisponde in modo ovvio a
una produzione.
La notazione A ::= e0 | e1 | ... | en−1 significa che la grammatica contiene le
produzioni A → e0, A → e1,. . . ,A → en−1, e cioè che per riscrivere A bisogna
scegliere uno degli ei .La notazione [e] nel membro destro di una produzione
significa che l’espressione e può essere usata o meno, cioè `e opzionale. La
54