6 \usepackage{../grammar}

     6 

     7 

     8 \hfuzz=220pt 

     9 

    10 \pgfplotsset{compat=1.11}

    11 

    12 \newcommand{\bl}[1]{\textcolor{blue}{#1}}  

    44 \frametitle{Regular Languages}

    38 

    45 

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

    46 While regular expressions are very useful for lexing, there is

    40 

    47 no regular expression that can recognise the language

    41 {\lstset{language=Scala}\fontsize{10}{12}\selectfont

    48 \bl{$a^nb^n$}.\bigskip

    42 \texttt{\lstinputlisting[xleftmargin=0mm]{../progs/pow.scala}}}

    49 

    43 

    50 \begin{center}

    44 \end{frame}

    51 \bl{$(((()()))())$} \;\;vs.\;\; \bl{$(((()()))()))$}

    45 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

    52 \end{center}\bigskip\bigskip

    46 

    53 

    47 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    48 \begin{frame}[c]

    55 \noindent So we cannot find out with regular expressions

    50 \mbox{}\\[5mm]

    56 whether parentheses are matched or unmatched.

    51 %\begin{textblock}{10}(3,5)

    52 \begin{tikzpicture}[scale=1.5,

    53                     node distance=1cm,

    54                     every node/.style={minimum size=7mm}]

    55 \node (r1)  {\bl{$r_1$}};

    56 \node (r2) [right=of r1] {\bl{$r_2$}};

    57 \draw[->,line width=1mm]  (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};

    58 \node (r3) [right=of r2] {\bl{$r_3$}};

    59 \draw[->,line width=1mm]  (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};

    60 \node (r4) [right=of r3] {\bl{$r_4$}};

    61 \draw[->,line width=1mm]  (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};

    62 \draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};

    63 \node (v4) [below=of r4] {\bl{$v_4$}};

    64 \draw[->,line width=1mm]  (r4) -- (v4);

    65 \node (v3) [left=of v4] {\bl{$v_3$}};

    66 \draw[->,line width=1mm]  (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};

    67 \node (v2) [left=of v3] {\bl{$v_2$}};

    68 \draw[->,line width=1mm]  (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};

    69 \node (v1) [left=of v2] {\bl{$v_1$}};

    70 \draw[->,line width=1mm]  (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};

    71 \draw[->,line width=0.5mm]  (r3) -- (v3);

    72 \draw[->,line width=0.5mm]  (r2) -- (v2);

    73 \draw[->,line width=0.5mm]  (r1) -- (v1);

    74 \draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};

    75 \end{tikzpicture}

    76 %\end{textblock}

    77 

    78 \begin{center}

    79 \begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}

    80   \\[-10mm]

    81   \bl{$inj\,(c)\,c\,Empty$} & \bl{$\dn$}  & \bl{$Char\,c$}\\

    82   \bl{$inj\,(r_1 + r_2)\,c\,Left(v)$} & \bl{$\dn$}  & \bl{$Left(inj\,r_1\,c\,v)$}\\

    83   \bl{$inj\,(r_1 + r_2)\,c\,Right(v)$} & \bl{$\dn$}  & \bl{$Right(inj\,r_2\,c\,v)$}\\

    84   \bl{$inj\,(r_1 \cdot r_2)\,c\,Seq(v_1,v_2)$} & \bl{$\dn$}  & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\

    85   \bl{$inj\,(r_1 \cdot r_2)\,c\,Left(Seq(v_1,v_2))$} & \bl{$\dn$}  & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\

    86   \bl{$inj\,(r_1 \cdot r_2)\,c\,Right(v)$} & \bl{$\dn$}  & \bl{$Seq(mkeps(r_1),inj\,r_2\,c\,v)$}\\

    87   \bl{$inj\,(r^*)\,c\,Seq(v,vs)$} & \bl{$\dn$}  & \bl{$inj\,r\,c\,v\,::\,vs$}\\

    88 \end{tabular}

    89 \end{center}

    61 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    94 

    62 \begin{frame}[c]

    95 

    63 \frametitle{Hierarchy of Languages}

    96 

    97 \newcommand{\qq}{\mbox{\texttt{"}}}

    98 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    99 \begin{frame}[c]

   100 \frametitle{CFGs}

   101 

   102 A \alert{context-free} grammar (CFG) \bl{$G$} consists of:

   103 

   104 \begin{itemize}

   105 \item a finite set of nonterminal symbols (upper case)

   106 \item a finite terminal symbols or tokens (lower case)

   107 \item a start symbol (which must be a nonterminal)

   108 \item a set of rules

   109 \begin{center}

   110 \bl{$A \rightarrow \text{rhs}_1 | \text{rhs}_2 | \ldots$}

   111 \end{center}

   112 

   113 where \bl{rhs} are sequences involving terminals and nonterminals (can also be empty).\medskip\pause

   114 

   115 \end{itemize}

   116 

   117 \end{frame}

   118 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   119 

   120 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   121 \mode<presentation>{

   122 \begin{frame}[c]

   123 \frametitle{\begin{tabular}{c}Hierarchy of Languages\end{tabular}}

   124 

   125 Recall that languages are sets of strings.

    67 [rect/.style={draw=black!50, 

   129 [rect/.style={draw=black!50, top color=white,bottom color=black!20, rectangle, very thick, rounded corners}]

    68               top color=white,

    69               bottom color=black!20, 

    70               rectangle, 

    71               very thick, 

    72               rounded corners}]

    83 \end{frame}

   140 \end{frame}}

    84 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   141 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

    85 

   142 

    86 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   143 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    87 \begin{frame}[c]

   144 \mode<presentation>{

    88 \frametitle{Grammars}

   145 \begin{frame}[c]

    89 

   146 \frametitle{\begin{tabular}{c}Arithmetic Expressions\end{tabular}}

    90 A (context-free) grammar \bl{$G$} consists of

   147 

   148 A grammar for arithmetic expressions and numbers:

   149 

   150 \begin{center}

   151 \bl{\begin{tabular}{lcl}

   152 $E$ & $\rightarrow$ &  $E \cdot + \cdot E \;|\;E \cdot * \cdot E \;|\;( \cdot E \cdot ) \;|\;N$ \\

   153 $N$ & $\rightarrow$ & $N \cdot N \;|\; 0 \;|\; 1 \;|\: \ldots \;|\; 9$ 

   154 \end{tabular}}

   155 \end{center}

   156 

   157 Unfortunately it is left-recursive (and ambiguous).\medskip\\

   158 A problem for \alert{recursive descent parsers} (e.g.~parser combinators).

   159 \bigskip\pause

   160 

   161 \end{frame}}

   162 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   163 

   164 

   165 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   166 \mode<presentation>{

   167 \begin{frame}[t]

   168 \frametitle{\begin{tabular}{c}Numbers\end{tabular}}

   169 

   170 

   171 

   172 \begin{center}

   173 \bl{\begin{tabular}{lcl}

   174 $N$ & $\rightarrow$ &  $N \cdot N \;|\; 0 \;|\; 1 \;|\; \ldots \;|\; 9$\\

   175 \end{tabular}}

   176 \end{center}

   177 

   178 A non-left-recursive, non-ambiguous grammar for numbers:

   179 

   180 \begin{center}

   181 \bl{\begin{tabular}{lcl}

   182 $N$ & $\rightarrow$ &  $0 \cdot N \;|\;1 \cdot N \;|\;\ldots\;|\; 0 \;|\; 1 \;|\; \ldots \;|\; 9$\\

   183 \end{tabular}}

   184 \end{center}

   185 

   186 

   187 \end{frame}}

   188 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   189 

   190 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   191 \mode<presentation>{

   192 \begin{frame}[c]

   193 \frametitle{\begin{tabular}{c}Operator Precedences\end{tabular}}

   194 

   195 

   196 To disambiguate

   197 

   198 \begin{center}

   199 \bl{\begin{tabular}{lcl}

   200 $E$ & $\rightarrow$ &  $E \cdot + \cdot E \;|\;E \cdot * \cdot E \;|\;( \cdot E \cdot ) \;|\;N$ \\

   201 \end{tabular}}

   202 \end{center}

   203 

   204 Decide on how many precedence levels, say\medskip\\

   205 \hspace{5mm}highest for \bl{$()$}, medium for \bl{*}, lowest for \bl{+}

   206 

   207 \begin{center}

   208 \bl{\begin{tabular}{lcl}

   209 $E_{low}$ & $\rightarrow$ & $E_{med} \cdot + \cdot E_{low} \;|\; E_{med}$ \\

   210 $E_{med}$ & $\rightarrow$ & $E_{hi} \cdot * \cdot E_{med} \;|\; E_{hi}$\\

   211 $E_{hi}$ & $\rightarrow$ &  $( \cdot E_{low} \cdot ) \;|\;N$ \\

   212 \end{tabular}}

   213 \end{center}\pause

   214 

   215 \small What happens with \bl{$1 + 3  + 4$}?

   216 \end{frame}}

   217 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   218 

   219 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   220 \mode<presentation>{

   221 \begin{frame}[c]

   222 \frametitle{\begin{tabular}{c}Removing Left-Recursion\end{tabular}}

   223 

   224 The rule for numbers is directly left-recursive:

   225 

   226 \begin{center}

   227 \bl{\begin{tabular}{lcl}

   228 $N$ & $\rightarrow$ & $N \cdot N \;|\; 0 \;|\; 1\;\;\;\;(\ldots)$ 

   229 \end{tabular}}

   230 \end{center}

   231 

   232 Translate

   233 

   234 \begin{center}

   235 \begin{tabular}{ccc}

   236 \bl{\begin{tabular}{lcl}

   237 $N$ & $\rightarrow$ & $N \cdot \alpha$\\

   238  &  $\;|\;$ & $\beta$\\

   239  \\ 

   240 \end{tabular}} 

   241 & {\Large$\Rightarrow$} &

   242 \bl{\begin{tabular}{lcl}

   243 $N$ & $\rightarrow$ & $\beta \cdot N'$\\

   244 $N'$ & $\rightarrow$ & $\alpha \cdot N'$\\

   245  &  $\;|\;$ & $\epsilon$ 

   246 \end{tabular}}

   247 \end{tabular}

   248 \end{center}\pause

   249 

   250 Which means

   251 

   252 \begin{center}

   253 \bl{\begin{tabular}{lcl}

   254 $N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1 \cdot N'$\\

   255 $N'$ & $\rightarrow$ & $N \cdot N' \;|\; \epsilon$\\

   256 \end{tabular}}

   257 \end{center}

   258 

   259 

   260 \end{frame}}

   261 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   262 

   263 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   264 \mode<presentation>{

   265 \begin{frame}[c]

   266 \frametitle{\begin{tabular}{c}Chomsky Normal Form\end{tabular}}

   267 

   268 All rules must be of the form

   269 

   270 \begin{center}

   271 \bl{$A \rightarrow a$}

   272 \end{center}

   273 

   274 or

   275 

   276 \begin{center}

   277 \bl{$A \rightarrow B\cdot C$}

   278 \end{center}

   279 

   280 No rule can contain \bl{$\epsilon$}.

   281 

   282 \end{frame}}

   283 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   284 

   285 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   286 \mode<presentation>{

   287 \begin{frame}[c]

   288 \frametitle{\begin{tabular}{c}$\epsilon$-Removal\end{tabular}}

   289 

   290 \begin{enumerate}

   291 \item If \bl{$A\rightarrow \alpha \cdot B \cdot \beta$} and \bl{$B \rightarrow \epsilon$} are in the grammar,

   292 then add \bl{$A\rightarrow \alpha \cdot \beta$} (iterate if necessary).

   293 \item Throw out all \bl{$B \rightarrow \epsilon$}.

   294 \end{enumerate}

   295 

   296 \small

   297 \begin{center}

   298 \begin{tabular}{ccc}

   299 \bl{\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}

   300 $N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1\cdot N'$\\

   301 $N'$ & $\rightarrow$ & $N \cdot N'\;|\;\epsilon$\\

   302 \\ 

   303 \\

   304 \\

   305 \\

   306 \\

   307 \end{tabular}} &

   308 \bl{\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}

   309 \\

   310 $N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1\cdot N'\;|\;0\;|\;1$\\

   311 $N'$ & $\rightarrow$ & $N \cdot N'\;|\;N\;|\;\epsilon$\\

   312 \\

   313 $N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1\cdot N'\;|\;0\;|\;1$\\

   314 $N'$ & $\rightarrow$ & $N \cdot N'\;|\;N$\\

   315 \end{tabular}}

   316 \end{tabular}

   317 \end{center}

   318 

   319 \pause\normalsize

   320 \begin{center}

   321 \bl{\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}

   322 $N$ & $\rightarrow$ & $0 \cdot N\;|\; 1\cdot N\;|\;0\;|\;1$\\

   323 \end{tabular}}

   324 

   325 \end{center}

   326 \end{frame}}

   327 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   328 

   329 

   330 

   331 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   332 \mode<presentation>{

   333 \begin{frame}[c]

   334 \frametitle{\begin{tabular}{c}CYK Algorithm\end{tabular}}

   335 

   336 If grammar is in Chomsky normalform \ldots

   337 

   338 \begin{center}

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

   340 $S$ & $\rightarrow$ &  $N\cdot P$ \\

   341 $P$ & $\rightarrow$ &  $V\cdot N$ \\

   342 $N$ & $\rightarrow$ &  $N\cdot N$ \\

   343 $N$ & $\rightarrow$ &  $\texttt{students} \;|\; \texttt{Jeff} \;|\; \texttt{geometry} \;|\; \texttt{trains} $ \\

   344 $V$ & $\rightarrow$ &  $\texttt{trains}$ 

   345 \end{tabular}}

   346 \end{center}

   347 

   348 \bl{\texttt{Jeff trains geometry students}}

   349 

   350 \end{frame}}

   351 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   352 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   353 \mode<presentation>{

   354 \begin{frame}[c]

   355 \frametitle{\begin{tabular}{c}CYK Algorithm\end{tabular}}

   356 

    93 \item a finite set of nonterminal symbols (upper case)

   359 \item fastest possible algorithm for recognition problem

    94 \item a finite terminal symbols or tokens (lower case)

   360 \item runtime is \bl{$O(n^3)$}\bigskip

    95 \item a start symbol (which must be a nonterminal)

   361 \item grammars need to be transferred into CNF

    96 \item a set of rules

    97 \begin{center}

    98 \bl{$A \rightarrow \text{rhs}$}

    99 \end{center}

   100 

   101 where \bl{rhs} are sequences involving terminals and nonterminals,

   102 including the empty sequence \bl{$\epsilon$}.\medskip\pause

   103 

   104 We also allow rules

   105 \begin{center}

   106 \bl{$A \rightarrow \text{rhs}_1 | \text{rhs}_2 | \ldots$}

   107 \end{center}

   532 \begin{frame}[c]

   368 \mode<presentation>{

   533 \frametitle{Input Types of Parsers}

   369 \begin{frame}[c]

   534 

   370 

   535 \begin{itemize}

   371 \begin{center}

   536 \item input: \alert{token list}

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

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

   373 \textit{Stmt} & $\rightarrow$ &  $\texttt{skip}$\\

   538 \end{itemize}\bigskip\pause

   374               & $|$ & \textit{Id}\;\texttt{:=}\;\textit{AExp}\\

   539 

   375               & $|$ & \texttt{if}\; \textit{BExp} \;\texttt{then}\; \textit{Block} \;\texttt{else}\; \textit{Block}\\

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

   376               & $|$ & \texttt{while}\; \textit{BExp} \;\texttt{do}\; \textit{Block}\\

   541 sequence (for example a string)

   377               & $|$ & \texttt{read}\;\textit{Id}\\

   542 

   378               & $|$ & \texttt{write}\;\textit{Id}\\

   543 \end{frame}

   379               & $|$ & \texttt{write}\;\textit{String}\medskip\\

   544 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   380 \textit{Stmts} & $\rightarrow$ &  \textit{Stmt} \;\texttt{;}\; \textit{Stmts}\\

   545 

   381               & $|$ & \textit{Stmt}\medskip\\

   546 

   382 \textit{Block} & $\rightarrow$ &  \texttt{\{}\,\textit{Stmts}\,\texttt{\}}\\

   547 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   383                 & $|$ & \textit{Stmt}\medskip\\

   548 \begin{frame}[c]

   384 \textit{AExp} & $\rightarrow$ & \ldots\\

   549 \frametitle{Scannerless Parsers}

   385 \textit{BExp} & $\rightarrow$ & \ldots\\

   550 

   386 \end{tabular}}

   551 \begin{itemize}

   387 \end{center}

   552 \item input: \alert{string}

   388 \end{frame}}

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

   389 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   554 \end{itemize}\bigskip

   390 

   555 

   391 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   556 but lexers are better when whitespaces or comments need to be

   392 \mode<presentation>{

   557 filtered out; then input is a sequence of tokens

   393 \begin{frame}[c]

   558 

   394 

   559 \end{frame}

   395 \mbox{\lstinputlisting[language=while]{../progs/fib.while}}

   560 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   396 

   561 

   397 \end{frame}}

   562 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   398 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   563 \begin{frame}[c]

   399 

   564 \frametitle{Successful Parses}

   400 

   565 

   401 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   566 \begin{itemize}

   402 \mode<presentation>{

   567 \item input: string

   403 \begin{frame}[c]

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

   404 \frametitle{\begin{tabular}{c}An Interpreter\end{tabular}}

   569 \end{itemize}\bigskip

   570 

   571 a parse is successful whenever the input has been fully

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

   573 

   574 \end{frame}

   575 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   576 

   577 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   578 \begin{frame}[c]

   579 \frametitle{Abstract Parser Class}

   580 

   581 \small

   582 \lstinputlisting[language=Scala,xleftmargin=1mm]{../progs/app7.scala}

   583 \end{frame}

   584 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   585 

   586 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   587 \begin{frame}[c]

   588 

   589 \small

   590 \fontsize{10}{12}\selectfont

   591 \lstinputlisting[language=Scala,xleftmargin=1mm]{../progs/app8.scala}

   592 \end{frame}

   593 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   594 

   595 

   596 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   597 \begin{frame}[c]

   598 \frametitle{Two Grammars}

   599 

   600 Which languages are recognised by the following two grammars?

   601 

   602 \begin{center}

   603 \bl{\begin{tabular}{lcl}

   604 $S$ & $\rightarrow$ &  $1 \cdot S \cdot S$\\

   605         & $|$ & $\epsilon$

   606 \end{tabular}}

   607 \end{center}\bigskip

   608 

   609 \begin{center}

   610 \bl{\begin{tabular}{lcl}

   611 $U$ & $\rightarrow$ &  $1 \cdot U$\\

   612         & $|$ & $\epsilon$

   613 \end{tabular}}

   614 \end{center}

   615 

   616 \end{frame}

   617 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   618 

   619 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   620 \begin{frame}[t]

   621 \frametitle{Ambiguous Grammars}

   622 

   623 \begin{center}

   624 \begin{tikzpicture}

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

   626     enlargelimits=false,

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

   628     xmax=1050,

   629     ymax=33,

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

   631     scaled ticks=false,

   632     axis lines=left,

   633     width=11cm,

   634     height=7cm, 

   635     legend entries={unambiguous,ambiguous},  

   636     legend pos=north east,

   637     legend cell align=left,

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

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

   640   table {s-grammar1.data};

   641 \only<2>{

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

   643   table {s-grammar2.data};}  

   644 \end{axis}

   645 \end{tikzpicture}

   646 \end{center}

   647 

   648 \end{frame}

   649 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   650 

   651 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   652 \begin{frame}

   653 \frametitle{While-Language}

   654 \mbox{}\\[-23mm]\mbox{}

   655 

   656 \bl{\begin{plstx}[rhs style=,one per line]

   657 : \meta{Stmt} ::= skip

   658          | \meta{Id} := \meta{AExp}

   659          | if \meta{BExp} then \meta{Block} else \meta{Block}

   660          | while \meta{BExp} do \meta{Block}\\

   661 : \meta{Stmts} ::= \meta{Stmt} ; \meta{Stmts}

   662           | \meta{Stmt}\\

   663 : \meta{Block} ::= \{ \meta{Stmts} \}

   664           | \meta{Stmt}\\

   665 : \meta{AExp} ::= \ldots\\

   666 : \meta{BExp} ::= \ldots\\

   667 \end{plstx}}

   668 

   669 \end{frame}

   670 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   671 

   672 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   673 \begin{frame}[c]

   674 \frametitle{An Interpreter}

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

   419 \item \bl{\text{eval}(stmt, env)}