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 $$ ...
Yuval Filmus's 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 ...
ComFreek's user avatar
  • 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 $$
Yuval Filmus's user avatar
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 ...
Davislor's user avatar
  • 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 ...
Yuval Filmus's user avatar
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 ...
xavierm02's user avatar
  • 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 ...
David Richerby's 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 $...
Vimal Patel's 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} &= \...
J.-E. Pin's user avatar
  • 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 ...
PMar's user avatar
  • 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 ...
Hendrik Jan's user avatar
  • 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) ...
rici's user avatar
  • 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 ...
Raphael's user avatar
  • 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 ...
ratchet freak's 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 ...
Jerry Coffin's user avatar
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 ...
Yuval Filmus's 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 ...
Raphael's user avatar
  • 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 ...
vonbrand's user avatar
  • 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 ...
rudolph1024's user avatar
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 ...
Yuval Filmus's user avatar
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 ...
Yuval Filmus's user avatar
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 ...
Craig  Hicks's user avatar
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$ ...
Yuval Filmus's user avatar
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 ...
Lorenzo's user avatar
  • 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 ...
benrg's user avatar
  • 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 ...
nir shahar's user avatar
  • 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 ...
Yuval Filmus's user avatar
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 (...
Yuval Filmus's user avatar
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.
Hendrik Jan's user avatar
  • 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 ...
rici's user avatar
  • 11.8k

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