DOCSEARCHbyAlgolia
Submit Docs

@lezer/lr Incremental Parser

repository·main·Indexed 20 days ago

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

A high-performance, memory-efficient incremental GLR (Generalized LR) parser library designed for syntax tree maintenance in editors. It provides the runtime engine for parsers generated by @lezer/generator, featuring a lightweight syntax tree and support for real-time edits and syntax errors. Key components include the LRParser for execution, ParserConfig for settings, and a tokenizer system utilizing InputStream, ExternalTokenizer, and ContextTracker for stateful parsing.

Tokens
2.5K
Snippets
7
Records
15
Agent score
72%

What's inside @lezer/lr

  1. Overview of @lezer/lr

    main

    Lezer is an incremental GLR (Generalized LR) parser designed for use in editors or similar systems. It is optimized for speed and compactness, making it suitable for maintaining a current program representation during real-time edits and in the presence of syntax errors.

    Key characteristics:

    • Incremental Parsing: Efficiently updates the syntax tree as the input changes.
    • Compactness: Prioritizes small parser table files and a lightweight syntax tree. Syntax tree nodes are minimal 'blobs' containing only a start position, end position, tag, and a set of child nodes.
    • Runtime Library: This package (@lezer/lr) provides the runtime engine that executes parsers generated by @lezer/generator.

  2. Core Parsing Components in @lezer/lr

    main

    The parsing engine is built around several key abstractions:

    • @LRParser: The main parser instance used to perform the parsing process.
    • @ParserConfig: Configuration object used to initialize the parser with specific settings and parse tables.
    • @Stack: Represents the parsing stack used during the GLR process to track state and symbols.

  3. Tokenizer Interfaces in @lezer/lr

    main

    To provide input to the parser, @lezer/lr uses a tokenizer system consisting of:

    • @InputStream: An abstraction for reading the raw input stream.
    • @ExternalTokenizer: An interface for integrating external tokenization logic into the parsing process.
    • @ContextTracker: A mechanism for tracking context during the parsing phase, which can influence how tokens are identified.

  4. Understand the limitations of lookbehind in InputStream

    main

    When using InputStream.peek(offset), be aware of the following constraints:

    1. Incremental Parsing: Looking forward (positive offset) can create dependencies on distant content, potentially reducing the effectiveness of incremental parsing.
    2. Lookbehind: The library does not track lookbehind. Looking backward (negative offset) more than 25 code units may cause invalid reparses.

  5. Use ContextTracker to manage stateful context

    main

    A ContextTracker<T> is used to track stateful context (like indentation in Python or parent elements in XML) required by external tokenizers. You define these in a grammar file using the @context syntax.

    When implementing a ContextTracker, you provide:

    • start: The initial value of the context.
    • shift(context, term, stack, input): Updates context during a shift action.
    • reduce(context, term, stack, input): Updates context during a reduce action.
    • reuse(context, node, stack, input): Updates context when a node is reused from a tree fragment.
    • hash(context): Reduces the context to a number for efficient storage and comparison (required for strict contexts).
    • strict: (Optional) Defaults to true. If false, nodes can be reused even if they weren't created in the same context.

  6. Configure an LRParser with ParserConfig

    main

    Use the configure(config) method on an LRParser instance to create a new parser with modified settings. This is useful for creating specialized versions of a parser without re-generating the entire grammar.

    Supported configuration options include:

    • props: Add new node property sources to the nodeSet.
    • top: Specify a different @top rule name to parse from.
    • dialect: A space-separated string of dialects to enable.
    • tokenizers: Replace existing ExternalTokenizer instances with new ones.
    • specializers: Replace existing external specializers.
    • contextTracker: Replace the ContextTracker used for stateful context.
    • strict: If true, the parser will throw a SyntaxError on mismatches instead of attempting error recovery.
    • wrap: Add a ParseWrapper to extend the parsing logic (e.g., for mixed-language parsing).
    • bufferLength: Set the maximum length of the generated TreeBuffers (defaults to 1024).
    const specializedParser = baseParser.configure({
  top: 'myCustomTopRule',
  strict: true,
  bufferLength: 2048
});

  7. Create a parse instance with LRParser.createParse()

    main

    To perform a parse, call createParse(input, fragments, ranges) on an LRParser instance. This returns a PartialParse object which implements the incremental parsing interface.

    Parameters:

    • input: The source input.
    • fragments: An array of TreeFragment objects used for incremental parsing.
    • ranges: An array of {from: number, to: number} defining the input segments.
    const parse = parser.createParse(input, fragments, ranges);
