README

Handler-driven tokenizer and AST builder for PHP. You describe a language as two ordered lists of small callables, one that turns characters into tokens and one that turns tokens into tree nodes. The library runs them, backtracks when a handler does not match, reports errors with line, column and a source snippet, and gives you a navigable, searchable, compilable syntax tree.

What you get

Two stages, one engine. Tokenizer and Lexifier both drive a SyntaxProcessor over an InputStream with your handlers. Learn it once. A Grammar bundles both stages and is reusable across sources.
Declarative rules for the common tokens. Rule::regex(), literals(), keywords(), string(), number(), skip(), lineComment() and blockComment() return ready-made handlers, so most token registries are a short list of one-liners.
Expressions solved. PrattParser parses operator precedence, associativity, prefix and postfix operators, parentheses and calls from a table of parselets, and gives every node its source span.
Backtracking for free. Each handler runs on a saved state. Return false and the input is rewound before the next handler is tried.
Positioned errors. A failed parse throws SyntaxError with the line and column where the construct started, where it failed, and the surrounding source.
A real tree. BaseNode keeps parent and sibling links, an attribute bag and ordered children. Ast adds depth-first and breadth-first traversal, predicate search, cloning, JSON serialisation and a readable text dump. AstCursor builds the tree imperatively; NodeTraverser rewrites it with enter/leave visitors that replace, remove or skip nodes.
Testable. ParserAssertions gives PHPUnit assertTokens(), assertAst() and assertSyntaxError().
Compilation. Nodes compile themselves through a Compiler; override compile() on your node classes to emit whatever output you need.
No runtime dependencies beyond PHP 8.1 and the ctype and json extensions. Fully typed, PHPStan level max with strict rules.

What it is not

Not a parser generator. There is no grammar file; handlers are plain PHP.
Not a grammar-driven statement parser. PrattParser covers expressions; for statements, handlers give you the primitives (match, consume, tryParse, peek) and the strategy is yours.
Not Unicode-aware at the character level. TokenParser works on bytes; match multi-byte text with regular expressions and the u modifier.

Install

composer require chatflowphp/parser

Quick start

A configuration language:

# Application settings
name  = "My App"
debug = true

[database]
host = localhost
port = 5432

1. Token handlers

A token handler receives the TokenParser and the TokenStream. It returns true after consuming input (with or without emitting a token) and false when the input at the current position is not its business. Rule builds handlers for the usual cases; anything that needs lookahead or context is a plain closure. Registries are typed per stage, so PHPStan checks the handler signatures.

use Parser\HandlerRegistry;
use Parser\Rules\Rule;
use Parser\Tokenizer\TokenParser;
use Parser\Tokenizer\TokenStream;

$tokens = HandlerRegistry::forTokens([
    Rule::skip('/[ \t\r]+/'),                       // consumed, no token
    Rule::lineComment('#'),
    Rule::literal('NEWLINE', "\n"),
    Rule::regex('SECTION', '/\[([\w.-]+)\]/', 1),    // lexeme is group 1
    Rule::literal('EQUALS', '='),
    Rule::string('STRING', '"'),
    Rule::keywords('BOOL', ['true', 'false']),
    Rule::number('NUMBER', signed: true),
    // An identifier before "=" is a key; any other bare word is a value.
    static function (TokenParser $in, TokenStream $out): bool {
        $groups = $in->matchRegex('/([A-Za-z_][\w.-]*)([ \t]*=)?/');   // groups, or null
        if ($groups === null) {
            return false;
        }
        $in->advance(strlen($groups[1]));                             // the word only
        $out->addToken($groups[2] === null ? 'WORD' : 'IDENT', $groups[1]);
        return true;
    },
]);

addToken() takes the token type and its lexeme. The token's Span (start and end line, column and byte offset) is computed from where the current handler started to where it stopped, so handlers never deal with positions.

2. Lexer handlers

A lexer handler receives the LexerParser (a cursor over the token stream) and the Ast. It matches token sequences and adds nodes through the cursor.

use Parser\Lexifier\Ast;
use Parser\Lexifier\BaseNode;
use Parser\Lexifier\LexerParser;

