<p>I test simple (toy) grammars and check if they are ambiguous by generating all possible sequences derived from start symbol, but limited to maximum length (for example 12). It is not practical for real grammars like Java language and it tests ambiguity grammar but does not say which production rules cause ambiguity.
Known example of ambiguity is 'dangling else'.</p>
<pre><code>S -&gt; i b t S e S
S -&gt; i b t S
S -&gt; s
</code></pre>
<p>After transformation to LL:</p>
<pre><code>S -&gt; i b t S S1
S -&gt; s
S1 -&gt; e S
S1 -&gt; 
</code></pre>
<p>There are grammars that solve the dangling else problem, are not ambiguous, but are not (after transformation) LL(k):</p>
<pre><code>S -&gt; i e t S
S -&gt; i e t W e S
S -&gt; o
W -&gt; i e t W e W
W -&gt; o
</code></pre>
<p>second:</p>
<pre><code>S -&gt; M
S -&gt; U
M -&gt; i e t M e M
M -&gt; o
U -&gt; i e t S
U -&gt; i e t M e U
</code></pre>
<p>If the solution to the ambiguity conflict was to always choose one rule, then conflicts will occur in unambiguous grammars, both those that are not LL(k) and those that are, and k is larger than the attempt to construct the LL table.
How to check if the grammar is ambiguous and distinguish from unambiguous not LL(k) for any k or k fixed? What to do in case of ambiguity?</p>
<p>Edit:</p>
<p>An interesting type of ambiguity, and difficult to avoid, is the type that can be described as variations on the theme of &quot;dangling else&quot;:
the case when we have two productions, one of which is a prefix of the other, and these productions &quot;call&quot; each other (not necessarily directly) recursively. Then it makes sense to forbid the situation where the long form expanded from the short form at a lower level, the other cases : short - short, long - long, short - long - are allowed; this is a sensible choice, because the opposite choice would cause an error if a limiting token like 'else' appeared, which was not assumed at the time of development. Yes, there can be unlimited other types of ambiguity, but they are not necessary when constructing a typical language.</p>

<grammar><ambiguity>
How to detect and resolve ambiguous grammars?
CC BY-SA 4.0
2024-11-06T22:15:31.470Z
Are you asking "is there an algorithm for the function which takes *any* grammar as its input and is *guaranteed* to return true if the grammar is unambiguous and false if ambiguous?"  Because no, there is no such algorithm. If you are asking for tips and tricks for finding ambiguities in *some* grammars but not others, please clarify the question to say more about what you're trying to do.
Eric Lippert
CC BY-SA 4.0
2024-11-06T22:26:06.857Z
FYI a short proof that "is this CFG ambiguous?" is undecidable can be found here: https://cstheory.stackexchange.com/questions/4352/how-is-proving-a-context-free-language-to-be-ambiguous-undecidable
Eric Lippert
CC BY-SA 4.0
2024-11-07T23:15:59.753Z
In practice, if you can't prove your grammar unambiguous, then it's probably complicated enough to be confusing to users even if it is unambiguous.
kaya3
# How to detect and resolve ambiguous grammars?
Posted by: username_0 on 2024-11-06
I test simple (toy) grammars and check if they are ambiguous by generating all possible sequences derived from start symbol, but limited to maximum length (for example 12). It is not practical for real grammars like Java language and it tests ambiguity grammar but does not say which production rules cause ambiguity.
Known example of ambiguity is 'dangling else'.
S -> i b t S e S
S -> i b t S
S -> s

After transformation to LL:
S -> i b t S S1
S -> s
S1 -> e S
S1 -> 

There are grammars that solve the dangling else problem, are not ambiguous, but are not (after transformation) LL(k):
S -> i e t S
S -> i e t W e S
S -> o
W -> i e t W e W
W -> o

second:
S -> M
S -> U
M -> i e t M e M
M -> o
U -> i e t S
U -> i e t M e U

If the solution to the ambiguity conflict was to always choose one rule, then conflicts will occur in unambiguous grammars, both those that are not LL(k) and those that are, and k is larger than the attempt to construct the LL table.
How to check if the grammar is ambiguous and distinguish from unambiguous not LL(k) for any k or k fixed? What to do in case of ambiguity?
Edit:
An interesting type of ambiguity, and difficult to avoid, is the type that can be described as variations on the theme of "dangling else":
the case when we have two productions, one of which is a prefix of the other, and these productions "call" each other (not necessarily directly) recursively. Then it makes sense to forbid the situation where the long form expanded from the short form at a lower level, the other cases : short - short, long - long, short - long - are allowed; this is a sensible choice, because the opposite choice would cause an error if a limiting token like 'else' appeared, which was not assumed at the time of development. Yes, there can be unlimited other types of ambiguity, but they are not necessary when constructing a typical language.
**Tags:** grammar ambiguity
> **Comments:**
> **username_1**: Are you asking "is there an algorithm for the function which takes *any* grammar as its input and is *guaranteed* to return true if the grammar is unambiguous and false if ambiguous?"  Because no, there is no such algorithm. If you are asking for tips and tricks for finding ambiguities in *some* grammars but not others, please clarify the question to say more about what you're trying to do.  
> **username_1**: FYI a short proof that "is this CFG ambiguous?" is undecidable can be found here: https://cstheory.stackexchange.com/questions/4352/how-is-proving-a-context-free-language-to-be-ambiguous-undecidable  
> **username_2**: In practice, if you can't prove your grammar unambiguous, then it's probably complicated enough to be confusing to users even if it is unambiguous.  
---
## 0 answers