// Use the returned PartialParse to advance the parse

  8. Use LRParser for parsing

    main

    The LRParser class is the primary entrypoint for performing LR parsing. It is configured using a ParserConfig object. To use it, you typically instantiate or call methods on an LRParser instance provided by the library.

    import { LRParser, ParserConfig } from '@lezer/lr';

// Usage depends on the specific implementation of LRParser
// provided by the library's parse module.

  9. Handle tokens with InputStream, ExternalTokenizer, and LocalTokenGroup

    main

    The @lezer/lr package provides several types for managing the token stream during parsing:

    • InputStream: Represents the source of input data being consumed by the parser.
    • ExternalTokenizer: An interface or class for providing tokens from an external source.
    • LocalTokenGroup: A mechanism for grouping tokens locally within the parser context.

  10. Use InputStream to interact with input streams in tokenizers

    main

    The InputStream class provides an interface for tokenizers to interact with the input as a stream of characters. It manages lookahead and abstracts away the complexity of non-contiguous input ranges.

    Key Methods:

    • next: A property representing the character code of the next code unit, or -1 at the end of the stream.
    • peek(offset: number): Look at a code unit near the current position. .peek(0) is equivalent to .next, and .peek(-1) looks at the previous character.
      • Warning: Looking backward more than 25 code units may cause invalid reparses because the library does not track lookbehind.
    • advance(n?: number): Moves the stream forward by n code units (defaulting to 1) and returns the new value of next.
    • acceptToken(token: number, endOffset?: number): Accepts a token. By default, the token ends at the current stream position. You can provide a relative endOffset to change this.
    • acceptTokenTo(token: number, endPos: number): Accepts a token ending at a specific absolute position.
    • pos: The current position of the stream.
    import { InputStream } from "@lezer/lr";

// Inside a tokenizer function:
function myTokenizer(input: InputStream, stack: any) {
  if (input.next === 65) { // 'A'
    input.acceptToken(TOKEN_ID_A);
    input.advance();
  }
}

  11. Create an ExternalTokenizer for custom grammar tokens

    main

    In @lezer/lr grammars, tokens declarations should resolve to an instance of ExternalTokenizer. This allows you to implement custom scanning logic that is integrated into the parser's precedence and fallback mechanisms.

    Constructor: new ExternalTokenizer(token: (input: InputStream, stack: Stack) => void, options?: ExternalOptions)

    Options (ExternalOptions):

    • contextual?: boolean: If true, the tokenizer depends on the current parse stack, preventing its result from being cached between parser actions at the same positions.
    • fallback?: boolean: If true, the tokenizer is allowed to run even if a previous tokenizer returned a token that didn't match any current state's actions.
    • extend?: boolean: If true, tokenizing will not stop after this tokenizer has produced a token (it allows multiple tokens to be produced/processed).
    import { ExternalTokenizer } from "@lezer/lr";

const myCustomTokenizer = new ExternalTokenizer((input, stack) => {
  // Custom scanning logic using input.next, input.peek, and input.acceptToken
  if (input.next === 42) { // '*'
    input.acceptToken(MY_TOKEN_STAR);
    input.advance();
  }
}, {
  fallback: true
});

  12. Get term names with getName()

    main

    The getName(term) method returns the string name associated with a given term ID.

    Note: This only works for all terms if the parser was generated with the --names option. Otherwise, it only returns names for tagged terms; for others, it returns the term ID or the node type name.

    const name = parser.getName(someTermId);