$nodes = HandlerRegistry::forNodes([
    static function (LexerParser $in): bool {
        if (!$in->isCurrentTokenOfType('NEWLINE')) {
            return false;
        }
        $in->skipTokensOfType('NEWLINE');
        return true;
    },
    static function (LexerParser $in, Ast $out): bool {
        if (!$in->isCurrentTokenOfType('SECTION')) {
            return false;
        }
        [$token] = $in->consume('SECTION');
        $cursor = $out->getCursor();
        $cursor->moveToRoot();
        $cursor->enterNode(new BaseNode('section', ['name' => $token->getLexeme()], $token->getSpan()));
        return true;
    },
    static function (LexerParser $in, Ast $out): bool {
        if (!$in->match(['IDENT', 'EQUALS'])) {
            return false;
        }
        [$key] = $in->consume(['IDENT', 'EQUALS']);
        $value = $in->consumeOneOf('STRING', 'NUMBER', 'BOOL', 'WORD')
            ?? $in->throwError('Missing value for key "' . $key->getLexeme() . '".');
        $out->getCursor()->addNode(new BaseNode(
            'assignment',
            ['key' => $key->getLexeme(), 'value' => $value->getLexeme()],
            $in->getConsumedSpan(),
        ));
        return true;
    },
]);

3. Parse

use Parser\Grammar;

$grammar = new Grammar($tokens, $nodes);   // build once, reuse for every source
$ast = $grammar->parse($source);

foreach ($ast->findNodesOfType('assignment') as $node) {
    echo $node->getAttribute('key'), ' => ', $node->getAttribute('value'), PHP_EOL;
}

echo json_encode($ast, JSON_PRETTY_PRINT);

The complete, typed version of this grammar, including custom node classes that compile back to normalised source, lives in examples/key-value. Run it with:

php examples/key-value/run.php

Two more examples, examples/arithmetic and examples/template, are listed under Examples.

Grammar::tokenize() and Grammar::lexify() run one stage at a time, which is handy for testing token handlers in isolation. The root node type defaults to root; pass a factory as the third constructor argument to change it:

$grammar = new Grammar($tokens, $nodes, static fn() => new ProgramNode());

Documentation

Start at the documentation hub:

Getting Started, the key-value language step by step
Token rules, Lexer handlers, Expressions
AST, Errors, Compiling, Testing

Examples

Example	Shows
key-value	Rules, one lookahead handler, typed nodes, sections via the cursor, normalising compiler
arithmetic	`PrattParser` with precedence, associativity, unary and postfix operators, calls; an evaluator
template	Mode-switching tokenizer, nested `if`/`for` blocks through cursor navigation, a renderer, round-trip compilation

php examples/template/run.php

How processing works

SyntaxProcessor::process() loops until the input is at its end. At every position it opens an error context, then tries the handlers in registration order:

Handler outcome	Effect
returns `false`	position is rewound, next handler is tried
returns `true`	consumption is kept, next position
returns `true` without consuming	`SyntaxError` (prevents infinite loops)
throws `TokenException`	`SyntaxError` with the position of the failure and the context start
no handler matched	`SyntaxError` "No matching definition found."

Any other exception propagates unchanged.

Input stream API

Both input streams share the InputStream contract (getPosition, isAtEnd, saveState, restoreState, discardState, beginContext, endContext, throwError) and add stage-specific methods.

`TokenParser` (characters)

Group	Methods
Navigate	`advance`, `backtrack`, `setPosition`, `isAtEnd`
Inspect	`currentChar`, `nextChar`, `previousChar`, `peek`, `isWhitespace`, `isAlpha`, `isDigit`, `isAlnum`
Match	`match`, `matchAny`, `matchesRegex`, `matchesRegexAny`, `matchRegex`
Consume	`consume`, `consumeAny`, `consumeOptional`, `consumeRegex`, `consumeRegexAny`, `consumeRegexGroups`, `consumeWhile`, `consumeUntil`, `consumeUntilOrEOF`
Skip	`expect`, `expectAny`, `skipWhile`, `skipUntil`, `skipWhitespace`
Read	`getSource`, `getSourceText`, `getRemaining`, `getProcessed`, `getCurrentLine`, `getLineAt`, `getSourcePosition`, `positionAt`, `spanBetween`, `getContextSpan`
Speculate	`tryParse`

Regular expressions are matched at the current position (PCRE anchored mode); they do not need ^ or \G, cannot match text further ahead, and tokenization stays linear in the size of the source.

`LexerParser` (tokens)

Wherever a sequence is accepted, pass a token type or a list of token types.

