LEMON.JS - LALR(1) Parser Generator for JavaScript

SQLite's parser generator, taught to emit JavaScript. Reads all 103 TPC-DS queries three to four times faster than the fashionable alternative, from a grammar a third the size, and ships in 7 KB gzipped with a lexer thrown in. Written in 2017, benchmarked in 2026, still winning.

Lemon.JS is an LALR(1) parser generator for JavaScript based on Lemon parser generator for C included in SQLite package distribution.

Looking for a lexer to go with it? FLEX.JS 2, which is FLEX itself with a JavaScript back end.

Parser Code Base

Files lemon.c, lempar.c, lemon.html are extracted from SQLite v3.17.0. Original parser generator code is slightly fixed to produce JavaScript compatible statements. Parser template translated from C to JavaScript. Source comments mostly not touched to keep it easy diff against original file.

Both original C version and patched JS version are included for side by side comparison for reference.

Installation

From npm, which carries a prebuilt generator for macOS, Linux and Windows on both x86_64 and arm64:

npm install --save-dev @sormy/lemon-js
npx lemon-js grammar.y

The package is @sormy/lemon-js and the command it installs is lemon-js.

Or from source, which is the way on any platform the package does not carry:

cc -o lemon-js -O2 lemon-js.c
./lemon-js grammar.y

Built this way the generator looks for lempar.js beside its own executable, so keep the two together, or name the template with -T.

Usage

lemon-js <filename>.y

Writes <filename>.js, a <filename>.d.ts declaration, and a <filename>.out report of the grammar and its states. -q drops the report.

• -q - do not write the report file.
• -l - leave out the // line ... comments pointing back at the grammar.
• -T<file> - read another parser template. Installed from npm this already points at the bundled lempar.js, so it is only needed for a template of your own.
• -s - print statistics about the parser tables.
• -g - print the grammar without actions.
• -b - report only the basis of each state, rather than every configuration.
• -c - do not compress the action table.
• -p - show the conflicts that precedence rules resolved.
• -r - do not sort or renumber the states.
• -x - print the version.

A grammar the generator will not accept is reported and exits non-zero.

See lemon.html, included here, or https://sqlite.org/lemon.html for more details.

Special Directives

• %name - Set parser class name (default is "Parse")
• %include - Include code in the beginning of file (useful for imports)
• %code - Include code in the end of file (useful for exports or main code)
• %token_destructor - Define code which will be executed on token destruction.
• %default_destructor - Destructor for the non-terminals that have none of their own.
• %token_prefix - Define token name prefix.
• %syntax_error - Define custom error handler for syntax errors.
• %parse_accept - Code to run when the parser accepts its input, meaning every token was processed without error.
• %parse_failure - Code to run once error recovery has failed and the parse cannot go on.
• %stack_overflow - Define handler for stack overflow.
• %extra_argument - Declare a name visible in every action, given to the constructor: %extra_argument { ctx } in the grammar, new Parser(ctx) in the code.
• %token_type - Type of the value a token carries, used in the generated declaration: %token_type { number } makes parse take a number.
• %default_type - NOT SUPPORTED, nothing to declare while the output is JavaScript
• %stack_size - Depth of the parser stack, 100 by default.
• %start_symbol - Symbol the grammar starts at, the left side of the first rule by default.
• %left - Set left associative tokens.
• %right - Set right associative tokens.
• %nonassoc - Set non associative tokens.
• %destructor - Destructor for one non-terminal symbol, as %token_destructor is for terminals.
• %type - NOT SUPPORTED, nothing to declare while the output is JavaScript
• %fallback - Give tokens an alternative meaning, tried when the original would be a syntax error.
• %wildcard - Name the token that matches any input token.
• %token_class - Define a class of tokens usable as one symbol in rules, %token_class number INTEGER|FLOAT.

Notes:

