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`

  • $\begingroup$ @ Raphael : I have this idea in my mind: X -->YX ∣ $ Y -->ε ∣ A ∣ MN M -->let A in N --> ε ∣ MA ∣ ME end A -->x=E E -->xE’ ∣ ƛx.EE’ ∣ (E) E’ ∣ *EE’ E’-->EE’ ∣ *EE’ ∣ ε The problem that I have now is in non-Terminal Y which has epsilon, consequently, it may affect the X too. So now I am thinking of deleting the Y -->ε , because I think it is useless and does not create a new product. but I am not 100% sure about it. $\endgroup$ – saeedrobot Jan 21 '16 at 10:37
  • $\begingroup$ Please integrate that into your question. $\endgroup$ – Raphael Jan 21 '16 at 17:27

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.

  • $\begingroup$ To solve the ambiguous in non-terminal E, I used this grammar E-->xE' |ƛx.EE' |(E)E'|*EE' E'--> EE' | *EE' | ε But I am not sure about my solution in this part(it should parse like[[x x] x] ). moreover, in X and Y I have no idea how should I remove the unnecessary empty production because as you mentioned it causes the problem. $\endgroup$ – saeedrobot Dec 18 '15 at 21:10
  • $\begingroup$ Is there any rule for this type of problem or samples ? $\endgroup$ – saeedrobot Dec 18 '15 at 21:16
  • $\begingroup$ I have tried to solve this problem.First I remove the ambiguous part in rule one then I removed unnecessary empty production in Y and my grammar looks like this. But as can be seen, in rule one I have a cycle. I still have a problem of Left-Factoring in rule 2. So is there anyone who can help me to convert the grammar to become an LL(1) grammar. 1) X -->YX|$|X 2) Y --> A|let A in | let A in Y|let A in E end 3) A--> x=E 4) E-->xE' | ƛx.EE' | (E)E' | *EE' 5) E'--> EE' | *EE' | ε $\endgroup$ – saeedrobot Dec 19 '15 at 16:28
  • $\begingroup$ @saeedrobot: It should be obvious that you can just remove X -> X without suffering any consequences. And I do not believe that Y -> let A in really expresses the intent of the grammar. I believe Y is "statement" (Hint: When asking questions, use meaningful identifiers; it will help the people helping you) and that doesn't look like a statement to me. The production Y -> let A in Y is sufficient to allow a Y to be preceded by any number of let A in clauses. $\endgroup$ – rici Dec 19 '15 at 17:07
  • $\begingroup$ ...@saeedrobot: And that is why I said that Y->ε was unnecessary; by that I meant that it was unnecessary. Not that it could be factored out. I've now fixed the answer to more bluntly say that the production is wrong and should be eliminated. Not factored out. Deleted. Trashed. $\endgroup$ – rici Dec 19 '15 at 17:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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