% file "JLRch31.tex"
% LEGEND---search on the following strings for impt comments by KSN.
% {E,e}ditor:    questions and special comments for the CRC editors.
% {A,a}uthor[s]: queries for the authors; answers requested.
% {O,o}ops:      mistake fixed by KSN -- please check.
% !! or check:   mental note by KSN of something that may still need checking.
% KSN:           comment on changes by KSN worth noting.
%% Author's responses usually start with Answer:

% Note: To print /without/ the .ps figures, three lines with \psfig must be
% commented out.  Also see a "\comment" with proposed additional text.--KSN
%% About the \comment: please see my response inside. I'm indifferent to
%% keep or leave out the proof. You decide.


% chapter 31

\documentclass[12pt,epsf]{article}
\special{landscape}\special{! /landplus90 true store}
\input{psfig}

\input{2up.tex}
\twouparticle

% \renewcommand{\baselinestretch}{1.5}
\setlength{\topmargin}{-0.2in}
\setlength{\textwidth}{6in} %6.5in
\setlength{\oddsidemargin}{.3in}
\setlength{\evensidemargin}{.3in}  %were -.2in
\setlength{\textheight}{8.5in}
\setlength{\footskip}{0.5in}
\setlength{\parskip}{3pt plus 1pt minus 1pt}

%% \makeindex

%% superstring macros
\newcommand{\dplus}{\ifmmode {D^{+}} \else ${D^{+}}$ \fi}
\newcommand{\dminus}{\ifmmode {D^{-}} \else ${D^{-}}$ \fi}
\newcommand{\mrg}{\rightarrow}
\newcommand{\lar}{\leftarrow}
\newcommand{\pref}[2]{{\it pref}(#1,#2)}
\newcommand{\ovlp}[2]{{\it ov}(#1,#2)} 
\newcommand{\merge}[2]{{\it m}(#1,#2)} 
\newcommand{\dist}[2]{{\it d}(#1,#2)}
\newcommand{\cost}[2]{{\it c}(#1,#2)}
\newcommand{\length}[1]{{\it l}(#1)}
\newcommand{\weight}[1]{{\it w}(#1)}
\newcommand{\card}[1]{{\it card}(#1)}
\newcommand{\first}[1]{{\it FIRST}(#1)}
\newcommand{\follow}[1]{{\it FOLLOW}(#1)}
\newcommand{\action}[1]{{\it ACTION}(#1)}
\newcommand{\goto}[1]{{\it GOTO}(#1)}
\newcommand{\qed}{\ \ \ \rule{7pt}{8pt}\medskip}
\newcommand{\partialqed}{\ \ \ \raisebox{2pt}{\framebox[7pt]{\ }}\medskip}
\newtheorem{defin}{Definition}
\newcommand{\bracket}[1]{\langle #1 \rangle}
\newcommand{\barr}{\overline}
\newcommand{\Gee}{G_S}
\newcommand{\Geep}{G_{P,N}}
\newcommand{\cyc}[1]{{\it CYC}(#1)}
\newcommand{\CYC}{{\it CYC}(G_S)}
\newcommand{\cycn}[1]{{\it CYC1}(#1)}
\newcommand{\tsp}[1]{{\it TSP}(#1)}
\newcommand{\TSP}{{\it TSP}(G_S)}
\newcommand{\opt}[1]{{\it OPT}(#1)}
\newcommand{\optn}[1]{{\it OPT1}(#1)}
\newcommand{\OPT}{{\it OPT}(P,N)}
%\newcommand{\SS}{{\cal S}}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
% \newcommand{\copt}{C_{\rm opt}}
\newcommand{\spi}{S_{\pi}}
\newcommand{\shift}[1]{{\it rotate}(#1)}
\newcommand{\str}[1]{{\it strings}(#1)}
\newcommand{\period}[1]{{\it period}(#1)}
\newcommand{\factor}[1]{{\it factor}(#1)}
\newcommand{\stri}[2]{{\it strings}(#1,#2)}
\newcommand{\weako}{o_w}
\newcommand{\culpo}{o_c}
%end of superstring special macros

%General Forms
% \newcommand{\proof}{\noindent {\bf Proof:}\space}
\newcommand{\proof}{{\bf Proof. \enspace}}
\newcommand{\comment}[1]{}
\newcommand{\hs}{\enspace}
\newcommand{\hhs}{\thinspace}
\newcommand{\diverges}{\uparrow}
\newcommand{\converges}{\downarrow}
\newcommand{\inter}{\bigcap}
\newcommand{\real}{\ifmmode {\rm R} \else ${\rm R}$ \fi}
\newcommand{\nat}{\ifmmode {\rm N} \else ${\rm N}$  \fi}
\newcommand{\tot}{\ifmmode {\cal T} \else ${\cal T}$ \fi}
\newcommand{\sigstar}{\ifmmode \Sigma^{\ast} \else $\Sigma^{\ast}$ \fi}

\newtheorem{theorem}{\sc Theorem}[section]
% \newtheorem{lemma}{Lemma}
\newtheorem{lemma}[theorem]{\sc Lemma}
% \newtheorem{corollary}{Corollary}
\newtheorem{corollary}[theorem]{\sc Corollary}
% \newtheorem{definition}{Definition}
\newtheorem{definition}{\sc Definition}[section]
% \newtheorem{fact}{Fact}
% \newtheorem{claim}{Claim}
\newtheorem{claim}[theorem]{\sc Claim}
% \newtheorem{conjecture}{Conjecture}
\newtheorem{conjecture}[theorem]{\sc Conjecture}
\newlength{\thislabel}
\newcommand{\labsize}[1]{\settowidth{\thislabel}{#1}}
\newtheorem{example}{\sc Example}[section]
%\newenvironment{example}{\begin{example}}
%{\hspace*{\fill}$\Diamond$\end{example }}
\def\lablimer2stlabel#1{\rm #1\hfil}

%%%%%%% KSN macros
\newcommand{\emptystring}{\epsilon}
\newcommand{\Vars}{V}   % variables in a grammar; I strongly prefer V.
\newcommand{\rmbrak}[1]{\mbox{$<$#1$>$}}
% \newcommand{\rmbrak}[1]{\mbox{$\langle$#1$\rangle$}}  %% may look better.

\pagestyle{plain}
\sloppy

\begin{document}
%% \sloppy
%% \setcounter{chapter}{12}
%% \chapter{}
\title{Formal Grammars and Languages
%% \footnote{Preliminary version of
%% a chapter in the forthcoming {\it CRC Handbook of Algorithms and Theory of
%% Computation.}}
}

%% Formal grammars (including regular
%% expressions, cfg's and csg's etc).  Language recognition
%% algorithms (for CFL, Younger-Kasami), lexical analysis,
%% parsing algorithms (bottom up, simple precedence parsing,
%% LR(k); top-down parsing, recursive descent parsing, LL(k))

\author{
Tao Jiang\\
Department of Computer Science\\
McMaster University\\
Hamilton, Ontario L8S 4K1, Canada
\and
Ming Li\\
Department of Computer Science\\
University of Waterloo\\
Waterloo, Ontario N2L 3G1, Canada
\and
Bala Ravikumar\\
Department of Computer Science\\
University of Rhode Island\\
Kingston, RI 02881, USA}

\date{}

\maketitle

\section{Introduction} \label{intro}
Formal language theory
%
% is believed to have originated
% KSN: Sounds like archaeology.
% Plus this kind-of contradicted later things said about Post and Thue.
%
as a discipline is generally regarded as growing from
the work of linguist Noam Chomsky
in the 1950s, when he attempted to give a precise
characterization of the structure of natural
languages.  His goal was to define the syntax of languages
using simple and precise mathematical
rules.  Later it was found that the syntax of
programming languages can be described using
one of Chomsky's grammatical models called
context-free grammars. Much earlier, the Norwegian
mathematician Axel Thue studied sequences of binary symbols
subject to interesting mathematical properties,
such as not having the same substring three times in
a row.
%
% KSN: first names for consistency? Editor? I'll need to look afresh
% at all 3 chapters on this issue.  But I vote for distinguishing
% Thue, Post, Chomsky, and Kleene.  The next clause was removable.
%
% at the turn of the century also made a significant impact in the
% development of formal languages.
%
His work influenced Emil Post, Stephen Kleene, 
and others to study the mathematical properties of 
strings and collections of strings.

% Collections of strings known as {\it languages} became central to
% computer science as it was realized
% soon after the advent of modern electronic computers
% that all forms of information (whether
% numbers, names, pictures or sound waves) can be represented as strings.
%
Soon after the advent of modern electronic computers, people realized
that all forms of information---whether
numbers, names, pictures, or sound waves---can be represented as strings.
Then collections of strings known as {\it languages\/} became central to
computer science.
This section is concerned with fundamental mathematical properties of 
languages and language generating systems, such as grammars.
Every programming language
%
% including Pascal, C, or Fortran
%
from Fortran to Java can be precisely described by a 
grammar. Moreover, the grammar allows us to write a computer program
(called the {\em syntax analyzer\/} in a compiler)
to determine whether a string of
statements is syntactically correct
in the programming language. 
%
% Wouldn't it be nice to also have...
% KSN: I made the pgh more authoritative and eliminated the footnote
% and the clumsy "where they originally arose" in regard to NLP.
%
Many people would wish that natural languages such as English could
be analyzed as precisely, that we could write computer programs
to tell which English sentences are grammatically correct.
Despite recent advances in {\em natural language processing\/},
many of which
have been spurred by formal grammars and other theoretical tools,
today's commercial products for grammar and style fall well
short of that ideal.  The main problem is that {\em there is no
common agreement\/} on what are grammatically correct (English)
sentences; nor has anyone yet been able to offer a grammar precise
enough to propose as definitive.  And style is a matter of taste!~such
as not beginning sentences with ``and'' or using interior exclamations.
%
% and a corresponding computer program to tell us what strings of words
% are grammatically correct English sentences.\footnote{Actually, English
% and the other natural languages have grammars; but these grammars are
% not precise enough to tell apart the correct and incorrect sentences
% with one hundred percent accuracy. The main problem is that
% {\em there is no universal agreement\/}
% on what are grammatically correct English sentences.}
% 
Formal languages and grammars have many applications in other fields,
including
molecular biology (see~\cite{Searls}) and
symbolic dynamics (see~\cite{Lind and Marcus}).

In this chapter, we will present some formal systems that define families of formal languages arising
in many computer science applications.
Our primary focus will be on context-free languages, since
they are most widely used to describe the syntax of programming languages. 
In the rest of this section, we present some basic definitions and
terminology.

\begin{definition}\label{tao.def1}
\rm
An {\bf alphabet} is a finite nonempty set of {\em symbols}.
Symbols are assumed to be indivisible.
\end{definition}

% For example, the alphabet for English consists of the $26$ upper-case
% letters $A, B, \ldots, Z$ and $26$ lower-case letters $a, b, \ldots, z$.
% KSN: /The/ alphabet?  I could not resist adding the following.
%
For example, an alphabet for English can consist of as few as the
$26$ lower-case letters $a,b,\dots,z$, adding some punctuation symbols
if sentences rather than single words will be considered.
Or it may include all of the symbols on a standard North American
typewriter, which together with terminal control codes
yields the 128-symbol ASCII alphabet, in which much of the world's
communication takes place.  The new world standard is an
alphabet called {\em UNICODE\/}, which is intended to provide symbols for
all the world's languages---as of this writing, over 38,000
symbols have been assigned.  But most important aspects of formal
languages can be modeled using the simple two-letter alphabet
$\{0,1\}$, over which ASCII and UNICODE are encoded to begin with. 
We usually use the symbol $\Sigma$ to denote an alphabet.

\begin{definition}\label{tao.def2}
\rm
A {\bf string} over an alphabet $\Sigma$ is a finite sequence of symbols
of $\Sigma$.
\end{definition}

The number of symbols in a string $x$ is called its {\em length},
denoted by $|x|$.  It is convenient to introduce a notation
$\emptystring$
for the empty string,
which contains no symbols at all. The length of
$\epsilon$ is $0$. 

\begin{definition}\label{tao.def3}
\rm
Let $x = a_1 a_2 \cdots a_n$ and $y = b_1 b_2 \cdots b_m$ be two strings.
The {\em concatenation} of $x$ and $y$, denoted by $xy$, is the string
$a_1 a_2 \cdots a_n b_1 b_2 \cdots b_m$.
\end{definition}

Then for any string $x$, $\epsilon x = x \epsilon = x$.
For any string $x$ and integer $n \ge 0$, we use $x^n$ to denote the
string formed by sequentially concatenating $n$ copies of $x$.

\begin{definition}\label{tao.def4}
\rm
The set of all strings over an alphabet $\Sigma$ is denoted 
by $\Sigma^*$, and
the set of all nonempty strings over $\Sigma$ is denoted by $\Sigma^+$.
The empty set of strings is denoted by $\emptyset$.
\end{definition}

\begin{definition}\label{tao.def5}
\rm
For any alphabet $\Sigma$, a {\bf language} over $\Sigma$ is a set of
strings over $\Sigma$.
The members of a language are also called the {\em words\/}
of the language.
\end{definition}

\begin{example}\label{tao.ex1}
\rm
The sets $L_1 = \{01,11,0110\}$ and $L_2 = \{0^n1^n| n \ge 0\}$
are two languages over the binary alphabet $\{0,1\}$. 
$L_1$ has three words, while $L_2$ is infinite.  The string $01$ is
in both languages while $11$ is in $L_1$ but not in $L_2$. 
\end{example}

Since languages are just sets, standard set operations such as union,
intersection, and complementation apply to languages.
It is useful to introduce two more operations for languages:
{\em concatenation\/} and {\em Kleene closure\/}.

\begin{definition}\label{tao.def6}
\rm
Let $L_1$ and $L_2$ be two languages over $\Sigma$.
The concatenation of $L_1$
and $L_2$, denoted by $L_1 L_2$,
is the language $\{xy | x \in L_1, y \in L_2\}$. 
\end{definition}

\begin{definition}\label{tao.def7}
\rm
Let $L$ be a language over $\Sigma$. Define $L^0 = \{\emptystring\}$ and
$L^i = L L^{i-1}$ for $i \ge 1$. The {\em Kleene closure} of $L$,
denoted by $L^*$, is the language
\[
L^* = \bigcup_{i \ge 0} L^i.
\]
% STYLE: The $$ or \[, \] for equations should be on lines by themselves.
% There is nothing wrong with a period or comma in an equation.
% 
The {\em positive closure} of $L$, denoted by $L^+$, is the language
\[
L^+ = \bigcup_{i \ge 1} L^i.
\]
%% Maybe no need to have positive closure?  KSN: Fine to keep it.
\end{definition}

In other words, the Kleene closure of a language $L$ consists of all
strings that can be formed by concatenating zero or more words from $L$.
For example, if $L = \{0,01\}$, then $LL = \{00, 001, 010, 0101\}$, and
$L^*$ comprises all binary strings in which every $1$ is preceded by a $0$. 
Note that concatenating zero words always gives the empty string,
and that a string with no 1s in it still makes the condition on
``every 1'' true.
$L^+$ has the meaning ``concatenate {\em one\/} or more words from $L$,''
%
% except it excludes $\emptystring$ in this case.
% KSN: Careful---if \emptystring \in L, it is not "excluded".
%
and satisfies the properties $L^* = L^+ \cup \{\emptystring\}$ and
$L^+ = L L^*$.  Furthermore,
for any language $L$, $L^*$ always contains $\emptystring$, and
$L^+$ contains $\emptystring$ if and only if $L$ does.
Also note that $\Sigma^*$ is in fact the Kleene closure of the alphabet
$\Sigma$ when $\Sigma$
is viewed as a language of words of length~$1$, and
$\Sigma^+$ is just the positive closure of $\Sigma$.
%% a bit unclear.
% KSN: I made it a little less unclear.  The pgh makes the 
% novice reader work a little, but that's what you want.


\section{Representation of Languages}\label{sec.rep}
In general a language over an alphabet $\Sigma$ is a subset of $\Sigma^*$. 
How can we describe a language rigorously so that we know 
whether a given string
belongs to the language or not?  As shown in 
Eaxmple~\ref{tao.ex1}, a finite language
such as $L_1$ can be explicitly defined by
enumerating its elements.  An infinite language such as
$L_2$ cannot be exhaustively enumerated, but in the case of $L_2$
we were able to give a simple rule characterizing all of its members.
In English, the rule is, ``some number of 0s followed by an
equal number of 1s.''
Can we find systematic methods for defining rules that
characterize a wide class of languages?
In the following we will introduce three such methods:
{\bf regular expressions},
{\bf pattern systems}, and {\bf grammars}.
Interestingly, only the last is capable of specifying the simple rule
for $L_2$, although the first two work for many intricate languages.
% 
% Languages that can be described
% by some systematic body of rules
% are often referred to as {\em formal languages\/}.
% KSN: "often" referred to as?  Since it's the title of the chapter,
% a less offhand wording is needed, as are subsections here.
%
The term {\bf formal languages} refers to languages that can be
described by a body of systematic rules.

\subsection{Regular Expressions and Languages}\label{KSN.regexp}
Let $\Sigma$ be an alphabet.

\begin{definition}\label{tao.def8}
\rm
The {\bf regular expressions} over $\Sigma$
and the languages they 
represent are defined inductively as follows.
\begin{enumerate}
\item
The symbol $\emptyset$ is a regular expression,
and represents the empty language.
%
% KSN: "represents" and "language" for consistency.
\item
The symbol $\emptystring$ is a regular expression, 
and represents the language whose only member is the
empty string, namely $\{\emptystring\}$.
\item
For each $c \in \Sigma$, $c$ is a regular expression, 
and represents the language $\{c\}$, whose only member is the
string consisting of the single character $c$.
%
% KSN: "a" and "b" are used as literals further below.  
% Hence I used "c" for "character" globally.
% The change in wording from the previous item is deliberate.
\item
If $r$ and $s$ are regular expressions representing the languages
$R$ and $S$, then $(r+s)$, $(rs)$ and $(r^*)$ are regular expressions 
that represent the languages $R \cup S$, $RS$, and $R^*$, respectively.
\end{enumerate}
\end{definition}

For example, $((0(0+1)^*)+((0+1)^*0))$ is a regular expression over 
$\{0,1\}$
that represents the language consisting of all binary strings that begin
or end with a $0$. Since the set operations union and concatenation are
both associative, and since we can stipulate that
Kleene closure takes precedence over concatenation
and concatenation over union,
many parentheses can be omitted from regular expressions.
For example, the
above regular expression can be written as $0(0+1)^*+(0+1)^*0$.
We will also abbreviate the expression $rr^*$ as $r^+$.
Let us look at a few more examples of regular expressions and the languages
they represent. 

\begin{example}\label{tao.ex2}
\rm
The expression $0(0+1)^*1$ represents the set of all strings
that begin with a $0$ and end with a $1$.
\end{example}

\begin{example}\label{tao.ex3}
\rm
The expression $0+1+0(0+1)^*0+1(0+1)^*1$ represents the set of
all nonempty binary strings that begin and end with the same bit.
Note the inclusion of the strings $0$ and $1$ as special cases.
\end{example}

\begin{example}\label{tao.ex4}
\rm
The expressions $0^*$, $0^*10^*$, and $0^*10^*10^*$ represent
the languages consisting of strings that contain no $1$, exactly
one $1$, and exactly two $1$'s, respectively.
\end{example}

\begin{example}\label{tao.ex5}
\rm
The expressions $(0+1)^*1(0+1)^*1(0+1)^*$, $(0+1)^*10^*1(0+1)^*$,
$0^*10^*1(0+1)^*$, and $(0+1)^*10^*10^*$ all represent the same
set of strings that contain at least two $1$'s.
\end{example}

% For any regular expression $r$, the language represented by $r$ is denoted
% by $L(r)$.
%
% KSN: Not used.  This notation was used in the last chapter, where it
% was not defined, and I removed the use.
% 
Two or more regular expressions that represent the same language,
as in Example~\ref{tao.ex5}, are called
{\em equivalent\/}. It is possible to introduce algebraic identities
for regular expressions in order to construct equivalent
expressions.
Two such identities are $r(s+t) = rs+rt$, which says that concatenation
distributes over union the same way ``times'' distributes over ``plus''
in ordinary algebra (but taking care that concatenation isn't
commutative), and $r^* = (r^*)^*$.
These two identities are easy to prove; the reader seeking more
detail may consult~\cite{Salomaa}.

\begin{example}\label{tao.ex6}
\rm
Let us construct a regular expression for the set of all strings that contain
no consecutive $0$s. 
A string in this set may begin and end with a sequence of $1$s.
Since there are no consecutive $0$s, every $0$ that is not the last
symbol of the string must be followed by a $1$.
%
% Editor note style: no apostrophe in 0s or 1960s, etc.  --KSN
%
This gives
us the expression $1^*(01^+)^*1^*(\emptystring+0)$. It is not hard to see
that the second $1^*$ is redundant and thus the expression can in fact be
simplified to $1^*(01^+)^*(\emptystring+0)$.
\end{example}

% Editor, authors: Somewhere around here it would have been nice to
% include a description of the ``regular expression'' formalism
% that much software uses, including the text editor I'm using now.
% Perl has pretty much codified the UNIX grep/sed/awk notation
% into a standard.  This standard includes the formalism of 
% pattern languages and a little more.  For instance, I used the
% regular expression "\<([a-z]*)\>" to find strings like "<sentence>",
% and used the pattern reference "\1" in "\\rmbrak{\1}" to
% replace it by "\rmbrak{sentence}".  But it will have to wait. --KSN
%%
%% Answer: no objection if we can find some simple, informative
%% reg expr used in a popular language.

Regular expressions were first introduced by~\cite{Kleene} for studying
the properties of neural nets. The above examples illustrate that regular
expressions often give very clear and concise representations of languages.
The languages represented by regular
expressions are called the {\em regular languages\/}.
Fortunately or unfortunately, not every language is regular.
For example, there are no regular expressions that represent
the languages $\{0^n1^n | n \ge 1\}$ or $\{xx ~|~ x \in \{0,1\}^*\}$;
the latter case is proved at the end of Section~2.1 in Chapter~30. 
% 
% Later on, we will see that regular languages are exactly the class of
% languages generated by the so called {\em right-linear grammars}.
%
% Editor !! if this is "Chapter 31", then the proof is not "later on",
% it was given in "Chapter 30".
% I felt these remarks were not needed here, unless they make a
% *backward* reference.  Note my response to author comment below.--KSN
%
% This connection
% allows one to prove some interesting mathematical properties about regular
% languages as well as to design an efficient algorithm to determine whether
% a given string belongs to the language represented by a given regular 
% expression.
%  
%% So I have to prove equivalence of reg expr and regular grammar. no space
%% also deal with pumping lemmas for both reg lang and CFL?
%
% KSN: You did this proof in Ch. 30.  Also "back" in Ch. 30,
% I was able to insert an argument for {xx} etc. not being regular,
% where you had "already" mentioned this fact. 


\subsection{Pattern Languages}
Another way of representing languages is to use
{\em pattern systems\/}
%
% \cite{Angluin},~\cite{Jiang}.
% KSN: Unless you redefine or reappraise them, make the
% originating reference distinctive:
%
\cite{Angluin} (see also \cite{Jiang}).

\begin{definition}\label{tao.def9}
\rm
A {\bf pattern system} is a triple $(\Sigma, V, p)$, where $\Sigma$
is the alphabet, $V$ is the set of {\em variables\/} with
$\Sigma \cap V = \emptyset$,
and $p$ is a string over $\Sigma \cup V$ called the {\em pattern\/}. 
\end{definition}

% An example pattern system is $(\{0,1\},\{v_1,v_2\},v_1v_10v_2)$.
% KSN: The reader can't interpret it until after the next defn anyway.
 
\begin{definition}\label{tao.def10}
\rm
The language generated by a pattern system $(\Sigma, V, p)$
consists of all strings over $\Sigma$ that can be obtained
from $p$ by replacing each variable in $p$ with a string over $\Sigma$.
\end{definition}

An example pattern system is $(\{0,1\},\{v_1,v_2\},v_1v_10v_2)$.
The language it generates 
contains all words that begin with a $0$ (since $v_1$ can be chosen
as the empty string, and $v_2$ as an arbitrary string), and
contains some words that begin with a $1$, such as
$110$ (by taking $v_1 = 1$, $v_2 = \emptystring$) and
$101001$ (by taking $v_1 = 10$, $v_2 = 1$).
However, it does not contain the strings
$\emptystring,1,10,11,100,101$, etc.   
The pattern system
$(\{0,1\}, \{v_1\}, v_1v_1)$ generates the set of all strings 
that are the
concatenation of two equal substrings, namely the set
$\{xx| x \in \{0,1\}^*\}$. The languages generated by pattern systems are
called {\em pattern languages\/}.

Regular languages and pattern languages are really different.
We have noted that the pattern language $\{xx| x \in \{0,1\}^*\}$
is not a regular language,
and one can prove that
the set represented by the regular expression
$0^*1^*$ is not a pattern language. Although it is easy to write an
algorithm to decide whether a given string
is in the language generated by a given pattern
system, such an algorithm would most likely have to be very
inefficient~\cite{Angluin}.

\subsection{General Grammars}
Perhaps the most useful and general system for representing languages
is based on the formal notion of a {\em grammar\/}.
%
% which are extensions of the pattern systems.
% Umm...at least, it would look like an anachronism with 1980.  --KSN

\begin{definition}\label{tao.def11}
\rm
A {\bf grammar} is a quadruple $(\Sigma,\Vars,S,P)$, where:
\begin{enumerate}
\item
$\Sigma$ is a finite nonempty set called the {\bf terminal alphabet}.
The elements of $\Sigma$ are called the {\bf terminals}.
\item
$\Vars$ is a finite nonempty set disjoint from $\Sigma$. The elements of
$\Vars$ are called the {\bf nonterminals} or {\bf variables}.
\item
$S \in \Vars$ is a distinguished nonterminal called the {\bf start symbol}.
\item $P$ is a finite set of {\bf productions} (or {\bf rules}) of the form
\[
\alpha \rightarrow \beta
\]
where $\alpha \in (\Sigma \cup \Vars)^*\Vars(\Sigma \cup \Vars)^*$ and
$\beta \in (\Sigma \cup \Vars)^*$, {\it i.e.} $\alpha$ is a string of terminals
and nonterminals containing at least one nonterminal and $\beta$ is a string
of terminals and nonterminals.
\end{enumerate}
\end{definition}

\begin{example}\label{tao.ex7}
\rm
Let $G_1 = (\{0,1\},\{S,T,O,I\},S,P)$, where $P$ contains the
following productions
\begin{eqnarray*}
%% S & \rightarrow & 0S1 \\
%% S & \rightarrow & \emptystring. 
S & \rightarrow & OT \\
S & \rightarrow & OI \\
T & \rightarrow & SI \\
O & \rightarrow & 0 \\
I & \rightarrow & 1 
\end{eqnarray*}
As we shall see, the grammar $G_1$ can be used to describe the set 
$\{0^n1^n | n \ge 1\}$.
\end{example}

\begin{example}\label{tao.ex8}
\rm
Let $G_2 = (\{0,1,2\},\{S,A\},S,P)$, where $P$ contains the following
productions
\begin{eqnarray*}
S & \rightarrow & 0SA2 \\
S & \rightarrow & \emptystring \\
2A & \rightarrow & A2 \\
0A & \rightarrow & 01 \\
1A & \rightarrow & 11 
\end{eqnarray*}
This grammar $G_2$ can be used to describe the set $\{0^n1^n2^n \ge n \ge 0\}$.
\end{example}

\begin{example}\label{tao.ex9}
\rm
To construct a grammar $G_3$ to describe English sentences, 
one might let the alphabet
$\Sigma$ comprise all English {\em words\/} rather than letters.
$\Vars$ would contain nonterminals
that correspond to the structural components in an English sentence,
such as
%
% KSN: The spacing in <...> below looked possibly bad enough to fool a
% compositor, and the centering was inconsistent with the above (!), 
% so I made a mode-free "\rmbrak" command to fix the former,
% and used \eqnarray* again to fix the latter.
%
\rmbrak{sentence}, \rmbrak{subject}, \rmbrak{predicate}, \rmbrak{noun},
\rmbrak{verb},
\rmbrak{article}, and so on.
The start symbol would be \rmbrak{sentence}. Some typical productions are:
%
\begin{eqnarray*}
\rmbrak{sentence} &\rightarrow& \rmbrak{subject} \rmbrak{predicate}\\
\rmbrak{subject} &\rightarrow& \rmbrak{noun}\\
\rmbrak{predicate} &\rightarrow& \rmbrak{verb} \rmbrak{article} \rmbrak{noun}\\
\rmbrak{noun} &\rightarrow& \mbox{mary}\\
\rmbrak{noun} &\rightarrow& \mbox{algorithm}\\
\rmbrak{verb} &\rightarrow& \mbox{wrote}\\
\rmbrak{article} &\rightarrow& \mbox{an}
\end{eqnarray*}
%
The rule $\rmbrak{sentence} \rightarrow \rmbrak{subject} \rmbrak{predicate}$
models the fact that a sentence can consist of a subject phrase and
a predicate phrase.
%
% "Go figure!"  But AOK by me (the subject "you" is implicit here). --KSN
% Second thought: the reading of "-->" as "can consist of" is IMPT
% when you have multiple RHS's; I use it in my classes, so also here.
%
The rules $\rmbrak{noun} \rightarrow \mbox{mary}$
and $\rmbrak{noun} \rightarrow \mbox{algorithm}$ mean that both ``mary'' and
``algorithm'' are possible nouns.
%
% KSN: The following is a gratuitous but interesting addition.
% I had "S = NV" in fourth or fifth grade, and some students in my
% classes, much less so now than ten years ago, recognize it.
%
This approach to grammar, stemming from Chomsky's work,
has influenced even elementary-school teaching.
\end{example}

To explain how a grammar represents a language, we need the following
concepts.

\begin{definition}\label{tao.def12}
\rm
Let $(\Sigma,\Vars,S,P)$ be a grammar. A {\bf sentential form}
of $G$ is any string
of terminals and nonterminals, i.e.\ a string over $\Sigma \cup \Vars$.
%
% Authors, editor: Many sources restrict the term to a string
% derivable from S, or from some variable, but this is AOK by me,
% as well as useful nomenclature in what follows. --KSN
%
%% Answer: Some sources don't restrict. Also derivation is undefined yet.
\end{definition}

\begin{definition}\label{tao.def13}
\rm
Let $(\Sigma,\Vars,S,P)$ be a grammar, and 
let $\gamma_1, \gamma_2$ be two sentential
forms of $G$.
We say that $\gamma_1$ {\bf directly derives} $\gamma_2$, written
%
% Relations are "written", nouns "denote" (picky but useful style).--KSN  
%
$\gamma_1 \Rightarrow \gamma_2$, if $\gamma_1 = \sigma \alpha \tau$,
$\gamma_2 = \sigma \beta \tau$, and $\alpha \rightarrow \beta$ is a
production in $P$.
\end{definition}

For example, the sentential form $00S11$ directly derives the sentential
form $00OT11$ in grammar $G_1$, and $A2A2$ directly derives
$AA22$ in grammar $G_2$.

\begin{definition}\label{tao.def14}
\rm
Let $\gamma_1$ and $\gamma_2$ be two sentential forms of a grammar $G$.
We say that $\gamma_1$ {\bf derives} $\gamma_2$, written
$\gamma_1 \Rightarrow^* \gamma_2$, if there exists a sequence of (zero or more)
sentential forms $\sigma_1, \ldots, \sigma_n$ such that
\[ \gamma_1 \Rightarrow \sigma_1 \Rightarrow \cdots \Rightarrow \sigma_n
\Rightarrow \gamma_2. \]
The sequence
$\gamma_1 \Rightarrow \sigma_1 \Rightarrow \cdots \Rightarrow \sigma_n
\Rightarrow \gamma_2$ is called a {\bf derivation}
of $\gamma_2$ from $\gamma_1$.
\end{definition}

For example, in grammar $G_1$, $S \Rightarrow^* 0011$ because
\[ S \Rightarrow \underline{O}T \Rightarrow 0\underline{T} \Rightarrow
0S\underline{I} \Rightarrow 0\underline{S}1 \Rightarrow 
0\underline{O}I1 \Rightarrow 00\underline{I}1 \Rightarrow 0011 \]
and in grammar $G_2$, $S \Rightarrow^* 001122$ because
\[ S \Rightarrow 0\underline{S}A2 \Rightarrow 00\underline{S}A2A2 \Rightarrow
0\underline{0A}2A2 \Rightarrow 001\underline{2A}2 
\Rightarrow 001\underline{1A}22 \Rightarrow 001122. \]
Here the left-hand side of the relevant production in each derivation step
is underlined for clarity.

\begin{definition}\label{tao.def15}
\rm
Let $(\Sigma,\Vars,S,P)$ be a grammar. The language generated by $G$,
denoted by $L(G)$, is defined as
\[
L(G) = \{x | x \in \Sigma^*, S \Rightarrow^* x\}.
\]
The words in $L(G)$ are also called the {\em sentences} of $L(G)$.
\end{definition}

Clearly, $L(G_1)$ contains all strings of the form $0^n1^n$, $n \ge 1$,
and $L(G_2)$ contains all strings of the form $0^n1^n2^n$, $n \ge 0$.
Although only a partial definition of $G_3$ is given, we 
know that $L(G_3)$ contains sentences like 
``mary wrote an algorithm'' and ``algorithm wrote an algorithm,'' but
does not contain strings like ``an wrote algorithm.''

Formal grammars were introduced as such by ~\cite{Post},
and had antecedents in work by Thue and others.
%
%% and perhaps earlier?
% [^^^author's query]
% KSN: Yes,---you already mentioned Thue above, so I did here.
% BTW, Post began his work in the 1920s as a little-known schoolteacher.
%  I also favor crediting Thue too.
However, the study of their rigorous use in describing
formal (and natural) languages
did not begin until the mid-1950s~\cite{Chomsky1}.
In the next section, we consider various restrictions on the form of
productions in a grammar, and see how these restrictions can affect its
power to represent languages. In particular, we will show
that regular languages and pattern languages can all be generated by
grammars under different restrictions. 

\section{Hierarchy of Grammars}\label{sec.hie}
Grammars can be divided into four classes by gradually increasing the
restrictions on the form of the productions. Such a classification is due to
Chomsky~\cite{Chomsky1,Chomsky2} and is called the {\em Chomsky hierarchy\/}.

\begin{definition}\label{tao.def16}
\rm
Let $G = (\Sigma,\Vars,S,P)$ be a grammar. 
\begin{enumerate}
\item 
$G$ is also called a {\bf Type-$0$} grammar or an
{\bf unrestricted} grammar.
\item
$G$ is a {\bf Type-1} or {\bf context-sensitive} 
grammar if each production
$\alpha \rightarrow \beta$ in $P$ 
%
% either has the form $S \rightarrow \emptystring$ or
% KSN: /Oops/.  This allows non-recursive languages.  Take any grammar G,
% make a new start symbol Z, add Z --> #S | \emptystring, and pad every
% RHS of a production in G by Z's.  Then  L(G') n #\Sigma^* = #L(G).
% The "special dispensation" clause is also useful below.   
%
%% Thanks for the correction.
satisfies $|\alpha| \leq |\beta|$.
By ``special dispensation,'' we also allow a Type-1 grammar to have the
production $S \rightarrow \emptystring$, provided $S$ does not appear
on the right-hand side of any production.
\item
$G$ is a {\bf Type-2} or {\bf context-free} 
grammar if each production
$\alpha \rightarrow \beta$ in $P$ satisfies $|\alpha| = 1$;
i.e., $\alpha$ is a single nonterminal.
\item
$G$ is a {\bf Type-$3$} or {\bf right-linear} or {\bf regular} 
grammar if
each production has one of the following three forms:
\[
A \rightarrow cB,~~~ A \rightarrow c,~~~A \rightarrow \emptystring, \]
where $A,B$ are nonterminals (with $B = A$ allowed) and $c$ is a terminal.
\end{enumerate}
\end{definition}

The language generated by a Type-$i$ 
grammar is called a Type-$i$ language,
$i = 0,1,2,3$. A Type-$1$ language is also called a {\bf context-sensitive
language} (CSL),
and a Type-$2$ language is also called a {\bf context-free language} (CFL).
The ``special dispensation'' allows a CSL to contain $\emptystring$,
and thus allows one to say that every CFL is also a CSL.
Many sources allow ``right-linear'' grammars to have productions
of the form $A \rightarrow xB$, where $x$ is any string of terminals,
and/or exclude one of the forms $A \rightarrow c$,
$A \rightarrow \emptystring$ from their definition of ``regular''
grammar (perhaps allowing $S \rightarrow \emptystring$ in the 
latter case).
% 
% KSN: Enough texts differ to warrant saying this, and my rewrite of
% the authors' next statement helps, too.
%
% It turns out that every Type-$3$ language is in fact a regular
% language, {\it i.e.} it is represented by some regular expression,
% and vice versa~\cite{HU79}.
%
Regardless of the choice of definitions, every Type-3 grammar generates
a regular language, and every regular language has a Type-3 grammar;
we have proved this using finite automata in Chapter~30.
Stated in other words:

%% See Chapter 29 for the proof of the equivalence of
%% Type-$3$ (right-linear) grammars and regular expressions.
%%%% If Ming will show this, we then move this theorem to Ming section,
%%%% and modify.
% KSN: He did.  If chapters are switched, "have proved"-->"will prove".
% "Chapter 29" is a misnomer for "30"---I fixed it below, too.

\begin{theorem}\label{tao.thm1}
The class of Type-$3$ languages and the class of regular languages
are equal.
\end{theorem}

The grammars $G_1$ and $G_3$ given in the last section are
context-free and the grammar $G_2$ is context-sensitive. Now we give
some examples of unrestricted and right-linear grammars.

\begin{example}\label{tao.ex10}
\rm
Let $G_4 = (\{0,1\},\{S,A,O,I,T\},S,P)$, where $P$ contains
\[
\begin{array}{rclcrcl}
S & \rightarrow  & AT && & &  \\
A & \rightarrow  & 0AO && A & \rightarrow  & 1AI \\
O0 & \rightarrow & 0O && O1 & \rightarrow & 1O \\
I0 & \rightarrow & 0I && I1 & \rightarrow & 1I \\
OT & \rightarrow & 0T  && IT & \rightarrow & 1T \\
A & \rightarrow  & \emptystring && T & \rightarrow & \emptystring 
\end{array}
\]
Then $G_4$ generates the set $\{xx|x \in \{0,1\}^*\}$.
%
% KSN: My addition here is needed; this one is much harder to
% understand than grammar $G_2$ above.  Plus I slipped in an
% example of what "context-sensitive" /means/.
%
To understand how this grammar works, think of the nonterminal $O$
as saying, ``I must ensure that the right half gets a terminal $0$
in the same place as the terminal $0$ in the production
$A \rightarrow 0AO$ that introduced me.''  The nonterminal $I$
eventually
forces the precise placement of a terminal $1$ in the right-hand side
in the same way.
The nonterminal $T$ makes sure that $O$ and $I$ place their $0$ and $1$
on the right-hand side rather than prematurely.  Only after
every $O$ and $I$ has moved right past any earlier-formed terminals
$0$ and $1$ and been eliminated ``in the context of'' $T$, and
the production $A \rightarrow \emptystring$ is used to signal
that no additional $O$ or $I$ will be introduced, can the endmarker $T$
be dispensed with via $T \rightarrow \emptystring$.  
For example,
we can derive the word $0101$ from $S$ as follows:
\[
S \Rightarrow \underline{A}T \Rightarrow 0\underline{A}OT
\Rightarrow 01\underline{A}IOT \Rightarrow
01I\underline{OT} \Rightarrow 01\underline{I0}T
\Rightarrow 010\underline{IT} \Rightarrow 0101\underline{T}
\Rightarrow 0101.
\]
%
% And this addition saves a long and obtrusive
% example later; see comment with "dangles" below.  --KSN
%
%% The "subtitle" is good.
Only the productions $A \rightarrow \emptystring$ and
$T \rightarrow \emptystring$ prevent this grammar from being Type-1.
The interested reader is challenged to write a Type-1
grammar for this language.
\end{example}

\begin{example}\label{tao.ex11}
\rm
We give a right-linear grammar $G_5$ to generate the language represented
by the regular expression in Example~\ref{tao.ex3}, i.e., the
set of all nonempty binary strings beginning and ending with the same bit.
Let $G_5 = (\{0,1\},\{S,O,I\},S,P)$, where $P$ contains
\[
\begin{array}{rclcrcl}
S & \rightarrow  & 0O && S & \rightarrow  & 1I \\
S & \rightarrow  & 0 && S & \rightarrow  & 1 \\
O & \rightarrow  & 0O && O & \rightarrow  & 1O \\
I & \rightarrow  & 0I && I & \rightarrow  & 1I \\
O & \rightarrow  & 0 && I & \rightarrow  & 1 
\end{array}
\]
Here $O$ means to remember that the last bit must be a $0$,
and $1$ similarly forces the last bit to be a $1$.
Note again how the grammar treats the words $0$ and $1$ as special cases.
\end{example}

% KSN: The definition of Chomsky normal form is also important
% to give /here/ rather than in-passing on page 17.
% Notice how my writing ties in to the items immediately above and below.

Every regular grammar is a context-free grammar, but not
every context-free grammar is context-sensitive.  
However, every context-free grammar $G$ can be transformed into
an equivalent
one in which every production has the form $A \rightarrow BC$
or $A \rightarrow c$, where $A$, $B$, and $C$ are
(possibly identical) variables, and $c$ is a terminal.
If the empty string is in $L(G)$, then we can arrange to include
$S \rightarrow \epsilon$ under the same ``special dispensation''
as for CSLs.  This form is called 
{\bf Chomsky normal form} \cite{Chomsky2}, where it was used to
prove the case $i=1$ of the next theorem.
The grammar $G_1$ in the last section is an example of a
context-free grammar
in Chomsky normal form.    

% The following theorem is due to Chomsky~\cite{Chomsky1,Chomsky2}.

\begin{theorem}\label{tao.thm2}
For each $i = 0,1,2$, the class of Type-$i$ languages properly
contains the class of Type-$(i+1)$ languages.
\end{theorem}

% For example, one can prove by using a technique called {\em pumping}
% that the set $\{0^n1^n|n \ge 1\}$ is context-free but not regular,
% and the sets $\{0^n1^n2^n|n \ge 0\}$ and $\{xx|x \in \{0,1\}^*\}$ are
% context-sensitive but not context-free~\cite{HU79}.
% It is however a bit involved to construct a language that is
% of Type-$0$ but not context-sensitive.
% KSN: ?Oops, perhaps you were thinking of "recursive but not a CSL".

\noindent
The containments are clear from the above remarks.  For the
proper containments, we have already seen that
$\{0^n 1^n | n \geq 0\}$ is a Type-2 language that is
not regular, and Chapter~32 will show that the language of the
Halting Problem is Type-0 but not Type-1.  One can prove by a
technique called ``pumping'' that the Type-1 languages
$\{0^n1^n2^n|n \ge 0\}$ and $\{xx|x \in \{0,1\}^*\}$
are not Type-2.
See \cite{HU79} for this, and for a presentation of the
algorithm for converting a context-free grammar into
Chomsky normal form.   
%
% See, {\it e.g.}~\cite{HU79}, for such a language.

The four classes of languages in the Chomsky hierarchy have also been
completely characterized in terms of Turing machines (see Chapter 30)
and natural restrictions on them.
We mention this here to make the point that these characterizations
show that these classes capture fundamental properties of
computation, not just of formal languages.
A {\em linear bounded automaton\/} is a possibly-nondeterministic
Turing machine that on any input $x$ uses only the
cells initially occupied by $x$, except for one visit to the
blank cell immediately to the right of $x$ (which is
the initially-scanned cell if $x = \emptystring$).
Pushdown automata may also be nondeterministic and were
likewise introduced in Chapter~30.
%
% Editor, authors: checking this will also be part of the q. about
% re-arranging the chapters.  The pgh that was here was clumsy and
% made a mistake in pluralizing "worktapes...as pushdown stacks." --KSN
%
%% Answer: Fine by me.
\begin{theorem}\label{KSN.CH}
~
\begin{enumerate}
\item[(a)]
The class of Type-0 languages equals the class of languages
accepted by Turing machines.
% a bit verbose but precise for the reader and consistent with the above. 
\item[(b)]
The class of Type-1 languages equals the class of languages
accepted by linear bounded automata.
\item[(c)]
The class of Type-2 languages equals the class of languages
accepted by pushdown automata.
\item[(d)]
The class of Type-3 languages equals the class of languages
accepted by finite automata.
\end{enumerate}
\end{theorem}

% To show the basic idea involved,
% let us construct a context-sensitive grammar for
% the pattern language $\{xx|x \in \{0,1\}^*\}$. The grammar $G_4$
% given in Example~\ref{tao.ex10} for this language is almost
% context-sensitive. 
% We just have to get rid of the two $\emptystring$-productions:
% $A \rightarrow \emptystring$ and $T \rightarrow \emptystring$.
% A careful modification of $G_4$ results in the following
% grammar $G_6 = (\{0,1\},\{S,A_0,A_1,O,I,T_0,T_1\},S,P)$,
% where $P$ contains
%
% KSN: This example "dangles" since it doesn't actually "show the basic idea"
% on how LBAs recognize exactly the CSLs---no mention is made of a machine
% at all.  One would have had to add sentences saying how the 
% example derivation resembles a TM computation.  But my rewrite
% above handles the point well enough, and gets you to the last point
% of this section quickly.  Besides, the grammar itself looked ugly
% with the subscripts and O vs. 0.  (It did nicely illustrate
% the "special dispensation", though.)  NB: I renumbered the
% subsequent grammars G7--G9 using macros.  --KSN 
% \[
% \begin{array}{rclcrcl}
% S & \rightarrow & \emptystring && & & \\
% S & \rightarrow  & A_0T_0  && S & \rightarrow  & A_1T_1 \\
% A_0 & \rightarrow  & 0A_0O && A_0 & \rightarrow  & 1A_0I \\
% A_1 & \rightarrow  & 0A_1O && A_1 & \rightarrow  & 1A_1I \\
% A_0 & \rightarrow & 0 && A_1 & \rightarrow & 1 \\
% O0 & \rightarrow & 0O && O1 & \rightarrow & 1O \\
% I0 & \rightarrow & 0I && I1 & \rightarrow & 1I \\
% OT_0 & \rightarrow & 0T_0 && IT_0 & \rightarrow & 1T_0 \\
% OT_1 & \rightarrow & 0T_1 && IT_1 & \rightarrow & 1T_1 \\
% T_0 & \rightarrow & O && T_1 & \rightarrow & 1,
% \end{array}
% \]
% which is context-sensitive and generates $\{xx|x \in \{0,1\}^*\}$.
% For example, we can derive $011011$ as
% \[ S \Rightarrow \underline{A_1}T_1 \Rightarrow 0\underline{A_1}OT_1
% \Rightarrow 01\underline{A_1}IOT_1 \Rightarrow \]
% \[ 011I\underline{OT_1} \Rightarrow 011\underline{I0}T_1
% \Rightarrow 0110\underline{IT_1} \Rightarrow 01101\underline{T_1}
% \Rightarrow 011011. \]

% Editor, authors, IMPT: Chapter 32 refers often to the simulation
% of TMs by Type-0 grammars, even referring to "the proof in Chapter 31?",
% but it was never given.  On the principle that the proof should
% go closest to where it is referenced, it would go into Chapter 32.
% However, the /cleanest/ proof I know uses the standard Turing machine
% notation from Chapter 30, and putting it after the new "GOTO"
% notation in Chapter 32 would seem odd.  Hence it seems best to include
% the proof right here.  My proof (below in the "\comment") also
% handles "Type-1 = LBA" in the same swoop.  My only reason for not
% doing so now is that giving the proof may break the continuity of
% this section.  If you approve it and would like to use it, please let
% me know ASAP so I can update the remarks about the theorem below. --KSN
%
%% Author's answer: The proof looks good. Continuity isn't a problem since
%% we could include it right after the theorem (i.e. two theorems above).
%% Also we have to say that simulations of the grammars by TMs are trivial.  
%% My only concern is: what about parts (c) anbd (d)? I guess we can say
%% proof for part (d) is given in Ch 30; but then won't we also have to prove
%% part (c), which could be involved? I'll leave the decision to KSN.

% KSN2: I've done this below; I did have to make a nontrivial change to
% nail in the LBA case...

\begin{proof}
(a) Given a Type-0 grammar $G$, one can build a nondeterministic
Turing machine $M$ that accepts $L(G)$ by having $M$ first write the
start symbol $S$ of $G$ on a second tape.  $M$ always nondeterministically
chooses a production and chooses a place (if any) on its second
tape where it can be applied.  If and when the second tape becomes
an all-terminal string, $M$ compares it to its input, and if they
match, $M$ accepts.  Then $L(M) = L(G)$, and by Theorem~2.4 of Chapter~30,
$M$ can be converted into an equivalent deterministic single-tape
Turing machine.

For the reverse simulation of a TM by a grammar we give full details.
Given any TM $M_0$,
we may modify $M_0$ into an equivalent
TM $M = (Q,\Sigma,\Gamma,\delta,B,q_0,q_f)$
that has the following five properties:
(i) $M$ never writes a blank; (ii) $M$ when reading a
blank always converts it to
a non-blank symbol on the current step;
(iii) $M$ begins with a transition from $q_0$ that overwrites
the first input cell (remembering what it was)
by a special symbol $\wedge$ that is never altered;
(iv) $M$ never 
re-enters state $q_0$ or
moves left of $\wedge$; and
(v) whenever $M$ is about to accept, 
$M$ moves left to the $\wedge$, where it executes an instruction that
moves right and enters a distinguished state $q_e$.
In state $q_e$ it overwrites any non-blank character by a special
new symbol $\#$ and moves right; when it hits the blank after having
$\#$-ed out the rightmost non-blank symbol on its tape, $M$ finally
goes to $q_f$ and accepts.
%
% KSN2: I changed (v) to make the LBA simulation "genau".

Given $M$ with these properties,
take $\Vars = \{S,A,\} \cup (Q \times \Gamma) \cup$
($\Gamma \setminus \Sigma$).  A single symbol
in $Q \times \Gamma$ is written using square brackets; e.g.\
$[q,c]$ means that $M$ is in state $q$ scanning character $c$.
The grammar $G$ has the following productions, which intuitively
can simulate any accepting computation by $M$ in reverse:
\begin{enumerate}
\item[(1)]
$S \rightarrow \wedge S_0;\quad S_0 \rightarrow \# S_0 ~|~ [q_e,\#]$;
\item[(2)]
$[r,d] \rightarrow [q,c]$, for all instructions $(q,c,d,r) \in \delta$
with $q,r \in Q$ and $c,d \in \Gamma$;
\item[(3)]
$c[r,B] \rightarrow [q,c]A$, for all $(q,c,R,r) \in \delta$;
\item[(4)]
$c[r,d] \rightarrow [q,c]d$, for all $(q,c,R,r) \in \delta$
and $d \in \Gamma$, $d \neq B$;
\item[(5)]
$[r,d]c \rightarrow d[q,c]$, for all $(q,c,L,r) \in \delta$ and
$d \in \Gamma$, $d \neq B$;
\item[(6)]
$[q_0,c] \rightarrow c$ for all $c \in \Sigma$, and
\item[(7)] 
$A \rightarrow \emptystring$.
\end{enumerate}
For all $x \in L(M)$, $G$ can generate $x$ by first using the
productions in (1) to lay down a $\#$ for every cell {\em used\/}
during the computation, using the productions (2)--(5) to
simulate the computation in reverse, using
(6) to restore the first
bit of $x$ 
(blank if $x = \emptystring$)
one step after having eliminated the nonterminal $\wedge$,
and using (7) to erase each $A$ marking an initially-blank cell that $M$ used.
Conversely, the only way $G$ can eliminate $\wedge$ and reach an
all-terminal string is by winding back an accepting computation
of $M$ all the way to state $q_0$ scanning the first cell.
Hence $L(G) = L(M)$.  

(b) If the given TM $M_0$ is a linear bounded automaton, then
we can patch the last construction to eliminate the productions in (3)
and (7), yielding a context-sensitive grammar $G$.
To do this, we need to make
$M$ postpone its one allowed
visit to the blank cell after the input until the last step of an
accepting computation.  To do this, we make $M$ nondeterministically guess
which bit of its input $x$ is the last one, and overwrite it by an immutable
right endmarker $\$$ the same way it did with $\wedge$ on the left.
Then we arrange that from state $q_e$, $M$ will accept only if
it sees a blank immediately to the right of the $\$$, meaning that its
initial guess delimited exactly the true input $x$.
(Technically this needs another state $q'_e$.)
Now $M$ never even scans a blank in the middle of an
accepting computation, and we can delete the
productions in (3) as well as (7).  Moreover, if $M_0$ accepts $\epsilon$,
we can add the production $S \rightarrow \emptystring$ allowed by the
``special dispensation'' for context-sensitive grammars above.
%
% KSN2: I try not to invoke the exception for the empty string in (a),
% because that makes the reduction noneffective, but it's OK in (b).

Going the other way, if the grammar $G$ in the first paragraph of this proof
is context-sensitive, then the resulting TM $M$ uses only $O(n)$ space,
and can be converted to an equivalent linear bounded
automaton by Theorem 3.1 of Chapter~30.

(c) Given a context-free grammar $G$, we may assume that $G$ is in
Chomsky normal form.  We can build a nondeterministic
PDA $M$ whose initial moves
lay down a bottom-of-stack marker $\wedge$ and the start symbol $S$
of $G$, and go to a ``central'' state $q$.  For every production of
the form $A \rightarrow BC$ in $G$, $M$ has moves that pop the stack
if $A$ is uppermost and push $C$ and then $B$, returning to state $q$.
For every production of the form $A \rightarrow c$, $M$ can pop an uppermost
$A$ from its stack if the currently-scanned input symbol is $c$;
then it moves its input head right.  If $G$ has the production
$S \rightarrow \emptystring$ as a special case, then $M$ can pop 
the initial $S$.  A computation path 
accepts if and only if the stack gets down to $\wedge$ precisely
when $M$ reaches the blank at the end of its input $x$.
Then accepting paths of $M$ on an input $x$ are in 1-1 correspondence
with leftmost derivations (see below)
of $x$ in $G$, so $L(M) = L(G)$.

Going from a PDA $M$ to an equivalent CFG $G$ is much trickier,
and is covered well in \cite{HU79}.

(d) This has been proved in Chapter~30, Theorem 2.2.
\end{proof}


Since $\{xx|x \in \{0,1\}^*\}$ is a pattern language, we know
from discussions above
that the class of pattern languages is not
contained in the class of context-free languages.  It is
contained in the class of
context-sensitive languages, however.
%% (Clearly neither is the converse true as the class of context-free languages
%% contains the class of regular languages and we have said before the class
%% of regular languages is not contained in the class of pattern languages.)

\begin{theorem}\label{tao.thm3}
Every pattern language is context-sensitive.
\end{theorem}

\noindent
This was proved by showing that every pattern language is accepted
by a linear bounded automaton \cite{Angluin}, whereupon it is
a corollary of Theorem~\ref{KSN.CH}(b).

Given a class of languages, we are often interested in the so called
{\em closure properties\/} of the class.

\begin{definition}\label{tao.def17}
\rm
A class of languages
%
% ({\it e.g.} regular languages)
%
is said to be {\em closed under\/}
a particular operation
(such as union, intersection, complementation,
concatenation, or Kleene closure)
if eevery application of the operation on
language(s) of the class yields a language of the class.
\end{definition}

Closure properties are often useful in constructing
new languages from existing languages,
and for proving many theoretical
properties of languages and grammars.
The closure properties of the four types of languages in the
Chomsky hierarchy
are summarized below.
Proofs may be found in
\cite{Harrison}, \cite{HU79}, or \cite{gurari}; the
closure of the CSLs under complementation is the famous
Immerman-Szelepcs\'{e}nyi Theorem, which is treated in
Chapter~33, Section~2.5.

\begin{theorem}\label{tao.thm4}
$~$
\begin{enumerate}
\item
The class of Type-$0$ languages is closed under union, intersection,
concatenation, and Kleene closure, but not under complementation.
\item
The class of context-free languages is closed under union, concatenation
and Kleene closure, but not under intersection or complementation.
\item
The classes of context-sensitive and regular languages are closed under
all of the five operations.
\end{enumerate}
\end{theorem}

For example, let
$L_1 = \{0^m1^n2^p | m=n\}$, $L_2 = \{0^m1^n2^p | n=p\}$,
and $L_3 = \{0^m1^n2^p | m=n {\rm ~or~} n=p\}$.
Now $L_1$ is the concatenation of the context-free languages
$\{0^n 1^n | n \ge 0\}$ and $2^*$, so $L_1$ is context-free.
Similarly $L_2$ is context-free.
Since $L_3 = L_1 \cup L_2$, $L_3$ is context-free.
However, intersecting $L_1$ with $L_2$ gives the language
$\{0^m1^n2^p | m=n=p\}$, which is not context-free.

We will look at context-free grammars more closely in the next section
and introduce the concepts of parsing and ambiguity.

\section{Context-free Grammars and Parsing}\label{sec.con}
{}From a practical point of view, for each grammar $G = (\Sigma,\Vars,S,P)$
representing some language, the following two problems are important:

\begin{enumerate}
\item
{\bf Membership problem}: Given a string over $\Sigma$,
does it belong to $L(G)$?
\item
{\bf Parsing problem}: Given a string in $L(G)$,
how can it be derived from $S$?
\end{enumerate}

The importance of the membership problem is quite obvious---given an 
English sentence or computer program, we wish to know if it is grammatically
correct or has the right format. Solving the membership problem for
context-free grammars is an integral step in the
%
% {\em lexical analysis}~\footnote{When a computer program written
% n some high-level programming language such as
% Pascal, C or Fortran is compiled, the lexical analyzer of the compiler tries
% to decompose each statement of the program into 
% individual phrases or {\em tokens}.}
%
% Ummm...tokens are "words", not "phrases", and more important,
% some modern languages are designed to make lexing /much/ simpler than
% for Fortran with its famous lexing non-locality ("DO 10 I = 1.10" etc.)
% or even for C.  For them it is more like matching simple regular
% expressions---and the standard compiler for some language I forget
% does lexing and parsing on the fly.  But I'll believe you and
% {Drobot} here, and my insert next may help.  Editor? authors?  --KSN
% KSN: I realized I could eliminate this and all other footnotes entirely.
%    
{\em lexical analysis\/} of computer programs,
namely the stage of decomposing each statement into {\em tokens\/},
prior to fully parsing the program.
For this reason, the membership problem is also often
referred to as lexical analysis (cf.\ \cite{Drobot}).
%
% Use "cf." for a non-primary source that is being cross-referenced.
%
Parsing is important because a derivation
usually brings out the ``meaning'' of the string.
For example, in the case of a Pascal program, a derivation of the program
in the Pascal grammar tells the compiler how the program should be executed.
The following theorem qualifies the decidability of the membership
problem for the four classes of grammars in the Chomsky hierarchy.
Proofs of the first assertion
can be found in~\cite{Chomsky2,Harrison,HU79},
while the second assertion is treated below.
Decidability and time complexity were defined in Chapter~30.
%
% KSN: this would become a minor forward-reference if we switched the
% chapters.  Editor, authors?   

\begin{theorem}\label{tao.thm5}
The membership problem for Type-$0$ grammars is undecidable in general,
but it is decidable given any context-sensitive grammar.
For context-free grammars the problem is decidable in
polynomial time, and for regular grammars, linear time.
\end{theorem}

Since context-free grammars play a very important role in describing 
computer programming languages, we discuss the membership and parsing problems
for context-free grammars in more detail in this and the next section.
First, let us look at another
example of a context-free grammar. For convenience, let us abbreviate
a set of productions
\[
A \rightarrow \alpha_1, \ldots,  A \rightarrow \alpha_n
\]
with the same left-hand side nonterminal as
\[
A \rightarrow \alpha_1 | \ldots | \alpha_n.
\]

% KSN: Calling the next grammar G_6 made sense,
%
\begin{example} \label{tao.ex12}
\rm
We construct a context-free grammar $G_6$ for the set of all valid 
real-number literals in Pascal.
In general, a real constant in Pascal has one of the following forms:
\[
m.n,~~~~~ m{\bf e}q,~~~~~m.n{\bf e}q,
\]
where $m,q$ are signed or unsigned integers and $n$ is an unsigned integer.
Let $\Sigma$
comprise the digits 0--9, the decimal point `.', the $+$ and $-$
signs, and the {\bf e} for scientific notation.
Let the set $\Vars$ of variables be
$\{S,M,N,D\}$ and let the set $P$ of the productions be:
%
% KSN: ^^^^^ Note that this looks strange if "\Vars" = N.
%
\begin{eqnarray*}
S & \rightarrow & M.N | M{\bf e}M | M.N{\bf e}M \\ 
M & \rightarrow & N | +N | -N \\
N & \rightarrow & DN | D \\
D & \rightarrow & 0 | 1 | 2 | 3 | 4 | 5 | 7 | 8 | 9
\end{eqnarray*}
Then the grammar generates all valid Pascal real values
(allowing redundant leading 0s).
% check!
For instance, the value
$12.3${\bf e}-4 can be derived via
\[
S \Rightarrow \underline{M}.N{\bf e}M \Rightarrow
\underline{N}.N{\bf e}M \Rightarrow \underline{D}N.N{\bf e}M \Rightarrow
1\underline{N}.N{\bf e}M \Rightarrow 1\underline{D}.N{\bf e}M \Rightarrow
\]
\[
12.\underline{N}{\bf e}M \Rightarrow 12.\underline{D}{\bf e}M \Rightarrow
12.3{\bf e}\underline{M} \Rightarrow 12.3{\bf e}-\underline{N} \Rightarrow
12.3{\bf e}\mbox{-}\underline{D} \Rightarrow 12.3{\bf e}\mbox{-}4
\]
\end{example} 

Perhaps the most natural representation of derivations in
a context-free grammar is a 
{\bf derivation tree} or a {\bf parse tree}.  Every leaf of
such a tree corresponds to a terminal (or to $\emptystring$), and
every internal node corresponds to a nonterminal.
If $A$ is an internal node with children $B_1, \ldots, B_n$,
ordered from left to right, then $A \rightarrow B_1 \cdots B_n$ must be a
production. The concatenation of all leaves from left to right yields
the string being derived. For example, the derivation tree corresponding
to the above derivation of $12.3${\bf e}-4 is given in Figure~\ref{fig.tree1}.
Such a tree also makes possible the extraction of the parts $12$, $3$ and -$4$,
which are useful in the storage of the real value in a computer memory.

\begin{figure}
\centerline{\psfig{figure=taofig1.ps,height=2.5truein,width=5truein,silen=}}
\par
\smallskip
\caption{The derivation tree for $12.3{\bf e}-4$.}
\label{fig.tree1}
\end{figure}

\begin{definition}\label{tao.def18}
\rm
A context-free grammar $G$ is {\bf ambiguous}
if there is a string $x \in L(G)$
that has two distinct derivation trees.
Otherwise $G$ is {\bf unambiguous}.
\end{definition}

Unambiguity is a very desirable property because it promises a unique
interpretation of each sentence in the language. It is not hard to see
that the grammar $G_6$ for Pascal real values and the grammar $G_1$ defined
in Example~\ref{tao.ex7} are both unambiguous. The following
example shows an ambiguous grammar.

\begin{example}\label{tao.ex13}
\rm
Consider a grammar $G_7$ for all valid arithmetic expressions that
are composed of unsigned positive integers and symbols $+,*,(,)$.
For convenience, let us use the symbol ${\bf n}$ to denote any unsigned
positive integer---it is treated as a terminal. This grammar has the productions
\begin{eqnarray*}
S & \rightarrow & T+S | S+T | T \\ 
T & \rightarrow & F*T | T*F | F \\ 
F & \rightarrow & {\bf n} | (S) 
\end{eqnarray*}
Two possible different derivation trees for the expression $1+2*3+4$
are shown in Figure~\ref{fig.tree2}. Thus $G_7$ is ambiguous.
The left tree means that the first addition should be done before
the second addition, while the right tree says the opposite.
\begin{figure}
\centerline{\psfig{figure=taofig2.ps,height=2.5truein,width=6truein,silen=}}
\par
\smallskip
\caption{Different derivation trees for the expression $1+2*3+4$.}
\label{fig.tree2}
\end{figure}
\end{example}

Although in the above example different derivations/interpretations
of any expression always result in the same value because the operations
addition and multiplication are associative, there are situations where 
the difference in the derivation can affect the final outcome.
Actually, the grammar $G_7$ can be made unambiguous by removing the
redundant productions 
$S \rightarrow T+S$ and $T \rightarrow F*T$. This corresponds to the
convention that a sequence of consecutive
additions or multiplications is always evaluated from left to right.
Deleting the two productions does not change the language of
strings generated by $G_7$, but it does fix unique interpretations of
those strings.

It is worth noting that there are context-free languages that
cannot be generated by any unambiguous context-free grammar.
Such languages are said to be {\em inherently ambiguous}. An example
taken from \cite{HU79} (where this fact is proved) is
\[
% \{ 0^ml^m2^n3^n | m,n > 0 \} \cup \{ 0^ml^n2^m3^n | m,n > 0 \}.
% KSN: Oops, the middle two terms of the second clause were switched.
% Much more insidious---the "1" was an "l".
%
%%  Thanks for the correction.
\{ 0^m1^m2^n3^n | m,n > 0 \} \cup \{ 0^m1^n2^n3^m | m,n > 0 \}.
\]
The reason is that every context-free grammar $G$ must yield two
parse trees for some strings of the form $x = 0^n 1^n 2^n 3^n$,
where one tree intuitively expresses that $x$ is a member of
the first set of the union, and the other tree expresses that
$x$ is in the second set.

We end this section by presenting an efficient algorithm for
the membership problem for context-free grammars,
following the treatment in \cite{HU79}. The algorithm is due to
Cocke, Younger, and Kasami, and is often called the CYK algorithm.
Let $G = (\Sigma,\Vars,S,P)$ be a context-free grammar
in Chomsky normal form.
%
% KSN: Since I defined Chomsky NF above, I deleted some text here.
% NB: the [HU79] algorithm is not necessarily efficient---the
% step of eliminating lambda-productions can blow up exponentially.

\begin{example}\label{tao.ex14}
\rm
If we use the algorithm in \cite{HU79} to convert the grammar
$G_7$ from Example~\ref{tao.ex13} into Chomsky normal form,
we are led to introduce new ``alias variables''
$A,B,C,D$ for the operators and parentheses, and ``helper
variables'' $S_1,T_1,T_2,F_1,F_2$ to break up the 
productions in $G_7$ with right-hand-sides of length $> 2$ into
length-$2$ pieces.  The resulting grammar is: 
\begin{eqnarray*}
S & \rightarrow & T_1 S | S T_2 | F_1 T | T F_2 | C S_1 | \mbox{\bf n} \\
T_1 & \rightarrow & T A \\
T_2 & \rightarrow & A T \\
T & \rightarrow & F_1 T | T F_2 | C S_1 | \mbox{\bf n} \\
F_1 & \rightarrow & F B \\
F_2 & \rightarrow & B F \\
F & \rightarrow & \mbox{\bf n} | C S_1 \\
S_1 & \rightarrow & S D \\
A & \rightarrow & + \\
B & \rightarrow & * \\
C & \rightarrow & ( \\
D & \rightarrow & ) 
\end{eqnarray*}
\end{example}

\noindent
While this grammar is much less intuitive to read than $G_7$,
having it in Chomsky normal form facilitates the description and
operation of the CYK algorithm.

Now suppose that $x = a_1 \cdots a_n$ is a string of $n$ terminals
that we want to test for membership in $L(G)$.
The basic idea of the CYK algorithm
is a form of {\em dynamic programming\/}. For each pair $i,j$, where
$1 \leq i \leq j \leq n$, define a set $X_{i,j} \subseteq \Vars$ by
\[
X_{i,j} = \{A | A \Rightarrow^* a_i \cdots a_j \}.
\]
Then $x \in L(G)$ if and only if $S \in X_{1,n}$. The sets $X_{i,j}$ can be
computed inductively in ascending order of $j-i$. It is easy to
figure out $X_{i,i}$ for each $i$ since
$X_{i,i} = \{A | A \rightarrow a_i \in P\}$. Suppose that we have
computed all $X_{i,j}$ where $j-i < d$ for some $d > 0$. To compute
a set $X_{i,j}$, where $j-i = d$, we just have to find all the nonterminals
$A$ such that there exist some nonterminals $B$ and $C$ satisfying
$A \rightarrow BC \in P$ and for some $k$, $i \leq k < j$,
$B \in X_{i,k}$ and $C \in X_{k+1,j}$.
A rigorous description of the algorithm in a Pascal-style pseudocode
is given below.

% KSN: The scoping of the for-loops in the original text was ambiguous,
% so I added semicolons and fixed one indentation.
% Semicolons were already used by the authors in the LL code sketch.
% Editor: note that lines 2 and 5 should /not/ be moved up to the
% preceding lines with the "for".
%
\bigskip
{\noindent \bf Algorithm} CYK($x = a_1 \cdots a_n$)
%% \medskip
\begin{enumerate}
\item
{\bf for} $i \leftarrow  1$ {\bf to} $n$  {\bf do}
\item
~~~~~$X_{i,i} \leftarrow \{A | A \rightarrow a_i \in P\}\;$;
\item
{\bf for} $d \leftarrow  1$ {\bf to} $n-1$  {\bf do}
\item
~~~~~{\bf for} $i \leftarrow 1$ {\bf to} $n-d$  {\bf do}
\item
~~~~~~~~~~$X_{i,i+d} \leftarrow \emptyset\;$;
\item
~~~~~{\bf for} $t \leftarrow 0$ {\bf to} $d-1$  {\bf do}
\item
~~~~~~~~~~$X_{i,i+d} \leftarrow X_{i,i+d} \cup
\{A | A \rightarrow BC \in P ~{\rm for~some}~ B \in X_{i,i+t} ~{\rm and}~
C \in X_{i+t+1,i+d} \}\;$;
\end{enumerate}

Table~\ref{taotab} shows the sets $X_{i,j}$ for the grammar $G_1$ and the
string $x = 000111$. In this run it
happens that every $X_{i,j}$ is either empty
or a singleton. The computation proceeds from the main diagonal toward
the upper-right corner.
%
% KSN: It's a little bit of a "swiz" to give an example of G_7 in
% Chomsky NF and then not give a run on G_7.  My editing may have
% worsened this impression, but it was there in the original text too.
% I don't have the time or inclination to fix or worry about this.
%%
%% Answer: Well, space was the concern.
\begin{table}
\caption {An example execution of the CYK algorithm.}
\label{taotab}
\begin{center}
\begin{tabular}{|c|c||c|c|c|c|c|c|}\hline
\multicolumn{2}{|c||}{}   & $0$ & $0$ & $0$ & $1$ & $1$ & $1$ \\ \cline{3-8}
\multicolumn{2}{|c||}{}   & \multicolumn{6}{c|}{$j \rightarrow$} \\ \cline{3-8}
\multicolumn{2}{|c||}{}   & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ \\ \hline\hline
             & $1$ & $O$ &     &     &     &     & $S$ \\ \cline{2-8}
             & $2$ &     & $O$ &     &     & $S$ & $T$ \\ \cline{2-8}
$i$          & $3$ &     &     & $O$ & $S$ & $T$ &     \\ \cline{2-8}
$\downarrow$ & $4$ &     &     &     & $I$ &     &     \\ \cline{2-8}
             & $5$ &     &     &     &     & $I$ &     \\ \cline{2-8}
             & $6$ &     &     &     &     &     & $I$ \\ \hline
\end{tabular}
\end{center}
\end{table}

We now analyze the asymptotic time complexity of the CYK algorithm .
Step 2 is executed $n$ times. Step 5 is executed 
$\sum_{d=1}^{n-1} n-d = (n-1)(n-1 + n-(n-1))/2 = n(n-1)/2 = O(n^2)$ times.
Step 7 is repeated for $\sum_{d=1}^{n-1} d(n-d) = O(n^3)$ times.
Therefore, the algorithm requires asymptotically $O(n^3)$ time to 
decide the membership of a string length $n$ in $L(G)$,
for any grammar $G$ in Chomsky normal form.


\section{More Efficient Parsing for Context-free Grammars}
\label{sec.parse}
The CYK algorithm presented in the last section can be easily extended
to solve the parsing problem for context-free grammars: In step~7, we also
record a production $A \rightarrow BC$ and the corresponding value of $t$
for any nonterminal $A$ that gets added to $X_{i,i+d}$. Thus a 
derivation tree for $x$ can be constructed by starting from the nonterminal
$S$ in $X_{1,n}$ and repeatedly applying the productions recorded for
appropriate nonterminals in appropriate sets $X_{i,j}$. However, the
cubic running time of this algorithm is generally too high
for parsing applications.
In practice, with compilation modules thousands of lines long,
people seek grammars in other forms besides Chomsky's that
permit parsing in linear or nearly-linear time.

Before we present some of these forms, we discuss parsing strategies
in general.
Parsing algorithms fall into two basic types, called
{\bf top-down parsers} and {\bf bottom-up parsers}.
As indicated by their names, a top-down parser builds derivation trees from
the top (root) to the bottom (leaves), while a bottom-up parser starts from
the leaves and works up to the root. Although neither method is good for
handling all context-free grammars, each provides efficient 
parsing for many important subclasses of the context-free grammars,
including those used in most programming languages.

We will only consider unambiguous grammars.
To simplify the description of the parsers, we will assume that each
string to be parsed ends with a special delimiter $\$$ that does not appear
anywhere else in the string. This assumption makes the detection of
the end of the string easy in a left-to-right scan. 
The assumption does not put any serious restriction on the range
of languages that can be parsed---the $\$$ is just like the
end-of-file marker in a real input file. The following definition will be useful.

\begin{definition}\label{tao.def19}
\rm
A derivation from a sentential form to another is said to be
{\bf leftmost} (or {\bf rightmost}) if at each step the leftmost
(or rightmost, respectively) nonterminal is replaced.
\end{definition}

For example, Example~\ref{tao.ex14}
gave a leftmost derivation of the word $12.3${\bf e}-4
in the grammar $G_6$.
%
% See---calling that one G_6 was useful again! --KSN
%
For a given word $x$, leftmost derivations are in 1-1
correspondence with derivation trees, since we can
find the leftmost derivation specified by a derivation tree by
tracing the tree down from the root going from left to right.
Rightmost derivations are likewise in 1-1 correspondence with
derivation trees.  Hence in an unambiguous context-free grammar,
every derivable string has a unique leftmost derivation and a
unique rightmost derivation.
The parsing methods considered next find one or the other.  



\subsection{Top-down Parsing}\label{sub.topdown}
An important member of the top-down parsers is the
{\bf LL parser} (see \cite{Aho,Drobot}). Here, the first
``L'' means scanning the input from left to right, and the second means
leftmost derivation. In other words, for any input string $x$, the parser
intends to find the sequence of productions used in the leftmost derivation
of $x$. 

Let $G = (\Sigma,\Vars,S,P)$ be a context-free grammar.
A {\em parsing table\/} $T$ for $G$ has rows indexed by members of
$\Vars$ and columns indexed by members of $\Sigma$ and $\$$.
Each entry $T[A,c]$ is either blank or contains one or more
productions of the form $A \rightarrow \alpha$.
Here we will suppose that $G$ allows the construction of
a parsing table $T$ such that every non-blank
entry $T[A,c]$ contains only {\em one\/} production.
Then the LL
parser for $G$ is a device
very similar to 
a pushdown automaton
as described in Chapter~30.
The parser has an input buffer, a pushdown stack,
a parsing table, and an output stream. The input buffer contains the
string to be parsed followed by the delimiter $\$$.
The stack contains
a sequence of terminals
or nonterminals, 
with another delimiter $\#$ that marks the bottom of the stack.
Initially, the
input pointer points to the first symbol of the input string,
and the stack
contains the start nonterminal $S$ on top of $\#$.
Figure~\ref{fig.llparser}
illustrates schematically the components of the parser. As usual, the input
pointer will only move to the right, while the stack pointer is allowed to
move up and down.
%
% KSN: I maintained the consistent notational conventions:
% c = terminal, A,B = nonterminals, X,Y = either.
% I preferred "T" for "table" to "M" (for machine?).

% \begin{figure}
% \centerline{\psfig{figure=Chapter31/llparse.eps,height=2.5truein,width=3.5truein,silen=}}
% \par
% \smallskip
% \caption{A schematic illustration of the LL parser.}
% \label{fig.llparser}
% \end{figure}

The parser is controlled by an algorithm that behaves as follows.
At any instant of time, the algorithm considers the symbol $X$ on
top of the stack and the current input symbol $c$ pointed by the
input pointer, and makes one of the following moves.

\begin{enumerate}
\item
If $X$ is a nonterminal, the algorithm consults the entry $T[X,a]$
of the parsing table $T$.  If the entry is blank,
the parser halts and states that 
the input string $x$ is not in the language $L(G)$.
If not, the entry is a production of the form
$X \rightarrow Y_1 \cdots Y_k$.  Then the algorithm replaces
the top stack symbol $X$ with the string $Y_1 \cdots Y_k$
(with $Y_1$ on top), and outputs the production.

\item
If $X$ is a terminal, $X$ is compared with $c$. If $X = c$, the
algorithm pops $X$ off the stack and shifts the input pointer to the next
input symbol. Otherwise, the algorithm halts and
states that $x \notin L(G)$.

\item If $X = \#$, then
provided $c = \$$, the algorithm halts and declares
the successful completion of parsing. Otherwise the
algorithm halts and states that $x \notin L(G)$.
\end{enumerate}

Intuitively, the parser reconstructs the derivation of a string
$x = a_1 \cdots a_n$ as follows. Suppose that the leftmost derivation
of $x$ is
\[
S = \gamma_0 \Rightarrow \gamma_1 \Rightarrow \cdots \Rightarrow \gamma_i
   \Rightarrow \gamma_{i+1} \Rightarrow \cdots \Rightarrow \gamma_m = x,
\]
where each $\gamma_j$ is a sentential form. Suppose, moreover, that the
derivation step $\gamma_i \Rightarrow \gamma_{i+1}$ is the result of applying
a production $X \rightarrow Y_1 \cdots Y_k$. This means that
$\gamma_i = \alpha X \beta$ for some string $\alpha$ of terminals
and sentential form $\beta$. Since no subsequent derivation will
change $\alpha$, this string must match a leading substring
$a_1 \cdots a_j$ of $x$ for some $j$. In other words, 
$\gamma_i = a_1 \cdots a_j X \beta$ and 
$\gamma_{i+1} = a_1 \cdots a_j Y_1 \cdots Y_k \beta$. Suppose that
the parser has successfully reconstructed the derivation steps
up to $\gamma_i$. To complete the derivation, the parser must transform
the tail end of $\gamma_i$ into $a_{j+1} \cdots a_n$. Thus, it
keeps the string $X \beta$ on the stack and repeatedly replaces
the top stack symbol (i.e., replaces the leftmost nonterminal) until
$a_{j+1}$ appears on top. At this point, $a_{j+1}$ is removed from
the stack, and the remainder of the stack must be transformed to match
%
% $a_{i+2} \cdots a_n$.
% Authors: i was a typo, right?  --KSN
%
%% Answer: right
$a_{j+2} \cdots a_n$.
The procedure is repeated until all the
input symbols are matched. 

The following example illustrates the parsing table for
a simple context-free grammar, and how the parser operates.

\begin{example}\label{tao.ex15}
\rm
%
% Consider the valid arithmetic expressions described by grammar $G_7$.
% For some reason (besides $G_7$ being ambiguous) to be explained later,
% let us write the productions differently.
% KSN: For some reason, the writing seems unfocused here.
%
Consider again the 
language of valid arithmetic expressions from Example~\ref{tao.ex13},
where an ambiguous grammar $G_7$ was given that could be made unambiguous
by removing two productions.
Let us remove the ambiguity in a different way. 
The new grammar is called $G_8$ and has the following productions
\begin{eqnarray*} 
S  & \rightarrow & TS' \\
S' & \rightarrow & +S | \emptystring \\
T & \rightarrow & FT' \\
T' & \rightarrow & *T | \emptystring \\
F & \rightarrow & {\bf n} | (S)
\end{eqnarray*}
It is easy to see that grammar $G_8$ is unambiguous.  A parsing table for
this grammar is shown in Table~\ref{parsetab1}. We will discuss how such
a table can be constructed shortly.

\begin{table}
\caption {An LL parsing table for grammar $G_8$.}
\label{parsetab1}
\begin{center}
\begin{tabular}{|c||l|l|l|l|l|l|}\hline
%% \multicolumn{2}{|c||}{}   & $0$ & $0$ & $0$ & $1$ & $1$ & $1$ \\ \cline{3-8}
NONTER-     & \multicolumn{6}{|c}{INPUT SYMBOL} \\ \cline{2-7}
MINAL       & ${\bf n}$ & $+$ & $*$ & ( & ) & $\$$ \\ \hline\hline
 $S$ & $S \rightarrow TS'$ &  &  & $S \rightarrow TS'$ &  &  \\ \hline
 $S'$ &  & $S' \rightarrow +S$ &  &  & 
           $S' \rightarrow \emptystring$  & $S' \rightarrow \emptystring$ \\ \hline
 $T$ & $T \rightarrow FT'$ &  &  & $T \rightarrow FT'$ &  &  \\ \hline
 $T'$ &  & $T' \rightarrow \emptystring$ & $T' \rightarrow *T$ &  & 
             $T' \rightarrow \emptystring$  & $T' \rightarrow \emptystring$ \\ \hline
 $F$ & $F \rightarrow {\bf n}$ &  &  & $F \rightarrow (S)$ &  &  \\ \hline
\end{tabular}
\end{center}
\end{table}

To demonstrate how the parser operates, consider the input
string $({\bf n} + {\bf n}) * {\bf n}$. Table~\ref{parsetab2} shows
the content of the stack, the remaining input symbols, and the output
after each step. If we trace the actions of the parser carefully, we see
that the sequence of
productions it outputs constitutes the leftmost derivation of
$({\bf n} + {\bf n}) * {\bf n}$.

\begin{table}
\caption {The steps in the LL parsing of $({\bf n} + {\bf n}) * {\bf n}$.}
\label{parsetab2}
\begin{center}
\begin{tabular}{|r|r|l|}\hline
\multicolumn{1}{|c|}{STACK} & \multicolumn{1}{|c|}{INPUT} & 
           \multicolumn{1}{|c|}{OUTPUT} \\ \hline\hline
$S\#$ &  $({\bf n} + {\bf n}) * {\bf n}\$$ &  \\
$TS'\#$ &  $({\bf n} + {\bf n}) * {\bf n}\$$ &  $S \rightarrow TS'$  \\
$FT'S'\#$ &  $({\bf n} + {\bf n}) * {\bf n}\$$ &  $T \rightarrow FT'$  \\
$(S)T'S'\#$ &  $({\bf n} + {\bf n}) * {\bf n}\$$ &  $F \rightarrow (S)$  \\
$S)T'S'\#$ &  ${\bf n} + {\bf n}) * {\bf n}\$$ &   \\
$TS')T'S'\#$ &  ${\bf n} + {\bf n}) * {\bf n}\$$ &  $S \rightarrow TS'$  \\
$FT'S')T'S'\#$ &  ${\bf n} + {\bf n}) * {\bf n}\$$ &  $T \rightarrow FT'$  \\
${\bf n}T'S')T'S'\#$ &  ${\bf n} + {\bf n}) * {\bf n}\$$ &  
                      $F \rightarrow {\bf n}$  \\
$T'S')T'S'\#$ &  $+ {\bf n}) * {\bf n}\$$ &  \\
$S')T'S'\#$ &  $+ {\bf n}) * {\bf n}\$$ &  $T' \rightarrow \emptystring$ \\
$+S)T'S'\#$ &  $+ {\bf n}) * {\bf n}\$$ &  $S' \rightarrow +S$ \\
$S)T'S'\#$ &  ${\bf n}) * {\bf n}\$$ &  \\
$TS')T'S'\#$ &  ${\bf n}) * {\bf n}\$$ &  $S \rightarrow TS'$ \\
$FT'S')T'S'\#$ &  ${\bf n}) * {\bf n}\$$ &  $T \rightarrow FT'$ \\
${\bf n}T'S')T'S'\#$ &  ${\bf n}) * {\bf n}\$$ &  $F \rightarrow {\bf n}$ \\
$T'S')T'S'\#$ &  $) * {\bf n}\$$ &  \\
$S')T'S'\#$ &  $) * {\bf n}\$$ &  $T' \rightarrow \emptystring$ \\
$)T'S'\#$ &  $) * {\bf n}\$$ &  $T' \rightarrow \emptystring$ \\
$T'S'\#$ &  $* {\bf n}\$$ & \\
$*TS'\#$ &  $* {\bf n}\$$ &  $T' \rightarrow *T$ \\
$TS'\#$ &  ${\bf n}\$$ &  \\
$FT'S'\#$ &  ${\bf n}\$$ &  $T \rightarrow FT'$ \\
${\bf n}T'S'\#$ &  ${\bf n}\$$ &  $F \rightarrow {\bf n}$ \\
$T'S'\#$ &  $\$$ &  $T' \rightarrow \emptystring$ \\
$S'\#$ &  $\$$ &  $S' \rightarrow \emptystring$ \\
$\#$ &  $\$$ &  \\ \hline
\end{tabular}
\end{center}
\end{table}

\end{example}

Now we turn to the question of how to construct an LL parser for a given
grammar $G = (\Sigma,\Vars,S,P)$.
It suffices to show how to compute the entries
$T[A,c]$, where $A \in \Vars$ and $c \in \Sigma \cup \{\$\}$. 
We first need to introduce two functions $\first{\alpha}$ and $\follow{A}$.
The former maps a sentential form to a terminal or $\emptystring$, and the latter
maps a nonterminal to a terminal or $\$$.

\begin{definition}\label{tao.def20}
\rm
For each sentential form $\alpha \in \{\Sigma \cup \Vars\}^*$,
and for each nonterminal $A \in \Vars$,
%
% KSN: The original text mixed "X" and "A" and was poorly formatted.
%
\begin{eqnarray*}
\first{\alpha} &=& \{c \in \Sigma ~|~
\mbox{for some~} \beta \in \{\Sigma \cup \Vars\}^*,~
\alpha \Rightarrow^* c\beta\} ~\cup~ 
\{ \emptystring ~|~ \alpha \Rightarrow^* \emptystring \}\\
\follow{A} &=& \{c \in \Sigma ~|~
\mbox{for some~} \alpha,\beta \in \{\Sigma \cup \Vars\}^*,~ 
S \Rightarrow^* \alpha Ac \beta \} \\
&\cup& \{ \$ ~|~ \mbox{for some~} \alpha \in \{\Sigma \cup \Vars\}^*,~
           S \Rightarrow^* \alpha A \}.
\end{eqnarray*}
\end{definition}

Intuitively, for any sentential form $\alpha$, $\first{\alpha}$
consists of all the terminals that appear as the first symbol of
some sentential form derivable from $\alpha$. The empty string
$\emptystring$ is included in $\first{\alpha}$ as a special case 
if $\alpha$ derives $\emptystring$. On the other hand, for any nonterminal $A$,
$\follow{A}$ consists of all the terminals that immediately follow an
occurrence of $A$ in some sentential form derivable from the start symbol $S$.
The end delimiter $\$$ is included in $\follow{A}$ as a special case
if $A$ appears at the end of some sentential form derivable from $S$.

Algorithms for computing the $\first$ and $\follow$ functions are fairly
straightforward and can be found in~\cite{Aho,Drobot}. It turns out that
to construct the parsing table for a grammar $G$, we only need to know
the values of $\first{\alpha}$ for those sentential forms $\alpha$
appearing on the right-hand sides of the productions in $G$.

\begin{example}\label{tao.ex16}
\rm
The following illustrate the functions $\first{\alpha}$ and $\follow{A}$ for
the grammar $G_8$ described in the above example. For the former,
only those sentential forms appearing on the right-hand sides of the
productions in $G_8$ are considered.

\begin{eqnarray*}
\first{TS'} & = & \{(, {\bf n}\} \\
\first{+S} & = & \{+\} \\
\first{FT'} & = & \{(, {\bf n}\} \\
\first{*T} &= & \{*\} \\
\first{(S)} &=& \{(\} \\
\first{{\bf n}} &=& \{{\bf n}\} \\
\first{\emptystring} &=& \{\emptystring\} \\
\follow{S} & = & \{),\$\} \\
\follow{S'} &=& \{),\$\} \\
\follow{T} &=& \{+,),\$\} \\
\follow{T'} &=& \{+,),\$\} \\
\follow{F'} &=& \{*,+,),\$\} \\
\end{eqnarray*}

\end{example}

Given the functions $\first{\alpha}$ and $\follow{A}$ for a grammar $G$,
we can easily construct the LL parsing table $T[A,c]$ for $G$. The basic
idea is as follows. Suppose that $A \rightarrow \alpha$ is a production
and $c \in \first{\alpha}$. Then, the parser will replace $A$ with $\alpha$
when $A$ is on top of the stack and $c$ is the current input symbol.
The only complication occurs when $\alpha$ may derive $\emptystring$. In this
case, the parser should still replace $A$ with $\alpha$ if the current
input symbol is a member of $\follow{A}$. The detailed algorithm
is given below.

\bigskip
{\noindent \bf Algorithm} LL-Parsing-Table($G = (\Sigma,\Vars,S,P)$)
%% \medskip
\begin{enumerate}
\item Initialize each entry of the table to blank.
\item {\bf for} each production $A \rightarrow \alpha$ in $P$  {\bf do}
\item $~~~~~$ {\bf for} each terminal $a \in \first{\alpha}$ {\bf do}
\item $~~~~~~~~~~$add $A \rightarrow \alpha$ to $T[A,a]\;$;
\item $~~~~~$ {\bf if} $\emptystring \in \first{\alpha}$ {\bf then}
\item $~~~~~~~~~~${\bf for} each terminal or delimiter $a \in \follow{A}$
                  {\bf do}
\item $~~~~~~~~~~~~~~~$add $A \rightarrow \alpha$ to $T[A,a]\;$;
\end{enumerate}

The above algorithm can be applied to any context-free grammar to
produce a parsing table. However, for some grammars the table may
have entries containing multiple productions. 
Multiply-defined entries in a parsing table,
however, would present our parsing algorithm with an
unwelcome choice.
It would be possible for it to make a wrong choice and incorrectly
report a string as not being derivable, and backtracking to the
last choice to try another would blow up the running time
unacceptably.

\begin{example}\label{tao.ex17}
\rm
Recall that we could make the grammar $G_7$ of
Example~\ref{tao.ex13} unambiguous by deleting two
unnecessary productions.  The resulting grammar, which we call $G_9$, 
has the following productions:
%
% KSN: below it really helps to number this grammar.
%
\begin{eqnarray*}
S & \rightarrow & S+T | T \\ 
T & \rightarrow & T*F | F \\ 
F & \rightarrow & {\bf n} | (S) 
\end{eqnarray*}
It is easy to see that both $\first{S+T}$ and $\first{T}$ contain 
the terminal ${\bf n}$. Hence, the entry $T[S,{\bf n}]$ of the parsing
table is multiply defined, so this table is not
well-conditioned for LL parsing.
\end{example}

A context-free grammar whose parsing table has no multiply-defined
entries is called an {\bf LL(1) grammar}. Here, the ``$1$'' signifies
the fact that the LL parser uses one input symbol of lookahead to
decide its next move. For example, $G_8$ is an LL($1$) grammar,
while $G_9$ is not.
It is easy to show that our LL parser runs in linear time for any LL($1$)
grammar.  

What can we do for grammars that are not LL($1$), such as $G_9$?
The first idea is to extend the LL parser to use more input symbols
of lookahead. In other words, we will allow the parser to see the
next several input symbols before it makes a decision.
For one more symbol of lookahead,
this requires expanding the parsing table to have a column for
every {\em pair\/} of symbols in $\Sigma$ (plus $\$$ as a
possible second symbol), but so doing may separate and/or 
eliminate multiply-defined entries in the original parsing table. The
$\first$ and $\follow$ functions have to be modified to take 
two (or more) lookahead symbols into consideration. For
any constant $k > 1$, a grammar is said to be an {\bf LL(k) grammar} if
its parsing table using $k$ lookahead symbols has no multiply defined
entries. For example, the grammar $G_1$ given in Example~\ref{tao.ex7}
is not LL($1$), but it is LL($2$).

Although LL($k$) grammars form a larger class than LL($1$) grammars, there
are still grammars that are not LL($k$) for any constant $k$.
The grammar $G_7$ and $G_9$ are examples.
%
% It would be nice to supply intuition as to why G_9 is not LL(k).  --KSN
%
The texts \cite{Aho,Drobot} provide several techniques for dealing
with non-LL($k$) grammars, such as grammar transformations and backtracking.
When backtracking is used, the parsing process is often called
{\em recursive-descent parsing\/}, and can be very time consuming due to
the use of many recursive calls.

\subsection{Bottom-up Parsing}\label{sub.bottomup}
The most popular bottom-up parsing technique is {\bf LR parsing}.
Here, the ``L'' again means scanning the input from left to right,
while the ``R'' means constructing the rightmost derivation.
For any input string $x$, the LR parser scans $x$ from left to right
and tries to find the {\em reverse\/} of the
sequence of productions used in the
rightmost derivation of $x$. It turns out that in bottom-up parsing
rightmost derivations are easier to deal with than leftmost derivations.
LR parsing is especially attractive in practice for many reasons
summarized in \cite{Aho}: (i) it can handle virtually all programming language
constructs; (ii) it has very efficient implementations; (iii) it is more
powerful than LL parsing; and (iv) it detects syntactic errors quickly.
The principal drawback of the method is that constructing an LR parser
is very involved. Fortunately, there exist efficient algorithms that
can automatically generate LR parsers from certain context-free grammars.
Because of space limitations, we describe only
the operation of an LR parser here,
and refer the reader to~\cite{Aho} for
the construction of such a parser.

Similar to an LL parser, an LR parser has an input buffer,
a pushdown stack, a parsing table, and an output stream, and is
controlled by an algorithm that is the same for all LR parsers.
The input string is again assumed to have an end delimiter $\$$.
At any time during parsing, the stack stores a string of the
form $q_m X_m q_{m-1} \cdots X_1 q_0$ (with $q_0$ at bottom), where 
each $X_i$ is a grammar symbol (i.e., a terminal or nonterminal of 
the grammar involved) and $q_i$ is a {\em state} symbol.
The number of distinct states is finite, and each state symbol
intends to summarize the information contained in the stack below it.
The combination of the state on top of the stack and the current input symbol
are used to index the parsing table and determine the move of the parser.
It will be seen that the state symbols subsume all
information in the grammar symbols, and a real parser omits the latter.
However, we retain the grammar symbols $X_1, \ldots, X_m$
to make our illustration easier to follow, and for consistency with
previous examples.

The parsing table consists of two parts: a parsing action function
$\action{q,c}$, which maps a state and an input symbol to a move, and
a function $\goto{q,X}$, which maps a state and a grammar symbol to 
a state. For each state $q$ and each input symbol $c$, the value
of the function $\action{q,c}$ can be one of the following:
\begin{enumerate}
\item {\em shift\/},
\item {\em reduce by $A \rightarrow \alpha$\/},
where $A \rightarrow \alpha$ is a
production in the grammar,
\item {\em accept\/}, and
\item {\em blank\/}.
\end{enumerate}

The algorithm controlling the LR parser operates as follows.
Suppose that the state on top of the stack is $q$ and the current input
symbol is $c$. It consults $\action{q,c}$ and makes one of the four
types of moves as below.

\begin{enumerate}
\item If $\action{q,c} =$ {\em shift\/}, the parser pushes the string
$\goto{q,c}c$ on the stack and shifts its input pointer
to the next input symbol.

\item If $\action{q,c} =$ {\em reduce by $A \rightarrow \alpha$\/},
the parser applies the production $A \rightarrow \alpha$ as follows.
Let $k = |\alpha|$, 
and let the current stack content be $q_m X_m q_{m-1} \cdots X_1 q_0$.
The parser first pops the top $2k$ symbols
$q_m, X_m, \ldots, q_{m-k+1}, X_{m-k+1}$ off the stack.
It then consults $\goto{q_{m-k},A}$ and pushes the string
$\goto{q_{m-k},A} A$ onto the stack, resulting in a stack with content
$\goto{q_{m-k},A} A q_{m-k} X_{m-k} \cdots X_1 q_0$. The parser also
outputs the production $A \rightarrow \alpha$.

It is always guaranteed in the above that $X_{m-k+1} \cdots X_m = \alpha$.

\item
If $\action{q,a} =$ {\em accept\/}, the parser successfully terminates.

\item
If $\action{q,a} =$ {\em blank\/}, the parser terminates and declares
that the input string is not a member of the language.
\end{enumerate}

Intuitively, the LR parser reconstructs the rightmost derivation of
a string $x = a_1 \cdots a_n$ as follows. Suppose that the rightmost
derivation of $x$ is
\[
S = \gamma_0 \Rightarrow \gamma_1 \Rightarrow \cdots \Rightarrow \gamma_i
   \Rightarrow \gamma_{i+1} \Rightarrow \cdots \Rightarrow \gamma_m = x,
\]
where each $\gamma_j$ is a sentential form. Furthermore, suppose that the
derivation step
$\gamma_i \Rightarrow \gamma_{i+1}$ is the result of applying
a production $A \rightarrow Y_1 \cdots Y_k$. This means that
$\gamma_i = \alpha A z$ for some sentential form
$\alpha = X_1 \cdots X_t$ and string $z$ of terminals,
and $\gamma_{i+1} = \alpha Y_1 \cdots Y_k z = 
X_1 \cdots X_t Y_1 \cdots Y_k z$. Since no subsequent derivation will
change $z$, this string must match a trailing substring 
$a_j \cdots a_n$ of $x$ for some $j$. In other words, 
$\gamma_i = X_1 \cdots X_t A a_j \cdots a_n$ and 
$\gamma_{i+1} = X_1 \cdots X_t Y_1 \cdots Y_k a_j \cdots a_n$.

Suppose that the parser has successfully reconstructed the derivation steps
in reverse from $\gamma_m$ back to $\gamma_{i+1}$. At this point,
the stack must be holding a string of the form
\[  q_{t+h} Y_h \cdots q_{t+1} Y_1 q_t X_t \cdots q_1 X_1 q_0, \]
where $h \leq k$ and $q_0, q_1, \ldots q_{t+h}$ are some states, and
the input pointer is pointing at $a_{j+h-k}$. Moreover, it must be
that $Y_{h+1} = a_{j+h-k}, \ldots, Y_k = a_{j-1}$. To recover $\gamma_i$,
the parser consults the state $q_{t+h}$ on top of stack and the current
input symbol $a_{j+h-k}$.
It then shifts the $h-k$ input symbols
$a_{j+h-k}, \ldots, a_{j-1}$ and $h-k$ appropriate state
symbols onto the stack.
It also advances the input pointer to $a_j$. Then, the parser
{\em reduces} the string $Y_1 \cdots Y_k$ to the nonterminal $A$ by replacing
the top $2k$ stack symbols with $A$ and an appropriate state symbol. 

The above shift-and-reduce process is repeated until the sentential form
$\gamma_0 = S$ is obtained.  For this reason, the LR parser is sometimes
called a {\em shift-reduce parser\/}. 

Clearly, the state symbols stored on the stack play a key role in dictating
the actions of the parser. Below we first give an example of LR parsing tables
and show exactly how the parser operates on a specific input. Then we will
briefly sketch how the states are chosen for a grammar and what they
represent.

\begin{example}\label{tao.ex18}
\rm
Consider again the unambiguous
% 
% version of grammar $G_7$
%
grammar $G_9$ given in
Example~\ref{tao.ex17}. For convenience, let us number the productions
as follows.
\begin{eqnarray*}
(1)~~~ S & \rightarrow & S+T \\ 
(2)~~~ S & \rightarrow & T \\ 
(3)~~~ T & \rightarrow & T*F \\ 
(4)~~~ T & \rightarrow & F \\ 
(5)~~~ F & \rightarrow & {\bf n} \\
(6)~~~ F & \rightarrow & (S)
\end{eqnarray*}
Tables~\ref{parsetab3} and~\ref{parsetab4} illustrate the functions
$\action{q,c}$ and $\goto{q,X}$ for the grammar. In the first table,
shf means shift, p$i$ means reduce by production $i$, acc means accept,
and blank means reject. The states are numbered $0, 1, \ldots, 11$.

\begin{table}
\caption {The function $\action{q,c}$ for the unambiguous grammar $G_9$.}
\label{parsetab3}
\begin{center}
\begin{tabular}{|r||l|l|l|l|l|l|}\hline
STATE  & ${\bf n}$ & $+$ & $*$ & ( & ) & $\$$ \\ \hline\hline
$0$ & shf & & & shf & & \\ \hline
$1$ & & shf & & & & acc\\ \hline
$2$ & & p$2$ & shf & & p$2$ & p$2$ \\ \hline
$3$ & & p$4$ & p$4$ & & p$4$ & p$4$ \\ \hline
$4$ & shf & & & shf & & \\ \hline
$5$ & & p$6$ & p$6$ & & p$6$ & p$6$ \\ \hline
$6$ & shf & & & shf & & \\ \hline
$7$ & shf & & & shf & & \\ \hline
$8$ & & shf & & & shf & \\ \hline
$9$ & & p$1$ & shf & & p$1$ & p$1$ \\ \hline
$10$ & & p$3$ & p$3$ & & p$3$ & p$3$ \\ \hline
$11$ & & p$5$ & p$5$ & & p$5$ & p$5$ \\ \hline
\end{tabular}
\end{center}
\end{table}

\begin{table}
\caption {The function $\goto{q,X}$ for the unambiguous grammar $G_9$.}
\label{parsetab4}
\begin{center}
\begin{tabular}{|r||l|l|l|l|l|l|l|l|l|}\hline
STATE  & ${\bf n}$ & $+$ & $*$ & ( & ) & $\$$ & $S$ & $T$ & $F$  \\ \hline\hline
$0$ & $5$ & & & $4$ & & & $1$ & $2$ & $3$ \\ \hline 
$1$ & & $6$ & & & & & & & \\ \hline 
$2$ & & & $7$ & & & & & & \\ \hline
$3$ & & & & & & & & & \\ \hline
$4$ & $5$ & & & $4$ & & & $8$ & $2$ & $3$ \\ \hline
$5$ & & & & & & & & & \\ \hline
$6$ & $5$ & & & $4$ & & & & $9$ & $3$ \\ \hline
$7$ & $5$ & & & $4$ & & & & & $10$ \\ \hline
$8$ & & $8$ & & & $11$ & & & & \\ \hline
$9$ & & $7$ & & & & & & & \\ \hline
$10$ & & & & & & & & & \\ \hline
$11$ & & & & & & & & & \\ \hline
\end{tabular}
\end{center}
\end{table}

Now we demonstrate how the parser operates on the string 
$({\bf n} + {\bf n}) * {\bf n}$. Table~\ref{parsetab5} shows
the content of the stack, the remaining input symbols, and the output
after each step. It is easy to see that the reverse sequence of
the productions in the reduce steps constitute the rightmost derivation of
$({\bf n} + {\bf n}) * {\bf n}$.

\begin{table}
\caption {The steps in the LR parsing of $({\bf n} + {\bf n}) * {\bf n}$.}
\label{parsetab5}
\begin{center}
\begin{tabular}{|r|r|l|}\hline
\multicolumn{1}{|c|}{STACK} & \multicolumn{1}{|c|}{INPUT} & 
           \multicolumn{1}{|c|}{ACTION} \\ \hline\hline
$0$ &  $({\bf n} + {\bf n}) * {\bf n}\$$ & shift  \\
$4 ( 0$ &  ${\bf n} + {\bf n}) * {\bf n}\$$ & shift  \\
$5 {\bf n} 4 ( 0$ &  $+ {\bf n}) * {\bf n}\$$ & 
                     reduce by $F \rightarrow {\bf n}$  \\
$3 F 4 ( 0$ &  $+ {\bf n}) * {\bf n}\$$ & 
                     reduce by $T \rightarrow F$  \\
$2 T 4 ( 0$ &  $+ {\bf n}) * {\bf n}\$$ & 
                     reduce by $S \rightarrow T$  \\
$8 S 4 ( 0$ &  $+ {\bf n}) * {\bf n}\$$ & shift  \\
$6 + 8 S 4 ( 0$ &  ${\bf n}) * {\bf n}\$$ & shift  \\
$5 {\bf n} 6 + 8 S 4 ( 0$ &  $) * {\bf n}\$$ & 
                     reduce by $F \rightarrow {\bf n}$  \\
$3 F 6 + 8 S 4 ( 0$ &  $) * {\bf n}\$$ & 
                     reduce by $T \rightarrow F$  \\
$9 T 6 + 8 S 4 ( 0$ &  $) * {\bf n}\$$ & 
                     reduce by $S \rightarrow S+T$  \\
$8 S 4 ( 0$ &  $) * {\bf n}\$$ & shift  \\
$11 ) 8 S 4 ( 0$ &  $* {\bf n}\$$ & 
                     reduce by $F \rightarrow (S)$  \\
$3 F 0$ &  $* {\bf n}\$$ & 
                     reduce by $T \rightarrow F$  \\
$2 T 0$ &  $* {\bf n}\$$ & shift  \\
$7 * 2 T 0$ &  ${\bf n}\$$ & shift  \\
$5 {\bf n} 7 * 2 T 0$ &  $\$$ & 
                     reduce by $F \rightarrow {\bf n}$  \\
$10 F 7 * 2 T 0$ &  $\$$ & 
                     reduce by $T \rightarrow T*F$  \\
$2 T 0$ &  $\$$ & 
                     reduce by $S \rightarrow T$  \\
$1 S 0$ &  $\$$ & accept   \\ \hline
\end{tabular}
\end{center}
\end{table}

\end{example}

There are several techniques for constructing an LR parsing table, such
as simple-LR (SLR), canonical-LR, and lookahead-LR (LALR), as
described by \cite{Aho}.
In general, these techniques all use states that are sets
of {\em items\/} of the form $A \rightarrow \alpha \cdot \beta$, where
$A \rightarrow \alpha \beta$ is a production and
the $\cdot$ marks a place in the right-hand side.
%
% KSN: I'm glad you used Aho-Sethi-Ullman---there are some
% bad mistakes in the LR(k) section of [HU79]!
%
Such items are
commonly known as the {\em LR items\/}. Each item expresses
the assertion that the part $\alpha$ has already been obtained
by previous shift/reduce steps and pushed on the stack, and the
part $\beta$ is expected to be obtainable from the next few input symbols
by some shift/reduce steps. Since at any given time the parser may not
be able to predict what input symbols should follow, it has to 
maintain a set
of LR items to deal with all possibilities.

Again, not all context-free grammars have effective LR parsers.
For example, the grammar with productions
\begin{eqnarray*}
S & \rightarrow & 0 S 0 | 1 S 1 | 0 | 1 | \emptystring 
\end{eqnarray*}
cannot be handled by LR parsing.
This grammar generates the set of all palindromes.
The grammars that have effective LR parsers are called {\em LR grammars\/}.
In fact, there are context-free languages that cannot be represented by any
LR grammars. The set of palindromes is one such language.


%% $$ \section*{Acknowledgement}
%% \bigskip
%% {\noindent \bf Acknowledgment.}
%% We would like to thank John Tromp and the reviewers for reading the
%% initial drafts and helping us to improve the presentation.

\section{Defining Terms}\label{terms}

{\noindent \bf ambiguous context-free grammar}: 
a context-free grammar in which some derivable terminal
strings have two distinct derivation trees.

{\noindent \bf bottom-up parsing}:
a process of building a derivation tree from the leaves up to the root.

{\noindent \bf Chomsky normal form}:
a form of context-free grammar in which every rule
has the
form $A \rightarrow BC$ or $A \rightarrow a$,
where $A,B,C$ are nonterminals and $a$ is a terminal.

{\noindent \bf context-free grammar}:
a grammar whose rules have the form
$A \rightarrow \beta$, where $A$ is a nonterminal and $\beta$ is
a string of nonterminals and terminals.

\noindent
{\bf context-free language}: a language that can be described by
some context-free grammar.

\noindent
{\bf context-sensitive grammar}: a grammar whose rules have the form
$\alpha \rightarrow \beta$, where $\alpha, \beta$ are strings of
nonterminals and terminals, and $|\alpha| \leq |\beta|$.

\noindent
{\bf context-sensitive language}: a language that can be described
by some context-sensitive grammar. 

\noindent
{\bf derivation} or {\bf parsing}:
a sequence of applications of rules of a grammar that
transforms the start symbol into a given terminal string or
sentential form.

\noindent
{\bf derivation tree} or {\bf parse tree}: a rooted, ordered tree
that describes
a particular derivation of a string with respect to some context-free
grammar.

\noindent
{\bf (formal) language}: a set of strings over some fixed alphabet.

\noindent
{\bf (formal) grammar}: a description of some language,
typically consisting of a set of terminals, a set of nonterminals,
a distinguished nonterminal called the start symbol, and a set of
rules (or productions) of the form $\alpha \rightarrow \beta$,
which determine which substrings $\alpha$ of a
sentential form 
can be replaced by some another string $\beta$.

\noindent
{\bf leftmost} (or {\bf rightmost}) {\bf derivation}: a derivation in which
at each step,
the leftmost (respectively, rightmost) nonterminal is rewritten.

\noindent
{\bf LL parsing}: a type of top-down parsing in which one reads the input
from left to right in order to reconstruct a leftmost derivation.

\noindent
{\bf LL(k) grammar}: a context-free grammar whose LL($k$) parsing table
has no multiply-defined entries.

\noindent
{\bf LL(k) parsing}: an LL parsing that
uses $k$ symbols of lookahead.

\noindent
{\bf LR parsing}: a type of bottom-up parsing in which one reads the input
from left to right in order to reconstruct a rightmost derivation
in reverse order of steps.

\noindent
{\bf LR grammar}: a context-free grammar that has an effective LR parser.

\noindent
{\bf membership problem} (or {\bf lexical analysis}): the problem 
or process of deciding whether
a given string is generated by a given grammar.

\noindent
{\bf parsing problem}: the problem of reconstructing a derivation of
a given input string in a given grammar. 

\noindent
{\bf regular expression}: a description of some language using the
operators union, concatenation, and Kleene closure.

\noindent
{\bf regular language}: a language that can be described by some
regular expression, or equivalently, by some
right-linear/regular grammar.

\noindent
{\bf right-linear} or {\bf regular grammar}: a grammar whose rules
have the form
$A \rightarrow cB$, $A \rightarrow c$, or $A \rightarrow \emptystring$,
where $A,B$ are nonterminals, $c$ is a terminal,
and $\emptystring$ is the empty string.

\noindent
{\bf sentential form}: a string of terminals and nonterminals obtained
at some step of a derivation in a grammar.

\noindent
{\bf top-down parsing}: a process of building derivation trees from the top (root) 
down to
the bottom (leaves).


\begin{thebibliography}{99}
\setlength{\baselineskip}{0.6\baselineskip}
\bibitem[Aho, Sethi and Ullman, 1985]{Aho}
        Aho, A.V., Ullman, J.D. and Sethi, I. 1985.
        {\it Compilers: Principles, Techniques, and Tools}.
        Addison-Wesley, Reading, MA.
\bibitem[Angluin, 1980]{Angluin}
        Angluin, D. 1980. 
        Finding patterns common to a set of strings.
        {\it Journal of Computer and System Sciences}. 21:46-62.
\bibitem[Chomsky, 1956]{Chomsky1}
        Chomsky, N. 1956. 
        Three models for the description of language.
        {\it IRE Trans. on Information Theory}. 2(2):113-124.
\bibitem[Chomsky, 1963]{Chomsky2}
        Chomsky, N. 1963. 
        Formal properties of grammars. 
        In {\it Handbook of Mathematical Psychology} Vol. 2, 323-418.
        John Wiley and Sons, New York.
\bibitem[Chomsky and Miller, 1958]{miller} 
        Chomsky, N. and Miller, G. 1958.
        Finite-state languages.
        {\it Information and Control}. 1:91-112.
\bibitem[Drobot, 1989]{Drobot} 
        Drobot, V. 1989. 
        {\it Formal Languages and Automata Theory}.
        Computer Science Press, Rockville, MD.
\bibitem[Floyd and Beigel, 1994]{floyd}
        Floyd, R.W. and Beigel, R. 1994.
        {\it The Language of Machines: an Introduction to
        Computability and Formal Languages}. Computer Science Press,
        New York.
\bibitem[Gurari, 1989]{gurari}
        Gurari, E. 1989.
        {\it An Introduction to the Theory of Computation}.
        Computer Science Press, Rockville, MD.
\bibitem[Harel, 1992]{Harel}
        Harel, D. 1992. 
        {\it Algorithmics: The Spirit of Computing}.
        Addison-Wesley, Reading, MA.
\bibitem[Harrison, 1978]{Harrison}
        Harrison, M. 1978.
        {\it Introduction to Formal Language Theory}.
        Addison-Wesley, Reading, MA.
\bibitem[Hopcroft and Ullman, 1979]{HU79}
        Hopcroft, J. and Ullman, J. 1979.
        {\it Introduction to Automata Theory, Languages and Computation}.
        Addison-Wesley, Reading, MA.
\bibitem[Jiang et al., 1995]{Jiang}
        Jiang, T., Salomaa, A., Salomaa, K., and Yu, S. 1995.
        Decision problems for patterns. 
        {\it Journal of Computer and System Sciences}. 50(1):53-63.
\bibitem[Kleene, 1956]{Kleene}
        Kleene, S. 1956.
        Representation of events in nerve nets and finite automata.
        In {\it Automata Studies}, 3-41. Princeton University Press, NJ.
\bibitem[Lind and Marcus, 1995]{Lind and Marcus}
	Lind, D. and Marcus, 1995 
	{\it Symbolic Dynamics}, Academic Press.

\bibitem[Post, 1943]{Post} 
        Post, E. 1943. 
        Formal reductions of the general combinatorial decision problems.
        {\it Amer. J. Math.} 65:197-215.
\bibitem[Salomaa, 1966]{Salomaa}
        Salomaa, A. 1966. 
        Two complete axiom systems for the algebra of regular events.
        {\it J. ACM}. 13(1):158-169.
\bibitem[Searls, 1993]{Searls}
	Searls, D. 1993.
	The computational linguistics of biological sequences. In {\it Artificial Intelligence
	and Molecular Biology.} L. Hunter (ed.), MIT Press, 1993, pp. 47-120.
\bibitem[Wood, 1987]{wood}
        Wood, D. 1987.
        {\it Theory of Computation}. Harper and Row.
\end{thebibliography}

\bigskip
\sloppy
{\noindent \large \bf Further Information}\\
The fundamentals of formal languages and grammars can be found in many text
books including~\cite{Drobot,floyd,gurari,Harel,Harrison,HU79,wood}.
The central focus of research in this area has been to find formal
grammatical representations of languages that are very expressive
and are yet easy to parse. The research results have greatly benefited many
fields of computer science, including programming languages, compiler design,
and natural language processing. 
The preceding chapter presents the machine model counterparts of
regular grammars, context-free grammars, context-sensitive grammars,
and unrestricted grammars, and the next chapter
introduces the concepts of decidability and undecidability, which has a close
relation to formal grammars.
The following annual conferences present the leading research 
work in formal languages and grammars: 
International Colloquium on Automata, Languages and Programming (ICALP),
ACM Annual Symposium on Theory of Computing (STOC), IEEE
Symposium on the Foundations of Computer Science (FOCS),
ACM Symposium on Principles of Programming Languages (POPL),
Symposium on Theoretical Aspects of Computer Science (STACS), Mathematical
Foundations of Computer Science (MFCS),
Fundamentals of Computation Theory (FCT), 
Foundation of Software Technology and Theoretical Computer Science (FSTTCS),
and Conference on Developments in Language Theory (DLT).
There are many related conferences, including Computational Learning
Theory (COLT), Colloquium on Trees in Algebra and Programming (CAAP),
%
% Editor !! CAAP is not a typo!
%
and International Conference on Concurrency Theory (CONCUR), where
either specific issues concerning formal grammars are considered
or specialized grammatical systems are studied for a specific application
area. We conclude with a list of major journals that publish papers
in formal language theory:
{\em Journal of the ACM\/},
{\em SIAM Journal on Computing\/},
{\em Journal of Computer and System Sciences\/},
{\em Information and Computation\/},
{\em Theory of Computing Systems\/}
(formerly {\em Mathematical Systems Theory\/}),
{\em Theoretical Computer Science\/},
{\em Information Processing Letters\/},
{\em International Journal of Foundations of Computer Science\/},
and {\em Acta Informatica\/}.

\end{document}






