Compiling a Grammar

This package is for development only: composer require phplrt/compiler --dev

The compiler reads a grammar file - the tokens, the rules, the reducers - and gives you back a working parser. It is the friendly front end to everything the lexer builder and parser builder can do.

Reading A Grammar

1use Phplrt\Compiler\Compiler;
2use Phplrt\Source\FileSource;
3use Phplrt\Source\StringSource;
4
5$parser = new Compiler()
6    ->load(FileSource::createFromPathname(__DIR__ . '/grammar.pp3'))
7    ->getParser();
8
9echo $parser->parse(StringSource::createFromString('2 + 2'));

load() reads the grammar (and everything it %includes), and getParser() compiles it. That is the whole thing for a script or a prototype.

You can load several grammars into one compiler - they all end up in the same lexer and parser:

1$compiler = new Compiler();
2$compiler->load(FileSource::createFromPathname(__DIR__ . '/lexemes.pp3'));
3$compiler->load(FileSource::createFromPathname(__DIR__ . '/expressions.pp3'));
4
5$parser = $compiler->getParser();

Grammar Formats

The format is decided by the file extension:

Write .pp3 for anything new. A .pp2 file keeps being read the way it always was, so an existing grammar needs no attention.

A grammar that did not come from a file (a StringSource, a string) is read as the newest format, since there is no extension to go by:

$compiler->load(StringSource::createFromString('%token T_DIGIT \d++  Num : <T_DIGIT> ;'));

Reading a .pp file gives you a clear error rather than a confusing one:

1error[UnsupportedFormatException]: Grammar files written in the "pp" format
2are not supported
3 --> /app/grammar.pp:1:1

Splitting A Grammar Up

Real grammars get long. %include pulls in another file, and the declarations land exactly where the %include is written:

1%include grammar/lexemes
2%include grammar/literals
3%include grammar/expressions
4
5%pragma root Expression

A few useful details:

• the path is relative to the file the %include is written in;
• the extension may be omitted - every known format is tried in turn;
• a grammar reached from several places is read once, so a shared lexemes.pp3 can be included by every file that needs it.

If the file is missing, the error names both the include and the file that wanted it:

1error[GrammarNotFoundException]: grammar/missing: failed to open stream:
2No such file or directory
3 --> /app/grammar.pp3:1:1
41 | %include grammar/missing
5  | ^^^^^^^^^^^^^^^^^^^^^^^^

Errors inside an included grammar are reported the same way, with the chain of includes that led there.

Generating Code

Reading a grammar file takes time. Not much - but it is time spent on every single request, doing exactly the same work, to produce exactly the same parser. Generate the parser once instead, commit it, and the compiler never runs in production again.

1use Phplrt\Compiler\Compiler;
2use Phplrt\Source\FileSource;
3
4new Compiler()
5    ->load(FileSource::createFromPathname(__DIR__ . '/grammar.pp3'))
6    ->generate()
7        ->withNamespaceName('App\Calculator')
8        ->withClassName('SumParser')
9        ->save(__DIR__ . '/SumParser.php');

1$parser = new App\Calculator\SumParser();
2
3echo $parser->parse(StringSource::createFromString('2 + 2')); // 4

That is it. The generated file needs phplrt/lexer and phplrt/parser, and nothing else - phplrt/compiler can go in require-dev.

What Comes Out

Given this grammar:

 1%skip  T_WHITESPACE  \s++
 2%token T_DIGIT       \d++
 3%token T_PLUS        \+
 4
 5Sum -> { return \array_sum($children); }
 6  : Number() (::T_PLUS:: Number())*
 7  ;
 8
 9Number -> { return (int) $children->value; }
10  : <T_DIGIT>
11  ;

