If it is possible to construct an SLR parse table with no conflicts for a particular grammar does that mean that the grammar is unambiguous?

I think that since we have constructed the parse table which means for every sentence we would be able to decide whether the string will be accepted or not. But I am a little bit confused on whether it is really true or not. Actually, I am trying to prove that a grammar is unambiguous and I constructed parse table with no conflicts.

  • $\begingroup$ It seems that you are correct. $\endgroup$ – Yuval Filmus Feb 6 '19 at 12:32

As said in the comment by Yuval, an SLR parse table with no conflicts (or parsing deterministic finite automaton) for a particular grammar implies that the grammar is unambiguous.

In fact, that is true for most if not all popular parsing methods.

  • LL(k)
  • LR(k)
  • SLR(k)
  • LALR(k)

Here is the sketch of a proof for all parsing methods. A parse table or a parsing finite automaton specifies an algorithm to produce all leftmost derivations (or rightmost derivations) of the input sentence. If there is no conflict in the parse table or the finite automaton is deterministic, only one derivation can be generated. That means the grammar is unambiguous.

Note for a given sentence, there is only one leftmost derivation is equivalent to there is only one rightmost derivation.

| cite | improve this answer | |

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.