# HG changeset patch # User Christian Urban # Date 1383104170 0 # Node ID 57df3d7b4a25eeca8113e4d58694c7beccd92c59 # Parent e60c4a9ba340789692fc82f26e267c6349c69c9a added slides diff -r e60c4a9ba340 -r 57df3d7b4a25 handouts/ho05.pdf Binary file handouts/ho05.pdf has changed diff -r e60c4a9ba340 -r 57df3d7b4a25 progs/app7.scala --- a/progs/app7.scala Tue Oct 29 12:24:22 2013 +0000 +++ b/progs/app7.scala Wed Oct 30 03:36:10 2013 +0000 @@ -4,13 +4,6 @@ def parse_all(ts: I) : Set[T] = for ((head, tail) <- parse(ts); if (tail.isEmpty)) yield head - - def || (right : => Parser[I, T]) : Parser[I, T] = - new AltParser(this, right) - def ==>[S] (f: => T => S) : Parser [I, S] = - new FunParser(this, f) - def ~[S] (right : => Parser[I, S]) : Parser[I, (T, S)] = - new SeqParser(this, right) } diff -r e60c4a9ba340 -r 57df3d7b4a25 slides/slides05.pdf Binary file slides/slides05.pdf has changed diff -r e60c4a9ba340 -r 57df3d7b4a25 slides/slides05.tex --- a/slides/slides05.tex Tue Oct 29 12:24:22 2013 +0000 +++ b/slides/slides05.tex Wed Oct 30 03:36:10 2013 +0000 @@ -592,75 +592,6 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\newcommand{\qq}{\mbox{\texttt{"}}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Grammars\end{tabular}} - -\begin{center} -\bl{\begin{tabular}{lcl} -$E$ & $\rightarrow$ & $F + (F \cdot \qq*\qq \cdot F) + (F \cdot \qq\backslash\qq \cdot F)$\\ -$F$ & $\rightarrow$ & $T + (T \cdot \qq\texttt{+}\qq \cdot T) + (T \cdot \qq\texttt{-}\qq \cdot T)$\\ -$T$ & $\rightarrow$ & $num + (\qq\texttt{(}\qq \cdot E \cdot \qq\texttt{)}\qq)$\\ -\end{tabular}} -\end{center} - -\bl{$E$}, \bl{$F$} and \bl{$T$} are non-terminals\\ -\bl{$E$} is start symbol\\ -\bl{$num$}, \bl{(}, \bl{)}, \bl{+} \ldots are terminals\bigskip\\ - - -\bl{\texttt{(2*3)+(3+4)}} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] - -\begin{center} -\bl{\begin{tabular}{lcl} -$E$ & $\rightarrow$ & $F + (F \cdot \qq*\qq \cdot F) + (F \cdot \qq\backslash\qq \cdot F)$\\ -$F$ & $\rightarrow$ & $T + (T \cdot \qq\texttt{+}\qq \cdot T) + (T \cdot \qq\texttt{-}\qq \cdot T)$\\ -$T$ & $\rightarrow$ & $num + (\qq\texttt{(}\qq \cdot E \cdot \qq\texttt{)}\qq)$\\ -\end{tabular}} -\end{center} - -\begin{center} -\begin{tikzpicture}[level distance=8mm, blue] - \node {E} - child {node {F} - child {node {T} - child {node {\qq(\qq\,E\,\qq)\qq} - child {node{F \qq*\qq{} F} - child {node {T} child {node {2}}} - child {node {T} child {node {3}}} - } - } - } - child {node {\qq+\qq}} - child {node {T} - child {node {\qq(\qq\,E\,\qq)\qq} - child {node {F} - child {node {T \qq+\qq{} T} - child {node {3}} - child {node {4}} - } - }} - }}; -\end{tikzpicture} -\end{center} - -\begin{textblock}{5}(1, 5) -\bl{\texttt{(2*3)+(3+4)}} -\end{textblock} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - \end{document} %%% Local Variables: diff -r e60c4a9ba340 -r 57df3d7b4a25 slides/slides06.pdf Binary file slides/slides06.pdf has changed diff -r e60c4a9ba340 -r 57df3d7b4a25 slides/slides06.tex --- a/slides/slides06.tex Tue Oct 29 12:24:22 2013 +0000 +++ b/slides/slides06.tex Wed Oct 30 03:36:10 2013 +0000 @@ -82,120 +82,52 @@ \newcommand{\bl}[1]{\textcolor{blue}{#1}} \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions -% The data files, written on the first run. -\begin{filecontents}{re-python.data} -1 0.029 -5 0.029 -10 0.029 -15 0.032 -16 0.042 -17 0.042 -18 0.055 -19 0.084 -20 0.136 -21 0.248 -22 0.464 -23 0.899 -24 1.773 -25 3.505 -26 6.993 -27 14.503 -28 29.307 -#29 58.886 -\end{filecontents} -\begin{filecontents}{re1.data} -1 0.00179 -2 0.00011 -3 0.00014 -4 0.00026 -5 0.00050 -6 0.00095 -7 0.00190 -8 0.00287 -9 0.00779 -10 0.01399 -11 0.01894 -12 0.03666 -13 0.07994 -14 0.08944 -15 0.02377 -16 0.07392 -17 0.22798 -18 0.65310 -19 2.11360 -20 6.31606 -21 21.46013 +\begin{filecontents}{s-grammar1.data} +1 0.01152 +51 0.07973 +101 0.09726 +151 0.09320 +201 0.10010 +251 0.16997 +301 0.26662 +351 0.46118 +401 0.62516 +451 0.87247 +501 1.16334 +551 1.71152 +601 2.10958 +651 2.44360 +701 2.98488 +751 3.50326 +801 4.11036 +851 4.93394 +901 5.77465 +951 7.39123 \end{filecontents} -\begin{filecontents}{re2.data} -1 0.00240 -2 0.00013 -3 0.00020 -4 0.00030 -5 0.00049 -6 0.00083 -7 0.00146 -8 0.00228 -9 0.00351 -10 0.00640 -11 0.01217 -12 0.02565 -13 0.01382 -14 0.02423 -15 0.05065 -16 0.06522 -17 0.02140 -18 0.05176 -19 0.18254 -20 0.51898 -21 1.39631 -22 2.69501 -23 8.07952 +\begin{filecontents}{s-grammar2.data} +1 0.01280 +2 0.00064 +3 0.00173 +4 0.00355 +5 0.00965 +6 0.02674 +7 0.06953 +8 0.11166 +9 0.18707 +10 0.09189 +11 0.12724 +12 0.24337 +13 0.59304 +14 1.53594 +15 4.01195 +16 10.73582 +17 29.51587 +#18 73.14163 \end{filecontents} -\begin{filecontents}{re-internal.data} -1 0.00069 -301 0.00700 -601 0.00297 -901 0.00470 -1201 0.01301 -1501 0.01175 -1801 0.01761 -2101 0.01787 -2401 0.02717 -2701 0.03932 -3001 0.03470 -3301 0.04349 -3601 0.05411 -3901 0.06181 -4201 0.07119 -4501 0.08578 -\end{filecontents} -\begin{filecontents}{re3.data} -1 0.001605 -501 0.131066 -1001 0.057885 -1501 0.136875 -2001 0.176238 -2501 0.254363 -3001 0.37262 -3501 0.500946 -4001 0.638384 -4501 0.816605 -5001 1.00491 -5501 1.232505 -6001 1.525672 -6501 1.757502 -7001 2.092784 -7501 2.429224 -8001 2.803037 -8501 3.463045 -9001 3.609 -9501 4.081504 -10001 4.54569 -\end{filecontents} \begin{document} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -239,9 +171,10 @@ \bl{$A \rightarrow \text{rhs}$} \end{center} -where \bl{rhs} are sequences involving terminals and nonterminals.\medskip\pause +where \bl{rhs} are sequences involving terminals and nonterminals, +including the empty sequence \bl{$\epsilon$}.\medskip\pause -We can also allow rules +We also allow rules \begin{center} \bl{$A \rightarrow \text{rhs}_1 | \text{rhs}_2 | \ldots$} \end{center} @@ -299,6 +232,111 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{\begin{tabular}{c}A CFG Derivation\end{tabular}} + +\begin{enumerate} +\item Begin with a string containing only the start symbol, say \bl{$S$}\bigskip +\item Replace any nonterminal \bl{$X$} in the string by the right-hand side of some production \bl{$X \rightarrow \text{rhs}$}\bigskip +\item Repeat 2 until there are no nonterminals +\end{enumerate} + +\begin{center} +\bl{$S \rightarrow \ldots \rightarrow \ldots \rightarrow \ldots \rightarrow \ldots $} +\end{center} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{\begin{tabular}{c}Example Derivation\end{tabular}} + +\begin{center} +\bl{\begin{tabular}{lcl} +$S$ & $\rightarrow$ & $\epsilon \;|\; a\cdot S\cdot a \;|\;b\cdot S\cdot b$ \\ +\end{tabular}} +\end{center}\bigskip + + +\begin{center} +\begin{tabular}{lcl} +\bl{$S$} & \bl{$\rightarrow$} & \bl{$aSa$}\\ + & \bl{$\rightarrow$} & \bl{$abSba$}\\ + & \bl{$\rightarrow$} & \bl{$abaSaba$}\\ + & \bl{$\rightarrow$} & \bl{$abaaba$}\\ + + +\end{tabular} +\end{center} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{\begin{tabular}{c}Example Derivation\end{tabular}} + +\begin{center} +\bl{\begin{tabular}{lcl} +$E$ & $\rightarrow$ & $num\_token$ \\ +$E$ & $\rightarrow$ & $E \cdot + \cdot E$ \\ +$E$ & $\rightarrow$ & $E \cdot - \cdot E$ \\ +$E$ & $\rightarrow$ & $E \cdot * \cdot E$ \\ +$E$ & $\rightarrow$ & $( \cdot E \cdot )$ +\end{tabular}} +\end{center}\bigskip + + +\begin{center} +\begin{tabular}{@{}c@{}c@{}} +\begin{tabular}{l@{\hspace{1mm}}l@{\hspace{1mm}}l} +\bl{$E$} & \bl{$\rightarrow$} & \bl{$E*E$}\\ + & \bl{$\rightarrow$} & \bl{$E+E*E$}\\ + & \bl{$\rightarrow$} & \bl{$E+E*E+E$}\\ + & \bl{$\rightarrow^+$} & \bl{$1+2*3+4$}\\ +\end{tabular} &\pause +\begin{tabular}{l@{\hspace{1mm}}l@{\hspace{1mm}}l} +\bl{$E$} & \bl{$\rightarrow$} & \bl{$E+E$}\\ + & \bl{$\rightarrow$} & \bl{$E+E+E$}\\ + & \bl{$\rightarrow$} & \bl{$E+E*E+E$}\\ + & \bl{$\rightarrow^+$} & \bl{$1+2*3+4$}\\ +\end{tabular} +\end{tabular} +\end{center} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{\begin{tabular}{c}Language of a CFG\end{tabular}} + +Let \bl{$G$} be a context-free grammar with start symbol \bl{$S$}. +Then the language \bl{$L(G)$} is: + +\begin{center} +\bl{$\{c_1\ldots c_n \;|\; \forall i.\; c_i \in T \wedge S \rightarrow^* c_1\ldots c_n \}$} +\end{center}\pause + +\begin{itemize} +\item Terminals, because there are no rules for replacing them. +\item Once generated, terminals are ``permanent''. +\item Terminals ought to be tokens of the language\\ +(but can also be strings). +\end{itemize} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \mode{ \begin{frame}[c] @@ -343,12 +381,36 @@ \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{\begin{tabular}{c}Arithmetic Expressions\end{tabular}} + +\begin{center} +\bl{\begin{tabular}{lcl} +$E$ & $\rightarrow$ & $num\_token$ \\ +$E$ & $\rightarrow$ & $E \cdot + \cdot E$ \\ +$E$ & $\rightarrow$ & $E \cdot - \cdot E$ \\ +$E$ & $\rightarrow$ & $E \cdot * \cdot E$ \\ +$E$ & $\rightarrow$ & $( \cdot E \cdot )$ +\end{tabular}} +\end{center}\pause\bigskip + +A CFG is \alert{left-recursive} if it has a nonterminal \bl{$E$} such +that \bl{$E \rightarrow^+ E\cdot \ldots$} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \mode{ \begin{frame}[c] \frametitle{\begin{tabular}{c}Ambiguous Grammars\end{tabular}} -A grammar is \alert{ambiguous} if there is a string that has at least parse trees. +A grammar is \alert{ambiguous} if there is a string that has at least two different parse trees. \begin{center} @@ -366,6 +428,362 @@ \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{\begin{tabular}{c}Dangling Else\end{tabular}} + +Another ambiguous grammar:\bigskip + +\begin{center} +\bl{\begin{tabular}{lcl} +$E$ & $\rightarrow$ & if $E$ then $E$\\ + & $|$ & if $E$ then $E$ else $E$ \\ + & $|$ & \ldots +\end{tabular}} +\end{center}\bigskip + +\bl{\texttt{if a then if x then y else c}} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{\begin{tabular}{c}Parser Combinators\end{tabular}} + +Parser combinators: \bigskip + +\begin{minipage}{1.1\textwidth} +\begin{center} +\mbox{}\hspace{-12mm}\mbox{}$\underbrace{\text{list of tokens}}_{\text{input}}$ \bl{$\Rightarrow$} +$\underbrace{\text{set of (parsed input, unparsed input)}}_{\text{output}}$ +\end{center} +\end{minipage}\bigskip + +\begin{itemize} +\item sequencing +\item alternative +\item semantic action +\end{itemize} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] + +Alternative parser (code \bl{$p\;||\;q$})\bigskip + +\begin{itemize} +\item apply \bl{$p$} and also \bl{$q$}; then combine the outputs +\end{itemize} + +\begin{center} +\large \bl{$p(\text{input}) \cup q(\text{input})$} +\end{center} + + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] + +Sequence parser (code \bl{$p\sim q$})\bigskip + +\begin{itemize} +\item apply first \bl{$p$} producing a set of pairs +\item then apply \bl{$q$} to the unparsed parts +\item then combine the results:\\ \mbox{}\;\;((output$_1$, output$_2$), unparsed part) +\end{itemize} + +\begin{center} +\begin{tabular}{l} +\large \bl{$\{((o_1, o_2), u_2) \;|\;$}\\[2mm] +\large\mbox{}\hspace{15mm} \bl{$(o_1, u_1) \in p(\text{input}) \wedge$}\\[2mm] +\large\mbox{}\hspace{15mm} \bl{$(o_2, u_2) \in q(u_1)\}$} +\end{tabular} +\end{center} + + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] + +Function parser (code \bl{$p \Rightarrow f$})\bigskip + +\begin{itemize} +\item apply \bl{$p$} producing a set of pairs +\item then apply the function \bl{$f$} to each first component +\end{itemize} + +\begin{center} +\begin{tabular}{l} +\large \bl{$\{(f(o_1), u_1) \;|\; (o_1, u_1) \in p(\text{input})\}$} +\end{tabular} +\end{center}\bigskip\bigskip\pause + +\bl{$f$} is the semantic action (``what to do with the parsed input'') + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{\begin{tabular}{c}Semantic Actions\end{tabular}} + +Addition + +\begin{center} +\bl{$T \sim + \sim E \Rightarrow \underbrace{f((x,y), z) \Rightarrow x + z}_{\text{semantic action}}$} +\end{center}\pause + +Multiplication + +\begin{center} +\bl{$F \sim * \sim T \Rightarrow f((x,y), z) \Rightarrow x * z$} +\end{center}\pause + +Parenthesis + +\begin{center} +\bl{$\text{(} \sim E \sim \text{)} \Rightarrow f((x,y), z) \Rightarrow y$} +\end{center} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{\begin{tabular}{c}Types of Parsers\end{tabular}} + +\begin{itemize} +\item {\bf Sequencing}: if \bl{$p$} returns results of type \bl{$T$}, and \bl{$q$} results of type \bl{$S$}, +then \bl{$p \sim q$} returns results of type + +\begin{center} +\bl{$T \times S$} +\end{center}\pause + +\item {\bf Alternative}: if \bl{$p$} returns results of type \bl{$T$} then \bl{$q$} \alert{must} also have results of type \bl{$T$}, +and \bl{$p \;||\; q$} returns results of type + +\begin{center} +\bl{$T$} +\end{center}\pause + +\item {\bf Semantic Action}: if \bl{$p$} returns results of type \bl{$T$} and \bl{$f$} is a function from +\bl{$T$} to \bl{$S$}, then +\bl{$p \Rightarrow f$} returns results of type + +\begin{center} +\bl{$S$} +\end{center} + +\end{itemize} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{\begin{tabular}{c}Input Types of Parsers\end{tabular}} + +\begin{itemize} +\item input: \alert{string} +\item output: set of (output\_type, \alert{string}) +\end{itemize}\bigskip\pause + +actually it can be any input type as long as it is a kind of sequence +(for example a string) + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{\begin{tabular}{c}Scannerless Parsers\end{tabular}} + +\begin{itemize} +\item input: \alert{string} +\item output: set of (output\_type, \alert{string}) +\end{itemize}\bigskip + +but lexers are better when whitespaces or comments need to be filtered out; +then input is a sequence of tokens + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{\begin{tabular}{c}Successful Parses\end{tabular}} + +\begin{itemize} +\item input: string +\item output: \alert{set of} (output\_type, string) +\end{itemize}\bigskip + +a parse is successful whenever the input has been +fully ``consumed'' (that is the second component is empty) + + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{Abstract Parsers} + +\mbox{\lstset{language=Scala}\fontsize{10}{12}\selectfont +\texttt{\lstinputlisting{../progs/app7.scala}}} +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +{\lstset{language=Scala}\fontsize{10}{12}\selectfont +\texttt{\lstinputlisting{../progs/app8.scala}}} +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{\begin{tabular}{c}Two Grammars\end{tabular}} + +Which languages are recognised by the following two grammars? + +\begin{center} +\bl{\begin{tabular}{lcl} +$S$ & $\rightarrow$ & $1 \cdot S \cdot S$\\ + & $|$ & $\epsilon$ +\end{tabular}} +\end{center}\bigskip + +\begin{center} +\bl{\begin{tabular}{lcl} +$U$ & $\rightarrow$ & $1 \cdot U$\\ + & $|$ & $\epsilon$ +\end{tabular}} +\end{center} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[t] +\frametitle{\begin{tabular}{c}Ambiguous Grammars\end{tabular}} + +\mbox{}\\[-25mm]\mbox{} + +\begin{center} +\begin{tikzpicture}[y=.2cm, x=.009cm] + %axis + \draw (0,0) -- coordinate (x axis mid) (1000,0); + \draw (0,0) -- coordinate (y axis mid) (0,30); + %ticks + \foreach \x in {0, 20, 100, 200,...,1000} + \draw (\x,1pt) -- (\x,-3pt) + node[anchor=north] {\small \x}; + \foreach \y in {0,5,...,30} + \draw (1pt,\y) -- (-3pt,\y) + node[anchor=east] {\small\y}; + %labels + \node[below=0.6cm] at (x axis mid) {\bl{1}s}; + \node[rotate=90, left=1.2cm] at (y axis mid) {secs}; + + %plots + \draw[color=blue] plot[mark=*, mark options={fill=white}] + file {s-grammar1.data}; + \only<2->{\draw[color=red] plot[mark=triangle*, mark options={fill=white} ] + file {s-grammar2.data};} + %legend + \begin{scope}[shift={(400,20)}] + \draw[color=blue] (0,0) -- + plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) + node[right]{\small unambiguous}; + \only<2->{\draw[yshift=\baselineskip, color=red] (0,0) -- + plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0) + node[right]{\small ambiguous};} + \end{scope} +\end{tikzpicture} +\end{center} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{\begin{tabular}{c}While-Language\end{tabular}} + + +\begin{center} +\bl{\begin{tabular}{@{}lcl@{}} +$Stmt$ & $\rightarrow$ & $\text{skip}$\\ + & $|$ & $Id := AExp$\\ + & $|$ & $\text{if}\; B\!Exp \;\text{then}\; Block \;\text{else}\; Block$\\ + & $|$ & $\text{while}\; B\!Exp \;\text{do}\; Block$\medskip\\ +$Stmts$ & $\rightarrow$ & $Stmt \;\text{;}\; Stmts$\\ + & $|$ & $Stmt$\medskip\\ +$Block$ & $\rightarrow$ & $\{ Stmts \}$\\ + & $|$ & $Stmt$\medskip\\ +$AExp$ & $\rightarrow$ & \ldots\\ +$BExp$ & $\rightarrow$ & \ldots\\ +\end{tabular}} +\end{center} + + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{\begin{tabular}{c}An Interpreter\end{tabular}} + +\begin{center} +\bl{\begin{tabular}{l} +$\{$\\ +\;\;$x := 5 \text{;}$\\ +\;\;$y := x * 3\text{;}$\\ +\;\;$y := x * 4\text{;}$\\ +\;\;$x := u * 3$\\ +$\}$ +\end{tabular}} +\end{center} + +\begin{itemize} +\item the interpreter has to record the value of \bl{$x$} before assigning a value to \bl{$y$}\pause +\item \bl{\text{eval}(stmt, env)} +\end{itemize} + + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \mode{