Building a Grammar

This package can be installed separately with composer require phplrt/parser-builder

Writing the rule array by hand works, but you have to keep track of indices yourself, and one inserted rule renumbers everything. The builder does that for you: you describe rules as objects, and it turns them into the flat array - validating and optimizing along the way.

This is also what the grammar compiler uses internally. A .pp3 file is easier to read, so reach for the builder when the grammar is not known ahead of time: assembled from plugins, from a config file, from a database.

A First Grammar

A grammar needs a lexer to refer to, so both builders work together:

 1use Phplrt\Lexer\Builder\LexerBuilder;
 2use Phplrt\Parser\Builder\ParserBuilder;
 3use Phplrt\Source\Source;
 4
 5// --------------------------------------------
 6//  Lexer Builder
 7// --------------------------------------------
 8$lexer = new LexerBuilder();
 9$digit = $lexer->addPattern('\d++', 'T_DIGIT');
10$plus  = $lexer->addValue('+', 'T_PLUS');
11$lexer->addPattern('\s++')
12    ->hide();
13
14
15// --------------------------------------------
16//  Parser Builder
17// --------------------------------------------
18$grammar = new ParserBuilder();
19
20// Sum : <T_DIGIT> (::T_PLUS:: <T_DIGIT>)*
21$sum = $grammar->addConcatenation([
22    $number = $grammar->addTokenReference($digit),
23    $grammar->addRepetition(
24        $grammar->addConcatenation([
25            $grammar->addTokenReference($plus)
26                ->skip(),
27            $number,
28        ]),
29    ),
30]);
31
32// Parsing should start with "$sum"
33$grammar->setInitialRule($sum);
34
35// Building process
36$compiledLexer = $lexer->build();
37$compiledParser = $grammar->build($compiledLexer);
38
39$parser = $compiledParser->toParser(
40    $compiledLexer->toLexer(),
41);
42
43$parser->parse(new Source('1 + 2 + 3'));

Every add*() method returns the rule it created, so you can nest calls or pull them out into variables - whichever reads better.

The Rules

 1// A token, by definition, by name or by id
 2$grammar->addTokenReference($digit);
 3$grammar->addTokenReference('T_DIGIT');
 4$grammar->addTokenReference(0);
 5
 6// ...and one that is read but thrown away
 7$grammar->addTokenReference('T_COMMA')
 8    ->skip();
 9
10// a b c
11$grammar->addConcatenation([$a, $b, $c]);
12
13// a | b | c
14$grammar->addAlternation([$a, $b, $c]);
15
16// a?
17$grammar->addOptional($a);
18
19// a*        a+                 a{2,5}
20$grammar->addRepetition($a);
21$grammar->addRepetition($a, min: 1);
22$grammar->addRepetition($a, min: 2, max: 5);
23
24// &a and !a - look ahead without reading
25$grammar->addPredicate($a);
26$grammar->addPredicate($a, isExpected: false);

Referring to a token by definition is the safest: rename it later and the grammar still works. By name is useful when the token is declared elsewhere - the reference is resolved when the grammar is built, so the order of declaration does not matter.

Naming Rules and Referring To Them

Every add*() method takes an optional name, and a named rule can be pointed at before it exists:

1$grammar->addConcatenation([
2    $grammar->addTokenReference('T_IF'),
3    $grammar->addRuleReference('Expression'), // not defined yet - fine
4], name: 'IfStatement');
5
6$grammar->addAlternation([...], name: 'Expression');

A RuleReference is a placeholder: it is replaced by the rule it points at while the grammar is being built, and never reaches the compiled parser. If nothing defines that name, you get a clear error:

1Rule Expression = Missing refers to the rule named "Missing",
2which has not been defined

Names are for building only. Once the parser is compiled, rules are numbers - except for the ones with a reducer, whose names survive so the generated methods can be called after them.

Reducers

A reducer turns a matched rule into a value. Attach one with setReducer():

1use Phplrt\Parser\Context;
2
3$number = $grammar->addTokenReference('T_DIGIT', 'Number')
4    ->setReducer(static fn(Context $ctx, mixed $children): int
5        => (int) $children->value,
6    );

Any callable works. But note: a closure cannot be written into a generated file. If you plan to generate code, define the reducer as PHP source instead:

1use Phplrt\Parser\Builder\Definition\Reducer\PhpCodeReducer;
2
3$number->setReducer(new PhpCodeReducer(
4    'return (int) $children->value;'
5));

PhpCodeReducer works both ways - it runs in memory and it can be dumped into the generated parser. CallableReducer (which you get implicitly when passing a closure) only runs in memory.

Where To Start

By default the grammar starts at the first rule added. Say otherwise with setInitialRule():

$grammar->setInitialRule($expression);

In a .pp3 file this is %pragma root Expression.

What The Builder Checks

build() does more than assemble an array. It runs a pipeline of passes, and several of them exist purely to tell you that a grammar is wrong before you ship it:

• references are resolved - every RuleReference is replaced by the rule it names;
• unreachable rules are dropped - a rule nothing refers to is not compiled, and does not have to be correct;
• token references are checked - a rule pointing at a token the lexer does not have is an error;
• left recursion is rejected:

1Rule Expression = (...) | <name is "T_NUMBER"> is left recursive:
2Expression -> (...) -> Expression

Then it optimizes. Redundant wrappers are removed, nested concatenations are joined, duplicate rules are merged, repeated alternatives are dropped. A real-world grammar typically loses a few percent of its rules this way, and parses a little faster for it.

Finally, it analyses the grammar it ended up with. Nothing is rewritten at this point: the passes only work out what can be told about the rules ahead of time, and the parser reads the answers instead of asking the same questions over and over. This is most of the reason it is quick.

Adding Your Own Passes

The pipeline is open. A pass gets the whole grammar and may rewrite it:

1use Phplrt\Parser\Builder\ParserBuilder;
2
3$grammar->addCompilerPass(new MyValidationPass(), ParserBuilder::PASS_PRIORITY_CHECK);

The priorities, in the order they run:

A built-in pass can be dropped by name, which is how you opt out of an optimization that does not suit your grammar:

1use Phplrt\Parser\Builder\Compiler\NestedConcatenationParserCompilerPass;
2
3$grammar->removeCompilerPass(NestedConcatenationParserCompilerPass::class);

There are analysis passes too - they do not change the grammar, they describe it:

$grammar->addAnalysisPass(new MyMetadataPass());

A .pp3 grammar can do all of this itself, without any PHP around it:

1%pragma parser.check    \App\Grammar\MyValidationPass
2%pragma parser.disable  \Phplrt\Parser\Builder\Compiler\NestedConcatenationParserCompilerPass

See Settings.

The Result

build() returns a ParserBuilderResult - everything a parser needs, still as data:

1$result = $grammar->build($compiledLexer);
2
3$result->grammar;    // list<RuleInterface>
4$result->initial;    // int
5$result->reducers;   // array<int, ReducerInterface>
6$result->constants;  // ['Sum' => 0, 'Number' => 1]
7$result->lookahead;  // what the analysis found out
8
9$parser = $result->toParser($compiledLexer->toLexer());

Keeping the result around is what makes code generation possible: the same data that runs in memory can be written out as PHP.