Functional parsers

Functional parsers

Purely functional parsers are an alternative of stream parsers where the used stream type is a lazy non-destructive type. These streams are lazy values, as in classical stream parsers, but the values are not removed as long as the parsing advances.

To make them work, the parsers of purely functional streams return, not the simple values, but a value of type option : “None” meaning “no match” (the equivalent of the exception “Parse.Failure” of normal streams) and “Some (r, s)” meaning “the result is r and the remaining stream is s”.

Syntax

The syntax of purely functional parsers, when loading “pa_fstream.cmo”, is the following:

        expression ::= fparser
                     | match-with-fparser
           fparser ::= "fparser" pos-opt "[" parser-cases "]"
                     | "fparser" pos-opt parser-case
match-with-fparser ::= "match" expression "with" fparser
      parser-cases ::= parser-cases parser-case
                     | <nothing>
       parser-case ::= "[:" stream-pattern ":]" pos-opt "->" expression
                     | "[:" ":]" pos-opt "->" expression
    stream-pattern ::= stream-patt-comp
                     | stream-patt-comp ";" stream-pattern
  stream-patt-comp ::= "`" pattern
                     | "`" pattern "when" expression
                     | pattern "=" expression
                     | pattern
                     | "when" expression
           pos-opt ::= pattern
                     | <nothing>

Notice that, unlike classical parsers, there is no difference, in a stream pattern, between the first stream pattern component and the other ones. In particular, there is no “question mark” syntax and expression optionnally ending those components. Moreover, the “lookahead” case is not necessary, we see further why. The syntaxes “pattern when” and “let..in” inside stream patterns we see in classical parsers are not implemented.

Streams

The functional parsers are functions taking as parameters functional streams, which are values of type “Fstream.t   a” for some type “a”. It is possible to build functional streams using the functions defined in the module “Fstream”:

Fstream.from

“Fstream.from f” returns a stream built from the function “f”. To create a new stream element, the function “f” is called with the current stream count, starting with zero. The user function “f” must return either “Some <value>” for a value or “None” to specify the end of the stream.

Fstream.of_list

Return a stream built from the list in the same order.

Fstream.of_string

Return a stream of the characters of the string parameter.

Fstream.of_channel

Return a stream of the characters read from the input channel parameter.

Semantics of parsers

Fparser

The purely functional parsers act like classical parsers, with a recursive descent algorithm, except that:

• If the first stream pattern component matches the beginning of the stream, there is no error if the following stream patterns components do not match: the control simply passes to the next parser case with the initial stream.
• If the semantic actions are of type “t”, the result of the parser is of type “option (t * Fstream.t)”, not just “t” like in classical parsers. If a stream pattern matches, the semantic action is evaluated, giving some result “e” and the result of the parser is “Some (e, strm)” where “strm” is the remaining stream.
• If no parser case matches, the result of the parser is “None”.

Error position

A difficulty, with purely functional parsers, is how to find the position of the syntax error, when the input is wrong. Since the system tries all parsers cases before returning “None”, and that the initial stream is not affected, it is not possible to directly find where the error happened. This is a problem for parsing using backtracking (here, it is limited backtracking, but the problem is the same).

The solution is to use the function “Fstream.count_unfrozen” applied to the initial stream. Like its name says, it returns the number of unfrozen elements of the stream, which is exactly the longest match found. If the input is a stream of characters, the return of this function is exactly the position in number of characters from the beginning of the stream.

However, it is not possible to know directly which rule failed and therefore it is not possible, as in classical parsers, to specify and get clear error messages. Future versions of purely functional parsers may propose solutions to resolve this problem.

Notice that, if using the “count_unfrozen” method, it is not possible to reuse that same stream to call another parser, and hope to get the right position of the error, if another error happens, since it may test less terminals than the first parser. Use a fresh stream in this case, if possible.