Cheap and Secure Web Hosting Provider : See Now

[Solved]: How to modify semantic actions when removing left-recursion from a grammer

, , No Comments
Problem Detail: 

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?

Asked By : Arani

Answered By : Arani

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6604

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback