Suppose the task is to make an LL(1) grammar for postfix operations, where the only operation is ternary.

Obvious approach is

$N$ - number
$O$ - operation
$S$ - expression


$S \rightarrow SSSO \mid N$

This grammar is obviously not LL(1), and refactoring it (removing left recursion and right branching) gives:

$S \rightarrow NS'$
$S' \rightarrow \epsilon \mid SSO$

which also is not LL(1). To show this, consider FOLLOW(S') and FIRST(S) - they have N in common.

Am I doing something wrong? Are there other ways to turn grammar to LL(1) or LL(1) grammar cannot be built in this case?

Note that for binary operations this approach gives LL(1) grammar:

$S \rightarrow NS'$
$S' \rightarrow \epsilon \mid SO$

  • 1
    $\begingroup$ Welcome to Computer Science! Please use LaTeX to typeset mathematics. This is done here with MathJax! See this page for some hints. $\endgroup$ – babou Jun 16 '14 at 8:01
  • $\begingroup$ Adding more rules won't help you if the expected final result is to be the same. So unless you are okay with actually changing your grammar, it won't just magically become an LL(1) grammar. $\endgroup$ – Alexis Wilke Jun 18 '14 at 0:26
  • $\begingroup$ @AlexisWilke the goal is to make LL(1) grammar for this language, I only showed that obvious approach to this fails $\endgroup$ – lisyarus Jun 18 '14 at 8:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.