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
1 Answer
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 + or * 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'(ϵ)) 
- Tnx I understand now, so that means in order to parse Postfix Expressions i first need to convert them to infix right ? if so what method should i use because i need to generate parser with javacc for evaluation?amir ahmed– amir ahmed2018-12-01 14:55:34 +00:00Commented Dec 1, 2018 at 14:55
- @amirahmed An LL parser cannot convert the input to infix. Instead, you need to figure out a LL grammar that describes your language. As this will produce a really weird parse tree (as in my above example) you then need a post-processing step to turn the parse tree into the structure you need. In practice, no one would go through all of that trouble just to parse postfix expressions – a hand-written stack automaton can do this much more easily.amon– amon2018-12-01 15:02:23 +00:00Commented Dec 1, 2018 at 15:02
- sorry for my limited knowledge on this matter, but while searching through web i found this article on LL grammar used to convert postfix expressions to infix link . due to the complexity of grammars i didn't understand it fully. can u excuse my curiosity and verify it for me ? tnxamir ahmed– amir ahmed2018-12-01 15:10:57 +00:00Commented Dec 1, 2018 at 15:10
- @amirahmed Attribute grammars are not standard LL as usually discussed in computer science, but a significant extension. In the linked page, they transform the grammar
E → E E binop | E uop | id | intlittoE → (id | intlit)(E binop | uop)*, which uses the same transformation I used above – just written differently (and doesn't have anything to do with attribute grammars, despite the page title). I am not familiar with JavaCC and can't tell whether their code makes any sense.amon– amon2018-12-01 15:52:17 +00:00Commented Dec 1, 2018 at 15:52