Sparse - Scin's Parsing Library

Sparse allows developers to easily create LR1 parsers and LR1 parsing tables.

Features:

• Complete Error Handling API - when parsing fails, you have the final say on where parsing stops
• Deferred Reductions - you create the nodes and Sparse builds the tree
• Full Slex integration - define your entire language as a set of DFA and CFG rules
• Optional Table Output - use Sparse to build your tables for use in other languages

Getting Started

1. Define the CFG of your language.

The CFG is defined by creating a file containing a list of productions. Variables are identifiers encased in angle brackets like <STATEMENT>, while terminals are encased in square-brackets like [L_COLON].

An example production includes: <IF_STATEMENT> : [IF] [L_PAREN] <EXPRESSION> [R_PAREN] <STATEMENT> <ELSE_IF_STATEMENTS> [ELSE] <STATEMENT>;.

An example CFG for a basic MDAS calculator is the following:

<S>: <PROGRAM>;
<PROGRAM>: <EXPRESSION> [EOF];
<PROGRAM>: [EOF];
<EXPRESSION>: <TERM_EXPRESSION>;
<TERM_EXPRESSION>: <FACTOR_EXPRESSION> [PLUS] <TERM_EXPRESSION>;
<TERM_EXPRESSION>: <FACTOR_EXPRESSION> [MINUS] <TERM_EXPRESSION>;
<TERM_EXPRESSION>: <FACTOR_EXPRESSION>;
<FACTOR_EXPRESSION>: <ENDPOINT> [STAR] <FACTOR_EXPRESSION>;
<FACTOR_EXPRESSION>: <ENDPOINT> [SLASH] <FACTOR_EXPRESSION>;
<FACTOR_EXPRESSION>: <ENDPOINT>;
<ENDPOINT>: [NUMBER];

2. Create your Slex lexer.

import { Slex } from "@scinorandex/slex";

// Make sure the identifiers here match with the terminals in your CFG.
enum TokenType {
  PLUS, MINUS, STAR, SLASH, NUMBER, EOF
}

type Metadata = {};

const lexerGenerator = new Slex<TokenType, Metadata>({
  EOF_TYPE: TokenType.EOF,
  isHigherPrecedence: ({ current, next }) => false,
});

lexerGenerator.addRule("plus", "$+", TokenType.PLUS);
lexerGenerator.addRule("minus", "$-", TokenType.MINUS);
lexerGenerator.addRule("star", "$*", TokenType.STAR);
lexerGenerator.addRule("forward_slash", "$/", TokenType.SLASH);
lexerGenerator.addRule("digit", "0|1|2|3|4|5|6|7|8|9");
lexerGenerator.addRule("float_number", "(${digit})+$.(${digit})+");
lexerGenerator.addRule("decimal_number", "(${digit})+");
lexerGenerator.addRule("number_literal", "${float_number}|${decimal_number}", TokenType.NUMBER);

const lexer = lexerGenerator.generate(`2.4 + 3.5 * 1 / 456.789`, () => ({}));

3. Define the node representation.

Sparse allows you to build the AST however you want, deferring to your functions when its time to make a reduction, giving you control over the representation.

type StringifiedNode = (StringifiedNode | string)[];

// It doesn't have to be a class. It just has to be a structure that all nodes
// in the AST adhere to. Classes allow this to be done easily through subclassing.
class Node {
  constructor(public readonly nodes: LR1StackSymbol<TokenType, {}, Node>[]) {}
  toObject(): StringifiedNode {
    return this.nodes.map((node) => (node.type === "token" 
      ? node.token.lexeme 
      : node.node.toObject()
    ));
  }
}

4. Building the productions and the parser.

Productions are built using the buildProductions() function, which can be passed into Sparse alongside toStringifiedTokenType, which converts a numerical TypeScript enum to the name of the terminal.

async function main() {
  const toStringifiedTokenType = (type: TokenType) => TokenType[type];
  const productions = buildProductions(await fs.readFile("./example/math/grammar.txt", "utf8"));
  const parserGenerator = Sparse.fromProductions<TokenType, Metadata, Node>({ productions, toStringifiedTokenType });
}

5. Define your reducer and begin parsing.

Finally, you can define the parser's reduction function and optionally define the recovery handling function.

const parser = parserGenerator.generate(lexer, {
  reducer: (_, { input, index }) => new Node(input),
});

console.log(parser.parse().result!.toObject());

Exporting and Loading the Parsing Table

You can export the parsing table with npx @scinorandex/sparse --input=<input> --output=<output> --export.

By default, LR(1) states are generated. You can generate LALR(1) states instead by passing the --lalr flag (or setting mode: "lalr1" in Sparse.fromProductions): the resulting table is never larger than the LR(1) one, but generation fails if the grammar is not LALR(1). Using LALR(1) yields a ~35% performance boost over LR(1) for the same grammar (tested on the LoLang example).

Afterwards, you can create a parser with pre-built states like the following:

async function main() {
  const toStringifiedTokenType = (type: TokenType) => TokenType[type];
  const productions = buildProductions(await fs.readFile("./example/math/grammar.txt", "utf8"));

  // Notice how the "new Sparse()" constructor is used here instead of "Sparse.fromProductions()"
  const states = buildStates(await fs.readFile("./example/math/table.txt", "utf8"));
  const parserGenerator = new Sparse<TokenType, Metadata, Node>({ productions, states, toStringifiedTokenType });
}

AI Disclaimer

This project was originally written without the use of AI tools, the core LR(1) table generator was written by hand as per the algorithms described in the Dragon Book. Every release prior to v0.1 contained no AI generated code.

OpenCode and Qwen 3.8 27B were to implement performance improvements on the original LR(1) table generator, implement LALR(1) support and partially implement grammar checking.