\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$ & $\epsilon \;|\; 0 \cdot N \;|\; 1 \cdot N \;|\: \ldots \;|\; 9 \cdot N$ +
−
\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.+
−
+
−
+
−
\end{document}+
−
+
−
%%% Local Variables: +
−
%%% mode: latex  +
−
%%% TeX-master: t+
−
%%% End: +
−