74 % \end{frame} |
74 % \end{frame} |
75 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
75 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
76 |
76 |
77 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
77 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
78 \begin{frame}[t] |
78 \begin{frame}[t] |
79 \frametitle{Lexer, Parser} |
79 \frametitle{Parser} |
80 \mbox{}\\[-16mm]\mbox{} |
80 \mbox{}\\[-16mm]\mbox{} |
81 |
81 |
82 \begin{center} |
82 \begin{center} |
83 \begin{tikzpicture}[scale=1, |
83 \begin{tikzpicture}[scale=1, |
84 node/.style={ |
84 node/.style={ |
106 \draw [->,line width=4mm] (B) -- (C); |
106 \draw [->,line width=4mm] (B) -- (C); |
107 \draw [->,line width=4mm] (C) -- (1); |
107 \draw [->,line width=4mm] (C) -- (1); |
108 \end{tikzpicture} |
108 \end{tikzpicture} |
109 \end{center} |
109 \end{center} |
110 |
110 |
111 Today a parser. |
111 |
112 |
112 \only<2>{ |
|
113 \begin{textblock}{1}(3,6) |
|
114 \begin{bubble}[8.5cm] |
|
115 \normalsize |
|
116 parser input: a sequence of tokens\smallskip\\ |
|
117 |
|
118 {\small\hspace{5mm}\code{key(read) lpar id(n) rpar semi}}\smallskip\\ |
|
119 |
|
120 parser output: an abstract syntax tree\smallskip\\ |
|
121 \footnotesize |
|
122 \hspace{2cm}\begin{tikzpicture} |
|
123 \node {\code{read}} |
|
124 child {node {\code{lpar}}} |
|
125 child {node {\code{n}}} |
|
126 child {node {\code{rpar}}}; |
|
127 \end{tikzpicture} |
|
128 \end{bubble} |
|
129 \end{textblock}} |
113 \end{frame} |
130 \end{frame} |
114 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
131 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
115 |
132 |
116 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
133 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
117 \begin{frame}[c] |
134 \begin{frame}[c] |
175 \end{center} |
192 \end{center} |
176 |
193 |
177 \end{frame} |
194 \end{frame} |
178 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
195 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
179 |
196 |
|
197 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
198 \begin{frame}[c] |
|
199 \LARGE |
|
200 \begin{center} |
|
201 Time flies like an arrow.\\ |
|
202 Fruit flies like bananas. |
|
203 \end{center} |
|
204 \end{frame} |
|
205 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
206 |
180 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
207 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
181 \begin{frame}[c] |
208 \begin{frame}[c] |
182 \frametitle{CFGs} |
209 \frametitle{CFGs} |
183 |
210 |
184 A \alert{\bf context-free grammar} \bl{$G$} consists of |
211 A \alert{\bf context-free grammar} \bl{$G$} consists of |
208 \begin{frame}[t] |
235 \begin{frame}[t] |
209 \frametitle{Palindromes} |
236 \frametitle{Palindromes} |
210 |
237 |
211 A grammar for palindromes over the alphabet~\bl{$\{a,b\}$}: |
238 A grammar for palindromes over the alphabet~\bl{$\{a,b\}$}: |
212 |
239 |
213 \bl{\begin{plstx}[margin=3cm] |
240 \only<1>{% |
|
241 \bl{\begin{plstx}[margin=1cm] |
214 : \meta{S} ::= a\cdot\meta{S}\cdot a\\ |
242 : \meta{S} ::= a\cdot\meta{S}\cdot a\\ |
215 : \meta{S} ::= b\cdot\meta{S}\cdot b\\ |
243 : \meta{S} ::= b\cdot\meta{S}\cdot b\\ |
216 : \meta{S} ::= a\\ |
244 : \meta{S} ::= a\\ |
217 : \meta{S} ::= b\\ |
245 : \meta{S} ::= b\\ |
218 : \meta{S} ::= \epsilon\\ |
246 : \meta{S} ::= \epsilon\\ |
219 \end{plstx}}\pause |
247 \end{plstx}}} |
220 |
248 % |
221 or |
249 \only<2>{% |
222 |
250 \bl{\begin{plstx}[margin=1cm] |
223 \bl{\begin{plstx}[margin=2cm] |
|
224 : \meta{S} ::= a\cdot \meta{S}\cdot a | b\cdot \meta{S}\cdot b | a | b | \epsilon\\ |
251 : \meta{S} ::= a\cdot \meta{S}\cdot a | b\cdot \meta{S}\cdot b | a | b | \epsilon\\ |
225 \end{plstx}}\pause\bigskip |
252 \end{plstx}}} |
226 |
253 |
227 \small |
254 %\small |
228 Can you find the grammar rules for matched parentheses? |
255 %Can you find the grammar rules for matched parentheses? |
229 |
256 |
230 \end{frame} |
257 \end{frame} |
231 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
258 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
232 |
259 |
233 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
260 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
234 \begin{frame}[c] |
261 \begin{frame}[c] |
235 \frametitle{Arithmetic Expressions} |
262 \frametitle{Arithmetic Expressions} |
236 |
263 |
237 \bl{\begin{plstx}[margin=3cm,one per line] |
264 \bl{\begin{plstx}[margin=3cm,one per line] |
238 : \meta{E} ::= num\_token |
265 : \meta{E} ::= 0 \mid 1 \mid 2 \mid ... \mid 9 |
239 | \meta{E} \cdot + \cdot \meta{E} |
266 | \meta{E} \cdot + \cdot \meta{E} |
240 | \meta{E} \cdot - \cdot \meta{E} |
267 | \meta{E} \cdot - \cdot \meta{E} |
241 | \meta{E} \cdot * \cdot \meta{E} |
268 | \meta{E} \cdot * \cdot \meta{E} |
242 | ( \cdot \meta{E} \cdot ) \\ |
269 | ( \cdot \meta{E} \cdot ) \\ |
243 \end{plstx}}\pause |
270 \end{plstx}}\pause |
290 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
317 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
291 \begin{frame}[t] |
318 \begin{frame}[t] |
292 \frametitle{Example Derivation} |
319 \frametitle{Example Derivation} |
293 |
320 |
294 \bl{\begin{plstx}[margin=3cm,one per line] |
321 \bl{\begin{plstx}[margin=3cm,one per line] |
295 : \meta{E} ::= num\_token |
322 : \meta{E} ::= 0 \mid 1 \mid 2 \mid ... \mid 9 |
296 | \meta{E} \cdot + \cdot \meta{E} |
323 | \meta{E} \cdot + \cdot \meta{E} |
297 | \meta{E} \cdot - \cdot \meta{E} |
324 | \meta{E} \cdot - \cdot \meta{E} |
298 | \meta{E} \cdot * \cdot \meta{E} |
325 | \meta{E} \cdot * \cdot \meta{E} |
299 | ( \cdot \meta{E} \cdot ) \\ |
326 | ( \cdot \meta{E} \cdot ) \\ |
300 \end{plstx}} |
327 \end{plstx}} |
371 \frametitle{Parse Trees} |
398 \frametitle{Parse Trees} |
372 \mbox{}\\[-12mm] |
399 \mbox{}\\[-12mm] |
373 |
400 |
374 \bl{\begin{plstx}: \meta{E} ::= \meta{T} | \meta{T} \cdot + \cdot \meta{E} | \meta{T} \cdot - \cdot \meta{E}\\ |
401 \bl{\begin{plstx}: \meta{E} ::= \meta{T} | \meta{T} \cdot + \cdot \meta{E} | \meta{T} \cdot - \cdot \meta{E}\\ |
375 : \meta{T} ::= \meta{F} | \meta{F} \cdot * \cdot \meta{T}\\ |
402 : \meta{T} ::= \meta{F} | \meta{F} \cdot * \cdot \meta{T}\\ |
376 : \meta{F} ::= num\_token | ( \cdot \meta{E} \cdot )\\ |
403 : \meta{F} ::= 0 ... 9 | ( \cdot \meta{E} \cdot )\\ |
377 \end{plstx}} |
404 \end{plstx}} |
378 |
405 |
379 \begin{center}\small |
406 \begin{textblock}{5}(6, 5) |
|
407 \small |
|
408 \begin{tikzpicture}[level distance=10mm, blue] |
|
409 \node {$\meta{E}$} |
|
410 child {node {$\meta{T}$} |
|
411 child {node {$\meta{F}$} child {node {1}}} |
|
412 } |
|
413 child {node {+}} |
|
414 child {node {$\meta{E}$} |
|
415 child[sibling distance=10mm] {node {$\meta{T}$} |
|
416 child {node {$\meta{F}$} child {node {2}}} |
|
417 child {node {+}} |
|
418 child {node {$\meta{T}$} child {node {$\meta{F}$} child {node {3}}}} |
|
419 } |
|
420 child {node {+}} |
|
421 child {node {$\meta{E}$} child {node {$\meta{T}$} |
|
422 child {node {$\meta{F}$} child {node {4}}}}} |
|
423 } |
|
424 ; |
|
425 \end{tikzpicture} |
|
426 \end{textblock} |
|
427 |
|
428 \begin{textblock}{5}(1, 10) |
|
429 \bl{\texttt{1 + 2 * 3 + 4}} |
|
430 \end{textblock} |
|
431 |
|
432 \end{frame} |
|
433 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
434 |
380 \begin{tikzpicture}[level distance=8mm, blue] |
435 \begin{tikzpicture}[level distance=8mm, blue] |
381 \node {$\meta{E}$} |
436 \node {$\meta{E}$} |
382 child {node {$\meta{T}$} |
437 child {node {$\meta{T}$} |
383 child {node {$\meta{T}$} |
438 child {node {$\meta{T}$} |
384 child {node {(\,$\meta{E}$\,)} |
439 child {node {(\,$\meta{E}$\,)} |
397 child {node {4}} |
452 child {node {4}} |
398 } |
453 } |
399 }} |
454 }} |
400 }}; |
455 }}; |
401 \end{tikzpicture} |
456 \end{tikzpicture} |
402 \end{center} |
|
403 |
|
404 \begin{textblock}{5}(1, 6.5) |
|
405 \bl{\texttt{(2*3)+(3+4)}} |
|
406 \end{textblock} |
|
407 |
|
408 \end{frame} |
|
409 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
410 |
457 |
411 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
458 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
412 \begin{frame}[t] |
459 \begin{frame}[t] |
413 \frametitle{Arithmetic Expressions} |
460 \frametitle{Arithmetic Expressions} |
414 |
461 |
415 \bl{\begin{plstx}[margin=3cm,one per line] |
462 \bl{\begin{plstx}[margin=3cm,one per line] |
416 : \meta{E} ::= num\_token |
463 : \meta{E} ::= 0..9 |
417 | \meta{E} \cdot + \cdot \meta{E} |
464 | \meta{E} \cdot + \cdot \meta{E} |
418 | \meta{E} \cdot - \cdot \meta{E} |
465 | \meta{E} \cdot - \cdot \meta{E} |
419 | \meta{E} \cdot * \cdot \meta{E} |
466 | \meta{E} \cdot * \cdot \meta{E} |
420 | ( \cdot \meta{E} \cdot ) \\ |
467 | ( \cdot \meta{E} \cdot ) \\ |
421 \end{plstx}}\pause\bigskip |
468 \end{plstx}}\pause\bigskip |