1 \documentclass{article} |
1 \documentclass{article} |
2 \usepackage{hyperref} |
2 \usepackage{../style} |
3 \usepackage{amssymb} |
|
4 \usepackage{amsmath} |
|
5 \usepackage[T1]{fontenc} |
|
6 \usepackage{tikz} |
|
7 \usetikzlibrary{arrows} |
|
8 \usetikzlibrary{automata} |
|
9 \usetikzlibrary{shapes} |
|
10 \usetikzlibrary{shadows} |
|
11 \usetikzlibrary{positioning} |
|
12 \usetikzlibrary{calc} |
|
13 \usetikzlibrary{fit} |
|
14 \usetikzlibrary{backgrounds} |
|
15 \usepackage{../langs} |
3 \usepackage{../langs} |
16 |
4 |
17 |
5 |
18 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% |
|
19 |
|
20 \newcommand\grid[1]{% |
|
21 \begin{tikzpicture}[baseline=(char.base)] |
|
22 \path[use as bounding box] |
|
23 (0,0) rectangle (1em,1em); |
|
24 \draw[red!50, fill=red!20] |
|
25 (0,0) rectangle (1em,1em); |
|
26 \node[inner sep=1pt,anchor=base west] |
|
27 (char) at (0em,\gridraiseamount) {#1}; |
|
28 \end{tikzpicture}} |
|
29 \newcommand\gridraiseamount{0.12em} |
|
30 |
|
31 \makeatletter |
|
32 \newcommand\Grid[1]{% |
|
33 \@tfor\z:=#1\do{\grid{\z}}} |
|
34 \makeatother |
|
35 |
|
36 \newcommand\Vspace[1][.3em]{% |
|
37 \mbox{\kern.06em\vrule height.3ex}% |
|
38 \vbox{\hrule width#1}% |
|
39 \hbox{\vrule height.3ex}} |
|
40 |
|
41 \def\VS{\Vspace[0.6em]} |
|
42 |
|
43 \begin{document} |
6 \begin{document} |
44 |
7 |
45 \section*{Handout 6 (Parser Combinators)} |
8 \section*{Handout 6 (Parser Combinators)} |
46 |
9 |
47 While regular expressions are very useful for lexing and for recognising |
10 While regular expressions are very useful for lexing and for recognising |
63 languages}. They include the regular languages as the picture below shows: |
26 languages}. They include the regular languages as the picture below shows: |
64 |
27 |
65 |
28 |
66 \begin{center} |
29 \begin{center} |
67 \begin{tikzpicture} |
30 \begin{tikzpicture} |
68 [rect/.style={draw=black!50, top color=white,bottom color=black!20, rectangle, very thick, rounded corners}] |
31 [rect/.style={draw=black!50, |
69 |
32 top color=white,bottom color=black!20, |
70 \draw (0,0) node [rect, text depth=30mm, text width=46mm] {all languages}; |
33 rectangle, very thick, rounded corners}] |
71 \draw (0,-0.4) node [rect, text depth=20mm, text width=44mm] {decidable languages}; |
34 |
72 \draw (0,-0.65) node [rect, text depth=13mm] {context sensitive languages}; |
35 \draw (0,0) node [rect, text depth=30mm, text width=46mm] {\small all languages}; |
73 \draw (0,-0.84) node [rect, text depth=7mm, text width=35mm] {context-free languages}; |
36 \draw (0,-0.4) node [rect, text depth=20mm, text width=44mm] {\small decidable languages}; |
74 \draw (0,-1.05) node [rect] {regular languages}; |
37 \draw (0,-0.65) node [rect, text depth=13mm] {\small context sensitive languages}; |
|
38 \draw (0,-0.84) node [rect, text depth=7mm, text width=35mm] {\small context-free languages}; |
|
39 \draw (0,-1.05) node [rect] {\small regular languages}; |
75 \end{tikzpicture} |
40 \end{tikzpicture} |
76 \end{center} |
41 \end{center} |
77 |
42 |
78 \noindent |
43 \noindent |
79 Context-free languages play an important role in `day-to-day' text processing and in |
44 Context-free languages play an important role in `day-to-day' text processing and in |