Is there any algorithm that tells us how to modify semantic actions associated with a left-recursive grammar? For example, we have the following grammar, and its associated semantic actions:

$ S \rightarrow id = expr $ { S.s = expr.size }

S $\rightarrow$ if expr then $S_1$ else $S_2$ { $S_1.t = S.t + 2; $ $S_2.t = S.t + 2;$ $S.s = expr.size + S_1.size + S_2.size + 2;$ }

S $\rightarrow$ while expr do $S_1$ { $S_1.t = S.t + 4;$ $S.s = expr.size + S_1.s + 1;$ }

S $\rightarrow$ $S_1$ ; $S_2$ {$S_1.t = S_2.t = S.t;$ $S.s = S_1.s + S_2.s; $ }

Clearly the non-recursive version of the grammer is:

S $\rightarrow$ id = expr T

S $\rightarrow$ if expr then $S_1$ else $S_2$ T

S $\rightarrow$ while expr do $S_1$ T

T $\rightarrow$ ; $S_2$ T

T $\rightarrow$ $\epsilon$

But we also need to change the semantic actions accordingly. Any ideas how this can be done?

  • $\begingroup$ I have trouble reading your question. What is a "semantic action"? Please incorporate text into your LaTeX formulae by using \text{...}; I have found this to be more readable than a mix of math and ordinary text. $\endgroup$
    – Raphael
    Commented Nov 12, 2012 at 11:21
  • $\begingroup$ @Raphael All the instructions written in curly brackets are called semantic actions. Thank you for informing me about \text{}. As you might have guessed, I have only getting started using LaTeX and I still have a lot of things to learn how to use it appropriately. $\endgroup$
    – Arani
    Commented Nov 13, 2012 at 19:48

2 Answers 2


From what I have discovered, there is no general technique to modify the semantic actions while removing left-recursion. Instead, the best method is to take a representative example, draw its parse tree, and then checking which semantic actions give us the same result as the previous grammar.


I have a partial solution (I'm seeking a general one). If your grammar has NO epsilon productions, then no nonterminals are nullable. This means the algorithm to remove left recursion goes through (though it introduces epsilon productions).

If you add semantic actions of the form Action (label, count) which recognise the empty string, and use a shift/reduce parser, and examine all** alternatives, there is no need at all to reorganise the parse tree. When parsing, if a terminal is recognised it pushes an attribute onto the parser stack, this is a shift action. When an action is encountered, it pops N values off the stack, and pushes a node with the specified label and the values popped off the stack, in reverse, as children. This is the reduce action.

The parser must propagate the current position and parser stack, and the operations of shift and reduce should be done with functional updates not mutations. It is then clear than refactoring the grammar does not change the sequence of shift and reduce actions, so the resultant parse tree is invariant under refactoring.

This means if you generate an AST rather than a parse tree you must refer to the attributes by number. The machinery works because the parser stack and control stack are decoupled and refactoring only changes the control stack. The difficulty is that the grammar must be epsilon free initially because the Reduce action terms are themselves nullable.

** The assumption all alternatives are examined is made so that the order of consideration is immaterial. Although refactorings produce equivalent grammars, there is no automatic assurance the resultant parse trees will be the same unless all possibilities are examined. In that case the ordering remains indeterminate, but the set of results will be equal.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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