Traqula provides a generic core to create a modular LL(K)-grammar parser (read our paper for full details). Typically, modularity is provided on Parser granularity, allowing you to create a parser by extending an existing parser. This kind of extension is similar to how Object-Oriented programming languages allow you to create a class by extending another (see: Chevrotain, ANTLR4). Traqula takes the modularity to the level of grammar rules, allowing you to create a parser by starting from an existing one, then adding, removing or patching existing rules, even allowing you to merge parsers (more information can be found on modifying a parser).
Traqula heavily relies on Chevrotain to perform efficient parsing. Traqula's core itself merely provides a modular system to create a Chevrotain parser using builder-based dependency injection.
Since Traqula starts from Chevrotain, it is important to know that all Chevrotain's documentation is relevant for Traqula too. We will however highlight some core functions:
These functions are provided to the ParserRule impl function of @traqula/core.
We used the notation CONSUME(x) to note that both CONSUME does exist but also CONSUME1 up to CONSUME9,
When providing the same argument to for example CONSUME, Chevrotain requires you to index the occurrence so the parser knows 'where it is at'.
Since Chevrotain is ESM only, but we want to target both CJS and ESM, Traqula depends on a Chevrotain wrapper @traqula/chevrotain.
To create a lexer, one simply defines a token using createToken from @traqula/core,
which is a smart typed wrapper around the version Chevrotain provides.
We define a token that parses 'test' in a case-insensitive way:
import {createToken} from "@traqula/core";
// We recommend using capitalized names for tokens.
const testToken = createToken({ name: 'Test', pattern: /TEST/i });
const wordToken = createToken({ name: 'Word', pattern: /[a-z]+/i });
To create a lexer, you simply add them to a LexerBuilder, and build lexer:
import {LexerBuilder} from "@traqula/core";
const myLexerbuilder = LexerBuilder.create().add(wordToken, testToken)
However: LexerBuilders function as an arrayBuilder where the lexer will lex tokens checking in the order of that array. In our example above our lexer would thus never lex the testToken because 'test' would first match the wordToken. To this end we manipulate our builder:
// Move the testToken before the wordToken in our array.
myLexerBuilder.moveBefore(wordToken, testToken)
// Alternatively:
const myOtherLexerBuilder = LexerBuilder.create().add(testToken, wordToken);
Chevrotain will try to warn you if a token can never be matched.
Using a lexerBuilder, you can either create a Chevrotain lexer using .build(), or get the tokenVocabulary to provide to the parser builder using .tokenVocabulary.
Traqula's core package exposes ParserRule which is the type used to create a single grammar rule.
The type expects you to specify the Context the rule expects, a name, the type the rule returns,
and optionally the
parameters of the grammar rule.
You should then declare the rule as an object containing the name,
and an impl that receives the chevrotain specific functions, returning a function thet receives: the context, and all parameters, which in turn returns something of the returnType.
below we define a simple rule named myRule (we suggest starting with a lowercase letter here), requiring a context { myKey: 'myValue' }, and a single string parameter, returning the string apple:
// context - name - returnType - list of arguments
const myRuleObj: ParserRule<{ myKey: 'myValue' }, 'myRule', 'apple', [ string ]> = {
name: 'myRule',
impl: ({ CONSUME, SUBRULE, ACTION }) => (context, firstRuleParameter) => {
CONSUME(testToken);
SUBRULE(otherRule);
return ACTION(() => 'apple');
}
}
When calling a subRule (e.g. SUBRULE(otherRule)), Traqula does NOT just call the implementation (impl) on that otherRule. Instead, it calls the rule that is currently registered in the parser under the same name, providing the key to Traqula's modularity.
Always provide the string literal type for the rule name, as the ParserBuilder will help you at compile time to verify the construction.
In order to build a modular parser, we group together the various grammar rules in a ParserBuilder.
The ParserBuilder will check that name (which works as the reference to the grammarRule) is only added once.
TypeScript will error on a call that tries to add a rule that is already contained within the builder.
const myParserBuilder = ParserBuilder
// <const> cast required in .create()
.create(<const> [myRuleObj, otherRule]);
When creating be carefully not to add too many rules to the parser using a single call to .create or .addMany.
When doing this, tsc might become unhappy and throw in a similar way that it does when you would add duplicate rules.
In case you want to merge a whole ParserBuilder,
you can call .merge() and provide the other ParserBuilder, possibly requiring you to resolve conflicts when name clashes present.
Building the chevrotain parser is possible using .build(), interestingly, Chevrotain allows multiple start rules, so you can parse starting from any grammar rule.
const myParser = myParserBuilder.build({
tokenVocabulary: myLexerBuilder.tokenVocabulary,
// By default, the positionTracking will be off as to ensure maximal
lexerConfig: {
// Default position tracking is `onlyOffset` since it is faster,
// but the errors generated are much more obscure.
positionTracking: 'full',
// SkipValidation can be off when you know the implementation of the lexer is correct.
// While testing however, we suggest you do not skip this step.
skipValidations: false,
},
parserConfig: {
// SkipValidation can be off when you know the implementation of the parser is correct.
// While testing however, we suggest you do not skip this step.
skipValidations: false,
},
});
// parse string the context
myParser.myRule('test me', { myKey: 'myValue' });
When creating a new parser,
disable skipValidation and only remove it once the implementation is final and correct.
Building a parser is an expensive operator since Chevrotain needs to perform its grammar recording. One should therefore always try to reuse a created parser.
By default, a parser and accompanying generator (see creating a generator) created using @traqula/core
should be able to support round tripping.
By default, to support this, the generator will require the original string for this to work.
However, you can also choose to manipulate the AST in such a way that it delivers the original string to the generator:
import { SourceLocationInlinedSource } from '@traqula/core';
const myAst = myParser.myRule('test me', { myKey: 'myValue' });
myAst.loc = {
sourceLocationType: 'inlinedSource',
newSource: 'test me',
start: 0,
end: Number.MAX_SAFE_INTEGER,
loc: myAst.loc,
startOnNew: 0,
endOnNew: 'test me'.length,
} satisfies SourceLocationInlinedSource;