173
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
1 |
\documentclass{article}
|
297
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
2 |
\usepackage{../style}
|
217
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
3 |
\usepackage{../langs}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
4 |
|
173
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
5 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
6 |
\begin{document}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
7 |
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
8 |
\section*{Handout 6 (Parser Combinators)}
|
173
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
9 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
10 |
While regular expressions are very useful for lexing and for recognising
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
11 |
many patterns in strings (like email addresses), they have their limitations. For
|
173
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
12 |
example there is no regular expression that can recognise the language
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
13 |
$a^nb^n$. Another example for which there exists no regular expression is the language of well-parenthesised
|
173
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
14 |
expressions. In languages like Lisp, which use parentheses rather
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
15 |
extensively, it might be of interest whether the following two expressions
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
16 |
are well-parenthesised (the left one is, the right one is not):
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
17 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
18 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
19 |
$(((()()))())$ \hspace{10mm} $(((()()))()))$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
20 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
21 |
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
22 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
23 |
Not being able to solve such recognition problems is a serious limitation.
|
173
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
24 |
In order to solve such recognition problems, we need more powerful
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
25 |
techniques than regular expressions. We will in particular look at \emph{context-free
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
26 |
languages}. They include the regular languages as the picture below shows:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
27 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
28 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
29 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
30 |
\begin{tikzpicture}
|
297
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
31 |
[rect/.style={draw=black!50,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
32 |
top color=white,bottom color=black!20,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
33 |
rectangle, very thick, rounded corners}]
|
173
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
34 |
|
297
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
35 |
\draw (0,0) node [rect, text depth=30mm, text width=46mm] {\small all languages};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
36 |
\draw (0,-0.4) node [rect, text depth=20mm, text width=44mm] {\small decidable languages};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
37 |
\draw (0,-0.65) node [rect, text depth=13mm] {\small context sensitive languages};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
38 |
\draw (0,-0.84) node [rect, text depth=7mm, text width=35mm] {\small context-free languages};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
39 |
\draw (0,-1.05) node [rect] {\small regular languages};
|
173
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
40 |
\end{tikzpicture}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
41 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
42 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
43 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
44 |
Context-free languages play an important role in `day-to-day' text processing and in
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
45 |
programming languages. Context-free languages are usually specified by grammars.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
46 |
For example a grammar for well-parenthesised expressions is
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
47 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
48 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
49 |
$P \;\;\rightarrow\;\; ( \cdot P \cdot ) \cdot P \;|\; \epsilon$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
50 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
51 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
52 |
\noindent
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
53 |
In general grammars consist of finitely many rules built up from \emph{terminal symbols}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
54 |
(usually lower-case letters) and \emph{non-terminal symbols} (upper-case letters). Rules
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
55 |
have the shape
|
173
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
56 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
57 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
58 |
$NT \;\;\rightarrow\;\; \textit{rhs}$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
59 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
60 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
61 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
62 |
where on the left-hand side is a single non-terminal and on the right a string consisting
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
63 |
of both terminals and non-terminals including the $\epsilon$-symbol for indicating the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
64 |
empty string. We use the convention to separate components on
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
65 |
the right hand-side by using the $\cdot$ symbol, as in the grammar for well-parenthesised expressions.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
66 |
We also use the convention to use $|$ as a shorthand notation for several rules. For example
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
67 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
68 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
69 |
$NT \;\;\rightarrow\;\; \textit{rhs}_1 \;|\; \textit{rhs}_2$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
70 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
71 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
72 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
73 |
means that the non-terminal $NT$ can be replaced by either $\textit{rhs}_1$ or $\textit{rhs}_2$.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
74 |
If there are more than one non-terminal on the left-hand side of the rules, then we need to indicate
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
75 |
what is the \emph{starting} symbol of the grammar. For example the grammar for arithmetic expressions
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
76 |
can be given as follows
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
77 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
78 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
79 |
\begin{tabular}{lcl}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
80 |
$E$ & $\rightarrow$ & $N$ \\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
81 |
$E$ & $\rightarrow$ & $E \cdot + \cdot E$ \\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
82 |
$E$ & $\rightarrow$ & $E \cdot - \cdot E$ \\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
83 |
$E$ & $\rightarrow$ & $E \cdot * \cdot E$ \\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
84 |
$E$ & $\rightarrow$ & $( \cdot E \cdot )$\\
|
175
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
85 |
$N$ & $\rightarrow$ & $N \cdot N \;|\; 0 \;|\; 1 \;|\: \ldots \;|\; 9$
|
173
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
86 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
87 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
88 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
89 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
90 |
where $E$ is the starting symbol. A \emph{derivation} for a grammar
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
91 |
starts with the staring symbol of the grammar and in each step replaces one
|
175
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
92 |
non-terminal by a right-hand side of a rule. A derivation ends with a string
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
93 |
in which only terminal symbols are left. For example a derivation for the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
94 |
string $(1 + 2) + 3$ is as follows:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
95 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
96 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
97 |
\begin{tabular}{lll}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
98 |
$E$ & $\rightarrow$ & $E+E$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
99 |
& $\rightarrow$ & $(E)+E$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
100 |
& $\rightarrow$ & $(E+E)+E$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
101 |
& $\rightarrow$ & $(E+E)+N$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
102 |
& $\rightarrow$ & $(E+E)+3$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
103 |
& $\rightarrow$ & $(N+E)+3$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
104 |
& $\rightarrow^+$ & $(1+2)+3$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
105 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
106 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
107 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
108 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
109 |
The \emph{language} of a context-free grammar $G$ with start symbol $S$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
110 |
is defined as the set of strings derivable by a derivation, that is
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
111 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
112 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
113 |
$\{c_1\ldots c_n \;|\; S \rightarrow^* c_1\ldots c_n \;\;\text{with all} \; c_i \;\text{being non-terminals}\}$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
114 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
115 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
116 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
117 |
A \emph{parse-tree} encodes how a string is derived with the starting symbol on
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
118 |
top and each non-terminal containing a subtree for how it is replaced in a derivation.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
119 |
The parse tree for the string $(1 + 23)+4$ is as follows:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
120 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
121 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
122 |
\begin{tikzpicture}[level distance=8mm, black]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
123 |
\node {$E$}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
124 |
child {node {$E$}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
125 |
child {node {$($}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
126 |
child {node {$E$}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
127 |
child {node {$E$} child {node {$N$} child {node {$1$}}}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
128 |
child {node {$+$}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
129 |
child {node {$E$}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
130 |
child {node {$N$} child {node {$2$}}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
131 |
child {node {$N$} child {node {$3$}}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
132 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
133 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
134 |
child {node {$)$}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
135 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
136 |
child {node {$+$}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
137 |
child {node {$E$}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
138 |
child {node {$N$} child {node {$4$}}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
139 |
};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
140 |
\end{tikzpicture}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
141 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
142 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
143 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
144 |
We are often interested in these parse-trees since they encode the structure of
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
145 |
how a string is derived by a grammar. Before we come to the problem of constructing
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
146 |
such parse-trees, we need to consider the following two properties of grammars.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
147 |
A grammar is \emph{left-recursive} if there is a derivation starting from a non-terminal, say
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
148 |
$NT$ which leads to a string which again starts with $NT$. This means a derivation of the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
149 |
form.
|
173
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
150 |
|
175
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
151 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
152 |
$NT \rightarrow \ldots \rightarrow NT \cdot \ldots$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
153 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
154 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
155 |
\noindent
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
156 |
It can be easily seen that the grammar above for arithmetic expressions is left-recursive:
|
175
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
157 |
for example the rules $E \rightarrow E\cdot + \cdot E$ and $N \rightarrow N\cdot N$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
158 |
show that this grammar is left-recursive. Some algorithms cannot cope with left-recursive
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
159 |
grammars. Fortunately every left-recursive grammar can be transformed into one that is
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
160 |
not left-recursive, although this transformation might make the grammar less human-readable.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
161 |
For example if we want to give a non-left-recursive grammar for numbers we might
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
162 |
specify
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
163 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
164 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
165 |
$N \;\;\rightarrow\;\; 0\;|\;\ldots\;|\;9\;|\;1\cdot N\;|\;2\cdot N\;|\;\ldots\;|\;9\cdot N$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
166 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
167 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
168 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
169 |
Using this grammar we can still derive every number string, but we will never be able
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
170 |
to derive a string of the form $\ldots \rightarrow N \cdot \ldots$.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
171 |
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
172 |
The other property we have to watch out for is when a grammar is
|
175
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
173 |
\emph{ambiguous}. A grammar is said to be ambiguous if there are two parse-trees
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
174 |
for one string. Again the grammar for arithmetic expressions shown above is ambiguous.
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
175 |
While the shown parse tree for the string $(1 + 23) + 4$ is unique, this is not the case in
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
176 |
general. For example there are two parse
|
175
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
177 |
trees for the string $1 + 2 + 3$, namely
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
178 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
179 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
180 |
\begin{tabular}{c@{\hspace{10mm}}c}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
181 |
\begin{tikzpicture}[level distance=8mm, black]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
182 |
\node {$E$}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
183 |
child {node {$E$} child {node {$N$} child {node {$1$}}}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
184 |
child {node {$+$}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
185 |
child {node {$E$}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
186 |
child {node {$E$} child {node {$N$} child {node {$2$}}}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
187 |
child {node {$+$}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
188 |
child {node {$E$} child {node {$N$} child {node {$3$}}}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
189 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
190 |
;
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
191 |
\end{tikzpicture}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
192 |
&
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
193 |
\begin{tikzpicture}[level distance=8mm, black]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
194 |
\node {$E$}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
195 |
child {node {$E$}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
196 |
child {node {$E$} child {node {$N$} child {node {$1$}}}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
197 |
child {node {$+$}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
198 |
child {node {$E$} child {node {$N$} child {node {$2$}}}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
199 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
200 |
child {node {$+$}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
201 |
child {node {$E$} child {node {$N$} child {node {$3$}}}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
202 |
;
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
203 |
\end{tikzpicture}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
204 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
205 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
206 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
207 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
208 |
In particular in programming languages we will try to avoid ambiguous
|
176
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
209 |
grammars because two different parse-trees for a string mean a program can
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
210 |
be interpreted in two different ways. In such cases we have to somehow make sure
|
175
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
211 |
the two different ways do not matter, or disambiguate the grammar in
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
212 |
some other way (for example making the $+$ left-associative). Unfortunately already
|
175
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
213 |
the problem of deciding whether a grammar
|
176
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
214 |
is ambiguous or not is in general undecidable.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
215 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
216 |
Let us now turn to the problem of generating a parse-tree for a grammar and string.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
217 |
In what follows we explain \emph{parser combinators}, because they are easy
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
218 |
to implement and closely resemble grammar rules. Imagine that a grammar
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
219 |
describes the strings of natural numbers, such as the grammar $N$ shown above.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
220 |
For all such strings we want to generate the parse-trees or later on we actually
|
177
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
221 |
want to extract the meaning of these strings, that is the concrete integers ``behind''
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
222 |
these strings. In Scala the parser combinators will be functions of type
|
176
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
223 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
224 |
\begin{center}
|
177
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
225 |
\texttt{I $\Rightarrow$ Set[(T, I)]}
|
176
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
226 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
227 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
228 |
\noindent
|
177
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
229 |
that is they take as input something of type \texttt{I}, typically a list of tokens or a string,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
230 |
and return a set of pairs. The first component of these pairs corresponds to what the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
231 |
parser combinator was able to process from the input and the second is the unprocessed
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
232 |
part of the input. As we shall see shortly, a parser combinator might return more than one such pair,
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
233 |
with the idea that there are potentially several ways how to interpret the input. As a concrete
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
234 |
example, consider the case where the input is of type string, say the string
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
235 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
236 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
237 |
\tt\Grid{iffoo\VS testbar}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
238 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
239 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
240 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
241 |
We might have a parser combinator which tries to interpret this string as a keyword (\texttt{if}) or
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
242 |
an identifier (\texttt{iffoo}). Then the output will be the set
|
177
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
243 |
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
244 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
245 |
$\left\{ \left(\texttt{\Grid{if}}\,,\, \texttt{\Grid{foo\VS testbar}}\right),
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
246 |
\left(\texttt{\Grid{iffoo}}\,,\, \texttt{\Grid{\VS testbar}}\right) \right\}$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
247 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
248 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
249 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
250 |
where the first pair means the parser could recognise \texttt{if} from the input and leaves
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
251 |
the rest as `unprocessed' as the second component of the pair; in the other case
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
252 |
it could recognise \texttt{iffoo} and leaves \texttt{\VS testbar} as unprocessed. If the parser
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
253 |
cannot recognise anything from the input then parser combinators just return the empty
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
254 |
set $\varnothing$. This will indicate something ``went wrong''.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
255 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
256 |
The main attraction is that we can easily build parser combinators out of smaller components
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
257 |
following very closely the structure of a grammar. In order to implement this in an object
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
258 |
oriented programming language, like Scala, we need to specify an abstract class for parser
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
259 |
combinators. This abstract class requires the implementation of the function
|
177
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
260 |
\texttt{parse} taking an argument of type \texttt{I} and returns a set of type
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
261 |
\mbox{\texttt{Set[(T, I)]}}.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
262 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
263 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
264 |
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
265 |
abstract class Parser[I, T] {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
266 |
def parse(ts: I): Set[(T, I)]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
267 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
268 |
def parse_all(ts: I): Set[T] =
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
269 |
for ((head, tail) <- parse(ts); if (tail.isEmpty))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
270 |
yield head
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
271 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
272 |
\end{lstlisting}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
273 |
\end{center}
|
176
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
274 |
|
177
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
275 |
\noindent
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
276 |
From the function \texttt{parse} we can then ``centrally'' derive the function \texttt{parse\_all},
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
277 |
which just filters out all pairs whose second component is not empty (that is has still some
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
278 |
unprocessed part). The reason is that at the end of parsing we are only interested in the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
279 |
results where all the input has been consumed and no unprocessed part is left.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
280 |
|
177
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
281 |
One of the simplest parser combinators recognises just a character, say $c$,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
282 |
from the beginning of strings. Its behaviour is as follows:
|
176
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
283 |
|
177
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
284 |
\begin{itemize}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
285 |
\item if the head of the input string starts with a $c$, it returns
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
286 |
the set $\{(c, \textit{tail of}\; s)\}$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
287 |
\item otherwise it returns the empty set $\varnothing$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
288 |
\end{itemize}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
289 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
290 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
291 |
The input type of this simple parser combinator for characters is
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
292 |
\texttt{String} and the output type \mbox{\texttt{Set[(Char, String)]}}.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
293 |
The code in Scala is as follows:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
294 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
295 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
296 |
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
297 |
case class CharParser(c: Char) extends Parser[String, Char] {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
298 |
def parse(sb: String) =
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
299 |
if (sb.head == c) Set((c, sb.tail)) else Set()
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
300 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
301 |
\end{lstlisting}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
302 |
\end{center}
|
176
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
303 |
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
304 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
305 |
The \texttt{parse} function tests whether the first character of the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
306 |
input string \texttt{sb} is equal to \texttt{c}. If yes, then it splits the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
307 |
string into the recognised part \texttt{c} and the unprocessed part
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
308 |
\texttt{sb.tail}. In case \texttt{sb} does not start with \texttt{c} then
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
309 |
the parser returns the empty set (in Scala \texttt{Set()}).
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
310 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
311 |
More interesting are the parser combinators that build larger parsers
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
312 |
out of smaller component parsers. For example the alternative
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
313 |
parser combinator is as follows.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
314 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
315 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
316 |
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
317 |
class AltParser[I, T]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
318 |
(p: => Parser[I, T],
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
319 |
q: => Parser[I, T]) extends Parser[I, T] {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
320 |
def parse(sb: I) = p.parse(sb) ++ q.parse(sb)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
321 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
322 |
\end{lstlisting}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
323 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
324 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
325 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
326 |
The types of this parser combinator are polymorphic (we just have \texttt{I}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
327 |
for the input type, and \texttt{T} for the output type). The alternative parser
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
328 |
builds a new parser out of two existing parser combinator \texttt{p} and \texttt{q}.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
329 |
Both need to be able to process input of type \texttt{I} and return the same
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
330 |
output type \texttt{Set[(T, I)]}. (There is an interesting detail of Scala, namely the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
331 |
\texttt{=>} in front of the types of \texttt{p} and \texttt{q}. They will prevent the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
332 |
evaluation of the arguments before they are used. This is often called
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
333 |
\emph{lazy evaluation} of the arguments.) The alternative parser should run
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
334 |
the input with the first parser \texttt{p} (producing a set of outputs) and then
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
335 |
run the same input with \texttt{q}. The result should be then just the union
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
336 |
of both sets, which is the operation \texttt{++} in Scala.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
337 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
338 |
This parser combinator already allows us to construct a parser that either
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
339 |
a character \texttt{a} or \texttt{b}, as
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
340 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
341 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
342 |
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
343 |
new AltParser(CharParser('a'), CharParser('b'))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
344 |
\end{lstlisting}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
345 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
346 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
347 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
348 |
Scala allows us to introduce some more readable shorthand notation for this, like \texttt{'a' || 'b'}.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
349 |
We can call this parser combinator with the strings
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
350 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
351 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
352 |
\begin{tabular}{rcl}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
353 |
input string & & output\medskip\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
354 |
\texttt{\Grid{ac}} & $\rightarrow$ & $\left\{(\texttt{\Grid{a}}, \texttt{\Grid{c}})\right\}$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
355 |
\texttt{\Grid{bc}} & $\rightarrow$ & $\left\{(\texttt{\Grid{b}}, \texttt{\Grid{c}})\right\}$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
356 |
\texttt{\Grid{cc}} & $\rightarrow$ & $\varnothing$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
357 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
358 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
359 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
360 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
361 |
We receive in the first two cases a successful output (that is a non-empty set).
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
362 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
363 |
A bit more interesting is the \emph{sequence parser combinator} implemented in
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
364 |
Scala as follows:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
365 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
366 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
367 |
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
368 |
class SeqParser[I, T, S]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
369 |
(p: => Parser[I, T],
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
370 |
q: => Parser[I, S]) extends Parser[I, (T, S)] {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
371 |
def parse(sb: I) =
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
372 |
for ((head1, tail1) <- p.parse(sb);
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
373 |
(head2, tail2) <- q.parse(tail1))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
374 |
yield ((head1, head2), tail2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
375 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
376 |
\end{lstlisting}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
377 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
378 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
379 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
380 |
This parser takes as input two parsers, \texttt{p} and \texttt{q}. It implements \texttt{parse}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
381 |
as follows: let first run the parser \texttt{p} on the input producing a set of pairs (\texttt{head1}, \texttt{tail1}).
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
382 |
The \texttt{tail1} stands for the unprocessed parts left over by \texttt{p}.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
383 |
Let \texttt{q} run on these unprocessed parts
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
384 |
producing again a set of pairs. The output of the sequence parser combinator is then a set
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
385 |
containing pairs where the first components are again pairs, namely what the first parser could parse
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
386 |
together with what the second parser could parse; the second component is the unprocessed
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
387 |
part left over after running the second parser \texttt{q}. Therefore the input type of
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
388 |
the sequence parser combinator is as usual \texttt{I}, but the output type is
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
389 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
390 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
391 |
\texttt{Set[((T, S), I)]}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
392 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
393 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
394 |
Scala allows us to provide some
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
395 |
shorthand notation for the sequence parser combinator. So we can write for
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
396 |
example \texttt{'a' $\sim$ 'b'}, which is the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
397 |
parser combinator that first consumes the character \texttt{a} from a string and then \texttt{b}.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
398 |
Calling this parser combinator with the strings
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
399 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
400 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
401 |
\begin{tabular}{rcl}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
402 |
input string & & output\medskip\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
403 |
\texttt{\Grid{abc}} & $\rightarrow$ & $\left\{((\texttt{\Grid{a}}, \texttt{\Grid{b}}), \texttt{\Grid{c}})\right\}$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
404 |
\texttt{\Grid{bac}} & $\rightarrow$ & $\varnothing$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
405 |
\texttt{\Grid{ccc}} & $\rightarrow$ & $\varnothing$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
406 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
407 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
408 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
409 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
410 |
A slightly more complicated parser is \texttt{('a' || 'b') $\sim$ 'b'} which parses as first character either
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
411 |
an \texttt{a} or \texttt{b} followed by a \texttt{b}. This parser produces the following results.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
412 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
413 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
414 |
\begin{tabular}{rcl}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
415 |
input string & & output\medskip\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
416 |
\texttt{\Grid{abc}} & $\rightarrow$ & $\left\{((\texttt{\Grid{a}}, \texttt{\Grid{b}}), \texttt{\Grid{c}})\right\}$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
417 |
\texttt{\Grid{bbc}} & $\rightarrow$ & $\left\{((\texttt{\Grid{b}}, \texttt{\Grid{b}}), \texttt{\Grid{c}})\right\}$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
418 |
\texttt{\Grid{aac}} & $\rightarrow$ & $\varnothing$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
419 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
420 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
421 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
422 |
Note carefully that constructing the parser \texttt{'a' || ('a' $\sim$ 'b')} will result in a tying error.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
423 |
The first parser has as output type a single character (recall the type of \texttt{CharParser}),
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
424 |
but the second parser produces a pair of characters as output. The alternative parser is however
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
425 |
required to have both component parsers to have the same type. We will see later how we can
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
426 |
build this parser without the typing error.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
427 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
428 |
The next parser combinator does not actually combine smaller parsers, but applies
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
429 |
a function to the result of the parser. It is implemented in Scala as follows
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
430 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
431 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
432 |
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
433 |
class FunParser[I, T, S]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
434 |
(p: => Parser[I, T],
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
435 |
f: T => S) extends Parser[I, S] {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
436 |
def parse(sb: I) =
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
437 |
for ((head, tail) <- p.parse(sb)) yield (f(head), tail)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
438 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
439 |
\end{lstlisting}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
440 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
441 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
442 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
443 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
444 |
This parser combinator takes a parser \texttt{p} with output type \texttt{T} as
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
445 |
input as well as a function \texttt{f} with type \texttt{T => S}. The parser \texttt{p}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
446 |
produces sets of type \texttt{(T, I)}. The \texttt{FunParser} combinator then
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
447 |
applies the function \texttt{f} to all the parer outputs. Since this function
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
448 |
is of type \texttt{T => S}, we obtain a parser with output type \texttt{S}.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
449 |
Again Scala lets us introduce some shorthand notation for this parser combinator.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
450 |
Therefore we will write \texttt{p ==> f} for it.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
451 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
452 |
%\bigskip
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
453 |
%takes advantage of the full generality---have a look
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
454 |
%what it produces if we call it with the string \texttt{abc}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
455 |
%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
456 |
%\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
457 |
%\begin{tabular}{rcl}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
458 |
%input string & & output\medskip\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
459 |
%\texttt{\Grid{abc}} & $\rightarrow$ & $\left\{((\texttt{\Grid{a}}, \texttt{\Grid{b}}), \texttt{\Grid{c}})\right\}$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
460 |
%\texttt{\Grid{bbc}} & $\rightarrow$ & $\left\{((\texttt{\Grid{b}}, \texttt{\Grid{b}}), \texttt{\Grid{c}})\right\}$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
461 |
%\texttt{\Grid{aac}} & $\rightarrow$ & $\varnothing$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
462 |
%\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
463 |
%\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
464 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
465 |
|
173
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
466 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
467 |
\end{document}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
468 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
469 |
%%% Local Variables:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
470 |
%%% mode: latex
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
471 |
%%% TeX-master: t
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
472 |
%%% End:
|