% !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: & Thurdays 15 -- 16\\ 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]\normalsizeparser 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 isno 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 expressionswhether parentheses are matched or unmatched. Also regularexpressions 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\pauseWe 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 theright-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\bigskipA CFG is \alert{\bf left-recursive} if it has a nonterminal \bl{$\meta{E}$} suchthat \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 thathas 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 parsedby 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.\smallskipThe 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.\smallskipThe 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: