World's most popular travel blog for travel bloggers.

[Solved]: How should I show that a grammar is not LL(1) and convert grammar to LL(1)

, , No Comments
Problem Detail: 

I'm trying to find the ambiguity in this grammar so I can remove it and convert it to LL(1), however for the life of me, I can't find the ambiguity. Moreover, I think there is cycle between X and Y and I could not find a solution to solve this.

1) X -->YX|$

2) Y --> ε|A|let A in Y|let A in E end

3) A--> x=E

4) E-->(E)|E*E|*E|EE|x|ƛx.E`

Asked By : saeedrobot

Answered By : rici

E → EE is obviously ambiguous, as as E → E*E. How should xxx be parsed? Is it [[x x] x] or [x [x x]]?

X is only problematic if Y is nullable. If you remove the incorrect empty production for Y, you will also fix that issue.


To clarify, Y → ε is incorrect because it would allow Y to derive

let A in 

which is not a complete statement (I mean, not a complete Y :) ). The production Y → let A in Y is sufficient to allow a statement to be preceded by any number of let A in clauses, without allowing it to be unterminated.

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback