\documentclass{article}+
−
\usepackage{charter}+
−
\usepackage{hyperref}+
−
\usepackage{amssymb}+
−
\usepackage{amsmath}+
−
\usepackage[T1]{fontenc}+
−
\usepackage{listings}+
−
\usepackage{xcolor}+
−
\usepackage{tikz}+
−
\usetikzlibrary{arrows}+
−
\usetikzlibrary{automata}+
−
\usetikzlibrary{shapes}+
−
\usetikzlibrary{shadows}+
−
\usetikzlibrary{positioning}+
−
\usetikzlibrary{calc}+
−
\usetikzlibrary{fit}+
−
\usetikzlibrary{backgrounds}+
−
\usepackage{fontspec}+
−
\setmonofont{Consolas}+
−
+
−
\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}%+
−
+
−
\definecolor{javared}{rgb}{0.6,0,0} % for strings+
−
\definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments+
−
\definecolor{javapurple}{rgb}{0.5,0,0.35} % keywords+
−
\definecolor{javadocblue}{rgb}{0.25,0.35,0.75} % javadoc+
−
+
−
\lstdefinelanguage{scala}{+
−
  morekeywords={abstract,case,catch,class,def,%+
−
    do,else,extends,false,final,finally,%+
−
    for,if,implicit,import,match,mixin,%+
−
    new,null,object,override,package,%+
−
    private,protected,requires,return,sealed,%+
−
    super,this,throw,trait,true,try,%+
−
    type,val,var,while,with,yield},+
−
  otherkeywords={=>,<-,<\%,<:,>:,\#,@},+
−
  sensitive=true,+
−
  morecomment=[l]{//},+
−
  morecomment=[n]{/*}{*/},+
−
  morestring=[b]",+
−
  morestring=[b]',+
−
  morestring=[b]"""+
−
}+
−
+
−
\lstdefinelanguage{while}{+
−
  morekeywords={while, if, then. else, read, write},+
−
  otherkeywords={=>,<-,<\%,<:,>:,\#,@},+
−
  sensitive=true,+
−
  morecomment=[l]{//},+
−
  morecomment=[n]{/*}{*/},+
−
  morestring=[b]",+
−
  morestring=[b]',+
−
  morestring=[b]"""+
−
}+
−
+
−
+
−
\lstset{language=Scala,+
−
	basicstyle=\ttfamily,+
−
	keywordstyle=\color{javapurple}\bfseries,+
−
	stringstyle=\color{javagreen},+
−
	commentstyle=\color{javagreen},+
−
	morecomment=[s][\color{javadocblue}]{/**}{*/},+
−
	numbers=left,+
−
	numberstyle=\tiny\color{black},+
−
	stepnumber=1,+
−
	numbersep=10pt,+
−
	tabsize=2,+
−
	showspaces=false,+
−
	showstringspaces=false}+
−
	+
−
\newcommand\grid[1]{%+
−
\begin{tikzpicture}[baseline=(char.base)]+
−
  \path[use as bounding box]+
−
    (0,0) rectangle (1em,1em);+
−
  \draw[red!50, fill=red!20]+
−
    (0,0) rectangle (1em,1em);+
−
  \node[inner sep=1pt,anchor=base west]+
−
    (char) at (0em,\gridraiseamount) {#1};+
−
\end{tikzpicture}}+
−
\newcommand\gridraiseamount{0.12em}+
−
+
−
\makeatletter+
−
\newcommand\Grid[1]{%+
−
  \@tfor\z:=#1\do{\grid{\z}}}+
−
\makeatother	+
−
+
−
\newcommand\Vspace[1][.3em]{%+
−
  \mbox{\kern.06em\vrle height.3ex}%+
−
  \vbox{\hrule width#1}%+
−
  \hbox{\vrule height.3ex}}+
−
+
−
\def\VS{\Vspace[0.6em]}+
−
	+
−
\begin{document}+
−
+
−
\section*{Handout 6}+
−
+
−
While regular expressions are very useful for lexing and for recognising+
−
many patterns (like email addresses), they have their limitations. For+
−
example there is no regular expression that can recognise the language +
−
$a^nb^n$. Another example is the language of well-parenthesised +
−
expressions.  In languages like Lisp, which use parentheses rather+
−
extensively, it might be of interest whether the following two expressions+
−
are well-parenthesised (the left one is, the right one is not):+
−
+
−
\begin{center}+
−
$(((()()))())$  \hspace{10mm} $(((()()))()))$+
−
\end{center}+
−
+
−
In order to solve such recognition problems, we need more powerful +
−
techniques than regular expressions. We will in particular look at \emph{context-free+
−
languages}. They include the regular languages as the picture below shows:+
−
+
−
+
−
\begin{center}+
−
\begin{tikzpicture}+
−
[rect/.style={draw=black!50, top color=white,bottom color=black!20, rectangle, very thick, rounded corners}]+
−
+
−
\draw (0,0) node [rect, text depth=30mm, text width=46mm] {all languages};+
−
\draw (0,-0.4) node [rect, text depth=20mm, text width=44mm] {decidable languages};+
−
\draw (0,-0.65) node [rect, text depth=13mm] {context sensitive languages};+
−
\draw (0,-0.84) node [rect, text depth=7mm, text width=35mm] {context-free languages};+
−
\draw (0,-1.05) node [rect] {regular languages};+
−
\end{tikzpicture}+
−
\end{center}+
−
+
−
\noindent+
−
Context-free languages play an important role in `day-to-day' text processing and in+
−
programming languages. Context-free languages are usually specified by grammars.+
−
For example a grammar for well-parenthesised  expressions is+
−
+
−
\begin{center}+
−
$P \;\;\rightarrow\;\; ( \cdot  P \cdot ) \cdot P \;|\; \epsilon$+
−
\end{center}+
−
 +
−
\noindent+
−
In general grammars consist of finitely many rules built up from terminal symbols (usually lower-case letters)+
−
and non-terminal symbols (upper-case letters).  Rules have the shape+
−
+
−
\begin{center}+
−
$NT \;\;\rightarrow\;\; \textit{rhs}$+
−
\end{center}+
−
 +
−
\noindent+
−
where on the left-hand side is a single non-terminal and on the right a string consisting+
−
of both terminals and non-terminals including the $\epsilon$-symbol for indicating the+
−
empty string. We use the convention  to separate components on+
−
the right hand-side by using the $\cdot$ symbol, as in the grammar for well-parenthesised  expressions.+
−
We also use the convention to use $|$ as a shorthand notation for several rules. For example+
−
+
−
\begin{center}+
−
$NT \;\;\rightarrow\;\; \textit{rhs}_1 \;|\; \textit{rhs}_2$+
−
\end{center}+
−
+
−
\noindent+
−
means that the non-terminal $NT$ can be replaced by either $\textit{rhs}_1$ or $\textit{rhs}_2$.+
−
If there are more than one non-terminal on the left-hand side of the rules, then we need to indicate+
−
what is the \emph{starting} symbol of the grammar. For example the grammar for arithmetic expressions+
−
can be given as follows+
−
+
−
\begin{center}+
−
\begin{tabular}{lcl}+
−
$E$ & $\rightarrow$ &  $N$ \\+
−
$E$ & $\rightarrow$ &  $E \cdot + \cdot E$ \\+
−
$E$ & $\rightarrow$ &  $E \cdot - \cdot E$ \\+
−
$E$ & $\rightarrow$ &  $E \cdot * \cdot E$ \\+
−
$E$ & $\rightarrow$ &  $( \cdot E \cdot )$\\+
−
$N$ & $\rightarrow$ & $N \cdot N \;|\; 0 \;|\; 1 \;|\: \ldots \;|\; 9$ +
−
\end{tabular}+
−
\end{center}+
−
+
−
\noindent+
−
where $E$ is the starting symbol. A \emph{derivation} for a grammar+
−
starts with the staring symbol of the grammar and in each step replaces one+
−
non-terminal by a right-hand side of a rule. A derivation ends with a string+
−
in which only terminal symbols are left. For example a derivation for the+
−
string $(1 + 2) + 3$ is as follows:+
−
+
−
\begin{center}+
−
\begin{tabular}{lll}+
−
$E$ & $\rightarrow$ & $E+E$\\+
−
       & $\rightarrow$ & $(E)+E$\\+
−
       & $\rightarrow$ & $(E+E)+E$\\+
−
       & $\rightarrow$ & $(E+E)+N$\\+
−
       & $\rightarrow$ & $(E+E)+3$\\+
−
       & $\rightarrow$ & $(N+E)+3$\\	+
−
       & $\rightarrow^+$ & $(1+2)+3$\\+
−
\end{tabular} +
−
\end{center}+
−
+
−
\noindent+
−
The \emph{language} of a context-free grammar $G$ with start symbol $S$ +
−
is defined as the set of strings derivable by a derivation, that is+
−
+
−
\begin{center}+
−
$\{c_1\ldots c_n \;|\; S \rightarrow^* c_1\ldots c_n \;\;\text{with all} \; c_i \;\text{being non-terminals}\}$+
−
\end{center}+
−
+
−
\noindent+
−
A \emph{parse-tree} encodes how a string is derived with the starting symbol on +
−
top and each non-terminal containing a subtree for how it is replaced in a derivation.+
−
The parse tree for the string $(1 + 23)+4$ is as follows:+
−
+
−
\begin{center}+
−
\begin{tikzpicture}[level distance=8mm, black]+
−
  \node {$E$}+
−
    child {node {$E$} +
−
       child {node {$($}}+
−
       child {node {$E$}       +
−
         child {node {$E$} child {node {$N$} child {node {$1$}}}}+
−
         child {node {$+$}}+
−
         child {node {$E$} +
−
            child {node {$N$} child {node {$2$}}}+
−
            child {node {$N$} child {node {$3$}}}+
−
            } +
−
        }+
−
       child {node {$)$}}+
−
     }+
−
     child {node {$+$}}+
−
     child {node {$E$}+
−
        child {node {$N$} child {node {$4$}}}+
−
     };+
−
\end{tikzpicture}+
−
\end{center}+
−
+
−
\noindent+
−
We are often interested in these parse-trees since they encode the structure of+
−
how a string is derived by a grammar. Before we come to the problem of constructing+
−
such parse-trees, we need to consider the following two properties of grammars.+
−
A grammar is \emph{left-recursive} if there is a derivation starting from a non-terminal, say+
−
$NT$ which leads to a string which again starts with $NT$. This means a derivation of the+
−
form.+
−
+
−
\begin{center}+
−
$NT \rightarrow \ldots \rightarrow NT \cdot \ldots$+
−
\end{center}+
−
+
−
\noindent+
−
It can be easily seems that the grammar above for arithmetic expressions is left-recursive:+
−
for example the rules $E \rightarrow E\cdot + \cdot E$ and $N \rightarrow N\cdot N$ +
−
show that this grammar is left-recursive. Some algorithms cannot cope with left-recursive +
−
grammars. Fortunately every left-recursive grammar can be transformed into one that is+
−
not left-recursive, although this transformation might make the grammar less human-readable.+
−
For example if we want to give a non-left-recursive grammar for numbers we might+
−
specify+
−
+
−
\begin{center}+
−
$N \;\;\rightarrow\;\; 0\;|\;\ldots\;|\;9\;|\;1\cdot N\;|\;2\cdot N\;|\;\ldots\;|\;9\cdot N$+
−
\end{center}+
−
+
−
\noindent+
−
Using this grammar we can still derive every number string, but we will never be able +
−
to derive a string of the form $\ldots \rightarrow N \cdot \ldots$.+
−
+
−
The other property we have to watch out is when a grammar is+
−
\emph{ambiguous}. A grammar is said to be ambiguous if there are two parse-trees+
−
for one string. Again the grammar for arithmetic expressions shown above is ambiguous.+
−
While the shown parse tree for the string $(1 + 23) + 4$ is unique, there are two parse+
−
trees for the string $1 + 2 + 3$, namely+
−
+
−
\begin{center}+
−
\begin{tabular}{c@{\hspace{10mm}}c}+
−
\begin{tikzpicture}[level distance=8mm, black]+
−
  \node {$E$}+
−
    child {node {$E$} child {node {$N$} child {node {$1$}}}}+
−
    child {node {$+$}}+
−
    child {node {$E$}+
−
       child {node {$E$} child {node {$N$} child {node {$2$}}}}+
−
       child {node {$+$}}+
−
       child {node {$E$} child {node {$N$} child {node {$3$}}}}+
−
    }+
−
    ;+
−
\end{tikzpicture} +
−
&+
−
\begin{tikzpicture}[level distance=8mm, black]+
−
  \node {$E$}+
−
    child {node {$E$}+
−
       child {node {$E$} child {node {$N$} child {node {$1$}}}}+
−
       child {node {$+$}}+
−
       child {node {$E$} child {node {$N$} child {node {$2$}}}} +
−
    }+
−
    child {node {$+$}}+
−
    child {node {$E$} child {node {$N$} child {node {$3$}}}}+
−
    ;+
−
\end{tikzpicture}+
−
\end{tabular} +
−
\end{center}+
−
+
−
\noindent+
−
In particular in programming languages we will try to avoid ambiguous+
−
grammars because two different parse-trees for a string mean a program can+
−
be interpreted in two different ways. In such cases we have to somehow make sure+
−
the two different ways do not matter, or disambiguate the grammar in+
−
some way (for example making the $+$ left-associative). Unfortunately already +
−
the problem of deciding whether a grammar+
−
is ambiguous or not is in general undecidable. +
−
+
−
Let us now turn to the problem of generating a parse-tree for a grammar and string.+
−
In what follows we explain \emph{parser combinators}, because they are easy+
−
to implement and closely resemble grammar rules. Imagine that a grammar+
−
describes the strings of natural numbers, such as the grammar $N$ shown above.+
−
For all such strings we want to generate the parse-trees or later on we actually +
−
want to extract the meaning of these strings, that is the concrete integers ``behind'' +
−
these strings. The parser combinators will be functions of type+
−
+
−
\begin{center}+
−
\texttt{I $\Rightarrow$ Set[(T, I)]}+
−
\end{center}+
−
+
−
\noindent +
−
that is they take as input something of type \texttt{I}, typically a list of tokens or a string,+
−
and return a set of pairs. The first component of these pairs corresponds to what the+
−
parser combinator was able to process from the input and the second is the unprocessed +
−
part of the input. As we shall see shortly, a parser combinator might return more than one such pair,+
−
with the idea that there are potentially several ways how to interpret the input.+
−
+
−
The abstract class for parser combinators requires the implementation of the function+
−
\texttt{parse} taking an argument of type \texttt{I} and returns a set of type  +
−
\mbox{\texttt{Set[(T, I)]}}.+
−
+
−
\begin{center}+
−
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]+
−
abstract class Parser[I, T] {+
−
  def parse(ts: I): Set[(T, I)]+
−
+
−
  def parse_all(ts: I): Set[T] =+
−
    for ((head, tail) <- parse(ts); if (tail.isEmpty)) +
−
      yield head+
−
}+
−
\end{lstlisting}+
−
\end{center}+
−
+
−
\noindent+
−
One of the simplest parser combinators recognises just a character, say $c$, +
−
from the beginning of strings. Its behaviour is as follows:+
−
+
−
\begin{itemize}+
−
\item if the head of the input string starts with a $c$, it returns +
−
	the set $\{(c, \textit{tail of}\; s)\}$+
−
\item otherwise it returns the empty set $\varnothing$	+
−
\end{itemize}+
−
+
−
\noindent+
−
The input type of this simple parser combinator for characters is+
−
\texttt{String} and the output type \mbox{\texttt{Set[(Char, String)]}}. +
−
The code in Scala is as follows:+
−
+
−
\begin{center}+
−
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]+
−
case class CharParser(c: Char) extends Parser[String, Char] {+
−
  def parse(sb: String) = +
−
    if (sb.head == c) Set((c, sb.tail)) else Set()+
−
}+
−
\end{lstlisting}+
−
\end{center}+
−
+
−
+
−
\end{document}+
−
+
−
%%% Local Variables: +
−
%%% mode: latex  +
−
%%% TeX-master: t+
−
%%% End: +
−