Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 0 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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