Group	Methods
Navigate	`advance`, `backtrack`, `setPosition`, `rewindTo`, `isAtEnd`
Inspect	`currentToken`, `nextToken`, `previousToken`, `peek`, `isCurrentTokenOfType`, `isNextTokenOfType`, `isPreviousTokenOfType`
Match	`match`, `matchAny`
Consume	`consume`, `consumeAny`, `consumeOptional`, `consumeOneOf`, `consumeWhile`, `consumeWhileType`, `consumeUntil`, `consumeUntilOrEOF`
Skip	`expect`, `expectAny`, `skipWhile`, `skipTokensOfType`, `skipUntil`, `skipUntilType`
Read	`getSource`, `getRemaining`, `getProcessed`, `getSourcePosition`, `positionAt`, `getConsumedSpan`, `spanOf`, `spanBetween`, `assertAtEnd`, `assertNotEOF`
Speculate	`tryParse`

consumeUntil stops before the end sequence; skipUntil moves past it.

tryParse() runs a closure on a saved state, keeps its consumption on success and rewinds on any exception before rethrowing. Use it for alternatives:

try {
    $node = $in->tryParse(fn(LexerParser $p) => parseFunctionCall($p));
} catch (TokenException) {
    $node = parseIdentifier($in);
}

Token rules

Every Rule factory returns a Closure(TokenParser, TokenStream): bool that matches at the current position, consumes the match and emits one token (none for the skipping rules). Order still matters: rules are tried in registration order like any handler, so put keywords() before the identifier rule and literals() after the comment rules.

Rule	Matches	Lexeme
`regex($type, $pattern, $group = 0)`	the pattern; an empty match counts as no match	capture group `$group` (index or name), `''` when it did not participate
`literal($type, $text)`	exactly `$text`	`$text`
`literals([$type => $text \| [$texts]])`	the longest text in the table, whatever the table order	the text
`keywords($type, $words, $boundary = '\b')`	the longest word followed by `$boundary`, a regex fragment	the word
`skip($pattern)`	the pattern; emits nothing
`lineComment($marker, $type = null)`	`$marker` to the end of the line, line break excluded; emits only with `$type`	the comment, marker included
`blockComment($open, $close, $type = null)`	`$open` to the next `$close`, line breaks included; emits only with `$type`	the comment, delimiters included
`string($type, $quote, $escape = '\\', $multiline = true)`	a quoted string; `$escape` makes the next character literal, `''` disables it	the raw text between the quotes, plus a `quote` attribute
`number($type, $float = true, $signed = false)`	`42`, and with `$float` also `3.14`, `.5`, `1e10`; with `$signed` a leading `+`/`-`	the number, plus a boolean `float` attribute

blockComment() and string() throw a TokenException for an unterminated comment or string, which SyntaxProcessor reports as a SyntaxError at the opening delimiter. Literal and keyword tables are compiled into one anchored regular expression, so a table with fifty operators costs one preg_match per position.

Expressions

Parser\Expression\PrattParser is an operator-precedence parser that runs inside a node handler. Register a parselet per token type, then call parse() with the LexerParser:

use Parser\Expression\Associativity;
use Parser\Expression\PrattParser;

$binary = static fn(Node $l, Token $op, Node $r): Node => new BinaryNode($op->getLexeme(), $l, $r);

$expr = (new PrattParser())
    ->atom('NUMBER', static fn(Token $t): Node => new NumberNode((float) $t->getLexeme()))
    ->atom('IDENT', static fn(Token $t): Node => new VariableNode($t->getLexeme()))
    ->grouping('LPAREN', 'RPAREN')
    ->call('LPAREN', 'RPAREN', 'COMMA', 60, static fn(Node $callee, array $args, Token $t): Node => new CallNode($callee, $args))
    ->unary('MINUS', 30, static fn(Token $op, Node $x): Node => new UnaryNode('-', $x))
    ->postfix('BANG', 50, static fn(PrattParser $p, Token $op, Node $x): Node => new UnaryNode('!', $x))
    ->binary('PLUS', 10, $binary)
    ->binary('MINUS', 10, $binary)
    ->binary('STAR', 20, $binary)
    ->binary('CARET', 40, $binary, Associativity::Right);

$nodes = HandlerRegistry::forNodes([
    static function (LexerParser $in, Ast $out) use ($expr): bool {
        $out->getCursor()->addNode($expr->parse($in));
        return true;
    },
]);

