ogni LL (1) la grammatica è anche un LR (1)?
-
09-10-2019 - |
Domanda
È ogni LL (1) grammatica anche un LR (1)?
Soluzione
Si, dal momento che entrambi LL e LR analizzano i dati da sinistra a destra; e dal momento che LL (1) guarda avanti solo token si deve necessariamente essere un LR (1). Ciò vale anche per LR (k), dove k> 1, dal momento che una grammatica LR (k) può essere trasformata in un (1) grammatica LR.
La differenza tra LR e LL grammatiche arriva dal fatto che LR produce la derivazione destra, dove come LL produce la derivazione a sinistra. Quindi questo significa che un parser LR può infatti parse un insieme più grande di una grammatica LL come si accumula dalle foglie.
Consente di dire che abbiamo produzioni come segue:
A -> "(" A ")" | "(" ")"
Poi LL (1) analizzerà il (())
stringa:
(()) -> A
-> "(" A ")"
-> "(" "(" ")" ")"
Qualora il 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 visita: http://en.wikipedia.org/wiki/LL_parsing