Esempio di una grammatica LR che non può essere rappresentato da LL?
Domanda
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.
Soluzione
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ù b
s - {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