Binding powers are plain integers; a higher power binds tighter. parse() stops before the first token that cannot continue the expression, so the handler decides what may follow (a newline, a semicolon, )).

Method	Registers
`atom($type, fn(Token): Node)`	a leaf built from one token
`unary($type, $power, fn(Token, Node): Node)`	a prefix operator whose operand is parsed at `$power`
`binary($type, $power, fn(Node, Token, Node): Node, $assoc)`	an infix operator; the right operand is parsed at `$power` (left-associative) or just below it (right-associative)
`postfix($type, $power, fn(PrattParser, Token, Node): Node)`	a postfix operator
`grouping($open, $close)`	parentheses; the inner node is returned unchanged
`call($open, $close, $separator, $power, fn(Node, list<Node>, Token): Node)`	a call on any expression followed by `$open`
`prefix($type, fn(PrattParser, Token): Node)`	anything else that starts an expression
`infix($type, $power, fn(PrattParser, Token, Node): Node)`	anything else that continues one, such as `?:`

Custom parselets continue with $parser->parseExpression($minPower) and consume tokens through $parser->getInput(). A node returned without a span gets the span of the tokens it was parsed from. A missing operand or an unclosed bracket throws a TokenException, which the processor turns into a positioned SyntaxError.

Positions and spans

Every token carries a Span: a start and end Position with 1-based line, column (in UTF-8 code points) and byte offset. Nodes carry an optional span that handlers set from the tokens they consumed:

[$token] = $in->consume('SECTION');
$node = new BaseNode('section', ['name' => $token->getLexeme()], $token->getSpan());

// or, after consuming several tokens inside one handler:
$node->setSpan($in->getConsumedSpan());

That is what makes errors after parsing precise:

foreach ($ast->findNodesOfType('assignment') as $node) {
    if (!isset($allowed[$node->getAttribute('key')])) {
        throw new RuntimeException(sprintf('Unknown key at %s.', $node->getSpan()?->getStart()));
        // Unknown key at line 5, column 1.
    }
}

The tree

$root = $ast->getRoot();                 // BaseNode 'root'
$ast->getAllNodes();                     // pre-order list
$ast->traverse(fn(Node $n) => ...);      // depth-first, callable, Visitor or NodeVisitor
$ast->traverseBFS($visitor);             // breadth-first
$ast->findNode(fn(Node $n) => $n->hasAttribute('name'));
$ast->findNodesOfType('assignment', 'section');
$ast->cloneAst();                        // deep copy
json_encode($ast);                       // {"nodeType": ..., "attributes": ..., "children": [...]}
echo $ast->dump();                       // indented text, see below

dump() (or AstDumper) renders one node per line with its attributes, which is the quickest way to see what a grammar produced:

root
  assignment key="name" value="My App"
  assignment key="debug" value=true
  section name="database"
    assignment key="host" value="localhost"
    assignment key="port" value=5432

Pass withSpans: true to append @line:column-line:column to every line.

Rewriting the tree

NodeTraverser walks the tree depth-first and calls enter() before and leave() after each node's children on every registered NodeVisitor. Each call returns what happens next: null or TraversalAction::Continue, SkipChildren, Remove, Stop, or a replacement Node. Replacements and removals are applied to the parent on the spot.

use Parser\Traversal\AbstractNodeVisitor;
use Parser\Traversal\CallbackNodeVisitor;
use Parser\Traversal\NodeTraverser;
use Parser\Traversal\TraversalAction;

// Fold constant additions, drop empty sections.
final class Folder extends AbstractNodeVisitor
{
    public function leave(Node $node): TraversalAction|Node|null
    {
        if ($node instanceof BinaryNode && $node->getOperator() === '+'
            && $node->getLeft() instanceof NumberNode && $node->getRight() instanceof NumberNode) {
            return new NumberNode($node->getLeft()->getValue() + $node->getRight()->getValue());
        }
        if ($node->getType() === 'section' && $node->getChildren() === []) {
            return TraversalAction::Remove;
        }
        return null;
    }
}

$ast->traverse(new Folder());                       // follows a replaced or removed root
$newRoot = (new NodeTraverser(new Folder(), new CallbackNodeVisitor(
    enter: fn(Node $n) => $n->getType() === 'comment' ? TraversalAction::SkipChildren : null,
)))->traverse($root);                               // any subtree

