Questions tagged [ambiguity]
Questions about ambiguity in context-free grammars.
113
questions
2
votes
2
answers
51
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 ...
- 21
0
votes
0
answers
59
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
262
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' →...
6
votes
1
answer
918
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 ...
- 12.5k
1
vote
2
answers
282
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{...
- 709
2
votes
1
answer
201
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 ...
- 23
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 ...
- 127
0
votes
1
answer
99
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?
- 3
1
vote
1
answer
373
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 "...
- 9,501
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
vote
1
answer
219
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 ...
- 11
1
vote
1
answer
101
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 ...
- 125
1
vote
2
answers
162
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?...
- 75
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?
- 1
2
votes
0
answers
64
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
3
votes
1
answer
81
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/...
- 31
1
vote
1
answer
611
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 ...
4
votes
1
answer
691
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 ...
- 151
0
votes
3
answers
526
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
41
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}
&...
2
votes
2
answers
903
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\}$.
1
vote
1
answer
366
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 + \, ...
- 37
1
vote
0
answers
494
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
67
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$...
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 ...
- 11
2
votes
0
answers
296
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,000
6
votes
1
answer
372
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
1
vote
1
answer
91
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 ...
- 597
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 ...
- 1,190
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.
- 1,190
0
votes
0
answers
111
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
215
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 ...
- 179
2
votes
1
answer
1k
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 ...
- 23
3
votes
1
answer
118
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 ...
- 31
1
vote
1
answer
321
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 ...
2
votes
1
answer
137
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 ...
- 345
0
votes
1
answer
140
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,...
- 15
3
votes
1
answer
166
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
1
vote
1
answer
544
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 ...
- 217
3
votes
1
answer
79
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
2
votes
1
answer
77
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 ...
- 21
2
votes
0
answers
69
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-...
- 141
0
votes
1
answer
852
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 ...
- 928
3
votes
2
answers
810
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 ...
- 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 ...
- 175
2
votes
1
answer
508
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?
- 695
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 ...
- 123
0
votes
0
answers
57
views
Is this grammar L4 ambiguous?
S-> AAB|ABA|BAA|epsilon
A->aS
B->bS
this is a grammar of the language L4 = {w ∈ Σ*: #a(w) = 2#b(w)} over Σ = {a, b}
Does the following examples shows that the L4 is ambiguous?
S->AAB->aSAB->aAB-...
- 51