\documentclass{article}

\usepackage{url}
\usepackage{MnSymbol}           % \leftmodels
\usepackage{enumerate}

\newcommand\bA{\mathbf{A}}
\newcommand\bB{\mathbf{B}}
\newcommand\bC{\mathbf{C}}
\newcommand\bD{\mathbf{D}}

\newcommand\liff{\Leftrightarrow}

\newcommand\solution{{\bf Solution.} }
\newcommand\remarks{{\bf Remarks.} }

\title{Enderton 1.3: Unambiguity of grammars / Uniqueness of parse trees}

\begin{document}

\maketitle

\section{Basic Result}

We need to show that there is just one way to form a wff using the
formula-building rules.  That is, there is just one parse tree.  The
parentheses insure this.  (For the wff
$\phi=((\bA\lor\bB)\land(\bC\lor\bD))$, it doesn't matter whether we
form the fragment $(\bA\lor\bB)$ first or $(\bC\lor\bD)$ first; the
tree is the same.)

The problem is that, without parentheses, $\bA\lor\bB\land\bC$ could
be read as $(\bA\lor\bB)\land\bC$ or $\bA\lor(\bB\land\bC)$.  There
would be no good way to assign semantics to this.

Recall that earlier we showed that a non-empty proper prefix of a wff
has more open parens than close parens.  It follows that a
non-sentence symbol wff phi is of the form (alpha conn beta), where
alpha and beta have balanced parentheses (alpha may be empty), and
conn is one of the five connectives.  Furthermore, there is a unique
way to write phi this way.

So an algorithm can find the connective at the root of the parse tree
by counting parentheses from left to right.

\subsection{Problems and Issues}

The parsing algorithm described above may need to read in the entire
wff before making any decisions.  It may need time $\Omega(n^2)$ to
process a wff of length $n$.  Neither is desirable.

\section{Related examples}

\subsection{Natural Language}

Here is a (very ambiguous) grammar from natural language.  The pipe
symbol $|$ indicates a choice of several rules.  So, for example, a
Sentence can be a noun-phrase followed by verb, or a noun-phrase,
(transitive) verb, and noun-phrase (object).  In places, I've included
words in square brackets that are optional but may improve readability.

\begin{tabular}{lcl}
Sentence & : & noun-phrase verb $|$ noun-phrase verb noun-phrase\\
noun-phrase & : &  adjective noun $|$ noun $|$ noun-phrase relative-clause\\
relative-clause & : &  [that] noun-phrase verb\\
noun & : &  badger $|$ bovine $|$ butterfly $|$ buffalo\\
verb & : &  bother $|$ bully $|$ bedevil $|$ buffalo\\
adjective & : & big $|$ blue $|$ Boston $|$ Binghamton $|$ Buffalo
\end{tabular}

E.g., a sentence could be

[The] Binghamton badgers [, that] Boston bovines bedevil [,] bother blue
butterflies.

(The commas and ``the'' actually change the meaning somewhat in English.)

or

Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo.

There is more than one way to parse this; find some!  In fact, there
are exponentially-many ways to parse a string of $n$ buffalos.  Ignore
capitalization for this exercise.

\subsection{Parenthesized wffs, revisited}

Here is an alternative grammar for our wffs.  We'll use $S$
(``start'') for wffs, $C$ for connectives, and $A$ for alphabet symbols.

\[\begin{array}{lcl}
S & : & A \>|\> (\lnot S) \>|\> (S C S)\\
C & : & \land \>|\> \lor \>|\> \to \>|\> \liff\\
A & : & \bA \>|\> \bB \>|\> \bC \>|\> \cdots
\end{array}
\]

With this grammar, we claim:
\begin{enumerate}
\item We derive exactly the same set of wffs as before.
\item A wff of length $n$ can be parsed in time $O(n)$.
\item A wff can be parsed left-to-right.  To decide which rule to
  apply ({\em i.e.}, for wffs), a parser need only look at one unread
  character in addition to the currently read symbol ({\em i.e.}, does
  the suffix start with a letter, with ``$(\lnot$,'' or with ``$(($'').
\end{enumerate}

Wffs can be parsed using a {\em stack machine}, in which the unbounded
memory consists of a stack.  The last item {\em pushed} onto the stack
is the only one available to be read, by a {\em pop} operation.
Following that pop, the previously-pushed item is available, etc.

The algorithm is as follows.  Start with ``wff'' on the stack.
Repeatedly pop the stack, getting a {\em variable}, $v$.  Determine
from the input (suffix of a supposed wff) which {\em rule} applies,
and push the variables and {\em terminals} on the right-hand-side of
the rule onto the stack, or consume input without pushing anything.

An example should make this clear.  Time proceeds down.

\[
\begin{array}{|l|l|}
\hline
\mbox{stack} & \mbox{Remaining wff}\\
\hline\hline
S & ((\bA\lor(\lnot\bB))\land\bC)\\
(S C S) & ((\bA\lor(\lnot\bB))\land\bC)\\
S C S) & (\bA\lor(\lnot\bB))\land\bC)\\
(S C S) C S) & (\bA\lor(\lnot\bB))\land\bC)\\
S C S) C S) & \bA\lor(\lnot\bB))\land\bC)\\
A C S) C S) & \bA\lor(\lnot\bB))\land\bC)\\
C S) C S) & \lor(\lnot\bB))\land\bC)\\
S) C S) & (\lnot\bB))\land\bC)\\
(\lnot S)) C S) & (\lnot\bB))\land\bC)\\
\lnot S)) C S) & \lnot\bB))\land\bC)\\
S)) C S) & \bB))\land\bC)\\
A)) C S) & \bB))\land\bC)\\
)) C S) & ))\land\bC)\\
) C S) & )\land\bC)\\
C S) & \land\bC)\\
S) & \bC)\\
A) & \bC)\\
) & )\\
&\\
\hline
\end{array}
\]

You can play with this using the MATLAB function \verb|popupparse|.
Select ``full'' grammar (for ``full parentheses'').

\subsection{Dropping Parentheses}

At the end of section 1.3, Enderton gives (very informally) rules for
dropping some parentheses and still recovering the wff unambiguously.
In my view, the definition is somewhat lacking.  Unambiguity is
asserted, but not proven.  The expression $(\bA)$ is {\em not}
allowed.

A grammar for the partially-parenthesized wffs is given under
\verb|popupparse|.  You can check that, for each left-hand-side of a
rule and each possible upcoming character, at most one non-empty
right-hand side applies.  (Apply the empty right-hand side, when
present, only as a last resort.)  We won't prove that this grammar is
correct (which means that it derives the collection of expressions
that you expect---we've never defined these), but you can play with it
on MATLAB.

\end{document}