enter() returning Remove skips the children and leave(); returning a node traverses the replacement instead. Stop ends the whole run; NodeTraverser::wasStopped() tells you it did.

AstCursor (from $ast->getCursor()) moves with moveToParent, moveToFirstChild, moveToLastChild, moveToChild, moveToNextSibling, moveToPreviousSibling, moveToRoot, and edits with addNode, enterNode, replaceNode, removeCurrentNode. Every impossible move throws NodeException.

Extend BaseNode for language-specific nodes and override compile(). A Compiler is line-oriented: write() appends, writeLine() ends the line, indent() / dedent() set the prefix of the following lines.

final class SectionNode extends BaseNode
{
    public function compile(Compiler $compiler): void
    {
        $compiler->writeLine(sprintf('[%s]', $this->getAttribute('name')));
        $compiler->indent();
        parent::compile($compiler);      // children, indented one level
        $compiler->dedent();
    }
}

$compiler = new StringCompiler();       // new StringCompiler('  ', "\r\n") to customise
$ast->compile($compiler);
$compiler->getOutput();

$file = new FileCompiler();
$ast->compile($file);
$file->save('/path/to/output.ini');

Errors

A failed parse throws SyntaxError:

Missing value for key "b". Error context starts at line 2, column 1 and ends at line 2, column 4.
2 | b =
  | ~~~^

The same data is available for tooling:

try {
    $grammar->parse($source);
} catch (SyntaxError $e) {
    $e->getReason();        // 'Missing value for key "b".'
    $e->getPosition();      // Position(line 2, column 4)
    $e->getContextStart();  // Position(line 2, column 1) or null
    $e->getExcerpt();       // the two lines above
    $e->getPrevious();      // the TokenException a handler threw, if any
}

Messages from consume()/expect() say what was expected and what was found: Expected 'IDENT', found NUMBER("42").

Exception	Thrown by
`ParserException`	base class of everything below
`SyntaxError`	`SyntaxProcessor` and `InputStream::throwError()`: a positioned parse failure
`TokenException`	input streams when an `expect`/`consume` does not match, or state cannot be restored
`NodeException`	`AstCursor` and `Ast` on invalid navigation

Testing grammars

Parser\Testing\ParserAssertions is a trait for PHPUnit test cases (phpunit/phpunit is not a dependency of the library, only suggested):

use Parser\Testing\ParserAssertions;

final class MyGrammarTest extends TestCase
{
    use ParserAssertions;

    public function testParse(): void
    {
        // 'TYPE' checks the type, 'TYPE:lexeme' checks both.
        self::assertTokens(['IDENT:name', 'EQUALS', 'STRING:My App'], $grammar->tokenize('name = "My App"'));

        // Compared against AstDumper output; the heredoc indentation is stripped.
        self::assertAst(
            <<<'TREE'
                root
                  assignment key="name" value="My App"
                TREE,
            $grammar->parse('name = "My App"'),
        );

        // Line, column and (optionally) reason; returns the SyntaxError.
        $error = self::assertSyntaxError(2, 5, fn() => $grammar->parse("a = 1\nb = @"), 'No matching definition found.');
    }
}

Development

composer install
composer check     # validate, code style, PHPStan, tests
composer bench     # tokenizer throughput

CI also runs Infection mutation testing; see docs/testing.md.

See CONTRIBUTING.md.

Versioning

Semantic Versioning: after 1.0 only additive changes until 2.0, deprecations announced one minor version ahead. Breaking changes are listed in the GitHub release notes.

License

MIT. See LICENSE.

chatflowphp / parser

Package info

Security

Statistics

README

What you get

What it is not

Install

Quick start

1. Token handlers

2. Lexer handlers

3. Parse

Documentation

Examples

How processing works

Input stream API

`TokenParser` (characters)

`LexerParser` (tokens)

Token rules

Expressions

Positions and spans

The tree

Rewriting the tree

Errors

Testing grammars

Development

Versioning

License

chatflowphp / parser

Package info

Security

Statistics

README

What you get

What it is not

Install

Quick start

1. Token handlers

2. Lexer handlers

3. Parse

Documentation

Examples

How processing works

Input stream API

TokenParser (characters)

LexerParser (tokens)

Token rules

Expressions

Positions and spans

The tree

Rewriting the tree

Errors

Testing grammars

Development

Versioning

License

`TokenParser` (characters)

`LexerParser` (tokens)