Streams and parsers

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:

Stream.of_string: returns the character stream of the string given as parameter.
Stream.of_channel: returns the character stream of the input channel.
Stream.of_list: returns the stream of the list elemnts.
Stream.from: given a function, returns the stream composed of the values returned by the function. See the library module Stream for details.

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:

Either by a normal value, indicating that a stream pattern matched the beginning of the stream.
Or by raising the exception Stream.Failure, indicating that no first element of the patterns matched the stream; in this case the stream had not been modified.
Or by raising the exception Stream.Error, indicating that a first element of a pattern matched the input stream, but the rest did not.

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
       ;;