# Tagged Questions

The tag has no usage guidance.

20 views

51 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 ...
235 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.. <...
32 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: ...
62 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 ...
98 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 ...
58 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$$ ...
167 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 + ...
133 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 ...
57 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 ...
182 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 ...
109 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? ...
267 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 ...
566 views

### Resolving ambiguity in dangling else

Initially the ambiguous grammar is as follows (with some cropped production rules): ...
2k 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. ...
115 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$
60 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.
180 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 ...
258 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 ...
592 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 ...
93 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 ...
1k 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?
219 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 ...
169 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. ...
459 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.g. there exists a tree $t\in L(G)$ which can be parsed by the grammar in more than one ways, using only leftmost ...
212 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$...
3k 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 ...
2k views

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 \ |\ ... 1answer 262 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 ... 0answers 166 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 ... 4answers 10k 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 } ...
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: \$\...