slides/slides05.tex
author Christian Urban <urbanc@in.tum.de>
Wed, 23 Oct 2019 21:39:11 +0100
changeset 664 dc2f5eb33a9a
parent 593 bb24d4e207b6
child 665 6d74d2a0a4b0
permissions -rw-r--r--
updated
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
582
d236e75e1d55 updated
Christian Urban <urbanc@in.tum.de>
parents: 550
diff changeset
     1
664
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
     2
% !TEX program = xelatex
44
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     3
\documentclass[dvipsnames,14pt,t]{beamer}
270
4dbeaf43031d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 215
diff changeset
     4
\usepackage{../slides}
4dbeaf43031d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 215
diff changeset
     5
\usepackage{../graphics}
215
828303e8e4af updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 169
diff changeset
     6
\usepackage{../langs}
828303e8e4af updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 169
diff changeset
     7
\usepackage{../data}
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
     8
\usepackage{../grammar}
44
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     9
270
4dbeaf43031d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 215
diff changeset
    10
\hfuzz=220pt 
4dbeaf43031d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 215
diff changeset
    11
4dbeaf43031d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 215
diff changeset
    12
\pgfplotsset{compat=1.11}
4dbeaf43031d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 215
diff changeset
    13
4dbeaf43031d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 215
diff changeset
    14
