Previous Up Next
Chapter 2 Streams and parsers
The first extension provided by Camlp4 is streams and parsers. A stream is a value of the abstract type 'a Stream.t. 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 'a Stream.t -> 'b which makes a kind of pattern matching inside a stream.

2.1 Streams

2.1.1 Streams constructor

A first way to create a stream is to use the parentheses [< and >]. There are two kinds of elements: simple elements prefixed by a quote ' and stream elements not prefixed by it. The stream is composed of the list of the simple and stream elements read in their order.

Examples:
     [< '3; '1; '4; '1; '5 >]
is a stream of these integers.
     # let s = [< '"hello"; '"world" >];;
     # let t = [< '"I"; '"say"; s; '"as"; '"an"; '"example" >];;
The above stream t is the stream of the strings: "I", "say", "hello", "world", "as", "an", "example".

To look (destructively) inside a stream, you can use the function Stream.next, removing the first element from the stream and returning it.

The streams are lazy values. You can create infinite streams, like this one, the stream of all integers:
     # let rec f n = [< 'n; f (n + 1) >];;
     # let s = f 0;;
2.1.2 Streams builders

A second way to create streams are the streams builders. They are: 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.

2.2 Parsers

The parsers are functions to look inside the streams.

A parser is introduced by the keyword parser. It is like the function statement, but with stream patterns instead of pattern. For example, the function Stream.next introduced in the previous section is defined as:
     parser [< 'x >] -> x
A parser can return with 3 different ways: Example:
     # 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 ""
The exceptio Stream.Error has a string parameter. You can specify which string, in the parser, after the stream pattern element and the token ??. For example:
     # let p =
         parser [< '3; '1 ?? "1 expected"; '4 ?? "4 expected" >] -> "hey"
       ;;
Note that the first stream pattern element does not accept this extension since the parser raises Stream.Failure if it is not recognized.

A parser can call another parser. You can specify that as a stream pattern element with syntax:
     pattern = expression
Example, with a recursive call:
     # 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"
       ;;
Note that a parser is not a system of grammars. You cannot use left recursion:
     (* BAD EXAMPLE! *)
     # let rec expr = parser [< x = expr; 'Equal; y = expr >] -> x;;
Which would loop when called, exactly like a function would.

And you cannot start two patterns with the same elements. Only the first one would be applied:
     (* BAD EXAMPLE! *)
     # let rec expr =
         parser
           [< 'If; x = expr; 'Then; y = expr; 'Else; z = expr >] -> "if"
         | [< 'If; x = expr; 'Then; y = expr >] -> "ifnoelse"
       ;;
If you want to do that, you need to left factorize your rules:
     # let rec expr =
         parser
           [< 'If; x = expr; 'Then; y = expr; v = expr_kont >] -> v
       and expr_kont =
         parser
           [< 'Else; z = expr >] -> "if"
         | [< >] -> "ifnoelse"
       ;;
or with an anonymous parser:
     # let rec expr =
         parser
           [< 'If; x = expr; 'Then; y = expr;
              v =
                parser
                  [< 'Else; z = expr >] -> "if"
                | [< >] -> "ifnoelse" >] -> v
       ;;


Previous Up Next