phplrt 4.0

Results and Reducers

A parser does two things: it decides whether the input is valid, and it builds something out of it. The first part is the grammar. The second part is reducers.

What You Get Without Reducers

A grammar with no reducers still returns something - the tokens it kept, nested the way the rules were:

Sum : <T_DIGIT> (::T_PLUS:: <T_DIGIT>)* ;

1$parser->parse(new Source('2 + 3'));
2// [Token("2"), Token("3")]

That is occasionally enough. Usually you want numbers, or AST nodes, or a configuration array - and for that you attach a reducer.

Attaching A Reducer

A reducer is a block of PHP that runs when its rule matches:

1Number -> { return (int) $children->value; }
2  : <T_DIGIT>
3  ;

Whatever it returns becomes the value of that rule, and gets handed to the rule above.

The same thing through the builder:

1use Phplrt\Parser\Context;
2
3$number->setReducer(static fn(Context $ctx, mixed $children): int
4    => (int) $children->value);

What $children Contains

This is the part worth reading twice.

A rule that recognizes a sequence - a concatenation or a repetition - gets an array:

1Pair : <T_DIGIT> <T_DIGIT> ;      // $children = [Token, Token]
2List : <T_DIGIT>+ ;               // $children = [Token, Token, ...]

Any other rule gets the single value it recognized:

1Number : <T_DIGIT> ;              // $children = Token
2Choice : Number() | Name() ;      // $children = whatever matched

And the arrays are flattened into the parent. If a nested rule returns a list, its items are spliced into the list of the rule above rather than nested inside it:

1Root : <T_A> Pair() <T_B> ;
2Pair : <T_DIGIT> <T_DIGIT> ;
3
4// Root's $children = [Token(a), Token(1), Token(2), Token(b)]
5//               not  [Token(a), [Token(1), Token(2)], Token(b)]

This is deliberate - it keeps the result flat and predictable - but it means that a rule which should produce a group must say so by returning a value of its own. A reducer returning an object or a scalar is never flattened:

1Pair -> { return $children; /* an array */ }  // still flattened
2Pair -> { return new PairNode($children); }   // stays one value ✔

Because a rule can match one thing or a list depending on the input, reducers often start with a check:

 1Expression -> {
 2    // Just one operand: nothing to fold
 3    if (!\is_array($children)) {
 4        return $children;
 5    }
 6
 7    // ...
 8}
 9  : Number() ((<T_PLUS> | <T_MINUS>) Number())*
10  ;

Building An AST

Here is the whole pattern. Define node classes:

 1abstract class Node
 2{
 3    public function __construct(
 4        public readonly int $offset,
 5    ) {}
 6}
 7
 8final class NumberNode extends Node
 9{
10    public function __construct(int $offset, public readonly float $value)
11    {
12        parent::__construct($offset);
13    }
14}
15
16final class BinaryNode extends Node
17{
18    public function __construct(
19        int $offset,
20        public readonly string $operator,
21        public readonly Node $left,
22        public readonly Node $right,
23    ) {
24        parent::__construct($offset);
25    }
26}

Then build them in the grammar:

 1%skip  T_WHITESPACE  \s++
 2%token T_NUMBER      \d++(?:\.\d++)?
 3%token T_PLUS        \+
 4%token T_MINUS       \-
 5
 6%pragma root Expression
 7
 8Expression -> {
 9    if (!\is_array($children)) {
10        return $children;
11    }
12
13    $node = \array_shift($children);
14
15    // Fold left: 1 + 2 - 3  =>  ((1 + 2) - 3)
16    while ($children !== []) {
17        $operator = \array_shift($children);
18        $right = \array_shift($children);
19
20        $node = new \BinaryNode($node->offset, $operator->value, $node, $right);
21    }
22
23    return $node;
24}
25  : Number() ((<T_PLUS> | <T_MINUS>) Number())*
26  ;
27
28Number -> { return new \NumberNode($offset, (float) $children->value); }
29  : <T_NUMBER>
30  ;

Parsing 1 + 2 - 3 gives you a tree:

1BinaryNode(-)
2├── BinaryNode(+)
3│   ├── NumberNode(1)
4│   └── NumberNode(2)
5└── NumberNode(3)

Note $offset in the Number reducer - that is one of the variables the compiler provides. Keeping an offset on every node is what lets you point at the right place in the source when something goes wrong later, during type-checking or evaluation.

The Context

Every reducer receives a Context as its first argument, describing where the analysis is:

1static function (Context $ctx, mixed $children): mixed {
2    $ctx->rule;    // int - the id of the rule being reduced
3    $ctx->token;   // the last token this rule read, or null
4    $ctx->source;  // the source being parsed
5    $ctx->content; // its content, already read
6
7    return null;
8}

In a .pp3 reducer you rarely touch $ctx directly, because the common fields have shorter names - $token, $offset, $source. See PHP in a Grammar.

Returning Nothing

A reducer that returns null leaves the value alone: the children are passed up as if there were no reducer at all. That makes null useful for reducers that only observe:

1Debug -> {
2    \error_log('matched at ' . $offset);
3
4    return null; // do not touch the result
5}
6  : <T_NAME>
7  ;

Reducers Run After Parsing

One thing to be aware of: reducers do not run while the input is being read. The parser first recognizes the whole source, then walks what it recognized and reduces it bottom-up.

This means:

  • a reducer never sees a rule that was tried and rejected - no wasted work, no side effects from a branch that did not win;
  • analyze() in Mode::Fast never runs reducers at all;
  • a reducer cannot influence parsing. It cannot look ahead, change what is matched next, or fail the parse to force a different alternative. If a decision depends on the input, express it in the grammar - that is what predicates are for.