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
$$
...
- 270k
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
12
votes
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
12
votes
Accepted
Is every unambiguous grammar regular?
The following grammar is unambiguous yet generates a non-regular language:
$$ S \to aSb \mid \epsilon $$
- 270k
10
votes
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
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 ...
- 270k
10
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,121
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,227
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
...
- 80.2k
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 $...
- 577
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,924
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
7
votes
Accepted
Can there be two different left most derevations for a grammar?
A leftmost derivation of a string in the language defined by a
grammar $G$ characterizes a parse-tree for that string. It is a way of
describing the parse tree, which is unique for each parse tree.
...
- 19.1k
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.3k
6
votes
does every CFL have an ambiguous CFG?
The following statement seems mathematically correct, though confusing.
Any grammar for the empty language $\varnothing$ is unambiguous: it has no strings for which there are two different valid ...
- 27.6k
6
votes
Accepted
Context-free grammars and priority
You are correct that additions operator is produced first when you
derive. But when you parse, you do the opposite (reduction), and the
multiplications are recognized first, wich is precisely what you ...
- 19.1k
6
votes
Accepted
Why is $\{a^n b^m c^p: n\neq m\} \cup \{a^n b^m c^p: m\neq p\}$ an inherently ambiguous language?
If $L_1,L_2$ are two disjoint context-free languages which are not inherently ambiguous, then $L_1 \cup L_2$ is also a context-free language which is not inherently ambiguous. The reason is simple: ...
- 270k
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,108
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
Ambiguous context free
Your question is strange. If you do not know what kind of language you
have, the question may well be meaningless, as the concept of
ambiguity can only be defined with respect to a known system of
...
- 19.1k
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 ...
- 270k
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 ...
- 70.9k
4
votes
Accepted
Show that every grammar for an inherently ambiguous CFL has infinitely many ambiguities
Intuitively, the reason the claim is true is that if a grammar $G$ had only finitely many ambiguous strings, then you could somehow resolve the ambiguity and come up with an equivalent unambiguous ...
- 270k
4
votes
Accepted
Help me find the ambiguity in this grammar
$$S \xrightarrow{} SS \xrightarrow{} SSS \xrightarrow{} TSS \xrightarrow{} abSS \xrightarrow{} abTS \xrightarrow{} ababS \xrightarrow{} ababT \xrightarrow{} ababab$$
$$S \xrightarrow{} SS \xrightarrow{...
- 11.3k
4
votes
parsing at semantic level due to ambiguities
There is no reason to "distinguish between value_expression and
type_conversion" since, according to the grammar a type_conversion is
a value_expression.
You probably mean to distinguish between ...
- 19.1k
4
votes
Accepted
Ambiguous Grammar to Unambiguous Grammar
First, there is a difference between a language and a grammar. A language is just a set of strings, while a grammar is a way to specify such languages. The attribute "ambiguous" applies to grammars. ...
- 1,090
4
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 ...
- 70.9k
4
votes
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
4
votes
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
4
votes
What techniques can I use to hand-write a parser for an ambiguous grammar?
I did not read in detail your grammar which is far too large for my
available time, and short of an example that you should provide (since you
assert it is ambiguous) I will not not attempt to check ...
- 19.1k
Only top scored, non community-wiki answers of a minimum length are eligible