I have a problem in formulating LL(K) grammar for this postfix expression problem, given (4 3 / 2 * 4 5 / +) as an input must output 52/12
closed as unclear what you're asking by Bart van Ingen Schenau, Jörg W Mittag, Robert Harvey, gnat, BobDalgleish Dec 6 '18 at 14:01
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
Postfix expressions cannot be directly parsed with LL(k) for any k. For example, consider the simplified grammar:
E → 1 E → E E + E → E E *
This allows us to describe expressions such as
1 1 1 + *,
1 1 * 1 +, or
1 1 1 ... + * +. But at the start of the expression it is not possible to tell whether the
E ← E E + or
E ← E E * alternative should be chosen – the
... part could be longer than any lookahead k.
Note that LR parsers are perfectly able to handle grammars like this because the grammar is parsed bottom up – the decision between the alternatives can be deferred until the
* input is encountered.
If such a left-recursive grammar is to be parsed with an LL parser, we need to rewrite the grammar to produce a different parse tree, and perform post-processing on the tree to bring it into the correct form that can be evaluated. Here we might use:
E → 1 E' E' → ϵ E' → 1 E' O E' O → + O → *
Of course, the resulting parse trees are fairly awkward. E.g. the input
1 1 1 + 1 1 * + * would be parsed as:
E(1 E'(1 E'(1 E'(ϵ) O(+) E'(1 E'(1 E'(ϵ) O(*) E'(ϵ))) O(+) E'(ϵ))) O(*) E'(ϵ))