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 $$ ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
12 votes
Accepted

Is every unambiguous grammar regular?

The following grammar is unambiguous yet generates a non-regular language: $$ S \to aSb \mid \epsilon $$
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 $...
user avatar
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} &= \...
user avatar
  • 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 ...
user avatar
  • 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. ...
user avatar
  • 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) ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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: ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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{...
user avatar
  • 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 ...
user avatar
  • 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. ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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-...
user avatar
  • 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 ...
user avatar
  • 19.1k

Only top scored, non community-wiki answers of a minimum length are eligible