you get this file:

 1<?php
 2
 3declare(strict_types=1);
 4
 5namespace App\Calculator;
 6
 7/**
 8 * @internal This code has been generated by the phplrt compiler and should not
 9 *           be edited by hand
10 */
11
12readonly class SumParser implements \Phplrt\Contracts\Parser\ParserInterface
13{
14    public const int T_WHITESPACE = 0;
15    public const int T_DIGIT = 1;
16    public const int T_PLUS = 2;
17
18    protected readonly \Phplrt\Contracts\Parser\ParserInterface $parser;
19
20    protected readonly \Phplrt\Contracts\Lexer\LexerInterface $lexer;
21
22    public function __construct()
23    {
24        $this->lexer = new \Phplrt\Lexer\Lexer(
25            pattern: '/\G(?|(?:(?:\s++)(*MARK:0))|(?:(?:\d++)(*MARK:1))|...',
26            channels: [
27                'Hidden',
28                3 => 'Unknown',
29            ],
30            names: [
31                'T_WHITESPACE',
32                'T_DIGIT',
33                'T_PLUS',
34            ],
35        );
36
37        $this->parser = new \Phplrt\Parser\Parser(
38            lexer: $this->lexer,
39            grammar: [
40                new \Phplrt\Parser\Grammar\Concatenation([1, 2]),
41                new \Phplrt\Parser\Grammar\Lexeme(self::T_DIGIT, true),
42                new \Phplrt\Parser\Grammar\Repetition(3, 0, \INF),
43                new \Phplrt\Parser\Grammar\Concatenation([4, 1]),
44                new \Phplrt\Parser\Grammar\Lexeme(self::T_PLUS, false),
45            ],
46            initial: 0,
47            reducers: [
48                0 => self::reduceSum(...),
49                1 => self::reduceNumber(...),
50            ],
51            lookahead: [ /* ... */ ],
52            kept: [ /* ... */ ],
53            choicePrediction: [ /* ... */ ],
54            expectations: [ /* ... */ ],
55        );
56    }
57
58    public function parse(\Phplrt\Contracts\Source\ReadableInterface $source): mixed
59    {
60        return $this->parser->parse($source);
61    }
62
63    private static function reduceSum(\Phplrt\Parser\Context $ctx, mixed $children): mixed
64    {
65        return \array_sum($children);
66    }
67
68    private static function reduceNumber(\Phplrt\Parser\Context $ctx, mixed $children): mixed
69    {
70        return (int) $children->value;
71    }
72}

A few things worth pointing out.

Tokens become constants. SumParser::T_DIGIT is a real class constant, so anything reading the token stream can name tokens instead of guessing ids:

1if ($token->id === SumParser::T_DIGIT) {
2    // ...
3}

Reducers become methods, named after their rule. Your code is right there - steppable in a debugger, visible in a stack trace, and checked by static analysis like any other file.

The whole lexer is one regular expression. No token list is walked at runtime; PCRE does the work in a single pass and (*MARK:n) says which token won.

The analysis is baked in. Whatever the compiler could work out about the grammar ahead of time is written out as a table, so the parser reads the answer instead of arriving at it again on every rule.

Shaping The Output

generate() returns an immutable object - each method returns a new one, so order does not matter:

1new Compiler()
2    ->load(FileSource::createFromPathname(__DIR__ . '/grammar.pp3'))
3    ->generate()
4        ->withNamespaceName('App\Parser')                  // namespace App\Parser;
5        ->withClassImport('App\Ast\NumberNode')            // use App\Ast\NumberNode;
6        ->withClassImport('App\Ast\Node', as: 'BaseNode')  // use App\Ast\Node as BaseNode;
7        ->withClassName('LanguageParser')                  // class LanguageParser
8        ->save(__DIR__ . '/LanguageParser.php');

save() is the only method that does anything: it writes the code down and creates the missing directories on the way.

Shaping The Declaration

The declared parser is readonly, and nothing but the constructor writes to it. How that is spelled follows the version it is generated for: a declaration from PHP 8.2 up, an annotation below it.

Where a parser of one's own adds state, drop it:

1(new Compiler())
2    ->load(FileSource::createFromPathname(__DIR__ . '/grammar.pp3'))
3    ->generate()
4        ->withClassName('LanguageParser')
5        ->withReadonly(false)
6        ->save(__DIR__ . '/LanguageParser.php');

class LanguageParser implements \Phplrt\Contracts\Parser\ParserInterface { /* ... */ }

A parser is also declared abstract, for a grammar that is the base of a parser written by hand, or final, for one nothing is meant to extend:

1use Phplrt\Compiler\Generator\ClassModifier;
2
3(new Compiler())
4    ->load(FileSource::createFromPathname(__DIR__ . '/grammar.pp3'))
5    ->generate()
6        ->withClassName('CompiledLanguageParser')
7        ->withClassModifier(ClassModifier::Abstract)
8        ->save(__DIR__ . '/CompiledLanguageParser.php');

abstract readonly class CompiledLanguageParser implements \Phplrt\Contracts\Parser\ParserInterface { /* ... */ }

1final readonly class LanguageParser extends CompiledLanguageParser
2{
3    // the methods the reducers of the grammar call
4}

A modifier is written onto a declaration, which an anonymous parser has none of, so asking for one without a class name is reported:

1error[UnsupportedClassModifierException]: An anonymous parser cannot be
2declared as abstract

Choosing The PHP Version To Generate For

