3
$\begingroup$

I am trying to understand connection between non determinism of grammar and LL(1) conflicts introduced by it.

As per my understanding non deterministic context free grammar is a context free grammar in which at some point in time during parsing, multiple actions are allowed. Also I believe non determinism occurs when we have multiple productions in grammar with same prefix of production (right hand side) bodies. Also I know we eliminate non determinism by left factoring grammar.

Wikipedia article says:

  1. We do left factoring to eliminate FIRST-FIRST conflicts. ref
  2. Left recursion is a special case of FIRST-FIRST conflict. ref
  3. Substitution is used for removing FIRST-FOLLOW conflict. However that may introduce FIRST-FIRST conflict.ref
  4. Left recursion is eliminated using rule like below ref :
    $A\rightarrow A\alpha | \beta $
    ios converted to
    $A\rightarrow \beta A'$
    $A'\rightarrow \alpha A' | \epsilon$

I have following doubts:

  1. Since both non determinism and FIRST-FIRST conflicts are removed with left factoring and since left recursion is special case of FIRST-FIRST conflict, is non determinism a reason behind FIRST-FIRST conflict and left recursion (and also for FIRST-FOLLOW conflict)? If yes, does non determinism cause anything else and there is nothing else apart from these three (FIRST-FIRST conflict, left recursion and FIRST-FOLLOW conflict) in which non determinism manifests?

  2. Does the solutions (left factoring, substitution and left recursion removal rule) for removing above can also remove non determinism from all grammars?

  3. I know LL grammar should be both non deterministic and unambiguous. Does ambiguity also manifests in some way in LL parsing table or grammar? I read ambiguity can be eliminated by enforcing association and precedence between grammar symbols and this resolves SHIFT-REDUCE conflicts in LR parsers. Is anything like this required for eliminating ambiguity to make grammar a valid LL grammar?

Improve this question
$\endgroup$
1
  • $\begingroup$ "Does the solutions (left factoring, substitution and left recursion removal rule) for removing above can also remove non determinism from all grammars?" First, some languages are inherently non-deterministic. Whatever grammar is used to generated one of such languages, it will be non-deterministic grammar. (I am speaking loosely as non-determinism can have in-equivalent definitions.) Second, it is far from clear whether a grammar that generate a deterministic language can be transformed to a deterministic grammar by those three operations. $\endgroup$
    – John L.
    Jun 9, 2019 at 18:59

1 Answer 1

Reset to default
3
$\begingroup$

  1. No algorithm can remove non-determinism (or ambiguity) from every grammar, not even for every grammar for a language which has a deterministic grammar.

  2. Some deterministic grammars -- and even some deterministic context-free languages -- have no $LL$ parser. Such grammars are not necessarily ambiguous. An accurate deterministic parser obviously cannot be generated for an ambiguous grammar, but failure to generate a parser doesn't say anything about ambiguity.

  3. Yacc-style precedence/associativity declarations do not, in general, solve grammar ambiguity. But they do work for a couple of common simple cases (operator precedence, dangling else) allowing for the use of simpler grammars. That's handy in practice, but it's a very limited technique.

Improve this answer
$\endgroup$
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$
    – RajS
    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$
    – rici
    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$
    – rici
    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$
    – rici
    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$
    – rici
    Jun 16, 2019 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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