56 

    56 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    57 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    57 \begin{frame}[c]

    58 \begin{frame}[c]

    58 %%\frametitle{Test Program}

    59 \frametitle{Parser Combinators}

    59 

    60 

    60 \mbox{}\\[-18mm]\mbox{}

    61 One of the simplest ways to implement a parser, see

    61 

    62 {\small\url{https://vimeo.com/142341803}} (by Haoyi Li)\bigskip

    62 {\lstset{language=While}%%\fontsize{10}{12}\selectfont

    63 

    63 \texttt{\lstinputlisting{../progs/while-tests/loops.while}}}

    64 \begin{itemize}

    64 

    65 \item[$\bullet$] build-in library in Scala

    65 \end{frame}

    66 \item[$\bullet$] fastparse (2) library by Haoyi Li; is part of Ammonite

    66 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

    67 \item[$\bullet$] possible exponential runtime behaviour  

    67 

    68 \end{itemize}

    68 

    69 

    70 \end{frame}

    71 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    72 

    73 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    74 \begin{frame}[c]

    75 \frametitle{Parser Combinators}

    76 

    77 Parser combinators: \bigskip

    78 

    79 \begin{minipage}{1.1\textwidth}

    80 \begin{center}

    81 \mbox{}\hspace{-12mm}\mbox{}$\underbrace{\text{list of tokens}}_{\text{input}}$ \bl{$\Rightarrow$} 

    82 $\underbrace{\text{set of (parsed input, unparsed input)}}_{\text{output}}$

    83 \end{center}

    84 \end{minipage}\bigskip

    85 

    86 \begin{itemize}

    87 \item atomic parsers

    88 \item sequencing

    89 \item alternative

    90 \item semantic action (map-parser)

    91 \end{itemize}

    92 

    93 \end{frame}

    94 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

    95 

    96 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    97 \begin{frame}[c]

    98 

    99 Atomic parsers, for example, number tokens

   100 

   101 \begin{center}

   102 \bl{$\texttt{Num(123)}::rest \;\Rightarrow\; \{(\texttt{Num(123)}, rest)\}$} 

   103 \end{center}\bigskip

   104 

   105 \begin{itemize}

   106 \item you consume one or more token from the\\ 

   107   input (stream)

   108 \item also works for characters and strings

   109 \end{itemize}

   110 \end{frame}

   111 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   112 

   113 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   114 \begin{frame}[c]

   115 

   116 Alternative parser (code \bl{$p\;||\;q$})\bigskip

   117 

   118 \begin{itemize}

   119 \item apply \bl{$p$} and also \bl{$q$}; then combine 

   120   the outputs

   121 \end{itemize}

   122 

   123 \begin{center}

   124 \large \bl{$p(\text{input}) \cup q(\text{input})$}

   125 \end{center}

   126 

   127 \end{frame}

   128 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   129 

   130 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   131 \begin{frame}[c]

   132 

   133 Sequence parser (code \bl{$p\sim q$})\bigskip

   134 

   135 \begin{itemize}

   136 \item apply first \bl{$p$} producing a set of pairs

   137 \item then apply \bl{$q$} to the unparsed part

   138 \item then combine the results:\medskip 

   139 \begin{center}

   140 ((output$_1$, output$_2$), unparsed part)

   141 \end{center}

   142 \end{itemize}

   143 

   144 \begin{center}

   145 \begin{tabular}{l}

   146 \large \bl{$\{((o_1, o_2), u_2) \;|\;$}\\[2mm] 

   147 \large\mbox{}\hspace{15mm} \bl{$(o_1, u_1) \in p(\text{input}) \wedge$}\\[2mm]

   148 \large\mbox{}\hspace{15mm} \bl{$(o_2, u_2) \in q(u_1)\}$}

   149 \end{tabular}

   150 \end{center}

   151 

   152 

   153 \end{frame}

   154 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   155 

   156 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   157 \begin{frame}[c]

   158 

   159 Map-parser (code \bl{$p.map(f)\;$})\bigskip

   160 

   161 \begin{itemize}

   162 \item apply \bl{$p$} producing a set of pairs

   163 \item then apply the function \bl{$f$} to each first component

   164 \end{itemize}

   165 

   166 \begin{center}

   167 \begin{tabular}{l}

   168 \large \bl{$\{(f(o_1), u_1) \;|\; (o_1, u_1) \in p(\text{input})\}$}

   169 \end{tabular}

   170 \end{center}\bigskip\bigskip\pause

   171 

   172 \bl{$f$} is the semantic action (``what to do with the parsed input'')

   173 

   174 \end{frame}

   175 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   176 

   177 

   178 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   179 \mode<presentation>{

   180 \begin{frame}[c]

   181 \frametitle{\begin{tabular}{c}Semantic Actions\end{tabular}}

   182 

   183 Addition

   184 

   185 \begin{center}

   186 \bl{$\meta{T} \sim + \sim \meta{E} \Rightarrow \underbrace{f\,((x,y), z) \Rightarrow x + z}_{\text{semantic action}}$}

   187 \end{center}\pause

   188 

   189 Multiplication

   190 

   191 \begin{center}

   192 \bl{$\meta{F} \sim * \sim \meta{T} \Rightarrow f\,((x,y), z) \Rightarrow x * z$}

   193 \end{center}\pause

   194 

   195 Parenthesis

   196 

   197 \begin{center}

   198 \bl{$\text{(} \sim \meta{E} \sim \text{)} \Rightarrow f\,((x,y), z) \Rightarrow y$}

   199 \end{center}

   200 

   201 \end{frame}}

   202 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   203 

   204 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   205 \begin{frame}[c]

   206 \frametitle{Types of Parsers}

   207 

   208 \begin{itemize}

   209 \item {\bf Sequencing}: if \bl{$p$} returns results of type \bl{$T$}, and \bl{$q$} results of type \bl{$S$},

   210 then \bl{$p \sim q$} returns results of type

   211 

   212 \begin{center}

   213 \bl{$T \times S$}

   214 \end{center}\pause

   215 

   216 \item {\bf Alternative}: if \bl{$p$} returns results of type \bl{$T$} then  \bl{$q$} \alert{must} also have results of type \bl{$T$},

   217 and \bl{$p \;||\; q$} returns results of type

   218 

   219 \begin{center}

   220 \bl{$T$}

   221 \end{center}\pause

   222 

   223 \item {\bf Semantic Action}: if \bl{$p$} returns results of type \bl{$T$} and \bl{$f$} is a function from

   224 \bl{$T$} to \bl{$S$}, then

   225 \bl{$p \Rightarrow f$} returns results of type

   226 

   227 \begin{center}

   228 \bl{$S$}

   229 \end{center}

   230 

   231 \end{itemize}

   232 

   233 \end{frame}

   234 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   235 

   236 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   237 \begin{frame}[c]

   238 \frametitle{Input Types of Parsers}

   239 

   240 \begin{itemize}

   241 \item input: \alert{token list}

   242 \item output: set of (output\_type, \alert{token list})

   243 \end{itemize}\bigskip\pause

   244 

   245 actually it can be any input type as long as it is a kind of

   246 sequence (for example a string)

   247 

   248 \end{frame}

   249 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   250 

   251 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   252 \begin{frame}[c]

   253 \frametitle{Scannerless Parsers}

   254 

   255 \begin{itemize}

   256 \item input: \alert{string}

   257 \item output: set of (output\_type, \alert{string})

   258 \end{itemize}\bigskip\bigskip

   259 

   260 but using lexers is better because whitespaces or comments can be

   261 filtered out; then input is a sequence of tokens

   262 

   263 \end{frame}

   264 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   265 

   266 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   267 \begin{frame}[c]

   268 \frametitle{Successful Parses}

   269 

   270 \begin{itemize}

   271 \item input: string

   272 \item output: \alert{set of} (output\_type, string)

   273 \end{itemize}\bigskip

   274 

   275 a parse is successful whenever the input has been fully

   276 ``consumed'' (that is the second component is empty)

   277 

   278 \end{frame}

   279 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   280 

   281 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   282 \begin{frame}[c]

   283 \frametitle{Abstract Parser Class}

   284 

   285 \small

   286 \lstinputlisting[language=Scala,xleftmargin=1mm]

   287  {../progs/app7.scala}

   288 \end{frame}

   289 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   290 

   291 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   292 \begin{frame}[c]

   293 

   294 \small

   295 \fontsize{10}{12}\selectfont

   296 \lstinputlisting[language=Scala,xleftmargin=1mm]

   297   {../progs/app8.scala}

   298 \end{frame}

   299 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   300 

   301 

   302 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   303 \begin{frame}[c]

   304 \frametitle{Two Grammars}

   305 

   306 Which languages are recognised by the following two grammars?

   307 

   308 \begin{center}

   309 \bl{\begin{tabular}{lcl}

   310 $\meta{S}$ & $\rightarrow$ &  $1 \cdot \meta{S} \cdot \meta{S}$\\

   311         & $|$ & $\epsilon$

   312 \end{tabular}}

   313 \end{center}\bigskip

   314 

   315 \begin{center}

   316 \bl{\begin{tabular}{lcl}

   317 $\meta{U}$ & $\rightarrow$ &  $1 \cdot \meta{U}$\\

   318         & $|$ & $\epsilon$

   319 \end{tabular}}

   320 \end{center}

   321 

   322 \end{frame}

   323 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   324 

   325 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   326 \begin{frame}[t]

   327 \frametitle{Ambiguous Grammars}

   328 

   329 \begin{center}

   330 \begin{tikzpicture}

   331 \begin{axis}[xlabel={\pcode{1}s},ylabel={time in secs},

   332     enlargelimits=false,

   333     xtick={0,100,...,1000},

   334     xmax=1050,

   335     ymax=33,

   336     ytick={0,5,...,30},

   337     scaled ticks=false,

   338     axis lines=left,

   339     width=11cm,

   340     height=7cm, 

   341     legend entries={unambiguous,ambiguous},  

   342     legend pos=north east,

   343     legend cell align=left,

   344     x tick label style={font=\small,/pgf/number format/1000 sep={}}]

   345 \addplot[blue,mark=*, mark options={fill=white}] 

   346   table {s-grammar1.data};

   347 \only<2>{

   348   \addplot[red,mark=triangle*, mark options={fill=white}] 

   349   table {s-grammar2.data};}  

   350 \end{axis}

   351 \end{tikzpicture}

   352 \end{center}

   353 

   354 \end{frame}

   355 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   377 \begin{frame}[c]

    90 \mode<presentation>{

   378 \frametitle{An Interpreter}

    91 \begin{frame}[c]

   379 

    92 \frametitle{\begin{tabular}{c}Aexps\end{tabular}}

   380 \begin{center}

    93 

   381 \bl{\begin{tabular}{l}

    94 \begin{center}

   382 $\{$\\

    95 \bl{\begin{tabular}{@{}lcl@{}}

   383 \;\;$x := 5 \text{;}$\\

    96 $\text{eval}(n)$ & $\dn$ & $n$\\

   384 \;\;$y := x * 3\text{;}$\\

    97 $\text{eval}(a_1 + a_2)$ & $\dn$ & $\text{eval}(a_1) + \text{eval}(a_2)$\\

   385 \;\;$y := x * 4\text{;}$\\

    98 $\text{eval}(a_1 - a_2)$ & $\dn$ & $\text{eval}(a_1) - \text{eval}(a_2)$\\

   386 \;\;$x := u * 3$\\

    99 $\text{eval}(a_1 * a_2)$ & $\dn$ & $\text{eval}(a_1) * \text{eval}(a_2)$\bigskip\\

   387 $\}$

   100 $\text{eval}(x)$ & $\dn$ & $???$\\

   388 \end{tabular}}

   101 \end{tabular}}

   389 \end{center}

   102 \end{center}

   390 

   103 

   391 \begin{itemize}

   104 \end{frame}}

   392 \item the interpreter has to record the value of \bl{$x$} before assigning a value to \bl{$y$}\pause

   105 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   393 \item \bl{\texttt{eval(stmt, env)}}

   106 

   394 \end{itemize}

   395 

   396 \end{frame}

   397 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   419 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   128 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   129 

   130 

   131 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   132 \begin{frame}[c]

   133 \frametitle{An Interpreter (1)}

   134 

   135 \begin{center}

   136 \bl{\begin{tabular}{l}

   137 $\{$\\

   138 \;\;$x := 5 \text{;}$\\

   139 \;\;$y := x * 3\text{;}$\\

   140 \;\;$y := x * 4\text{;}$\\

   141 \;\;$x := u * 3$\\

   142 $\}$

   143 \end{tabular}}

   144 \end{center}

   145 

   146 \begin{itemize}

   147 \item the interpreter has to record the value of \bl{$x$} before assigning a value to \bl{$y$}\pause

   148 \item \bl{\texttt{eval(stmt, env)}}

   149 \end{itemize}

   150 

   151 \end{frame}

   152 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   153 

   492 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   218 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   493 \begin{frame}[t]

   219 % \begin{frame}[t]

   494 \frametitle{%

   220 % \frametitle{%

   495   \begin{tabular}{@ {}c@ {}}

   221 %   \begin{tabular}{@ {}c@ {}}

   496   \\[-3mm]

   222 %   \\[-3mm]

   497   \LARGE Compilers and \\[-2mm] 

   223 %   \LARGE Compilers and \\[-2mm] 

   498   \LARGE Formal Languages\\[3mm] 

   224 %   \LARGE Formal Languages\\[3mm] 

   499   \end{tabular}}

   225 %   \end{tabular}}

   500 

   226 

   501   \normalsize

   227 %   \normalsize

   502   \begin{center}

   228 %   \begin{center}

   503   \begin{tabular}{ll}

   229 %   \begin{tabular}{ll}

   504     Email:  & christian.urban at kcl.ac.uk\\

   230 %     Email:  & christian.urban at kcl.ac.uk\\

   505     %Office Hours: & Thursdays 12 -- 14\\

   231 %     %Office Hours: & Thursdays 12 -- 14\\

   506     %Location: & N7.07 (North Wing, Bush House)\\

   232 %     %Location: & N7.07 (North Wing, Bush House)\\

   507     Slides \& Progs: & KEATS (also homework is there)\\  

   233 %     Slides \& Progs: & KEATS (also homework is there)\\  

   508   \end{tabular}

   234 %   \end{tabular}

   509   \end{center}

   235 %   \end{center}

   510 

   236 

   511   \begin{center}

   237 %   \begin{center}

   512     \begin{tikzpicture}

   238 %     \begin{tikzpicture}

   513       \node[drop shadow,fill=white,inner sep=0pt] 

   239 %       \node[drop shadow,fill=white,inner sep=0pt] 

   514       {\footnotesize\rowcolors{1}{capri!10}{white}

   240 %       {\footnotesize\rowcolors{1}{capri!10}{white}

   515         \begin{tabular}{|p{4.8cm}|p{4.8cm}|}\hline

   241 %         \begin{tabular}{|p{4.8cm}|p{4.8cm}|}\hline

   516           1 Introduction, Languages          & \cellcolor{blue!50} 6 While-Language \\

   242 %           1 Introduction, Languages          & \cellcolor{blue!50} 6 While-Language \\

   517           2 Regular Expressions, Derivatives & 7 Compilation, JVM \\

   243 %           2 Regular Expressions, Derivatives & 7 Compilation, JVM \\

   518           3 Automata, Regular Languages      & 8 Compiling Functional Languages \\

   244 %           3 Automata, Regular Languages      & 8 Compiling Functional Languages \\

   519           4 Lexing, Tokenising               & 9 Optimisations \\

   245 %           4 Lexing, Tokenising               & 9 Optimisations \\

   520           5 Grammars, Parsing                & 10 LLVM \\ \hline

   246 %           5 Grammars, Parsing                & 10 LLVM \\ \hline

   521         \end{tabular}%

   247 %         \end{tabular}%

   522       };

   248 %       };

   523     \end{tikzpicture}

   249 %     \end{tikzpicture}

   524   \end{center}

   250 %   \end{center}

   526 \end{frame}

   252 % \end{frame}

   527 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     

   253 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%