57
votes
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
$$
...
- 274k
13
votes
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
13
votes
Accepted
Is every unambiguous grammar regular?
The following grammar is unambiguous yet generates a non-regular language:
$$ S \to aSb \mid \epsilon $$
- 274k
11
votes
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,211
10
votes
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 ...
- 274k
9
votes
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,245
9
votes
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
...
- 81.4k
9
votes
Are these special (one production) Context-Free Grammars always unambiguous?
Here is a simple counter example:
$S \rightarrow aSbSaSbS \space |\space \epsilon$
and string $w: abababab.$
In one case we use last $S$ and in other case we use second $S$. All other $S$ goes to $...
- 597
8
votes
When is the concatenation of two regular languages unambiguous?
Updated (thanks to Yuval Filmus).
Given two languages $X$ and $Y$ of $A^*$, let
\begin{align}
X^{-1}Y &= \{u \in A^* \mid \text{there exists $x \in X$ such that $xu \in Y$} \} \\
YX^{-1} &= \...
- 5,944
8
votes
How to find unambiguous grammar for palindromes
First, I believe you are looking for a different word than 'unambiguous'. A grammar is ambiguous if some string in its language has two or more derivations; I'm sure that a palindromic string must ...
- 81
8
votes
Accepted
Language of ambiguous words
The standard example that context-free languages are not closed under intersection can also be used as a counter-example for the language of ambiguous words.
Construct unambiguous grammars for $\{ a^n ...
- 29.6k
7
votes
Accepted
Is there a different resolution of the "dangling else" problem other than "match closest"?
This problem is an exact analogue of the problem of matching parentheses in an expression in which some of the close parentheses have been omitted. Here an "if" (or $a$ in the representative grammar) ...
- 11.8k
7
votes
How to prove that a grammar is unambiguous?
For some grammars, a proof by induction (over word length) is possible.
Consider for example a grammar $G$ over $\Sigma = \{a,b\}$ given by the following rules:
$\qquad \displaystyle S \to aSa \mid ...
- 71.9k
6
votes
Why are ambiguous grammars bad?
Take the most vexing parse in C++ for example:
bar foo(foobar());
Is this a function declaration foo of type ...
- 4,276
6
votes
Why are ambiguous grammars bad?
I think the question contains an assumption that's only borderline correct at best.
In real life it's pretty common to simply live with ambiguous grammars, as long as they aren't (so to speak) too ...
- 711
5
votes
Accepted
How to eliminate context-free grammar's ambiguity
There is no general trick — indeed, given a context-free grammar, it is undecidable to determine whether it is ambiguous or not, and it is also undecidable to determine whether the language it ...
- 274k
5
votes
Accepted
How to make an unambigous grammar of a programming language
Grammars of real programming languages are often more restricted than CFG in order to enable efficient parsing. You may have heard of LL(k) and LR(k) grammars, for instance. All these grammars are, by ...
- 71.9k
4
votes
Big Oh vs Big Theta
A (sloppy) upper bound is easier to prove than a tight upper bound, let alone upper and lower bounds.
Some algorithm's runtime can't be given with the same function as upper/lower bound. E.g. simple ...
- 13.9k
4
votes
Accepted
How to find whether a grammar is ambiguous?
Since you are trying to prove that the grammar is ambiguous, you must simply provide an example of a string where that grammar results in more than one parse tree or derivation. (Note that this is an ...
- 156
4
votes
How to prove that Ambiguity is still present in Resolved Production of Dangling Else Problem?
A grammar $G$ for a language $L$ is ambiguous if there is a string $w \in L$ which has two different parse trees (with respect to $G$). Hence in order to show that ambiguity is still present, all you ...
- 274k
4
votes
Accepted
How to check for ambiguous grammar if you don't know the string
You cannot tell that a context-free grammar is ambiguous, since the problem is undecidable. This can be proved by a straightforward reduction from the Post correspondence problem, for example. What ...
- 274k
4
votes
Accepted
Why postfix arithmetic expression is not ambiguous?
With operator precedence infix is not ambiguous. Brackets are a convenience but not necessary to form an expression. However when parsing you have to resolve each precedence level in precedence ...
- 206
4
votes
Accepted
CFLs are inherently unambiguous?
Every non-empty context-free language has an ambiguous grammar. Indeed, take any context-free grammar for the language, and add to it the production $S \to S$ (if it is not already there), where $S$ ...
- 274k
4
votes
unambiguous context-free languages and complementation
Both questions turn out to have negative answers, as shown in [this][1] article.
In particular, the authors construct
An unambiguous context-free language whose complement is not context-free.
An ...
- 101
4
votes
How is `y λx.x y` parsed using the standard pure untyped lambda calculus conventions?
The left associativity of applications is only relevant when you have a sequence of applications. If it were correct to interpret y λx.x y as ...
- 1,963
4
votes
Proving that $X\to aX|Y$, $Y \to Yab|b$ is unambiguous
First, figure out what the language is.
Then, try to do a few examples of productions in the grammar. What do you notice about the derivation trees and sequences? How would this help you to prove this ...
- 11.5k
3
votes
Accepted
Finding a unambiguous grammar
You can get an unambiguous grammar by thinking of words in $L$ as walks that start and end on the Y axis; each $a$ corresponds to a move $\nearrow$, and each $b$ corresponds to a move $\searrow$. Each ...
- 274k
3
votes
Accepted
Explanation of Grammar Ambiguity
A grammar $G$ is non-amgibuous if every word in $L(G)$ has a unique parse tree. The simplest way to prove that your grammar non-ambiguous is to prove that $L(S + S),L(S * S),L(a)$ are all distinct (...
- 274k
3
votes
Accepted
Are linear languages always unambiguous?
The linear language $\{ a^ib^jc^k \mid i=j \text{ or } j=k\}$ is inherently ambiguous.
- 29.6k
3
votes
Accepted
Duplicating the quotation marks in in the quotation-mark enclosed strings
Just replace " in the list of possible characters with "".
That might have consequences for other grammar productions which use the same non-terminals, in which case you might need to separate ...
- 11.8k
Only top scored, non community-wiki answers of a minimum length are eligible