Skip to main content
Computer Science

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

15
  • 1
    $\begingroup$ Thanks for 1st point. Was unaware of it. But are your 1,2,3 points answers to corresponding 1,2,3 points in my question? If yes, I am unable to get how. Specifically, I want confirmation for this: All FIRST-FOLLOW conflict, FIRST-FIRST conflict and left recursion contribute to non determinism. None of them directly contributes to ambiguity. $\endgroup$ Commented Jun 16, 2019 at 12:52
  • 1
    $\begingroup$ @anir: No. Non-determinism leads to parsing conflicts. Parsing conflicts are a symptom, not a cause, but they are not always a symptom of non-determinism, much less ambiguity. And there is no procedure which can reliably "remove conflicts". You are misreading your sources, probably because you insist on your own incorrect mental model. There are some techniques which you might be able to use to debug grammars, but nothing guarantees that they will work with every grammar. $\endgroup$ Commented Jun 16, 2019 at 15:48
  • 1
    $\begingroup$ It is correct to say that "non-determinism manifests as conflicts". I don't know why you feel so uncomfortable with that statement. A parsing conflict is not a feature of a grammar. Non-determinism is. $\endgroup$ Commented Jun 16, 2019 at 15:55
  • 1
    $\begingroup$ @anir: you're right; that was a mistake. If a CFG is deterministic then there is some $k$ for which an $LR(k)$ parser exists. The problem is that there is no way to find such a $k$ other than trying all of them. So if we run the LR algorithm with some value of $k$ and find a conflict, we don't know that the grammar is non-deterministic. It might be that we just need a larger $k$. $\endgroup$ Commented Jun 16, 2019 at 19:52
  • 1
    $\begingroup$ In that sense, the conflict is produced by the parsing table construction algorithm. A conflict produced in the construction of an LR(1) parse table might or might not be present in the construction of an LALR(3) table. (Just as an example.) Non-determinism, on the other hand, is a feature of the grammar (but not a computable feature). $\endgroup$ Commented Jun 16, 2019 at 19:57