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)

, ,
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`

`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.