Questions tagged [ambiguity]
Questions about ambiguity in context-free grammars.
18
questions with no upvoted or accepted answers
5
votes
0
answers
237
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 ...
- 286
4
votes
0
answers
402
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 ...
- 151
3
votes
0
answers
315
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 ...
- 157
2
votes
0
answers
68
views
Unparsing an operator grammar in the face of ambiguity
I'm using the grammar scheme of Danielsson and Norell ("Parsing Mixfix Operators"). The short version is:
user defined mixfix operators such as _+_ or <...
- 121
2
votes
0
answers
311
views
Proper algorithm for resolving ambiguity in grammars via enforcing associativity and precedence rules
I was told there is a algorithm that always resolves ambiguity for grammars that have issues with precedence and associativity. I know ambiguity in general is undecidable, so I only want to resolve ...
- 3,040
2
votes
0
answers
70
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-...
- 141
1
vote
1
answer
530
views
How to prove that this "priority" strategy (in ANTLR4) solves the "dangling-else" ambiguity?
As shown in this post @ stackoverflow, ANTLR4 seems able to resolve the "dangling-else" ambiguity @ wiki in the following "if-then-else" grammar by prioritizing the "...
- 9,551
1
vote
0
answers
508
views
Chomsky Normal Form for context free grammars ambiguous/unambiguous properties?
My textbook states:
Finally, it must be stressed that the Chomsky normal form says nothing about ambiguity in general—a CFG in Chomsky normal form may or may not be ambiguous, just like we have for ...
- 11
1
vote
0
answers
340
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{...
- 11
1
vote
0
answers
174
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-...
- 153
0
votes
0
answers
87
views
Methods of eliminating ambiguity in CFG
I am looking for all possible ways to find and eliminate ambiguity in CF grammar. Please share your knowledge or opinion (preferably you will indicate the literature so that I can familiarize myself)....
- 1
0
votes
0
answers
39
views
how ambiguity of following grammar cant be decidable?
SO According to question grammar should be like this (A -> AA ).
->So i learn that if grammar is left and right recursive both then that grammar must be ambiguous but here the answer is deferent....
0
votes
0
answers
34
views
How to change a grammar so that it can be unambiguous?
The original grammar is
$$ S \to SaS \mid SbS \mid ScS \mid d $$
My answer is
$$ S \to daS \mid dbS \mid dcS \mid d $$
Is that correct?
- 1
0
votes
0
answers
43
views
Making context-free grammar unambiguous
I'm trying to change below context free grammar such that it becomes unambiguous, but I don't know what steps I should take. Is there any specific way of doing that?
Here is my CFG:
\begin{align}
&...
0
votes
0
answers
122
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, ...
- 179
0
votes
0
answers
57
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-...
- 51
0
votes
0
answers
1k
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 ...
- 119
0
votes
0
answers
62
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 ...
- 167