Questions tagged [ambiguity]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
1
vote
1answer
497 views

Unambiguous CFG for $a^ib^j$ where $i \le j \le 2i$

could you please help me for finding an unambiguous CFG for the following expression: $a^ib^j$ where $i \le j \le 2i$
1
vote
1answer
73 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 ...
1
vote
1answer
188 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?
1
vote
1answer
164 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?
1
vote
1answer
73 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 ...
1
vote
1answer
30 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 ...
1
vote
0answers
50 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-...
1
vote
0answers
246 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{...
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
150 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-...
0
votes
1answer
164 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 ...
0
votes
1answer
2k 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
2answers
292 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 ...
0
votes
2answers
450 views

Relation between CLR Grammar and Ambiguity

I am studying CLR Parser and have a query about Grammar. If a Grammar can't be parsed using CLR(1) Parser ( i.e LR(1)) parser is it necessarily ambiguous? Is it possible that a grammar which is ...
0
votes
1answer
635 views

Is a grammar that accepts function declarations, function calls and expressions (at any order!) necessarily cyclic?

As the title suggests, assume a grammar which has to recognize function declarations, function calls, and expressions, at any order. Does that mean it has to be cyclic, and therefore ambiguous? I ...
0
votes
1answer
46 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 ...
0
votes
1answer
251 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 ...
0
votes
1answer
920 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} ...
0
votes
1answer
53 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 ...
0
votes
1answer
88 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,...
0
votes
1answer
51 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 ...
0
votes
1answer
258 views

How does the Earley Parser store possible parses of an ambiguous sentence?

I've got a pretty basic question concerning the Earley parser: In case of syntactic ambiguity ( S -> NP VP(V NP(NP PP)) vs. S -> NP VP(VP((V NP) PP) ), are both parses stored in one chart or in two? ...
0
votes
1answer
364 views

Determine if two grammars for the same language are ambiguous

I'm reading the book: Formal Syntax and Semantics of Programming Languages. I don't understand this exercise: Consider the following two grammars, each of which generates strings of correctly ...
0
votes
1answer
475 views

Is this grammar ambiguous?

I have the grammar: $\qquad \begin{align} S &\to S = P \mid S \neq P \mid P \\ P &\to NUM \end{align}$ This grammar suffers from left recursion. To eliminate left recursion, I got: $\...
0
votes
0answers
32 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
0answers
44 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-...
0
votes
0answers
798 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 ...
0
votes
0answers
60 views

Can we say we reduced a rule if we reduced an equivalent set of smaller rules?

I have constructed an SLR(1) parsing table with the following rules. S -> S + S + S (rule 1) S -> S + S (rule 2) S -> y Is reducing rule 2, then shifting + and y, then again rule 2, equivalent to ...
-1
votes
1answer
74 views

Help me find the ambiguity in this grammar

I've been sitting on this for 20+ minutes and can't seem to generate a string that is ambiguous. Can anyone help me? The grammar is: $$S \xrightarrow{} SS \mid T$$ $$T \xrightarrow{} aTb \mid ab $$ ...
-1
votes
1answer
6k 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. ...
-1
votes
1answer
247 views

Programming Languages Grammar Ambiguity [closed]

I don't know if it is the right site to ask this. But we're studying about ambiguities of grammar. Including left most derivation and right most derivation. We are given the problem: ...
-1
votes
2answers
349 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 ...
-2
votes
1answer
126 views

Find an unambiguous grammar [closed]

S → aS | aSbS | (empty) where the alphabet is {a,b} in other words, the set of strings where any prefix has at least as many 'a's as 'b's.