+
−
% !TEX program = xelatex+
−
\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer}+
−
\usepackage{../slides}+
−
\usepackage{../graphicss}+
−
\usepackage{../langs}+
−
\usepackage{../data}+
−
\usepackage{../grammar}+
−
+
−
\hfuzz=220pt +
−
+
−
\pgfplotsset{compat=1.11}+
−
+
−
\newcommand{\bl}[1]{\textcolor{blue}{#1}}  +
−
+
−
% beamer stuff +
−
\renewcommand{\slidecaption}{CFL 05, King's College London}+
−
+
−
\usepackage{tcolorbox}+
−
\newtcolorbox{mybox}{colback=red!5!white,colframe=red!75!black}+
−
\newtcolorbox{mybox2}[1]{colback=red!5!white,colframe=red!75!black,fonttitle=\bfseries,title=#1}+
−
\newtcolorbox{mybox3}[1]{colback=Cyan!5!white,colframe=Cyan!75!black,fonttitle=\bfseries,title=#1}+
−
+
−
+
−
+
−
\begin{document}+
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
\begin{frame}[t]+
−
\frametitle{%+
−
  \begin{tabular}{@ {}c@ {}}+
−
  \\[-3mm]+
−
  \LARGE Compilers and \\[-1mm] +
−
  \LARGE Formal Languages\\[-5mm] +
−
  \end{tabular}}+
−
+
−
  \normalsize+
−
  \begin{center}+
−
  \begin{tabular}{ll}+
−
  Email:  & christian.urban at kcl.ac.uk\\+
−
Office Hour: & Fridays 12 -- 14\\  +
−
  Location: & N7.07 (North Wing, Bush House)\\+
−
  Slides \& Progs: & KEATS\\+
−
  Pollev: & \texttt{\alert{https://pollev.com/cfltutoratki576}}\\  +
−
  \end{tabular}+
−
  \end{center}+
−
+
−
  \begin{center}+
−
    \begin{tikzpicture}+
−
      \node[drop shadow,fill=white,inner sep=0pt] +
−
      {\footnotesize\rowcolors{1}{capri!10}{white}+
−
        \begin{tabular}{|p{4.8cm}|p{4.8cm}|}\hline+
−
          1 Introduction, Languages          & 6 While-Language \\+
−
          2 Regular Expressions, Derivatives & 7 Compilation, JVM \\+
−
          3 Automata, Regular Languages      & 8 Compiling Functional Languages \\+
−
          4 Lexing, Tokenising               & 9 Optimisations \\+
−
          \cellcolor{blue!50}+
−
          5 Grammars, Parsing                & 10 LLVM \\ \hline+
−
        \end{tabular}%+
−
      };+
−
    \end{tikzpicture}+
−
  \end{center}+
−
\end{frame}+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     +
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
%\begin{frame}[c]+
−
%  \frametitle{Coursework 1: Submissions}+
−
%  +
−
%  \begin{itemize}+
−
%  \item Scala (29)+
−
%  \item Haskell (1)+
−
%  \item Kotlin (1)+
−
%  \item Rust (1)+
−
%  \end{itemize}\bigskip\bigskip  +
−
%  +
−
%  \small+
−
%  Please get in contact if you intend to do CW Strand 2. No zips please.+
−
%  Give definitions also on paper if asked. BTW, simp +
−
%  can stay unchanged. Use \texttt{ders} for CW2, not \texttt{ders2}!+
−
%  \end{frame}+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
+
−
{+
−
\setbeamercolor{background canvas}{bg=cream}+
−
\begin{frame}<1-10>[c]+
−
\end{frame}+
−
+
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
\begin{frame}[c]+
−
  \frametitle{Coursework 1: Submissions}+
−
  +
−
  \begin{itemize}+
−
  \item Scala (162)+
−
  \item Ocaml (1)+
−
  \item Java (1)  \ldots uses new features of Java 21  +
−
  \item Rust (6)+
−
  \end{itemize}\bigskip\bigskip  +
−
  +
−
+
−
\end{frame}+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
}+
−
+
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
\begin{frame}[t]+
−
\frametitle{Parser}+
−
\mbox{}\\[-16mm]\mbox{}+
−
+
−
\begin{center}+
−
  \begin{tikzpicture}[scale=1,+
−
                      node/.style={+
−
                      rectangle,rounded corners=3mm,+
−
                      very thick,draw=black!50,+
−
                      minimum height=18mm, minimum width=20mm,+
−
                      top color=white,bottom color=black!20,drop shadow}]+
−
  \node (0) at (-2.3,0) {}; +
−
  +
−
  \node (A) at (0,0)  [node] {};+
−
  \node [below right] at (A.north west) {lexer};+
−
+
−
  \node (B) at (3,0)  [node] {};+
−
  \node [below right=1mm] at (B.north west) +
−
    {\mbox{}\hspace{-1mm}parser};+
−
+
−
  \node (C) at (6,0)  [node] {};+
−
  \node [below right] at (C.north west) +
−
    {\mbox{}\hspace{-1mm}code gen};+
−
+
−
  \node (1) at (8.4,0) {}; +
−
+
−
  \draw [->,line width=4mm] (0) -- (A); +
−
  \draw [->,line width=4mm] (A) -- (B); +
−
  \draw [->,line width=4mm] (B) -- (C); +
−
  \draw [->,line width=4mm] (C) -- (1); +
−
  \end{tikzpicture}+
−
  \end{center}+
−
  +
−
+
−
\only<2>{+
−
\begin{textblock}{1}(3,6)+
−
\begin{bubble}[8.5cm]+
−
\normalsize+
−
parser input: a sequence of tokens\smallskip\\+
−
+
−
{\small\hspace{5mm}\code{key(read) lpar id(n) rpar semi}}\smallskip\\+
−
+
−
parser output: an abstract syntax tree\smallskip\\+
−
\footnotesize+
−
\hspace{2cm}\begin{tikzpicture}+
−
  \node {\code{read}}+
−
    child {node {\code{lpar}}}+
−
    child {node {\code{n}}}+
−
    child {node {\code{rpar}}};+
−
\end{tikzpicture}+
−
\end{bubble}+
−
\end{textblock}}+
−
\end{frame}+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
\begin{frame}[c]+
−
\frametitle{What Parsing is Not}+
−
+
−
Usually parsing does not check semantic correctness, e.g.+
−
+
−
\begin{itemize}+
−
\item  whether a function is not used before it+
−
  is defined+
−
\item whether a function has the correct number of arguments +
−
  or are of correct type+
−
\item whether a variable can be declared twice in a scope  +
−
\end{itemize}  +
−
+
−
\end{frame}+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   +
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
{+
−
\setbeamercolor{background canvas}{bg=cream}+
−
\begin{frame}[c]+
−
+
−
\begin{center}+
−
\begin{tikzpicture}[scale=1.5,>=stealth',very thick,+
−
                    every state/.style={minimum size=0pt,+
−
                    draw=blue!50,very thick,fill=blue!20}]+
−
  \node[state,initial]   (q0) at (0,2) {$q_0$};+
−
  \node[state,accepting] (q1) at (2,2) {$q_1$};+
−
  \node[state]           (q2) at (0,0) {$q_2$};+
−
  \node[state]           (q3) at (2,0) {$q_3$};+
−
+
−
  \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1)+
−
            (q1) edge[bend left] node[above] {\alert{$a$}} (q0)+
−
            (q2) edge[bend left] node[above] {\alert{$a$}} (q3)+
−
            (q3) edge[bend left] node[above] {\alert{$a$}} (q2)+
−
            (q0) edge[bend left] node[right] {\alert{$b$}} (q2)+
−
            (q2) edge[bend left] node[left]  {\alert{$b$}} (q0)+
−
            (q1) edge[bend left] node[right] {\alert{$b$}} (q3)+
−
            (q3) edge[bend left] node[left]  {\alert{$b$}} (q1);+
−
\end{tikzpicture}+
−
\end{center}+
−
+
−
\hfill{}Which language?+
−
+
−
\end{frame}+
−
}+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
+
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
\begin{frame}[c]+
−
\frametitle{Regular Languages}+
−
+
−
While regular expressions are very useful for lexing, there is+
−
no regular expression that can recognise the language+
−
\bl{$a^nb^n$}.\bigskip+
−
+
−
\begin{center}+
−
\bl{$(((()()))())$} \;\;vs.\;\; \bl{$(((()()))()))$}+
−
\end{center}\bigskip\bigskip+
−
+
−
\small+
−
\noindent So we cannot find out with regular expressions+
−
whether parentheses are matched or unmatched. Also regular+
−
expressions are not recursive, e.g.~\bl{$(1 + 2) + 3$}.+
−
+
−
\end{frame}+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   +
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
\begin{frame}[c]+
−
\frametitle{Hierarchy of Languages}+
−
+
−
\begin{center}+
−
\begin{tikzpicture}+
−
[rect/.style={draw=black!50, +
−
              top color=white,+
−
              bottom color=black!20, +
−
              rectangle, +
−
              very thick, +
−
              rounded corners}, scale=1.2]+
−
+
−
\draw (0,0) node [rect, text depth=39mm, text width=68mm] {all languages};+
−
\draw (0,-0.4) node [rect, text depth=28.5mm, text width=64mm] {decidable languages};+
−
\draw (0,-0.85) node [rect, text depth=17mm] {context sensitive languages};+
−
\draw (0,-1.14) node [rect, text depth=9mm, text width=50mm] {context-free languages};+
−
\draw (0,-1.4) node [rect] {regular languages};+
−
\end{tikzpicture}+
−
+
−
\end{center}+
−
+
−
\end{frame}+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   +
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +
−
\begin{frame}[c]+
−
  \LARGE+
−
  \begin{center}+
−
  Time flies like an arrow.\\ +
−
  Fruit flies like bananas.+
−
  \end{center}  +
−
\end{frame}+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
  +
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
\begin{frame}[c]+
−
\frametitle{CFGs}+
−
+
−
A \alert{\bf context-free grammar} \bl{$G$} consists of+
−
+
−
\begin{itemize}+
−
\item a finite set of nonterminal symbols (e.g.~$\meta{A}$ upper case)+
−
\item a finite set terminal symbols or tokens (lower case)+
−
\item a start symbol (which must be a nonterminal)+
−
\item a set of rules+
−
\begin{center}+
−
\bl{$\meta{A} ::= \textit{rhs}$}+
−
\end{center}+
−
+
−
where \bl{\textit{rhs}} are sequences involving terminals and nonterminals,+
−
including the empty sequence \bl{$\epsilon$}.\medskip\pause+
−
+
−
We also allow rules+
−
\begin{center}+
−
\bl{$\meta{A} ::= \textit{rhs}_1 | \textit{rhs}_2 | \ldots$}+
−
\end{center}+
−
\end{itemize}+
−
+
−
\end{frame}+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   +
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
\begin{frame}[t]+
−
\frametitle{Palindromes}+
−
+
−
A grammar for palindromes over the alphabet~\bl{$\{a,b\}$}:+
−
+
−
\only<1>{%+
−
\bl{\begin{plstx}[margin=1cm]+
−
: \meta{S} ::= a\cdot\meta{S}\cdot a\\+
−
: \meta{S} ::= b\cdot\meta{S}\cdot b\\+
−
: \meta{S} ::= a\\+
−
: \meta{S} ::= b\\+
−
: \meta{S} ::= \epsilon\\+
−
\end{plstx}}}+
−
%+
−
\only<2>{%+
−
\bl{\begin{plstx}[margin=1cm]+
−
: \meta{S} ::=  a\cdot \meta{S}\cdot a | b\cdot \meta{S}\cdot b | a | b | \epsilon\\+
−
\end{plstx}}}+
−
+
−
%\small+
−
%Can you find the grammar rules for matched parentheses?+
−
+
−
\end{frame}+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   +
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
\begin{frame}[c]+
−
\frametitle{Arithmetic Expressions}+
−
+
−
\bl{\begin{plstx}[margin=3cm,one per line]+
−
: \meta{E} ::=  0 \mid 1 \mid 2 \mid ... \mid 9+
−
   | \meta{E} \cdot + \cdot \meta{E} +
−
   | \meta{E} \cdot - \cdot \meta{E} +
−
   | \meta{E} \cdot * \cdot \meta{E} +
−
   | ( \cdot \meta{E} \cdot ) \\+
−
\end{plstx}}\pause+
−
+
−
\bl{\texttt{1 + 2 * 3 + 4}}+
−
+
−
\end{frame}+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   +
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
\begin{frame}[c]+
−
\frametitle{A CFG Derivation}+
−
+
−
\begin{enumerate}+
−
\item Begin with a string containing only the start symbol, say \bl{\meta{S}}\bigskip+
−
\item Replace any nonterminal \bl{\meta{X}} in the string by the+
−
right-hand side of some production \bl{$\meta{X} ::= \textit{rhs}$}\bigskip+
−
\item Repeat 2 until there are no nonterminals left+
−
\end{enumerate}+
−
+
−
\begin{center}+
−
\bl{$\meta{S} \rightarrow \ldots \rightarrow \ldots  \rightarrow \ldots  \rightarrow \ldots $}+
−
\end{center}+
−
+
−
\end{frame}+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +
−
  +
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
\begin{frame}[t]+
−
\frametitle{Example Derivation}+
−
+
−
\bl{\begin{plstx}[margin=2cm]+
−
: \meta{S} ::=  \epsilon | a\cdot \meta{S}\cdot a | b\cdot \meta{S}\cdot b \\+
−
\end{plstx}}\bigskip+
−
+
−
\begin{center}+
−
\begin{tabular}{lcl}+
−
\bl{\meta{S}} & \bl{$\rightarrow$} & \bl{$a\meta{S}a$}\\+
−
              & \bl{$\rightarrow$} & \bl{$ab\meta{S}ba$}\\+
−
              & \bl{$\rightarrow$} & \bl{$aba\meta{S}aba$}\\+
−
              & \bl{$\rightarrow$} & \bl{$abaaba$}\\+
−
+
−
 +
−
\end{tabular}+
−
\end{center}+
−
+
−
\end{frame}+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   +
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
\begin{frame}[t]+
−
\frametitle{Example Derivation}+
−
+
−
\bl{\begin{plstx}[margin=3cm,one per line]+
−
: \meta{E} ::=  0 \mid 1 \mid 2 \mid ... \mid 9+
−
   | \meta{E} \cdot + \cdot \meta{E} +
−
   | \meta{E} \cdot - \cdot \meta{E} +
−
   | \meta{E} \cdot * \cdot \meta{E} +
−
   | ( \cdot \meta{E} \cdot ) \\+
−
\end{plstx}}+
−
+
−
\small+
−
\begin{center}+
−
\begin{tabular}{@{}c@{}c@{}}+
−
\begin{tabular}{@{\hspace{-2mm}}l@{\hspace{1mm}}l@{\hspace{1mm}}l@{\hspace{4mm}}}+
−
\bl{\meta{E}} & \bl{$\rightarrow$} & \bl{$\meta{E}*\meta{E}$}\\+
−
              & \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}*\meta{E}$}\\+
−
              & \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}*\meta{E}+\meta{E}$}\\+
−
              & \bl{$\rightarrow^+$} & \bl{$1+2*3+4$}\\+
−
\end{tabular} &\pause+
−
\begin{tabular}{@{}l@{\hspace{0mm}}l@{\hspace{1mm}}l}+
−
\bl{$\meta{E}$} & \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}$}\\+
−
                & \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}+\meta{E}$}\\+
