How to modify semantic actions when removing left-recursion from a grammer

Question

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?

Answer 1

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.

Answer 2

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.