The parser is generated for the PHP the generator itself runs on. Where the parser is meant to run somewhere else, say so:

1use Phplrt\Compiler\Generator\TargetPhpVersion;
2
3new Compiler()
4    ->load(FileSource::createFromPathname(__DIR__ . '/grammar.pp3'))
5    ->generate()
6        ->withClassName('LanguageParser')
7        ->withTargetPhpVersion(TargetPhpVersion::Php81)
8        ->save(__DIR__ . '/LanguageParser.php');

The lowest target is TargetPhpVersion::Php81, and a version is also read from a string: TargetPhpVersion::fromString('8.1').

This matters when the parser is committed rather than built on the machine that runs it - a library generating on 8.4 and shipping to users on 8.1, or a build step running on a newer PHP than production. Generate for the lowest version you support, and the file loads everywhere above it.

Named Class or Anonymous?

With a class name, you get a declaration:

class LanguageParser implements \Phplrt\Contracts\Parser\ParserInterface { /* ... */ }

$parser = new App\Parser\LanguageParser();

Without one, the file returns an anonymous parser:

return new class implements \Phplrt\Contracts\Parser\ParserInterface { /* ... */ };

$parser = require __DIR__ . '/parser.php';

Use the named form for anything autoloaded - it is a normal class, and composer will find it. The anonymous form is handy for a one-off script, or when you do not want the parser in the global class namespace at all.

Getting The Code Without Writing It

The output is Stringable, so you can do what you like with it:

1$code = (string) new Compiler()
2    ->load(FileSource::createFromPathname(__DIR__ . '/grammar.pp3'))
3    ->generate()
4        ->withNamespaceName('App\Parser')
5        ->withClassName('LanguageParser');
6
7// run it through php-cs-fixer, diff it against the committed version,
8// write it into a phar, whatever you need

That is how the build is kept honest: generate into a string, compare it with the committed file, and fail if the two have drifted apart. Automation and CI has the project layout, the composer scripts and the CI jobs that do it.

When Not To Generate

Generation is not always the answer. Read the grammar at runtime when:

• you are still writing it, and regenerating on every change is friction;
• the grammar is user-supplied or assembled at runtime;
• it is a script, run once, where startup cost does not matter.

1// Perfectly reasonable for a CLI tool
2$parser = new Compiler()
3    ->load(FileSource::createFromPathname($argv[1]))
4    ->getParser();

phplrt Does This To Itself

The .pp3 format is described by a grammar written in .pp3, and the parser reading your grammar files is generated from it - the same generate() call you have just seen, committed to the repository.

It has to be that way: reading a grammar file needs a parser, so the parser of a format cannot be built from the grammar describing it at runtime. The grammar lives in resources/pp3.pp3 - split with %include into lexemes, statements and quantifiers - the parser it compiles into lives in src/Syntax/PP3/PP3Parser.php, and a test compares the two so they cannot drift apart.

The nice side effect is what you get too: a parser that is built costs a few milliseconds to construct, and a parser that is generated costs a new.

Getting At The Pieces

The compiler is a thin layer over the two builders, and both are public:

 1$compiler = new Compiler();
 2$compiler->load(FileSource::createFromPathname(__DIR__ . '/grammar.pp3'));
 3
 4// Add a token the grammar file does not mention
 5$compiler->lexer->addPattern('#[^\n]*+')
 6    ->hide();
 7
 8// Add a compiler pass of your own
 9$compiler->parser->addCompilerPass(new MyValidationPass());
10
11$parser = $compiler->getParser();

build() gives you the compiled description instead of a ready parser - which is what the generator works from:

1$result = $compiler->build();
2
3$result->lexer;  // LexerBuilderResult
4$result->parser; // ParserBuilderResult

Errors

Everything that can go wrong points at the exact spot in the grammar:

1error[UnsupportedPragmaException]: Unrecognized pragma "unknown"
2 --> /app/grammar.pp3:2:1
31 | %token T_A a
42 | %pragma unknown value
5  | ^^^^^^^^^^^^^^^^^^^^^
63 | A : <T_A> ;

The message above is what printing the exception gives you - see Errors for catching and rendering them.

What's Next?

• PP3 Grammar Syntax - everything a .pp3 file can say.
• Results and Reducers - the PHP a grammar carries and what it is given.
• Command Line - checking and compiling a grammar with vendor/bin/phplrt.
• Custom Generator - turning a compiled grammar into something other than a PHP parser.
• Automation and CI - composer scripts and CI jobs that keep the grammar and the generated parser in step.
• PP2 Grammar Syntax - everything a .pp2 file can say.