Separation of Parsing and Lexing



In many cases it is appropriate to separate parsing and lexing. A lexer breaks up the input stream into tokens like identifiers, parentheses, numbers, strings etc. Furthermore usually the lexer strips off whitespace. The parser handles the grammar of the language by using the tokens as primitives.

This approach has several advantages:

However many combinator libraries do not offer the possibility to split up the parsing task into a lexer and a parser. `Fmlib_parse` supports the splitting up of lexing and parsing with a lot of functionality.

How to write a lexer

A lexer analyzes the input stream consisting of characters in the following way:

    WS Token WS Token WS .... WS EOS

where WS is a possibly empty sequence of whitespace like blanks, tabs, newlines, comments etc. Token is a lexically correct token. EOS represents the end of the input stream.

Since the lexer has to succeed immediately after recognizing a syntactically correct token it is not a normal parser which succeeds only after having seen the end of input. Therefore a lexer is a partial parser. After having successfully recognized a token the lexer must be restartable to recognize the next token or to recognize the end of input.

The easiest way to write a lexer with the help of Fmlib_parse is to use Fmlib_parse.Character by doing the following steps:

Look into to see an example with a simple json parser on how it works.

How to write a parser

How to wire the lexer and the parser

The final parse looks like

module Parse_lex =

    let start: t =
        make Lexer.start Parser.token_parser

using Fmlib_parse.Parse_with_lexer to generate the final parser which scans a stream of characters breaks the input up into tokens by using the lexer and analyzes the grammar by using the token parser. See same example as above.