Skip to content

parser.md

Latest commit

 

History

History
335 lines (254 loc) · 11.5 KB

parser.md

File metadata and controls

335 lines (254 loc) · 11.5 KB
Raw

Parser

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

The parser is the second half of reading source code. The lexer produced a flat list of tokens; the parser checks that they appear in an order the grammar allows, and builds whatever you asked it to build.

Two Methods

That is the whole runtime API:

$parser->parse($source);   // returns your result, or throws on a syntax error
$parser->analyze($source); // reports what it made of the source, never throws
use Phplrt\Source\Source;

$parser->parse(new Source('2 + 2')); // 4
$parser->parse(new Source('2 +'));   // Syntax error, unexpected end of input

parse() is the one you want almost always: the grammar describes the whole source, anything else is a mistake, and a mistake is an exception.

analyze() is for everything else - validating without building, reading a fragment of a larger file, or collecting errors instead of stopping at the first. See Analysing A Source below.

Where Parsers Come From

You will rarely write one by hand. Normally you either compile a grammar file:

$parser = new Compiler()
    ->load(new File(__DIR__ . '/grammar.pp3'))
    ->getParser();

or generate the code once and use the class:

$parser = new App\Calculator\CalculatorParser();

Both give you the same thing: an object implementing ParserInterface.

What A Parser Actually Is

Underneath, a parser is a flat list of rules plus a couple of lookup tables. Rules refer to each other by index - there are no objects pointing at objects, just integers pointing into an array.

Here is the calculator written out by hand, so you can see the shape of it:

use Phplrt\Parser\Context;
use Phplrt\Parser\Grammar\Concatenation;
use Phplrt\Parser\Grammar\Lexeme;
use Phplrt\Parser\Grammar\Repetition;
use Phplrt\Parser\Parser;

// Sum : <T_DIGIT> (::T_PLUS:: <T_DIGIT>)*
$parser = new Parser(
    lexer: $lexer,
    grammar: [
        0 => new Concatenation([1, 2]),     // rule #1 then rule #2
        1 => new Lexeme(tokenId: 0),        // T_DIGIT, kept
        2 => new Repetition(ruleId: 3),     // rule #3, zero or more times
        3 => new Concatenation([4, 1]),
        4 => new Lexeme(tokenId: 1, keep: false), // T_PLUS, thrown away
    ],
    initial: 0, // start at rule #0
    reducers: [
        0 => static fn(Context $ctx, mixed $children): int => \array_sum(
            \array_map(static fn($token) => (int) $token->value, $children),
        ),
    ],
);

echo $parser->parse(new Source('1 + 2 + 3')); // 6

This is exactly what the compiler generates for you - it just also works out what can be told about the grammar ahead of time, which makes it considerably faster.

The rule classes are described in Grammar Rules, and the friendlier way to produce this array is the parser builder.

How It Reads

Phplrt recognizes a PEG with a backtracking, table-driven recursive descent, guided by FIRST sets, and it builds the result only after the whole input has been recognized.

That is a mouthful, so taken apart:

Table-driven. The grammar is a flat array of rules addressed by index, not a set of generated functions. A rule is looked up by its id and recognized according to what kind of rule it is. This is what makes a grammar plain data: it can be optimized, dumped to a file and loaded back.

Recursive descent with backtracking. Rules are tried top-down. When an alternative fails, the token stream is rewound to where the rule started and the next alternative is tried; a failed concatenation rewinds the same way. There is no memoization - this is not a packrat parser - so a grammar that backtracks heavily pays for it. In practice the FIRST sets keep that from happening.

FIRST-set prediction. Every rule knows which tokens are allowed to start it, so before descending into a rule the parser asks whether the token in front of it can begin that rule at all, and gives up right away when it cannot. That turns "try this rule and find out" into a single lookup, which is where most of the speed comes from. The tables are computed while the grammar is being built, so a parser assembled without them is a plain PEG: it reads the same sources, only slower.

Deferred tree construction. Nothing is built while the input is being read. The parser only writes down what it has recognized, and a branch that fails leaves nothing behind. The result is assembled afterwards, in one pass, by running the reducers bottom-up - which is why an analysis that only checks the syntax costs less than one building a value.

Two consequences are worth knowing before you write a grammar.

Alternatives are ordered. The first one that matches wins, and the rest are not tried:

Rule : "a" | "ab" ;

This never reads ab. "a" already matched, and the parser does not go back to look for something longer. Put the longer alternative first:

Rule : "ab" | "a" ;

The upside is that a grammar is never ambiguous: there is exactly one way to read any input, and you can always tell which one by reading top to bottom.

Left recursion is not allowed. A rule cannot start with itself:

// This never terminates, and the builder will refuse it
Expression : Expression() ::T_PLUS:: Number() ;

Write it as a repetition instead - this is the standard translation, and it is what you want anyway:

Expression : Number() (::T_PLUS:: Number())* ;

