afl-material: slides/slides05.tex@d236e75e1d55 (annotated)

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

author	Christian Urban <urbanc@in.tum.de>
	Mon, 22 Oct 2018 23:37:11 +0100
changeset 582	d236e75e1d55
parent 550	71fc4a7a7039
child 583	200d2a3eb1b1
permissions	-rw-r--r--