Perché una grammatica LL non può essere lasciata ricorsiva?

Question

Nella dragon book, LL grammatica è definita come segue:

Una grammatica è LL se e solo se per qualsiasi produzione A -> a|b, valgono le seguenti due condizioni.

1. FIRST(a) e FIRST(b) sono disgiunti. Ciò implica che essi non possono entrambi trarre EMPTY

2. Se b può derivare EMPTY, quindi a non può trarre alcun stringa che inizia con FOLLOW(A), cioè FIRST(a) e FOLLOW(A) devono essere disgiunti.

E so che LL grammatica non può essere lasciato ricorsivo, ma qual è la ragione formale? Suppongo che la grammatica ricorsiva a sinistra contraddica la regola 2, giusto? per esempio, ho scritto seguente grammatica:

S->SA|empty 
A->a 

Perché FIRST(SA) = {a, empty} e FOLLOW(S) ={$, a}, poi FIRST(SA) e FOLLOW(S) non sono disgiunti, in modo da questa grammatica non è LL. Ma non so se è la ricorsione a sinistra a fare FIRST(SA) e FOLLOW(S) non disgiunti, o c'è qualche altra ragione? Mettilo in un altro modo, è vero che ogni grammatica ricorsiva a sinistra avrà una produzione che violerà la condizione 2 della grammatica LL?

Answer 1

OK, ho capirlo, se una grammatica contiene produzione di sinistra-ricorsivo, come:

S->SA 

Poi in qualche modo deve contenere un'altra produzione a "finire" la ricorsione, dire:

S->B 

E poiché FIRST (B) è un sottoinsieme di FIRST (SA), quindi sono comuni, questo viola la condizione 1, ci deve essere conflitto durante il riempimento delle voci della tabella di parsing corrispondenti ai terminali sia in FIRST (B) che FIRST (SA) . Per riassumere, grammatica sinistra-ricorsione potrebbe causare primo insieme di due o più produzioni avere terminali comuni, violando così condizione 1.

Answer 2

consideri la grammatica:

S->SA|empty 
A->a 

Questa è una scorciatoia per le tre regole:

S -> SA 
S -> empty 
A -> a 

Ora consideriamo la stringa aaa. Come è stato prodotto? Si può leggere solo un carattere alla volta se non avete lookahead, in modo da iniziare fuori come questo (avete S come simbolo iniziale):

S -> SA 
S -> empty 
A -> a 

Bene, hanno prodotto il primo a. Ma ora non puoi applicare più regole perché non ci sono più non-terminali. Sei bloccato!

Che cosa si dovrebbe aver fatto è stato questo:

S -> SA 
S -> SA 
S -> SA 
S -> empty 
A -> a 
A -> a 
A -> a 

Ma voi non lo sanno senza leggere l'intera stringa. Avresti bisogno di una quantità infinita di lookahead.

In senso generale, sì, ogni grammatica ricorsiva a sinistra può avere stringhe ambigue senza lookahead infinito. Guarda nuovamente l'esempio: ci sono due regole diverse per S. Quale dovremmo usare?

Answer 3

Un LL(k) grammatica è quella che consente la costruzione di un deterministico, discesa parser con solo k simboli guarda avanti. Il problema con la ricorsione a sinistra è che rende impossibile determinare quale regola applicare fino a quando non viene esaminata la stringa di input completa, il che rende potenzialmente infinito lo k richiesto.

Usando il tuo esempio, scegliere un k, e dare il parser una sequenza di input di lunghezza n >= k:

aaaaaaa... 

Un parser non può decidere se si deve applicare S->SA o S->empty guardando i k simboli avanti perché la la decisione dipenderebbe dal numero di volte in cui è stato scelto S->SA e queste sono informazioni che il parser non ha.

Il parser avrebbe dovuto scegliere S->SA esattamente n tempi e S->empty una volta, ed è impossibile decidere che è giusto, cercando in primi k simboli nel flusso di input.

Per conoscere, un parser avrebbe dovuto esaminare sia la sequenza di input completo, e tenere il conto di quante volte S->SA è stato scelto, ma tale parser cadrebbe al di fuori della definizione di LL(k).

Si noti che il lookahead illimitato non è una soluzione perché un parser viene eseguito su risorse limitate, quindi ci sarà sempre una sequenza di input finita di una lunghezza abbastanza grande da far arrestare il parser prima di produrre qualsiasi output.