DOCSEARCHbyAlgolia
Submit Docs

Lezer Parser Generator

repository·main·Indexed 41 days ago

https://github.com/lezer-parser/generator

An LR(1)/LALR parser generator for the Lezer parsing library that transforms grammar definitions into functional parser code. It provides a command-line tool, a programmatic JavaScript API, and a Rollup plugin to build grammars from .grammar files. Version 1.8.0 supports pseudo-LALR with opt-in GLR support and features for resolving token conflicts via precedence and groups.

Tokens
6K
Snippets
13
Records
29
Agent score
51%

What's inside Lezer Generator

  1. Overview of @lezer/generator

    main

    @lezer/generator is an LR(1) parser generator (specifically pseudo-LALR, with opt-in GLR support) designed to produce grammars for the Lezer parser. It provides two primary ways to use it:

    1. Command-line tool: lezer-generator for building grammars from files.
    2. Programming interface: An API for programmatic grammar generation.

    The tool accepts a specific grammar format. For real-world examples, you can examine lezer-javascript or the test/cases/ directory in the source.

  3. Use the @lezer/generator Rollup plugin

    main

    You can integrate the generator into your build pipeline using the @lezer/generator/rollup plugin. This plugin automatically transforms files with the .grammar extension or .grammar.terms extension (which refers to terms produced by a .grammar file) during the Rollup build process.

    You can configure the name of the exported parser by passing the exportName option to the plugin.

    import {lezer} from "@lezer/generator/rollup"

export default {
  input: "./in.js",
  output: {file: "out.js", format: "cjs"},
  plugins: [lezer({exportName: 'MyParser'})}]
}

  4. Use @lezer/generator via the command-line interface

    main
    The parser generator is primarily intended to be used through its command-line interface (CLI) to build grammars. For detailed instructions on building a grammar using the CLI, refer to the official guide.

  5. Use Expression types to navigate grammar expressions

    main

    All grammar expressions inherit from the Expression class. You can traverse the expression tree using the .walk(f) method, which accepts a visitor function f: (expr: Expression) => Expression. This allows you to transform or inspect the expression tree.

    Common expression types include:

    • ChoiceExpression: Represents alternatives (e.g., A | B).
    • SequenceExpression: Represents a sequence of elements (e.g., A B).
    • RepeatExpression: Represents repetitions (?, *, or +).
    • NameExpression: A reference to a rule or token by name.
    • LiteralExpression: A fixed string literal.
    • SetExpression: A character set (e.g., [a-z]).
    • AnyExpression: Matches any character (_).
    • CharClass: A predefined character class (e.g., @digit).

  6. Configure rule properties in Lezer

    main

    When defining rules in a Lezer grammar, you can use various properties (prefixed with @) to control node behavior. Note that some properties are restricted to specific rule types:

    • @dialect: Specifies a dialect. Only allowed on token rules. Must hold a plain string value.
    • @dynamicPrecedence: Sets an integer between -10 and 10. Only allowed on nonterminals.
    • @inline: Marks a rule as inline. Only allowed on nonterminals. Inline nodes cannot have other properties, dynamic precedence, or a dialect.
    • @isGroup: Assigns a rule to a group. Only allowed on nonterminals.
    • @export: Specifies an exported name for the node.
    • @name: Sets the node name. Node names cannot contain spaces.

    If you attempt to use a property in an invalid context (e.g., @dialect on a non-token rule), the generator will raise an error.

  7. Understand the Grammar AST structure

    main

    The @lezer/generator package uses an Abstract Syntax Tree (AST) to represent grammar declarations. The root of a grammar is represented by a GrammarDeclaration, which contains rules, tokens, context, and precedence information.

    Key components of the grammar AST include:

    • GrammarDeclaration: The top-level container for all grammar elements.
    • RuleDeclaration: Represents a grammar rule, including its identifier, parameters, properties, and the expression it expands to.
    • TokenDeclaration: Defines tokens, including their precedences, conflicts, and associated rules.
    • Expression: The base class for all grammar expressions (e.g., sequences, choices, repetitions).

  8. Resolve token conflicts using precedence and groups

    main

    Lezer handles overlapping tokens (tokens that could match the same input) using two mechanisms:

    1. Token Precedence

    You can specify explicit precedence relations between tokens. If a precedence is defined, the generator uses it to resolve conflicts. If you define a cyclic relationship, the generator will raise an error.

    2. Token Groups

    Token groups allow conflicting tokens to exist in the same grammar if they do not occur in the same parsing context (i.e., they are not used in the same states).

    • Tokens are assigned a 16-bit bitmask representing the groups they belong to.
    • Each state is assigned zero or one token group.
    • If a state uses tokens that conflict, the generator will raise an error.
    • If tokens conflict but are used in different states, they are assigned to a TokenGroup to allow them to coexist without ambiguity.

  9. Configure BuildOptions for @lezer/generator

    main

    When using the generator to build a parser, you can provide a BuildOptions object to customize the output. Key options include:

    • fileName: The name of the grammar file.
    • warn: A callback function for warnings (defaults to console.warn).
    • includeNames: If true, includes term names in the output file.
    • moduleStyle: The module system for the output file. Options are "cjs" (CommonJS) or "es" (ES2015 modules). Defaults to "es".
    • typeScript: If true, outputs TypeScript code instead of plain JavaScript.
    • exportName: The name of the export holding the parser (defaults to "parser").
    • externalTokenizer: A function to provide placeholders for external tokenizers.
    • externalPropSource: A function to resolve external property sources.
    • externalSpecializer: A function to provide placeholders for external specializers.
    • externalProp: A function to initialize external properties.
    • contextTracker: A function or ContextTracker instance to use in the built parser.
    const options: BuildOptions = {
  moduleStyle: 'es',
  typeScript: true,
  exportName: 'myParser',
  includeNames: true
};

  10. Reference predefined CharClasses

    main

    The generator provides a set of predefined character classes via the CharClasses object. These can be used to build SetExpression or CharClass nodes.

    export const CharClasses: {[name: string]: [number, number][]} = {
  asciiLetter: [[65, 91], [97, 123]],
  asciiLowercase: [[97, 123]],
  asciiUppercase: [[65, 91]],
  digit: [[48, 58]],
  whitespace: [[9, 14], [32, 33], [133, 134], [160, 161], [5760, 5761], [8192, 8023], [8232, 8234], [8239, 8240], [8287, 8288], [12288, 12289]],
  eof: [[0xffff, 0xffff]]
}

  11. Reference Grammar AST Node Types

    main

    The following classes define the structure of the grammar AST. Most nodes include a start property indicating their position in the source.

    export class Node {
  constructor(readonly start: number) {}
}

