1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
"http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>
<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.06">
<TITLE>
Streams and parsers
</TITLE>
</HEAD>
<BODY TEXT=black BGCOLOR=white>
<A HREF="tutorial001.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial003.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>
<TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#2de52d"><DIV ALIGN=center><TABLE>
<TR><TD><A NAME="htoc6"><B><FONT SIZE=6>Chapter 2</FONT></B></A></TD>
<TD WIDTH="100%" ALIGN=center><B><FONT SIZE=6>Streams and parsers</FONT></B></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE>
<A NAME="c:tutstrm"></A>
The first extension provided by Camlp4 is streams and parsers. A
stream is a value of the abstract type <CODE>'a Stream.t</CODE>. It is like
a list but where only the first element is available: to read the
second element you have to remove the first one from the stream. A
parser is a function of type <CODE>'a Stream.t -> 'b</CODE> which makes a
kind of pattern matching inside a stream.<BR>
<BR>
<A NAME="toc5"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#66ff66"><DIV ALIGN=center><TABLE>
<TR><TD><A NAME="htoc7"><B><FONT SIZE=5>2.1</FONT></B></A></TD>
<TD WIDTH="100%" ALIGN=center><B><FONT SIZE=5>Streams</FONT></B></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE><BR>
<TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#7fff7f"><DIV ALIGN=center><TABLE>
<TR><TD><A NAME="htoc8"><B><FONT SIZE=4>2.1.1</FONT></B></A></TD>
<TD WIDTH="100%" ALIGN=center><B><FONT SIZE=4>Streams constructor</FONT></B></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE><BR>
A first way to create a stream is to use the parentheses <CODE>[<</CODE> and
<CODE>>]</CODE>. There are two kinds of elements: simple elements prefixed
by a quote <CODE>'</CODE> and stream elements not prefixed by it. The stream
is composed of the list of the simple and stream elements read in
their order.<BR>
<BR>
Examples:
<PRE>
[< '3; '1; '4; '1; '5 >]
</PRE>
is a stream of these integers.
<PRE>
# let s = [< '"hello"; '"world" >];;
# let t = [< '"I"; '"say"; s; '"as"; '"an"; '"example" >];;
</PRE>
The above stream <CODE>t</CODE> is the stream of the strings: "I", "say",
"hello", "world", "as", "an", "example".<BR>
<BR>
To look (destructively) inside a stream, you can use the function
<CODE>Stream.next</CODE>, removing the first element from the stream and
returning it.<BR>
<BR>
The streams are lazy values. You can create infinite streams, like
this one, the stream of all integers:
<PRE>
# let rec f n = [< 'n; f (n + 1) >];;
# let s = f 0;;
</PRE>
<TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#7fff7f"><DIV ALIGN=center><TABLE>
<TR><TD><A NAME="htoc9"><B><FONT SIZE=4>2.1.2</FONT></B></A></TD>
<TD WIDTH="100%" ALIGN=center><B><FONT SIZE=4>Streams builders</FONT></B></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE><BR>
A second way to create streams are the streams builders. They are:
<UL><LI><CODE>Stream.of_string</CODE>: returns the character stream of the
string given as parameter.<BR>
<BR>
<LI><CODE>Stream.of_channel</CODE>: returns the character stream of the
input channel.<BR>
<BR>
<LI><CODE>Stream.of_list</CODE>: returns the stream of the list elemnts.<BR>
<BR>
<LI><CODE>Stream.from</CODE>: given a function, returns the stream
composed of the values returned by the function. See the library
module <CODE>Stream</CODE> for details.</UL>
Warning: the streams created by these stream builders are much more
efficient than the one created by the stream constructors, but they
cannot be inserted in them.<BR>
<BR>
<A NAME="toc6"></A><TABLE CELLPADDING=0 CELLSPACING=0 WIDTH="100%">
<TR><TD BGCOLOR="#66ff66"><DIV ALIGN=center><TABLE>
<TR><TD><A NAME="htoc10"><B><FONT SIZE=5>2.2</FONT></B></A></TD>
<TD WIDTH="100%" ALIGN=center><B><FONT SIZE=5>Parsers</FONT></B></TD>
</TR></TABLE></DIV></TD>
</TR></TABLE><BR>
The parsers are functions to look inside the streams.<BR>
<BR>
A parser is introduced by the keyword <CODE>parser</CODE>. It is like the
<CODE>function</CODE> statement, but with stream patterns instead of
pattern. For example, the function <CODE>Stream.next</CODE> introduced in
the previous section is defined as:
<PRE>
parser [< 'x >] -> x
</PRE>
A parser can return with 3 different ways:
<UL><LI>Either by a normal value, indicating that a stream pattern
matched the beginning of the stream.<BR>
<BR>
<LI>Or by raising the exception <CODE>Stream.Failure</CODE>, indicating
that no first element of the patterns matched the stream; in this case
the stream had not been modified.<BR>
<BR>
<LI>Or by raising the exception <CODE>Stream.Error</CODE>, indicating that
a first element of a pattern matched the input stream, but the rest
did not.</UL>
Example:
<PRE>
# let p = parser [< '3; '1; '4 >] -> "hey";;
# p [< '3; '1; '4 >];;
string : "hey"
# p [< '3; '1; '4; '1; '5; '9 >];;
string : "hey"
# p [< '1; '1; '4 >];;
Exception: Stream.Failure
# p [< '3; '2; '4 >];;
Exception: Stream.Error ""
</PRE>
The exceptio <CODE>Stream.Error</CODE> has a string parameter. You can
specify which string, in the parser, after the stream pattern element
and the token <CODE>??</CODE>. For example:
<PRE>
# let p =
parser [< '3; '1 ?? "1 expected"; '4 ?? "4 expected" >] -> "hey"
;;
</PRE>
Note that the first stream pattern element does not accept this
extension since the parser raises <CODE>Stream.Failure</CODE> if it is not
recognized.<BR>
<BR>
A parser can call another parser. You can specify that as a stream
pattern element with syntax:
<PRE>
pattern = expression
</PRE>
Example, with a recursive call:
<PRE>
# type tok = If | Then | Else | Let | In | Equal | Ident of int;;
# let rec expr =
parser
[< 'If; x = expr; 'Then; y = expr; 'Else; z = expr >] -> "if"
| [< 'Let; 'Ident x; 'Equal; x = expr; 'In; y = expr >] -> "let"
;;
</PRE>
Note that a parser is not a system of grammars. You cannot use left
recursion:
<PRE>
(* BAD EXAMPLE! *)
# let rec expr = parser [< x = expr; 'Equal; y = expr >] -> x;;
</PRE>
Which would loop when called, exactly like a function would.<BR>
<BR>
And you cannot start two patterns with the same elements. Only the
first one would be applied:
<PRE>
(* BAD EXAMPLE! *)
# let rec expr =
parser
[< 'If; x = expr; 'Then; y = expr; 'Else; z = expr >] -> "if"
| [< 'If; x = expr; 'Then; y = expr >] -> "ifnoelse"
;;
</PRE>
If you want to do that, you need to left factorize your rules:
<PRE>
# let rec expr =
parser
[< 'If; x = expr; 'Then; y = expr; v = expr_kont >] -> v
and expr_kont =
parser
[< 'Else; z = expr >] -> "if"
| [< >] -> "ifnoelse"
;;
</PRE>
or with an anonymous parser:
<PRE>
# let rec expr =
parser
[< 'If; x = expr; 'Then; y = expr;
v =
parser
[< 'Else; z = expr >] -> "if"
| [< >] -> "ifnoelse" >] -> v
;;
</PRE>
<I><FONT COLOR=maroon>
<br>
For remarks about Camlp4, write to:
<img src="http://cristal.inria.fr/~ddr/images/email.jpg" alt=email align=top>
</FONT></I><HR>
<A HREF="tutorial001.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial003.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
|
