Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [ambiguity]

The tag has no usage guidance.

0
votes
1answer
27 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
votes
0answers
18 views

How useful is Ambiguity in Natural Language Processing? [on hold]

Ambiguity is not desirable while designing a compiler for a programming language, but i have came to know that ambiguity is somewhat important for NLP, I will like to know further about this. Thanks ...
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.
0
votes
0answers
28 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, ...
0
votes
1answer
39 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 ...
2
votes
1answer
40 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
1answer
29 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 ...
1
vote
1answer
56 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
1answer
50 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 ...
0
votes
1answer
81 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,...
3
votes
1answer
52 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 ...
1
vote
1answer
170 views

CFG - Ambiguous to Unambiguous

Given the ambiguous CFG : S → 01S1|SS|ϵ I came up with the following CFG which I think is unambiguous: S → 01X | 011X X → 01X1 | ϵ Is my CFG unambiguous and does it represent the same language?
2
votes
1answer
37 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
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 ...
1
vote
0answers
49 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-...
0
votes
1answer
130 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 ...
3
votes
2answers
401 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
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 ...
1
vote
1answer
139 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?
2
votes
1answer
486 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 ...
0
votes
0answers
43 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-...
2
votes
1answer
1k 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 \...
1
vote
0answers
234 views

Given a context free grammar, prove if the grammar is ambiguous

Here is a context free grammar that I have been given for practice: Grammar $G = (V,\Sigma,R,S)$ where $V$ is $\{S,A,B,a,b,c\}$ and $\Sigma$ is $\{a,b,c\}$. $R$ has the following rules: $$\begin{...
2
votes
0answers
143 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 ...
1
vote
1answer
58 views

Making a grammar ambiguous by applying a morphism

I have an encoding of an unambiguous grammar $G$. Can I apply a morphism $σ$ so that the grammar becomes ambiguous? I have no clear concepts about this, only the idea: "grammar $G$ is ambiguous if ...
1
vote
0answers
144 views

Context Free Grammar Prove Un-/Ambiguity

I know, it is not possible to decide whether a context free grammar is ambiguous or not. However, I am having a really hard time preparing for an upcoming exam in which I'll have to give a prove of un-...
4
votes
1answer
420 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. ...
9
votes
2answers
684 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 ...
2
votes
4answers
441 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{...
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") ?
0
votes
1answer
1k 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 ...
0
votes
0answers
758 views

Show that any LL(k) grammar is unambiguous

I am confused on several areas of this. First, this is so obvious I am finding it hard to prove. Second, what are some definitions, axioms, or lemmas of an ll(k) grammar that I can use to build up a ...
-1
votes
2answers
333 views

Find the Unambiguous Grammar [closed]

Consider the following grammar: S->A. A->A+A|B++. B->y Check whether grammar is Ambiguous or not? Also ,unambiguate the grammar.Now please tell me what will be the grammar after removing the ...
0
votes
1answer
205 views

It has been asked to prove that a grammar is unambiguous which seem ambiguous to me

S->aAB A->bBb B->A|epsilon It seems that the string abbbb can be derived by using more than one ways. After using the starting production and the ...
2
votes
1answer
466 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 ...
3
votes
0answers
222 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
1answer
82 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 ...
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))$...
1
vote
1answer
72 views

Ambiguity Problem (Language Structures)

I'm having serious issues fining an unambiguous version of a particular grammar. I've looked online for help for this particular problem and for general methods for finding unambiguous versions of ...
0
votes
2answers
268 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 ...
1
vote
2answers
437 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 ...
1
vote
1answer
35 views

Duplicating the quotation marks in in the quotation-mark enclosed strings

There is such a grammar string_literal ::= " { graphic_character } " The double-quotes that you see must appear in the user program and curly braces mean "any ...
0
votes
1answer
835 views

Is showing two different derivations enough to prove that a CFG is ambiguous?

I'm wondering, is showing two different ways to derive the same word enough proof to show that a context-free grammar is ambiguous? For example: O = start symbol Non-terminal = {O} Terminal = {r, s} ...
2
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-...
2
votes
0answers
189 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: ...
0
votes
1answer
50 views

Where is the ambiguity in this grammar?

I am trying to understand ambiguous grammar in programming languages. I was given this ruleset and told it was ambiguous. If my understanding is correct, this means that it is possible to create the ...
16
votes
2answers
320 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 ...
3
votes
3answers
686 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 ...
2
votes
2answers
326 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.
5
votes
1answer
295 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 ...