Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more

Questions tagged [ambiguity]

Questions about ambiguity in context-free grammars.

Filter by
Sorted by
Tagged with
15 votes
2 answers
4k views

How do C compilers distinguish casting from grouping?

In the C language, there's the 2 similar-in-form but distict-in-meaning constructs: (type)value which is a casting, and (value), ...
DannyNiu's user avatar
  • 352
2 votes
2 answers
124 views

Derivation trees to show a given grammar is ambiguous

Given the grammar with productions: \begin{align} S \rightarrow aSb \mid SS \mid \lambda\\ \end{align} I would like to show that it is ambiguous. As I understand it, if you can show that some string ...
cpf9231's user avatar
  • 21
0 votes
0 answers
91 views

Methods of eliminating ambiguity in CFG

I am looking for all possible ways to find and eliminate ambiguity in CF grammar. Please share your knowledge or opinion (preferably you will indicate the literature so that I can familiarize myself)....
gendalin's user avatar
1 vote
1 answer
465 views

How to remove ambiguity from the grammar?

I want to remove ambiguity from the grammar below: S → ABC A → abA | ab B → b | BC C → c | cC I have removed left recursion and left factoring and obtained the grammar as follows: S → ABC A → abA' A' →...
Luna Insorita's user avatar
6 votes
1 answer
923 views

Language of ambiguous words

Consider an ambiguous context-free grammar $G$. Define $A(G)$ the set of ambiguous words, meaning: $$A(G) = \{u\in L(G) \mid u \text{ has at least two derivation trees for }G\}$$ Can we say something ...
Nathaniel's user avatar
  • 15.7k
1 vote
2 answers
390 views

How to disambiguate CFG with unary/binary minus and binary prefix operator

I'm designing an expression language that's trying to (a) be maximally compatible with a different ambiguous language; and (b) be LR(1). I'm facing the current fragment of the language: $$ \begin{...
Jonas Kölker's user avatar
2 votes
1 answer
217 views

Prove/find context free grammar is unambiguous for the language $L$

I am trying to find a grammar and prove that it is unambiguous for the language $L$, where $$L = \{ w \in \{a,b\}^+; |w|_a = |w|_b \} $$ Essentially: word $w$ contains at least one $a$ and $b$; where ...
Visor450's user avatar
1 vote
2 answers
4k views

Proving the grammar S → SS+ | SS∗ | a is unambiguous

Consider the context-free grammar G = ({a, +, ∗}, {S}, {S → SS+ | SS∗ | a}, {S}) and consider the string aa+a* generated by this grammar. Is this grammar unambiguous? I have browsed the Internet and I ...
Charlie's user avatar
  • 127
0 votes
1 answer
106 views

Any context-free grammar generating a regular language is unambiguous

I am not sure whether this statement is true or not. Could there be an example of CFG generating a regular language and is ambiguous?
yemen's user avatar
  • 3
1 vote
1 answer
564 views

How to prove that this "priority" strategy (in ANTLR4) solves the "dangling-else" ambiguity?

As shown in this post @ stackoverflow, ANTLR4 seems able to resolve the "dangling-else" ambiguity @ wiki in the following "if-then-else" grammar by prioritizing the "...
hengxin's user avatar
  • 9,561
0 votes
0 answers
39 views

how ambiguity of following grammar cant be decidable?

SO According to question grammar should be like this (A -> AA ). ->So i learn that if grammar is left and right recursive both then that grammar must be ambiguous but here the answer is deferent....
Lucifer The devil's user avatar
0 votes
1 answer
1k views

Can a grammar that has only one leftmost derivation tree for every sentence, have more than one rightmost derivation tree for some sentence?

I'm currently studying the book Engineering a Compiler by Keith Cooper, and in chapter 3, there is the following definition: A grammar G is ambiguous if some sentence in L(G) has more than one ...
Angelo Marcelino's user avatar
4 votes
1 answer
39 views

What is the primary reference for the observation/discussion of how neural networks struggle with ambiguous training datasets?

