6
Ogni grammatica LL (1) è anche una LR (1)?Ogni grammatica LL (1) è anche un LR (1)?
A
risposta
8
Sì, poiché sia LL che LR analizzano i dati da sinistra a destra; e poiché LL (1) guarda avanti solo un token, deve necessariamente essere un LR (1). Questo vale anche per LR (k), dove k> 1, poiché una grammatica LR (k) può essere trasformata in una grammatica LR (1).
La differenza tra grammatiche LR e LL deriva dal fatto che LR produce la derivazione più a destra, dove LL produce la derivazione più a sinistra. Ciò significa che un parser LR può infatti analizzare un set maggiore di una grammatica LL mentre si accumula dalle foglie.
consente di dire che abbiamo produzioni come segue:
A -> "(" A ")" | "(" ")"
Poi LL (1) sarà analizzare la stringa (()):
(()) -> A
-> "(" A ")"
-> "(" "(" ")" ")"
Dove come la LR (1) analizzerà come segue:
Input Stack Action
(()) 0
()) 0 '('
)) 0 '(' '('
) 0 '(' '(' ')' Reduce using A -> "(" ")"
) 0 '(' A
- 0 '(' A ')' Reduce using A -> "(" A ")"
- 0 A Accept
Per maggiori informazioni vedere: http://en.wikipedia.org/wiki/LL_parsing
+0
ma la sequenza (di produzioni) utilizzata da LL (1) per analizzare non è sempre nella sequenza opposta (delle produzioni) usata da LR (1) analizzare. Anche se l'ex è il top down e quest'ultimo è un parser dal basso, quindi la tua ragione per cui LL (1) sia LR (1) non sembra abbastanza. – siddharth
+1
Qualcosa che è LR non significa che l'albero di analisi sia identico all'asse di analisi LL inverso, e quindi il parser non utilizzerà necessariamente le produzioni nell'ordine opposto. Ciò che significa è che un parser LR può analizzare correttamente lo stesso set di stringhe dato la stessa grammatica. – Mike
+0
Questo fatto contraddice? http://cs.stackexchange.com/questions/60763/does-my-grammar-contradict-ll-⊆-lr1/60764#60764 – Pranav
Penso di avere questa domanda al college un giorno molte lune fa;) – foreyez