Esempio di una grammatica LR che non può essere rappresentato da LL?

Question

Tutti grammatiche LL sono grammatiche LR, ma non il contrario, ma ho ancora fatica a trattare con la distinzione. Sono curioso di sapere piccoli esempi, se esistono, delle grammatiche LR che non hanno una rappresentazione LL equivalente.

Answer 1

Bene, per quanto riguarda le grammatiche sono interessati, la sua facile - qualsiasi semplice sinistra-ricorsiva grammatica è LR (probabilmente LR (1)) e non LL. Quindi un elenco di grammatica come:

list ::= list ',' element | element

è LR (1) (assumendo la produzione di elemento è), ma non LL. Tali grammatiche possono essere abbastanza facilmente convertiti in grammatiche LL sinistro del factoring e tale, quindi questo non è troppo interessante comunque.

Di più interesse è lingue che sono LR ma non LL - che è una lingua per la quale esiste un LR (1) grammatica, ma non LL grammatica (k) per ogni k. Un esempio è le cose che hanno bisogno di partite finale opzionale. Ad esempio, la lingua di un numero qualsiasi di simboli a seguito dallo stesso numero o un minor numero di simboli b, ma non più bs - {a ^ i ^ j b | i> = j}. C'è un LR banale (1) grammatica:

S ::= a S | P
P ::= a P b | \epsilon

, ma non LL grammatica (k). La ragione è che una grammatica LL deve decidere se far corrispondere un A + B coppia o un una strana quando guardando una A, mentre la grammatica LR può rinviare la decisione fino a dopo vede la B o la fine dell'input.

Questo post su cs.stackechange.com ha un sacco di riferimenti su questo