−
                & \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}*\meta{E}+\meta{E}$}\\+
−
                & \bl{$\rightarrow^+$} & \bl{$1+2*3+4$}\\+
−
\end{tabular}+
−
\end{tabular}+
−
\end{center}+
−
+
−
\end{frame}+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   +
−
+
−
   +
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
\begin{frame}[c]+
−
\frametitle{Language of a CFG}+
−
+
−
Let \bl{$G$} be a context-free grammar with start symbol \bl{\meta{S}}. +
−
Then the language \bl{$L(G)$} is:+
−
+
−
\begin{center}+
−
\bl{$\{c_1\ldots c_n \;|\; \forall i.\; c_i \in T \wedge \meta{S} \rightarrow^* c_1\ldots c_n \}$}+
−
\end{center}\pause+
−
+
−
\begin{itemize}+
−
\item Terminals, because there are no rules for replacing them.+
−
\item Once generated, terminals are ``permanent''.+
−
\item Terminals ought to be tokens of the language\\+
−
(but can also be strings).+
−
\end{itemize}+
−
+
−
\end{frame}+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   +
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
\begin{frame}[t]+
−
\frametitle{Parse Trees}+
−
\mbox{}\\[-12mm]+
−
+
−
\bl{\begin{plstx}: \meta{E} ::= \meta{T} | \meta{T} \cdot + \cdot \meta{E} |  \meta{T} \cdot - \cdot \meta{E}\\+
−
: \meta{T} ::= \meta{F} | \meta{F} \cdot * \cdot \meta{T}\\+
−
: \meta{F} ::= 0 ... 9 | ( \cdot \meta{E} \cdot )\\+
−
\end{plstx}}+
−
+
−
\begin{textblock}{5}(6, 5)+
−
\small+
−
\begin{tikzpicture}[level distance=10mm, blue]+
−
  \node {$\meta{E}$}+
