105 functional/object-oriented programming language, like Scala, we need |
105 functional/object-oriented programming language, like Scala, we need |
106 to specify an abstract class for parser combinators. In the abstract |
106 to specify an abstract class for parser combinators. In the abstract |
107 class we specify that \texttt{I} is the \emph{input type} of the |
107 class we specify that \texttt{I} is the \emph{input type} of the |
108 parser combinator and that \texttt{T} is the \emph{output type}. This |
108 parser combinator and that \texttt{T} is the \emph{output type}. This |
109 implies that the function \texttt{parse} takes an argument of type |
109 implies that the function \texttt{parse} takes an argument of type |
110 \texttt{I} and returns a set of type \mbox{\texttt{Set[(T, I)]}}. |
110 \texttt{I} and returns a set of type \mbox{\texttt{Set[(T, |
|
111 I)]}}.\footnote{In the actual code on KEATS there is some |
|
112 kerfuffle about correct type-bounds and using clauses. Ignore this |
|
113 part of the implementation for the moment---it is not needed for |
|
114 understanding how the code works.} |
111 |
115 |
112 \begin{center} |
116 \begin{center} |
113 \begin{lstlisting}[language=Scala] |
117 \begin{lstlisting}[language=Scala] |
114 abstract class Parser[I, T](using is: I => Seq[_]) { |
118 abstract class Parser[I, T] { |
115 def parse(in: I): Set[(T, I)] |
119 def parse(in: I): Set[(T, I)] |
116 |
120 |
117 def parse_all(in: I) : Set[T] = |
121 def parse_all(in: I) : Set[T] = |
118 for ((hd, tl) <- parse(in); |
122 for ((hd, tl) <- parse(in); |
119 if is(tl).isEmpty) yield hd |
123 if tl.isEmpty) yield hd |
120 } |
124 } |
121 \end{lstlisting} |
125 \end{lstlisting} |
122 \end{center} |
126 \end{center} |
123 |
127 |
124 \noindent It is the obligation in each instance of this class to |
128 \noindent It is the obligation in each instance of this class to |
212 |
216 |
213 \begin{center} |
217 \begin{center} |
214 \begin{lstlisting}[language=Scala, numbers=none] |
218 \begin{lstlisting}[language=Scala, numbers=none] |
215 class AltParser[I, T] |
219 class AltParser[I, T] |
216 (p: => Parser[I, T], |
220 (p: => Parser[I, T], |
217 q: => Parser[I, T])(using I => Seq[_]) |
221 q: => Parser[I, T]) extends Parser[I, T] { |
218 extends Parser[I, T] { |
|
219 def parse(in: I) = p.parse(in) ++ q.parse(in) |
222 def parse(in: I) = p.parse(in) ++ q.parse(in) |
220 } |
223 } |
221 \end{lstlisting} |
224 \end{lstlisting} |
222 \end{center} |
225 \end{center} |
223 |
226 |
304 |
307 |
305 \begin{center} |
308 \begin{center} |
306 \begin{lstlisting}[language=Scala,numbers=none] |
309 \begin{lstlisting}[language=Scala,numbers=none] |
307 class SeqParser[I, T, S] |
310 class SeqParser[I, T, S] |
308 (p: => Parser[I, T], |
311 (p: => Parser[I, T], |
309 q: => Parser[I, S])(using I => Seq[_]) |
312 q: => Parser[I, S]) extends Parser[I, (T, S)] { |
310 extends Parser[I, (T, S)] { |
|
311 def parse(in: I) = |
313 def parse(in: I) = |
312 for ((output1, u1) <- p.parse(in); |
314 for ((output1, u1) <- p.parse(in); |
313 (output2, u2) <- q.parse(u1)) |
315 (output2, u2) <- q.parse(u1)) |
314 yield ((output1, output2), u2) |
316 yield ((output1, output2), u2) |
315 } |
317 } |
481 |
483 |
482 \begin{center} |
484 \begin{center} |
483 \begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none] |
485 \begin{lstlisting}[language=Scala,basicstyle=\small\ttfamily, numbers=none] |
484 class MapParser[I, T, S] |
486 class MapParser[I, T, S] |
485 (p: => Parser[I, T], |
487 (p: => Parser[I, T], |
486 f: T => S)(using I => Seq[_]) extends Parser[I, S] { |
488 f: T => S) extends Parser[I, S] { |
487 def parse(in: I) = |
489 def parse(in: I) = |
488 for ((hd, tl) <- p.parse(in)) yield (f(hd), tl) |
490 for ((hd, tl) <- p.parse(in)) yield (f(hd), tl) |
489 } |
491 } |
490 \end{lstlisting} |
492 \end{lstlisting} |
491 \end{center} |
493 \end{center} |
591 \noindent |
593 \noindent |
592 The function in the semantic action converts a string into an |
594 The function in the semantic action converts a string into an |
593 \texttt{Int}. Now \texttt{parse} generates \texttt{Set((123,abc))}, |
595 \texttt{Int}. Now \texttt{parse} generates \texttt{Set((123,abc))}, |
594 but this time \texttt{123} is an \texttt{Int}. Think carefully what |
596 but this time \texttt{123} is an \texttt{Int}. Think carefully what |
595 the input and output type of the parser is without the semantic action |
597 the input and output type of the parser is without the semantic action |
596 adn what with the semantic action (the type of the function can |
598 and what with the semantic action (the type of the function can |
597 already tell you). Let us come back to semantic actions when we are |
599 already tell you). Let us come back to semantic actions when we are |
598 going to implement actual context-free grammars. |
600 going to implement actual context-free grammars. |
599 |
601 |
600 \subsubsection*{Shorthand notation for parser combinators} |
602 \subsubsection*{Shorthand notation for parser combinators} |
601 |
603 |