Skip to content
Hyperlark

Lexers

The lexer splits the input into tokens, one per terminal match. LALR’s default lexer is the contextual one, Earley’s the dynamic one; Choosing a lexer describes each.

The samples on this page use this grammar as GRAMMAR:

start:  NUMBER (OP NUMBER)*
OP:     "+" | "-" | "*" | "/"      // string alternatives
NUMBER: /[0-9]+/                    // a regex
%ignore " "                        // drop spaces between tokens

Ignoring text

Section titled “Ignoring text”

%ignore names a terminal, or an inline pattern. All occurrences of the terminal will be ignored, and won’t be part of the parse. It is especially important for LALR(1), because adding whitespace (or comments) explicitly in the grammar harms its predictive abilities. To collect ignored tokens such as comments, see Lexer callbacks.

Seeing the tokens

Section titled “Seeing the tokens”

lex only lexes (and postlexes) the text, without parsing it. It always runs the basic lexer, which ignores the parser state, so under the contextual lexer a token can differ from the one the parser sees. With dont_ignore=True in Python, or true as the second argument in Rust and TypeScript, it returns all tokens, even those marked for %ignore.

import hyperlark as lark
p = lark.Lark(GRAMMAR, parser="lalr")
for t in p.lex("1 + 22"):
    print(t.type, repr(t.value))   # NUMBER '1'  OP '+'  NUMBER '22'

To see the tokens in C, drive an interactive parser with lark_interactive_feed_next, which pulls one token at a time.

Lexer callbacks

Section titled “Lexer callbacks”

lexer_callbacks can be used to interface with the lexer as it generates tokens (Python and Rust), to alter or collect them. It accepts a dictionary of the form {TOKEN_TYPE: callback}, where the callback is of type f(Token) -> Token. The callback also receives ignored tokens; its return value for them is discarded. The samples add a comment terminal to the grammar:

start:   NUMBER (OP NUMBER)*
OP:      "+" | "-" | "*" | "/"
NUMBER:  /[0-9]+/
COMMENT: /#[^\n]*/
%ignore " "
%ignore COMMENT
comments = []
p = lark.Lark(GRAMMAR, parser="lalr", lexer_callbacks={"COMMENT": comments.append})
p.parse("1 + 22  # a note")
comments   # [Token('COMMENT', '# a note')]

It only works with the basic and contextual lexers (a custom lexer gets them only through a BasicLexer it wraps). The dynamic lexers, Earley’s default, refuse callbacks with GrammarError; under Earley, pass lexer="basic". TypeScript has no lexer callbacks; lex(text, true) returns the ignored tokens, so pick the comments out of that.

Terminal priority

Section titled “Terminal priority”

Terminals can be assigned a priority to influence lexing, as in IF.2: "if". Priorities are signed integers with a default value of 0.

When using a lexer (basic or contextual), it is your responsibility to make sure the terminals don’t collide, or that if they do, they are matched in the desired order:

  1. Highest priority first.
  2. Length of match (for regexps, the longest theoretical match is used).
  3. Length of the literal / pattern definition.
  4. Name.

Keywords are the exception to this order: at equal priority a string literal beats a regex that matches the same text, so keywords need no priority.

NAME: /[a-z]+/
IF:   "if"

if lexes as IF and iffy as NAME. Under the contextual lexer a keyword is tried only where the parser state accepts it, so elsewhere if lexes as NAME.

Consider setting a priority only as a last resort. BOOL: /true|false/ loses to NAME: /[a-z]+/ by rule 2. BOOL.2 wins, but then trueish lexes as BOOL followed by the NAME ish. To get true as a keyword and trueish as a name, give each keyword its own string terminal (TRUE: "true"). BOOL: "true" | "false" does not help: a terminal with alternatives counts as a regex, so NAME still wins against it.

When using Earley’s dynamic lexing, terminal priorities are used to prefer certain lexings and resolve ambiguity.

Keeping punctuation in the tree

Section titled “Keeping punctuation in the tree”

The tree builder filters out punctuation by default: unnamed literals (like "+") and terminals whose name starts with an underscore (like _NEWLINE); see Shaping the tree. keep_all_tokens prevents that removal in every rule, and a rule prefixed with ! (!start: ...) keeps all its terminals. Named terminals such as OP are kept either way.

p = lark.Lark(GRAMMAR, parser="lalr", keep_all_tokens=True)

In C the flag applies to lark_from_source; lark_from_json uses the setting the grammar was saved with.

Choosing a lexer

Section titled “Choosing a lexer”

lexer="auto", the default, chooses based on the parser. Most grammars never change it:

Parserauto resolves toAlso available
LALRcontextualbasic
Earleydynamic (basic with a postlex)basic, dynamic_complete
  • contextual (LALR only) uses the parser’s lookahead prediction to narrow its choice of terminals: at each point it matches only the terminals that are legal in that parser state, resolving common terminal collisions.
  • basic ignores the parser state and works with both parsers. Under Earley it is faster, but tokenizes without Earley’s ambiguity resolution, so choose it only if you know why. Under LALR, choose it when lex must return the parser’s tokens.
  • dynamic (Earley only) has no fixed tokenization: at each position it matches every terminal the parse expects, each regex once, taking the regex’s own match.
  • dynamic_complete also tries the shorter prefixes of that match, which start: A B with A: /a+/ and B: "a" needs to parse aaa. It can be much slower, especially for open-ended terminals such as /.*/.

