56
Consider the following grammar for arithmetic expressions:
$$
X \to X + X \mid X - X \mid X * X \mid X / X \mid \texttt{var} \mid \texttt{const}
$$
Consider the following expression:
$$
a - b - c
$$
What is its value? Here are two possible parse trees:
According to the one on the left, we should interpret $a-b-c$ as $(a-b)-c$, which is the usual ...
12
Every nonempty context-free language has an ambiguous grammar. Consider any context-free grammar for the language with starting symbol $S$. We add new non-terminals $S',A',B'$, make $S'$ the new starting symbol, and add the following rules:
$$
\begin{align*}
&S' \to A' \\
&S' \to B' \\
&A' \to S \\
&B' \to S
\end{align*}
$$
12
In contrast to the other existing answers [1, 2], there is indeed a field of application, where ambiguous grammars are useful. In the field of natural language processing (NLP), when you want to parse natural language (NL) with formal grammars, you've got the problem that NL is inherently ambiguous on different levels [adapted from Koh18, ch. 6.4]:
...
12
The following grammar is unambiguous yet generates a non-regular language:
$$ S \to aSb \mid \epsilon $$
10
I am using terminology and notations from Earley's paper. It is possible that the description you read is different.
It seems frequent that general CF parsing algorithms are first
presented in the form of a recognizer, and then the information
management needed to actually build parse trees and parse forests is
sort of added as an afterthought. One reason ...
10
Hint: Given DFAs for $A$ and $B$, construct an NFA which accepts words in $AB$ having at least two different decompositions. The NFA keeps track of two copies of the standard NFA for $AB$ (formed by joining DFAs for $A$ and $B$ with $\epsilon$ transitions), ensuring that the switch from $A$ to $B$ happens at two different points.
10
Even if there’s a well-defined way to handle ambiguity (ambiguous expressions are syntax errors, for example), these grammars still cause trouble. As soon as you introduce ambiguity into a grammar, a parser can no longer be sure that the first match it gets is definitive. It needs to keep trying all the other ways to parse a statement, to rule out any ...
9
The problem with $S\to aSbS\mid bSaS\mid \varepsilon$ is that you're just making sure you match each $a$ with a $b$ (where we consider an $a$ and a $b$ to be matched iff they appeared during the same derivation step).
To ensure non-ambiguity, you must add a constraint on the matching to ensure that it is unique (while maintaining its existence). One way to ...
9
Does IF a THEN IF b THEN x ELSE y mean
IF a THEN
IF b THEN
x
ELSE
y
or
IF a THEN
IF b THEN x
ELSE
y
? AKA the dangling else problem.
9
Here is a simple counter example:
$S \rightarrow aSbSaSbS \space |\space \epsilon$
and string $w: abababab.$
In one case we use last $S$ and in other case we use second $S$. All other $S$ goes to $\epsilon$.
Why I was able to get this grammar?
Let's rewrite above grammar with numbers assigned to each $S$'s.
$S \rightarrow aS_1bS_2aS_3bS_4 | \epsilon$
...
8
Updated (thanks to Yuval Filmus).
Given two languages $X$ and $Y$ of $A^*$, let
\begin{align}
X^{-1}Y &= \{u \in A^* \mid \text{there exists $x \in X$ such that $xu \in Y$} \} \\
YX^{-1} &= \{u \in A^* \mid \text{there exists $x \in X$ such that $ux \in Y$} \}
\end{align}
I claim that $XY$ is unambiguous if and only if the language $X^{-1}X \cap ...
8
First, I believe you are looking for a different word than 'unambiguous'. A grammar is ambiguous if some string in its language has two or more derivations; I'm sure that a palindromic string must have only one derivation in this grammar.
I suspect the word you really mean is 'deterministic'. YACC must declare that this grammar has 'shift-reduce' ...
7
This problem is an exact analogue of the problem of matching parentheses in an expression in which some of the close parentheses have been omitted. Here an "if" (or $a$ in the representative grammar) is an open parenthesis and an "else" ($b$) is a close parenthesis. (From the sequence of $a$s and $b$s you can mechanically insert $c$s by placing one before ...
6
The following statement seems mathematically correct, though confusing.
Any grammar for the empty language $\varnothing$ is unambiguous: it has no strings for which there are two different valid derivation trees.
6
You are correct that additions operator is produced first when you
derive. But when you parse, you do the opposite (reduction), and the
multiplications are recognized first, wich is precisely what you want.
THis need a bit of discussion, when you compare top-down and bottom up
parsing, but basically the bottom of the tree must be know correct
before the top ...
6
A leftmost derivation of a string in the language defined by a
grammar $G$ characterizes a parse-tree for that string. It is a way of
describing the parse tree, which is unique for each parse tree.
But to answer the specifics of your question, there is no lefmost
derivation of a language, only of the strings of a
language. Furthermore, since a leftmost ...
6
If $L_1,L_2$ are two disjoint context-free languages which are not inherently ambiguous, then $L_1 \cup L_2$ is also a context-free language which is not inherently ambiguous. The reason is simple: starting with context-free grammars for $L_1,L_2$ with start symbols $S_1,S_2$ (respectively) and otherwise disjoint non-terminals, you can construct an ...
5
Your question is strange. If you do not know what kind of language you
have, the question may well be meaningless, as the concept of
ambiguity can only be defined with respect to a known system of
enumeration of the sentences of the language. There is none if the language is not Recursively Enumerable.
Thus it does not make sense to ask whether a language ...
5
Grammars of real programming languages are often more restricted than CFG in order to enable efficient parsing. You may have heard of LL(k) and LR(k) grammars, for instance. All these grammars are, by definition, unambiguous; the corresponding language classes are (strict) subsets of DCFL.
You would realize a grammar is ambiguous (or otherwise not in the ...
5
Take the most vexing parse in C++ for example:
bar foo(foobar());
Is this a function declaration foo of type bar(foobar()) (the parameter is a function pointer returning a foobar), or a variable declaration foo of type int and initialized with a default initialized foobar?
This is differentiated in compilers by assuming the first unless the expression ...
5
I think the question contains an assumption that's only borderline correct at best.
In real life it's pretty common to simply live with ambiguous grammars, as long as they aren't (so to speak) too ambiguous.
For example, if you look around at grammars compiled with yacc (or similar, such as bison or byacc) you'll find that quite a few produce warnings ...
4
Intuitively, the reason the claim is true is that if a grammar $G$ had only finitely many ambiguous strings, then you could somehow resolve the ambiguity and come up with an equivalent unambiguous grammar $G'$, thus contradicting the inherent ambiguity. The way you would resolve the ambiguity is something like this: you would generate all small strings (say ...
4
$$S \xrightarrow{} SS \xrightarrow{} SSS \xrightarrow{} TSS \xrightarrow{} abSS \xrightarrow{} abTS \xrightarrow{} ababS \xrightarrow{} ababT \xrightarrow{} ababab$$
$$S \xrightarrow{} SS \xrightarrow{} TS \xrightarrow{} abS \xrightarrow{} abSS \xrightarrow{} abTS \xrightarrow{} ababS \xrightarrow{} ababT \xrightarrow{} ababab$$
As @babou mentions in a ...
4
There is no reason to "distinguish between value_expression and
type_conversion" since, according to the grammar a type_conversion is
a value_expression.
You probably mean to distinguish between indexed_name and
type_conversion ... and possibly also function_call, but you do not
give its syntax, so I am not sure.
I do not know VHDL, but it may be that the ...
4
First, there is a difference between a language and a grammar. A language is just a set of strings, while a grammar is a way to specify such languages. The attribute "ambiguous" applies to grammars. There is no such thing as a "unambiguous language". What you want is an unambiguous grammar for the same language.
In general, it is not possible to give an ...
4
For some grammars, a proof by induction (over word length) is possible.
Consider for example a grammar $G$ over $\Sigma = \{a,b\}$ given by the following rules:
$\qquad \displaystyle S \to aSa \mid bSb \mid \varepsilon$
All words of length $\leq 1$ in $L(G)$ -- there's only $\varepsilon$ -- have only one left-derivation.
Assume that all words of length $\...
4
This answer has 3 parts:
I first answer the question as asked,
sketching the beginning of a proof concerning the example given. A
full proof is too long and tedious to be given here.
Then I give a general procedure to solve the problem and decide
whether a regular expression is deterministic/unambiguous.
Finally I discuss some difficulties and problems with ...
4
No, and there is indeed a reduction to the undecidability of ambiguity.
First, note that ambiguity is (for context-free grammars) semi-decidable: just keep generating words by different left-derivations and say "ambiguous!" when you first find a word you've seen before.
Now, the method you are proposing allows to semi-decide unambiguity. You effectively ...
4
I did not read in detail your grammar which is far too large for my
available time, and short of an example that you should provide (since you
assert it is ambiguous) I will not not attempt to check whether it is,
which is in general undecidable.
This said, as already remarked by user rici there are general
context-free (GCF) parsers that will parse any CF ...
4
A (sloppy) upper bound is easier to prove than a tight upper bound, let alone upper and lower bounds.
Some algorithm's runtime can't be given with the same function as upper/lower bound. E.g. simple sorting algorithms are $O(n^2)$, but have lower bound $\Omega(n)$.
Some insist of striving to give performance in asymptotic terms via $\sim$, where $f(n) \sim ...
Only top voted, non community-wiki answers of a minimum length are eligible