Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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
22 votes
Accepted

How do C compilers distinguish casting from grouping?

It's not possible for an LR(1) parser to solve this problem without using the Lexer Hack: information from the symbol table, which is able to differentiate type names from variable names, is reported ...
Scott McPeak'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
  • 448
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
12 votes

How do C compilers distinguish casting from grouping?

They can easily be distinguished by a compiler: In the first case, the thing in parentheses is a type, in the second case it isn’t. Now if you insist on parsing based on a grammar only, that may be a ...
gnasher729's user avatar
  • 30.4k
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,241
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,255
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

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
  • 30.8k
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
  • 12k
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 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
  • 72.5k
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
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
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

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

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

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
  • 2,157
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.6k
3 votes
Accepted

What are the sufficient conditions for a grammar to be unambiguous?

If you can construct a deterministic parser corresponding to a grammar, then the grammar is clearly the unambiguous. (If it were ambiguous, there would need to be a point in some parse which admitted ...
rici's user avatar
  • 12k
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
  • 30.8k
3 votes

Why ambiguous grammars are allowed for operator precedence parser?

An operator precedence parser usually has no ambiguity at all. However, the evaluation order is not determined by the parse tree, but by the operator precedences and associativities. As a practical ...
gnasher729's user avatar
  • 30.4k
3 votes

Unambiguous context-free grammar for strings with at least as many a's as b's

Let us replace $a$ with $\nearrow$ and $b$ with $\searrow$. Given a sequence of arrows, we construct a "walk" in which each arrow's tail starts from the preceding arrow's head. We keep track of the ...
Yuval Filmus's user avatar

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