It is known that neural networks, such as convolutional neural networks, struggle with pattern recognition if training sets contain ambiguities (i.e. several labels can correspond to one and the same ...
Capo Mestre's user avatar
1 vote
1 answer
239 views

Prove that the language generated by the grammar $S \to SxS \mid a$ is inherently ambiguous

With the following grammar: $$S \to SxS \mid a$$ Is L(G) inherently ambiguous? What is the proof? I know how to prove the grammar is ambiguous but I don't know how to prove if the grammar is ...
Otávio Reis's user avatar
1 vote
1 answer
113 views

Parse forest from an ambiguous grammar

Parser-generators like nearleyjs can return a parse forest instead of a parse tree. Since not all input may result in a parse forest (eg, the input may exercise ...
Harry's user avatar
  • 125
1 vote
2 answers
181 views

Proving that $X\to aX|Y$, $Y \to Yab|b$ is unambiguous

Prove that the following grammar is unambiguous: $$X \to aX | Y$$ $$Y \to Yab | b$$ I know that I must prove that the strings produced by this grammar have only one parse tree, but how can I do this?...
hermi's user avatar
  • 75
0 votes
0 answers
35 views

How to change a grammar so that it can be unambiguous?

The original grammar is $$ S \to SaS \mid SbS \mid ScS \mid d $$ My answer is $$ S \to daS \mid dbS \mid dcS \mid d $$ Is that correct?
Derican's user avatar
2 votes
0 answers
68 views

Unparsing an operator grammar in the face of ambiguity

I'm using the grammar scheme of Danielsson and Norell ("Parsing Mixfix Operators"). The short version is: user defined mixfix operators such as _+_ or <...
Maya's user avatar
  • 121
3 votes
2 answers
96 views

How is `y λx.x y` parsed using the standard pure untyped lambda calculus conventions?

How would the following term in the pure untyped lambda calculus be parsed: y λx.x y The relevant conventions listed on https://en.wikipedia.org/wiki/...
digilante's user avatar
1 vote
1 answer
702 views

Given a CFG G (in Chomsky normal form) and a string w, determine whether w has more than one parse tree in G in polynomial time

So I have the following language: C = {<G,w>|G is a CFG in Chomsky normal form and w has more than one parse tree in G} How to prove that this language is in P (decidable in deterministic ...
Ronen Hanukayev's user avatar
4 votes
1 answer
701 views

Is every unambiguous grammar regular?

While searching for an answer to this question I found out that there is an unambiguous grammar for every regular language. But is there a regular language for every unambiguous grammar? How can I ...
Jake Wright's user avatar
0 votes
3 answers
563 views

Big O vs Big $\Theta$ during coding interview

Almost every time I see an article about time or space complexity, people are expressing the complexity with Big O, whereas it should be $\Theta$. From the book "Cracking the coding interview": "...
Hugh's user avatar
  • 119
0 votes
0 answers
44 views

Making context-free grammar unambiguous

I'm trying to change below context free grammar such that it becomes unambiguous, but I don't know what steps I should take. Is there any specific way of doing that? Here is my CFG: \begin{align} &...
Mohammad Derakhshan's user avatar
2 votes
2 answers
1k views

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

I have designed this Grammar but it is ambiguous: $$S\to aSbS \mid bSaS \mid aS \mid\epsilon$$ Would anyone help me make it unambiguous? Assume the alphabet is $\{a,b\}$.
Daniyal Qureshi's user avatar
1 vote
1 answer
422 views

Is grammar that describes an equation in prefix (Polish) notation always unambiguous?

I recently completed a problem in which I was asked to generate a parse tree for the expression $+ \, 5 \, * \, 4 \, 3$ using the following grammar and rightmost derivation: $$Expr \rightarrow + \, ...
Goya's user avatar
  • 37
1 vote
0 answers
515 views

Chomsky Normal Form for context free grammars ambiguous/unambiguous properties?

My textbook states: Finally, it must be stressed that the Chomsky normal form says nothing about ambiguity in general—a CFG in Chomsky normal form may or may not be ambiguous, just like we have for ...
ronaldlu's user avatar
0 votes
1 answer
69 views

Ambiguous Grammar demostration exercise

Hi im stuck on an exercise of ambiguous grammar. I need an example that shows that this grammar is ambiguous. The grammar is defined as follows: $$S \rightarrow aT | bR$$ $$R \rightarrow a | aS | bRR$...
Sebas Belaustegui's user avatar
1 vote
1 answer
1k views

Convert ambiguous grammar to unambiguous and SLR(1)

I have the following ambiguous operator grammar: E->E+E*E | E-E*E E->E+E | E-E | E+E | E*E | E/E E->(E) | x I must convert it to an unambiguous one ...
Nikos 's user avatar
  • 11
2 votes
0 answers
312 views

Proper algorithm for resolving ambiguity in grammars via enforcing associativity and precedence rules

I was told there is a algorithm that always resolves ambiguity for grammars that have issues with precedence and associativity. I know ambiguity in general is undecidable, so I only want to resolve ...
Charlie Parker's user avatar
6 votes
1 answer
378 views

Are these special (one production) Context-Free Grammars always unambiguous?

Consider the following (Context-Free) Grammars with only one production rule (not including the epsilon production): $S \rightarrow aSb\;|\;\epsilon$ $S \rightarrow aSbS\;|\;\epsilon$ $S \rightarrow ...
meci's user avatar
  • 183
1 vote
1 answer
92 views

Is following grammar has language which is inherently ambiguous?

Grammar is as follow: $S \rightarrow aaAb | aab | A$ $A \rightarrow aaAb | aAb | \epsilon$ I think that this grammar has equivalent unambiguous grammar as follow. Let’s first rewrite the grammar ...
Vimal Patel's user avatar
0 votes
1 answer
1k views

Why ambiguous grammars are allowed for operator precedence parser?

I am aware of what is ambiguity, and why is it necessary to eliminate ambiguity in compilers in a certain context, but how can we allow ambiguity for operator precedence parser? Say I have a set of ...
Turing101's user avatar
  • 1,200
31 votes
6 answers
10k views

Why are ambiguous grammars bad?

I understand that if there exist 2 or more left or right derivation trees, then the grammar is ambiguous, but I am unable to understand why it is so bad that everyone wants to get rid of it.
Turing101's user avatar
  • 1,200
0 votes
0 answers
122 views

Is there any grammar parseable by LALR(1) but not LR(1)?

https://en.wikipedia.org/wiki/LALR_parser - as far as I understand, LALR(1) is a simplified version of LR(1), aiming to achieve a greater parsing performance at the expense of reduced power. So, IIUC, ...
gaazkam's user avatar
  • 179
0 votes
1 answer
228 views

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

There is no algorithm that, given an arbitrary grammar, decides if it's ambiguous or not. However, Are there any sufficient conditions that make it easier to tell that a grammar is unambiguous? For ...
gaazkam's user avatar
  • 179
2 votes
1 answer
2k views

Finding an unambiguous grammar of a language provided by a CFG

I'm working through 'Intro to Automata Theory, Language and Computation' 2nd edition by Hopcroft, Motwani & Ullman. In section 5.4, exercise 5.4.3 I am tasked with finding an unambiguous grammar ...
Denzak's user avatar
  • 23
3 votes
1 answer
126 views

Equivalent unambiguous grammar

Given the grammar: $S \to AS\mid \varepsilon$ $A \to A1\mid 0A1 \mid \varepsilon$ Generate a new unambiguous grammar that generates the same language as the grammar above. I have no idea how to ...
Sarah's user avatar
  • 31
1 vote
1 answer
392 views

Is there any relationship between grammar being ambiguous and the language itself?

According to my understanding, a grammar is ambiguous if it generate strings which can be interpreted in more than one ways ( that is , more than one parse tree), but when it comes to the language ...
Mathews George's user avatar
2 votes
1 answer
148 views

How to make an unambigous grammar of a programming language

We know that the decision problem of whether an arbitrary context-free grammar is ambiguous is undecidable. My question is how are made the unambigous grammar of programming language? My guessing is ...
asv's user avatar
  • 345
0 votes
1 answer
153 views

How to eliminate ambiguity of the follwing CFG?

Consider the following CFG: $S\to AED | F \\ A \to Aa | a\\ B \to Bb | b\\ C \to Cc | c\\ D \to Dd | d\\ E \to bEc | bc\\ F \to aFd | BC$ The CFG produces $a^*bbb...ccc...d^*$ (equal number of b,...
Nyte_Sorrow's user avatar
3 votes
1 answer
174 views

unambiguous context-free languages and complementation

I was considering the following two natural questions about the relationship between unambiguity and complementation for the class of context-free languages: Is the complement of an unambiguous ...
Lorenzo's user avatar
  • 101
1 vote
1 answer
554 views

Convert ambiguous grammar $S \to 01S1\mid SS\mid\epsilon$ to unambiguous grammar

Given the ambiguous CFG : $ S \to 01S1\mid SS\mid\epsilon $ I came up with the following CFG which I think is unambiguous: $S \to 01X \mid 011X$ $X \to 01X1 \mid \epsilon$ Is my CFG unambiguous and ...
hsnsd's user avatar
  • 217
3 votes
1 answer
83 views

CFLs are inherently unambiguous?

As reading the textbook of Introduction to the theory of computation_third edition - Michael Sipser, which have the concept that we call a context-free language L inherently unambiguous if there does ...
Maxfield's user avatar
  • 227
2 votes
1 answer
80 views

unambiguous equivalent grammar

There is a grammar G given: S->XaX X->aX|bX|eps I just replied to the first question that was ...
Annie's user avatar
  • 21
2 votes
0 answers
70 views

Examples of context-free grammars whose ambiguity is unknown

Are there any examples of context-free grammars for which we simply do not know whether they are ambiguous? By examples I mean an actual specification for the grammar, not some kind of non-...
Tob Ernack's user avatar
0 votes
1 answer
904 views

Why postfix arithmetic expression is not ambiguous?

A binary tree can be written as an expression, no matter prefix, postfix or infix. But why an infix expression needs brackets, while the others don't? Say, why postfix, prefix produce only one binary ...
ice1000's user avatar
  • 940
3 votes
2 answers
873 views

How to check for ambiguous grammar if you don't know the string

Let's say I have a CFG grammar $G$ which describes some rules for language generation. How can you tell that grammar can generate ambiguous results for a string if you don't know that string? I know ...
Sigma's user avatar
  • 685
4 votes
1 answer
4k views

How to eliminate context-free grammar's ambiguity

I want to write a CFG that generates the words over {a,b} with the same number of ocurrences of a's and b's. I have come up with a couple of possibilties so far. I think they're correct but they're ...
clvr_bottle's user avatar
2 votes
1 answer
527 views

Are linear languages always unambiguous?

Deterministic Context free languages are always unambiguous. Now DCFL are a subset of linear languages. Are there any linear languages which are inherently ambiguous?
Kishan Kumar's user avatar
2 votes
1 answer
1k views

Is this unambiguous grammar equivalent?

I have a simple context free grammar $(\{A\}, \{(,)\}, R, A)$, which consists of this one production rule: $A \rightarrow AA\, \vert\, (A)\, \vert\, \epsilon$ I believe this is ambiguous! For ...
Adam Williams's user avatar