Separation of Parsing and Lexing

Up

Overview

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:

• For a real language the complexity of parsing a source file is separated into two managable sized parts.

• Handling whitespace in the parser makes the parser unnecessarily complex.

• As soon as a language has identifiers and keywords where the keywords look syntactically like identifiers, a parser handling characters directly requires a lot of backtracking which makes the parser inefficient. A lexer can recognize identifiers and after successful recognition of an identifier it checks by using an efficient lookup table if the identifier is a keyword.

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:

• Define a module Token and Token_plus of the following form:

    module Token = struct
        type t =
            T1 of ...
            T2 of ...
            ...
            End (* end of input *)
        ...
    end
  
    module Token_plus = struct
        type t = Position.range * Token
    end

• Write a module which satisfies the interface Fmlib_parse.Interfaces.LEXER.

    module Lexer =
    struct
        module C =
        struct
            include
                Character.Make
                    (Unit)              (* Trivial user state *)
                    (Token_plus)
                    (Fmlib_std.Void)    (* No semantic error possible *)
  
            let ws: _ t =
                ... (* combinator recognizing optional but arbitrarily long
                       whitespace *)
                Basic.skip_zero_or_more
                    (...)
  
            let tok: Token.t t =
                ... (* Combinator recognizing tokens. *)
  
  
            let final: Token_plus.t t =
                C.lexer ws eos tok
        end
  
        (* Public Functions *)
  
        include C.Parser
  
        let start: t =
            (* Recognize the first token *)
            C.make_partial Position.start () C.final
  
        let restart (lex: t): t =
            (* Recognize subsequent tokens *)
            assert (has_succeeded lex);
            assert (not (has_consumed_end lex));
  
            C.make_partial (position lex) () C.final
            |>
            transfer_lookahead lex
    end

• Note that the function Fmlib_parse.Character.Make.lexer has the following definition

    let lexer
            (ws: _ t) (eos: Token.t) (tok: Token.t t)
        : Token_plus.t
        =
        let* _ = ws
        in
        located (
            tok
            </>
            expect_end eos
        )

  It first strips off whitespace and then it expects either a token or the end of input. The token or the end of input is returned with the corresponding position information. This functionality is usually expected from a lexer. However you can write your own combinator if you want to have a different behaviour. When you write your own function, be careful where to put Fmlib_parse.Character.Make.expect_end.

Look into https://github.com/hbr/fmlib/blob/master/src/parse/test_json.ml to see an example with a simple json parser on how it works.

How to write a parser

• Write a module State where State.t represents the state of your parser. If you don't need a state, then use Unit.

• Write a module Semantic where Semantic.t it the type of semantic errors. If your parser issues only syntax errors, then use Fmlib_std.Void.

• Write a module Final where Final.t represents the structure you want to parse.

• Finally write the module representing the parser using Fmlib_parse.Token_parser which uses Token.t as the primitive tokens. Look into the same example as above.

      module Parser =
      struct
          module C =
          struct
              include
                  Token_parser.Make
                      (State)
                      (Token)
                      (Final)
                      (Semantic)
  
              ...
  
              let final: Final.t t =
                  ...
          end
  
          (* Public Functions *)
  
          include C.Parser
  
          let token_parser: t =
              make State.start final
      end
  

How to wire the lexer and the parser

The final parse looks like

    module Parse_lex =
    struct
        include
            Parse_with_lexer
                (State)
                (Token)
                (Final)
                (Semantic)
                (Lexer)
                (Parser)

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

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.

Up