-5

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

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'(ϵ))
| improve this answer | |
  • 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 Dec 1 '18 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 Dec 1 '18 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 ? tnx – amir ahmed Dec 1 '18 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 | intlit to E → (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 Dec 1 '18 at 15:52

Not the answer you're looking for? Browse other questions tagged or ask your own question.