To override the choice:

p = lark.Lark(GRAMMAR, parser="earley", lexer="dynamic_complete")

C has no lexer option: lark_from_source uses the contextual lexer, and lark_from_json the lexer the grammar was saved with. The feature matrix has the per-target table.

Indentation: postlex and Indenter

Section titled “Indentation: postlex and Indenter”

A postlex post-processes the token stream between the lexer and the parser. The built-in Indenter is a postlex that “injects” indent/dedent tokens based on indentation, which no regex can produce. Inside brackets, newlines are dropped and the indentation is ignored, so no indent/dedent tokens get generated. Your grammar must:

  1. Include the next line’s leading whitespace in the newline terminal, as _NEWLINE: /(\r?\n[\t ]*)+/ does. The indenter measures it there.
  2. %declare the indent and dedent terminals, declaring them without defining them, since the indenter produces them.
  3. Name the newline, indent and dedent terminals as the indenter is configured. A missing one is an error; a missing bracket name is ignored.

The samples in this section use this grammar as GRAMMAR:

?start: _NEWLINE* tree
tree: NAME _NEWLINE [_INDENT tree+ _DEDENT]
NAME: /\w+/
_NEWLINE: /(\r?\n[\t ]*)+/
%declare _INDENT _DEDENT
%import common.WS_INLINE
%ignore WS_INLINE
from hyperlark import Lark, PythonIndenter
p = Lark(GRAMMAR, parser="lalr", postlex=PythonIndenter())
p.parse("root\n    branch\n        leaf\n")

All three samples use PythonIndenter’s values, spelled out in the Rust sample. To change them in Python, inherit from Indenter and implement NL_type, OPEN_PAREN_types, CLOSE_PAREN_types, INDENT_type, DEDENT_type and tab_len. In TypeScript the "python" preset is the only postlex and cannot be changed. C has no postlex.

For a postlex of your own in Python, subclass PostLex, implement process(stream) as a generator over the incoming tokens, and set always_accept to the terminals the lexer must accept in every parser state. In Rust, implement the Postlex trait: session(names) returns the stream for one pass over the input, and always_accept() lists the same terminals.

Yield each token before pulling the next one. A postlex that reads ahead runs ahead of the parser, so under the contextual lexer a terminal that only the parser state disambiguates can fail to match.

The dynamic lexers refuse a postlex: requesting one raises ConfigurationError, and under auto, Earley with a postlex uses basic.

The indentation example is a complete Python program.

Custom lexers

Section titled “Custom lexers”

You can use a custom lexer to tokenize text when the built-in lexers are too slow, or not flexible enough, or in Python to tokenize a stream of objects. It works under LALR and Earley, in Python, Rust and TypeScript.

In Python and TypeScript you pass a lexer class. It is constructed once, with the parser, and its lex runs once per parse; both samples wrap the built-in BasicLexer. In Rust you implement TokenSource, and pass one over each input to parse_custom in place of parse. parse_custom also takes an optional start rule and on_error callback; the built-in lexer as a TokenSource is BasicTokenSource::new(p.basic_lexer()?, text).

Each token names a grammar terminal and carries its text: Token("NUMBER", "42") in Python, { type: "NUMBER", value: "42" } in TypeScript, CustomToken::new("NUMBER", "42") or the full struct in Rust. A type the grammar does not know fails the parse with UnexpectedToken.

Your lexer can read the parser state before each token. Under LALR it is the state number: position on the parser_state (parserState) argument in Python and TypeScript, state in Rust. Under Earley it is the terminals the parser expects next: a set of Terminal objects in Python (compare t.name), a set of names in TypeScript, and expects, a slice of terminal ids, in Rust. That set can be incomplete: before OP in start: NUMBER (OP NUMBER)* it is empty. In Python and TypeScript, parser_state is one object the parser updates in place, so read position or the set before each token rather than copying it once at the top of lex.

from hyperlark import Lark
from hyperlark.lexer import BasicLexer, Lexer


class MyLexer(Lexer):
    def __init__(self, lexer_conf):
        self.lexer = BasicLexer(lexer_conf)          # reuse the built-in lexer


    def lex(self, lexer_state, parser_state):
        for tok in self.lexer.lex(lexer_state, parser_state):
            yield tok                                # change or drop tokens here


    # 2 selects lex(lexer_state, parser_state). Omit it and define
    # lex(self, text) when you do not need the parser state.
    __future_interface__ = 2


p = Lark(GRAMMAR, parser="lalr", lexer=MyLexer)

A custom lexer cannot be used with interactive parsing: parse_interactive, OwnedInteractiveParser::new and parseInteractive raise an error.