17 Parsing and Ambiguity
% noend hides “end for”; drop it to keep them
In this chapter we expand on the concept of parsing and ambiguity. They come into play since one important use of context-free grammars is to specify all the valid programs of a given programming language.
Definition 17.1 Given a context-free grammar G=(V,\Sigma,R,S) and a word w\in \mathscr{L}(G), a parse tree for w is a rooted tree with internal vertices labeled with symbols in V and leaves with symbols in \Sigma\cup\{\varepsilon\}:
- the root has label S
- if a vertex has label A and its children read from left to right form the word \alpha\in (\Sigma\cup V)^* then A\ \boldsymbol{\to}\ \alpha\in R;
- the leaves (again read from left to right) form the word w (the leaves with label \varepsilon contribute nothing).
Now, to each derivation of w we can associate a parse tree (using the rules of the derivation) and viceversa, a parse tree may correspond to several possible derivations of w, depending on the order in which the non-terminals are expanded.
If the non-terminal variables describe operations, then we can use a parse tree to associate a priority among the operations and hence an intended meaning of the word w.
Example 17.1 Let’s construct a grammar generating all valid numeric expressions using sums \textcolor{darkred}{\mathtt{+}} and differences \textcolor{darkred}{\mathtt{-}} (for sake of simplicity without parentheses):
\begin{array}{lcl} E\ &\boldsymbol{\to}&\ E \textcolor{darkred}{\mathtt{+}} E\ \vert\ E \textcolor{darkred}{\mathtt{-}} E\ \vert\ N\\ N\ &\boldsymbol{\to}&\ D\ \vert\ D'N\\ D'\ &\boldsymbol{\to}&\ \textcolor{darkred}{\mathtt{1}}\ \vert\ \textcolor{darkred}{\mathtt{2}}\ \vert\ \textcolor{darkred}{\mathtt{3}}\ \vert\ \textcolor{darkred}{\mathtt{4}}\ \vert\ \textcolor{darkred}{\mathtt{5}}\ \vert\ \textcolor{darkred}{\mathtt{6}}\ \vert\ \textcolor{darkred}{\mathtt{7}}\ \vert\ \textcolor{darkred}{\mathtt{8}}\ \vert\ \textcolor{darkred}{\mathtt{9}}\\ D\ &\boldsymbol{\to}&\ \textcolor{darkred}{\mathtt{0}}\ \vert\ D' \end{array}
or in a more readable syntax
\begin{array}{lcl} \langle \mathbf{Expr}\rangle\ &\boldsymbol{\to}&\ \langle \mathbf{Expr}\rangle \textcolor{darkred}{\mathtt{+}} \langle \mathbf{Expr}\rangle\ \vert\ \langle \mathbf{Expr}\rangle \textcolor{darkred}{\mathtt{-}} \langle \mathbf{Expr}\rangle\ \vert\ \langle \mathbf{Number}\rangle\\ \langle \mathbf{Number}\rangle\ &\boldsymbol{\to}&\ \langle \mathbf{Digit}\rangle\ \vert\ \langle \mathbf{NonZeroDigit}\rangle\langle \mathbf{Number}\rangle\\ \langle \mathbf{NonZeroDigit}\rangle\ &\boldsymbol{\to}&\ \textcolor{darkred}{\mathtt{1}}\ \vert\ \textcolor{darkred}{\mathtt{2}}\ \vert\ \textcolor{darkred}{\mathtt{3}}\ \vert\ \textcolor{darkred}{\mathtt{4}}\ \vert\ \textcolor{darkred}{\mathtt{5}}\ \vert\ \textcolor{darkred}{\mathtt{6}}\ \vert\ \textcolor{darkred}{\mathtt{7}}\ \vert\ \textcolor{darkred}{\mathtt{8}}\ \vert\ \textcolor{darkred}{\mathtt{9}}\\ \langle \mathbf{Digit}\rangle\ &\boldsymbol{\to}&\ \textcolor{darkred}{\mathtt{0}}\ \vert\ \langle \mathbf{NonZeroDigit}\rangle \end{array}
The following is a parse tree for the expression \textcolor{darkred}{\mathtt{1-2+3}}.
There is also a different parse tree for \textcolor{darkred}{\mathtt{1-2+3}}:
If we want to use the grammar above not just to generate words but to give a meaning to them we have a problem! Do we need to do first the difference (as in Figure 17.1) or the sum as in Figure 17.2? This problem is called ambiguity.
Definition 17.2 A grammar G is ambiguous if there exist a word w\in \mathscr{L}(G) with two distinct ordered, labeled parse trees for w.
Exercise 17.1 (🌱) Show that the grammar for the \mathsf{Dyck}\text{-}1 language we saw in Equation 16.1 is ambiguous. (For example giving two non-isomorphic parse trees for \textcolor{darkred}{\mathtt{()()()}})
A common way to check that two parse trees for a word w are non-isomorphic is to do a pre-order (Root, Left, Right) traversal on both of them. This corresponds to the so called leftmost derivation of w: at each step of the derivation of w the non-terminal to expand is the leftmost in the string. Two leftmost derivations are distinct if at some step either they expand a different non-terminal or they expand the same non-terminal but with a different rule. Using a post-order traversal gives the notion of rightmost derivation.
Example 17.2 One famous example of ambiguos grammar is given by the grammar for the programming language C. A simplified grammar exhibiting the dangling else ambiguity looks as follows:
\begin{array}{lcl} \langle\mathbf{Statement}\rangle\ &\boldsymbol{\to}&\ \dots\ \vert\ \langle\mathbf{Selection\text{-}statement}\rangle\\ \langle\mathbf{Selection\text{-}statement}\rangle\ &\boldsymbol{\to}&\ \dots\ \vert\ \textcolor{darkred}{\mathtt{if(}} \langle Expression\rangle\textcolor{darkred}{\mathtt{)}}\ \langle\mathbf{Statement}\rangle \ \textcolor{darkred}{\mathtt{else}}\ \langle\mathbf{Statement}\rangle\\ \langle\mathbf{Selection\text{-}statement}\rangle\ &\boldsymbol{\to}&\ \dots\ \vert\ \textcolor{darkred}{\mathtt{if(}} \langle Expression\rangle\textcolor{darkred}{\mathtt{)}}\ \langle\mathbf{Statement}\rangle \end{array} This gives rise to the famous Dangling else problem which is due to the above grammar being ambiguous. How do we interpret the following string?
\textcolor{darkred}{\mathtt{if(a)\ if(b)\ s1;\ else\ s2;}} can be parsed either as
if(a) {
if(b)
s1;
else
s2;
}or as
if (a) {
if (b)
s1;
}
else
s2;The C standard imposes to interpret a possibly ambiguous if-then-else as the first tree, but this is not imposed by the grammar itself.
Sometimes it is possible to remove the ambibuity from a grammar giving another grammar generating the same language but now unambiguous. Other times it is not possible, there are languages in \mathbf{CFL} where every possible grammar generating them is ambiguous (they are called inherently ambiguous context-free languages).
This is a difficult problem! There is no algorithm to decide whether a given context-free grammar is ambiguous!
Exercise 17.2 Construct a context-free grammar generating the language L=\{\textcolor{darkred}{\mathtt{a}}^n\textcolor{darkred}{\mathtt{b}}^n\textcolor{darkred}{\mathtt{c}}^m :n,m\in \mathbb{N}\}\cup \{\textcolor{darkred}{\mathtt{a}}^m\textcolor{darkred}{\mathtt{b}}^n\textcolor{darkred}{\mathtt{c}}^n :n,m\in \mathbb{N}\}\ . Show that your grammar is ambiguous.1
Exercise 17.3 Show that the grammar S\ \boldsymbol{\to}\ \varepsilon\ \vert\ \textcolor{darkred}{\mathtt{(}}S\textcolor{darkred}{\mathtt{)}}S generates exactly \mathsf{Dyck}\text{-}1 (see Definition 16.3) and this grammar in not ambiguous.
Exercise 17.4 Continue Exercise 16.9 and construct an unambiguous grammar for \mathsf{Dyck}\text{-}2.
Exercise 17.5 Design an unambiguous grammar generating exactly the language seen in Example 17.1.
Exercise 17.6 Design an unambiguous grammar generating all numeric expressions with operations \textcolor{darkred}{\mathtt{+}},\textcolor{darkred}{\mathtt{-}},\textcolor{darkred}{\mathtt{*}},\textcolor{darkred}{\mathtt{/}},\textcolor{darkred}{\mathtt{(}},\textcolor{darkred}{\mathtt{)}} and implementing the usual precedences between operations. (See this RACSO Exercise)
17.1 The CYK algorithm
Given a grammar G=(V,\Sigma, R,S) and a word w a natural problem is to decide whether w\in \mathscr{L}(G) and if this is the case to construct a parse tree for w. In this section, we describe an algorithm to solve this problem: the Cocke–Younger–Kasami (CYK) parsing algorithm. This is an example of the common technique of dynamic programming.
A reference for the CYK algorithm is (Kozen 1997, chap. 27).
For simplicity, we assume all the productions of G have the form A\ \boldsymbol{\to}\ BC with A,B,C\in V or A\ \boldsymbol{\to}\ \textcolor{darkred}{\mathtt{s}} with \textcolor{darkred}{\mathtt{s}}\in \Sigma (or S\ \boldsymbol{\to}\ \varepsilon if \varepsilon\in \mathscr{L}(G)).
As we see in Chapter 18 this is not an unreasonable assumption since every context-free grammar can be transformed into an equivalent one of this form and the new grammar has size at most |G|^2, where |G| denotes the size of the grammar (for example, the total length of its productions).
Exercise 17.7 Show that for a grammar G of the form above any production of a non-empty word of length n consists of the application of exactly 2n-1 productions.
By the special form of the grammar, if w=\varepsilon it is trivial to check whether w\in \mathscr{L}(G). So we can also assume w\neq \varepsilon. Let n=|w|.
The idea of the algorithm is not only to decide whether w\in \mathscr{L}(G), but for each subword of w to know what variables can generate it. To store this information we can use Boolean variables P[i,\ell,A], for 1\leq i\leq n, 1\leq \ell\leq n-i+1 and A\in V, with intended meaning the truth value of “the subword of w starting in position i and of length \ell can be generated from the variable A”. (As usual, we use the convention that w[1] is the first symbol of w, that is w=w[1]w[2]\cdots w[n].)
Our goal is to compute the truth value of P[1,n,S] since P[1,n,S]=1 if and only if w\in \mathscr{L}(G) by construction.
It is immediate to know the values of P[i,1,A] for each i\leq n and A\in V. How?
Now, in a typical dynamic programming approach, you want to compute all truth values P[i,\ell,A] assuming you already know all the truth values P[i,k,A] with k<\ell. How
Exercise 17.8 Using the CYK algorithm as described above, decide whether w=\textcolor{darkred}{\mathtt{aabbab}} is in \mathscr{L}(G) where G is the following grammar
\begin{array}{lcl} S\ &\boldsymbol{\to}&\ AB\ \vert\ BA \ \vert\ SS\ \vert\ AC\ \vert\ BD\\ C\ &\boldsymbol{\to}&\ SB\\ D\ &\boldsymbol{\to}&\ SA\\ A\ &\boldsymbol{\to}&\ \textcolor{darkred}{\mathtt{a}}\\ B\ &\boldsymbol{\to}&\ \textcolor{darkred}{\mathtt{b}} \end{array}
Following this approach, a possible pseudocode implementing the CYK algorithm is the following.
The cost of the previous algorithm is \mathcal{O}(n^3|G|).
Exercise 17.9 Try to adapt the CYK algorithm to a general grammar. What problems might occur? How does the running time change?
Exercise 17.10 Adapt the previous code to also obtain a parse tree of w when w\in \mathscr{L}(G).
Exercise 17.11 Adapt the previous code to also know whether G generates w ambiguously or not, i.e. whether there are at least two distinct parse trees for w.
A natural question to ask is whether the CYK algorithm we described has the optimal running time \mathcal{O}(n^3|G|) for deciding whether w\in \mathscr{L}(G). This is not the case and (surprisingly) parsing for context-free grammars is tightly connected with matrix multiplication of 0/1-valued matrices.
On one side Valiant (1975) showed that algorithms for fast multiplication of 0/1-valued matrices can be used to do the computations in the CYK algorithm. On the other side Lee (2002) showed that any parsing algorithm for CFGs with running time \mathcal{O}(n^{3-\varepsilon}|G|) can be turned into an algorithm to compute the product of n\times n 0/1-valued matrices in time \mathcal{O}(n^{3-\varepsilon/3}).
Your grammar will be ambiguous since L is an inherently ambiguous context-free language.↩︎