584
|
1 |
|
595
|
2 |
% !TEX program = xelatex
|
173
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
3 |
\documentclass{article}
|
297
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
4 |
\usepackage{../style}
|
217
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
5 |
\usepackage{../langs}
|
588
|
6 |
\usepackage{../grammar}
|
799
|
7 |
\usepackage{../graphics}
|
173
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
8 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
9 |
\begin{document}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
10 |
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
11 |
\section*{Handout 6 (Parser Combinators)}
|
173
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
12 |
|
584
|
13 |
This handout explains how \emph{parser combinators} work and how they
|
587
|
14 |
can be implemented in Scala. Their most distinguishing feature is that
|
|
15 |
they are very easy to implement (admittedly it is only easy in a
|
|
16 |
functional programming language). Another good point of parser
|
|
17 |
combinators is that they can deal with any kind of input as long as
|
|
18 |
this input is of ``sequence-kind'', for example a string or a list of
|
|
19 |
tokens. The only two properties of the input we need is to be able to
|
|
20 |
test when it is empty and ``sequentially'' take it apart. Strings and
|
|
21 |
lists fit this bill. However, parser combinators also have their
|
|
22 |
drawbacks. For example they require that the grammar to be parsed is
|
|
23 |
\emph{not} left-recursive and they are efficient only when the grammar
|
|
24 |
is unambiguous. It is the responsibility of the grammar designer to
|
591
|
25 |
ensure these two properties hold.
|
173
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
26 |
|
587
|
27 |
The general idea behind parser combinators is to transform the input
|
|
28 |
into sets of pairs, like so
|
175
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
29 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
30 |
\begin{center}
|
385
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
31 |
$\underbrace{\text{list of tokens}}_{\text{input}}$
|
594
|
32 |
$\quad\Rightarrow\quad$
|
591
|
33 |
$\underbrace{\text{set of (parsed part, unprocessed part)}}_{\text{output}}$
|
385
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
34 |
\end{center}
|
175
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
35 |
|
587
|
36 |
\noindent
|
590
|
37 |
Given the extended effort we have spent implementing a lexer in order
|
591
|
38 |
to generate lists of tokens, it might be surprising that in what
|
|
39 |
follows we shall often use strings as input, rather than lists of
|
|
40 |
tokens. This is for making the explanation more lucid and for quick
|
|
41 |
examples. It does not make our previous work on lexers obsolete
|
|
42 |
(remember they transform a string into a list of tokens). Lexers will
|
|
43 |
still be needed for building a somewhat realistic compiler.
|
584
|
44 |
|
590
|
45 |
As mentioned above, parser combinators are relatively agnostic about what
|
587
|
46 |
kind of input they process. In my Scala code I use the following
|
|
47 |
polymorphic types for parser combinators:
|
176
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
48 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
49 |
\begin{center}
|
584
|
50 |
input:\;\; \texttt{I} \qquad output:\;\; \texttt{T}
|
176
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
51 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
52 |
|
587
|
53 |
\noindent That is they take as input something of type \texttt{I} and
|
590
|
54 |
return a set of pairs of type \texttt{Set[(T, I)]}. Since the input
|
|
55 |
needs to be of ``sequence-kind'', I actually have to often write
|
591
|
56 |
\texttt{I <\% Seq[\_]} for the input type. This ensures the
|
|
57 |
input is a subtype of Scala sequences. The first component of the
|
|
58 |
generated pairs corresponds to what the parser combinator was able to
|
|
59 |
parse from the input and the second is the unprocessed, or
|
|
60 |
leftover, part of the input (therefore the type of this unprocessed part is
|
|
61 |
the same as the input). A parser combinator might return more than one
|
|
62 |
such pair; the idea is that there are potentially several ways of how
|
|
63 |
to parse the input. As a concrete example, consider the string
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
64 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
65 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
66 |
\tt\Grid{iffoo\VS testbar}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
67 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
68 |
|
385
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
69 |
\noindent We might have a parser combinator which tries to
|
386
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
70 |
interpret this string as a keyword (\texttt{if}) or as an
|
385
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
71 |
identifier (\texttt{iffoo}). Then the output will be the set
|
177
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
72 |
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
73 |
\begin{center}
|
386
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
74 |
$\left\{ \left(\texttt{\Grid{if}}\;,\; \texttt{\Grid{foo\VS testbar}}\right),
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
75 |
\left(\texttt{\Grid{iffoo}}\;,\; \texttt{\Grid{\VS testbar}}\right) \right\}$
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
76 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
77 |
|
587
|
78 |
\noindent where the first pair means the parser could recognise
|
590
|
79 |
\texttt{if} from the input and leaves the \texttt{foo\VS testbar} as
|
591
|
80 |
unprocessed part; in the other case it could recognise
|
587
|
81 |
\texttt{iffoo} and leaves \texttt{\VS testbar} as unprocessed. If the
|
|
82 |
parser cannot recognise anything from the input at all, then parser
|
|
83 |
combinators just return the empty set $\{\}$. This will indicate
|
|
84 |
something ``went wrong''\ldots or more precisely, nothing could be
|
385
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
85 |
parsed.
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
86 |
|
594
|
87 |
Also important to note is that the output type \texttt{T} for the
|
|
88 |
processed part can potentially be different from the input type
|
|
89 |
\texttt{I} in the parser. In the example above is just happens to be
|
|
90 |
the same. The reason for the difference is that in general we are
|
|
91 |
interested in transforming our input into something
|
|
92 |
``different''\ldots for example into a tree; or if we implement the
|
|
93 |
grammar for arithmetic expressions, we might be interested in the
|
|
94 |
actual integer number the arithmetic expression, say \texttt{1 + 2 *
|
|
95 |
3}, stands for. In this way we can use parser combinators to
|
|
96 |
implement relatively easily a calculator, for instance (we shall do
|
|
97 |
this later on).
|
584
|
98 |
|
594
|
99 |
The main driving force behind parser combinators is that we can easily
|
|
100 |
build parser combinators out of smaller components following very
|
|
101 |
closely the structure of a grammar. In order to implement this in a
|
591
|
102 |
functional/object-oriented programming language, like Scala, we need
|
|
103 |
to specify an abstract class for parser combinators. In the abstract
|
|
104 |
class we specify that \texttt{I} is the \emph{input type} of the
|
593
|
105 |
parser combinator and that \texttt{T} is the \emph{output type}. This
|
591
|
106 |
implies that the function \texttt{parse} takes an argument of type
|
|
107 |
\texttt{I} and returns a set of type \mbox{\texttt{Set[(T, I)]}}.
|
177
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
108 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
109 |
\begin{center}
|
385
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
110 |
\begin{lstlisting}[language=Scala]
|
177
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
111 |
abstract class Parser[I, T] {
|
590
|
112 |
def parse(in: I) : Set[(T, I)]
|
177
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
113 |
|
590
|
114 |
def parse_all(in: I) : Set[T] =
|
|
115 |
for ((head, tail) <- parse(in); if (tail.isEmpty))
|
177
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
116 |
yield head
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
117 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
118 |
\end{lstlisting}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
119 |
\end{center}
|
176
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
120 |
|
591
|
121 |
\noindent It is the obligation in each instance of this class to
|
584
|
122 |
supply an implementation for \texttt{parse}. From this function we
|
|
123 |
can then ``centrally'' derive the function \texttt{parse\_all}, which
|
|
124 |
just filters out all pairs whose second component is not empty (that
|
|
125 |
is has still some unprocessed part). The reason is that at the end of
|
|
126 |
the parsing we are only interested in the results where all the input
|
|
127 |
has been consumed and no unprocessed part is left over.
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
128 |
|
385
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
129 |
One of the simplest parser combinators recognises just a
|
584
|
130 |
single character, say $c$, from the beginning of strings. Its
|
385
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
131 |
behaviour can be described as follows:
|
176
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
132 |
|
177
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
133 |
\begin{itemize}
|
584
|
134 |
\item If the head of the input string starts with a $c$, then return
|
|
135 |
the set
|
|
136 |
\[\{(c, \textit{tail of}\; s)\}\]
|
|
137 |
where \textit{tail of}
|
|
138 |
$s$ is the unprocessed part of the input string.
|
|
139 |
\item Otherwise return the empty set $\{\}$.
|
177
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
140 |
\end{itemize}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
141 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
142 |
\noindent
|
590
|
143 |
The input type of this simple parser combinator is \texttt{String} and
|
|
144 |
the output type is \texttt{Char}. This means \texttt{parse} returns
|
|
145 |
\mbox{\texttt{Set[(Char, String)]}}. The code in Scala is as follows:
|
177
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
146 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
147 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
148 |
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
149 |
case class CharParser(c: Char) extends Parser[String, Char] {
|
587
|
150 |
def parse(in: String) =
|
|
151 |
if (in.head == c) Set((c, in.tail)) else Set()
|
177
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
152 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
153 |
\end{lstlisting}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
154 |
\end{center}
|
176
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
155 |
|
589
|
156 |
\noindent You can see \texttt{parse} tests whether the
|
587
|
157 |
first character of the input string \texttt{in} is equal to
|
584
|
158 |
\texttt{c}. If yes, then it splits the string into the recognised part
|
587
|
159 |
\texttt{c} and the unprocessed part \texttt{in.tail}. In case
|
|
160 |
\texttt{in} does not start with \texttt{c} then the parser returns the
|
584
|
161 |
empty set (in Scala \texttt{Set()}). Since this parser recognises
|
|
162 |
characters and just returns characters as the processed part, the
|
|
163 |
output type of the parser is \texttt{Char}.
|
|
164 |
|
|
165 |
If we want to parse a list of tokens and interested in recognising a
|
590
|
166 |
number token, for example, we could write something like this
|
584
|
167 |
|
|
168 |
\begin{center}
|
|
169 |
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily,numbers=none]
|
|
170 |
case object NumParser extends Parser[List[Token], Int] {
|
|
171 |
def parse(ts: List[Token]) = ts match {
|
|
172 |
case Num_token(s)::ts => Set((s.toInt, ts))
|
|
173 |
case _ => Set ()
|
|
174 |
}
|
|
175 |
}
|
|
176 |
\end{lstlisting}
|
|
177 |
\end{center}
|
|
178 |
|
|
179 |
\noindent
|
|
180 |
In this parser the input is of type \texttt{List[Token]}. The function
|
|
181 |
parse looks at the input \texttt{ts} and checks whether the first
|
589
|
182 |
token is a \texttt{Num\_token} (let us assume our lexer generated
|
|
183 |
these tokens for numbers). But this parser does not just return this
|
584
|
184 |
token (and the rest of the list), like the \texttt{CharParser} above,
|
590
|
185 |
rather it extracts also the string \texttt{s} from the token and
|
|
186 |
converts it into an integer. The hope is that the lexer did its work
|
|
187 |
well and this conversion always succeeds. The consequence of this is
|
|
188 |
that the output type for this parser is \texttt{Int}, not
|
|
189 |
\texttt{Token}. Such a conversion would be needed if we want to
|
|
190 |
implement a simple calculator program, because string-numbers need to
|
|
191 |
be transformed into \texttt{Int}-numbers in order to do the
|
|
192 |
calculations.
|
385
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
193 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
194 |
|
584
|
195 |
These simple parsers that just look at the input and do a simple
|
|
196 |
transformation are often called \emph{atomic} parser combinators.
|
|
197 |
More interesting are the parser combinators that build larger parsers
|
587
|
198 |
out of smaller component parsers. There are three such parser
|
|
199 |
combinators that can be implemented generically. The \emph{alternative
|
584
|
200 |
parser combinator} is as follows: given two parsers, say, $p$ and
|
|
201 |
$q$, we apply both parsers to the input (remember parsers are
|
587
|
202 |
functions) and combine the output (remember they are sets of pairs):
|
|
203 |
|
|
204 |
\begin{center}
|
|
205 |
$p(\text{input}) \cup q(\text{input})$
|
|
206 |
\end{center}
|
|
207 |
|
|
208 |
\noindent In Scala we can implement alternative parser
|
|
209 |
combinator as follows
|
|
210 |
|
|
211 |
\begin{center}
|
|
212 |
\begin{lstlisting}[language=Scala, numbers=none]
|
|
213 |
class AltParser[I, T]
|
|
214 |
(p: => Parser[I, T],
|
|
215 |
q: => Parser[I, T]) extends Parser[I, T] {
|
|
216 |
def parse(in: I) = p.parse(in) ++ q.parse(in)
|
|
217 |
}
|
|
218 |
\end{lstlisting}
|
|
219 |
\end{center}
|
|
220 |
|
|
221 |
\noindent The types of this parser combinator are again generic (we
|
|
222 |
have \texttt{I} for the input type, and \texttt{T} for the output
|
|
223 |
type). The alternative parser builds a new parser out of two existing
|
590
|
224 |
parsers \texttt{p} and \texttt{q} which are given as arguments. Both
|
|
225 |
parsers need to be able to process input of type \texttt{I} and return
|
|
226 |
in \texttt{parse} the same output type \texttt{Set[(T,
|
587
|
227 |
I)]}.\footnote{There is an interesting detail of Scala, namely the
|
|
228 |
\texttt{=>} in front of the types of \texttt{p} and \texttt{q}. They
|
|
229 |
will prevent the evaluation of the arguments before they are
|
|
230 |
used. This is often called \emph{lazy evaluation} of the
|
590
|
231 |
arguments. We will explain this later.} The alternative parser runs
|
|
232 |
the input with the first parser \texttt{p} (producing a set of pairs)
|
|
233 |
and then runs the same input with \texttt{q} (producing another set of
|
|
234 |
pairs). The result should be then just the union of both sets, which
|
|
235 |
is the operation \texttt{++} in Scala.
|
587
|
236 |
|
|
237 |
The alternative parser combinator allows us to construct a parser that
|
|
238 |
parses either a character \texttt{a} or \texttt{b} using the
|
|
239 |
\texttt{CharParser} shown above. For this we can write
|
|
240 |
|
|
241 |
\begin{center}
|
|
242 |
\begin{lstlisting}[language=Scala, numbers=none]
|
|
243 |
new AltParser(CharParser('a'), CharParser('b'))
|
|
244 |
\end{lstlisting}
|
|
245 |
\end{center}
|
|
246 |
|
|
247 |
\noindent Later on we will use Scala mechanism for introducing some
|
799
|
248 |
more readable shorthand notation for this, like \texttt{p"a" ||
|
|
249 |
p"b"}. Let us look in detail at what this parser combinator produces
|
590
|
250 |
with some sample strings.
|
587
|
251 |
|
|
252 |
\begin{center}
|
|
253 |
\begin{tabular}{rcl}
|
|
254 |
input strings & & output\medskip\\
|
|
255 |
\texttt{\Grid{acde}} & $\rightarrow$ & $\left\{(\texttt{\Grid{a}}, \texttt{\Grid{cde}})\right\}$\\
|
|
256 |
\texttt{\Grid{bcde}} & $\rightarrow$ & $\left\{(\texttt{\Grid{b}}, \texttt{\Grid{cde}})\right\}$\\
|
|
257 |
\texttt{\Grid{ccde}} & $\rightarrow$ & $\{\}$
|
|
258 |
\end{tabular}
|
|
259 |
\end{center}
|
|
260 |
|
|
261 |
\noindent We receive in the first two cases a successful
|
|
262 |
output (that is a non-empty set). In each case, either
|
591
|
263 |
\pcode{a} or \pcode{b} is in the parsed part, and
|
587
|
264 |
\pcode{cde} in the unprocessed part. Clearly this parser cannot
|
|
265 |
parse anything with \pcode{ccde}, therefore the empty
|
|
266 |
set is returned.
|
|
267 |
|
|
268 |
A bit more interesting is the \emph{sequence parser combinator}. Given
|
|
269 |
two parsers, say again, $p$ and $q$, we want to apply first the input
|
590
|
270 |
to $p$ producing a set of pairs; then apply $q$ to all the unparsed
|
587
|
271 |
parts in the pairs; and then combine the results. Mathematically we would
|
591
|
272 |
write something like this for the set of pairs:
|
587
|
273 |
|
|
274 |
\begin{center}
|
|
275 |
\begin{tabular}{lcl}
|
|
276 |
$\{((\textit{output}_1, \textit{output}_2), u_2)$ & $\,|\,$ &
|
|
277 |
$(\textit{output}_1, u_1) \in p(\text{input})
|
|
278 |
\;\wedge\;$\\
|
|
279 |
&& $(\textit{output}_2, u_2) \in q(u_1)\}$
|
|
280 |
\end{tabular}
|
|
281 |
\end{center}
|
|
282 |
|
|
283 |
\noindent Notice that the $p$ will first be run on the input,
|
590
|
284 |
producing pairs of the form $(\textit{output}_1, u_1)$ where the $u_1$
|
591
|
285 |
stands for the unprocessed, or leftover, parts of $p$. We want that
|
590
|
286 |
$q$ runs on all these unprocessed parts $u_1$. Therefore these
|
|
287 |
unprocessed parts are fed into the second parser $q$. The overall
|
|
288 |
result of the sequence parser combinator is pairs of the form
|
584
|
289 |
$((\textit{output}_1, \textit{output}_2), u_2)$. This means the
|
593
|
290 |
unprocessed part of the sequence parser combinator is the unprocessed
|
591
|
291 |
part the second parser $q$ leaves as leftover. The parsed parts of the
|
|
292 |
component parsers are combined in a pair, namely
|
|
293 |
$(\textit{output}_1, \textit{output}_2)$. The reason is we want to
|
|
294 |
know what $p$ and $q$ were able to parse. This behaviour can be
|
|
295 |
implemented in Scala as follows:
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
296 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
297 |
\begin{center}
|
385
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
298 |
\begin{lstlisting}[language=Scala,numbers=none]
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
299 |
class SeqParser[I, T, S]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
300 |
(p: => Parser[I, T],
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
301 |
q: => Parser[I, S]) extends Parser[I, (T, S)] {
|
587
|
302 |
def parse(in: I) =
|
|
303 |
for ((output1, u1) <- p.parse(in);
|
386
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
304 |
(output2, u2) <- q.parse(u1))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
305 |
yield ((output1, output2), u2)
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
306 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
307 |
\end{lstlisting}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
308 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
309 |
|
587
|
310 |
\noindent This parser takes again as arguments two parsers, \texttt{p}
|
591
|
311 |
and \texttt{q}. It implements \texttt{parse} as follows: first run the
|
|
312 |
parser \texttt{p} on the input producing a set of pairs
|
587
|
313 |
(\texttt{output1}, \texttt{u1}). The \texttt{u1} stands for the
|
591
|
314 |
unprocessed parts left over by \texttt{p} (recall that there can be
|
|
315 |
several such pairs). Let then \texttt{q} run on these unprocessed
|
|
316 |
parts producing again a set of pairs. The output of the sequence
|
|
317 |
parser combinator is then a set containing pairs where the first
|
|
318 |
components are again pairs, namely what the first parser could parse
|
|
319 |
together with what the second parser could parse; the second component
|
|
320 |
is the unprocessed part left over after running the second parser
|
|
321 |
\texttt{q}. Note that the input type of the sequence parser combinator
|
|
322 |
is as usual \texttt{I}, but the output type is
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
323 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
324 |
\begin{center}
|
590
|
325 |
\texttt{(T, S)}
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
326 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
327 |
|
584
|
328 |
\noindent
|
591
|
329 |
Consequently, the function \texttt{parse} in the sequence parser
|
|
330 |
combinator returns sets of type \texttt{Set[((T, S), I)]}. That means
|
|
331 |
we have essentially two output types for the sequence parser
|
|
332 |
combinator (packaged in a pair), because in general \textit{p} and
|
|
333 |
\textit{q} might produce different things (for example we recognise a
|
|
334 |
number with \texttt{p} and then with \texttt{q} a string corresponding
|
|
335 |
to an operator). If any of the runs of \textit{p} and \textit{q}
|
|
336 |
fail, that is produce the empty set, then \texttt{parse} will also
|
|
337 |
produce the empty set.
|
584
|
338 |
|
587
|
339 |
With the shorthand notation we shall introduce later for the sequence
|
799
|
340 |
parser combinator, we can write for example \pcode{p"a" ~ p"b"}, which
|
587
|
341 |
is the parser combinator that first recognises the character
|
|
342 |
\texttt{a} from a string and then \texttt{b}. Let us look again at
|
591
|
343 |
some examples of how this parser combinator processes some strings:
|
385
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
344 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
345 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
346 |
\begin{tabular}{rcl}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
347 |
input strings & & output\medskip\\
|
584
|
348 |
\texttt{\Grid{abcde}} & $\rightarrow$ & $\left\{((\texttt{\Grid{a}}, \texttt{\Grid{b}}), \texttt{\Grid{cde}})\right\}$\\
|
|
349 |
\texttt{\Grid{bacde}} & $\rightarrow$ & $\{\}$\\
|
|
350 |
\texttt{\Grid{cccde}} & $\rightarrow$ & $\{\}$
|
385
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
351 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
352 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
353 |
|
586
|
354 |
\noindent In the first line we have a successful parse, because the
|
587
|
355 |
string starts with \texttt{ab}, which is the prefix we are looking
|
584
|
356 |
for. But since the parsing combinator is constructed as sequence of
|
|
357 |
the two simple (atomic) parsers for \texttt{a} and \texttt{b}, the
|
|
358 |
result is a nested pair of the form \texttt{((a, b), cde)}. It is
|
586
|
359 |
\emph{not} a simple pair \texttt{(ab, cde)} as one might erroneously
|
587
|
360 |
expect. The parser returns the empty set in the other examples,
|
584
|
361 |
because they do not fit with what the parser is supposed to parse.
|
|
362 |
|
|
363 |
|
799
|
364 |
A slightly more complicated parser is \pcode{(p"a" || p"b") ~ p"c"} which
|
587
|
365 |
parses as first character either an \texttt{a} or \texttt{b}, followed
|
|
366 |
by a \texttt{c}. This parser produces the following outputs.
|
385
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
367 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
368 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
369 |
\begin{tabular}{rcl}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
370 |
input strings & & output\medskip\\
|
585
|
371 |
\texttt{\Grid{acde}} & $\rightarrow$ & $\left\{((\texttt{\Grid{a}}, \texttt{\Grid{c}}), \texttt{\Grid{de}})\right\}$\\
|
|
372 |
\texttt{\Grid{bcde}} & $\rightarrow$ & $\left\{((\texttt{\Grid{b}}, \texttt{\Grid{c}}), \texttt{\Grid{de}})\right\}$\\
|
|
373 |
\texttt{\Grid{abde}} & $\rightarrow$ & $\{\}$
|
385
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
374 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
375 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
376 |
|
585
|
377 |
\noindent
|
799
|
378 |
Now consider the parser \pcode{(p"a" ~ p"b") ~ p"c"} which parses
|
585
|
379 |
\texttt{a}, \texttt{b}, \texttt{c} in sequence. This parser produces
|
|
380 |
the following outputs.
|
|
381 |
|
|
382 |
\begin{center}
|
|
383 |
\begin{tabular}{rcl}
|
|
384 |
input strings & & output\medskip\\
|
|
385 |
\texttt{\Grid{abcde}} & $\rightarrow$ & $\left\{(((\texttt{\Grid{a}},\texttt{\Grid{b}}), \texttt{\Grid{c}}), \texttt{\Grid{de}})\right\}$\\
|
|
386 |
\texttt{\Grid{abde}} & $\rightarrow$ & $\{\}$\\
|
|
387 |
\texttt{\Grid{bcde}} & $\rightarrow$ & $\{\}$
|
|
388 |
\end{tabular}
|
|
389 |
\end{center}
|
|
390 |
|
|
391 |
|
|
392 |
\noindent The second and third example fail, because something is
|
590
|
393 |
``missing'' in the sequence we are looking for. The first succeeds but
|
|
394 |
notice how the results nest with sequences: the parsed part is a
|
|
395 |
nested pair of the form \pcode{((a, b), c)}. If we nest the sequence
|
799
|
396 |
parser differently, say \pcode{p"a" ~ (p"b" ~ p"c")}, then also
|
590
|
397 |
our output pairs nest differently
|
589
|
398 |
|
|
399 |
\begin{center}
|
|
400 |
\begin{tabular}{rcl}
|
|
401 |
input strings & & output\medskip\\
|
|
402 |
\texttt{\Grid{abcde}} & $\rightarrow$ & $\left\{((\texttt{\Grid{a}},(\texttt{\Grid{b}}, \texttt{\Grid{c}})), \texttt{\Grid{de}})\right\}$\\
|
|
403 |
\end{tabular}
|
|
404 |
\end{center}
|
|
405 |
|
|
406 |
\noindent
|
|
407 |
Two more examples: first consider the parser
|
799
|
408 |
\pcode{(p"a" ~ p"a") ~ p"a"} and the input \pcode{aaaa}:
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
409 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
410 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
411 |
\begin{tabular}{rcl}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
412 |
input string & & output\medskip\\
|
385
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
413 |
\texttt{\Grid{aaaa}} & $\rightarrow$ &
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
414 |
$\left\{(((\texttt{\Grid{a}}, \texttt{\Grid{a}}), \texttt{\Grid{a}}), \texttt{\Grid{a}})\right\}$\\
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
415 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
416 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
417 |
|
591
|
418 |
\noindent Notice again how the results nest deeper and deeper as pairs (the
|
585
|
419 |
last \pcode{a} is in the unprocessed part). To consume everything of
|
799
|
420 |
this string we can use the parser \pcode{((p"a" ~ p"a") ~ p"a") ~
|
|
421 |
p"a"}. Then the output is as follows:
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
422 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
423 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
424 |
\begin{tabular}{rcl}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
425 |
input string & & output\medskip\\
|
385
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
426 |
\texttt{\Grid{aaaa}} & $\rightarrow$ &
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
427 |
$\left\{((((\texttt{\Grid{a}}, \texttt{\Grid{a}}), \texttt{\Grid{a}}), \texttt{\Grid{a}}), \texttt{""})\right\}$\\
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
428 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
429 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
430 |
|
385
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
431 |
\noindent This is an instance where the parser consumed
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
432 |
completely the input, meaning the unprocessed part is just the
|
587
|
433 |
empty string. So if we called \pcode{parse_all}, instead of \pcode{parse},
|
585
|
434 |
we would get back the result
|
|
435 |
|
|
436 |
\[
|
|
437 |
\left\{(((\texttt{\Grid{a}}, \texttt{\Grid{a}}), \texttt{\Grid{a}}), \texttt{\Grid{a}})\right\}
|
|
438 |
\]
|
|
439 |
|
|
440 |
\noindent where the unprocessed (empty) parts have been stripped away
|
|
441 |
from the pairs; everything where the second part was not empty has
|
587
|
442 |
been thrown away as well, because they represent
|
590
|
443 |
ultimately-unsuccessful-parses. The main point is that the sequence
|
|
444 |
parser combinator returns pairs that can nest according to the
|
|
445 |
nesting of the component parsers.
|
385
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
446 |
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
447 |
|
799
|
448 |
Consider also carefully that constructing a parser such \pcode{p"a" ||
|
|
449 |
(p"a" ~ p"b")} will result in a typing error. The intention with this
|
591
|
450 |
parser is that we want to parse either an \texttt{a}, or an \texttt{a}
|
590
|
451 |
followed by a \texttt{b}. However, the first parser has as output type
|
|
452 |
a single character (recall the type of \texttt{CharParser}), but the
|
|
453 |
second parser produces a pair of characters as output. The alternative
|
|
454 |
parser is required to have both component parsers to have the same
|
591
|
455 |
type---the reason is that we need to be able to build the union of two
|
|
456 |
sets, which requires in Scala that the sets have the same type. Since
|
|
457 |
they are not in this case, there is a typing error. We will see later
|
|
458 |
how we can build this parser without the typing error.
|
385
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
459 |
|
587
|
460 |
The next parser combinator, called \emph{semantic action}, does not
|
591
|
461 |
actually combine two smaller parsers, but applies a function to the result
|
587
|
462 |
of a parser. It is implemented in Scala as follows
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
463 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
464 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
465 |
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
|
799
|
466 |
class MapParser[I, T, S]
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
467 |
(p: => Parser[I, T],
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
468 |
f: T => S) extends Parser[I, S] {
|
587
|
469 |
def parse(in: I) =
|
|
470 |
for ((head, tail) <- p.parse(in)) yield (f(head), tail)
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
471 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
472 |
\end{lstlisting}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
473 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
474 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
475 |
|
590
|
476 |
\noindent This parser combinator takes a parser \texttt{p} (with input
|
|
477 |
type \texttt{I} and output type \texttt{T}) as one argument but also a
|
|
478 |
function \texttt{f} (with type \texttt{T => S}). The parser \texttt{p}
|
|
479 |
produces sets of type \texttt{Set[(T, I)]}. The semantic action
|
|
480 |
combinator then applies the function \texttt{f} to all the `processed'
|
|
481 |
parser outputs. Since this function is of type \texttt{T => S}, we
|
|
482 |
obtain a parser with output type \texttt{S}. Again Scala lets us
|
|
483 |
introduce some shorthand notation for this parser
|
799
|
484 |
combinator. Therefore we will write short \texttt{p.map(f)} for it.
|
386
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
485 |
|
589
|
486 |
What are semantic actions good for? Well, they allow you to transform
|
590
|
487 |
the parsed input into datastructures you can use for further
|
591
|
488 |
processing. A simple (contrived) example would be to transform parsed
|
|
489 |
characters into ASCII numbers. Suppose we define a function \texttt{f}
|
|
490 |
(from characters to \texttt{Int}s) and use a \texttt{CharParser} for parsing
|
589
|
491 |
the character \texttt{c}.
|
587
|
492 |
|
591
|
493 |
|
587
|
494 |
\begin{center}
|
|
495 |
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
|
|
496 |
val f = (c: Char) => c.toInt
|
|
497 |
val c = new CharParser('c')
|
|
498 |
\end{lstlisting}
|
|
499 |
\end{center}
|
|
500 |
|
|
501 |
\noindent
|
589
|
502 |
We then can run the following two parsers on the input \texttt{cbd}:
|
587
|
503 |
|
|
504 |
\begin{center}
|
|
505 |
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
|
|
506 |
c.parse("cbd")
|
799
|
507 |
c.map(f).parse("cbd")
|
587
|
508 |
\end{lstlisting}
|
|
509 |
\end{center}
|
|
510 |
|
|
511 |
\noindent
|
589
|
512 |
In the first line we obtain the expected result \texttt{Set(('c',
|
|
513 |
"bd"))}, whereas the second produces \texttt{Set((99, "bd"))}---the
|
|
514 |
character has been transformed into an ASCII number.
|
588
|
515 |
|
|
516 |
A slightly less contrived example is about parsing numbers (recall
|
591
|
517 |
\texttt{NumParser} above). However, we want to do this here for
|
|
518 |
strings, not for tokens. For this assume we have the following
|
|
519 |
(atomic) \texttt{RegexParser}.
|
588
|
520 |
|
|
521 |
\begin{center}
|
|
522 |
\begin{lstlisting}[language=Scala,xleftmargin=0mm,
|
|
523 |
basicstyle=\small\ttfamily, numbers=none]
|
|
524 |
import scala.util.matching.Regex
|
|
525 |
|
|
526 |
case class RegexParser(reg: Regex) extends Parser[String, String] {
|
|
527 |
def parse(in: String) = reg.findPrefixMatchOf(in) match {
|
|
528 |
case None => Set()
|
|
529 |
case Some(m) => Set((m.matched, m.after.toString))
|
|
530 |
}
|
|
531 |
}
|
|
532 |
\end{lstlisting}
|
|
533 |
\end{center}
|
|
534 |
|
|
535 |
\noindent
|
|
536 |
This parser takes a regex as argument and splits up a string into a
|
|
537 |
prefix and the rest according to this regex
|
|
538 |
(\texttt{reg.findPrefixMatchOf} generates a match---in the successful
|
|
539 |
case---and the corresponding strings can be extracted with
|
591
|
540 |
\texttt{matched} and \texttt{after}). The input and output type for
|
|
541 |
this parser is \texttt{String}. Using \texttt{RegexParser} we can
|
|
542 |
define a \texttt{NumParser} for \texttt{Strings} to \texttt{Int} as
|
|
543 |
follows:
|
588
|
544 |
|
|
545 |
\begin{center}
|
|
546 |
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
|
|
547 |
val NumParser = RegexParser("[0-9]+".r)
|
|
548 |
\end{lstlisting}
|
|
549 |
\end{center}
|
|
550 |
|
|
551 |
\noindent
|
591
|
552 |
This parser will recognise a number at the beginning of a string. For
|
588
|
553 |
example
|
|
554 |
|
|
555 |
\begin{center}
|
|
556 |
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
|
|
557 |
NumParser.parse("123abc")
|
|
558 |
\end{lstlisting}
|
|
559 |
\end{center}
|
|
560 |
|
|
561 |
\noindent
|
|
562 |
produces \texttt{Set((123,abc))}. The problem is that \texttt{123} is
|
590
|
563 |
still a string (the required double-quotes are not printed by
|
|
564 |
Scala). We want to convert this string into the corresponding
|
|
565 |
\texttt{Int}. We can do this as follows using a semantic action
|
588
|
566 |
|
|
567 |
\begin{center}
|
|
568 |
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
|
799
|
569 |
NumParser.map{s => s.toInt}.parse("123abc")
|
588
|
570 |
\end{lstlisting}
|
|
571 |
\end{center}
|
|
572 |
|
|
573 |
\noindent
|
589
|
574 |
The function in the semantic action converts a string into an
|
591
|
575 |
\texttt{Int}. Now \texttt{parse} generates \texttt{Set((123,abc))},
|
|
576 |
but this time \texttt{123} is an \texttt{Int}. Let us come back to
|
|
577 |
semantic actions when we are going to implement actual context-free
|
593
|
578 |
grammars.
|
587
|
579 |
|
|
580 |
\subsubsection*{Shorthand notation for parser combinators}
|
|
581 |
|
|
582 |
Before we proceed, let us just explain the shorthand notation for
|
|
583 |
parser combinators. Like for regular expressions, the shorthand notation
|
590
|
584 |
will make our life much easier when writing actual parsers. We can define
|
591
|
585 |
some implicits which allow us to write
|
|
586 |
|
|
587 |
\begin{center}
|
|
588 |
\begin{tabular}{ll}
|
799
|
589 |
\pcode{p || q} & alternative parser\\
|
591
|
590 |
\pcode{p ~ q} & sequence parser\\
|
799
|
591 |
\pcode{p.map(f)} & semantic action parser
|
591
|
592 |
\end{tabular}
|
|
593 |
\end{center}
|
|
594 |
|
|
595 |
\noindent
|
799
|
596 |
as well as to use string interpolations for specifying simple string parsers.
|
590
|
597 |
|
|
598 |
The idea is that this shorthand notation allows us to easily translate
|
|
599 |
context-free grammars into code. For example recall our context-free
|
|
600 |
grammar for palindromes:
|
|
601 |
|
|
602 |
\begin{plstx}[margin=3cm]
|
591
|
603 |
: \meta{Pal} ::= a\cdot \meta{Pal}\cdot a | b\cdot \meta{Pal}\cdot b | a | b | \epsilon\\
|
590
|
604 |
\end{plstx}
|
|
605 |
|
|
606 |
\noindent
|
|
607 |
Each alternative in this grammar translates into an alternative parser
|
|
608 |
combinator. The $\cdot$ can be translated to a sequence parser
|
|
609 |
combinator. The parsers for $a$, $b$ and $\epsilon$ can be simply
|
799
|
610 |
written as \texttt{p"a"}, \texttt{p"b"} and \texttt{p""}.
|
590
|
611 |
|
587
|
612 |
|
386
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
613 |
\subsubsection*{How to build parsers using parser combinators?}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
614 |
|
588
|
615 |
The beauty of parser combinators is the ease with which they can be
|
|
616 |
implemented and how easy it is to translate context-free grammars into
|
|
617 |
code (though the grammars need to be non-left-recursive). To
|
591
|
618 |
demonstrate this consider again the grammar for palindromes from above.
|
590
|
619 |
The first idea would be to translate it into the following code
|
588
|
620 |
|
|
621 |
\begin{center}
|
|
622 |
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
|
|
623 |
lazy val Pal : Parser[String, String] =
|
799
|
624 |
((p"a" ~ Pal ~ p"a") || (p"b" ~ Pal ~ p"b") || p"a" || p"b" || p"")
|
588
|
625 |
\end{lstlisting}
|
|
626 |
\end{center}
|
|
627 |
|
|
628 |
\noindent
|
590
|
629 |
Unfortunately, this does not quite work yet as it produces a typing
|
799
|
630 |
error. The reason is that the parsers \texttt{p"a"}, \texttt{p"b"} and
|
|
631 |
\texttt{p""} all produce strings as output type and therefore can be
|
|
632 |
put into an alternative \texttt{...|| p"a" || p"b" || p""}. But both
|
|
633 |
sequence parsers \pcode{p"a" ~ Pal ~ p"a"} and \pcode{p"b" ~ Pal ~ p"b"}
|
591
|
634 |
produce pairs of the form
|
|
635 |
|
|
636 |
\begin{center}
|
|
637 |
(((\texttt{a}-part, \texttt{Pal}-part), \texttt{a}-part), unprocessed part)
|
|
638 |
\end{center}
|
|
639 |
|
|
640 |
\noindent That is how the
|
|
641 |
sequence parser combinator nests results when \pcode{\~} is used
|
|
642 |
between two components. The solution is to use a semantic action that
|
|
643 |
``flattens'' these pairs and appends the corresponding strings, like
|
588
|
644 |
|
|
645 |
\begin{center}
|
|
646 |
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
|
|
647 |
lazy val Pal : Parser[String, String] =
|
799
|
648 |
((p"a" ~ Pal ~ p"a").map{ case ((x, y), z) => x + y + z } ||
|
|
649 |
(p"b" ~ Pal ~ p"b").map{ case ((x, y), z) => x + y + z } ||
|
|
650 |
p"a" || p"b" || p"")
|
588
|
651 |
\end{lstlisting}
|
|
652 |
\end{center}
|
|
653 |
|
589
|
654 |
\noindent
|
591
|
655 |
How does this work? Well, recall again what the pairs look like for
|
799
|
656 |
the parser \pcode{p"a" ~ Pal ~ p"a"}. The pattern in the semantic
|
591
|
657 |
action matches the nested pairs (the \texttt{x} with the
|
|
658 |
\texttt{a}-part and so on). Unfortunately when we have such nested
|
|
659 |
pairs, Scala requires us to define the function using the
|
|
660 |
\pcode{case}-syntax
|
|
661 |
|
|
662 |
\begin{center}
|
|
663 |
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
|
|
664 |
{ case ((x, y), z) => ... }
|
|
665 |
\end{lstlisting}
|
|
666 |
\end{center}
|
|
667 |
|
|
668 |
\noindent
|
|
669 |
If we have more sequence parser combinators or have them differently nested,
|
|
670 |
then the pattern in the semantic action needs to be adjusted accordingly.
|
|
671 |
The action we implement above is to concatenate all three strings, which
|
|
672 |
means after the semantic action is applied the output type of the parser
|
|
673 |
is \texttt{String}, which means it fits with the alternative parsers
|
799
|
674 |
\texttt{...|| p"a" || p"b" || p""}.
|
591
|
675 |
|
|
676 |
If we run the parser above with \pcode{Pal.parse_all("abaaaba")} we obtain
|
593
|
677 |
as result the \pcode{Set(abaaaba)}, which indicates that the string is a palindrome
|
591
|
678 |
(an empty set would mean something is wrong). But also notice what the
|
|
679 |
intermediate results are generated by \pcode{Pal.parse("abaaaba")}
|
|
680 |
|
|
681 |
\begin{center}
|
|
682 |
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
|
|
683 |
Set((abaaaba,""),(aba,aaba), (a,baaaba), ("",abaaaba))
|
|
684 |
\end{lstlisting}
|
|
685 |
\end{center}
|
|
686 |
|
|
687 |
\noindent
|
|
688 |
That there are more than one output might be slightly unexpected, but
|
|
689 |
can be explained as follows: the pairs represent all possible
|
|
690 |
(partial) parses of the string \pcode{"abaaaba"}. The first pair above
|
593
|
691 |
corresponds to a complete parse (all output is consumed) and this is
|
591
|
692 |
what \pcode{Pal.parse_all} returns. The second pair is a small
|
|
693 |
``sub-palindrome'' that can also be parsed, but the parse fails with
|
|
694 |
the rest \pcode{aaba}, which is therefore left as unprocessed. The
|
|
695 |
third one is an attempt to parse the whole string with the
|
|
696 |
single-character parser \pcode{a}. That of course only partially
|
|
697 |
succeeds, by leaving \pcode{"baaaba"} as the unprocessed
|
593
|
698 |
part. Finally, since we allow the empty string to be a palindrome we
|
591
|
699 |
also obtain the last pair, where actually nothing is consumed from the
|
|
700 |
input string. While all this works as intended, we need to be careful
|
|
701 |
with this (especially with including the \pcode{""} parser in our
|
|
702 |
grammar): if during parsing the set of parsing attempts gets too big,
|
|
703 |
then the parsing process can become very slow as the potential
|
|
704 |
candidates for applying rules can snowball.
|
589
|
705 |
|
|
706 |
|
591
|
707 |
Important is also to note is that we must define the
|
|
708 |
\texttt{Pal}-parser as a \emph{lazy} value in Scala. Look again at the
|
|
709 |
code: \texttt{Pal} occurs on the right-hand side of the definition. If we had
|
|
710 |
just written
|
|
711 |
|
|
712 |
\begin{center}
|
|
713 |
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
|
|
714 |
val Pal : Parser[String, String] = ...rhs...
|
|
715 |
\end{lstlisting}
|
|
716 |
\end{center}
|
|
717 |
|
589
|
718 |
\noindent
|
593
|
719 |
then Scala before making this assignment to \texttt{Pal} attempts to
|
591
|
720 |
find out what the expression on the right-hand side evaluates to. This
|
|
721 |
is straightforward in case of simple expressions \texttt{2 + 3}, but
|
|
722 |
the expression above contains \texttt{Pal} in the right-hand
|
|
723 |
side. Without \pcode{lazy} it would try to evaluate what \texttt{Pal}
|
|
724 |
evaluates to and start a new recursion, which means it falls into an
|
|
725 |
infinite loop. The definition of \texttt{Pal} is recursive and the
|
|
726 |
\pcode{lazy} key-word prevents it from being fully evaluated. Therefore
|
|
727 |
whenever we want to define a recursive parser we have to write
|
|
728 |
|
|
729 |
\begin{center}
|
|
730 |
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
|
|
731 |
lazy val SomeParser : Parser[...,...] = ...rhs...
|
|
732 |
\end{lstlisting}
|
|
733 |
\end{center}
|
|
734 |
|
|
735 |
\noindent That was not necessary for our atomic parsers, like
|
|
736 |
\texttt{RegexParser} or \texttt{CharParser}, because they are not recursive.
|
|
737 |
Note that this is also the reason why we had to write
|
|
738 |
|
|
739 |
\begin{center}
|
|
740 |
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
|
|
741 |
class AltParser[I, T]
|
|
742 |
(p: => Parser[I, T],
|
|
743 |
q: => Parser[I, T]) extends Parser[I, T] {...}
|
|
744 |
|
|
745 |
class SeqParser[I, T, S]
|
|
746 |
(p: => Parser[I, T],
|
|
747 |
q: => Parser[I, S]) extends Parser[I, (T, S)] {...}
|
|
748 |
\end{lstlisting}
|
|
749 |
\end{center}
|
|
750 |
|
|
751 |
\noindent where the \texttt{\textbf{\textcolor{codepurple}{=>}}} in front of
|
|
752 |
the argument types for \texttt{p} and \texttt{q} prevent Scala from
|
|
753 |
evaluating the arguments. Normally, Scala would first evaluate what
|
|
754 |
kind of parsers \texttt{p} and \texttt{q} are, and only then generate
|
593
|
755 |
the alternative parser combinator, respectively sequence parser
|
|
756 |
combinator. Since the arguments can be recursive parsers, such as
|
591
|
757 |
\texttt{Pal}, this would lead again to an infinite loop.
|
|
758 |
|
|
759 |
As a final example in this section, let us consider the grammar for
|
|
760 |
well-nested parentheses:
|
|
761 |
|
|
762 |
\begin{plstx}[margin=3cm]
|
|
763 |
: \meta{P} ::= (\cdot \meta{P}\cdot ) \cdot \meta{P} | \epsilon\\
|
|
764 |
\end{plstx}
|
|
765 |
|
|
766 |
\noindent
|
|
767 |
Let us assume we want to not just recognise strings of
|
593
|
768 |
well-nested parentheses but also transform round parentheses
|
591
|
769 |
into curly braces. We can do this by using a semantic
|
|
770 |
action:
|
|
771 |
|
|
772 |
\begin{center}
|
|
773 |
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily,
|
|
774 |
xleftmargin=0mm, numbers=none]
|
|
775 |
lazy val P : Parser[String, String] =
|
799
|
776 |
(p"(" ~ P ~ p")" ~ P).map{ case (((_,x),_),y) => "{" + x + "}" + y } || p""
|
591
|
777 |
\end{lstlisting}
|
|
778 |
\end{center}
|
|
779 |
|
|
780 |
\noindent
|
|
781 |
Here we define a function where which ignores the parentheses in the
|
|
782 |
pairs, but replaces them in the right places with curly braces when
|
|
783 |
assembling the new string in the right-hand side. If we run
|
|
784 |
\pcode{P.parse_all("(((()()))())")} we obtain
|
|
785 |
\texttt{Set(\{\{\{\{\}\{\}\}\}\{\}\})} as expected.
|
|
786 |
|
|
787 |
|
588
|
788 |
|
386
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
789 |
\subsubsection*{Implementing an Interpreter}
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
790 |
|
593
|
791 |
The first step before implementing an interpreter for a full-blown
|
592
|
792 |
language is to implement a simple calculator for arithmetic
|
|
793 |
expressions. Suppose our arithmetic expressions are given by the
|
|
794 |
grammar:
|
|
795 |
|
|
796 |
\begin{plstx}[margin=3cm,one per line]
|
593
|
797 |
: \meta{E} ::= \meta{E} \cdot + \cdot \meta{E}
|
592
|
798 |
| \meta{E} \cdot - \cdot \meta{E}
|
|
799 |
| \meta{E} \cdot * \cdot \meta{E}
|
|
800 |
| ( \cdot \meta{E} \cdot )
|
|
801 |
| Number \\
|
|
802 |
\end{plstx}
|
|
803 |
|
|
804 |
\noindent
|
|
805 |
Naturally we want to implement the grammar in such a way that we can
|
593
|
806 |
calculate what the result of, for example, \texttt{4*2+3} is---we are
|
|
807 |
interested in an \texttt{Int} rather than a string. This means every
|
|
808 |
component parser needs to have as output type \texttt{Int} and when we
|
|
809 |
assemble the intermediate results, strings like \texttt{"+"},
|
|
810 |
\texttt{"*"} and so on, need to be translated into the appropriate
|
|
811 |
Scala operation of adding, multiplying and so on. Being inspired by
|
|
812 |
the parser for well-nested parentheses above and ignoring the fact
|
|
813 |
that we want $*$ to take precedence over $+$ and $-$, we might want to
|
|
814 |
write something like
|
592
|
815 |
|
|
816 |
\begin{center}
|
|
817 |
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
|
|
818 |
lazy val E: Parser[String, Int] =
|
799
|
819 |
((E ~ p"+" ~ E).map{ case ((x, y), z) => x + z} ||
|
|
820 |
(E ~ p"-" ~ E).map{ case ((x, y), z) => x - z} ||
|
|
821 |
(E ~ p"*" ~ E).map{ case ((x, y), z) => x * z} ||
|
|
822 |
(p"(" ~ E ~ p")").map{ case ((x, y), z) => y} ||
|
592
|
823 |
NumParserInt)
|
|
824 |
\end{lstlisting}
|
|
825 |
\end{center}
|
|
826 |
|
|
827 |
\noindent
|
593
|
828 |
Consider again carefully how the semantic actions pick out the correct
|
|
829 |
arguments for the calculation. In case of plus, we need \texttt{x} and
|
|
830 |
\texttt{z}, because they correspond to the results of the component
|
|
831 |
parser \texttt{E}. We can just add \texttt{x + z} in order to obtain
|
|
832 |
an \texttt{Int} because the output type of \texttt{E} is
|
|
833 |
\texttt{Int}. Similarly with subtraction and multiplication. In
|
|
834 |
contrast in the fourth clause we need to return \texttt{y}, because it
|
|
835 |
is the result enclosed inside the parentheses. The information about
|
|
836 |
parentheses, roughly speaking, we just throw away.
|
592
|
837 |
|
|
838 |
So far so good. The problem arises when we try to call \pcode{parse_all} with the
|
|
839 |
expression \texttt{"1+2+3"}. Lets try it
|
|
840 |
|
|
841 |
\begin{center}
|
|
842 |
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
|
|
843 |
E.parse_all("1+2+3")
|
|
844 |
\end{lstlisting}
|
|
845 |
\end{center}
|
|
846 |
|
|
847 |
\noindent
|
593
|
848 |
\ldots and we wait and wait and \ldots still wait. What is the
|
|
849 |
problem? Actually, the parser just fell into an infinite loop! The
|
|
850 |
reason is that the above grammar is left-recursive and recall that our
|
|
851 |
parser combinators cannot deal with such left-recursive
|
|
852 |
grammars. Fortunately, every left-recursive context-free grammar can be
|
|
853 |
transformed into a non-left-recursive grammars that still recognises
|
|
854 |
the same strings. This allows us to design the following grammar
|
|
855 |
|
|
856 |
\begin{plstx}[margin=3cm]
|
|
857 |
: \meta{E} ::= \meta{T} \cdot + \cdot \meta{E} | \meta{T} \cdot - \cdot \meta{E} | \meta{T}\\
|
|
858 |
: \meta{T} ::= \meta{F} \cdot * \cdot \meta{T} | \meta{F}\\
|
|
859 |
: \meta{F} ::= ( \cdot \meta{E} \cdot ) | Number\\
|
|
860 |
\end{plstx}
|
|
861 |
|
|
862 |
\noindent
|
|
863 |
Recall what left-recursive means from Handout 5 and make sure you see
|
|
864 |
why this grammar is \emph{non} left-recursive. This version of the grammar
|
|
865 |
also deals with the fact that $*$ should have a higher precedence. This does not
|
|
866 |
affect which strings this grammar can recognise, but in which order we are going
|
|
867 |
to evaluate any arithmetic expression. We can translate this grammar into
|
|
868 |
parsing combinators as follows:
|
592
|
869 |
|
|
870 |
|
593
|
871 |
\begin{center}
|
|
872 |
\begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none]
|
|
873 |
lazy val E: Parser[String, Int] =
|
799
|
874 |
(T ~ p"+" ~ E).map{ case ((x, y), z) => x + z } ||
|
|
875 |
(T ~ p"-" ~ E).map{ case ((x, y), z) => x - z } || T
|
593
|
876 |
lazy val T: Parser[String, Int] =
|
799
|
877 |
(F ~ p"*" ~ T).map{ case ((x, y), z) => x * z } || F
|
593
|
878 |
lazy val F: Parser[String, Int] =
|
799
|
879 |
(p"(" ~ E ~ p")").map{ case ((x, y), z) => y } || NumParserInt
|
593
|
880 |
\end{lstlisting}
|
|
881 |
\end{center}
|
592
|
882 |
|
593
|
883 |
\noindent
|
594
|
884 |
Let us try out some examples:
|
592
|
885 |
|
593
|
886 |
\begin{center}
|
|
887 |
\begin{tabular}{rcl}
|
|
888 |
input strings & & output of \pcode{parse_all}\medskip\\
|
|
889 |
\texttt{\Grid{1+2+3}} & $\rightarrow$ & \texttt{Set(6)}\\
|
|
890 |
\texttt{\Grid{4*2+3}} & $\rightarrow$ & \texttt{Set(11)}\\
|
|
891 |
\texttt{\Grid{4*(2+3)}} & $\rightarrow$ & \texttt{Set(20)}\\
|
594
|
892 |
\texttt{\Grid{(4)*((2+3))}} & $\rightarrow$ & \texttt{Set(20)}\\
|
593
|
893 |
\texttt{\Grid{4/2+3}} & $\rightarrow$ & \texttt{Set()}\\
|
|
894 |
\texttt{\Grid{1\VS +\VS 2\VS +\VS 3}} & $\rightarrow$ & \texttt{Set()}\\
|
|
895 |
\end{tabular}
|
|
896 |
\end{center}
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
897 |
|
593
|
898 |
\noindent
|
594
|
899 |
Note that we call \pcode{parse_all}, not \pcode{parse}. The examples
|
|
900 |
should be quite self-explanatory. The last two example do not produce
|
|
901 |
any integer result because our parser does not define what to do in
|
|
902 |
case of division (could be easily added), but also has no idea what to
|
595
|
903 |
do with whitespaces. To deal with them is the task of the lexer! Yes,
|
594
|
904 |
we can deal with them inside the grammar, but that would render many
|
|
905 |
grammars becoming unintelligible, including this one.\footnote{If you
|
|
906 |
think an easy solution is to extend the notion of what a number
|
|
907 |
should be, then think again---you still would have to deal with
|
595
|
908 |
cases like \texttt{\Grid{(\VS (\VS 2+3)\VS )}}. Just think of the mess
|
|
909 |
you would have in a grammar for a full-blown language where there are
|
|
910 |
numerous such cases.}
|
173
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
911 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
912 |
\end{document}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
913 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
914 |
%%% Local Variables:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
915 |
%%% mode: latex
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
916 |
%%% TeX-master: t
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
917 |
%%% End:
|