Questions tagged [ambiguity]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
29
votes
6answers
6k 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.
23
votes
4answers
19k views

How to prove that a grammar is unambiguous?

My problem is how can I prove that a grammar is unambiguous? I have the following grammar: $$S → statement ∣ \mbox{if } expression \mbox{ then } S ∣ \mbox{if } expression \mbox{ then } S \mbox{ else } ...
16
votes
2answers
321 views

When is the concatenation of two regular languages unambiguous?

Given languages $A$ and $B$, let's say that their concatenation $AB$ is unambiguous if for all words $w \in AB$, there is exactly one decomposition $w = ab$ with $a \in A$ and $b \in B$, and ambiguous ...
9
votes
1answer
743 views

How do I reconstruct the forest of syntax trees from the Earley vector?

Using the Earley vector as a recognizer is quite straightforward: when the end of the string is reached, you just have to check for a completed axiomatic production started at position 0. If you have ...
9
votes
2answers
695 views

Is there a different resolution of the “dangling else” problem other than “match closest”?

The following context-free grammar presents a "dangling else" type ambiguity (imagine that $a$ stands for if expr then and $b$ stands for ...
7
votes
2answers
3k views

Inherent ambiguity of the language $L_2 = \{a^nb^mc^m \;|\; m,n \geq 1\}\cup \{a^nb^nc^m \;|\; m,n \geq 1\}$

I went through a question asking me to choose the inherently ambiguous language among a set of options. $$L_1 = \{a^nb^mc^md^n \;|\; m,n \geq 1\}\cup \{a^nb^nc^md^m \;|\; m,n \geq 1\}$$ $$and$$ $$L_2 ...
6
votes
4answers
3k views

Big Oh vs Big Theta

I mathematically understand $f(n) \in O(g(n))$ : $f(n)$ does not grow faster than $g(n)$. More formally, $\exists c, n_0$ s.t. $f(n) \leq cg(n) \forall n \geq n_0$. Similarly, $f(n) \in \Theta(g(n))$...
6
votes
2answers
3k views

Proof that there is unambigous grammar for every regular language

How can I prove, or where can I find proof that for every regular language there is unambigous grammar?
5
votes
2answers
1k views

does every CFL have an ambiguous CFG?

some questions have been popping up recently on ambiguity in CFLs/CFGs which can have subtleties (eg languages vs grammars & ambiguity vs inherent ambiguity). wikipedia states: Many [context ...
5
votes
1answer
214 views

Hardness of ambiguity/non-ambiguity for context-free grammars

A grammar is ambiguous if at least one of the words in the language it defines can be parsed in more than one way. A simple example of an ambiguous grammar $$ E \rightarrow E+E \ |\ E*E \ |\ 0 \ |\ ...
5
votes
1answer
302 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 ...
5
votes
0answers
209 views

How to disambiguate symbolic regular expressions

What I mean by a "symbolic regular expression" (if there already is a different name for this I'm not aware of it) is a regular expression that may include exponents that are symbolic arithmetic ...
4
votes
1answer
423 views

How to find unambiguous grammar for palindromes

I am trying to figure out how to make an unambiguous grammar for palindromes over the alphabet {a, b}. I have the following, but it is ambiguous and causes conflicts in yacc. ...
4
votes
2answers
2k views

unambiguous grammar that produce equal number of a and b

is there any unambiguous grammar on alphabet={a,b} that can produce strings which have equal number of a and b (e.g. "aabb" , "baba" , "abba") ?
4
votes
2answers
233 views

Priority in formal grammar

From my recitation class, I have the following exercise: $\mathrm{EXP} = 0 \mid 1 \mid b \mathrm{EXP} \mid \mathrm{EXP} a \mid \mathrm{EXP} m \mathrm{EXP}$ The above grammar is ambiguous. ...
4
votes
1answer
887 views

Prove that regular expression is unambiguous

I've got following definition: Function $f$ is a valid mapping of word $w$ to regular expression $R$, if any of following conditions is true: $R = w$ and $f$ is the identity or $R = \epsilon$ and $w ...
4
votes
1answer
90 views

Method for Creating Any Unambiguous Grammar?

I'm in an undergraduate class where we're studying formal grammars right now. I asked my teacher if there was any known set of rules for creating context free grammars that Was guaranteed to produce ...
4
votes
1answer
445 views

Show that every grammar for an inherently ambiguous CFL has infinitely many ambiguities

Prove that if a CFL $L$ is inherently ambiguous, then for any grammar $G$ with $L(G) = L$, there are infinitely many strings in $L$ that have (at least) 2 different derivations in $G$. Here's a ...
4
votes
1answer
393 views

What precisely is infinite ambiguity in a grammar?

From what I've read, an example of infinite ambiguity is usually given in a form of a loop: $S \rightarrow aA \\ A \rightarrow B \\ B \rightarrow A \\ B \rightarrow b$ But a grammar is called ...
3
votes
3answers
709 views

What techniques can I use to hand-write a parser for an ambiguous grammar?

I'm writing a compiler, and I've built a recursive-descent parser to handle the syntax analysis. I'd like to enhance the type system to support functions as a valid variable type, but I'm building a ...
3
votes
1answer
123 views

parsing at semantic level due to ambiguities

I have a VHDL elaboration engine/simulator. As I understand it, the language syntax allows for ambiguities at syntax level. That is, an assignment ...
3
votes
1answer
54 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 ...
3
votes
2answers
409 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 ...
3
votes
1answer
244 views

How to convert a grammar with finitely many ambiguous strings into a new, unambiguous grammar?

Suppose $L$ is an infinite CFL, and $G$ is a grammar with finitely many ambiguous strings which generates $L$. Is it possible to convert $G$ into an unambiguous grammar which also generates $L$? If ...
3
votes
1answer
2k 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 ...
3
votes
1answer
1k views

Ambiguous Grammar and SLR parsing table : No conflicts?

We have been studying the development of SLR parsers, and that now we have done the arithmetic expression grammar (the unambiguous version), I was curious to see if the same could be done to the if-...
3
votes
1answer
916 views

Is the ambiguity of a regular tree grammar decidable?

Is there an algorithm which decides whether a regular tree grammar $G$ is ambiguous, i.e. there exists a tree $t\in L(G)$ which can be parsed by the grammar in more than one ways, using only leftmost ...
3
votes
0answers
225 views

How to refactor a grammar to be suitable for recursive descent?

I'm trying to learn how to use a recursive descent parser, and reading on this page I find this example: $S \rightarrow AB \\ A \rightarrow a \\ A \rightarrow SA \\ B \rightarrow b \\ B \rightarrow ...
2
votes
4answers
450 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{...
2
votes
2answers
1k views

Can there be two different left most derevations for a grammar?

Suppose there is a CFG with the rules S--> Aa A--> Bb B--> A B--> Epsilon To my best understanding the left most derivation would go like this.. <...
2
votes
2answers
467 views

Lexing and parsing a language with juxtaposition as an operator

Normal human math notation treats juxtaposition as implied multiplication, e.g., $2x$ means $2$ multiplied by $x$. This does not seem to be a common feature of computer languages, although it was, for ...
2
votes
2answers
329 views

Ambiguous context free

Is there any technique to prove that a given language L is not ambiguous context-free? Here I don't know that whether L is CFL or not.
2
votes
3answers
6k views

How does one make an unambiguous context-free grammar for arithmetic expressions?

Say I have a context-free grammar defined by the following rule. $$ \langle EXPR\rangle \rightarrow \langle EXPR\rangle + \langle EXPR\rangle~|~\langle EXPR\rangle \times \langle EXPR\rangle~|~(\...
2
votes
1answer
54 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 ...
2
votes
2answers
5k views

How to show that given language is unambiguous

Given following grammar: $$ \begin{align} S \rightarrow &A1B \\ A \rightarrow & 0A \mid \varepsilon \\ B \rightarrow & 0B \mid 1B \mid \varepsilon \\ \end{align} $$ How can I show that ...
2
votes
1answer
39 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 ...
2
votes
1answer
2k views

Finding a unambiguous grammar

As an exercise we were supposed to find a grammar $G$ that generates language $L(G) = \{w \in \{a,b\}^* \mid |w|_a = |w|_b\}$. That was not so hard, I found a grammar which I think is correct: $S \...
2
votes
1answer
83 views

Explanation of Grammar Ambiguity

Consider now the grammar G S -> (S + S) S -> (S * S) S -> a Is it ambiguous? Answer: No because there are disambiguating parentheses and so no left or right recursion. Can someone explain how the ...
2
votes
1answer
491 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 ...
2
votes
2answers
609 views

Context-free grammars and priority

This grammar is supposed to give priority to multiplication: E -> E + T | T. T -> T * F | F. F -> x. A derivation for "x + x * x" would be (unless I'm wrong): E => E + T => T + T => F + T => x + T =...
2
votes
1answer
30 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 ...
2
votes
1answer
51 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 ...
2
votes
1answer
478 views

Find unambiguous grammar for an ambiguous grammar

Hi I want to find an unambiguous grammar for a known ambiguous one, and the production is like this: S->bA|aB A->a|aS|bAA B->b|bS|aBB I have found the ...
2
votes
1answer
94 views

How to decide if CSP is ambiguous?

When you pick up some reading about CSP the main focus is how to solve it. My goal is to compute/decide if CSP is ambiguous (has 2 or more solutions) or not (has 1 solution). Of course brute-force ...
2
votes
1answer
4k views

Resolving ambiguity in dangling else

Initially the ambiguous grammar is as follows (with some cropped production rules): ...
2
votes
1answer
42 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 ...
2
votes
0answers
147 views

How would I build a parser generator for a context free grammar using Pushdown Automata?

I am building a parser generator, not for any project in particular, just for fun to improve my understanding of parsing, grammars, languages, etc. I am at the point where I have lexer generation ...
2
votes
0answers
190 views

Is it possible to make this grammar unambiguous? expr: … | expr expr [closed]

I am writing a simple calculator in yacc / bison. The grammar for an expression looks somewhat like this: ...
1
vote
2answers
229 views

Is there a name/interest for regular languages that have a non-ambiguous ending?

The basic idea is to have one or more symbol that clearly indicate the end. For example: Non-ambiguous: $ab^*c$ $(a|b)c$ $ab^+c$ $ab?c$ $a(b|c)$ $c(ab)^*ccc$ $acc^*d$ $abc|bcd$ ...
1
vote
2answers
445 views

Ambiguity vs. context-sensitivity

It is said that attributes supply some semantic information to the grammar. Meantime, the same attributes let you to resolve ambiguities. Text books agree that it is worth haveing a CF grammar which ...