# Tag Info

Accepted

### Why are ambiguous grammars bad?

Consider the following grammar for arithmetic expressions: $$X \to X + X \mid X - X \mid X * X \mid X / X \mid \texttt{var} \mid \texttt{const}$$ Consider the following expression: $$a - b - c$$ ...
• 270k

### Why are ambiguous grammars bad?

In contrast to the other existing answers [1, 2], there is indeed a field of application, where ambiguous grammars are useful. In the field of natural language processing (NLP), when you want to parse ...
• 438
Accepted

### does every CFL have an ambiguous CFG?

Every nonempty context-free language has an ambiguous grammar. Consider any context-free grammar for the language with starting symbol $S$. We add new non-terminals $S',A',B'$, make $S'$ the new ...
• 270k
Accepted

### Is every unambiguous grammar regular?

The following grammar is unambiguous yet generates a non-regular language: $$S \to aSb \mid \epsilon$$
• 270k
Accepted

### How do I reconstruct the forest of syntax trees from the Earley vector?

I am using terminology and notations from Earley's paper. It is possible that the description you read is different. It seems frequent that general CF parsing algorithms are first presented in the ...
• 19.1k

### When is the concatenation of two regular languages unambiguous?

Hint: Given DFAs for $A$ and $B$, construct an NFA which accepts words in $AB$ having at least two different decompositions. The NFA keeps track of two copies of the standard NFA for $AB$ (formed by ...
• 270k

### Why are ambiguous grammars bad?

Even if there’s a well-defined way to handle ambiguity (ambiguous expressions are syntax errors, for example), these grammars still cause trouble. As soon as you introduce ambiguity into a grammar, a ...
• 1,121
Accepted

### unambiguous grammar that produce equal number of a and b

The problem with $S\to aSbS\mid bSaS\mid \varepsilon$ is that you're just making sure you match each $a$ with a $b$ (where we consider an $a$ and a $b$ to be matched iff they appeared during the same ...
• 1,227

### Why are ambiguous grammars bad?

Does IF a THEN IF b THEN x ELSE y mean IF a THEN IF b THEN x ELSE y or ...
• 80.2k

• 70.9k
Accepted

### Prove that regular expression is unambiguous

This answer has 3 parts: I first answer the question as asked, sketching the beginning of a proof concerning the example given. A full proof is too long and tedious to be given here. Then I give a ...
• 19.1k
Accepted

### Method for Creating Any Unambiguous Grammar?

No, and there is indeed a reduction to the undecidability of ambiguity. First, note that ambiguity is (for context-free grammars) semi-decidable: just keep generating words by different left-...
• 70.9k