591 \end{center}\pause

   610 \end{center}

   592 

   611 

   593 \begin{center}

   612 \end{frame}

   594   \tt Time flies like an arrow;\\ 

   613 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   595   fruit flies like bananas.

   614 

   596   \end{center}  

   597 

   598 \end{frame}

   599 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   600 

   601 

   602 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   603 \begin{frame}[c]

   604 \frametitle{Parser Combinators}

   605 

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

   607 {\small\url{https://vimeo.com/142341803}}\bigskip

   608 

   609 Parser combinators: \bigskip

   610 

   611 \begin{minipage}{1.1\textwidth}

   612 \begin{center}

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

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

   615 \end{center}

   616 \end{minipage}\bigskip

   617 

   618 \begin{itemize}

   619 \item atomic parsers

   620 \item sequencing

   621 \item alternative

   622 \item semantic action

   623 \end{itemize}

   624 

   625 \end{frame}

   626 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   627 

   628 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   629 \begin{frame}[c]

   630 

   631 Atomic parsers, for example, number tokens

   632 

   633 \begin{center}

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

   635 \end{center}\bigskip

   636 

   637 \begin{itemize}

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

   639   input (stream)

   640 \item also works for characters and strings

   641 \end{itemize}

   642 \end{frame}

   643 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   644 

   645 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   646 \begin{frame}[c]

   647 

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

   649 

   650 \begin{itemize}

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

   652   the outputs

   653 \end{itemize}

   654 

   655 \begin{center}

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

   657 \end{center}

   658 

   659 \end{frame}

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

   661 

   662 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   663 \begin{frame}[c]

   664 

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

   666 

   667 \begin{itemize}

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

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

   670 \item then combine the results:\medskip 

   671 \begin{center}

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

   673 \end{center}

   674 \end{itemize}

   675 

   676 \begin{center}

   677 \begin{tabular}{l}

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

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

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

   681 \end{tabular}

   682 \end{center}

   683 

   684 

   685 \end{frame}

   686 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   687 

   688 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   689 \begin{frame}[c]

   690 

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

   692 

   693 \begin{itemize}

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

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

   696 \end{itemize}

   697 

   698 \begin{center}

   699 \begin{tabular}{l}

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

   701 \end{tabular}

   702 \end{center}\bigskip\bigskip\pause

   703 

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

   705 

   706 \end{frame}

   707 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   708 

   709 

   710 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   711 \mode<presentation>{

   712 \begin{frame}[c]

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

   714 

   715 Addition

   716 

   717 \begin{center}

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

   719 \end{center}\pause

   720 

   721 Multiplication

   722 

   723 \begin{center}

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

   725 \end{center}\pause

   726 

   727 Parenthesis

   728 

   729 \begin{center}

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

   731 \end{center}

   732 

   733 \end{frame}}

   734 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   735 

   736 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   737 \begin{frame}[c]

   738 \frametitle{Types of Parsers}

   739 

   740 \begin{itemize}

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

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

   743 

   744 \begin{center}

   745 \bl{$T \times S$}

   746 \end{center}\pause

   747 

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

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

   750 

   751 \begin{center}

   752 \bl{$T$}

   753 \end{center}\pause

   754 

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

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

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

   758 

   759 \begin{center}

   760 \bl{$S$}

   761 \end{center}

   762 

   763 \end{itemize}

   764 

   765 \end{frame}

   766 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   767 

   768 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   769 \begin{frame}[c]

   770 \frametitle{Input Types of Parsers}

   771 

   772 \begin{itemize}

   773 \item input: \alert{token list}

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

   775 \end{itemize}\bigskip\pause

   776 

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

   778 sequence (for example a string)

   779 

   780 \end{frame}

   781 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   782 

   783 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   784 \begin{frame}[c]

   785 \frametitle{Scannerless Parsers}

   786 

   787 \begin{itemize}

   788 \item input: \alert{string}

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

   790 \end{itemize}\bigskip\bigskip

   791 

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

   793 filtered out; then input is a sequence of tokens

   794 

   795 \end{frame}

   796 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   797 

   798 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   799 \begin{frame}[c]

   800 \frametitle{Successful Parses}

   801 

   802 \begin{itemize}

   803 \item input: string

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

   805 \end{itemize}\bigskip

   806 

   807 a parse is successful whenever the input has been fully

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

   809 

   810 \end{frame}

   811 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   812 

   813 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   814 \begin{frame}[c]

   815 \frametitle{Abstract Parser Class}

   816 

   817 \small

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

   819  {../progs/app7.scala}

   820 \end{frame}

   821 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   822 

   823 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   824 \begin{frame}[c]

   825 

   826 \small

   827 \fontsize{10}{12}\selectfont

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

   829   {../progs/app8.scala}

   830 \end{frame}

   831 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   832 

   833 

   834 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   835 \begin{frame}[c]

   836 \frametitle{Two Grammars}

   837 

   838 Which languages are recognised by the following two grammars?

   839 

   840 \begin{center}

   841 \bl{\begin{tabular}{lcl}

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

   843         & $|$ & $\epsilon$

   844 \end{tabular}}

   845 \end{center}\bigskip

   846 

   847 \begin{center}

   848 \bl{\begin{tabular}{lcl}

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

   850         & $|$ & $\epsilon$

   851 \end{tabular}}

   852 \end{center}

   853 

   854 \end{frame}

   855 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   856 

   857 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   858 \begin{frame}[t]

   859 \frametitle{Ambiguous Grammars}

   860 

   861 \begin{center}

   862 \begin{tikzpicture}

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

   864     enlargelimits=false,

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

   866     xmax=1050,

   867     ymax=33,

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

   869     scaled ticks=false,

   870     axis lines=left,

   871     width=11cm,

   872     height=7cm, 

   873     legend entries={unambiguous,ambiguous},  

   874     legend pos=north east,

   875     legend cell align=left,

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

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

   878   table {s-grammar1.data};

   879 \only<2>{

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

   881   table {s-grammar2.data};}  

   882 \end{axis}

   883 \end{tikzpicture}

   884 \end{center}

   885 

   886 \end{frame}

   887 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   888 

   889 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   890 \begin{frame}

   891 \frametitle{While-Language}

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

   893 

   894 \bl{\begin{plstx}[rhs style=,one per line]: \meta{Stmt} ::= skip

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

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

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

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

   899           | \meta{Stmt}\\

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

   901           | \meta{Stmt}\\

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

   903 : \meta{BExp} ::= \ldots\\\end{plstx}}

   904 

   905 \end{frame}

   906 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   907 

   908 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   909 \begin{frame}[c]

   910 \frametitle{An Interpreter}

   911 

   912 \begin{center}

   913 \bl{\begin{tabular}{l}

   914 $\{$\\

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

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

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

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

   919 $\}$

   920 \end{tabular}}

   921 \end{center}

   922 

   923 \begin{itemize}

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

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

   926 \end{itemize}

   927 

   928 \end{frame}

   929 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   930 

   931 

   932 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   933 \mode<presentation>{

   934 \begin{frame}[c]

   935 \frametitle{\begin{tabular}{c}Interpreter\end{tabular}}

   936 

   937 \begin{center}

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

   939 $\text{eval}(n, E)$ & $\dn$ & $n$\\

   940 $\text{eval}(x, E)$ & $\dn$ & $E(x)$ \;\;\;\textcolor{black}{lookup \bl{$x$} in \bl{$E$}}\\

   941 $\text{eval}(a_1 + a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) + \text{eval}(a_2, E)$\\

   942 $\text{eval}(a_1 - a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) - \text{eval}(a_2, E)$\\

   943 $\text{eval}(a_1 * a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) * \text{eval}(a_2, E)$\bigskip\\

   944 $\text{eval}(a_1 = a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) = \text{eval}(a_2, E)$\\

   945 $\text{eval}(a_1\,!\!= a_2, E)$ & $\dn$ & $\neg(\text{eval}(a_1, E) = \text{eval}(a_2, E))$\\

   946 $\text{eval}(a_1 < a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) < \text{eval}(a_2, E)$\

   947 \end{tabular}}

   948 \end{center}

   949 

   950 \end{frame}}

   951 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   952 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   953 \mode<presentation>{

   954 \begin{frame}[c]

   955 \frametitle{\begin{tabular}{c}Interpreter (2)\end{tabular}}

   956 

   957 \begin{center}

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

   959 $\text{eval}(\text{skip}, E)$ & $\dn$ & $E$\\

   960 $\text{eval}(x:=a, E)$ & $\dn$ & \bl{$E(x \mapsto \text{eval}(a, E))$}\\

   961 \multicolumn{3}{@{}l@{}}{$\text{eval}(\text{if}\;b\;\text{then}\;cs_1\;\text{else}\;cs_2 , E) \dn$}\\

   962 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{if}\;\text{eval}(b,E)\;\text{then}\;

   963 \text{eval}(cs_1,E)$}\\

   964 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\phantom{\text{if}\;\text{eval}(b,E)\;}\text{else}\;\text{eval}(cs_2,E)$}\\

   965 \multicolumn{3}{@{}l@{}}{$\text{eval}(\text{while}\;b\;\text{do}\;cs, E) \dn$}\\

   966 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{if}\;\text{eval}(b,E)$}\\

   967 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{then}\;

   968 \text{eval}(\text{while}\;b\;\text{do}\;cs, \text{eval}(cs,E))$}\\

   969 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{else}\; E$}\\

   970 $\text{eval}(\text{write}\; x, E)$ & $\dn$ & $\{\;\text{println}(E(x))\; ;\;E\;\}$\\

   971 \end{tabular}}

   972 \end{center}

   973 

   974 \end{frame}}

   975 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   976 

   977 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   978 \begin{frame}[c]

   979 \frametitle{Test Program}

   980 

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

   982 

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

   984 %\texttt{\lstinputlisting{../progs/loops.while}}}

   985 

   986 \end{frame}

   987 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   988 

   989 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   990 \mode<presentation>{

   991 \begin{frame}[t]

   992 \frametitle{\begin{tabular}{c}Interpreted Code\end{tabular}}

   993 

   994 \begin{center}

   995 \begin{tikzpicture}

   996 \begin{axis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=secs, legend style=small]

   997 \addplot+[smooth] file {interpreted.data};

   998 \end{axis}

   999 \end{tikzpicture}

  1000 \end{center}

  1001 

  1002 \end{frame}}

  1003 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

  1004 

  1005 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

  1006 \mode<presentation>{

  1007 \begin{frame}[c]

  1008 \frametitle{\begin{tabular}{c}Java Virtual Machine\end{tabular}}

  1009 

  1010 \begin{itemize}

  1011 \item introduced in 1995

  1012 \item is a stack-based VM (like Postscript, CLR of .Net)

  1013 \item contains a JIT compiler

  1014 \item many languages take advantage of JVM's infrastructure (JRE)

  1015 \item is garbage collected $\Rightarrow$ no buffer overflows

  1016 \item some languages compile to the JVM: Scala, Clojure\ldots

  1017 \end{itemize}

  1018 

  1019 \end{frame}}