Questions tagged [ambiguity]

The tag has no usage guidance.

84 questions
Filter by
Sorted by
Tagged with
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 ...
326 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 ...
765 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 ...
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 ... 2answers 349 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. 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 ... 1answer 925 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 ... 1answer 4k views Resolving ambiguity in dangling else Initially the ambiguous grammar is as follows (with some cropped production rules): ... 1answer 94 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 ... 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.. <... 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: ... 1answer 97 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 ... 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 ... 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 TT \xrightarrow{} aTb \mid ab $$... 2answers 641 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 =... 1answer 633 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 ... 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 ... 1answer 247 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 ... 1answer 257 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? ... 1answer 448 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 ... 1answer 491 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 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. 2answers 481 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 ... 1answer 764 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 ... 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 ... 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 ... 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? 1answer 362 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 ... 2answers 236 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. ... 1answer 400 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 ... 2answers 231 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 ... 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 ... 1answer 215 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 \ |\ ...
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: \$\...