export class GrammarDeclaration extends Node {
  constructor(start: number,
              readonly rules: readonly RuleDeclaration[],
              readonly topRules: readonly RuleDeclaration[],
              readonly tokens: TokenDeclaration | null,
              readonly localTokens: readonly LocalTokenDeclaration[],
              readonly context: ContextDeclaration | null,
              readonly externalTokens: readonly ExternalTokenDeclaration[],
              readonly externalSpecializers: readonly ExternalSpecializeDeclaration[],
              readonly externalPropSources: readonly ExternalPropSourceDeclaration[],
              readonly precedences: PrecDeclaration | null,
              readonly mainSkip: Expression | null,
              readonly scopedSkip: readonly { 
                expr: Expression,
                topRules: readonly RuleDeclaration[],
                rules: readonly RuleDeclaration[]
              }[],
              readonly dialects: readonly Identifier[],
              readonly externalProps: readonly ExternalPropDeclaration[],
              readonly autoDelim: boolean)
}

export class RuleDeclaration extends Node {
  constructor(start: number,
              readonly id: Identifier,
              readonly props: readonly Prop[],
              readonly params: readonly Identifier[],
              readonly expr: Expression)
}

export class TokenDeclaration extends Node {
  constructor(start: number,
              readonly precedences: readonly TokenPrecDeclaration[],
              readonly conflicts: readonly TokenConflictDeclaration[],
              readonly rules: readonly RuleDeclaration[],
              readonly literals: readonly LiteralDeclaration[])
}

export class Identifier extends Node {
  constructor(start: number, readonly name: string)
}

export class Expression extends Node {
  walk(f: (expr: Expression) => Expression): Expression
  eq(_other: Expression): boolean
  prec!: number
}

export class Prop extends Node {
  constructor(start: number, readonly at: boolean, readonly name: string, readonly value: readonly PropPart[])
}

export class PropPart extends Node {
  constructor(start: number, readonly value: string | null, readonly name: string | null)
}

  12. Troubleshoot rule complexity warnings

    main

    The Lezer generator may issue warnings if a rule is generating an excessive number of choices.

    Warning: Rule [name] is generating a lot ([count]) of choices.

    Cause: This typically happens when a rule uses a large number of ? or | operators, or is a ChoiceExpression with many branches.

    Solution: Consider splitting the rule into multiple smaller rules or reducing the number of operators used in a single expression to improve parser performance and maintainability.