The builder detects left recursion while compiling and reports it, so you will not discover this at runtime.

Syntax Errors

parse() throws UnexpectedTokenException when the input does not match:

use Phplrt\Parser\Exception\UnexpectedTokenException;

try {
    $parser->parse(new VirtualFile('expr.txt', "1 + 2\n3 * (4 + )\n"));
} catch (UnexpectedTokenException $e) {
    echo $e->getMessage(); // Syntax error, unexpected "3" (T_NUMBER), T_PLUS expected
    echo $e;               // ...plus the snippet below
}
error[UnexpectedTokenException]: Syntax error, unexpected "3" (T_NUMBER), T_PLUS expected
 --> expr.txt:2:1
  |
1 | 1 + 2
2 | 3 * (4 + )
  | ^
3 |

What could have been read instead comes from a table the compiler writes down: a token is called by its name, and one declared inline stands for what it is recognized by - "+" for a value, /\d++/ for a pattern. Several of them read as one of X, Y, Z expected. A parser built by hand and given no such table says nothing about them, and the message ends after the token it stopped on.

The exception carries the token it choked on, so you can build your own message:

$e->token->name;   // T_NUMBER
$e->token->offset; // 6
$e->source;        // the source it was reading

Because the parser backtracks, "the token it choked on" needs a definition. The reported position is the furthest one any rule reached before failing, not the position where the last attempt gave up - otherwise every error would point at the start of the outermost rule. This usually lands where you expect, but it can surprise you: an alternative that got further into the input before failing wins the report, even if a different alternative was the intended one.

See Error Reporting for the full picture.

Input Must Be Consumed Entirely

A parse succeeds only if the grammar reads the whole source. Trailing junk is an error, not a stopping point:

$parser->parse(new Source('2 2')); // Syntax error, unexpected "2" (T_DIGIT)

Analysing A Source

Sometimes that is the wrong rule. The source may hold another language after the fragment yours describes, it may be a line someone is still typing, or you may want to report what is wrong rather than stop at it.

analyze() reads as far as the grammar goes and reports what it made of the source. Nothing about the source makes it throw - how far it got is the class of the result:

use Phplrt\Parser\Analysis\Result\FailureResult;
use Phplrt\Parser\Analysis\Result\PartialResult;
use Phplrt\Parser\Analysis\Result\SuccessfulResult;

$result = $parser->analyze(new Source('2 + 2 } and then some HTML'));

$result instanceof PartialResult; // the grammar stopped before the end
$result->value;                   // 4 - the same value parse() gives for "2 + 2"
$result->token->offset;           // 6 - where the fragment ends
Result Means Carries
SuccessfulResult the grammar read the source in full value
PartialResult the grammar read a fragment and stopped value, token, error
FailureResult the grammar read nothing at all token, error

A source read in full has nothing to report, so only the other two carry an error. The reading stops where it can no longer go on, so there is exactly one thing to say - and it is the very exception the source would be rejected with, not a description of it, so it already knows how to print itself along with the fragment it occurred in:

echo $result->error;
error[UnexpectedTokenException]: Syntax error, unexpected "3" (T_NUMBER), T_PLUS expected
 --> expr.txt:2:1
  |
1 | 1 + 2
2 | 3 + } 4
  | ^
3 |

Its parts are reachable one by one:

$result->error->getMessage(); // Syntax error, unexpected "3" (T_NUMBER), T_PLUS expected
$result->error->token;        // the token it is about
$result->error->source;       // the source it occurred in
$result->error->getCode();    // and the rest of what an exception carries

It is the very same object parse() throws for the same source - not one built to look like it - so an editor and a build never disagree about what is wrong. Rethrowing it is a valid way to turn an analysis back into a failure:

if ($result instanceof FailureResult) {
    throw $result->error;
}

Two Modes

The second argument says how much work to do:

use Phplrt\Parser\Analysis\Mode;

$parser->analyze($source, Mode::Tolerant); // the default - builds the value
$parser->analyze($source, Mode::SyntaxCheck); // recognizes only, runs no reducer

Mode::SyntaxCheck is what check() used to be, except that it tells you how much of the source is valid rather than just whether all of it is:

$result = $parser->analyze($source, Mode::SyntaxCheck);

$result instanceof SuccessfulResult; // the grammar has read something
$result instanceof PartialResult;    // ...and there is more to read

The mode changes nothing about how much of the source is read - only whether the value is built. In Mode::SyntaxCheck every value is null.

The Rules Are Greedy

You get the longest fragment, and a partial iteration is given back whole. With the calculator grammar above, 2 + 2 + stops at the trailing + rather than after it, because the + opens an iteration the grammar cannot finish. That is what tells "not finished yet" from "written wrong", which is what a prompt needs:

// Keep reading lines while the expression is only started
while ($parser->analyze($input, Mode::SyntaxCheck) instanceof PartialResult) {
    $input = new Source($input->content . "\n" . readline('... '));
}

Whats Next?