Ho un problema nella formulazione della grammatica LL (K) per questo problema di espressione postfisso, dato (4 3/2 * 4 5 / +) come input deve produrre 52/12
Ho un problema nella formulazione della grammatica LL (K) per questo problema di espressione postfisso, dato (4 3/2 * 4 5 / +) come input deve produrre 52/12
Le espressioni postfix non possono essere analizzate direttamente con LL (k) per ogni k. Ad esempio, considera la grammatica semplificata:
E → 1
E → E E +
E → E E *
Questo ci consente di descrivere espressioni come 1 1 1 + * , 1 1 * 1 + o 1 1 1 ... + * + . Ma all'inizio dell'espressione non è possibile stabilire se l'alternativa E ← E E + o E ← E E * debba essere scelta - la parte ... potrebbe essere più lunga di qualsiasi lookahead k.
Nota che i parser LR sono perfettamente in grado di gestire grammatiche come questa perché la grammatica viene analizzata dal basso verso l'alto - la decisione tra le alternative può essere posticipata finché non si incontra l'input + o * .
Se una tale grammatica ricorsiva a sinistra deve essere analizzata con un parser LL, dobbiamo riscrivere la grammatica per produrre un albero di analisi diverso ed eseguire la post-elaborazione sull'albero per portarlo nella forma corretta che può essere valutata. Qui potremmo usare:
E → 1 E'
E' → ϵ
E' → 1 E' O E'
O → +
O → *
Ovviamente, gli alberi di analisi risultanti sono piuttosto scomodi. Per esempio. l'input 1 1 1 + 1 1 * + * sarà analizzato come:
E(1
E'(1
E'(1
E'(ϵ)
O(+)
E'(1
E'(1
E'(ϵ)
O(*)
E'(ϵ)))
O(+)
E'(ϵ)))
O(*)
E'(ϵ))