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

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?

• 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. – Raphael Nov 12 '12 at 11:21
• @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. – Arani Nov 13 '12 at 19:48