234 

   235 

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

   237 \mode<presentation>{

   238 \begin{frame}[c]

   239 \frametitle{\begin{tabular}{c}A CFG Derivation\end{tabular}}

   240 

   241 \begin{enumerate}

   242 \item Begin with a string containing only the start symbol, say \bl{$S$}\bigskip

   243 \item Replace any nonterminal \bl{$X$} in the string by the

   244 right-hand side of some production \bl{$X \rightarrow \text{rhs}$}\bigskip

   245 \item Repeat 2 until there are no nonterminals

   246 \end{enumerate}

   247 

   248 \begin{center}

   249 \bl{$S \rightarrow \ldots \rightarrow \ldots  \rightarrow \ldots  \rightarrow \ldots $}

   250 \end{center}

   251 

   252 \end{frame}}

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

   254   

   255 

   256 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   257 \mode<presentation>{

   258 \begin{frame}[c]

   259 \frametitle{\begin{tabular}{c}Example Derivation\end{tabular}}

   260 

   261 \begin{center}

   262 \bl{\begin{tabular}{lcl}

   263 $S$ & $\rightarrow$ &  $\epsilon \;|\; a\cdot S\cdot a \;|\;b\cdot S\cdot b$ \\

   264 \end{tabular}}

   265 \end{center}\bigskip

   266 

   267 

   268 \begin{center}

   269 \begin{tabular}{lcl}

   270 \bl{$S$} & \bl{$\rightarrow$} & \bl{$aSa$}\\

   271               & \bl{$\rightarrow$} & \bl{$abSba$}\\

   272               & \bl{$\rightarrow$} & \bl{$abaSaba$}\\

   273               & \bl{$\rightarrow$} & \bl{$abaaba$}\\

   274 

   275  

   276 \end{tabular}

   277 \end{center}

   278 

   279 \end{frame}}

   280 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   281 

   282 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   283 \mode<presentation>{

   284 \begin{frame}[c]

   285 \frametitle{\begin{tabular}{c}Example Derivation\end{tabular}}

   286 

   287 \begin{center}

   288 \bl{\begin{tabular}{lcl}

   289 $E$ & $\rightarrow$ &  $num\_token$ \\

   290 $E$ & $\rightarrow$ &  $E \cdot + \cdot E$ \\

   291 $E$ & $\rightarrow$ &  $E \cdot - \cdot E$ \\

   292 $E$ & $\rightarrow$ &  $E \cdot * \cdot E$ \\

   293 $E$ & $\rightarrow$ &  $( \cdot E \cdot )$ 

   294 \end{tabular}}

   295 \end{center}\bigskip

   296 

   297 

   298 \begin{center}

   299 \begin{tabular}{@{}c@{}c@{}}

   300 \begin{tabular}{l@{\hspace{1mm}}l@{\hspace{1mm}}l}

   301 \bl{$E$} & \bl{$\rightarrow$} & \bl{$E*E$}\\

   302               & \bl{$\rightarrow$} & \bl{$E+E*E$}\\

   303               & \bl{$\rightarrow$} & \bl{$E+E*E+E$}\\

   304               & \bl{$\rightarrow^+$} & \bl{$1+2*3+4$}\\

   305 \end{tabular} &\pause

   306 \begin{tabular}{l@{\hspace{1mm}}l@{\hspace{1mm}}l}

   307 \bl{$E$} & \bl{$\rightarrow$} & \bl{$E+E$}\\

   308               & \bl{$\rightarrow$} & \bl{$E+E+E$}\\

   309               & \bl{$\rightarrow$} & \bl{$E+E*E+E$}\\

   310               & \bl{$\rightarrow^+$} & \bl{$1+2*3+4$}\\

   311 \end{tabular}

   312 \end{tabular}

   313 \end{center}

   314 

   315 \end{frame}}

   316 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   317 

   318 

   319 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   320 \mode<presentation>{

   321 \begin{frame}[c]

   322 \frametitle{\begin{tabular}{c}Language of a CFG\end{tabular}}

   323 

   324 Let \bl{$G$} be a context-free grammar with start symbol \bl{$S$}. 

   325 Then the language \bl{$L(G)$} is:

   326 

   327 \begin{center}

   328 \bl{$\{c_1\ldots c_n \;|\; \forall i.\; c_i \in T \wedge S \rightarrow^* c_1\ldots c_n \}$}

   329 \end{center}\pause

   330 

   331 \begin{itemize}

   332 \item Terminals, because there are no rules for replacing them.

   333 \item Once generated, terminals are ``permanent''.

   334 \item Terminals ought to be tokens of the language\\

   335 (but can also be strings).

   336 \end{itemize}

   337 

   338 \end{frame}}

   339 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   400 \end{center}\pause\bigskip

   401 

   402 A CFG is \alert{left-recursive} if it has a nonterminal \bl{$E$} such

   403 that \bl{$E \rightarrow^+ E\cdot \ldots$}

   404 

   405 \end{frame}}

   406 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   407 

   408 

   409 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   410 \mode<presentation>{

   411 \begin{frame}[c]

   412 \frametitle{\begin{tabular}{c}Ambiguous Grammars\end{tabular}}

   413 

   414 A grammar is \alert{ambiguous} if there is a string that has at least two different parse trees.

   415 

   416 

   417 \begin{center}

   418 \bl{\begin{tabular}{lcl}

   419 $E$ & $\rightarrow$ &  $num\_token$ \\

   420 $E$ & $\rightarrow$ &  $E \cdot + \cdot E$ \\

   421 $E$ & $\rightarrow$ &  $E \cdot - \cdot E$ \\

   422 $E$ & $\rightarrow$ &  $E \cdot * \cdot E$ \\

   423 $E$ & $\rightarrow$ &  $( \cdot E \cdot )$ 

   424 \end{tabular}}

   428 

   429 \end{frame}}

   430 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   431 

   432 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   433 \mode<presentation>{

   434 \begin{frame}[c]

   435 \frametitle{\begin{tabular}{c}Dangling Else\end{tabular}}

   436 

   437 Another ambiguous grammar:\bigskip

   438 

   439 \begin{center}

   440 \bl{\begin{tabular}{lcl}

   441 $E$ & $\rightarrow$ &  if $E$ then $E$\\

   442  & $|$ &  if $E$ then $E$ else $E$ \\

   443  & $|$ &  \ldots

   444 \end{tabular}}

   445 \end{center}\bigskip

   446 

   447 \bl{\texttt{if a then if x then y else c}}

   448 

   449 \end{frame}}

   450 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   451 

   452 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   453 \mode<presentation>{

   454 \begin{frame}[c]

   455 \frametitle{\begin{tabular}{c}Parser Combinators\end{tabular}}

   456 

   457 Parser combinators: \bigskip

   458 

   459 \begin{minipage}{1.1\textwidth}

   460 \begin{center}

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

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

   463 \end{center}

   464 \end{minipage}\bigskip

   465 

   466 \begin{itemize}

   467 \item sequencing

   468 \item alternative

   469 \item semantic action

   470 \end{itemize}

   471 

   472 \end{frame}}

   473 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   474 

   475 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   476 \mode<presentation>{

   477 \begin{frame}[c]

   478 

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

   480 

   481 \begin{itemize}

   482 \item apply \bl{$p$} and also \bl{$q$}; then combine the outputs

   483 \end{itemize}

   484 

   485 \begin{center}

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

   487 \end{center}

   488 

   489 

   490 \end{frame}}

   491 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   492 

   493 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   494 \mode<presentation>{

   495 \begin{frame}[c]

   496 

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

   498 

   499 \begin{itemize}

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

   501 \item then apply \bl{$q$} to the unparsed parts

   502 \item then combine the results:\\ \mbox{}\;\;((output$_1$, output$_2$), unparsed part)

   503 \end{itemize}

   504 

   505 \begin{center}

   506 \begin{tabular}{l}

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

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

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

   510 \end{tabular}

   511 \end{center}

   512 

   513 

   514 \end{frame}}

   515 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   516 

   517 

   518 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   519 \mode<presentation>{

   520 \begin{frame}[c]

   521 

   522 Function parser (code \bl{$p \Rightarrow f$})\bigskip

   523 

   524 \begin{itemize}

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

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

   527 \end{itemize}

   528 

   529 \begin{center}

   530 \begin{tabular}{l}

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

   532 \end{tabular}

   533 \end{center}\bigskip\bigskip\pause

   534 

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

   536 

   537 \end{frame}}

   538 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   539 

   540 

   541 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   542 \mode<presentation>{

   543 \begin{frame}[c]

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

   545 

   546 Addition

   547 

   548 \begin{center}

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

   550 \end{center}\pause

   551 

   552 Multiplication

   553 

   554 \begin{center}

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

   556 \end{center}\pause

   557 

   558 Parenthesis

   559 

   560 \begin{center}

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

   562 \end{center}

   563 

   564 \end{frame}}

   565 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   566 

   567 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   568 \mode<presentation>{

   569 \begin{frame}[c]

   570 \frametitle{\begin{tabular}{c}Types of Parsers\end{tabular}}

   571 

   572 \begin{itemize}

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

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

   575 

   576 \begin{center}

   577 \bl{$T \times S$}

   578 \end{center}\pause

   579 

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

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

   582 

   583 \begin{center}

   584 \bl{$T$}

   585 \end{center}\pause

   586 

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

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

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

   590 

   591 \begin{center}

   592 \bl{$S$}

   593 \end{center}

   594 

   595 \end{itemize}

   596 

   597 \end{frame}}

   598 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   599 

   600 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   601 \mode<presentation>{

   602 \begin{frame}[c]

   603 \frametitle{\begin{tabular}{c}Input Types of Parsers\end{tabular}}

   604 

   605 \begin{itemize}

   606 \item input: \alert{string}

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

   608 \end{itemize}\bigskip\pause

   609 

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

   611 (for example a string)

   612 

   613 \end{frame}}

   614 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   615 

   616 

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

   618 \mode<presentation>{

   619 \begin{frame}[c]

   620 \frametitle{\begin{tabular}{c}Scannerless Parsers\end{tabular}}

   621 

   622 \begin{itemize}

   623 \item input: \alert{string}

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

   625 \end{itemize}\bigskip

   626 

   627 but lexers are better when whitespaces or comments need to be filtered out;

   628 then input is a sequence of tokens

   629 

   630 \end{frame}}

   631 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   632 

   633 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   634 \mode<presentation>{

   635 \begin{frame}[c]

   636 \frametitle{\begin{tabular}{c}Successful Parses\end{tabular}}

   637 

   638 \begin{itemize}

   639 \item input: string

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

   641 \end{itemize}\bigskip

   642 

   643 a parse is successful whenever the input has been

   644 fully ``consumed'' (that is the second component is empty)

   645 

   646 

   647 \end{frame}}

   648 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   649 

   650 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   651 \mode<presentation>{

   652 \begin{frame}[c]

   653 \frametitle{Abstract Parsers}

   654 

   655 \mbox{\lstset{language=Scala}\fontsize{10}{12}\selectfont

   656 \texttt{\lstinputlisting{../progs/app7.scala}}}

   657 \end{frame}}

   658 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   659 

   660 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   661 \mode<presentation>{

   662 \begin{frame}[c]

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

   664 \texttt{\lstinputlisting{../progs/app8.scala}}}

   665 \end{frame}}

   666 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   667 

   668 

   669 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   670 \mode<presentation>{

   671 \begin{frame}[c]

   672 \frametitle{\begin{tabular}{c}Two Grammars\end{tabular}}

   673 

   674 Which languages are recognised by the following two grammars?

   675 

   676 \begin{center}

   677 \bl{\begin{tabular}{lcl}

   678 $S$ & $\rightarrow$ &  $1 \cdot S \cdot S$\\

   679         & $|$ & $\epsilon$

   680 \end{tabular}}

   681 \end{center}\bigskip

   682 

   683 \begin{center}

   684 \bl{\begin{tabular}{lcl}

   685 $U$ & $\rightarrow$ &  $1 \cdot U$\\

   686         & $|$ & $\epsilon$

   687 \end{tabular}}

   688 \end{center}

   689 

   690 \end{frame}}

   691 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   692 

   693 

   694 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   695 \mode<presentation>{

   696 \begin{frame}[t]

   697 \frametitle{\begin{tabular}{c}Ambiguous Grammars\end{tabular}}

   698 

   699 \mbox{}\\[-25mm]\mbox{}

   700 

   701 \begin{center}

   702 \begin{tikzpicture}[y=.2cm, x=.009cm]

   703  	%axis

   704 	\draw (0,0) -- coordinate (x axis mid) (1000,0);

   705     	\draw (0,0) -- coordinate (y axis mid) (0,30);

   706     	%ticks

   707     	\foreach \x in {0, 20, 100, 200,...,1000}

   708      		\draw (\x,1pt) -- (\x,-3pt)

   709 			node[anchor=north] {\small \x};

   710     	\foreach \y in {0,5,...,30}

   711      		\draw (1pt,\y) -- (-3pt,\y) 

   712      			node[anchor=east] {\small\y}; 

   713 	%labels      

   714 	\node[below=0.6cm] at (x axis mid) {\bl{1}s};

   715 	\node[rotate=90, left=1.2cm] at (y axis mid) {secs};

   716 

   717 	%plots

   718 	\draw[color=blue] plot[mark=*, mark options={fill=white}] 

   719 		file {s-grammar1.data};

   720          \only<2->{\draw[color=red] plot[mark=triangle*, mark options={fill=white} ] 

   721                   file {s-grammar2.data};}

   722 	%legend

   723 	\begin{scope}[shift={(400,20)}] 

   724 	\draw[color=blue] (0,0) -- 

   725 		plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) 

   726 		node[right]{\small unambiguous};

   727 	\only<2->{\draw[yshift=\baselineskip, color=red] (0,0) -- 

   728                 plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0)

   729                 node[right]{\small ambiguous};}  

   730 	\end{scope}

   731 \end{tikzpicture}

   732 \end{center}

   733 

   734 \end{frame}}

   735 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   736 

   737 

   738 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   739 \mode<presentation>{

   740 \begin{frame}[c]

   741 \frametitle{\begin{tabular}{c}While-Language\end{tabular}}

   742 

   743 

   744 \begin{center}

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

   746 $Stmt$ & $\rightarrow$ &  $\text{skip}$\\

   747               & $|$ & $Id := AExp$\\

   748               & $|$ & $\text{if}\; B\!Exp \;\text{then}\; Block \;\text{else}\; Block$\\

   749               & $|$ & $\text{while}\; B\!Exp \;\text{do}\; Block$\medskip\\

   750 $Stmts$ & $\rightarrow$ &  $Stmt \;\text{;}\; Stmts$\\

   751               & $|$ & $Stmt$\medskip\\

   752 $Block$ & $\rightarrow$ &  $\{ Stmts \}$\\

   753                 & $|$ & $Stmt$\medskip\\

   754 $AExp$ & $\rightarrow$ & \ldots\\

   755 $BExp$ & $\rightarrow$ & \ldots\\

   756 \end{tabular}}

   757 \end{center}

   758 

   759 

   760 \end{frame}}

   761 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   762 

   763 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   764 \mode<presentation>{

   765 \begin{frame}[c]

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

   767 

   768 \begin{center}

   769 \bl{\begin{tabular}{l}

   770 $\{$\\

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

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

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

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

   775 $\}$

   776 \end{tabular}}

   777 \end{center}

   778 

   779 \begin{itemize}

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

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

   782 \end{itemize}

   783