\newcommand{\bl}[1]{\textcolor{blue}{#1}}  
44
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    15
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    16
% beamer stuff 
445
e7d0157f0471 updated slides
Christian Urban <urbanc@in.tum.de>
parents: 370
diff changeset
    17
\renewcommand{\slidecaption}{CFL 05, King's College London}
270
4dbeaf43031d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 215
diff changeset
    18
44
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    19
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    20
\begin{document}
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    21
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    22
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
270
4dbeaf43031d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 215
diff changeset
    23
\begin{frame}[t]
44
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    24
\frametitle{%
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    25
  \begin{tabular}{@ {}c@ {}}
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    26
  \\[-3mm]
445
e7d0157f0471 updated slides
Christian Urban <urbanc@in.tum.de>
parents: 370
diff changeset
    27
  \LARGE Compilers and \\[-2mm] 
44
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    28
  \LARGE Formal Languages (5)\\[3mm] 
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    29
  \end{tabular}}
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    30
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    31
  \normalsize
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    32
  \begin{center}
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    33
  \begin{tabular}{ll}
664
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
    34
    Email:  & christian.urban at kcl.ac.uk\\
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
    35
    Office Hours: & Thursdays 12 -- 14\\
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
    36
    Location: & N7.07 (North Wing, Bush House)\\
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
    37
    Slides \& Progs: & KEATS (also homework is there)\\  
44
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    38
  \end{tabular}
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    39
  \end{center}
270
4dbeaf43031d updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 215
diff changeset
    40
\end{frame}
289
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    41
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
44
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    42
462
Christian Urban <urbanc@in.tum.de>
parents: 451
diff changeset
    43
Christian Urban <urbanc@in.tum.de>
parents: 451
diff changeset
    44
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <urbanc@in.tum.de>
parents: 451
diff changeset
    45
\begin{frame}[c]
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
    46
\frametitle{\begin{tabular}{c}Last Week\\[-1mm] 
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
    47
            Regexes and Values\end{tabular}}
44
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    48
289
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    49
Regular expressions and their corresponding values:
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    50
147
4725bba8ef26 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 93
diff changeset
    51
\begin{center}
289
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    52
\begin{columns}
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    53
\begin{column}{3cm}
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    54
\begin{tabular}{@{}rrl@{}}
445
e7d0157f0471 updated slides
Christian Urban <urbanc@in.tum.de>
parents: 370
diff changeset
    55
  \bl{$r$} & \bl{$::=$}  & \bl{$\ZERO$}\\
e7d0157f0471 updated slides
Christian Urban <urbanc@in.tum.de>
parents: 370
diff changeset
    56
           & \bl{$\mid$} & \bl{$\ONE$}   \\
289
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    57
           & \bl{$\mid$} & \bl{$c$}          \\
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    58
           & \bl{$\mid$} & \bl{$r_1 \cdot r_2$}\\
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    59
           & \bl{$\mid$} & \bl{$r_1 + r_2$}   \\
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    60
  \\
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    61
           & \bl{$\mid$} & \bl{$r^*$}         \\
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    62
  \end{tabular}
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    63
\end{column}
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    64
\begin{column}{3cm}
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    65
\begin{tabular}{@{\hspace{-7mm}}rrl@{}}
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    66
  \bl{$v$} & \bl{$::=$}  & \\
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    67
           &             & \bl{$Empty$}   \\
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    68
           & \bl{$\mid$} & \bl{$Char(c)$}          \\
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    69
           & \bl{$\mid$} & \bl{$Seq(v_1,v_2)$}\\
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    70
           & \bl{$\mid$} & \bl{$Left(v)$}   \\
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    71
           & \bl{$\mid$} & \bl{$Right(v)$}  \\
664
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
    72
           & \bl{$\mid$} & \bl{$Stars [v_1,\ldots\,v_n]$} \\
289
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    73
  \end{tabular}
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    74
\end{column}
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    75
\end{columns}
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    76
\end{center}
44
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    77
289
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    78
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    79
\end{frame}
147
4725bba8ef26 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 93
diff changeset
    80
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
4725bba8ef26 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 93
diff changeset
    81
44
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    82
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
272
1446bc47a294 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 270
diff changeset
    83
\begin{frame}[c]
44
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    84
289
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    85
\begin{textblock}{10}(3,5)
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    86
\begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}]
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    87
\node (r1)  {\bl{$r_1$}};
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    88
\node (r2) [right=of r1] {\bl{$r_2$}};
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    89
\draw[->,line width=1mm]  (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    90
\node (r3) [right=of r2] {\bl{$r_3$}};
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    91
\draw[->,line width=1mm]  (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    92
\node (r4) [right=of r3] {\bl{$r_4$}};
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    93
\draw[->,line width=1mm]  (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    94
\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    95
\node (v4) [below=of r4] {\bl{$v_4$}};
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    96
\draw[->,line width=1mm]  (r4) -- (v4);
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    97
\node (v3) [left=of v4] {\bl{$v_3$}};
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    98
\draw[->,line width=1mm]  (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
    99
\node (v2) [left=of v3] {\bl{$v_2$}};
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   100
\draw[->,line width=1mm]  (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   101
\node (v1) [left=of v2] {\bl{$v_1$}};
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   102
\draw[->,line width=1mm]  (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   103
\draw[->,line width=0.5mm]  (r3) -- (v3);
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   104
\draw[->,line width=0.5mm]  (r2) -- (v2);
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   105
\draw[->,line width=0.5mm]  (r1) -- (v1);
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   106
\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
147
4725bba8ef26 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 93
diff changeset
   107
\end{tikzpicture}
289
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   108
\end{textblock}
147
4725bba8ef26 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 93
diff changeset
   109
289
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   110
\begin{textblock}{6}(1,0.8)
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   111
\begin{bubble}[6cm]
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   112
\small
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   113
\begin{tabular}{ll}
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   114
\bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\
445
e7d0157f0471 updated slides
Christian Urban <urbanc@in.tum.de>
parents: 370
diff changeset
   115
\bl{$r_2$}: & \bl{$\ONE \cdot (b \cdot c)$}\\
e7d0157f0471 updated slides
Christian Urban <urbanc@in.tum.de>
parents: 370
diff changeset
   116
\bl{$r_3$}: & \bl{$(\ZERO \cdot (b \cdot c)) + (\ONE \cdot c)$}\\
e7d0157f0471 updated slides
Christian Urban <urbanc@in.tum.de>
parents: 370
diff changeset
   117
\bl{$r_4$}: & \bl{$(\ZERO \cdot (b \cdot c)) + ((\ZERO \cdot c) + \ONE)$}\\
147
4725bba8ef26 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 93
diff changeset
   118
\end{tabular}
289
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   119
\end{bubble}
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   120
\end{textblock}
147
4725bba8ef26 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 93
diff changeset
   121
289
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   122
\begin{textblock}{6}(1,11.4)
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   123
\begin{bubble}[7.6cm]
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   124
\small
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   125
\begin{tabular}{ll}
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   126
\bl{$v_1$}: & \bl{$Seq(Char(a), Seq(Char(b), Char(c)))$}\\
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   127
\bl{$v_2$}: & \bl{$Seq(Empty, Seq(Char(b), Char(c)))$}\\
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   128
\bl{$v_3$}: & \bl{$Right(Seq(Empty, Char(c)))$}\\
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   129
\bl{$v_4$}: & \bl{$Right(Right(Empty))$}\\
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   130
\end{tabular}
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   131
\end{bubble}
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   132
\end{textblock}
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   133
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   134
\begin{textblock}{6}(12,11.4)
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   135
\begin{bubble}[2cm]
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   136
\small
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   137
\begin{tabular}{ll}
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   138
\bl{$|v_1|$}: & \bl{$abc$}\\
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   139
\bl{$|v_2|$}: & \bl{$bc$}\\
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   140
\bl{$|v_3|$}: & \bl{$c$}\\
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   141
\bl{$|v_4|$}: & \bl{$[]$}
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   142
\end{tabular}
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   143
\end{bubble}
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   144
\end{textblock}
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   145
44
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   146
272
1446bc47a294 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 270
diff changeset
   147
\end{frame}
44
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   148
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   149
289
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   150
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   151
\begin{frame}[c]
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   152
\frametitle{Simplification}
147
4725bba8ef26 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 93
diff changeset
   153
289
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   154
\begin{itemize}
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   155
\item If we simplify after the derivative, then we are builing the
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   156
value for the simplified regular expression, but \emph{not} for the original
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   157
regular expression.
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   158
\end{itemize}
44
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   159
147
4725bba8ef26 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 93
diff changeset
   160
\begin{center}
289
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   161
\begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}]
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   162
\node (r1)  {\bl{$r_1$}};
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   163
\node (r2) [right=of r1] {\bl{$r_2$}};
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   164
\draw[->,line width=1mm]  (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   165
\node (r3) [right=of r2] {\bl{$r_3$}};
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   166
\draw[->,line width=1mm]  (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   167
\node (r4) [right=of r3] {\bl{$r_4$}};
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   168
\draw[->,line width=1mm]  (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   169
\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   170
\node (v4) [below=of r4] {\bl{$v_4$}};
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   171
\draw[->,line width=1mm]  (r4) -- (v4);
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   172
\node (v3) [left=of v4] {\bl{$v_3$}};
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   173
\draw[->,line width=1mm]  (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   174
\node (v2) [left=of v3] {\bl{$v_2$}};
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   175
\draw[->,line width=1mm]  (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   176
\node (v1) [left=of v2] {\bl{$v_1$}};
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   177
\draw[->,line width=1mm]  (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   178
\draw[->,line width=0.5mm]  (r3) -- (v3);
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   179
\draw[->,line width=0.5mm]  (r2) -- (v2);
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   180
\draw[->,line width=0.5mm]  (r1) -- (v1);
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   181
\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
147
4725bba8ef26 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 93
diff changeset
   182
\end{tikzpicture}
4725bba8ef26 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 93
diff changeset
   183
\end{center}
44
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   184
289
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   185
\small
445
e7d0157f0471 updated slides
Christian Urban <urbanc@in.tum.de>
parents: 370
diff changeset
   186
\hspace{4.5cm}\bl{$(b \cdot c) + (\ZERO + \ONE)$}
289
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   187
$\mapsto$
445
e7d0157f0471 updated slides
Christian Urban <urbanc@in.tum.de>
parents: 370
diff changeset
   188
\bl{$(b \cdot c) + \ONE$}
289
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   189
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   190
\end{frame}
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   191
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   192
528
68fab15cd6fb updated
cu
parents: 500
diff changeset
   193
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
68fab15cd6fb updated
cu
parents: 500
diff changeset
   194
% \begin{frame}[t]
361
9c7eb266594c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 360
diff changeset
   195
528
68fab15cd6fb updated
cu
parents: 500
diff changeset
   196
% \begin{center}
68fab15cd6fb updated
cu
parents: 500
diff changeset
   197
% \bl{$\only<1>{(b \cdot c)}%
68fab15cd6fb updated
cu
parents: 500
diff changeset
   198
%      \only<2-3>{(\underline{b \cdot c})}%
68fab15cd6fb updated
cu
parents: 500
diff changeset
   199
%      \only<1-3>{+}% 
68fab15cd6fb updated
cu
parents: 500
diff changeset
   200
%      \only<1>{(\ZERO + \ONE)}%
68fab15cd6fb updated
cu
parents: 500
diff changeset
   201
%      \only<2-3>{(\underline{\ZERO + \ONE})}$}%
68fab15cd6fb updated
cu
parents: 500
diff changeset
   202
% \only<4->{%
68fab15cd6fb updated
cu
parents: 500
diff changeset
   203
% \bl{$\underline{(b \cdot c) + (\ZERO + \ONE)}$}%
68fab15cd6fb updated
cu
parents: 500
diff changeset
   204
% }
68fab15cd6fb updated
cu
parents: 500
diff changeset
   205
% $\mapsto$
68fab15cd6fb updated
cu
parents: 500
diff changeset
   206
% \bl{$(b \cdot c) + \ONE$}
68fab15cd6fb updated
cu
parents: 500
diff changeset
   207
% \end{center}\bigskip
361
9c7eb266594c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 360
diff changeset
   208
528
68fab15cd6fb updated
cu
parents: 500
diff changeset
   209
% \onslide<3->{%
68fab15cd6fb updated
cu
parents: 500
diff changeset
   210
% \begin{center}
68fab15cd6fb updated
cu
parents: 500
diff changeset
   211
% \begin{tabular}{lcl}
68fab15cd6fb updated
cu
parents: 500
diff changeset
   212
% \bl{$f_{s1}$} & \bl{$=$} & \bl{$\lambda v.v$}\\
68fab15cd6fb updated
cu
parents: 500
diff changeset
   213
% \bl{$f_{s2}$} & \bl{$=$} & \bl{$\lambda v. \textit{Right}(v)$}
68fab15cd6fb updated
cu
parents: 500
diff changeset
   214
% \end{tabular}
68fab15cd6fb updated
cu
parents: 500
diff changeset
   215
% \end{center}}
361
9c7eb266594c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 360
diff changeset
   216
528
68fab15cd6fb updated
cu
parents: 500
diff changeset
   217
% \only<4>{%
68fab15cd6fb updated
cu
parents: 500
diff changeset
   218
% \begin{center}
68fab15cd6fb updated
cu
parents: 500
diff changeset
   219
% \begin{tabular}{@{}l@{\hspace{1mm}}l@{}}
68fab15cd6fb updated
cu
parents: 500
diff changeset
   220
% \bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}\\
68fab15cd6fb updated
cu
parents: 500
diff changeset
   221
% \quad \bl{$\lambda v.\,$} 
68fab15cd6fb updated
cu
parents: 500
diff changeset
   222
%         case \bl{$v = Left(v')$}: 
68fab15cd6fb updated
cu
parents: 500
diff changeset
   223
%       & return \bl{$Left(f_{s1}(v'))$}\\
68fab15cd6fb updated
cu
parents: 500
diff changeset
   224
% \quad \phantom{$\lambda v.\,$} 
68fab15cd6fb updated
cu
parents: 500
diff changeset
   225
%         case \bl{$v = Right(v')$}: 
68fab15cd6fb updated
cu
parents: 500
diff changeset
   226
%       & return \bl{$Right(f_{s2}(v'))$}\\ 
68fab15cd6fb updated
cu
parents: 500
diff changeset
   227
% \end{tabular}
68fab15cd6fb updated
cu
parents: 500
diff changeset
   228
% \end{center}}%
68fab15cd6fb updated
cu
parents: 500
diff changeset
   229
% \only<5->{%
68fab15cd6fb updated
cu
parents: 500
diff changeset
   230
% \begin{center}
68fab15cd6fb updated
cu
parents: 500
diff changeset
   231
% \begin{tabular}{@{}l@{\hspace{1mm}}l@{}}
68fab15cd6fb updated
cu
parents: 500
diff changeset
   232
% \only<5->{\phantom{\bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}}}\\
68fab15cd6fb updated
cu
parents: 500
diff changeset
   233
% \quad \bl{$\lambda v.\,$} 
68fab15cd6fb updated
cu
parents: 500
diff changeset
   234
%         case \bl{$v = Left(v')$}: 
68fab15cd6fb updated
cu
parents: 500
diff changeset
   235
%       & return \bl{$Left(v')$}\\
68fab15cd6fb updated
cu
parents: 500
diff changeset
   236
% \quad \phantom{$\lambda v.\,$} 
68fab15cd6fb updated
cu
parents: 500
diff changeset
   237
%         case \bl{$v = Right(v')$}: 
68fab15cd6fb updated
cu
parents: 500
diff changeset
   238
%       & return \bl{$Right(Right(v'))$}\\ 
68fab15cd6fb updated
cu
parents: 500
diff changeset
   239
% \end{tabular}
68fab15cd6fb updated
cu
parents: 500
diff changeset
   240
% \end{center}}%
361
9c7eb266594c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 360
diff changeset
   241
528
68fab15cd6fb updated
cu
parents: 500
diff changeset
   242
% \only<6->{%
68fab15cd6fb updated
cu
parents: 500
diff changeset
   243
% \begin{center}
68fab15cd6fb updated
cu
parents: 500
diff changeset
   244
% \begin{tabular}{@{}l@{\hspace{4mm}}l@{}}
68fab15cd6fb updated
cu
parents: 500
diff changeset
   245
% \bl{$\textit{mkeps}$} simplified case: &
68fab15cd6fb updated
cu
parents: 500
diff changeset
   246
% \bl{$\textit{Right}(\textit{Empty})$}\\
68fab15cd6fb updated
cu
parents: 500
diff changeset
   247
% rectified case: &
68fab15cd6fb updated
cu
parents: 500
diff changeset
   248
% \bl{$\textit{Right}(\textit{Right}(\textit{Empty}))$}
68fab15cd6fb updated
cu
parents: 500
diff changeset
   249
% \end{tabular}
68fab15cd6fb updated
cu
parents: 500
diff changeset
   250
% \end{center}}%
361
9c7eb266594c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 360
diff changeset
   251
528
68fab15cd6fb updated
cu
parents: 500
diff changeset
   252
% \end{frame}
68fab15cd6fb updated
cu
parents: 500
diff changeset
   253
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
361
9c7eb266594c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 360
diff changeset
   254
9c7eb266594c updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 360
diff changeset
   255
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
289
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   256
\begin{frame}[c]
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   257
\frametitle{Records}
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   258
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   259
\begin{itemize}
583
Christian Urban <urbanc@in.tum.de>
parents: 582
diff changeset
   260
\item new regex: \bl{$(x:r)$}\hspace{7mm}new value: \bl{$Rec(x,v)$}\medskip\pause
44
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   261
289
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   262
\item \bl{$nullable(x:r) \dn nullable(r)$}
583
Christian Urban <urbanc@in.tum.de>
parents: 582
diff changeset
   263
\item \bl{$der\,c\,(x:r) \dn (x:der\,c\,r)$}
289
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   264
\item \bl{$mkeps(x:r) \dn Rec(x, mkeps(r))$}
583
Christian Urban <urbanc@in.tum.de>
parents: 582
diff changeset
   265
\item \bl{$inj\,(x:r)\,c\,Rec(x, v) \dn Rec(x, inj\,r\,c\,v)$}
Christian Urban <urbanc@in.tum.de>
parents: 582
diff changeset
   266
\end{itemize}\bigskip\bigskip\pause
44
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   267
289
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   268
\small
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   269
for extracting subpatterns \bl{$(z: ((x:ab) + (y:ba))$}
44
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   270
289
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   271
\end{frame}
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   272
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
46
Christian Urban <urbanc@in.tum.de>
parents: 44
diff changeset
   273
583
Christian Urban <urbanc@in.tum.de>
parents: 582
diff changeset
   274
148
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   275
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   276
\begin{frame}[c]
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   277
\frametitle{Environments}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   278
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   279
Obtaining the ``recorded'' parts of a value: 
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   280
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   281
\begin{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   282
\begin{tabular}{lcl}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   283
  \bl{$env(Empty)$}     & \bl{$\dn$} & \bl{$[]$}\\
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   284
  \bl{$env(Char(c))$}   & \bl{$\dn$} & \bl{$[]$}\\
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   285
  \bl{$env(Left(v))$}   & \bl{$\dn$} & \bl{$env(v)$}\\
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   286
  \bl{$env(Right(v))$}  & \bl{$\dn$} & \bl{$env(v)$}\\
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   287
  \bl{$env(Seq(v_1,v_2))$}& \bl{$\dn$} & \bl{$env(v_1) \,@\, env(v_2)$}\\
664
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   288
  \bl{$env(Stars [v_1,\ldots ,v_n])$} & \bl{$\dn$} & 
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   289
     \bl{$env(v_1) \,@\ldots @\, env(v_n)$}\\
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   290
  \bl{$env(Rec(x:v))$} & \bl{$\dn$} & \bl{$(x:|v|) :: env(v)$}\\
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   291
\end{tabular}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   292
\end{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   293
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   294
\end{frame}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   295
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   296
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   297
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   298
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   299
\begin{frame}[c]
289
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   300
\frametitle{While Tokens}
150
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 149
diff changeset
   301
148
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   302
\begin{center}
289
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   303
\begin{tabular}{@{}r@{\hspace{2mm}}c@{\hspace{2mm}}l@{}}
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   304
\pcode{WHILE\_REGS} & $\dn$ & \raisebox{-1mm}{\large(}\pcode{("k" : KEYWORD)} +\\ 
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   305
                  &       & \phantom{(}\pcode{("i" : ID)} +\\ 
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   306
                  &       & \phantom{(}\pcode{("o" : OP)} + \\
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   307
                  &       & \phantom{(}\pcode{("n" : NUM)} + \\
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   308
                  &       & \phantom{(}\pcode{("s" : SEMI)} +\\ 
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   309
                  &       & \phantom{(}\pcode{("p" : (LPAREN + RPAREN))} +\\ 
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   310
                  &       & \phantom{(}\pcode{("b" : (BEGIN + END))} +\\ 
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   311
                  &       & \phantom{(}\pcode{("w" : WHITESPACE)}\raisebox{-1mm}{\large)$^*$}
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   312
\end{tabular}
148
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   313
\end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   314
289
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   315
\end{frame}
c22c8baff491 updated slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 272
diff changeset
   316
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
148
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   317
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   318
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   319
148
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   320
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   321
\begin{frame}[t]
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   322
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   323
\consolas
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   324
\begin{center}
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   325
\code{"if true then then 42 else +"}
148
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   326
\end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   327
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   328
\only<1>{
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   329
\small\begin{tabular}{l}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   330
KEYWORD(if),\\ 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   331
WHITESPACE,\\ 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   332
IDENT(true),\\ 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   333
WHITESPACE,\\ 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   334
KEYWORD(then),\\ 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   335
WHITESPACE,\\ 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   336
KEYWORD(then),\\ 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   337
WHITESPACE,\\ 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   338
NUM(42),\\ 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   339
WHITESPACE,\\ 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   340
KEYWORD(else),\\ 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   341
WHITESPACE,\\ 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   342
OP(+)
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   343
\end{tabular}}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   344
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   345
\only<2>{
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   346
\small\begin{tabular}{l}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   347
KEYWORD(if),\\ 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   348
IDENT(true),\\ 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   349
KEYWORD(then),\\ 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   350
KEYWORD(then),\\ 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   351
NUM(42),\\ 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   352
KEYWORD(else),\\ 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   353
OP(+)
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   354
\end{tabular}}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   355
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   356
\end{frame}
148
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   357
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   358
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   359
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   360
\begin{frame}[c]
664
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   361
\frametitle{Coursework: Submissions}
582
d236e75e1d55 updated
Christian Urban <urbanc@in.tum.de>
parents: 550
diff changeset
   362
d236e75e1d55 updated
Christian Urban <urbanc@in.tum.de>
parents: 550
diff changeset
   363
\begin{itemize}
664
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   364
\item Scala (29)
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   365
\item Haskell (1)
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   366
\item Kotlin (1)
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   367
\item Rust (1)
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   368
\end{itemize}\bigskip  
582
d236e75e1d55 updated
Christian Urban <urbanc@in.tum.de>
parents: 550
diff changeset
   369
664
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   370
Please get in contact if you intend to do CW Strand 2.
582
d236e75e1d55 updated
Christian Urban <urbanc@in.tum.de>
parents: 550
diff changeset
   371
\end{frame}
d236e75e1d55 updated
Christian Urban <urbanc@in.tum.de>
parents: 550
diff changeset
   372
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
664
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   373
  
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   374
582
d236e75e1d55 updated
Christian Urban <urbanc@in.tum.de>
parents: 550
diff changeset
   375
d236e75e1d55 updated
Christian Urban <urbanc@in.tum.de>
parents: 550
diff changeset
   376
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
664
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   377
%\begin{frame}[c]
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   378
%\frametitle{Coursework: PLs (16)}
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   379
%
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   380
%\begin{itemize}
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   381
%\item Java (16)
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   382
%\item C++, C, C\# (14)
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   383
%\item JavaScript (10)
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   384
%\item Scala (9)
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   385
%\item Python (9)  
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   386
%\item PHP (6)
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   387
%\item Haskell (3)
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   388
%\item Ruby (4)
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   389
%\item Bash, Perl, Powershell (2)
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   390
%\item TypeScript (1)
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   391
%\item R (1)
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   392
%\item Coconut (1)  
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   393
%\item Pascal (1)
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   394
%\end{itemize}  
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   395
%
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   396
%\end{frame}
528
68fab15cd6fb updated
cu
parents: 500
diff changeset
   397
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
150
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 149
diff changeset
   398
290
3a2fa69ea675 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 289
diff changeset
   399
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
664
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   400
%\begin{frame}[c]
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   401
%\frametitle{Coursework: Nullable}
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   402
%
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   403
%\begin{center}
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   404
%\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   405
%  \bl{$nullable([c_1 c_2 \ldots c_n])$}  & \bl{$\dn$} & $?$\\
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   406
%  \bl{$nullable(r^+)$}                   & \bl{$\dn$} & $?$\\
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   407
%  \bl{$nullable(r^?)$}                   & \bl{$\dn$} & $?$\\
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   408
%  \bl{$nullable(r^{\{n\}})$}              & \bl{$\dn$} & $?$\\
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   409
%  \bl{$nullable(r^{\{n..\}})$}            & \bl{$\dn$} & $?$\\
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   410
%  \bl{$nullable(r^{\{..n\}})$}            & \bl{$\dn$} & $?$\\
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   411
%  \bl{$nullable(r^{\{n..m\}})$}           & \bl{$\dn$} & $?$\\
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   412
%  \bl{$nullable(\sim{}r)$}               & \bl{$\dn$} & $?$\\
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   413
%                                                        
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   414
%\end{tabular}
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   415
%\end{center}
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   416
%
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   417
%\end{frame}
290
3a2fa69ea675 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 289
diff changeset
   418
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
150
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 149
diff changeset
   419
528
68fab15cd6fb updated
cu
parents: 500
diff changeset
   420
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
664
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   421
%\begin{frame}[c]
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   422
%%%\frametitle{Coursework: der}
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   423
%
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   424
%\begin{center}
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   425
%\begin{tabular}{@ {}l@ {\hspace{1mm}}c@ {\hspace{1mm}}l@ {}}
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   426
%  \bl{$der\, c\, ([c_1 c_2 \ldots c_n])$}  & \bl{$\dn$} & $?$\\
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   427
%  \bl{$der\, c\, (r^+)$}                   & \bl{$\dn$} & $?$\\
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   428
%  \bl{$der\, c\, (r^?)$}                   & \bl{$\dn$} & $?$\\
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   429
%  \bl{$der\, c\, (r^{\{n\}})$}              & \bl{$\dn$} &
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   430
%     \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{n-\liningnums{1}\}}$}\\
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   431
%  \bl{$der\, c\, (r^{\{n..\}})$}            & \bl{$\dn$} &
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   432
%     \bl{$if\;n=0\;then (der\,c\,r)\cdot r^*$}\\
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   433
%  & & \bl{$\phantom{if\;n=0\;}else \;(der\,c\,r)\cdot r^{\{n-\liningnums{1}..\}}$}\\
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   434
%  \bl{$der\, c\, (r^{\{..n\}})$}            & \bl{$\dn$} &
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   435
%     \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{..n-\liningnums{1}\}}$}\\
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   436
%  
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   437
%  \bl{$der\, c\, (r^{\{n..m\}})$}          & \bl{$\dn$} &
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   438
%     \bl{$if\;n = 0 \wedge m = 0\;then\;\ZERO\; else$}\\
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   439
%  \multicolumn{3}{l}{\bl{$if\;n = 0 \wedge m > 0\;then\;(der\,c\,r)\cdot r^{\{..m-\liningnums{1}\}}$}}\\
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   440
%  \multicolumn{3}{l}{\bl{$\phantom{if\;n = 0 \wedge m > 0\;}else
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   441
%          \;(der\,c\,r)\cdot r^{\{n-\liningnums{1}..m-\liningnums{1}\}}$}}\\
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   442
%  \bl{$der\, c\, (\sim{}r)$}              & \bl{$\dn$} & $?$\\
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   443
%\end{tabular}
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   444
%\end{center}
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   445
%
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   446
%\end{frame}
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   447
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
528
68fab15cd6fb updated
cu
parents: 500
diff changeset
   448
664
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   449
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   450
%\begin{frame}[c]
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   451
%\frametitle{Coursework: CFUN}
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   452
%
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   453
%\begin{center}
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   454
%\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   455
%  \bl{$nullable(CFUN(\_))$}  & \bl{$\dn$} & \bl{$false$}\\
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   456
%  \bl{$der\,c\,(CFUN(f))$}   & \bl{$\dn$} &
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   457
%     \bl{$if\;f(c)\;then\;\ONE\;else\;\ZERO$}\bigskip\\
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   458
%  \bl{$CHAR(c)$}                   & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;c=d)$}\\
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   459
%  \bl{$CSET([c_1,\ldots,c_n])$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;d\in [c_1,\ldots,c_n])$}\\
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   460
%  \bl{$ALL$}                   & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;true)$}\\                                                      
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   461
%\end{tabular}
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   462
%\end{center}
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   463
%
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   464
%\end{frame}
528
68fab15cd6fb updated
cu
parents: 500
diff changeset
   465
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
582
d236e75e1d55 updated
Christian Urban <urbanc@in.tum.de>
parents: 550
diff changeset
   466
 
528
68fab15cd6fb updated
cu
parents: 500
diff changeset
   467
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
68fab15cd6fb updated
cu
parents: 500
diff changeset
   468
\begin{frame}[t]
68fab15cd6fb updated
cu
parents: 500
diff changeset
   469
\frametitle{Lexer, Parser}
68fab15cd6fb updated
cu
parents: 500
diff changeset
   470
\mbox{}\\[-16mm]\mbox{}
68fab15cd6fb updated
cu
parents: 500
diff changeset
   471
68fab15cd6fb updated
cu
parents: 500
diff changeset
   472
\begin{center}
68fab15cd6fb updated
cu
parents: 500
diff changeset
   473
  \begin{tikzpicture}[scale=1,
68fab15cd6fb updated
cu
parents: 500
diff changeset
   474
                      node/.style={
68fab15cd6fb updated
cu
parents: 500
diff changeset
   475
                      rectangle,rounded corners=3mm,
68fab15cd6fb updated
cu
parents: 500
diff changeset
   476
                      very thick,draw=black!50,
68fab15cd6fb updated
cu
parents: 500
diff changeset
   477
                      minimum height=18mm, minimum width=20mm,
68fab15cd6fb updated
cu
parents: 500
diff changeset
   478
                      top color=white,bottom color=black!20}]
68fab15cd6fb updated
cu
parents: 500
diff changeset
   479
  \node (0) at (-2.3,0) {}; 
68fab15cd6fb updated
cu
parents: 500
diff changeset
   480
  
68fab15cd6fb updated
cu
parents: 500
diff changeset
   481
  \node (A) at (0,0)  [node] {};
68fab15cd6fb updated
cu
parents: 500
diff changeset
   482
  \node [below right] at (A.north west) {lexer};
68fab15cd6fb updated
cu
parents: 500
diff changeset
   483
68fab15cd6fb updated
cu
parents: 500
diff changeset
   484
  \node (B) at (3,0)  [node] {};
68fab15cd6fb updated
cu
parents: 500
diff changeset
   485
  \node [below right=1mm] at (B.north west) 
68fab15cd6fb updated
cu
parents: 500
diff changeset
   486
    {\mbox{}\hspace{-1mm}parser};
68fab15cd6fb updated
cu
parents: 500
diff changeset
   487
68fab15cd6fb updated
cu
parents: 500
diff changeset
   488
  \node (C) at (6,0)  [node] {};
68fab15cd6fb updated
cu
parents: 500
diff changeset
   489
  \node [below right] at (C.north west) 
68fab15cd6fb updated
cu
parents: 500
diff changeset
   490
    {\mbox{}\hspace{-1mm}code gen};
68fab15cd6fb updated
cu
parents: 500
diff changeset
   491
68fab15cd6fb updated
cu
parents: 500
diff changeset
   492
  \node (1) at (8.4,0) {}; 
68fab15cd6fb updated
cu
parents: 500
diff changeset
   493
68fab15cd6fb updated
cu
parents: 500
diff changeset
   494
  \draw [->,line width=4mm] (0) -- (A); 
68fab15cd6fb updated
cu
parents: 500
diff changeset
   495
  \draw [->,line width=4mm] (A) -- (B); 
68fab15cd6fb updated
cu
parents: 500
diff changeset
   496
  \draw [->,line width=4mm] (B) -- (C); 
68fab15cd6fb updated
cu
parents: 500
diff changeset
   497
  \draw [->,line width=4mm] (C) -- (1); 
68fab15cd6fb updated
cu
parents: 500
diff changeset
   498
  \end{tikzpicture}
68fab15cd6fb updated
cu
parents: 500
diff changeset
   499
  \end{center}
68fab15cd6fb updated
cu
parents: 500
diff changeset
   500
  
68fab15cd6fb updated
cu
parents: 500
diff changeset
   501
Today a parser.  
68fab15cd6fb updated
cu
parents: 500
diff changeset
   502
  
68fab15cd6fb updated
cu
parents: 500
diff changeset
   503
\end{frame}
68fab15cd6fb updated
cu
parents: 500
diff changeset
   504
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   505
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   506
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   507
\begin{frame}[c]
550
71fc4a7a7039 updated
Christian Urban <urbanc@in.tum.de>
parents: 529
diff changeset
   508
\frametitle{What Parsing is Not}
71fc4a7a7039 updated
Christian Urban <urbanc@in.tum.de>
parents: 529
diff changeset
   509
71fc4a7a7039 updated
Christian Urban <urbanc@in.tum.de>
parents: 529
diff changeset
   510
Usually parsing does not check semantic correctness, e.g.
71fc4a7a7039 updated
Christian Urban <urbanc@in.tum.de>
parents: 529
diff changeset
   511
71fc4a7a7039 updated
Christian Urban <urbanc@in.tum.de>
parents: 529
diff changeset
   512
\begin{itemize}
71fc4a7a7039 updated
Christian Urban <urbanc@in.tum.de>
parents: 529
diff changeset
   513
\item  whether a function is not used before it
71fc4a7a7039 updated
Christian Urban <urbanc@in.tum.de>
parents: 529
diff changeset
   514
  is defined
71fc4a7a7039 updated
Christian Urban <urbanc@in.tum.de>
parents: 529
diff changeset
   515
\item whether a function has the correct number of arguments 
71fc4a7a7039 updated
Christian Urban <urbanc@in.tum.de>
parents: 529
diff changeset
   516
  or are of correct type
71fc4a7a7039 updated
Christian Urban <urbanc@in.tum.de>
parents: 529
diff changeset
   517
\item whether a variable can be declared twice in a scope  
71fc4a7a7039 updated
Christian Urban <urbanc@in.tum.de>
parents: 529
diff changeset
   518
\end{itemize}  
71fc4a7a7039 updated
Christian Urban <urbanc@in.tum.de>
parents: 529
diff changeset
   519
71fc4a7a7039 updated
Christian Urban <urbanc@in.tum.de>
parents: 529
diff changeset
   520
\end{frame}
71fc4a7a7039 updated
Christian Urban <urbanc@in.tum.de>
parents: 529
diff changeset
   521
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
71fc4a7a7039 updated
Christian Urban <urbanc@in.tum.de>
parents: 529
diff changeset
   522
71fc4a7a7039 updated
Christian Urban <urbanc@in.tum.de>
parents: 529
diff changeset
   523
71fc4a7a7039 updated
Christian Urban <urbanc@in.tum.de>
parents: 529
diff changeset
   524
71fc4a7a7039 updated
Christian Urban <urbanc@in.tum.de>
parents: 529
diff changeset
   525
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
71fc4a7a7039 updated
Christian Urban <urbanc@in.tum.de>
parents: 529
diff changeset
   526
\begin{frame}[c]
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   527
\frametitle{Regular Languages}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   528
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   529
While regular expressions are very useful for lexing, there is
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   530
no regular expression that can recognise the language
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   531
\bl{$a^nb^n$}.\bigskip
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   532
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   533
\begin{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   534
\bl{$(((()()))())$} \;\;vs.\;\; \bl{$(((()()))()))$}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   535
\end{center}\bigskip\bigskip
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   536
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   537
\small
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   538
\noindent So we cannot find out with regular expressions
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   539
whether parentheses are matched or unmatched. Also regular
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   540
expressions are not recursive, e.g.~\bl{$(1 + 2) + 3$}.
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   541
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   542
\end{frame}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   543
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   544
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   545
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   546
\begin{frame}[c]
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   547
\frametitle{Hierarchy of Languages}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   548
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   549
\begin{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   550
\begin{tikzpicture}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   551
[rect/.style={draw=black!50, 
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   552
              top color=white,
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   553
              bottom color=black!20, 
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   554
              rectangle, 
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   555
              very thick, 
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   556
              rounded corners}, scale=1.2]
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   557
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   558
\draw (0,0) node [rect, text depth=39mm, text width=68mm] {all languages};
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   559
\draw (0,-0.4) node [rect, text depth=28.5mm, text width=64mm] {decidable languages};
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   560
\draw (0,-0.85) node [rect, text depth=17mm] {context sensitive languages};
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   561
\draw (0,-1.14) node [rect, text depth=9mm, text width=50mm] {context-free languages};
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   562
\draw (0,-1.4) node [rect] {regular languages};
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   563
\end{tikzpicture}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   564
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   565
\end{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   566
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   567
\end{frame}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   568
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   569
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   570
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   571
\begin{frame}[c]
360
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 358
diff changeset
   572
\frametitle{CF Grammars}
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   573
360
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 358
diff changeset
   574
A \alert{\bf context-free grammar} \bl{$G$} consists of
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   575
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   576
\begin{itemize}
664
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   577
\item a finite set of nonterminal symbols (e.g.~$\meta{A}$ upper case)
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   578
\item a finite set terminal symbols or tokens (lower case)
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   579
\item a start symbol (which must be a nonterminal)
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   580
\item a set of rules
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   581
\begin{center}
451
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   582
\bl{$\meta{A} ::= \textit{rhs}$}
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   583
\end{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   584
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   585
where \bl{\textit{rhs}} are sequences involving terminals and nonterminals,
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   586
including the empty sequence \bl{$\epsilon$}.\medskip\pause
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   587
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   588
We also allow rules
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   589
\begin{center}
451
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   590
\bl{$\meta{A} ::= \textit{rhs}_1 | \textit{rhs}_2 | \ldots$}
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   591
\end{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   592
\end{itemize}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   593
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   594
\end{frame}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   595
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   596
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   597
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
582
d236e75e1d55 updated
Christian Urban <urbanc@in.tum.de>
parents: 550
diff changeset
   598
\begin{frame}[t]
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   599
\frametitle{Palindromes}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   600
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   601
A grammar for palindromes over the alphabet~\bl{$\{a,b\}$}:
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   602
451
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   603
\bl{\begin{plstx}[margin=3cm]
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   604
: \meta{S} ::= a\cdot\meta{S}\cdot a\\
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   605
: \meta{S} ::= b\cdot\meta{S}\cdot b\\
588
a4646557016d updated
Christian Urban <urbanc@in.tum.de>
parents: 583
diff changeset
   606
: \meta{S} ::= a\\
a4646557016d updated
Christian Urban <urbanc@in.tum.de>
parents: 583
diff changeset
   607
: \meta{S} ::= b\\
a4646557016d updated
Christian Urban <urbanc@in.tum.de>
parents: 583
diff changeset
   608
: \meta{S} ::= \epsilon\\
451
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   609
\end{plstx}}\pause
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   610
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   611
or
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   612
451
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   613
\bl{\begin{plstx}[margin=2cm]
588
a4646557016d updated
Christian Urban <urbanc@in.tum.de>
parents: 583
diff changeset
   614
: \meta{S} ::=  a\cdot \meta{S}\cdot a | b\cdot \meta{S}\cdot b | a | b | \epsilon\\
451
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   615
\end{plstx}}\pause\bigskip
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   616
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   617
\small
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   618
Can you find the grammar rules for matched parentheses?
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   619
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   620
\end{frame}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   621
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   622
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   623
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   624
\begin{frame}[c]
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   625
\frametitle{Arithmetic Expressions}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   626
451
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   627
\bl{\begin{plstx}[margin=3cm,one per line]
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   628
: \meta{E} ::=  num\_token 
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   629
   | \meta{E} \cdot + \cdot \meta{E} 
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   630
   | \meta{E} \cdot - \cdot \meta{E} 
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   631
   | \meta{E} \cdot * \cdot \meta{E} 
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   632
   | ( \cdot \meta{E} \cdot ) \\
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   633
\end{plstx}}\pause
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   634
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   635
\bl{\texttt{1 + 2 * 3 + 4}}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   636
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   637
\end{frame}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   638
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   639
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   640
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   641
\begin{frame}[c]
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   642
\frametitle{A CFG Derivation}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   643
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   644
\begin{enumerate}
451
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   645
\item Begin with a string containing only the start symbol, say \bl{\meta{S}}\bigskip
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   646
\item Replace any nonterminal \bl{\meta{X}} in the string by the
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   647
right-hand side of some production \bl{$\meta{X} ::= \textit{rhs}$}\bigskip
582
d236e75e1d55 updated
Christian Urban <urbanc@in.tum.de>
parents: 550
diff changeset
   648
\item Repeat 2 until there are no nonterminals left
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   649
\end{enumerate}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   650
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   651
\begin{center}
451
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   652
\bl{$\meta{S} \rightarrow \ldots \rightarrow \ldots  \rightarrow \ldots  \rightarrow \ldots $}
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   653
\end{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   654
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   655
\end{frame}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   656
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   657
  
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   658
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
451
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   659
\begin{frame}[t]
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   660
\frametitle{Example Derivation}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   661
451
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   662
\bl{\begin{plstx}[margin=2cm]
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   663
: \meta{S} ::=  \epsilon | a\cdot \meta{S}\cdot a | b\cdot \meta{S}\cdot b \\
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   664
\end{plstx}}\bigskip
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   665
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   666
\begin{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   667
\begin{tabular}{lcl}
451
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   668
\bl{\meta{S}} & \bl{$\rightarrow$} & \bl{$a\meta{S}a$}\\
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   669
              & \bl{$\rightarrow$} & \bl{$ab\meta{S}ba$}\\
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   670
              & \bl{$\rightarrow$} & \bl{$aba\meta{S}aba$}\\
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   671
              & \bl{$\rightarrow$} & \bl{$abaaba$}\\
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   672
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   673
 
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   674
\end{tabular}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   675
\end{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   676
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   677
\end{frame}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   678
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   679
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   680
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
451
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   681
\begin{frame}[t]
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   682
\frametitle{Example Derivation}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   683
451
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   684
\bl{\begin{plstx}[margin=3cm,one per line]
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   685
: \meta{E} ::=  num\_token 
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   686
   | \meta{E} \cdot + \cdot \meta{E} 
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   687
   | \meta{E} \cdot - \cdot \meta{E} 
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   688
   | \meta{E} \cdot * \cdot \meta{E} 
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   689
   | ( \cdot \meta{E} \cdot ) \\
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   690
\end{plstx}}
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   691
451
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   692
\small
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   693
\begin{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   694
\begin{tabular}{@{}c@{}c@{}}
451
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   695
\begin{tabular}{@{\hspace{-2mm}}l@{\hspace{1mm}}l@{\hspace{1mm}}l@{\hspace{4mm}}}
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   696
\bl{\meta{E}} & \bl{$\rightarrow$} & \bl{$\meta{E}*\meta{E}$}\\
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   697
              & \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}*\meta{E}$}\\
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   698
              & \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}*\meta{E}+\meta{E}$}\\
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   699
              & \bl{$\rightarrow^+$} & \bl{$1+2*3+4$}\\
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   700
\end{tabular} &\pause
451
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   701
\begin{tabular}{@{}l@{\hspace{0mm}}l@{\hspace{1mm}}l}
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   702
\bl{$\meta{E}$} & \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}$}\\
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   703
                & \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}+\meta{E}$}\\
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   704
                & \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}*\meta{E}+\meta{E}$}\\
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   705
                & \bl{$\rightarrow^+$} & \bl{$1+2*3+4$}\\
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   706
\end{tabular}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   707
\end{tabular}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   708
\end{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   709
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   710
\end{frame}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   711
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   712
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   713
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   714
\begin{frame}[c]
664
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
   715
\frametitle{Context Sensitive Grammars}
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   716
360
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 358
diff changeset
   717
It is much harder to find out whether a string is parsed
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 358
diff changeset
   718
by a context sensitive grammar:
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   719
451
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   720
\bl{\begin{plstx}[margin=2cm]
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   721
: \meta{S} ::= b\meta{S}\meta{A}\meta{A} | \epsilon\\
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   722
: \meta{A} ::= a\\
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   723
: b\meta{A} ::= \meta{A}b\\
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   724
\end{plstx}}\pause
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   725
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   726
\begin{center}
451
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   727
\bl{$\meta{S} \rightarrow\ldots\rightarrow^? ababaa$}
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   728
\end{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   729
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   730
\end{frame}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   731
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   732
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   733
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   734
\begin{frame}[c]
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   735
\frametitle{Language of a CFG}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   736
451
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   737
Let \bl{$G$} be a context-free grammar with start symbol \bl{\meta{S}}. 
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   738
Then the language \bl{$L(G)$} is:
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   739
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   740
\begin{center}
451
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   741
\bl{$\{c_1\ldots c_n \;|\; \forall i.\; c_i \in T \wedge \meta{S} \rightarrow^* c_1\ldots c_n \}$}
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   742
\end{center}\pause
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   743
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   744
\begin{itemize}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   745
\item Terminals, because there are no rules for replacing them.
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   746
\item Once generated, terminals are ``permanent''.
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   747
\item Terminals ought to be tokens of the language\\
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   748
(but can also be strings).
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   749
\end{itemize}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   750
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   751
\end{frame}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   752
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   753
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   754
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
451
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   755
\begin{frame}[t]
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   756
\frametitle{Parse Trees}
582
d236e75e1d55 updated
Christian Urban <urbanc@in.tum.de>
parents: 550
diff changeset
   757
\mbox{}\\[-12mm]
451
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   758
593
bb24d4e207b6 updated
Christian Urban <urbanc@in.tum.de>
parents: 588
diff changeset
   759
\bl{\begin{plstx}: \meta{E} ::= \meta{T} | \meta{T} \cdot + \cdot \meta{E} |  \meta{T} \cdot - \cdot \meta{E}\\
529
5c28e4134ee1 updated
cu
parents: 528
diff changeset
   760
: \meta{T} ::= \meta{F} | \meta{F} \cdot * \cdot \meta{T}\\
5c28e4134ee1 updated
cu
parents: 528
diff changeset
   761
: \meta{F} ::= num\_token | ( \cdot \meta{E} \cdot )\\
451
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   762
\end{plstx}}
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   763
451
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   764
\begin{center}\small
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   765
\begin{tikzpicture}[level distance=8mm, blue]
451
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   766
  \node {$\meta{E}$}
529
5c28e4134ee1 updated
cu
parents: 528
diff changeset
   767
    child {node {$\meta{T}$} 
451
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   768
     child {node {$\meta{T}$} 
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   769
                 child {node {(\,$\meta{E}$\,)}
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   770
                            child {node{$\meta{F}$ *{} $\meta{F}$}
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   771
                                  child {node {$\meta{T}$} child {node {2}}}
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   772
                                  child {node {$\meta{T}$} child {node {3}}} 
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   773
                               }
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   774
                          }
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   775
              }
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   776
     child {node {+}}
451
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   777
     child {node {$\meta{T}$}
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   778
       child {node {(\,$\meta{E}$\,)} 
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   779
       child {node {$\meta{F}$}
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   780
       child {node {$\meta{T}$ +{} $\meta{T}$}
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   781
                    child {node {3}}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   782
                    child {node {4}} 
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   783
                 }
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   784
                 }}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   785
    }};
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   786
\end{tikzpicture}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   787
\end{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   788
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   789
\begin{textblock}{5}(1, 6.5)
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   790
\bl{\texttt{(2*3)+(3+4)}}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   791
\end{textblock}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   792
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   793
\end{frame}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   794
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   795
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   796
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
451
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   797
\begin{frame}[t]
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   798
\frametitle{Arithmetic Expressions}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   799
451
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   800
\bl{\begin{plstx}[margin=3cm,one per line]
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   801
: \meta{E} ::=  num\_token 
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   802
   | \meta{E} \cdot + \cdot \meta{E} 
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   803
   | \meta{E} \cdot - \cdot \meta{E} 
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   804
   | \meta{E} \cdot * \cdot \meta{E} 
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   805
   | ( \cdot \meta{E} \cdot ) \\
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   806
\end{plstx}}\pause\bigskip
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   807
451
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   808
A CFG is \alert{\bf left-recursive} if it has a nonterminal \bl{$\meta{E}$} such
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   809
that \bl{$\meta{E} \rightarrow^+ \meta{E}\cdot \ldots$}
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   810
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   811
\end{frame}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   812
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   813
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   814
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
451
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   815
\begin{frame}[t]
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   816
\frametitle{Ambiguous Grammars}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   817
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   818
A grammar is \alert{\bf ambiguous} if there is a string that
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   819
has at least two different parse trees.
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   820
451
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   821
\bl{\begin{plstx}[margin=3cm,one per line]: \meta{E} ::=  num\_token 
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   822
   | \meta{E} \cdot + \cdot \meta{E} 
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   823
   | \meta{E} \cdot - \cdot \meta{E} 
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   824
   | \meta{E} \cdot * \cdot \meta{E} 
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   825
   | ( \cdot \meta{E} \cdot ) \\
4a5876f321ae updated
Christian Urban <urbanc@in.tum.de>
parents: 445
diff changeset
   826
\end{plstx}}
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   827
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   828
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   829
\bl{\texttt{1 + 2 * 3 + 4}}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   830
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   831
\end{frame}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   832
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   833
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   834
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   835
\begin{frame}[c]
582
d236e75e1d55 updated
Christian Urban <urbanc@in.tum.de>
parents: 550
diff changeset
   836
\frametitle{`Dangling' Else}
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   837
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   838
Another ambiguous grammar:\bigskip
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   839
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   840
\begin{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   841
\bl{\begin{tabular}{lcl}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   842
$E$ & $\rightarrow$ &  if $E$ then $E$\\
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   843
 & $|$ &  if $E$ then $E$ else $E$ \\
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   844
 & $|$ &  \ldots
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   845
\end{tabular}}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   846
\end{center}\bigskip
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   847
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   848
\bl{\texttt{if a then if x then y else c}}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   849
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   850
\end{frame}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   851
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   852
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   853
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   854
\begin{frame}[c]
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   855
\frametitle{Parser Combinators}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   856
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   857
One of the simplest ways to implement a parser, see
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   858
{\small\url{https://vimeo.com/142341803}}\bigskip
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   859
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   860
Parser combinators: \bigskip
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   861
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   862
\begin{minipage}{1.1\textwidth}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   863
\begin{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   864
\mbox{}\hspace{-12mm}\mbox{}$\underbrace{\text{list of tokens}}_{\text{input}}$ \bl{$\Rightarrow$} 
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   865
$\underbrace{\text{set of (parsed input, unparsed input)}}_{\text{output}}$
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   866
\end{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   867
\end{minipage}\bigskip
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   868
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   869
\begin{itemize}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   870
\item atomic parsers
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   871
\item sequencing
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   872
\item alternative
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   873
\item semantic action
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   874
\end{itemize}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   875
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   876
\end{frame}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   877
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   878
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   879
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   880
\begin{frame}[c]
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   881
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   882
Atomic parsers, for example, number tokens
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   883
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   884
\begin{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   885
\bl{$\texttt{Num(123)}::rest \;\Rightarrow\; \{(\texttt{Num(123)}, rest)\}$} 
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   886
\end{center}\bigskip
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   887
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   888
\begin{itemize}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   889
\item you consume one or more token from the\\ 
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   890
  input (stream)
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   891
\item also works for characters and strings
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   892
\end{itemize}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   893
\end{frame}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   894
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   895
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   896
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   897
\begin{frame}[c]
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   898
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   899
Alternative parser (code \bl{$p\;||\;q$})\bigskip
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   900
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   901
\begin{itemize}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   902
\item apply \bl{$p$} and also \bl{$q$}; then combine 
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   903
  the outputs
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   904
\end{itemize}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   905
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   906
\begin{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   907
\large \bl{$p(\text{input}) \cup q(\text{input})$}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   908
\end{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   909
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   910
\end{frame}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   911
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   912
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   913
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   914
\begin{frame}[c]
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   915
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   916
Sequence parser (code \bl{$p\sim q$})\bigskip
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   917
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   918
\begin{itemize}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   919
\item apply first \bl{$p$} producing a set of pairs
528
68fab15cd6fb updated
cu
parents: 500
diff changeset
   920
\item then apply \bl{$q$} to the unparsed part
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   921
\item then combine the results:\medskip 
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   922
\begin{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   923
((output$_1$, output$_2$), unparsed part)
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   924
\end{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   925
\end{itemize}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   926
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   927
\begin{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   928
\begin{tabular}{l}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   929
\large \bl{$\{((o_1, o_2), u_2) \;|\;$}\\[2mm] 
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   930
\large\mbox{}\hspace{15mm} \bl{$(o_1, u_1) \in p(\text{input}) \wedge$}\\[2mm]
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   931
\large\mbox{}\hspace{15mm} \bl{$(o_2, u_2) \in q(u_1)\}$}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   932
\end{tabular}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   933
\end{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   934
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   935
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   936
\end{frame}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   937
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   938
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   939
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   940
\begin{frame}[c]
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   941
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   942
Function parser (code \bl{$p \Rightarrow f\;$})\bigskip
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   943
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   944
\begin{itemize}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   945
\item apply \bl{$p$} producing a set of pairs
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   946
\item then apply the function \bl{$f$} to each first component
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   947
\end{itemize}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   948
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   949
\begin{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   950
\begin{tabular}{l}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   951
\large \bl{$\{(f(o_1), u_1) \;|\; (o_1, u_1) \in p(\text{input})\}$}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   952
\end{tabular}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   953
\end{center}\bigskip\bigskip\pause
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   954
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   955
\bl{$f$} is the semantic action (``what to do with the parsed input'')
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   956
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   957
\end{frame}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   958
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   959
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   960
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   961
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   962
\mode<presentation>{
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   963
\begin{frame}[c]
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   964
\frametitle{\begin{tabular}{c}Semantic Actions\end{tabular}}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   965
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   966
Addition
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   967
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   968
\begin{center}
582
d236e75e1d55 updated
Christian Urban <urbanc@in.tum.de>
parents: 550
diff changeset
   969
\bl{$\meta{T} \sim + \sim \meta{E} \Rightarrow \underbrace{f\,((x,y), z) \Rightarrow x + z}_{\text{semantic action}}$}
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   970
\end{center}\pause
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   971
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   972
Multiplication
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   973
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   974
\begin{center}
582
d236e75e1d55 updated
Christian Urban <urbanc@in.tum.de>
parents: 550
diff changeset
   975
\bl{$\meta{F} \sim * \sim \meta{T} \Rightarrow f\,((x,y), z) \Rightarrow x * z$}
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   976
\end{center}\pause
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   977
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   978
Parenthesis
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   979
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   980
\begin{center}
582
d236e75e1d55 updated
Christian Urban <urbanc@in.tum.de>
parents: 550
diff changeset
   981
\bl{$\text{(} \sim \meta{E} \sim \text{)} \Rightarrow f\,((x,y), z) \Rightarrow y$}
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   982
\end{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   983
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   984
\end{frame}}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   985
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   986
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   987
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   988
\begin{frame}[c]
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   989
\frametitle{Types of Parsers}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   990
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   991
\begin{itemize}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   992
\item {\bf Sequencing}: if \bl{$p$} returns results of type \bl{$T$}, and \bl{$q$} results of type \bl{$S$},
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   993
then \bl{$p \sim q$} returns results of type
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   994
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   995
\begin{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   996
\bl{$T \times S$}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   997
\end{center}\pause
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   998
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
   999
\item {\bf Alternative}: if \bl{$p$} returns results of type \bl{$T$} then  \bl{$q$} \alert{must} also have results of type \bl{$T$},
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1000
and \bl{$p \;||\; q$} returns results of type
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1001
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1002
\begin{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1003
\bl{$T$}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1004
\end{center}\pause
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1005
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1006
\item {\bf Semantic Action}: if \bl{$p$} returns results of type \bl{$T$} and \bl{$f$} is a function from
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1007
\bl{$T$} to \bl{$S$}, then
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1008
\bl{$p \Rightarrow f$} returns results of type
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1009
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1010
\begin{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1011
\bl{$S$}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1012
\end{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1013
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1014
\end{itemize}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1015
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1016
\end{frame}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1017
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1018
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1019
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1020
\begin{frame}[c]
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1021
\frametitle{Input Types of Parsers}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1022
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1023
\begin{itemize}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1024
\item input: \alert{token list}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1025
\item output: set of (output\_type, \alert{token list})
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1026
\end{itemize}\bigskip\pause
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1027
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1028
actually it can be any input type as long as it is a kind of
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1029
sequence (for example a string)
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1030
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1031
\end{frame}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1032
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1033
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1034
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1035
\begin{frame}[c]
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1036
\frametitle{Scannerless Parsers}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1037
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1038
\begin{itemize}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1039
\item input: \alert{string}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1040
\item output: set of (output\_type, \alert{string})
664
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
  1041
\end{itemize}\bigskip\bigskip
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1042
664
dc2f5eb33a9a updated
Christian Urban <urbanc@in.tum.de>
parents: 593
diff changeset
  1043
but using lexers is better because whitespaces or comments can be
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1044
filtered out; then input is a sequence of tokens
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1045
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1046
\end{frame}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1047
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1048
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1049
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1050
\begin{frame}[c]
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1051
\frametitle{Successful Parses}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1052
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1053
\begin{itemize}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1054
\item input: string
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1055
\item output: \alert{set of} (output\_type, string)
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1056
\end{itemize}\bigskip
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1057
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1058
a parse is successful whenever the input has been fully
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1059
``consumed'' (that is the second component is empty)
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1060
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1061
\end{frame}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1062
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1063
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1064
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1065
\begin{frame}[c]
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1066
\frametitle{Abstract Parser Class}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1067
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1068
\small
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1069
\lstinputlisting[language=Scala,xleftmargin=1mm]
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1070
 {../progs/app7.scala}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1071
\end{frame}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1072
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1073
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1074
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1075
\begin{frame}[c]
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1076
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1077
\small
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1078
\fontsize{10}{12}\selectfont
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1079
\lstinputlisting[language=Scala,xleftmargin=1mm]
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1080
  {../progs/app8.scala}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1081
\end{frame}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1082
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1083
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1084
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1085
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1086
\begin{frame}[c]
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1087
\frametitle{Two Grammars}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1088
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1089
Which languages are recognised by the following two grammars?
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1090
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1091
\begin{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1092
\bl{\begin{tabular}{lcl}
582
d236e75e1d55 updated
Christian Urban <urbanc@in.tum.de>
parents: 550
diff changeset
  1093
$\meta{S}$ & $\rightarrow$ &  $1 \cdot \meta{S} \cdot \meta{S}$\\
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1094
        & $|$ & $\epsilon$
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1095
\end{tabular}}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1096
\end{center}\bigskip
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1097
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1098
\begin{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1099
\bl{\begin{tabular}{lcl}
582
d236e75e1d55 updated
Christian Urban <urbanc@in.tum.de>
parents: 550
diff changeset
  1100
$\meta{U}$ & $\rightarrow$ &  $1 \cdot \meta{U}$\\
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1101
        & $|$ & $\epsilon$
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1102
\end{tabular}}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1103
\end{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1104
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1105
\end{frame}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1106
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1107
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1108
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1109
\begin{frame}[t]
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1110
\frametitle{Ambiguous Grammars}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1111
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1112
\begin{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1113
\begin{tikzpicture}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1114
\begin{axis}[xlabel={\pcode{1}s},ylabel={time in secs},
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1115
    enlargelimits=false,
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1116
    xtick={0,100,...,1000},
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1117
    xmax=1050,
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1118
    ymax=33,
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1119
    ytick={0,5,...,30},
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1120
    scaled ticks=false,
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1121
    axis lines=left,
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1122
    width=11cm,
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1123
    height=7cm, 
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1124
    legend entries={unambiguous,ambiguous},  
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1125
    legend pos=north east,
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1126
    legend cell align=left,
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1127
    x tick label style={font=\small,/pgf/number format/1000 sep={}}]
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1128
\addplot[blue,mark=*, mark options={fill=white}] 
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1129
  table {s-grammar1.data};
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1130
\only<2>{
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1131
  \addplot[red,mark=triangle*, mark options={fill=white}] 
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1132
  table {s-grammar2.data};}  
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1133
\end{axis}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1134
\end{tikzpicture}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1135
\end{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1136
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1137
\end{frame}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1138
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1139
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1140
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1141
\begin{frame}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1142
\frametitle{While-Language}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1143
\mbox{}\\[-23mm]\mbox{}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1144
370
a65767fe5d71 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 361
diff changeset
  1145
\bl{\begin{plstx}[rhs style=,one per line]: \meta{Stmt} ::= skip
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1146
         | \meta{Id} := \meta{AExp}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1147
         | if \meta{BExp} then \meta{Block} else \meta{Block}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1148
         | while \meta{BExp} do \meta{Block}\\
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1149
: \meta{Stmts} ::= \meta{Stmt} ; \meta{Stmts}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1150
          | \meta{Stmt}\\
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1151
: \meta{Block} ::= \{ \meta{Stmts} \}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1152
          | \meta{Stmt}\\
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1153
: \meta{AExp} ::= \ldots\\
370
a65767fe5d71 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 361
diff changeset
  1154
: \meta{BExp} ::= \ldots\\\end{plstx}}
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1155
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1156
\end{frame}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1157
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1158
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1159
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1160
\begin{frame}[c]
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1161
\frametitle{An Interpreter}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1162
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1163
\begin{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1164
\bl{\begin{tabular}{l}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1165
$\{$\\
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1166
\;\;$x := 5 \text{;}$\\
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1167
\;\;$y := x * 3\text{;}$\\
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1168
\;\;$y := x * 4\text{;}$\\
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1169
\;\;$x := u * 3$\\
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1170
$\}$
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1171
\end{tabular}}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1172
\end{center}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1173
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1174
\begin{itemize}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1175
\item the interpreter has to record the value of \bl{$x$} before assigning a value to \bl{$y$}\pause
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1176
\item \bl{\texttt{eval(stmt, env)}}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1177
\end{itemize}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1178
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1179
\end{frame}
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1180
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1181
465
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1182
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1183
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1184
\mode<presentation>{
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1185
\begin{frame}[c]
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1186
\frametitle{\begin{tabular}{c}Interpreter\end{tabular}}
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1187
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1188
\begin{center}
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1189
\bl{\begin{tabular}{@{}lcl@{}}
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1190
$\text{eval}(n, E)$ & $\dn$ & $n$\\
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1191
$\text{eval}(x, E)$ & $\dn$ & $E(x)$ \;\;\;\textcolor{black}{lookup \bl{$x$} in \bl{$E$}}\\
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1192
$\text{eval}(a_1 + a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) + \text{eval}(a_2, E)$\\
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1193
$\text{eval}(a_1 - a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) - \text{eval}(a_2, E)$\\
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1194
$\text{eval}(a_1 * a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) * \text{eval}(a_2, E)$\bigskip\\
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1195
$\text{eval}(a_1 = a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) = \text{eval}(a_2, E)$\\
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1196
$\text{eval}(a_1\,!\!= a_2, E)$ & $\dn$ & $\neg(\text{eval}(a_1, E) = \text{eval}(a_2, E))$\\
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1197
$\text{eval}(a_1 < a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) < \text{eval}(a_2, E)$\
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1198
\end{tabular}}
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1199
\end{center}
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1200
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1201
\end{frame}}
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1202
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1203
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1204
\mode<presentation>{
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1205
\begin{frame}[c]
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1206
\frametitle{\begin{tabular}{c}Interpreter (2)\end{tabular}}
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1207
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1208
\begin{center}
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1209
\bl{\begin{tabular}{@{}lcl@{}}
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1210
$\text{eval}(\text{skip}, E)$ & $\dn$ & $E$\\
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1211
$\text{eval}(x:=a, E)$ & $\dn$ & \bl{$E(x \mapsto \text{eval}(a, E))$}\\
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1212
\multicolumn{3}{@{}l@{}}{$\text{eval}(\text{if}\;b\;\text{then}\;cs_1\;\text{else}\;cs_2 , E) \dn$}\\
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1213
\multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{if}\;\text{eval}(b,E)\;\text{then}\;
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1214
\text{eval}(cs_1,E)$}\\
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1215
\multicolumn{3}{@{}l@{}}{\hspace{2cm}$\phantom{\text{if}\;\text{eval}(b,E)\;}\text{else}\;\text{eval}(cs_2,E)$}\\
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1216
\multicolumn{3}{@{}l@{}}{$\text{eval}(\text{while}\;b\;\text{do}\;cs, E) \dn$}\\
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1217
\multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{if}\;\text{eval}(b,E)$}\\
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1218
\multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{then}\;
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1219
\text{eval}(\text{while}\;b\;\text{do}\;cs, \text{eval}(cs,E))$}\\
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1220
\multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{else}\; E$}\\
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1221
$\text{eval}(\text{write}\; x, E)$ & $\dn$ & $\{\;\text{println}(E(x))\; ;\;E\;\}$\\
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1222
\end{tabular}}
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1223
\end{center}
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1224
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1225
\end{frame}}
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1226
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1227
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1228
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1229
\begin{frame}[c]
582
d236e75e1d55 updated
Christian Urban <urbanc@in.tum.de>
parents: 550
diff changeset
  1230
\frametitle{Test Program}
465
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1231
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1232
\mbox{}\\[-18mm]\mbox{}
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1233
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1234
{\lstset{language=While}%%\fontsize{10}{12}\selectfont
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1235
\texttt{\lstinputlisting{../progs/loops.while}}}
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1236
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1237
\end{frame}
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1238
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1239
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1240
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1241
\mode<presentation>{
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1242
\begin{frame}[t]
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1243
\frametitle{\begin{tabular}{c}Interpreted Code\end{tabular}}
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1244
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1245
\begin{center}
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1246
\begin{tikzpicture}
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1247
\begin{axis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=secs, legend style=small]
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1248
\addplot+[smooth] file {interpreted.data};
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1249
\end{axis}
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1250
\end{tikzpicture}
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1251
\end{center}
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1252
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1253
\end{frame}}
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1254
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1255
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1256
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1257
\mode<presentation>{
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1258
\begin{frame}[c]
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1259
\frametitle{\begin{tabular}{c}Java Virtual Machine\end{tabular}}
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1260
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1261
\begin{itemize}
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1262
\item introduced in 1995
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1263
\item is a stack-based VM (like Postscript, CLR of .Net)
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1264
\item contains a JIT compiler
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1265
\item many languages take advantage of JVM's infrastructure (JRE)
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1266
\item is garbage collected $\Rightarrow$ no buffer overflows
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1267
\item some languages compile to the JVM: Scala, Clojure\ldots
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1268
\end{itemize}
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1269
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1270
\end{frame}}
b5e1cfaf3319 updated
Christian Urban <urbanc@in.tum.de>
parents: 462
diff changeset
  1271
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
358
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1272
b3129cff41e9 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 290
diff changeset
  1273
44
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
  1274
\end{document}
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
  1275
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
  1276
%%% Local Variables:  
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
  1277
%%% mode: latex
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
  1278
%%% TeX-master: t
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
  1279
%%% End: 
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
  1280