Questions tagged [ambiguity]
Questions about ambiguity in context-free grammars.
114
questions
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), ...
- 506
1
vote
1
answer
530
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 "...
CommunityBot
- 1
3
votes
2
answers
95
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/...
- 314
2
votes
2
answers
89
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 ...
- 353
0
votes
0
answers
87
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)....
- 1
1
vote
1
answer
408
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' →...
D.W.♦
- 159k
1
vote
2
answers
3k
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 ...
6
votes
1
answer
922
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 ...
- 30.6k
1
vote
2
answers
360
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{...
- 12k
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 ...
- 39k
2
votes
1
answer
209
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 ...
- 12k
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 ...
- 1
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?
- 15.5k
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....
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 ...
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 ...
- 1,035
1
vote
1
answer
228
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 ...
D.W.♦
- 159k
1
vote
1
answer
112
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 ...
D.W.♦
- 159k
1
vote
2
answers
176
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?...
- 277k
0
votes
0
answers
34
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?
- 277k
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 <...
- 121
1
vote
1
answer
679
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 ...
- 277k
6
votes
1
answer
830
views
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?
I came across a very hard interview question in last month’s Ph.D. entrance exam. It was asking which one of the languages is inherently ambiguous. Short answer says 2). Why is the language in 2) an ...
- 277k
4
votes
1
answer
699
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 ...
- 277k
0
votes
3
answers
551
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":
"...
- 119
0
votes
0
answers
43
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}
&...
- 277k
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\}$.
- 39k
1
vote
1
answer
407
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 + \, ...
- 277k
-2
votes
2
answers
7k
views
Ambiguous Grammar to Unambiguous Grammar
I'm wondering if somebody can please help me to understand how I go about converting this grammar to an unambiguous grammar. If you can point me in the right direction, I would greatly appreciate it.
...
- 7,455
1
vote
0
answers
508
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 ...
- 11
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$...
- 4,474
2
votes
0
answers
311
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 ...
- 3,040
6
votes
1
answer
377
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 ...
- 183
0
votes
1
answer
11k
views
How to find whether a grammar is ambiguous?
$$S\rightarrow aAB$$
$$A\rightarrow bBb$$
$$B\rightarrow A|\epsilon$$
I'm choosing the string abbbb.
First left most derivation is the following:
$$S\Rightarrow aAB\Rightarrow abBbB\Rightarrow ...
- 11
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 ...
- 2,082
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 ...
CommunityBot
- 1
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.
- 448
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, ...
- 179
0
votes
1
answer
227
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 ...
- 12k
3
votes
2
answers
866
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 ...
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 ...
- 277k
3
votes
1
answer
123
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 ...
- 277k
1
vote
1
answer
383
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 ...
CommunityBot
- 1
2
votes
1
answer
147
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 ...
- 72.4k
2
votes
4
answers
1k
views
How to prove that Ambiguity is still present in Resolved Production of Dangling Else Problem?
$\textbf{stmt} \to$ $ \textbf{if} $expr$ \textbf{then}$ stmt
$\mid $ $\textbf{if}$ expr $ \textbf{then}$ stmt$ \textbf{else}$ stmt
$\mid \textbf{...
- 530
3
votes
1
answer
171
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 ...
- 101
0
votes
1
answer
150
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,...
- 12k
2
votes
1
answer
79
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 ...
CommunityBot
- 1
0
votes
2
answers
430
views
Grammar ambiguous or not?
So I've been struggling for the past hour with $G=(\{S\},\{a,b\},P,S)$ with productions $S\to aaSb | abSbS | \varepsilon$. I need to prove whether this grammar is ambiguous or not. Thus far I think it ...
- 39
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 ...
- 227