\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]{%

  \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

example there is no regular expression that can recognise the language 

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

\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

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$.

\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.

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

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'' 

\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,

\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}