1 \documentclass[dvipsnames,14pt,t]{beamer} |
|
2 \usepackage{beamerthemeplainculight} |
|
3 \usepackage[T1]{fontenc} |
|
4 \usepackage[latin1]{inputenc} |
|
5 \usepackage{mathpartir} |
|
6 \usepackage[absolute,overlay]{textpos} |
|
7 \usepackage{ifthen} |
|
8 \usepackage{tikz} |
|
9 \usepackage{pgf} |
|
10 \usepackage{calc} |
|
11 \usepackage{ulem} |
|
12 \usepackage{courier} |
|
13 \usepackage{listings} |
|
14 \renewcommand{\uline}[1]{#1} |
|
15 \usetikzlibrary{arrows} |
|
16 \usetikzlibrary{automata} |
|
17 \usetikzlibrary{shapes} |
|
18 \usetikzlibrary{shadows} |
|
19 \usetikzlibrary{positioning} |
|
20 \usetikzlibrary{calc} |
|
21 \usetikzlibrary{plotmarks} |
|
22 \usepackage{graphicx} |
|
23 |
|
24 \definecolor{javared}{rgb}{0.6,0,0} % for strings |
|
25 \definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments |
|
26 \definecolor{javapurple}{rgb}{0.5,0,0.35} % keywords |
|
27 \definecolor{javadocblue}{rgb}{0.25,0.35,0.75} % javadoc |
|
28 |
|
29 \lstset{language=Java, |
|
30 basicstyle=\ttfamily, |
|
31 keywordstyle=\color{javapurple}\bfseries, |
|
32 stringstyle=\color{javagreen}, |
|
33 commentstyle=\color{javagreen}, |
|
34 morecomment=[s][\color{javadocblue}]{/**}{*/}, |
|
35 numbers=left, |
|
36 numberstyle=\tiny\color{black}, |
|
37 stepnumber=1, |
|
38 numbersep=10pt, |
|
39 tabsize=2, |
|
40 showspaces=false, |
|
41 showstringspaces=false} |
|
42 |
|
43 \lstdefinelanguage{scala}{ |
|
44 morekeywords={abstract,case,catch,class,def,% |
|
45 do,else,extends,false,final,finally,% |
|
46 for,if,implicit,import,match,mixin,% |
|
47 new,null,object,override,package,% |
|
48 private,protected,requires,return,sealed,% |
|
49 super,this,throw,trait,true,try,% |
|
50 type,val,var,while,with,yield}, |
|
51 otherkeywords={=>,<-,<\%,<:,>:,\#,@}, |
|
52 sensitive=true, |
|
53 morecomment=[l]{//}, |
|
54 morecomment=[n]{/*}{*/}, |
|
55 morestring=[b]", |
|
56 morestring=[b]', |
|
57 morestring=[b]""" |
|
58 } |
|
59 |
|
60 \lstset{language=Scala, |
|
61 basicstyle=\ttfamily, |
|
62 keywordstyle=\color{javapurple}\bfseries, |
|
63 stringstyle=\color{javagreen}, |
|
64 commentstyle=\color{javagreen}, |
|
65 morecomment=[s][\color{javadocblue}]{/**}{*/}, |
|
66 numbers=left, |
|
67 numberstyle=\tiny\color{black}, |
|
68 stepnumber=1, |
|
69 numbersep=10pt, |
|
70 tabsize=2, |
|
71 showspaces=false, |
|
72 showstringspaces=false} |
|
73 |
|
74 % beamer stuff |
|
75 \renewcommand{\slidecaption}{AFL 08, King's College London, 21.~November 2012} |
|
76 \newcommand{\bl}[1]{\textcolor{blue}{#1}} |
|
77 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions |
|
78 |
|
79 |
|
80 % The data files, written on the first run. |
|
81 \begin{filecontents}{s-grammar1.data} |
|
82 1 0.01152 |
|
83 51 0.07973 |
|
84 101 0.09726 |
|
85 151 0.09320 |
|
86 201 0.10010 |
|
87 251 0.16997 |
|
88 301 0.26662 |
|
89 351 0.46118 |
|
90 401 0.62516 |
|
91 451 0.87247 |
|
92 501 1.16334 |
|
93 551 1.71152 |
|
94 601 2.10958 |
|
95 651 2.44360 |
|
96 701 2.98488 |
|
97 751 3.50326 |
|
98 801 4.11036 |
|
99 851 4.93394 |
|
100 901 5.77465 |
|
101 951 7.39123 |
|
102 \end{filecontents} |
|
103 |
|
104 \begin{filecontents}{s-grammar2.data} |
|
105 1 0.01280 |
|
106 2 0.00064 |
|
107 3 0.00173 |
|
108 4 0.00355 |
|
109 5 0.00965 |
|
110 6 0.02674 |
|
111 7 0.06953 |
|
112 8 0.11166 |
|
113 9 0.18707 |
|
114 10 0.09189 |
|
115 11 0.12724 |
|
116 12 0.24337 |
|
117 13 0.59304 |
|
118 14 1.53594 |
|
119 15 4.01195 |
|
120 16 10.73582 |
|
121 17 29.51587 |
|
122 #18 73.14163 |
|
123 \end{filecontents} |
|
124 |
|
125 |
|
126 \begin{document} |
|
127 |
|
128 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
129 \mode<presentation>{ |
|
130 \begin{frame}<1>[t] |
|
131 \frametitle{% |
|
132 \begin{tabular}{@ {}c@ {}} |
|
133 \\[-3mm] |
|
134 \LARGE Automata and \\[-2mm] |
|
135 \LARGE Formal Languages (8)\\[3mm] |
|
136 \end{tabular}} |
|
137 |
|
138 \normalsize |
|
139 \begin{center} |
|
140 \begin{tabular}{ll} |
|
141 Email: & christian.urban at kcl.ac.uk\\ |
|
142 Of$\!$fice: & S1.27 (1st floor Strand Building)\\ |
|
143 Slides: & KEATS (also home work is there)\\ |
|
144 \end{tabular} |
|
145 \end{center} |
|
146 |
|
147 |
|
148 \end{frame}} |
|
149 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
150 |
|
151 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
152 \mode<presentation>{ |
|
153 \begin{frame}[c] |
|
154 \frametitle{\begin{tabular}{c}Building a ``Web Browser''\end{tabular}} |
|
155 |
|
156 Using a lexer: assume the following regular expressions |
|
157 |
|
158 \begin{center} |
|
159 \bl{\begin{tabular}{lcl} |
|
160 $SY\!M$ & $\dn$ & $(\text{a}..\text{zA}..\text{Z0}..\text{9}..)$\\ |
|
161 $W\!O\!RD$ & $\dn$ & $SY\!M^+$\\ |
|
162 $BT\!AG$ & $\dn$ & $<\!W\!O\!RD\!>$\\ |
|
163 $ET\!AG$ & $\dn$ & $<\!/W\!O\!RD\!>$\\ |
|
164 $W\!HIT\!E$ & $\dn$ & $\texttt{" "} + \texttt{"}\slash{}n\texttt{"}$\\ |
|
165 \end{tabular}} |
|
166 \end{center} |
|
167 |
|
168 \end{frame}} |
|
169 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
170 |
|
171 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
172 \mode<presentation>{ |
|
173 \begin{frame}[c] |
|
174 \frametitle{\begin{tabular}{c}Interpreting a List of Tokens\end{tabular}} |
|
175 |
|
176 \begin{itemize} |
|
177 \item the text should be formatted consistently up to a specified width, say 60 characters |
|
178 \item potential linebreaks are inserted by the formatter (not the input) |
|
179 \item repeated whitespaces are ``condensed'' to a single whitepace |
|
180 \item \bl{$<\!p\!>$} \bl{$<\!\slash{}p\!>$} start/end paragraph |
|
181 \item \bl{$<\!b\!>$} \bl{$<\!\slash{}b\!>$} start/end bold |
|
182 \item \bl{$<\!red\!>$} \bl{$<\!\slash{}red\!>$} start/end red (cyan, etc) |
|
183 |
|
184 |
|
185 \end{itemize} |
|
186 |
|
187 \end{frame}} |
|
188 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
189 |
|
190 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
191 \mode<presentation>{ |
|
192 \begin{frame}[c] |
|
193 \frametitle{\begin{tabular}{c}Interpreting a List of Tokens\end{tabular}} |
|
194 |
|
195 The lexer cannot prevent errors like |
|
196 |
|
197 \begin{center} |
|
198 \bl{$<\!b\!>$} \ldots \bl{$<\!p\!>$} \ldots \bl{$<\!\slash{}b\!>$} \ldots \bl{$<\!\slash{}p\!>$} |
|
199 \end{center} |
|
200 |
|
201 or |
|
202 |
|
203 \begin{center} |
|
204 \bl{$<\!\slash{}b\!>$} \ldots \bl{$<\!b\!>$} |
|
205 \end{center} |
|
206 |
|
207 |
|
208 \end{frame}} |
|
209 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
210 |
|
211 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
212 \mode<presentation>{ |
|
213 \begin{frame}[c] |
|
214 \frametitle{\begin{tabular}{c}Parser Combinators\end{tabular}} |
|
215 |
|
216 Parser combinators: \bigskip |
|
217 |
|
218 \begin{minipage}{1.1\textwidth} |
|
219 \begin{center} |
|
220 \mbox{}\hspace{-12mm}\mbox{}$\underbrace{\text{list of tokens}}_{\text{input}}$ \bl{$\Rightarrow$} |
|
221 $\underbrace{\text{set of (parsed input, unparsed input)}}_{\text{output}}$ |
|
222 \end{center} |
|
223 \end{minipage}\bigskip |
|
224 |
|
225 \begin{itemize} |
|
226 \item sequencing |
|
227 \item alternative |
|
228 \item semantic action |
|
229 \end{itemize} |
|
230 |
|
231 \end{frame}} |
|
232 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
233 |
|
234 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
235 \mode<presentation>{ |
|
236 \begin{frame}[c] |
|
237 |
|
238 Alternative parser (code \bl{$p\;||\;q$})\bigskip |
|
239 |
|
240 \begin{itemize} |
|
241 \item apply \bl{$p$} and also \bl{$q$}; then combine the outputs |
|
242 \end{itemize} |
|
243 |
|
244 \begin{center} |
|
245 \large \bl{$p(\text{input}) \cup q(\text{input})$} |
|
246 \end{center} |
|
247 |
|
248 |
|
249 \end{frame}} |
|
250 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
251 |
|
252 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
253 \mode<presentation>{ |
|
254 \begin{frame}[c] |
|
255 |
|
256 Sequence parser (code \bl{$p\sim q$})\bigskip |
|
257 |
|
258 \begin{itemize} |
|
259 \item apply first \bl{$p$} producing a set of pairs |
|
260 \item then apply \bl{$q$} to the unparsed parts |
|
261 \item then combine the results:\\ \mbox{}\;\;((output$_1$, output$_2$), unparsed part) |
|
262 \end{itemize} |
|
263 |
|
264 \begin{center} |
|
265 \begin{tabular}{l} |
|
266 \large \bl{$\{((o_1, o_2), u_2) \;|\;$}\\[2mm] |
|
267 \large\mbox{}\hspace{15mm} \bl{$(o_1, u_1) \in p(\text{input}) \wedge$}\\[2mm] |
|
268 \large\mbox{}\hspace{15mm} \bl{$(o_2, u_2) \in q(u_1)\}$} |
|
269 \end{tabular} |
|
270 \end{center} |
|
271 |
|
272 |
|
273 \end{frame}} |
|
274 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
275 |
|
276 |
|
277 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
278 \mode<presentation>{ |
|
279 \begin{frame}[c] |
|
280 |
|
281 Function parser (code \bl{$p \Longrightarrow f$})\bigskip |
|
282 |
|
283 \begin{itemize} |
|
284 \item apply \bl{$p$} producing a set of pairs |
|
285 \item then apply the function \bl{$f$} to each first component |
|
286 \end{itemize} |
|
287 |
|
288 \begin{center} |
|
289 \begin{tabular}{l} |
|
290 \large \bl{$\{(f(o_1), u_1) \;|\; (o_1, u_1) \in p(\text{input})\}$} |
|
291 \end{tabular} |
|
292 \end{center}\bigskip\bigskip\pause |
|
293 |
|
294 \bl{$f$} is the semantic action (``what to do with the parsed input'') |
|
295 |
|
296 \end{frame}} |
|
297 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
298 |
|
299 |
|
300 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
301 \mode<presentation>{ |
|
302 \begin{frame}[c] |
|
303 |
|
304 Token parser:\bigskip |
|
305 |
|
306 \begin{itemize} |
|
307 \item if the input is |
|
308 |
|
309 \begin{center} |
|
310 \large \bl{$tok_1:: tok_2 :: \ldots :: tok_n$} |
|
311 \end{center} |
|
312 |
|
313 then return |
|
314 |
|
315 \begin{center} |
|
316 \large \bl{$\{(tok_1,\; tok_2 :: \ldots :: tok_n)\}$} |
|
317 \end{center} |
|
318 |
|
319 or |
|
320 |
|
321 \begin{center} |
|
322 \large \bl{$\{\}$} |
|
323 \end{center} |
|
324 |
|
325 if \bl{$tok_1$} is not the right token we are looking for |
|
326 \end{itemize} |
|
327 |
|
328 |
|
329 |
|
330 \end{frame}} |
|
331 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
332 |
|
333 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
334 \mode<presentation>{ |
|
335 \begin{frame}[c] |
|
336 |
|
337 Number-Token parser:\bigskip |
|
338 |
|
339 \begin{itemize} |
|
340 \item if the input is |
|
341 |
|
342 \begin{center} |
|
343 \large \bl{$num\_tok(42):: tok_2 :: \ldots :: tok_n$} |
|
344 \end{center} |
|
345 |
|
346 then return |
|
347 |
|
348 \begin{center} |
|
349 \large \bl{$\{(42,\; tok_2 :: \ldots :: tok_n)\}$} |
|
350 \end{center} |
|
351 |
|
352 or |
|
353 |
|
354 \begin{center} |
|
355 \large \bl{$\{\}$} |
|
356 \end{center} |
|
357 |
|
358 if \bl{$tok_1$} is not the right token we are looking for |
|
359 \end{itemize}\pause |
|
360 |
|
361 \begin{center} |
|
362 list of tokens \bl{$\Rightarrow$} set of (\alert{int}, list of tokens) |
|
363 \end{center} |
|
364 |
|
365 \end{frame}} |
|
366 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
367 |
|
368 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
369 \mode<presentation>{ |
|
370 \begin{frame}[c] |
|
371 |
|
372 \begin{itemize} |
|
373 \item if the input is |
|
374 |
|
375 \begin{center} |
|
376 \begin{tabular}{l} |
|
377 \large \bl{$num\_tok(42)::$}\\ |
|
378 \hspace{7mm}\large \bl{$num\_tok(3) ::$}\\ |
|
379 \hspace{14mm}\large \bl{$tok_3 :: \ldots :: tok_n$} |
|
380 \end{tabular} |
|
381 \end{center} |
|
382 |
|
383 and the parser is |
|
384 |
|
385 \begin{center} |
|
386 \bl{$ntp \sim ntp$} |
|
387 \end{center} |
|
388 |
|
389 the successful output will be |
|
390 |
|
391 \begin{center} |
|
392 \large \bl{$\{((42, 3),\; tok_2 :: \ldots :: tok_n)\}$} |
|
393 \end{center}\pause |
|
394 |
|
395 Now we can form |
|
396 \begin{center} |
|
397 \bl{$(ntp \sim ntp) \Longrightarrow f$} |
|
398 \end{center} |
|
399 |
|
400 where \bl{$f$} is the semantic action (``what to do with the pair'') |
|
401 |
|
402 \end{itemize} |
|
403 |
|
404 \end{frame}} |
|
405 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
406 |
|
407 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
408 \mode<presentation>{ |
|
409 \begin{frame}[c] |
|
410 \frametitle{\begin{tabular}{c}Semantic Actions\end{tabular}} |
|
411 |
|
412 Addition |
|
413 |
|
414 \begin{center} |
|
415 \bl{$T \sim + \sim E \Longrightarrow \underbrace{f((x,y), z) \Rightarrow x + z}_{\text{semantic action}}$} |
|
416 \end{center}\pause |
|
417 |
|
418 Multiplication |
|
419 |
|
420 \begin{center} |
|
421 \bl{$F \sim * \sim T \Longrightarrow f((x,y), z) \Rightarrow x * z$} |
|
422 \end{center}\pause |
|
423 |
|
424 Parenthesis |
|
425 |
|
426 \begin{center} |
|
427 \bl{$\text{(} \sim E \sim \text{)} \Longrightarrow f((x,y), z) \Rightarrow y$} |
|
428 \end{center} |
|
429 |
|
430 \end{frame}} |
|
431 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
432 |
|
433 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
434 \mode<presentation>{ |
|
435 \begin{frame}[c] |
|
436 \frametitle{\begin{tabular}{c}Types of Parsers\end{tabular}} |
|
437 |
|
438 \begin{itemize} |
|
439 \item {\bf Sequencing}: if \bl{$p$} returns results of type \bl{$T$}, and \bl{$q$} results of type \bl{$S$}, |
|
440 then \bl{$p \sim q$} returns results of type |
|
441 |
|
442 \begin{center} |
|
443 \bl{$T \times S$} |
|
444 \end{center}\pause |
|
445 |
|
446 \item {\bf Alternative}: if \bl{$p$} returns results of type \bl{$T$} then \bl{$q$} \alert{must} also have results of type \bl{$T$}, |
|
447 and \bl{$p \;||\; q$} returns results of type |
|
448 |
|
449 \begin{center} |
|
450 \bl{$T$} |
|
451 \end{center}\pause |
|
452 |
|
453 \item {\bf Semantic Action}: if \bl{$p$} returns results of type \bl{$T$} and \bl{$f$} is a function from |
|
454 \bl{$T$} to \bl{$S$}, then |
|
455 \bl{$p \Longrightarrow f$} returns results of type |
|
456 |
|
457 \begin{center} |
|
458 \bl{$S$} |
|
459 \end{center} |
|
460 |
|
461 \end{itemize} |
|
462 |
|
463 \end{frame}} |
|
464 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
465 |
|
466 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
467 \mode<presentation>{ |
|
468 \begin{frame}[c] |
|
469 \frametitle{\begin{tabular}{c}Input Types of Parsers\end{tabular}} |
|
470 |
|
471 \begin{itemize} |
|
472 \item input: \alert{list of tokens} |
|
473 \item output: set of (output\_type, \alert{list of tokens}) |
|
474 \end{itemize}\bigskip\pause |
|
475 |
|
476 actually it can be any input type as long as it is a kind of sequence |
|
477 (for example a string) |
|
478 |
|
479 \end{frame}} |
|
480 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
481 |
|
482 |
|
483 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
484 \mode<presentation>{ |
|
485 \begin{frame}[c] |
|
486 \frametitle{\begin{tabular}{c}Scannerless Parsers\end{tabular}} |
|
487 |
|
488 \begin{itemize} |
|
489 \item input: \alert{string} |
|
490 \item output: set of (output\_type, \alert{string}) |
|
491 \end{itemize}\bigskip |
|
492 |
|
493 but lexers are better when whitespaces or comments need to be filtered out |
|
494 |
|
495 \end{frame}} |
|
496 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
497 |
|
498 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
499 \mode<presentation>{ |
|
500 \begin{frame}[c] |
|
501 \frametitle{\begin{tabular}{c}Successful Parses\end{tabular}} |
|
502 |
|
503 \begin{itemize} |
|
504 \item input: string |
|
505 \item output: \alert{set of} (output\_type, string) |
|
506 \end{itemize}\bigskip |
|
507 |
|
508 a parse is successful whenever the input has been |
|
509 fully ``consumed'' (that is the second component is empty) |
|
510 |
|
511 |
|
512 \end{frame}} |
|
513 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
514 |
|
515 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
516 \mode<presentation>{ |
|
517 \begin{frame}[c] |
|
518 {\lstset{language=Scala}\fontsize{10}{12}\selectfont |
|
519 \texttt{\lstinputlisting{app7.scala}}} |
|
520 \end{frame}} |
|
521 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
522 |
|
523 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
524 \mode<presentation>{ |
|
525 \begin{frame}[c] |
|
526 {\lstset{language=Scala}\fontsize{10}{12}\selectfont |
|
527 \texttt{\lstinputlisting{app7.scala}}} |
|
528 \end{frame}} |
|
529 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
530 |
|
531 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
532 \mode<presentation>{ |
|
533 \begin{frame}[c] |
|
534 {\lstset{language=Scala}\fontsize{10}{12}\selectfont |
|
535 \texttt{\lstinputlisting{app8.scala}}} |
|
536 \end{frame}} |
|
537 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
538 |
|
539 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
540 \mode<presentation>{ |
|
541 \begin{frame}[c] |
|
542 \frametitle{\begin{tabular}{c}Two Grammars\end{tabular}} |
|
543 |
|
544 Which languages are recognised by the following two grammars? |
|
545 |
|
546 \begin{center} |
|
547 \bl{\begin{tabular}{lcl} |
|
548 $S$ & $\rightarrow$ & $1 \cdot S \cdot S$\\ |
|
549 & $|$ & $\epsilon$ |
|
550 \end{tabular}} |
|
551 \end{center}\bigskip |
|
552 |
|
553 \begin{center} |
|
554 \bl{\begin{tabular}{lcl} |
|
555 $U$ & $\rightarrow$ & $1 \cdot U$\\ |
|
556 & $|$ & $\epsilon$ |
|
557 \end{tabular}} |
|
558 \end{center} |
|
559 |
|
560 \end{frame}} |
|
561 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
562 |
|
563 |
|
564 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
565 \mode<presentation>{ |
|
566 \begin{frame}[t] |
|
567 \frametitle{\begin{tabular}{c}Ambiguous Grammars\end{tabular}} |
|
568 |
|
569 \mbox{}\\[-25mm]\mbox{} |
|
570 |
|
571 \begin{center} |
|
572 \begin{tikzpicture}[y=.2cm, x=.009cm] |
|
573 %axis |
|
574 \draw (0,0) -- coordinate (x axis mid) (1000,0); |
|
575 \draw (0,0) -- coordinate (y axis mid) (0,30); |
|
576 %ticks |
|
577 \foreach \x in {0, 20, 100, 200,...,1000} |
|
578 \draw (\x,1pt) -- (\x,-3pt) |
|
579 node[anchor=north] {\small \x}; |
|
580 \foreach \y in {0,5,...,30} |
|
581 \draw (1pt,\y) -- (-3pt,\y) |
|
582 node[anchor=east] {\small\y}; |
|
583 %labels |
|
584 \node[below=0.6cm] at (x axis mid) {\bl{1}s}; |
|
585 \node[rotate=90, left=1.2cm] at (y axis mid) {secs}; |
|
586 |
|
587 %plots |
|
588 \draw[color=blue] plot[mark=*, mark options={fill=white}] |
|
589 file {s-grammar1.data}; |
|
590 \only<2->{\draw[color=red] plot[mark=triangle*, mark options={fill=white} ] |
|
591 file {s-grammar2.data};} |
|
592 %legend |
|
593 \begin{scope}[shift={(400,20)}] |
|
594 \draw[color=blue] (0,0) -- |
|
595 plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
596 node[right]{\small unambiguous}; |
|
597 \only<2->{\draw[yshift=\baselineskip, color=red] (0,0) -- |
|
598 plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
599 node[right]{\small ambiguous};} |
|
600 \end{scope} |
|
601 \end{tikzpicture} |
|
602 \end{center} |
|
603 |
|
604 \end{frame}} |
|
605 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
606 |
|
607 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
608 \mode<presentation>{ |
|
609 \begin{frame}[c] |
|
610 \frametitle{\begin{tabular}{c}What about Left-Recursion?\end{tabular}} |
|
611 |
|
612 \begin{itemize} |
|
613 \item we record when we recursively called a parser\bigskip |
|
614 \item whenever the is a recursion, the parser must have consumed something --- so |
|
615 we can decrease the input string/list of token by one (at the end) |
|
616 \end{itemize} |
|
617 \end{frame}} |
|
618 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
619 |
|
620 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
621 \mode<presentation>{ |
|
622 \begin{frame}[c] |
|
623 \frametitle{\begin{tabular}{c}While-Language\end{tabular}} |
|
624 |
|
625 |
|
626 \begin{center} |
|
627 \bl{\begin{tabular}{@{}lcl@{}} |
|
628 $Stmt$ & $\rightarrow$ & $\text{skip}$\\ |
|
629 & $|$ & $Id := AExp$\\ |
|
630 & $|$ & $\text{if}\; B\!Exp \;\text{then}\; Block \;\text{else}\; Block$\\ |
|
631 & $|$ & $\text{while}\; B\!Exp \;\text{do}\; Block$\medskip\\ |
|
632 $Stmts$ & $\rightarrow$ & $Stmt \;\text{;}\; Stmts$\\ |
|
633 & $|$ & $Stmt$\medskip\\ |
|
634 $Block$ & $\rightarrow$ & $\{ Stmts \}$\\ |
|
635 & $|$ & $Stmt$\medskip\\ |
|
636 $AExp$ & $\rightarrow$ & \ldots\\ |
|
637 $BExp$ & $\rightarrow$ & \ldots\\ |
|
638 \end{tabular}} |
|
639 \end{center} |
|
640 |
|
641 |
|
642 \end{frame}} |
|
643 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
644 |
|
645 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
646 \mode<presentation>{ |
|
647 \begin{frame}[c] |
|
648 \frametitle{\begin{tabular}{c}An Interpreter\end{tabular}} |
|
649 |
|
650 \begin{center} |
|
651 \bl{\begin{tabular}{l} |
|
652 $\{$\\ |
|
653 \;\;$x := 5 \text{;}$\\ |
|
654 \;\;$y := x * 3\text{;}$\\ |
|
655 \;\;$y := x * 4\text{;}$\\ |
|
656 \;\;$x := u * 3$\\ |
|
657 $\}$ |
|
658 \end{tabular}} |
|
659 \end{center} |
|
660 |
|
661 \begin{itemize} |
|
662 \item the interpreter has to record the value of \bl{$x$} before assigning a value to \bl{$y$}\pause |
|
663 \item \bl{\text{eval}(stmt, env)} |
|
664 \end{itemize} |
|
665 |
|
666 |
|
667 \end{frame}} |
|
668 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
669 |
|
670 \end{document} |
|
671 |
|
672 %%% Local Variables: |
|
673 %%% mode: latex |
|
674 %%% TeX-master: t |
|
675 %%% End: |
|
676 |
|