LL (1) non può essere ambiguo

Question

Come si può dimostrare che nessuna grammatica LL (1) può essere ambigua?

So che cos'è una grammatica ambigua ma non posso provare il suddetto teorema/lemma.

Answer 1

Penso che sia quasi un risultato diretto della definizione di LL (1). Prova la prova per contraddizione; supponiamo che tu abbia una grammatica LL (1) ambigua e cerchi qualcosa che puoi dimostrare essere vero e non vero. Come punto di partenza "cosa sai sempre quando elabori l'input?"

Dato che questo sembra un problema di compiti a casa e in realtà non ho finito il problema più di quanto ho abbozzato sopra, mi fermerò qui.

Answer 2

Provare che nessuna grammatica ambigua può essere una grammatica LL (1). Per suggerimenti, vedere http://www.cse.ohio-state.edu/~rountev/756/pdf/SyntaxAnalysis.pdf, diapositive 18-20. Vedi anche http://seclab.cs.sunysb.edu/sekar/cse304/Parse.pdf, pag. 11 e precedenti.

Answer 3

Ecco la mia prima bozza a prova. Potrebbe essere necessario un po 'di messa a punto, ma penso che copra tutti i casi. Penso che molte soluzioni siano possibili. Questa è una prova diretta.

(Nota a lato: è un peccato SO non supporta matematica, come nel LaTeX.)

Proof

Sia T e N gli insiemi di simboli terminali e non terminali .

Facciamo il seguente stiva

MaybeEmpty(s) = true <=> s ->* empty 
First(s) = X containing all x for which there exists Y such that s ->* xY 
Follow(A) = X containing all x for which there exists Y,Z such that S ->* YAxZ 

Si noti che una grammatica è LL (1) se vale quanto segue per ogni coppia di produzioni A -> B e A -> C:

1. (not MaybeEmpty(B)) or (not MaybeEmpty(C)) 
2. (First(B) intersect First(C)) = empty 
3. MaybeEmpty(C) => (First(B) intersect Follow(A)) = empty 

Si consideri una lingua con LL (1), con A -> B e A -> C. Vale a dire che c'è una stringa di terminali TZ che ammette derivazioni multiple da alberi di analisi distinti.

Supponiamo che la derivazione sinistra raggiunga S ->* TAY ->* TZ. Il passaggio successivo potrebbe essere TAY -> TBY o TAY -> TCY. Quindi la lingua è ambigua se sia BY ->* Z e CY ->* Z. (Si noti che poiché A è un arbitrario non terminali, se non esiste un tale caso, la lingua è non ambigua.)

Caso 1: Z = vuoto

dalla regola 1 di LL (1) grammatiche , al più uno di B e C può derivare vuoto (caso non ambiguo).

Caso 2: Z non vuoto, e né B né C derivano vuoto

dalla regola 2 LL (1) grammatiche, al massimo uno di B e C possono consentire l'ulteriore derivazione perché il terminale principale di Z non può essere in entrambi First(B) e First(C) (caso non ambiguo).

Caso 3: Z non vuoto e sia MaybeEmpty(B) o MaybeEmpty(C)

nota la regola da 1 di LL (1) grammatiche, B e C possono non entrambi derivare vuoto. Supponiamo quindi che MaybeEmpty(C) sia vero.

Fornisce due sottocasi.

Caso 3a: CY -> Y; e Case 3b: CY ->* DY, dove D non è vuoto.

In 3a è necessario scegliere tra BY ->* Z e CY -> Y ->* Z, ma si noti che First(Y) subset-of Follow(A). Poiché Follow(A) non interseca First(B), può essere eseguita una sola derivazione (non ambigua).

In 3b dobbiamo scegliere tra BY ->* Z e CY ->* DY ->* Z, ma si noti che First(D) subset-of First(C). Poiché First(C) non interseca First(B), può essere eseguita solo una derivazione (non ambigua).

Quindi in ogni caso la derivazione può essere ampliata solo da una delle produzioni disponibili. Quindi la grammatica non è ambigua.