52
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 ...
20
There is (at least) one way to prove unambiguity of a grammar $G = (N,T,\delta,S)$ for language $L$. It consists of two steps:
Prove $L \subseteq \mathcal{L}(G)$.
Prove $[z^n]S_G(z) = |L_n|$.
The first step is pretty clear: show that the grammar generates (at least) the words you want, that is correctness.
The second step shows that $G$ has as many syntax ...
12
The question is wrong. The second language is also inherently ambiguous. The usual way this is proved is as follows. Suppose $L_2$ had an unambiguous grammar. Let $p$ be the constant promised by Ogden's lemma, and consider the word $a^{p!+p} b^p c^p$. Mark the positions of $b^p c^p$ and apply Ogden's lemma to pump this word to the word $a^{p!+p} b^{p!+p} c^{...
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]:
...
11
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*}
$$
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
Ambiguous grammars can be enumerated, since each ambiguous grammar has a proof of ambiguity, namely a word with two different parses.
9
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 ...
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.
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
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 ...
7
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 ...
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
This is a good question, but some Googling would have told you that there is no general method for deciding ambiguity, so you need to make your question more specific.
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
You're quite right to be dubious, $L_{2}$ is also inherently ambiguous. It's even been used as a "prototype of an inherently ambiguous language" by Flajolet (right at the start of section 2).
5
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 ...
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
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
To show a grammar is unambiguous you have to argue that for each string in the language there is only one derivation tree.
In this particular case you can observe that $A$ only generates $0$'s, so the $1$ generated by the start symbol $S$ must be the first $1$ in the string.
Any grammar can be made ambiguous by adding chain productions like $S\to S$.
4
According to your alternative definition, you're looking for a language such that $u\in L\Rightarrow \forall v\neq\epsilon, uv\notin L$ (where $\epsilon$ denotes the empty string).
That property defines a useful kind of language in coding, called prefix-free codes. Note that this language class doesn't include nor is included in regular languages.
So what ...
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
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
Juxtaposition is used in mathematics because most mathematical texts
use single character variables (possibly with diacritic signs,
subscripts, superscripts, etc...) so that there is no ambiguity.
A mathematician might write $2x$ to multiply $2$ and $x$. It would be
quite unusual to write $x2$ to multiply $x$ by $2$. Actually, as much
as I can see (but I am ...
Only top voted, non community-wiki answers of a minimum length are eligible