• a regular expression holding /*, such as /\/*/, ends a %code or %include section early: the generator reads /* as the start of a comment and swallows the rest of the file. It says so and stops rather than producing anything, and writing the star as a character class, /\/[*]/, avoids it.
• the best place to put something like module.exports = ParserName; or export default ParserName; is in %code section.

Performance

Measured with npm run bench, best of 30 rounds, on a MacBook Pro (M1 Max), macOS 26.6.2, Node 24.20.0. Peak memory is over three parses, in a process running one parser and nothing else. Every parser has to reach the same answer, or the run reports the grammars have drifted.

Parsing alone, the input scanned once beforehand into the shape each expects.

Arithmetic, nested seven deep, 242 KB and 129,000 tokens:

| parser | time | tokens/s | peak memory | | ------------------ | ------- | -------- | ----------- | | lemon-js | 5.6 ms | 23.0 M | 127 MB | | chevrotain 13.2.0 | 8.4 ms | 15.3 M | 167 MB | | jison 0.4.18 | 36.1 ms | 3.6 M | 166 MB |

SELECT statements, six levels of precedence, 421 KB and 125,000 tokens:

| parser | time | tokens/s | peak memory | | ------------------ | ------- | -------- | ----------- | | lemon-js | 5.2 ms | 24.1 M | 162 MB | | chevrotain 13.2.0 | 13.1 ms | 9.5 M | 171 MB | | jison 0.4.18 | 36.7 ms | 3.4 M | 171 MB |

The 103 TPC-DS queries, real analytical SQL with common table expressions, correlated subqueries and window functions, 148 KB and 24,000 tokens:

| parser | time | tokens/s | peak memory | | ------------------ | ------- | -------- | ----------- | | lemon-js | 1.5 ms | 15.7 M | 90 MB | | chevrotain 13.2.0 | 5.1 ms | 4.8 M | 102 MB |

Read as text instead, each with a scanner of its own. FLEX.JS 2.0.0 generates those from a grammar file, the same way this generates parsers, with -Cf: a fifth quicker than the default tables and several times the size. -Cfe is the middle of those - a full table indexed by equivalence class, as quick as -Cf at a third of the size.

The arithmetic:

| parser | time | tokens/s | peak memory | | ------------------- | ------- | -------- | ----------- | | lemon-js + flex-js | 9.4 ms | 13.7 M | 100 MB | | chevrotain 13.2.0 | 20.5 ms | 6.3 M | 179 MB |

The TPC-DS queries, on every axis:

| parser | time | tokens/s | peak memory | raw | minified | gzipped | dependencies | | ------ | ---- | -------- | ----------- | --- | -------- | ------- | ------------ | | lemon-js + flex-js, -Cf | 2.4 ms | 10.3 M | ~85 MB | 450 KB | 261 KB | 13.4 KB | none | | lemon-js + flex-js, -Cfe | 2.4 ms | 10.0 M | ~87 MB | 182 KB | 81 KB | 12.0 KB | none | | lemon-js + flex-js, default tables | 3.0 ms | 7.9 M | ~87 MB | 93 KB | 34 KB | 10.0 KB | none | | chevrotain 13.2.0 | 10.3 ms | 2.4 M | 108 MB | 255 KB | 120 KB | 32.5 KB | 5 packages |

Both sides are the whole thing: a generated parser and scanner against chevrotain's runtime and its grammar. Minified, the full table costs more; gzipped, rows of small integers compress away.

chevrotain is bimodal here: about half the runs settle around 10 ms and the rest around 21 ms, for every one of the 30 rounds. The figure above is the quicker mode. Peak memory moves about 15 MB between runs whatever the parser, since it depends on when the collector wakes.

The generated SQL:

| parser | time | tokens/s | peak memory | | ------------------- | --------- | -------- | ----------- | | lemon-js + flex-js | 10.3 ms | 12.1 M | 106 MB | | peggy 5.0.6 | 31.4 ms | 4.0 M | 113 MB | | chevrotain 13.2.0 | 35.0 ms | 3.6 M | 185 MB | | lezer 1.8.0 | 53.0 ms | 2.3 M | 177 MB | | jison 0.4.18 | 99.5 ms | 1.3 M | 227 MB | | nearley 2.20.1 | 197.6 ms | 0.6 M | 141 MB | | ohm-js 17.4.0 | 1651.8 ms | 0.1 M | 2089 MB |

Only chevrotain is measured on TPC-DS: writing that grammar twice was work enough. Both parse all 103 queries and agree on ten counts taken while parsing, down to the sum of every numeric literal.

The two grammars for it, for the same language:

| | lemon-js | chevrotain | | ------------------------------ | -------- | ---------- | | lines | 160 | 498 | | precedence declared | 8 lines | a rule per level | | numbered DSL calls | none | 62 | | hand-written lookahead | none | 3 | | token order mattering | no | IN hid INTERVAL and INTERSECT | | tokens needing distinct names | no | <> and != |

Reading the tables:

• The gap against chevrotain widens with precedence. It walks a rule per level to reach a name; a table asks one question whatever the grammar.
• Jison is LALR too, so the algorithm is not the difference. It keeps a location stack and a line, column and length for every token, read or not. Lemon.JS keeps none unasked, which is what the figures compare. A grammar that wants them is not stopped: the token value is yours, so the scanner puts the line in it with %option yylineno and a rule propagates where a production began.
• Lezer has no actions: a parse builds a syntax tree and the counting is a walk over it, timed with it. It is built for reparsing while a document is edited.
• Ohm memoises every rule at every position, near 5 MB per KB read.
• Nearley is an Earley parser and takes grammars the rest refuse.
• Chevrotain does not always run at the same speed. Over nine runs of the whole benchmark its best-of-30 on the TPC-DS text landed near 10.3 ms four times and near 20.8 ms the other five, and on the generated SQL near 35 ms four times and near 80 ms five. A whole process is slow or is not, so every figure here is its fast one, which is the one that favours it. The pairing moves by a twentieth of a millisecond on the same text, and by half a millisecond when the scanner carries the compressed tables, which do more work per byte.
• Read the arithmetic from text as close rather than ordered.
• Peggy, lezer, ohm and nearley cannot be handed tokens, so they appear only where the input is text.
• The scanning is not what wins it. Asked for the same tokens as objects, a generated flex-js scanner leads chevrotain's lexer by a tenth to a quarter, which flex-js's own benchmark shows - nothing like the gap here. The pairing never builds them: the scanner's rules hand each token to the parser and return nothing.

Size

What a caller ships is the parser the generator wrote, and a lexer beside it. Minified, and gzipped as a server would send them:

| | minified | gzipped | | ------------------------------------------ | -------- | ------- | | the SQL parser generated for the benchmark | 10 KB | 3 KB | | flex-js, the lexer beside it | 13 KB | 3 KB | | both together | 23 KB | 6 KB | | chevrotain's runtime, before any grammar | 110 KB | 30 KB |

The generator itself is C and stays behind. Nothing it writes refers back to it, and what it writes has no dependencies at all.

Generated Parser

The generator writes a .js beside the grammar holding one class, named by %name. Nothing is exported unless you say so, which is what the %code section is for:

%code { module.exports = Parser; }

The class carries a constant for every terminal, named with %token_prefix, and these methods:

• new Parser(argument) - the argument is the one %extra_argument names, and is left out by a grammar that declares none.
• parse(major, minor) - hand over one token: its constant, and the value the actions receive. Call parse() with nothing to say the input has ended.
• setTraceCallback(callback, prompt) - report every shift, reduce and accept. The callback is given the text, and the prompt goes in front of each line.
• trace(message) - write one line through that callback.
• getStackPeak() - how deep the parser stack has been, to compare against %stack_size.
• init() - return the parser to its starting state, ready for another input. The constructor calls it, so it is only needed to reuse a parser.
• finalize() - run the destructors over whatever the stack still holds, for a parse given up partway. It is worth calling only for a grammar that declares destructors: they may hold something JavaScript will not reclaim on its own, where the stack itself it will. The parser needs init() again afterwards, so this is not a cleanup to reach for out of habit.

The declaration beside the parser gives TypeScript callers the token constants as literal types. It assumes export =, which module.exports = Parser in a %code section comes to.

var parser = new Parser(context);

parser.parse(parser.TOKEN_INT, 42);
parser.parse(parser.TOKEN_PLUS);
parser.parse(parser.TOKEN_INT, 8);
parser.parse();

Reporting where an error is

Neither this nor lemon in C tracks where a token came from; the stack holds a state, a token and its value. That is the lexer's to know, so %syntax_error reaches it through %extra_argument.

%extra_argument { ctx }
%syntax_error {
  ctx.errors.push('unexpected ' + JSON.stringify(TOKEN) +
    ' at line ' + ctx.lexer.getLine() + ', column ' + ctx.lexer.getColumn());
}

With the lexer on the context and its rules feeding the parser, a bad token reports as unexpected "oops" at line 2, column 3. TOKEN is the value the lexer passed for it, and the parser also carries yyTokenName, which names every token the grammar declared.

Lexer

A primitive single-state lexer is bundled in lexer/. It has no dependencies, takes the first rule that matches, and is enough for the calculator example or as a starting point for one of your own.

Past that, FLEX.JS 2 is the lexer this is meant to be used with: FLEX itself, generating scanners from a grammar file. The pairing lemon and flex have in C.

npm install --save-dev flex-js

The scanner is a named export, and the two meet through yy: give the scanner the parser, and let the rules hand tokens straight to it.

var { Scanner } = require("./tokens.js");
var Parser = require("./calc.js");

var context = {};
var parser = new Parser(context);
var scanner = new Scanner("1 + 2 + 39");

scanner.yy = parser; // a rule body calls yy.parse(yy.TOKEN_INT, value)
scanner.lex(); // every token, straight into the parser
parser.parse(); // no more tokens: finish

context.result; // 42

Development

npm test          # against a generator compiled from this tree
npm run bench     # against other parsers, installed into benchmark/
./build-dev.sh    # both generators, and the C example, to compare them
./build-dist.sh   # the binaries the package ships, each one run afterwards
npm run test:dist # the same tests, against those binaries

npm test compiles lemon-js.c first, so it never runs against a stale binary. Publishing builds the shipped binaries and then runs the tests against them, reaching them the way an install does.

The original lemon.c and lempar.c are kept beside the ported ones so the changes stay easy to read as a diff. Nothing should reformat them, which is why trailing whitespace is left alone in C files.

Alternative Lexers

Maintained:

• moo - all rules compiled into one sticky expression, first match wins
• chevrotain - lexer and parser toolkit, token modes, first match wins

Unmaintained:

• lexed.js
• lexer
• jslex

Alternative Parsers

• jison - parser generator, jison-lex accepts FLEX-style lex files
• peggy - PEG parser generator, successor to PEG.js, no separate scanner
• jscc - LALR(1) parser generator

License

Public domain. The generator and its template come from SQLite, whose author disclaims copyright to them, and the translation to JavaScript and the changes to the generator are released on the same terms. See LICENSE.