−
  child {node {$\meta{T}$}+
−
    child {node {$\meta{F}$} child {node {1}}}+
−
  }+
−
  child {node {+}}+
−
  child {node {$\meta{E}$}+
−
    child[sibling distance=10mm] {node {$\meta{T}$}+
−
      child {node {$\meta{F}$} child {node {2}}}+
−
      child {node {*}}+
−
      child {node {$\meta{T}$} child {node {$\meta{F}$} child {node {3}}}}+
−
    }+
−
    child {node {+}}+
−
    child {node {$\meta{E}$} child {node {$\meta{T}$}+
−
        child {node {$\meta{F}$} child {node {4}}}}}+
−
  } +
−
  ;+
−
\end{tikzpicture}+
−
\end{textblock}+
−
+
−
\begin{textblock}{5}(1, 10)+
−
\bl{\texttt{1 + 2 * 3 + 4}}+
−
\end{textblock}+
−
+
−
\end{frame}+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   +
−
+
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
\begin{frame}[t]+
−
\frametitle{Arithmetic Expressions}+
−
+
−
\bl{\begin{plstx}[margin=3cm,one per line]+
−
: \meta{E} ::=  0..9 +
−
   | \meta{E} \cdot + \cdot \meta{E} +
−
   | \meta{E} \cdot - \cdot \meta{E} +
−
   | \meta{E} \cdot * \cdot \meta{E} +
−
   | ( \cdot \meta{E} \cdot ) \\+
−
\end{plstx}}\pause\bigskip+
−
+
−
A CFG is \alert{\bf left-recursive} if it has a nonterminal \bl{$\meta{E}$} such+
−
that \bl{$\meta{E} \rightarrow^+ \meta{E}\cdot \ldots$}+
−
+
−
\end{frame}+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   +
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
\begin{frame}[t]+
−
\frametitle{Ambiguous Grammars}+
−
+
−
A grammar is \alert{\bf ambiguous} if there is a string that+
−
has at least two different parse trees.+
−
+
−
\bl{\begin{plstx}[margin=3cm,one per line]: \meta{E} ::=  0 ... 9 +
−
   | \meta{E} \cdot + \cdot \meta{E} +
−
   | \meta{E} \cdot - \cdot \meta{E} +
−
   | \meta{E} \cdot * \cdot \meta{E} +
−
   | ( \cdot \meta{E} \cdot ) \\+
−
\end{plstx}}+
−
+
−
+
−
\bl{\texttt{1 + 2 * 3 + 4}}+
−
+
−
\end{frame}+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   +
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
\begin{frame}[c]+
−
\frametitle{`Dangling' Else}+
−
+
−
Another ambiguous grammar:\bigskip+
−
+
−
\begin{center}+
−
\bl{\begin{tabular}{lcl}+
−
$E$ & $\rightarrow$ &  if $E$ then $E$\\+
−
 & $|$ &  if $E$ then $E$ else $E$ \\+
−
 & $|$ &  \ldots+
−
\end{tabular}}+
−
\end{center}\bigskip+
−
+
−
\bl{\texttt{if a then if x then y else c}}+
−
+
−
\end{frame}+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
\begin{frame}[c]+
−
\frametitle{CYK Algorithm}+
−
+
−
Suppose the grammar:+
−
+
−
\begin{center}+
−
\bl{\begin{tabular}{@ {}lcl@ {}}+
−
$\meta{S}$ & $::=$ &  $\meta{N}\cdot \meta{P}$ \\+
−
$\meta{P}$ & $::=$ &  $\meta{V}\cdot \meta{N}$ \\+
−
$\meta{N}$ & $::=$ &  $\meta{N}\cdot \meta{N}$ \\+
−
$\meta{N}$ & $::=$ &  $\texttt{students} \;|\; \texttt{Jeff} \;|\; \texttt{geometry} \;|\; \texttt{trains} $ \\+
−
$\meta{V}$ & $::=$ &  $\texttt{trains}$ +
−
\end{tabular}}+
−
\end{center}+
−
+
−
\bl{\texttt{Jeff trains geometry students}}+
−
+
−
\end{frame}+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
\begin{frame}[c]+
−
\frametitle{CYK Algorithm}+
−
+
−
\begin{center}+
−
  \begin{tikzpicture}[scale=1,line width=0.8mm]+
−
  \draw (-2,0) -- (2,0);+
−
  \draw (-2,1) -- (2,1);+
−
  \draw (-2,2) -- (1,2);+
−
  \draw (-2,3) -- (0,3);+
−
  \draw (-2,4) -- (-1,4);+
−
  +
−
  \draw (0,0) -- (0, 3);+
−
  \draw (1,0) -- (1, 2);+
−
  \draw (2,0) -- (2, 1);+
−
  \draw (-1,0) -- (-1, 4);+
−
  \draw (-2,0) -- (-2, 4);+
−
  +
−
  \draw (-1.5,-0.5) node {\footnotesize{}\texttt{Jeff}}; +
−
  \draw (-0.5,-1.0) node {\footnotesize{}\texttt{trains}}; +
−
  \draw ( 0.5,-0.5) node {\footnotesize{}\texttt{geometry}}; +
−
  \draw ( 1.5,-1.0) node {\footnotesize{}\texttt{students}}; +
−
  +
−
  \draw (-1.5,0.5) node {$N$}; +
−
  \draw (-0.5,0.5) node {$N,V$}; +
−
  \draw ( 0.5,0.5) node {$N$}; +
−
  \draw ( 1.5,0.5) node {$N$}; +
−
+
−
  \draw (-2.4, 3.5) node {$1$}; +
−
  \draw (-2.4, 2.5) node {$2$}; +
−
  \draw (-2.4, 1.5) node {$3$}; +
−
  \draw (-2.4, 0.5) node {$4$}; +
−
  \end{tikzpicture}+
−
  \end{center}+
−
+
−
\begin{textblock}{5}(10,10)+
−
\small\bl{\begin{tabular}{@ {}lcl@ {}}+
−
$\meta{S}$ & $::=$ &  $\meta{N}\cdot \meta{P}$ \\+
−
$\meta{P}$ & $::=$ &  $\meta{V}\cdot \meta{N}$ \\+
−
$\meta{N}$ & $::=$ &  $\meta{N}\cdot \meta{N}$ \\+
−
            $\meta{N}$ & $::=$ &  $\texttt{students} \;|\; \texttt{Jeff}$\\+
−
            & & $\;|\; \texttt{geometry} \;|\; \texttt{trains} $ \\+
−
$\meta{V}$ & $::=$ &  $\texttt{trains}$ +
−
\end{tabular}}  +
−
\end{textblock}+
−
+
−
\end{frame}+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
\begin{frame}[t]+
−
\frametitle{Chomsky Normal Form}+
−
+
−
A grammar for palindromes over the alphabet~\bl{$\{a,b\}$}:+
−
+
−
\bl{\begin{plstx}[margin=0cm]+
−
: \meta{S} ::=  a\cdot \meta{S}\cdot a | b\cdot \meta{S}\cdot b | a\cdot a | b\cdot b | a | b \\+
−
\end{plstx}}+
−
+
−
\end{frame}+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   +
−
+
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
\begin{frame}[c]+
−
\frametitle{CYK Algorithm}+
−
+
−
+
−
\begin{itemize}+
−
\item fastest possible algorithm for recognition problem+
−
\item runtime is \bl{$O(n^3)$}\bigskip+
−
\item grammars need to be transformed into CNF+
−
\end{itemize}+
−
+
−
\end{frame}+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  +
−
+
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
\begin{frame}[c,fragile]+
−
  \begin{mybox3}{}\it +
−
    "The C++ grammar is ambiguous, context-dependent and potentially+
−
    requires infinite lookahead to resolve some ambiguities."+
−
  \end{mybox3}\bigskip+
−
+
−
+
−
  \hfill from the \href{http://www.computing.surrey.ac.uk/research/dsrg/fog/FogThesis.pdf}{PhD thesis} by Willink (2001)+
−
  +
−
  \small+
−
  \begin{center}+
−
  \begin{lstlisting}[language={},numbers=none]+
−
    int(x), y, *const z;+
−
    int(x), y, new int;+
−
  \end{lstlisting}+
−
  \end{center}+
−
\end{frame}+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
\begin{frame}[c]+
−
\frametitle{Context Sensitive Grammars}+
−
+
−
It is much harder to find out whether a string is parsed+
−
by a context sensitive grammar:+
−
+
−
\bl{\begin{plstx}[margin=2cm]+
−
: \meta{S} ::= b\meta{S}\meta{A}\meta{A} | \epsilon\\+
−
: \meta{A} ::= a\\+
−
: b\meta{A} ::= \meta{A}b\\+
−
\end{plstx}}\pause+
−
+
−
\begin{center}+
−
\bl{$\meta{S} \rightarrow\ldots\rightarrow^? ababaa$}+
−
\end{center}+
−
+
−
\end{frame}+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   +
−
+
−
\begin{frame}[t,fragile]+
−
\begin{mybox3}{}+
−
  For CW2, please include '$\backslash$' as a symbol in strings, because+
−
  the collatz program contains+
−
  \begin{lstlisting}[language=Scala, numbers=none]+
−
  write "\n";\end{lstlisting}  +
−
\end{mybox3}+
−
\end{frame}+
−
+
−
\begin{frame}[t]+
−
\begin{mybox3}{}+
−
  val (r1s, f1s) = simp(r1)\\+
−
  val (r2s, f2s) = simp(r2)\\+
−
  how are the+
−
  first rectification functions f1s and f2s made? could you maybe+
−
  show an example?+
−
\end{mybox3}+
−
\end{frame}+
−
+
−
\begin{frame}<1-24>[c]+
−
\end{frame}+
−
+
−
+
−
\begin{frame}[t]+
−
\begin{minipage}{1.2\textwidth}  +
−
  \begin{mybox3}{}\small+
−
    \textbf{Questions regarding CFL CW1}+
−
+
−
Dear Dr Urban    +
−
    +
−
 Regarding CW1, I am stuck on finding the nullable and derivative rules for some important regexes.\smallskip+
−
+
−
The NOT Regex nullable rule: I am not sure how to approach this, I am inclined to simply put this as the negation of the nullable function on the input regex (e.g !nullable(r)). However I have found instances where negating a nullable does not make it un-nullable. For example the negation of r* can still match regex ab (which is not nullable). So I would like some actual clarification, pointers and help in this area.\smallskip+
−
+
−
The NOT Regex derivation rule: again I am dumbfounded here, I am inclined to think that I should derive the regex and then negate that derivation. But none of this ever works. Please provide some helpful information so I can solve this.+
−
\end{mybox3}+
−
\end{minipage}+
−
\end{frame}+
−
+
−
+
−
+
−
\end{document}+
−
+
−
%%% Local Variables:  +
−
%%% mode: latex+
−
%%% TeX-master: t+
−
%%% End: +
−
+
−