equal
deleted
inserted
replaced
13 |
13 |
14 \newcommand{\bl}[1]{\textcolor{blue}{#1}} |
14 \newcommand{\bl}[1]{\textcolor{blue}{#1}} |
15 |
15 |
16 % beamer stuff |
16 % beamer stuff |
17 \renewcommand{\slidecaption}{CFL 05, King's College London} |
17 \renewcommand{\slidecaption}{CFL 05, King's College London} |
|
18 |
|
19 \usepackage{tcolorbox} |
|
20 \newtcolorbox{mybox}{colback=red!5!white,colframe=red!75!black} |
|
21 \newtcolorbox{mybox2}[1]{colback=red!5!white,colframe=red!75!black,fonttitle=\bfseries,title=#1} |
|
22 \newtcolorbox{mybox3}[1]{colback=Cyan!5!white,colframe=Cyan!75!black,fonttitle=\bfseries,title=#1} |
|
23 |
18 |
24 |
19 |
25 |
20 \begin{document} |
26 \begin{document} |
21 |
27 |
22 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
28 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
345 \end{center} |
351 \end{center} |
346 |
352 |
347 \end{frame} |
353 \end{frame} |
348 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
354 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
349 |
355 |
350 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
356 |
351 \begin{frame}[c] |
|
352 \frametitle{Context Sensitive Grammars} |
|
353 |
|
354 It is much harder to find out whether a string is parsed |
|
355 by a context sensitive grammar: |
|
356 |
|
357 \bl{\begin{plstx}[margin=2cm] |
|
358 : \meta{S} ::= b\meta{S}\meta{A}\meta{A} | \epsilon\\ |
|
359 : \meta{A} ::= a\\ |
|
360 : b\meta{A} ::= \meta{A}b\\ |
|
361 \end{plstx}}\pause |
|
362 |
|
363 \begin{center} |
|
364 \bl{$\meta{S} \rightarrow\ldots\rightarrow^? ababaa$} |
|
365 \end{center}\pause |
|
366 |
|
367 \begin{center} |
|
368 \tt Time flies like an arrow;\\ |
|
369 fruit flies like bananas. |
|
370 \end{center} |
|
371 |
|
372 \end{frame} |
|
373 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
374 |
357 |
375 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
358 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
376 \begin{frame}[c] |
359 \begin{frame}[c] |
377 \frametitle{Language of a CFG} |
360 \frametitle{Language of a CFG} |
378 |
361 |
430 \end{textblock} |
413 \end{textblock} |
431 |
414 |
432 \end{frame} |
415 \end{frame} |
433 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
416 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
434 |
417 |
435 \begin{tikzpicture}[level distance=8mm, blue] |
|
436 \node {$\meta{E}$} |
|
437 child {node {$\meta{T}$} |
|
438 child {node {$\meta{T}$} |
|
439 child {node {(\,$\meta{E}$\,)} |
|
440 child {node{$\meta{F}$ *{} $\meta{F}$} |
|
441 child {node {$\meta{T}$} child {node {2}}} |
|
442 child {node {$\meta{T}$} child {node {3}}} |
|
443 } |
|
444 } |
|
445 } |
|
446 child {node {+}} |
|
447 child {node {$\meta{T}$} |
|
448 child {node {(\,$\meta{E}$\,)} |
|
449 child {node {$\meta{F}$} |
|
450 child {node {$\meta{T}$ +{} $\meta{T}$} |
|
451 child {node {3}} |
|
452 child {node {4}} |
|
453 } |
|
454 }} |
|
455 }}; |
|
456 \end{tikzpicture} |
|
457 |
418 |
458 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
419 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
459 \begin{frame}[t] |
420 \begin{frame}[t] |
460 \frametitle{Arithmetic Expressions} |
421 \frametitle{Arithmetic Expressions} |
461 |
422 |
478 \frametitle{Ambiguous Grammars} |
439 \frametitle{Ambiguous Grammars} |
479 |
440 |
480 A grammar is \alert{\bf ambiguous} if there is a string that |
441 A grammar is \alert{\bf ambiguous} if there is a string that |
481 has at least two different parse trees. |
442 has at least two different parse trees. |
482 |
443 |
483 \bl{\begin{plstx}[margin=3cm,one per line]: \meta{E} ::= num\_token |
444 \bl{\begin{plstx}[margin=3cm,one per line]: \meta{E} ::= 0 ... 9 |
484 | \meta{E} \cdot + \cdot \meta{E} |
445 | \meta{E} \cdot + \cdot \meta{E} |
485 | \meta{E} \cdot - \cdot \meta{E} |
446 | \meta{E} \cdot - \cdot \meta{E} |
486 | \meta{E} \cdot * \cdot \meta{E} |
447 | \meta{E} \cdot * \cdot \meta{E} |
487 | ( \cdot \meta{E} \cdot ) \\ |
448 | ( \cdot \meta{E} \cdot ) \\ |
488 \end{plstx}} |
449 \end{plstx}} |
509 |
470 |
510 \bl{\texttt{if a then if x then y else c}} |
471 \bl{\texttt{if a then if x then y else c}} |
511 |
472 |
512 \end{frame} |
473 \end{frame} |
513 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
474 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
475 |
|
476 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
477 \begin{frame}[c] |
|
478 \frametitle{Context Sensitive Grammars} |
|
479 |
|
480 It is much harder to find out whether a string is parsed |
|
481 by a context sensitive grammar: |
|
482 |
|
483 \bl{\begin{plstx}[margin=2cm] |
|
484 : \meta{S} ::= b\meta{S}\meta{A}\meta{A} | \epsilon\\ |
|
485 : \meta{A} ::= a\\ |
|
486 : b\meta{A} ::= \meta{A}b\\ |
|
487 \end{plstx}}\pause |
|
488 |
|
489 \begin{center} |
|
490 \bl{$\meta{S} \rightarrow\ldots\rightarrow^? ababaa$} |
|
491 \end{center}\pause |
|
492 |
|
493 \begin{center} |
|
494 \tt Time flies like an arrow;\\ |
|
495 fruit flies like bananas. |
|
496 \end{center} |
|
497 |
|
498 \end{frame} |
|
499 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
500 |
514 |
501 |
515 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
502 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
516 \begin{frame}[c] |
503 \begin{frame}[c] |
517 \frametitle{Parser Combinators} |
504 \frametitle{Parser Combinators} |
518 |
505 |
930 \end{itemize} |
917 \end{itemize} |
931 |
918 |
932 \end{frame}} |
919 \end{frame}} |
933 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
920 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
934 |
921 |
|
922 \begin{frame}[t] |
|
923 \begin{mybox3}{} |
|
924 val (r1s, f1s) = simp(r1)\\ |
|
925 val (r2s, f2s) = simp(r2)\\ |
|
926 how are the |
|
927 first rectification functions f1s and f2s made? could you maybe |
|
928 show an example? |
|
929 \end{mybox3} |
|
930 \end{frame} |
|
931 |
|
932 \begin{frame}<1-12>[c] |
|
933 \end{frame} |
|
934 |
935 |
935 |
936 \end{document} |
936 \end{document} |
937 |
937 |
938 %%% Local Variables: |
938 %%% Local Variables: |
939 %%% mode: latex |
939 %%% mode: latex |