-4

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.

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'(ϵ))
  • 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.