.editorconfig000064400000000042146412213010007207 0ustar00[composer.json] indent_size = 4 .github/dependabot.yml000064400000000761146412213010010732 0ustar00# To get started with Dependabot version updates, you'll need to specify which # package ecosystems to update and where the package manifests are located. # Please see the documentation for all configuration options: # https://docs.github.com/code-security/dependabot/dependabot-version-updates/configuration-options-for-the-dependabot.yml-file version: 2 updates: - package-ecosystem: "composer" # Files stored in repository root directory: "/" schedule: interval: "monthly" .github/workflows/php-tests.yml000064400000002756146412213010012617 0ustar00name: PHP Tests on: pull_request: push: permissions: contents: read jobs: run: runs-on: ${{ matrix.operating-system }} strategy: matrix: operating-system: [ ubuntu-latest ] php-version: ['8.2', '8.3'] name: PHP ${{ matrix.php-version }} test on ${{ matrix.operating-system }} steps: - name: Checkout Code uses: actions/checkout@v3 - name: Install PHP id: php uses: shivammathur/setup-php@v2 with: php-version: ${{ matrix.php-version }} - name: Check PHP version run: php -v - name: Cache Composer packages id: composer-cache uses: actions/cache@v3 with: path: vendor key: ${{ runner.os }}-${{ matrix.operating-system }}-php-${{ steps.php.outputs.php-version }} restore-keys: | ${{ runner.os }}-${{ matrix.operating-system }}-php-${{ steps.php.outputs.php-version }} - if: steps.composer-cache.outputs.cache-hit != 'true' name: Install Composer dependencies run: composer install --prefer-dist --no-progress - name: PHPUnit Tests run: vendor/bin/phpunit --coverage-clover ./tests/coverage.xml - name: Upload coverage reports to Codecov uses: codecov/codecov-action@v3 with: token: ${{ secrets.CODECOV_TOKEN }} files: ./tests/coverage.xml flags: os-${{ matrix.operating-system }}_php-${{ matrix.php-version }} verbose: true .gitignore000064400000000160146412213010006523 0ustar00# IDE's .idea/ # Composer vendor/ composer.phar composer.lock # PhpUnit tests/coverage/ .phpunit.result.cache CHANGELOG.md000064400000000243146412213010006346 0ustar00Changelog ========= 1.0.1 (2013-01-29) ------------------ - 2b40f94: Fixed an invalid format in the CLI 1.0.0 (2013-01-15) ------------------ - First release. LICENSE000064400000002126146412213010005544 0ustar00Copyright (c) 2024 Lisachenko Alexander Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. README.md000064400000002272146412213010006020 0ustar00Dissect ----------------- This library is based on @jakubledl and @WalterWoshid work. Dissect library provides a set of tools to create and use lexical parsers. Read more at /docs folder. For the goaop/framework it is responsible for parsing pointcut DSL expressions into AST tree, which might be then processed. ![GitHub Actions Workflow Status](https://img.shields.io/github/actions/workflow/status/goaop/dissect/php-tests.yml?branch=master) [![Total Downloads](https://img.shields.io/packagist/dt/goaop/dissect.svg)](https://packagist.org/packages/goaop/dissect) [![Daily Downloads](https://img.shields.io/packagist/dd/goaop/dissect.svg)](https://packagist.org/packages/goaop/dissect) [![PHP Version](https://img.shields.io/badge/php-%3E%3D%208.2-8892BF.svg)](https://php.net/) ![GitHub License](https://img.shields.io/github/license/goaop/dissect) ## Installation ```bash composer require goaop/dissect ``` # Documentation? [Here](docs/index.md). ## Testing - Run `composer run-script test`
or - Run `composer run-script test-coverage` ## Show your support Give a ⭐ if this project helped you! ## 📝 License This project is [MIT](https://opensource.org/licenses/MIT) licensed. TODO.md000064400000001141146412213010005622 0ustar00Goals ===== 1.1 --- - Optional operator precedence support (à la *yacc*, *bison*) - ✔ - A performance-oriented regex lexer (based on doctrine/lexer) - ✔ - An option to generate a hybrid recursive ascent parser - □ 1.0 --- - Compute reduction lookahead by the channel algorithm from *yacc* instead of the current LALR-by-SLR algorithm - ✔ - Change the analyzer API to allow for grammar debugging (provide access to resolved conflicts, dumping the automaton to DOT ...) - ✔ - Provide classes for dumping the parse table to PHP (both the dev & prod version) - ✔ bin/dissect000064400000000074146412213010006670 0ustar00#!/usr/bin/env php run(); composer.json000064400000003032146412213010007256 0ustar00{ "name": "goaop/dissect", "description": "A set of tools for lexical and syntactical analysis written in pure PHP", "version": "3.0.0", "type": "library", "homepage": "https://github.com/goaop/dissect", "license": "MIT", "authors": [ { "name": "Jakub Lédl", "email": "jakubledl@gmail.com", "homepage": "https://github.com/jakubledl" }, { "name": "WalterWoshid", "email": "wotschel.valentin@googlemail.com", "homepage": "https://github.com/WalterWoshid" } ], "keywords": [ "lexing", "parsing", "ast", "parser" ], "bin": [ "bin/dissect.php", "bin/dissect" ], "scripts": { "test": "phpunit", "test-coverage": "phpunit --coverage-html tests/coverage" }, "require": { "php": "^8.2.0" }, "require-dev": { "phpunit/phpunit": "^11.0.3", "rector/rector": "^1.0", "symfony/console": ">=6.0" }, "suggest": { "symfony/console": "for the command-line tool" }, "autoload": { "psr-4": { "Dissect\\": [ "src/" ] } }, "autoload-dev": { "psr-4": { "Dissect\\": [ "tests/" ] } }, "minimum-stability": "stable", "extra": { "branch-alias": { "dev-master": "3.0-dev" } }, "config": { "sort-packages": true } } docs/ast.md000064400000007447146412213010006613 0ustar00Building an AST =============== Often, when parsing a language that's more complex than [mathematical expressions][prev], you will want to represent the input as an *abstract syntax tree*, or AST (for a real-life example, see [Twig][twig-ast] or [Gherkin][gherkin-ast]). Getting the AST of the input with Dissect is nothing special; the callbacks in your grammar can return anything, so they might as well return AST nodes. Dissect however helps you by providing a simple base class for the different node types: `Dissect\Node\CommonNode`. Let's say we want to create an AST for the mathematical expressions from the previous chapter. Since the input can consist of binary operations and integers, let's create a subclass for each case: ```php use Dissect\Node\CommonNode; use Dissect\Node\Node; class BinaryExpressionNode extends CommonNode { const PLUS = 1; const TIMES = 2; const POWER = 3; public function __construct(Node $left, $op, Node $right) { parent::__construct(['operator' => $op], [ 'left' => $left, 'right' => $right, ]); } public function getLeft() { return $this->getNode('left'); } public function getRight() { return $this->getNode('right'); } public function getOperator() { return $this->getAttribute('operator'); } } class IntNode extends CommonNode { public function __construct($value) { parent::__construct(['value' => $value]); } public function getValue() { return $this->getAttribute('value'); } } ``` The original constructor has two parameters, an array of child nodes and an array of node attributes. `Dissect\Node\Node` is an interface describing common operations for an AST node. We can now easily modify the original grammar to build the AST: ```php $this('Additive') ->is('Additive', '+', 'Multiplicative') ->call(function ($l, $_, $r) { return new BinaryExpressionNode($l, BinaryExpressionNode::PLUS, $r); }) ->is('Multiplicative'); $this('Multiplicative') ->is('Multiplicative', '*', 'Power') ->call(function ($l, $_, $r) { return new BinaryExpressionNode($l, BinaryExpressionNode::TIMES, $r); }) ->is('Power'); $this('Power') ->is('Primary', '**', 'Power') ->call(function ($l, $_, $r) { return new BinaryExpressionNode($l, BinaryExpressionNode::POWER, $r); }) ->is('Primary'); $this('Primary') ->is('(', 'Additive', ')') ->call(function ($_, $e, $_) { return $e; }) ->is('INT') ->call(function ($int) { return new IntNode((int)$int->getValue()); }); ``` Traversing the AST ------------------ When we have the AST of our input, we want to interpret it somehow. The most common way to do this is to create a *node visitor* (sometimes called a *tree walker*). A trivial node visitor for our example could be the following recursive function: ```php function visit(Node $node) { if ($node instanceof BinaryExpressionNode) { switch ($node->getOperator()) { case BinaryExpressionNode::PLUS: return visit($node->getLeft()) + visit($node->getRight()); case BinaryExpressionNode::TIMES: return visit($node->getLeft()) * visit($node->getRight()); case BinaryExpressionNode::POWER: return pow(visit($node->getLeft()), visit($node->getRight()); } } elseif ($node instanceof IntNode) { return $node->getValue(); } else { throw new \Exception("Unknown node type."); } } echo visit($parser->parse(...)); ``` [prev]: parsing.md#example-parsing-mathematical-expressions [twig-ast]: https://github.com/fabpot/Twig/tree/master/lib/Twig/Node [gherkin-ast]: https://github.com/Behat/Gherkin/tree/master/src/Behat/Gherkin/Node docs/cli.md000064400000005620146412213010006562 0ustar00The command-line interface ========================== Dissect provides you with a command-line tool for processing and debugging your grammars. This chapted describes the tool and its options. Running the tool ---------------- Let's assume that the executable is located in a folder called `bin`. The most basic way to invoke it is $ bin/dissect This will analyze the given grammar and, if successful, save the parse table in a file `parse_table.php` in the same folder where you've defined your grammar. You can use `/` instead of `\` as the namespace separator or enclose the class name in quotes. To change the directory in which the parse table will be saved, use the `--output-dir` (or `-o`) option: $ bin/dissect --output-dir=../dir Dumping the parse table in the debug format ------------------------------------------- By default, the parse table will be saved as a single line of PHP code, with minimal whitespace. If you want to inspect the generated table manually, you can use the `--debug` (or `-d`) option: $ bin/dissect --debug The parse table will then be written in a human-readable way and with comments explaining the steps of the parser. Dumping the handle-finding automaton ------------------------------------ If you have an understanding of the LR parsing process, being able to inspect the LR automaton visually could be an aid in resolving potential grammar conflicts. In order to dump the automaton as a Graphviz graph, use the `--dfa` (or `-D`) option: $ bin/dissect --dfa This will create a file called `automaton.dot` in the output directory. You can then run something like dot -Tpng automaton.dot > automaton.png to render it as a PNG image. Of course, for more complex grammars, the automaton will quickly become rather large and unwieldy. You can then use the `--state` (or `-s`) option to dump only the specified state: $ bin/dissect --dfa --state=5 As an example, let's say we use the following grammar: ```php class PalindromeGrammar extends Grammar { public function __construct() { $this('S') ->is('a', 'S', 'a') ->is('b', 'S', 'b') ->is(/* empty */); $this->start('S'); } } ``` When running the command-line tool, we'll notice a list of resolved conflicts in the output: Resolved a shift/reduce conflict in state 2 on lookahead a Resolved a shift/reduce conflict in state 3 on lookahead b If we wanted to examine the conflict in state 3, we could run $ bin/dissect PalindromeGrammar --dfa --state=3 and then $ dot -Tpng state_3.dot > state_3.png The result will be the following image: ![State 3](https://raw.github.com/jakubledl/dissect/develop/docs/state_3.png) in which we can clearly see how the conflict arose: the state #3 calls both for a shift and a reduction by the rule `S -> ` on lookahead `b`. docs/common.md000064400000006735146412213010007313 0ustar00Describing common syntactic structures ====================================== This chapter of the documentation shows how to implement common grammar patterns like lists & repetitions in a way that's most efficient for a LALR(1) parser like Dissect. List of 1 or more `Foo`s ------------------------ ```php $this('Foo+') ->is('Foo+', 'Foo') ->call(function ($list, $foo) { $list[] = $foo; return $list; }) ->is('Foo') ->call(function ($foo) { return [$foo]; }); ``` With some practice, it's very easy to see how this works: when the parser recognizes the first `Foo`, it reduces it to a single-item array and for each following `Foo`, it just pushes it onto the array. Note that `Foo+` is just a rule name, it could be equally well called `Foos`, `ListOfFoo` or anything else you feel like. List of 0 or more `Foo`s ------------------------ ```php $this('Foo*') ->is('Foo*', 'Foo') ->call(function ($list, $foo) { $list[] = $foo; return $list; }) ->is(/* empty */) ->call(function () { return []; }); ``` This works pretty much the same like the previous example, the only difference being that we allow `Foo*` to match nothing. A comma separated list ---------------------- The first example of this chapter is trivial to modify to include commas between the `Foo`s. Just change the second line to: ```php $this('Foo+') ->is('Foo+', ',', 'Foo') ... ``` The second example, however, cannot be modified so easily. We cannot just put a comma in the first alternative: ```php $this('Foo*') ->is('Foo*', ',', 'Foo') ... ``` since that would allow the list to start with a comma: , Foo , Foo , Foo Instead, we say that a "list of zero or more `Foo`s separated by commas" is actually "a list of one or more `Foo`s separated by commas or nothing at all". So our rule now becomes: ```php $this('Foo*') ->is('Foo+') ->is(/* empty */) ->call(function () { return []; }); $this('Foo+') ->is('Foo+', ',', 'Foo') ... ``` A note on left recursion ------------------------ One of the principal advantages of LR parsers over alternatives like LL or recursive descent is the ability to handle left-recursive rules, which are a natural expression of many grammar patterns. However, not only do LR parsers handle left recursion, they actually work *better* with left-recursive rules than with right-recursive ones in terms of memory, since a left-recursive rule can be recognized using a constant amount of memory, whereas for right-recursive rules, the amount of memory required grows lineary with each round of recursion. You may have noticed that all the examples above use left recursion for two reasons: efficiency and naturalness (you read arrays from left to right, not the other way around, right?). In short, when you *can* comfortably express your rule using left recursion, *do* so. Expressions ----------- A grammar for very basic mathematical expressions is described in the [chapter on parsing][arith]. It would require some modifications to allow for other operators, function calls, ternary operator(s), but there's a lot of grammars for practical programming languages on the internet that you can take inspiration from. For a familiar (although slighty less readable) example, take a look at [this grammar][php-grammar] for PHP itself. [php-grammar]: https://github.com/php/php-src/blob/master/Zend/zend_language_parser.y [arith]: parsing.md#example-parsing-mathematical-expressions docs/index.md000064400000003433146412213010007122 0ustar00Welcome to Dissect! =================== Dissect is a set of tools for lexical and syntactical analysis written in pure PHP. This guide assumes that you're already familiar with basic concepts of parsing. Explaining them is beyond the scope of this simple guide, so if you're not, see, for example, [this article][parsing]. This page serves as an index for individual documentation pages. 1. [Lexical analysis with Dissect](lexing.md) 1. [SimpleLexer](lexing.md#simplelexer) 2. [StatefulLexer](lexing.md#statefullexer) 3. [Improving lexer performance](lexing.md#improving-lexer-performance) 4. [RegexLexer](lexing.md#regexlexer) 2. [Parsing with Dissect](parsing.md) 1. [Why an LALR(1) parser?](parsing.md#why-an-lalr1-parser) 2. [Writing a grammar](parsing.md#writing-a-grammar) 3. [Example: Parsing mathematical expressions](parsing.md#example-parsing-mathematical-expressions) 4. [Invalid input](parsing.md#invalid-input) 5. [Precomputing the parse table](parsing.md#precomputing-the-parse-table) 6. [Resolving conflicts](parsing.md#resolving-conflicts) 3. [Building an AST](ast.md) 1. [Travesing the AST](ast.md#traversing-the-ast) 4. [Describing common syntactic structures](common.md) 1. [List of 1 or more `Foo`s](common.md#list-of-1-or-more-foos) 2. [List of 0 or more `Foo`s](common.md#list-of-0-or-more-foos) 3. [A comma separated list](common.md#a-comma-separated-list) 4. [Expressions](common.md#expressions) 5. [The command-line interface](cli.md) 1. [Running the tool](cli.md#running-the-tool) 2. [Dumping the parse table in the debug format](cli.md#dumping-the-parse-table-in-the-debug-format) 3. [Dumping the handle-finding automaton](cli.md#dumping-the-handle-finding-automaton) [parsing]: http://en.wikipedia.org/wiki/Parsing docs/lexing.md000064400000015624146412213010007306 0ustar00Lexical analysis with Dissect ============================= There are three classes for lexical analysis in Dissect, all under the namespace `Dissect\Lexer`: `SimpleLexer`, `StatefulLexer` and `RegexLexer`. SimpleLexer ----------- `SimpleLexer` simply accepts some token definitions and applies them on the input. Let's create a subclass for this chapter: ```php use Dissect\Lexer\SimpleLexer; class ArithLexer extends SimpleLexer { public function __construct() { // token definitions } } ``` ### Defining tokens There are 3 ways to define a token. The simplest one looks like this: ```php $this->token('+'); ``` This definition will simply match a plus symbol, using `+` both as the name and value of the token. You can use 2 arguments: ```php $this->token('CLASS', 'class'); ``` if you want the token name (first argument) to differ from what will actually be recognized (second argument). The final way defines a token by a regular expression: ```php $this->regex('INT', '/^[1-9][0-9]*/'); ``` Let's now define some tokens we will use in the next chapter: ```php class ArithLexer extends SimpleLexer { public function __construct() { $this->regex('INT', '/^[1-9][0-9]*/'); $this->token('('); $this->token(')'); $this->token('+'); $this->token('*'); $this->token('**'); } } ``` > **Tip**: You can also chain the method calls using a fluent interface. ### Skipping tokens Some tokens have to be recognized, but we don't want them cluttering the output. The best example are probably whitespace tokens: the lexer has to recognize them, but they carry no meaning or value, so we can tell the lexer to `skip` them: ```php class ArithLexer extends SimpleLexer { public function __construct() { $this->regex('INT', '/[1-9][0-9]*/'); $this->token('('); $this->token(')'); $this->token('+'); $this->token('*'); $this->token('**'); $this->regex('WSP', "/^[ \r\n\t]+/"); $this->skip('WSP'); } } ``` > You can pass any number of token names to the `skip` method. ### Lexing Now that we've defined our tokens, we can simply call: ```php $lexer = new ArithLexer(); $stream = $lexer->lex($input); ``` The return value is an object implementing the `Dissect\Lexer\TokenStream\TokenStream` interface. The interface defines several methods you can use to inspect and move through the token stream. See [TokenStream.php][tokenstream] for all the methods you can use. > If you `count` the token stream, you may be surprised to find out that > for input like `5 + 3`, it actually contains 4 tokens. That's because, > as the last step of lexing, a special token called `$eof` is appended > to mark the end of input. This is crucial to the parsing process, so > please, never define a token called `$eof` yourself. It could lead to > some pretty strange errors. Another forbidden token names are `$start` > and `$epsilon`. StatefulLexer ------------- `SimpleLexer` should work fine for general use cases. However, let's imagine we're lexing a very simple templating language: Outer content, {{ variable_name }}, other outer content `SimpleLexer` falls short here, because the outer content can be pretty much anything, while the content inside the tags has to be strictly intepreted. Furthermore, if we were to work with this template, we'd want to skip the whitespace inside tags, but keep it in the outer content. That's where `StatefulLexer` comes in; during lexing, it maintains a stack of states with the top one being the current one, and for each token, you can define the action the lexer should take after recognizing it. Let's see an example for our templating language: ```php use Dissect\Lexer\StatefulLexer; class TemplateLexer extends StatefulLexer { public function __construct() { $lexer->state('outside') ->regex('CONTENT', '/^[^"{{"]*/') ->token('{{')->action('tag'); $lexer->state('tag') ->regex('WSP', "/^[ \r\n\t]+/") ->regex('VAR', '/^[a-zA-Z_]+/') ->token('}}')->action(StatefulLexer::POP_STATE) ->skip('WSP'); $lexer->start('outside'); } } ``` Please note that before defining any tokens, we have to define a state. For the tokens that cause the state transition, we call `action` to specify what should the lexer do. The action can be either a string, in which case the lexer goes to the state specified by the string, or `StatefulLexer::POP_STATE`, which causes the lexer to pop the current state of the stack, essentialy going back to previous state. Finally, we tell the lexer in which state to start by calling `start`. Improving lexer performance --------------------------- There's one important trick to improve the performance of your lexers. The documentation uses it implicitly, but it requires an explicit mention: When using one of the lexer classes documented above and defining tokens using regular expressions, *always* anchor the regex at the beginning using `^` like this: ```php $this->regex('INT', '/^[1-9][0-9]*/'); ``` This little optimization will lead to substantial performance gains on any but the shortest input strings, since without anchoring, the PCRE engine would always look for matches throughout the entire remaining input string, which would be incredibly wasteful for long inputs. RegexLexer ---------- When designing the lexer classes, my goal was not to sacrifice user-friendliness for performance. However, I'm well aware that there are use cases that require the highest performace possible. That's why I adapted the highly performant but slightly less user-friendly [lexer][doctrinelexer] from [doctrine][doctrine] into Dissect. The usage is almost identical to the original class, writing a lexer for the arithmetic expressions could look something like this: ```php use Dissect\Lexer\RegexLexer; use RuntimeException; class ArithLexer extends RegexLexer { protected $tokens = ['+', '*', '**', '(', ')']; protected function getCatchablePatterns() { return ['[1-9][0-9]*']; } protected function getNonCatchablePatterns() { return ['\s+']; } protected function getType(&$value) { if (is_numeric($value)) { $value = (int)$value; return 'INT'; } elseif (in_array($value, $this->tokens)) { // the types of the simple tokens equal their values here return $value; } else { throw new RuntimeException(sprintf('Invalid token "%s"', $value)); } } } ``` Continue -------- Now that we've demonstrated how to perform lexical analysis with Dissect, we can move onto syntactical analysis, commonly known as [parsing][parsing]. [tokenstream]: ../src/Lexer/TokenStream/TokenStream.php [parsing]: parsing.md [doctrinelexer]: https://github.com/doctrine/lexer/blob/master/lib/Doctrine/Common/Lexer/AbstractLexer.php [doctrine]: https://github.com/doctrine/lexer docs/parsing.md000064400000032104146412213010007453 0ustar00Parsing with Dissect ==================== Why an LALR(1) parser? ---------------------- Parsing is a task that's needed more often than one would think; for examples in some famous PHP projects, see [this parser][twigparser] from [Twig][twig] and [these][annotationsparser] [two][dqlparser] from [Doctrine][doctrine]. Chances are you've written one; if you did, it was most likely a [recursive descent parser][rdparser], just like the examples above. Now, such parsers have several disadvantages: first, they obviously have to be manually written. Second, they're *recursive*, which means one thing: nest the input deep enough (like an annotation, which has another annotation as a parameter, that annotation has another annotation as a parameter ...) and your PHP process blows up because of stack overflow (to be fair, you'd have to nest pretty deep). And third, such parsers belong to a class of parsers known as [LL(k)][llk], which means they're generally not as powerful as [LR(k)][lrk] parsers. For instance, they cannot handle left-recursive rules (rules like `A -> A ...`), which are probably the only sane way of expressing left-associative binary operators (like addition, for example). But let's get to actually parsing something. Writing a grammar ----------------- A grammar is represented by a subclass of `Dissect\Parser\Grammar`. ```php use Dissect\Parser\Grammar; class ArithGrammar extends Grammar { public function __construct() { // rule definitions } } ``` First, you tell Dissect what rule are you describing. Let's say we want to describe a rule for a `Sum`: ```php $this('Sum') ``` and then you specify what the rule actually `is`: ```php $this('Sum') ->is('int', '+', 'int'); ``` A rule can of course have many alternatives: ```php $this('Sum') ->is('int', '+', 'int') ->is('string', '+', 'string'); ``` and you will probably want to specify how to evalute the rule: ```php $this('Sum') ->is('int', '+', 'int') ->call(function ($l, $_, $r) { return $l + $r; }) ->is('string', '+', 'string') ->call(function ($l, $_, $r) { return $l . $r; }); ``` > The number of arguments to the callback function is always equal > to the length of the rule to which it belongs. ### Empty rules A grammar can (and many times will) contain empty rules, that is, rules that can match 0 tokens of the input. This is useful when, for example, describing a list of function arguments, which can be either empty or a list of values separated by commas. An empty rule is defined simply by calling `is` with 0 arguments: ```php $this('Empty') ->is(); ``` If you find this notation unclear, you can explicitly mark empty rules with a comment: ```php $this('Empty') ->is(/* empty */); ``` > **Beware:** When you don't specify a callback for a rule, Dissect > will default to returing the leftmost (first) component of the rule. You > are, however, required to specify a callback for an empty rule, since > in a rule with zero components, there is obviously no leftmost one. Example: Parsing mathematical expressions ----------------------------------------- In the chapter on lexing, we've created a lexer we will now use to process our expressions: ```php class ArithLexer extends SimpleLexer { public function __construct() { $this->regex('INT', '/^[1-9][0-9]*/'); $this->token('('); $this->token(')'); $this->token('+'); $this->token('*'); $this->token('**'); $this->regex('WSP', "/^[ \r\n\t]+/"); $this->skip('WSP'); } } $lexer = new ArithLexer(); ``` As for the grammar, let's start out slow, with only a single operator: ```php $this('Expr') ->is('Expr', '+', 'Expr') ->call(function ($l, $_, $r) { return $l + $r; }) ->is('INT') ->call(function ($i) { return (int)$i->getValue(); }); $this->start('Expr'); ``` These two rule specify an expression to be either two expression separated by a plus or simply an integer. The call to `start()` sets the starting rule of the grammar. Now, we can simply pass the grammar to a parser object: ```php use Dissect\Parser\LALR1\Parser; $parser = new Parser(new ArithGrammar()); $stream = $lexer->lex('1 + 2 + 3'); echo $parser->parse($stream); // => 6 ``` and yay, it works! ### Operator associativity Actually, it doesn't. It *seems* to work because addition happens to be commutative, but a problem appears once we add another rule to the grammar to represent subtraction: ```php $this('Expr') ->is('Expr', '+', 'Expr') ... ->is('Expr', '-', 'Expr') ->call(function ($l, $_, $r) { return $l - $r; }) ->is('INT') ... ``` The result looks like this: ```php $stream = $lexer->lex('3 - 5 - 2'); echo $parser->parse($stream); // => 0 ``` Well, that's certainly incorrect. The problem is that our grammar actually contains a conflict (a *shift/reduce* conflict, if you're a fan of termini technici. See the [section on conflict resolution](#resolving-conflicts).) which Dissect automatically resolves in a way that makes our `+` and `-` operators right-associative. The problem is fortunately easy to solve: we have to mark them as left-associative operators: ```php ->is('INT') ... $this->operators('+', '-')->left(); ``` This makes Dissect treat the two tokens in a special way, the conflict is resolved to represent left-associativity and the parser works correctly: ```php $stream = $lexer->lex('3 - 5 - 2'); echo $parser->parse($stream); // => -4 ``` ### Operator precedence Unfortunately, we're not out of the woods yet. When we add another two rules to represent multiplication and division, we see that the parser still makes mistakes: ```php $this('Expr') ... ->is('Expr', '*', 'Expr') ->call(function ($l, $_, $r) { return $l * $r; }) ->is('Expr', '/', 'Expr') ->call(function ($l, $_, $r) { return $l / $r; }) ... $this->operators('*', '/')->left(); ... $stream = $lexer->lex('2 + 3 * 5'); echo $parser->parse($stream); // => 25 ``` The problem is that Dissect doesn't know anything about the precedence of our operators. But we can, of course, provide the necessary information: ```php $this->operators('+', '-')->left()->prec(1); $this->operators('*', '/')->left()->prec(2); ... $stream = $lexer->lex('2 + 3 * 5'); echo $parser->parse($stream); // => 17 ``` The higher the integer passed to the `prec()` method, the higher the precedence of the specified operators. And we have the basic grammar for mathematical expressions in place! As an exercise, try to handle the rest of the tokens defined in the lexer: - Create a rule to handle parentheses around expressions. - Create a rule for the final operator, `**`, which represents exponentiation. Give it the highest precedence and make it *right-associative* (the method is, shockingly, called `right()`). ### Specifying precedences on rules instead of operators As a final touch, we'd like to add a unary minus operator to our grammar: ```php $this('Expr') ... ->is('-', 'Expr') ->call(function ($_, $e) { return -$e; }) ... ``` But you might feel that something is amiss. Unary minus should have the highest precedence, but we've specified the precedence of `-` to be the lowest, actually. But don't worry, we can assign precedences directly to rules: ```php $this('Expr') ... ->is('-', 'Expr')->prec(4) // higher than everything ->call(function ($_, $e) { return -$e; }) ... ``` ### Nonassociativity Apart from being left- or right-associative, operators can be nonassociative, which means that for an operator `op`, the input `a op b op c` means neither `(a op b) op c` or `a op (b op c)`, but is considered a syntax error. This has certain use cases; for instance, one of the nonassociative operators in the grammar for PHP is `<`: when parsing `1 < 2 < 3`, the PHP parser reports a syntax error. The corresponding method in Dissect grammars is `nonassoc()`: ```php $this->operators('<', '>')->nonassoc()->prec(...); ``` ### Describing common syntactic structures To see how to describe commonly used syntactic structures such as repetitions and lists, see the [dedicated documentation section][common]. Invalid input ------------- When the parser encounters a syntactical error, it stops dead and throws a `Dissect\Parser\Exception\UnexpectedTokenException`. The exception gives you programmatic access to information about the problem: `getToken()` returns a `Dissect\Lexer\Token` representing the invalid token and `getExpected()` returns an array of token types the parser expected to encounter. Precomputing the parse table ---------------------------- The parser needs a *parse table* to decide what to do based on given input. That parse table is created from the grammar and, if we give the parser only the grammar, needs to be computed every time we instantiate the parser. Grammar analysis is costly; if you need the speed, a far better choice would be to precompute the table beforehand (perhaps as a part of your build process) like this: ```php use Dissect\Parser\LALR1\Analysis\Analyzer; $analyzer = new Analyzer(); $parseTable = $analyzer->analyze($grammar)->getParseTable(); ``` Now that we've got the parse table, we can dump it to a string which we then save to a file. To do this, we can use either `Dissect\Parser\LALR1\Dumper\ProductionTableDumper`: ```php $dumper = new ProductionTableDumper(); $php = $dumper->dump($parseTable); ``` which produces very compact, whitespace-free and absolutely unreadable code, or `Dissect\Parser\LALR1\Dumper\DebugTableDumper`: ```php $dumper = new DebugTableDumper($grammar); $php = $dumper->dump($parseTable); ``` which produces indented, readable representation with comments explaining each step the parser takes when processing the input. ### Using the dumped parse table To use the dumped parse table, just write ```php $parser = new Parser($grammar, require $parseTableFile); ``` You still need to pass the grammar, since it contains the callbacks used to evalute the input. > If you intend to use Dissect more like a traditional parser generator, > you don't actually need to do any of this, of course. Dissect provides a > command-line interface you can use to process and debug your grammars. > It's described in its own [documentation section][cli]. Resolving conflicts ------------------- *Caution, this is advanced stuff. You probably won't ever need to worry about this.* LALR(1) is generally a very poweful parsing algorithm. However, there are practical grammars that are, unfortunately, almost-but-not-quite LALR(1). When running an LALR(1) analyzer on such grammars, one sees that they contain 2 types of conflicts: - **Shift/Reduce conflicts** - the parser doesn't know whether to shift another token or reduce what's on the stack. - **Reduce/Reduce conflicts** - the parser can reduce by multiple grammar rules. There are 4 commonly used ways of resolving such conflicts and Dissect allows you to combine them any way you want: 1. On a shift/reduce conflict, consult the operators precedence and associativity information. The rules for resolution are a little complicated, but the conflict may be resolved as a reduce (either the precedence of the rule is higher than that of the shifted token or the token is left-associative), a shift (the rule precedence is lower or the token is right-associative) or even as an error (when the token is nonassociative). Note that Dissect doesn't report conflicts resolved using this technique, since they were intentionally created by the user and therefore are not really conflicts. Represented by the constant `Grammar::OPERATORS`. 2. On a shift/reduce conflict, always shift. This is represented by the constant `Grammar::SHIFT` and, together with the above method, is enabled by default. 3. On a reduce/reduce conflict, reduce using the longer rule. Represented by `Grammar::LONGER_REDUCE`. Both this and the previous way represent the same philosophy: take the largest bite possible. This is usually what the user intended to express. 4. On a reduce/reduce conflict, reduce using the rule that was declared earlier in the grammar. Represented by `Grammar::EARLIER_REDUCE`. To specify precisely how should Dissect resolve parse table conflicts, call `resolve` on your grammar: ```php $this->resolve(Grammar::SHIFT | Grammar::OPERATORS | Grammar::LONGER_REDUCE); ``` There are two other constants: `Grammar::NONE` that forbids any conflicts in the grammar (even the operators-related ones) and `Grammar::ALL`, which is a combination of all the 4 above methods defined simply for convenience. [twigparser]: https://github.com/fabpot/Twig/blob/master/lib/Twig/Parser.php [twig]: https://github.com/fabpot/Twig [annotationsparser]: https://github.com/doctrine/common/blob/master/lib/Doctrine/Common/Annotations/DocParser.php [dqlparser]: https://github.com/doctrine/doctrine2/blob/master/lib/Doctrine/ORM/Query/Parser.php [doctrine]: https://github.com/doctrine [rdparser]: http://en.wikipedia.org/wiki/Recursive_descent_parser [llk]: http://en.wikipedia.org/wiki/LL_parser [lrk]: http://en.wikipedia.org/wiki/LR_parser [cli]: cli.md [common]: common.md docs/state_3.png000064400000036340146412213010007544 0ustar00PNG  IHDRKnbKGD IDATxw\SOv3B@r "SeBq -8X jW+uU*(ZŁ" )!rsOr_{r((x@ R*Qd!E*Qd!E*Qd߾}gkkk@n·SԮ.0l;d1p*2 OaX+Ν;7oD* kWTT<~fIIIXϰ~gҥK'O>~A (3`b2PᠻL&S(N@PfX#̰vAps@PP֎@ 3L҉D"IIIqppSVV2~A (3L'|cǎ>7D!}82L}82L @pD!b6477644X,sss"q~fx]uuuqqqgϞN>}z@@ٳxhQ˥ֶe33={_|ɓ'7nylmm]Jp#FؿGGyyysp-jkkPPOOӧO sʵkn޼/m!O.\^|ׅ7իW\.ӳRB RE[n}w{///{ PXWVVN>=>> .UUUvvvΝC=D6(¹\i*++?.ᖒ۷oϘ1 .D=Df(ccc/^SGGGɭ]6..HSSSrk,Q@7775*$$$&&---f:r*!c{ehTUU_?^XXMD6(Zlݺu(r$ Z Q>̙3x<~ʕp?s粳/^d]]] 6t+@Evp'N̟?_EEEOp _~)%ޫVN t@BAAQg2{ACQxVVք #J?7rG! TP/ϟ?;wkkk9NKK Fh4 4rH===%%%GEEرlp onn...0aB߿+))))))..f2555]]]TSS7773f̘1cFmggw9J]n]CCA#rjo„ #FKNN)q !!!qqq/_622ڶm/0[ꦦW^4immݴiL{@ׯ_R([cTxԩSq8˛v2,^,k$ãkw絴LLL޽/c+++}:fggL݁(2x߰a@8q RTUUVH]ׯ'+R$!#E,[D"]tIz(*l6ohiiiXHQ۶mqqqҫBaXXHk>ɓGYb4X,̙3 233?HE቉;vؼy3ƇSN}|c'NpԸ1t*; vrr7nׅ7bggg??X} %\>sL $(ot3fLrr_O?a d(###UUUQ4 Apww矣o߾/!jO鱱-~3P1Khh۷_z/!: ꕫuv)5:;;'NHR322`4Ƞ'*++gdd2rCׯx?eeeL&dVVVVWW:'3 SSS g@PPxddd\\ܫWLMMQ 2(>|ꊵ/C6SXXXQQ|` 4Ӄkjj***8N__JfCђ*<55:wIRRRSPP㝜&O|ϟˠGZݻwǏ*oAAAnn.Ǐgfffdddeedkkk{{{{{{333CCCccc&aEeee~e~~>RVV8q *$K^͛'YQ?BBB޿֖rJdϹ .))_6lA|񣦦e˰r`QZZziӦQ(1c,Xpї/_X,Օ}ȑQF(:d2QDXt)F!111S#wo7777nP;BͶmېx!$x=w\PP:a8p*W'OxsPFHTٳg5k_ڥ Y(JBBH̙3d !󾾾D"QUU5<<<--Mn(h"痚J]1bfΜ)b`ggWXzyyy !H#F _}JJJGȁLn}(//WVV駟vD`X?k̙3nnnIxWS+J-))nr *EP.]Z\\ܧ@!:^VVqe_ݿXuuNPPP}}-[|G <-O?TZZÉ366&ϟ?#ʚ7oH4119{9QxCCN_~xU.]@ X)=[j //"3|tvv޻wYUn:4&: ̹s玝@XxFd '⥲GVՕ'?~ȬƂ xx:t֖u)fddgN hkk&qHNN ۠n A|___@XXo$HHDVxaa!Hާ|nhh LKK AƳgp8իWvDvp8͛7pŋ755a,SXXn._|DHCza2VVV?Dbo$ZSxb;w"޸qMwLPP0[ZZ|}})ʩSE?~L&{.cZ3//o7ӵkr}樨(di1S,;;@ H={4++Os)...))?~|``(H$ #33k_ÇӦM\RgeeRSS% Lr)ShjjN:ǽ YYY=|޺uHCC#44dΝ;WUU5::O1.`nn_\.w4baHoR޼B秡+}/^ ~eAeA\#RdݺuO<̤h筅UxII |2AH@@ ^HK.p8 KNggg⑐ӅUʕ+-,,`. [hrnEGG'44T#׮]suuUWWӧO߽{#Z ޽{W[ JTuuuuJ4ȑ#86X{>۷ot};r?Ó7hMթڵBm߾}ͨ86.\ H>|4imm[l{zz D:KH6nܨ3jԨN Aۺu+֎ɕ+Wx0w{{{NJ<`p/ܹኊDZDEE9RnC… %_cdžKc%<<,xiDa2x<^7.**JB#;}_Xr%֛7o/Dᵵd2( >>>~~~ҮEfCjjj'NV9·N: g嵄?~\CCA~1؆"$^zUlh# y 2쿈ucҤI(mmmǎ^MEOOJG,V߾} (r└cTTT(Hf޼yҳ/xh]LLL+9w 066%{4))IUUf̛7?~q-X`ʕUUUW\R]'IwÇ3f D"+Gɓ'˗/X!8@jj74 CBnرc͛d2_|9zh қV%%%#*@ \x-' 0k,<4">|ϟ7nܨN&-,,v)K0 sΑHE? ?PRRx 44-$===>|۷L@,X0j(EZƃ ]]]Ƌ-  h} df%Lё榪~xFF\E)((\tiHl6;11U8{//_>eeH1LJ76mbiax葯/377?x`CCFCCCLLp̻ƬgxݻF ^}||x9rx/rEAAAXXJP(AAAl6kfoܸHP %7WS("G ; 7n8"}Ν+ittt$''d#W"cbb|||h4L LNNFq&w9;;e]2 t&F0Txii)olܹv~Iz ~iӦd<ooof͚$|XxӧOΜ9?\xMi`fflٲ 6ȬF9>333+++///// @" MMM̌ pT*UIIgd2>l,٧OԔ{)ۨ>>}7~ޙk ; <<bҥK'O~H[JKK *Mi! ?:;; JJJT*ZZZ!U܋ٲK`0ͳ#yDu@2"|&G***d_P8B𭱼[EEۻ\&4طo̪`ĈFIDAT)J$zw==#G&N##4l6ATN=bWzT-,,dS!#))iĉT*USS3<<\k]&뀨|PTT$J!lƍo߾\ţ666Xwwwd\HCUՐ! p86 F ?.Ç)fC+0ȏ aE+W qy ÁN&#p0uXI$RRR444F_ٳg„ 2AlPÐbY^'N~||ȑ#߾}{ԩ[7!<¡E/[lq$PLŐs|RPP#S:Nojj뽏Ϛ5K>͐sXK?Uw7n+W0 CvÇSNUUU2?5kȑ#dfpppMM iVz oE:O2&L6:^VVqe_-BT*]:::$iĈAAA' g2@҃/] @XbE[[f O***AF~*J>iO$D0iÑEk>ۧO:dkk+@x0:[n}Ln[|v!i&gA6auww[FzJH)M<(6sLiXg***H P}]ޟH!qE@ᜐlݴiӾ} (&›󏹹96lM=_9s] IfPYYY]]]_ȋ`0ttt LMMMLLLLLp˘7{,:[jUƗ'O/_y!JI&kۖ|$INNNaa!Grr;IYY+**8N__ybeen$Aӽ.]*GEAAƌ`G|bƇ#G5 @PO~!)}i}~'T @zz:`AAAcǎUUU77UV:u˗b,% տ+NCC#88uuuXrΝ Br8p OII`E "=;bFFF FGG'''+===ׯ_%iii2Eb-ZHEED"Hn߽{x!r'''*++}}}uttz ~Æ \s҆bZ[[<<} pBzQxWWF;u}+W"Q~Z k!tC&d].\(zy]r%**NaÆ . Ӵ} HT*5::___ " U9~8Lf̂ߢgm3E(F0QxGGJ=s挌@sssFFǑx*J E8)));:: Fff&jjjN6;vHJ={lf͒j h& !---~0ψLRXXb444^zX uuun_m<R^]lggWXGl Oyy@;yFn߾=vXqb4Ax(k.CCCT$ lzpd2yԩOЀ,-JLLD GSΟ?_ڵH@¦P(%$$`\2P{3gΝ;W:^ )L&%%&OVD2 d29>>^H2]h4FCxW^}[n舴2?0Yf5_Ek ppp@ހ ?t萚 %[" M۸ 3rj ]\\ܖ.]w+Woߎ" gpFA˲]~:`JKKCʼnAmEDbP(7ABbdgggV!Z[[t-[$12Gssq#dlݺ˗UUU>>>QFdA7nlooѣKB7a&I"$W❎D Gڭ-6W\nh{S G:>P޽SSS{ZmA@ /bD;w D!===T*YHs45}! r \{nTrqqqJJJC'%%%C>C{Jhd>]n`߾}O*-;@~~~ȧH [633n,^ի@䍄<#1nܸ, ij읦H$r{(MMbdd(ѿ'OpSN!3KKK> zohmmUUU=x Z7 pvv_s1&f0,ӧk׮Ol@"YSSӬ>Ugff<4GkkߑH斖/_>nܸ!Ir_xx!֎ɇx%12G]] O1.`nn_\.ϒU9< Beeep\!քXXX\zuA3̧Ob,\Džf3fӧ|,MWKԑn~Bk}ϒS^^N$%䓢""HÇoHwT+͛8N6o͜0dQOOOri4bLBnnP"^y===_|loV7RxSS4[beeSqܦ&KKK777D򒒒x 1 nr(1tAyyb7sPZZZ\]] >| W^OOCBB$m<߃BLፍ ܁xr<9͞zzz;wH,))n| &3ܹN֥X"k޽{ս}v¢]yl6IL%o"!zM6 UWW߹s+*++RSSEv1Y@6ވ|ݼy}y kQeˌHppI .\ ʛ6m̶g7^BllTk[o]]]==xpbccuuuǖ8W^vv6믿8WD7^sƈ`kk{MA+V"敷h")dAפk׮r~~~K. f'&&:;;,`0֬Y#ACIU--- LB=z<ЀGcff$̾(idn|:h5*|ƍVH ¨T*B JMM6}ƍ@ ^XX(Y<6&_U)333+++///// @" MMM̌ pT*UIIg XWWW___SSSWWW^^d2Ll6UKKKmT"K8p innvpp044LKK({ geeeuuuKKHvttt LMMMLLLMMͭH((pŠ .Kn "s>}իWX2,N$CJ /.<˗/OHHx򥩩)*!|9zhddݻw'O/!j okk8qjzz:rK΋/&Mv]va dh&LHJJ3 g„ Η/_!AB166|rJJ aP_[[ٳPAZqww߻wmx^ ӳtR&;X2(h#You֤IP? Yn]RRҍ7zg؂@寽Y`jvv4+oN$E 9֛iӦ>x\U N:tõk֘ JzɔR-͟yf(oHqTNyxx{Nz)${xx?sN} aӧOSNmhh}ѣZp鈈M6AyC$D3t:Ν;zzzҮNسgϒ%Ko A 赵͜9SUU5--M65E8Ndd$@8~8־@%dX~-L>y*B477S($}(xlٲgϞ9rD"ɬv9`֬YH [[[݁(^f͚/^pyI222!9sdff=yDg֭_}՗_~ahhGE]JǏvrr4i/•|RSS3mڴ}=zܹsHFehΨB?~\CCZ`x?tttzzzG,_|?;v,Ao1\.bmF"\\\&INp8񇦦 \ r-D"EGG?;::^ kP&;;uʕX{ȅlll222Μ9s% #GX,B%K899hׯ_8p@UUk "nڴIYY4..nfTرcv2G#TWWYBXXX?~kDd]VMMX{ȯ>|zje˖ =sscǎuuuadX# Gݲe N'~~~򖴼˛#@H{{{bbS222͛a/޸q@ .^+ > %(**KLL,))1223gϤId6F]VVvݛ7o޸qkʔ)AAAAAA$@0$#'''))ڵki... Ŋ\۷o={y޽R6yٳgϞ=[6!1 Q]]vΝ $ѣ̌z'v@CCCUUUiiKKKKJJ>}D&mll<==M0BQxoJJJJJJx+D /E[[jooG2wuup81c5LƬa(S[[d2kjj>~X]]][[pZZZl6RFQ(%%#G뛙ΰP82luu!E*QdfrQ{EIENDB`phpunit.xml000064400000000712146412213010006747 0ustar00 tests/ src/ rector.php000064400000002606146412213010006551 0ustar00withPaths([ __DIR__ . '/src', __DIR__ . '/tests', ]) // uncomment to reach your current PHP version // ->withPhpSets() ->withRules([ // Dead-code RemoveUselessParamTagRector::class, RemoveUselessReturnTagRector::class, RemoveUselessVarTagRector::class, PublicConstantVisibilityRector::class, ClosureToArrowFunctionRector::class, AddVoidReturnTypeWhereNoReturnRector::class, AddTestsVoidReturnTypeWhereNoReturnRector::class, // DeclareStrictTypesRector::class, ]) ->withSets([ PHPUnitSetList::ANNOTATIONS_TO_ATTRIBUTES, PHPUnitSetList::PHPUNIT_CODE_QUALITY, ]); src/Console/Application.php000064400000002536146412213010011711 0ustar00 */ class Application extends BaseApplication { // credit goes to everzet & kostiklv, since // I copied the BehatApplication class when // dealing with some CLI problems. public function __construct($version) { parent::__construct('Dissect', $version); } protected function getCommandName(InputInterface $input): string { return 'dissect'; } protected function getDefaultCommands(): array { $default = parent::getDefaultCommands(); $default[] = new Command\DissectCommand(); return $default; } public function getDefinition(): InputDefinition { return new InputDefinition([ new InputOption('--help', '-h', InputOption::VALUE_NONE, 'Display this help message.'), new InputOption('--verbose', '-v', InputOption::VALUE_NONE, 'Increase verbosity of exceptions.'), new InputOption('--version', '-V', InputOption::VALUE_NONE, 'Display version information.'), ]); } } src/Console/Command/DissectCommand.php000064400000016526146412213010013725 0ustar00setName('dissect') ->addArgument('grammar-class', InputArgument::REQUIRED, 'The grammar class.') ->addOption('debug', 'd', InputOption::VALUE_NONE, 'Writes the parse table in the debug format.') ->addOption('dfa', 'D', InputOption::VALUE_NONE, 'Exports the LALR(1) DFA as a Graphviz graph.') ->addOption('state', 's', InputOption::VALUE_REQUIRED, 'Exports only the specified state instead of the entire DFA.') ->addOption('output-dir', 'o', InputOption::VALUE_REQUIRED, 'Overrides the default output directory.') ->setHelp(<<--output-dir option: --output-dir=../some/other/dir The parse table is by default written with minimal whitespace to make it compact. If you wish to inspect the table manually, you can export it in a readable and well-commented way with the --debug option. If you wish to inspect the handle-finding automaton for your grammar (perhaps to aid with grammar debugging), use the --dfa option. When in use, Dissect will create a file with the automaton exported as a Graphviz graph in the output directory. Additionally, you can use the --state option to export only the specified state and any relevant transitions: --dfa --state=5 EOT ); } protected function execute(InputInterface $input, OutputInterface $output): int { $class = strtr( $input->getArgument('grammar-class'), '/', '\\' ); $formatter = $this->getHelperSet()->get('formatter'); $output->writeln('Analyzing...'); $output->writeln(''); if (!class_exists($class)) { /** @noinspection PhpPossiblePolymorphicInvocationInspection */ $output->writeln([ $formatter->formatBlock( sprintf('The class "%s" could not be found.', $class), 'error', true ), ]); return 1; } $grammar = new $class(); if ($dir = $input->getOption('output-dir')) { $cwd = rtrim(getcwd(), DIRECTORY_SEPARATOR); $outputDir = $cwd . DIRECTORY_SEPARATOR . $dir; } else { $refl = new ReflectionClass($class); $outputDir = pathinfo($refl->getFileName(), PATHINFO_DIRNAME); } $analyzer = new Analyzer(); try { $result = $analyzer->analyze($grammar); $conflicts = $result->getResolvedConflicts(); $automaton = $result->getAutomaton(); $table = $result->getParseTable(); if ($conflicts) { foreach ($conflicts as $conflict) { $output->writeln($this->formatConflict($conflict)); } $output->writeln(sprintf( "%d conflicts in total", count($conflicts) )); $output->writeln(''); } $output->writeln('Writing the parse table...'); $fileName = $outputDir . DIRECTORY_SEPARATOR . 'parse_table.php'; if ($input->getOption('debug')) { $tableDumper = new DebugTableDumper($grammar); } else { $tableDumper = new ProductionTableDumper(); } $code = $tableDumper->dump($table); $ret = @file_put_contents($fileName, $code); if ($ret === false) { $output->writeln('Error writing the parse table'); } else { $output->writeln('Parse table written'); } } catch(ConflictException $e) { /** @noinspection PhpPossiblePolymorphicInvocationInspection */ $output->writeln([ $formatter->formatBlock( explode("\n", $e->getMessage()), 'error', true ), ]); $automaton = $e->getAutomaton(); } if ($input->getOption('dfa')) { $output->writeln(''); $automatonDumper = new AutomatonDumper($automaton); if ($input->getOption('state') === null) { $output->writeln('Exporting the DFA...'); $dot = $automatonDumper->dump(); $file = 'automaton.dot'; } else { $state = (int)$input->getOption('state'); if (!$automaton->hasState($state)) { /** @noinspection PhpPossiblePolymorphicInvocationInspection */ $output->writeln([ $formatter->formatBlock( sprintf('The automaton has no state #%d', $state), 'error', true ), ]); return 1; } $output->writeln(sprintf( 'Exporting the DFA state %d...', $state )); $dot = $automatonDumper->dumpState($state); $file = sprintf('state_%d.dot', $state); } $fileName = $outputDir . DIRECTORY_SEPARATOR . $file; $ret = @file_put_contents($fileName, $dot); if ($ret === false) { $output->writeln('Error writing to the file'); } else { $output->writeln('Successfully exported'); } } return 0; } protected function formatConflict(array $conflict): string { $type = $conflict['resolution'] === Grammar::SHIFT ? 'shift/reduce' : 'reduce/reduce'; return sprintf( "Resolved a %s conflict in state %d on lookahead %s", $type, $conflict['state'], $conflict['lookahead'] ); } } src/Lexer/AbstractLexer.php000064400000004366146412213010011671 0ustar00 * @see \Dissect\Lexer\AbstractLexerTest */ abstract class AbstractLexer implements Lexer { private int $line = 1; /** * Returns the current line. */ protected function getCurrentLine(): int { return $this->line; } /** * Attempts to extract another token from the string. * Returns the token on success or null on failure. * * @param string $string The string to extract the token from. */ abstract protected function extractToken(string $string): ?Token; /** * Should given token be skipped? */ abstract protected function shouldSkipToken(Token $token): bool; /** * {@inheritDoc} */ public function lex(string $string): TokenStream { // normalize line endings $string = strtr($string, ["\r\n" => "\n", "\r" => "\n"]); $tokens = []; $position = 0; $originalString = $string; $originalLength = Util::stringLength($string); while (true) { $token = $this->extractToken($string); if ($token === null) { break; } if (!$this->shouldSkipToken($token)) { $tokens[] = $token; } $shift = Util::stringLength($token->getValue()); $position += $shift; // update line + offset if ($position > 0) { $this->line = substr_count($originalString, "\n", 0, $position) + 1; } $string = Util::substring($string, $shift); } if ($position !== $originalLength) { throw new RecognitionException($this->line); } $tokens[] = new CommonToken(Parser::EOF_TOKEN_TYPE, '', $this->line); return new ArrayTokenStream(...$tokens); } } src/Lexer/CommonToken.php000064400000001523146412213010011347 0ustar00 */ class CommonToken implements Token { /** * Constructor. * * @param mixed $type The type of the token. * @param int|string $value The token value. * @param int $line The line. */ public function __construct( protected mixed $type, protected int|string $value, protected int $line ) {} /** * {@inheritDoc} */ public function getType(): mixed { return $this->type; } /** * {@inheritDoc} */ public function getValue(): int|string { return $this->value; } /** * {@inheritDoc} */ public function getLine(): int { return $this->line; } } src/Lexer/Exception/RecognitionException.php000064400000001423146412213010015212 0ustar00 */ class RecognitionException extends RuntimeException { protected int $sourceLine; /** * Constructor. * * @param int $line The line in the source. */ public function __construct(int $line) { $this->sourceLine = $line; parent::__construct(sprintf("Cannot extract another token at line %d.", $line)); } /** * Returns the source line number where the exception occured. * * @return int The source line number. */ public function getSourceLine(): int { return $this->sourceLine; } } src/Lexer/Lexer.php000064400000001104146412213010010170 0ustar00 */ interface Lexer { /** * Lexes the given string, returning a token stream. * * @param string $string The string to lex. * * @throws RecognitionException When unable to extract more tokens from the string. */ public function lex(string $string): TokenStream; } src/Lexer/Recognizer/Recognizer.php000064400000001236146412213010013335 0ustar00 */ interface Recognizer { /** * Returns a boolean value specifying whether * the string matches or not and if it does, * returns the match in the second variable. * * @param string $string The string to match. * @param ?string $result The variable that gets set to the value of the match. * * @return boolean Whether the match was successful or not. */ public function match(string $string, ?string &$result = null): bool; } src/Lexer/Recognizer/RegexRecognizer.php000064400000001537146412213010014334 0ustar00 * @see \Dissect\Lexer\Recognizer\RegexRecognizerTest */ class RegexRecognizer implements Recognizer { protected string $regex; /** * Constructor. * * @param string $regex The regex to use in the match. */ public function __construct(string $regex) { $this->regex = $regex; } /** * {@inheritDoc} */ public function match(string $string, ?string &$result = null): bool { $r = preg_match($this->regex, $string, $match, PREG_OFFSET_CAPTURE); if ($r === 1 && $match[0][1] === 0) { $result = $match[0][0]; return true; } return false; } } src/Lexer/Recognizer/SimpleRecognizer.php000064400000001453146412213010014510 0ustar00 * @see \Dissect\Lexer\Recognizer\SimpleRecognizerTest */ class SimpleRecognizer implements Recognizer { protected string $string; /** * Constructor. * * @param string $string The string to match by. */ public function __construct(string $string) { $this->string = $string; } /** * {@inheritDoc} */ public function match(string $string, ?string &$result = null): bool { if (strncmp($string, $this->string, strlen($this->string)) === 0) { $result = $this->string; return true; } return false; } } src/Lexer/RegexLexer.php000064400000003741146412213010011174 0ustar00 * @author Jonathan Wage * @author Roman Borschel * @author Jakub Lédl * @see \Dissect\Lexer\RegexLexerTest */ abstract class RegexLexer implements Lexer { /** * {@inheritDoc} */ public function lex(string $string): TokenStream { static $regex; if (!isset($regex)) { $regex = '/(' . implode(')|(', $this->getCatchablePatterns()) . ')|' . implode('|', $this->getNonCatchablePatterns()) . '/i'; } $string = strtr($string, ["\r\n" => "\n", "\r" => "\n"]); $flags = PREG_SPLIT_NO_EMPTY | PREG_SPLIT_DELIM_CAPTURE | PREG_SPLIT_OFFSET_CAPTURE; $matches = preg_split($regex, $string, -1, $flags); $tokens = []; $line = 1; $oldPosition = 0; foreach ($matches as $match) { list ($value, $position) = $match; $type = $this->getType($value); if ($position > 0) { $line += substr_count($string, "\n", $oldPosition, $position - $oldPosition); } $oldPosition = $position; $tokens[] = new CommonToken($type, $value, $line); } $tokens[] = new CommonToken(Parser::EOF_TOKEN_TYPE, '', $line); return new ArrayTokenStream(...$tokens); } /** * The patterns corresponding to tokens. */ abstract protected function getCatchablePatterns(): array; /** * The patterns corresponding to tokens to be skipped. */ abstract protected function getNonCatchablePatterns(): array; /** * Retrieves the token type. */ abstract protected function getType(string &$value): string; } src/Lexer/SimpleLexer.php000064400000004636146412213010011357 0ustar00 * @see \Dissect\Lexer\SimpleLexerTest */ class SimpleLexer extends AbstractLexer { protected array $skipTokens = []; /** * @var SimpleRecognizer[] */ protected array $recognizers = []; /** * Adds a new token definition. If given only one argument, * it assumes that the token type and recognized value are * identical. * * @param string $type The token type. * @param string|null $value The value to be recognized. */ public function token(string $type, string $value = null): self { if ($value) { $this->recognizers[$type] = new SimpleRecognizer($value); } else { $this->recognizers[$type] = new SimpleRecognizer($type); } return $this; } /** * Adds a new regex token definition. * * @param string $type The token type. * @param string $regex The regular expression used to match the token. */ public function regex(string $type, string $regex): static { $this->recognizers[$type] = new RegexRecognizer($regex); return $this; } /** * Marks the token types given as arguments to be skipped. * * @param mixed $types Unlimited number of token types. */ public function skip(mixed ...$types): static { $this->skipTokens = $types; return $this; } /** * {@inheritDoc} */ protected function shouldSkipToken(Token $token): bool { return in_array($token->getType(), $this->skipTokens); } /** * {@inheritDoc} */ protected function extractToken(string $string): ?Token { $value = $type = null; foreach ($this->recognizers as $t => $recognizer) { if ($recognizer->match($string, $v)) { if ($value === null || Util::stringLength($v) > Util::stringLength($value)) { $value = $v; $type = $t; } } } if ($type !== null) { return new CommonToken($type, $value, $this->getCurrentLine()); } return null; } } src/Lexer/StatefulLexer.php000064400000012400146412213010011701 0ustar00 * @see \Dissect\Lexer\StatefulLexerTest */ class StatefulLexer extends AbstractLexer { protected array $states = []; protected array $stateStack = []; protected ?string $stateBeingBuilt = null; protected ?string $typeBeingBuilt = null; /** * Signifies that no action should be taken on encountering a token. */ public const NO_ACTION = 0; /** * Indicates that a state should be popped of the state stack on * encountering a token. */ public const POP_STATE = 1; /** * Adds a new token definition. If given only one argument, * it assumes that the token type and recognized value are * identical. * * @param string $type The token type. * @param string|null $value The value to be recognized. */ public function token(string $type, string $value = null): StatefulLexer { if ($this->stateBeingBuilt === null) { throw new LogicException("Define a lexer state first."); } if ($value === null) { $value = $type; } $this->states[$this->stateBeingBuilt]['recognizers'][$type] = new SimpleRecognizer($value); $this->states[$this->stateBeingBuilt]['actions'][$type] = self::NO_ACTION; $this->typeBeingBuilt = $type; return $this; } /** * Adds a new regex token definition. * * @param string $type The token type. * @param string $regex The regular expression used to match the token. */ public function regex(string $type, string $regex): AbstractLexer { if ($this->stateBeingBuilt === null) { throw new LogicException("Define a lexer state first."); } $this->states[$this->stateBeingBuilt]['recognizers'][$type] = new RegexRecognizer($regex); $this->states[$this->stateBeingBuilt]['actions'][$type] = self::NO_ACTION; $this->typeBeingBuilt = $type; return $this; } /** * Marks the token types given as arguments to be skipped. * * @param mixed $types Unlimited number of token types. */ public function skip(mixed ...$types): StatefulLexer { if ($this->stateBeingBuilt === null) { throw new LogicException("Define a lexer state first."); } $this->states[$this->stateBeingBuilt]['skip_tokens'] = $types; return $this; } /** * Registers a new lexer state. * * @param string $state The new state name. */ public function state(string $state): StatefulLexer { $this->stateBeingBuilt = $state; $this->states[$state] = [ 'recognizers' => [], 'actions' => [], 'skip_tokens' => [], ]; return $this; } /** * Sets the starting state for the lexer. * * @param string $state The name of the starting state. */ public function start(string $state): StatefulLexer { $this->stateStack[] = $state; return $this; } /** * Sets an action for the token type that is currently being built. * * @param mixed $action The action to take. */ public function action(mixed $action): StatefulLexer { if ($this->stateBeingBuilt === null || $this->typeBeingBuilt === null) { throw new LogicException("Define a lexer state and type first."); } $this->states[$this->stateBeingBuilt]['actions'][$this->typeBeingBuilt] = $action; return $this; } /** * {@inheritDoc} */ protected function shouldSkipToken(Token $token): bool { $state = $this->states[$this->stateStack[count($this->stateStack) - 1]]; return in_array($token->getType(), $state['skip_tokens']); } /** * {@inheritDoc} */ protected function extractToken(string $string): ?Token { if (empty($this->stateStack)) { throw new LogicException("You must set a starting state before lexing."); } $value = $type = $action = null; $state = $this->states[$this->stateStack[count($this->stateStack) - 1]]; foreach ($state['recognizers'] as $t => $recognizer) { /** @var string $t */ /** @var SimpleRecognizer|RegexRecognizer $recognizer */ if ($recognizer->match($string, $v)) { if ($value === null || Util::stringLength($v) > Util::stringLength($value)) { $value = $v; $type = $t; $action = $state['actions'][$type]; } } } if ($type !== null) { if (is_string($action)) { // enter new state $this->stateStack[] = $action; } elseif ($action === self::POP_STATE) { array_pop($this->stateStack); } return new CommonToken($type, $value, $this->getCurrentLine()); } return null; } } src/Lexer/Token.php000064400000000705146412213010010177 0ustar00 */ interface Token { /** * Returns the token type. */ public function getType(): mixed; /** * Returns the token value. */ public function getValue(): int|string; /** * Returns the line on which the token was found. */ public function getLine(): int; } src/Lexer/TokenStream/ArrayTokenStream.php000064400000004427146412213010014613 0ustar00 * @see \Dissect\Lexer\TokenStream\ArrayTokenStreamTest */ class ArrayTokenStream implements TokenStream { /** * @var Token[] */ protected array $tokens; protected int $position = 0; /** * Constructor. */ public function __construct(Token ...$tokens) { $this->tokens = $tokens; } /** * {@inheritDoc} */ public function getPosition(): int { return $this->position; } /** * {@inheritDoc} */ public function getCurrentToken(): Token { return $this->tokens[$this->position]; } /** * {@inheritDoc} */ public function lookAhead(int $n): Token { if (isset($this->tokens[$this->position + $n])) { return $this->tokens[$this->position + $n]; } throw new OutOfBoundsException('Invalid look-ahead.'); } /** * {@inheritDoc} */ public function get($n): Token { if (isset($this->tokens[$n])) { return $this->tokens[$n]; } throw new OutOfBoundsException('Invalid index.'); } /** * {@inheritDoc} */ public function move($n): void { if (!isset($this->tokens[$n])) { throw new OutOfBoundsException('Invalid index to move to.'); } $this->position = $n; } /** * {@inheritDoc} */ public function seek($n): void { if (!isset($this->tokens[$this->position + $n])) { throw new OutOfBoundsException('Invalid seek.'); } $this->position += $n; } /** * {@inheritDoc} */ public function next(): void { if (!isset($this->tokens[$this->position + 1])) { throw new OutOfBoundsException('Attempting to move beyond the end of the stream.'); } $this->position++; } public function count(): int { return count($this->tokens); } public function getIterator(): ArrayIterator { return new ArrayIterator($this->tokens); } } src/Lexer/TokenStream/TokenStream.php000064400000003016146412213010013605 0ustar00 */ interface TokenStream extends Countable, IteratorAggregate { /** * Returns the current position in the stream. */ public function getPosition(): int; /** * Retrieves the current token. * * @return Token The current token. */ public function getCurrentToken(): Token; /** * Returns a look-ahead token. Negative values are allowed * and serve as look-behind. * * @throws OutOfBoundsException If current position + $n is out of range. */ public function lookAhead(int $n): Token; /** * Returns the token at absolute position $n. * * @throws OutOfBoundsException If $n is out of range. */ public function get(int $n): Token; /** * Moves the cursor to the absolute position $n. * * @throws OutOfBoundsException If $n is out of range. */ public function move(int $n): void; /** * Moves the cursor by $n, relative to the current position. * * @throws OutOfBoundsException If current position + $n is out of range. */ public function seek(int $n): void; /** * Moves the cursor to the next token. * * @throws OutOfBoundsException If at the end of the stream. */ public function next(): void; } src/Node/CommonNode.php000064400000004725146412213010010771 0ustar00 */ class CommonNode implements Node { protected array $nodes; protected array $attributes; protected array $children = []; /** * Constructor. * * @param array $attributes The attributes of this node. * @param array $nodes The children of this node. */ public function __construct(array $attributes = [], array $nodes = []) { $this->attributes = $attributes; $this->nodes = $nodes; } /** * {@inheritDoc} */ public function getNodes(): array { return $this->nodes; } /** * {@inheritDoc} */ public function hasNode(string $name): bool { return isset($this->nodes[$name]); } /** * {@inheritDoc} */ public function getNode(int|string $name): Node { if (!isset($this->children[$name])) { throw new RuntimeException(sprintf('No child node "%s" exists.', $name)); } return $this->nodes[$name]; } /** * {@inheritDoc} */ public function setNode(string $name, Node $child): void { $this->children[$name] = $child; } /** * {@inheritDoc} */ public function removeNode(string $name): void { unset($this->children[$name]); } /** * {@inheritDoc} */ public function getAttributes(): array { return $this->attributes; } /** * {@inheritDoc} */ public function hasAttribute(string $key): bool { return isset($this->attributes[$key]); } /** * {@inheritDoc} */ public function getAttribute(string $key): mixed { if (!isset($this->attributes[$key])) { throw new RuntimeException(sprintf('No attribute "%s" exists.', $key)); } return $this->attributes[$key]; } /** * {@inheritDoc} */ public function setAttribute(string $key, mixed $value): void { $this->attributes[$key] = $value; } /** * {@inheritDoc} */ public function removeAttribute(string $key): void { unset($this->attributes[$key]); } public function count(): int { return count($this->children); } public function getIterator(): ArrayIterator { return new ArrayIterator($this->children); } } src/Node/Node.php000064400000004420146412213010007610 0ustar00 */ interface Node extends Countable, IteratorAggregate { /** * Returns the children of this node. * * @return array The children belonging to this node. */ public function getNodes(): array; /** * Checks for existence of child node named $name. * * @param string $name The name of the child node. * * @return boolean If the node exists. */ public function hasNode(string $name): bool; /** * Returns a child node specified by $name. * * @param int|string $name The name of the node. * * @return Node The child node specified by $name. * * @throws RuntimeException When no child node named $name exists. */ public function getNode(int|string $name): Node; /** * Sets a child node. * * @param string $name The name. * @param Node $child The new child node. */ public function setNode(string $name, Node $child); /** * Removes a child node by name. * * @param string $name The name. */ public function removeNode(string $name); /** * Returns all attributes of this node. * * @return array The attributes. */ public function getAttributes(): array; /** * Determines whether this node has an attribute * under $key. * * @param string $key The key. * @return boolean Whether there's an attribute under $key. */ public function hasAttribute(string $key): bool; /** * Gets an attribute by key. * * @param string $key The key. * @return mixed The attribute value. * * @throws RuntimeException When no attribute exists under $key. */ public function getAttribute(string $key): mixed; /** * Sets an attribute by key. * * @param string $key The key. * @param mixed $value The new value. */ public function setAttribute(string $key, mixed $value); /** * Removes an attribute by key. * * @param string $key The key. */ public function removeAttribute(string $key); } src/Parser/Exception/UnexpectedTokenException.php000064400000002702146412213010016215 0ustar00 */ class UnexpectedTokenException extends RuntimeException { public const MESSAGE = <<token = $token; $this->expected = $expected; if ($token->getValue() !== $token->getType()) { $info = $token->getValue() . ' (' . $token->getType() . ')'; } else { $info = $token->getType(); } parent::__construct(sprintf( self::MESSAGE, $info, $token->getLine(), implode(', ', $expected) )); } /** * Returns the unexpected token. */ public function getToken(): Token { return $this->token; } /** * Returns the expected token types. * * @return string[] The expected token types. */ public function getExpected(): array { return $this->expected; } } src/Parser/Grammar.php000064400000020430146412213010010657 0ustar00 * @see \Dissect\Parser\GrammarTest */ class Grammar { /** * The name given to the rule the grammar is augmented with * when start() is called. */ public const START_RULE_NAME = '$start'; /** * The epsilon symbol signifies an empty production. */ public const EPSILON = '$epsilon'; /** * @var Rule[] */ protected array $rules = []; protected array $groupedRules = []; protected int $nextRuleNumber = 1; protected int $conflictsMode = 9; // SHIFT | OPERATORS protected ?string $currentNonterminal = null; /** * @var string[] */ private array $nonterminals = []; protected ?Rule $currentRule = null; protected array $operators = []; protected ?array $currentOperators = null; /** * Signifies that the parser should not resolve any * grammar conflicts. */ public const NONE = 0; /** * Signifies that the parser should resolve * shift/reduce conflicts by always shifting. */ public const SHIFT = 1; /** * Signifies that the parser should resolve * reduce/reduce conflicts by reducing with * the longer rule. */ public const LONGER_REDUCE = 2; /** * Signifies that the parser should resolve * reduce/reduce conflicts by reducing * with the rule that was given earlier in * the grammar. */ public const EARLIER_REDUCE = 4; /** * Signifies that the conflicts should be * resolved by taking operator precendence * into account. */ public const OPERATORS = 8; /** * Signifies that the parser should automatically * resolve all grammar conflicts. */ public const ALL = 15; /** * Left operator associativity. */ public const LEFT = 0; /** * Right operator associativity. */ public const RIGHT = 1; /** * The operator is nonassociative. */ public const NONASSOC = 2; public function __invoke(string $nonterminal): static { $this->currentNonterminal = $nonterminal; return $this; } /** * Defines an alternative for a grammar rule. * * @param string ...$components The components of the rule. * * @return Grammar This instance. */ public function is(string ...$components): static { $this->currentOperators = null; if ($this->currentNonterminal === null) { throw new LogicException( 'You must specify a name of the rule first.' ); } $num = $this->nextRuleNumber++; $rule = new Rule($num, $this->currentNonterminal, $components); $this->rules[$num] = $this->currentRule = $this->groupedRules[$this->currentNonterminal][] = $rule; return $this; } /** * Sets the callback for the current rule. * * @param callable $callback The callback. * * @return Grammar This instance. */ public function call(callable $callback): static { if ($this->currentRule === null) { throw new LogicException( 'You must specify a rule first.' ); } $this->currentRule->setCallback($callback); return $this; } /** * Returns the set of rules of this grammar. * * @return Rule[] The rules. */ public function getRules(): array { return $this->rules; } public function getRule($number): Rule { return $this->rules[$number]; } /** * Returns the nonterminal symbols of this grammar. * * @return string[] The nonterminals. */ public function getNonterminals(): array { return $this->nonterminals; } /** * Returns rules grouped by nonterminal name. * * @return array The rules grouped by nonterminal name. */ public function getGroupedRules(): array { return $this->groupedRules; } /** * Sets a start rule for this grammar. * * @param string $name The name of the start rule. */ public function start(string $name): void { $this->rules[0] = new Rule(0, self::START_RULE_NAME, [$name]); } /** * Returns the augmented start rule. For internal use only. * * @return Rule The start rule. */ public function getStartRule(): Rule { if (!isset($this->rules[0])) { throw new LogicException("No start rule specified."); } return $this->rules[0]; } /** * Sets the mode of conflict resolution. * * @param int $mode The bitmask for the mode. */ public function resolve(int $mode): void { $this->conflictsMode = $mode; } /** * Returns the conflict resolution mode for this grammar. * * @return int The bitmask of the resolution mode. */ public function getConflictsMode(): int { return $this->conflictsMode; } /** * Does a nonterminal $name exist in the grammar? * * @param string $name The name of the nonterminal. */ public function hasNonterminal(string $name): bool { return array_key_exists($name, $this->groupedRules); } /** * Defines a group of operators. * * @param string ...$ops Any number of tokens that serve as the operators. * * @return Grammar This instance for fluent interface. */ public function operators(string ...$ops): static { $this->currentRule = null; $this->currentOperators = $ops; foreach ($ops as $op) { $this->operators[$op] = [ 'prec' => 1, 'assoc' => self::LEFT, ]; } return $this; } /** * Marks the current group of operators as left-associative. * * @return Grammar This instance for fluent interface. */ public function left(): static { return $this->assoc(self::LEFT); } /** * Marks the current group of operators as right-associative. * * @return Grammar This instance for fluent interface. */ public function right(): static { return $this->assoc(self::RIGHT); } /** * Marks the current group of operators as nonassociative. * * @return Grammar This instance for fluent interface. */ public function nonassoc(): static { return $this->assoc(self::NONASSOC); } /** * Explicitly sets the associatity of the current group of operators. * * @param int $a One of Grammar::LEFT, Grammar::RIGHT, Grammar::NONASSOC * * @return Grammar This instance for fluent interface. */ public function assoc(int $a): static { if (!$this->currentOperators) { throw new LogicException('Define a group of operators first.'); } foreach ($this->currentOperators as $op) { $this->operators[$op]['assoc'] = $a; } return $this; } /** * Sets the precedence (as an integer) of the current group of operators. * If no group of operators is being specified, sets the precedence * of the currently described rule. * * @param int $i The precedence as an integer. * * @return Grammar This instance for fluent interface. */ public function prec(int $i): static { if (!$this->currentOperators) { if (!$this->currentRule) { throw new LogicException('Define a group of operators or a rule first.'); } else { $this->currentRule->setPrecedence($i); } } else { foreach ($this->currentOperators as $op) { $this->operators[$op]['prec'] = $i; } } return $this; } /** * Is the passed token an operator? * * @param string $token The token type. */ public function hasOperator(string $token): bool { return array_key_exists($token, $this->operators); } public function getOperatorInfo($token) { return $this->operators[$token]; } } src/Parser/LALR1/Analysis/AnalysisResult.php000064400000002413146412213010014652 0ustar00 */ class AnalysisResult { protected Automaton $automaton; protected array $parseTable; protected array $resolvedConflicts; /** * Constructor. * * @param array $parseTable The parse table. * @param array $conflicts An array of conflicts resolved during parse table * construction. */ public function __construct(array $parseTable, Automaton $automaton, array $conflicts) { $this->parseTable = $parseTable; $this->automaton = $automaton; $this->resolvedConflicts = $conflicts; } /** * Returns the handle-finding FSA. */ public function getAutomaton(): Automaton { return $this->automaton; } /** * Returns the resulting parse table. * * @return array The parse table. */ public function getParseTable(): array { return $this->parseTable; } /** * Returns an array of resolved parse table conflicts. * * @return array The conflicts. */ public function getResolvedConflicts(): array { return $this->resolvedConflicts; } } src/Parser/LALR1/Analysis/Analyzer.php000064400000052772146412213010013472 0ustar00 * @see \Dissect\Parser\LALR1\Analysis\AnalyzerTest */ class Analyzer { /** * Performs a grammar analysis. * * @param Grammar $grammar The grammar to analyse. * * @return AnalysisResult The result of the analysis. */ public function analyze(Grammar $grammar): AnalysisResult { $automaton = $this->buildAutomaton($grammar); list($parseTable, $conflicts) = $this->buildParseTable($automaton, $grammar); return new AnalysisResult($parseTable, $automaton, $conflicts); } /** * Builds the handle-finding FSA from the grammar. * * @param Grammar $grammar The grammar. * * @return Automaton The resulting automaton. */ protected function buildAutomaton(Grammar $grammar): Automaton { // the eventual automaton $automaton = new Automaton(); // the queue of states that need processing $queue = new SplQueue(); // the BST for state kernels $kernelSet = new KernelSet(); // rules grouped by their name $groupedRules = $grammar->getGroupedRules(); // FIRST sets of nonterminals $firstSets = $this->calculateFirstSets($groupedRules); // keeps a list of tokens that need to be pumped // through the automaton $pumpings = []; // the item from which the whole automaton // is derived $initialItem = new Item($grammar->getStartRule(), 0); // construct the initial state $state = new State($kernelSet->insert([ [$initialItem->getRule()->getNumber(), $initialItem->getDotIndex()], ]), [$initialItem]); // the initial item automatically has EOF // as its lookahead $pumpings[] = [$initialItem, [Parser::EOF_TOKEN_TYPE]]; $queue->enqueue($state); $automaton->addState($state); while (!$queue->isEmpty()) { $state = $queue->dequeue(); // items of this state are grouped by // the active component to calculate // transitions easily $groupedItems = []; // calculate closure $added = []; $currentItems = $state->getItems(); for ($x = 0; $x < count($currentItems); $x++) { $item = $currentItems[$x]; if (!$item->isReduceItem()) { $component = $item->getActiveComponent(); $groupedItems[$component][] = $item; // if nonterminal if ($grammar->hasNonterminal($component)) { // calculate lookahead $lookahead = []; $cs = $item->getUnrecognizedComponents(); foreach ($cs as $i => $c) { if (!$grammar->hasNonterminal($c)) { // if terminal, add it and break the loop $lookahead = Util::union($lookahead, [$c]); break; } else { // if nonterminal $new = $firstSets[$c]; if (!in_array(Grammar::EPSILON, $new)) { // if the component doesn't derive // epsilon, merge FIRST sets and break $lookahead = Util::union($lookahead, $new); break; } else { // if it does if ($i < (count($cs) - 1)) { // if more components ahead, remove epsilon unset($new[array_search(Grammar::EPSILON, $new)]); } // and continue the loop $lookahead = Util::union($lookahead, $new); } } } // two items are connected if the unrecognized // part of rule 1 derives epsilon $connect = false; // only store the pumped tokens if there // actually is an unrecognized part $pump = true; if (empty($lookahead)) { $connect = true; $pump = false; } else { if (in_array(Grammar::EPSILON, $lookahead)) { unset($lookahead[array_search(Grammar::EPSILON, $lookahead)]); $connect = true; } } foreach ($groupedRules[$component] as $rule) { if (!in_array($component, $added)) { // if $component hasn't yet been expaned, // create new items for it $newItem = new Item($rule, 0); $currentItems[] = $newItem; $state->add($newItem); } else { // if it was expanded, each original // rule might bring new lookahead tokens, // so get the rule from the current state $newItem = $state->get($rule->getNumber(), 0); } if ($connect) { $item->connect($newItem); } if ($pump) { $pumpings[] = [$newItem, $lookahead]; } } } // mark the component as processed $added[] = $component; } } // calculate transitions foreach ($groupedItems as $thisComponent => $theseItems) { $newKernel = []; foreach ($theseItems as $thisItem) { $newKernel[] = [ $thisItem->getRule()->getNumber(), $thisItem->getDotIndex() + 1, ]; } $num = $kernelSet->insert($newKernel); if ($automaton->hasState($num)) { // the state already exists $automaton->addTransition($state->getNumber(), $thisComponent, $num); // extract the connected items from the target state $nextState = $automaton->getState($num); foreach ($theseItems as $thisItem) { $thisItem->connect( $nextState->get( $thisItem->getRule()->getNumber(), $thisItem->getDotIndex() + 1 ) ); } } else { // new state needs to be created $newState = new State($num, array_map(function (Item $i) { $new = new Item($i->getRule(), $i->getDotIndex() + 1); // connect the two items $i->connect($new); return $new; }, $theseItems)); $automaton->addState($newState); $queue->enqueue($newState); $automaton->addTransition($state->getNumber(), $thisComponent, $num); } } } // pump all the lookahead tokens foreach ($pumpings as $pumping) { $pumping[0]->pumpAll($pumping[1]); } return $automaton; } /** * Encodes the handle-finding FSA as a LR parse table. * * * @return array The parse table. */ protected function buildParseTable(Automaton $automaton, Grammar $grammar): array { $conflictsMode = $grammar->getConflictsMode(); $conflicts = []; $errors = []; // initialize the table $table = [ 'action' => [], 'goto' => [], ]; foreach ($automaton->getTransitionTable() as $num => $transitions) { foreach ($transitions as $trigger => $destination) { if (!$grammar->hasNonterminal($trigger)) { // terminal implies shift $table['action'][$num][$trigger] = $destination; } else { // nonterminal goes in the goto table $table['goto'][$num][$trigger] = $destination; } } } foreach ($automaton->getStates() as $num => $state) { if (!isset($table['action'][$num])) { $table['action'][$num] = []; } foreach ($state->getItems() as $item) { if ($item->isReduceItem()) { $ruleNumber = $item->getRule()->getNumber(); foreach ($item->getLookahead() as $token) { if (isset($errors[$num]) && isset($errors[$num][$token])) { // there was a previous conflict resolved as an error // entry for this token. continue; } if (array_key_exists($token, $table['action'][$num])) { // conflict $instruction = $table['action'][$num][$token]; if ($instruction > 0) { if ($conflictsMode & Grammar::OPERATORS) { if ($grammar->hasOperator($token)) { $operatorInfo = $grammar->getOperatorInfo($token); $rulePrecedence = $item->getRule()->getPrecedence(); // unless the rule has given precedence if ($rulePrecedence === null) { foreach (array_reverse($item->getRule()->getComponents()) as $c) { // try to extract it from the rightmost terminal if ($grammar->hasOperator($c)) { $ruleOperatorInfo = $grammar->getOperatorInfo($c); $rulePrecedence = $ruleOperatorInfo['prec']; break; } } } if ($rulePrecedence !== null) { // if we actually have a rule precedence $tokenPrecedence = $operatorInfo['prec']; if ($rulePrecedence > $tokenPrecedence) { // if the rule precedence is higher, reduce $table['action'][$num][$token] = -$ruleNumber; } elseif ($rulePrecedence < $tokenPrecedence) { // if the token precedence is higher, shift // (i.e. don't modify the table) } else { // precedences are equal, let's turn to associativity $assoc = $operatorInfo['assoc']; if ($assoc === Grammar::RIGHT) { // if right-associative, shift // (i.e. don't modify the table) } elseif ($assoc === Grammar::LEFT) { // if left-associative, reduce $table['action'][$num][$token] = -$ruleNumber; } elseif ($assoc === Grammar::NONASSOC) { // the token is nonassociative. // this actually means an input error, so // remove the shift entry from the table // and mark this as an explicit error // entry unset($table['action'][$num][$token]); $errors[$num][$token] = true; } } continue; // resolved the conflict, phew } // we couldn't calculate the precedence => the conflict was not resolved // move along. } } // s/r if ($conflictsMode & Grammar::SHIFT) { $conflicts[] = [ 'state' => $num, 'lookahead' => $token, 'rule' => $item->getRule(), 'resolution' => Grammar::SHIFT, ]; continue; } else { throw new ShiftReduceConflictException( $num, $item->getRule(), $token, $automaton ); } } else { // r/r $originalRule = $grammar->getRule(-$instruction); $newRule = $item->getRule(); if ($conflictsMode & Grammar::LONGER_REDUCE) { $count1 = count($originalRule->getComponents()); $count2 = count($newRule->getComponents()); if ($count1 > $count2) { // original rule is longer $resolvedRules = [$originalRule, $newRule]; $conflicts[] = [ 'state' => $num, 'lookahead' => $token, 'rules' => $resolvedRules, 'resolution' => Grammar::LONGER_REDUCE, ]; continue; } elseif ($count2 > $count1) { // new rule is longer $table['action'][$num][$token] = -$ruleNumber; $resolvedRules = [$newRule, $originalRule]; $conflicts[] = [ 'state' => $num, 'lookahead' => $token, 'rules' => $resolvedRules, 'resolution' => Grammar::LONGER_REDUCE, ]; continue; } } if ($conflictsMode & Grammar::EARLIER_REDUCE) { if (-$instruction < $ruleNumber) { // original rule was earlier $resolvedRules = [$originalRule, $newRule]; $conflicts[] = [ 'state' => $num, 'lookahead' => $token, 'rules' => $resolvedRules, 'resolution' => Grammar::EARLIER_REDUCE, ]; } else { // new rule was earlier $table['action'][$num][$token] = -$ruleNumber; $conflicts[] = [ 'state' => $num, 'lookahead' => $token, 'rules' => $resolvedRules, 'resolution' => Grammar::EARLIER_REDUCE, ]; $resolvedRules = [$newRule, $originalRule]; } continue; } // everything failed, throw an exception throw new ReduceReduceConflictException( $num, $originalRule, $newRule, $token, $automaton ); } } $table['action'][$num][$token] = -$ruleNumber; } } } } return [$table, $conflicts]; } /** * Calculates the FIRST sets of all nonterminals. * * @param array $rules The rules grouped by the LHS. * * @return array Calculated FIRST sets. */ protected function calculateFirstSets(array $rules): array { // initialize $firstSets = []; foreach (array_keys($rules) as $lhs) { $firstSets[$lhs] = []; } do { $changes = false; foreach ($rules as $lhs => $ruleArray) { foreach ($ruleArray as $rule) { $components = $rule->getComponents(); $new = []; if (empty($components)) { $new = [Grammar::EPSILON]; } else { foreach ($components as $i => $component) { if (array_key_exists($component, $rules)) { // if nonterminal, copy its FIRST set to // this rule's first set $x = $firstSets[$component]; if (!in_array(Grammar::EPSILON, $x)) { // if the component doesn't derive // epsilon, merge the first sets and // we're done $new = Util::union($new, $x); break; } else { // if all components derive epsilon, // the rule itself derives epsilon if ($i < (count($components) - 1)) { // more components ahead, remove epsilon unset($x[array_search(Grammar::EPSILON, $x)]); } $new = Util::union($new, $x); } } else { // if terminal, simply add it the the FIRST set // and we're done $new = Util::union($new, [$component]); break; } } } if (Util::different($new, $firstSets[$lhs])) { $firstSets[$lhs] = Util::union($firstSets[$lhs], $new); $changes = true; } } } } while ($changes); return $firstSets; } } src/Parser/LALR1/Analysis/Automaton.php000064400000003455146412213010013646 0ustar00 * @see \Dissect\Parser\LALR1\Analysis\AutomatonTest */ class Automaton { protected array $states = []; protected array $transitionTable = []; /** * Adds a new automaton state. * * @param State $state The new state. */ public function addState(State $state): void { $this->states[$state->getNumber()] = $state; } /** * Adds a new transition in the FSA. * * @param int $origin The number of the origin state. * @param string $label The symbol that triggers this transition. * @param int $dest The destination state number. */ public function addTransition(int $origin, string $label, int $dest): void { $this->transitionTable[$origin][$label] = $dest; } /** * Returns a state by its number. * * @param int $number The state number. * * @return State The requested state. */ public function getState(int $number): State { return $this->states[$number]; } /** * Does this automaton have a state identified by $number? * * @param $number */ public function hasState($number): bool { return isset($this->states[$number]); } /** * Returns all states in this FSA. * * @return array The states of this FSA. */ public function getStates(): array { return $this->states; } /** * Returns the transition table for this automaton. * * @return array The transition table. */ public function getTransitionTable(): array { return $this->transitionTable; } } src/Parser/LALR1/Analysis/Exception/ConflictException.php000064400000001513146412213010017246 0ustar00 */ class ConflictException extends LogicException { public function __construct( string $message, protected int $state, protected Automaton $automaton ) { parent::__construct($message); } /** * Returns the number of the inadequate state. */ public function getStateNumber(): int { return $this->state; } /** * Returns the faulty automaton. */ public function getAutomaton(): Automaton { return $this->automaton; } } src/Parser/LALR1/Analysis/Exception/ReduceReduceConflictException.php000064400000005040146412213010021525 0ustar00 */ class ReduceReduceConflictException extends ConflictException { /** * The exception message template. */ public const MESSAGE = << %s vs: %d. %s -> %s (on lookahead "%s" in state %d). Restructure your grammar or choose a conflict resolution mode. EOT; protected Rule $firstRule; protected Rule $secondRule; protected string $lookahead; /** * Constructor. * * @param int $state The number of the inadequate state. * @param Rule $firstRule The first conflicting grammar rule. * @param Rule $secondRule The second conflicting grammar rule. * @param string $lookahead The conflicting lookahead. * @param Automaton $automaton The faulty automaton. */ public function __construct(int $state, Rule $firstRule, Rule $secondRule, string $lookahead, Automaton $automaton) { $components1 = $firstRule->getComponents(); $components2 = $secondRule->getComponents(); parent::__construct( sprintf( self::MESSAGE, $firstRule->getNumber(), $firstRule->getName(), empty($components1) ? '/* empty */' : implode(' ', $components1), $secondRule->getNumber(), $secondRule->getName(), empty($components2) ? '/* empty */' : implode(' ', $components2), $lookahead, $state ), $state, $automaton ); $this->firstRule = $firstRule; $this->secondRule = $secondRule; $this->lookahead = $lookahead; } /** * Returns the first conflicting rule. * * @return Rule The first conflicting rule. */ public function getFirstRule(): Rule { return $this->firstRule; } /** * Returns the second conflicting rule. * * @return Rule The second conflicting rule. */ public function getSecondRule(): Rule { return $this->secondRule; } /** * Returns the conflicting lookahead. * * @return string The conflicting lookahead. */ public function getLookahead(): string { return $this->lookahead; } } src/Parser/LALR1/Analysis/Exception/ShiftReduceConflictException.php000064400000003473146412213010021403 0ustar00 */ class ShiftReduceConflictException extends ConflictException { /** * The exception message template. */ public const MESSAGE = << %s (on lookahead "%s" in state %d). Restructure your grammar or choose a conflict resolution mode. EOT; protected Rule $rule; protected string $lookahead; /** * Constructor. * * @param Rule $rule The conflicting grammar rule. * @param string $lookahead The conflicting lookahead to shift. * @param Automaton $automaton The faulty automaton. */ public function __construct($state, Rule $rule, $lookahead, Automaton $automaton) { $components = $rule->getComponents(); parent::__construct( sprintf( self::MESSAGE, $rule->getNumber(), $rule->getName(), empty($components) ? '/* empty */' : implode(' ', $components), $lookahead, $state ), $state, $automaton ); $this->rule = $rule; $this->lookahead = $lookahead; } /** * Returns the conflicting rule. * * @return Rule The conflicting rule. */ public function getRule(): Rule { return $this->rule; } /** * Returns the conflicting lookahead. * * @return string The conflicting lookahead. */ public function getLookahead(): string { return $this->lookahead; } } src/Parser/LALR1/Analysis/Item.php000064400000007014146412213010012570 0ustar00 * A -> a . b c * * * This means that within this item, a has been recognized * and b is expected. If the dot is at the very end of the * rule: * * 
 * A -> a b c .
 *
* * it means that the whole rule has been recognized and * can be reduced. * * @author Jakub Lédl * @see \Dissect\Parser\LALR1\Analysis\ItemTest */ class Item { protected Rule $rule; protected int $dotIndex; protected array $lookahead = []; protected array $connected = []; /** * Constructor. * * @param Rule $rule The rule of this item. * @param int $dotIndex The index of the dot in this item. */ public function __construct(Rule $rule, int $dotIndex) { $this->rule = $rule; $this->dotIndex = $dotIndex; } /** * Returns the dot index of this item. * * @return int The dot index. */ public function getDotIndex(): int { return $this->dotIndex; } /** * Returns the currently expected component. * * If the item is: * * 
     * A -> a . b c
     *
* * then this method returns the component "b". * * @return string The component. */ public function getActiveComponent(): string { return $this->rule->getComponent($this->dotIndex); } /** * Returns the rule of this item. * * @return Rule The rule. */ public function getRule(): Rule { return $this->rule; } /** * Determines whether this item is a reduce item. * * An item is a reduce item if the dot is at the very end: * * 
     * A -> a b c .
     *
* * @return boolean Whether this item is a reduce item. */ public function isReduceItem(): bool { return $this->dotIndex === count($this->rule->getComponents()); } /** * Connects two items with a lookahead pumping channel. * * @param Item $i The item. */ public function connect(Item $i): void { $this->connected[] = $i; } /** * Pumps a lookahead token to this item and all items connected * to it. * * @param string $lookahead The lookahead token name. */ public function pump(string $lookahead): void { if (!in_array($lookahead, $this->lookahead)) { $this->lookahead[] = $lookahead; foreach ($this->connected as $item) { $item->pump($lookahead); } } } /** * Pumps several lookahead tokens. * * @param array $lookahead The lookahead tokens. */ public function pumpAll(array $lookahead): void { foreach ($lookahead as $l) { $this->pump($l); } } /** * Returns the computed lookahead for this item. * * @return string[] The lookahead symbols. */ public function getLookahead(): array { return $this->lookahead; } /** * Returns all components that haven't been recognized * so far. * * @return array The unrecognized components. */ public function getUnrecognizedComponents(): array { return array_slice($this->rule->getComponents(), $this->dotIndex + 1); } } src/Parser/LALR1/Analysis/KernelSet/KernelSet.php000064400000004054146412213010015463 0ustar00 * @see \Dissect\Parser\LALR1\Analysis\KernelSet\KernelSetTest */ class KernelSet { protected int $nextNumber = 0; protected ?Node $root = null; /** * Inserts a new node in the BST and returns * the number of the new state if no such state * exists. Otherwise, returns the number of the * existing state. * * @param array $kernel The state kernel. * * @return int The state number. */ public function insert(array $kernel): int { $kernel = KernelSet::hashKernel($kernel); if ($this->root === null) { $this->root = new Node($kernel, $n = $this->nextNumber++); return $n; } $node = $this->root; while (true) { if ($kernel < $node->kernel) { if ($node->left === null) { $node->left = new Node($kernel, $n = $this->nextNumber++); return $n; } else { $node = $node->left; } } elseif ($kernel > $node->kernel) { if ($node->right === null) { $node->right = new Node($kernel, $n = $this->nextNumber++); return $n; } else { $node = $node->right; } } else { return $node->number; } } } /** * Hashes a state kernel using a pairing function. * * @param array $kernel The kernel. * * @return array The hashed kernel. */ public static function hashKernel(array $kernel): array { $kernel = array_map(function ($tuple) { list ($car, $cdr) = $tuple; return ($car + $cdr) * ($car + $cdr + 1) / 2 + $cdr; }, $kernel); sort($kernel); return $kernel; } } src/Parser/LALR1/Analysis/KernelSet/Node.php000064400000000555146412213010014456 0ustar00kernel = $hashedKernel; $this->number = $number; } } src/Parser/LALR1/Analysis/State.php000064400000003210146412213010012744 0ustar00 * @see \Dissect\Parser\LALR1\Analysis\StateTest */ class State { protected array $items = []; protected array $itemMap = []; protected int $number; /** * Constructor. * * @param int $number The number identifying this state. * @param array $items The initial items of this state. */ public function __construct(int $number, array $items) { $this->number = $number; foreach ($items as $item) { $this->add($item); } } /** * Adds a new item to this state. * * @param Item $item The new item. */ public function add(Item $item): void { $this->items[] = $item; $this->itemMap[$item->getRule()->getNumber()][$item->getDotIndex()] = $item; } /** * Returns an item by its rule number and dot index. * * @param int $ruleNumber The number of the rule of the desired item. * @param int $dotIndex The dot index of the desired item. * * @return Item The item. */ public function get(int $ruleNumber, int $dotIndex): Item { return $this->itemMap[$ruleNumber][$dotIndex]; } /** * Returns the number identifying this state. */ public function getNumber(): int { return $this->number; } /** * Returns an array of items constituting this state. * * @return array The items. */ public function getItems(): array { return $this->items; } } src/Parser/LALR1/Dumper/AutomatonDumper.php000064400000010040146412213010014460 0ustar00 * @see \Dissect\Parser\LALR1\Dumper\AutomatonDumperTest */ class AutomatonDumper { protected Automaton $automaton; /** * Constructor. */ public function __construct(Automaton $automaton) { $this->automaton = $automaton; } /** * Dumps the entire automaton. * * @return string The automaton encoded in DOT. */ public function dump(): string { $writer = new StringWriter(); $this->writeHeader($writer); $writer->writeLine(); foreach ($this->automaton->getStates() as $state) { $this->writeState($writer, $state); } $writer->writeLine(); foreach ($this->automaton->getTransitionTable() as $num => $map) { foreach ($map as $trigger => $destination) { $writer->writeLine(sprintf( '%d -> %d [label="%s"];', $num, $destination, $trigger )); } } $writer->outdent(); $this->writeFooter($writer); return $writer->get(); } /** * Dumps only the specified state + any relevant * transitions. * * @param int $n The number of the state. * * @return string The output in DOT format. */ public function dumpState(int $n): string { $writer = new StringWriter(); $this->writeHeader($writer, $n); $writer->writeLine(); $this->writeState($writer, $this->automaton->getState($n)); $table = $this->automaton->getTransitionTable(); $row = $table[$n] ?? []; foreach ($row as $dest) { if ($dest !== $n) { $this->writeState($writer, $this->automaton->getState($dest), false); } } $writer->writeLine(); foreach ($row as $trigger => $dest) { $writer->writeLine(sprintf( '%d -> %d [label="%s"];', $n, $dest, $trigger )); } $writer->outdent(); $this->writeFooter($writer); return $writer->get(); } protected function writeHeader(StringWriter $writer, $stateNumber = null): void { $writer->writeLine(sprintf( 'digraph %s {', $stateNumber ? 'State' . $stateNumber : 'Automaton' )); $writer->indent(); $writer->writeLine('rankdir="LR";'); } protected function writeState(StringWriter $writer, State $state, $full = true): void { $n = $state->getNumber(); $string = sprintf( '%d [label="State %d', $n, $n ); if ($full) { $string .= '\n\n'; $items = []; foreach ($state->getItems() as $item) { $items[] = $this->formatItem($item); } $string .= implode('\n', $items); } $string .= '"];'; $writer->writeLine($string); } protected function formatItem(Item $item): string { $rule = $item->getRule(); $components = $rule->getComponents(); // the dot array_splice($components, $item->getDotIndex(), 0, ['•']); if ($rule->getNumber() === 0) { $string = ''; } else { $string = sprintf("%s → ", $rule->getName()); } $string .= implode(' ', $components); if ($item->isReduceItem()) { $string .= sprintf( ' [%s]', implode(' ', $item->getLookahead()) ); } return $string; } protected function writeFooter(StringWriter $writer): void { $writer->writeLine('}'); } } src/Parser/LALR1/Dumper/DebugTableDumper.php000064400000010330146412213010014511 0ustar00 * @see \Dissect\Parser\LALR1\Dumper\DebugTableDumperTest */ class DebugTableDumper implements TableDumper { protected Grammar $grammar; protected StringWriter $writer; protected bool $written = false; /** * Constructor. * * @param Grammar $grammar The grammar of this parse table. */ public function __construct(Grammar $grammar) { $this->grammar = $grammar; $this->writer = new StringWriter(); } /** * {@inheritDoc} */ public function dump(array $table): string { // for readability ksort($table['action']); ksort($table['goto']); // the grammar dictates the parse table, // therefore the result is always the same if (!$this->written) { $this->writeHeader(); $this->writer->indent(); foreach ($table['action'] as $n => $state) { $this->writeState($n, $state); $this->writer->writeLine(); } $this->writer->outdent(); $this->writeMiddle(); $this->writer->indent(); foreach ($table['goto'] as $n => $map) { $this->writeGoto($n, $map); $this->writer->writeLine(); } $this->writer->outdent(); $this->writeFooter(); $this->written = true; } return $this->writer->get(); } protected function writeHeader() { $this->writer->writeLine('writer->writeLine(); $this->writer->writeLine('return ['); $this->writer->indent(); $this->writer->writeLine("'action' => ["); } protected function writeState($n, array $state) { $this->writer->writeLine($n . ' => ['); $this->writer->indent(); foreach ($state as $trigger => $action) { $this->writeAction($trigger, $action); $this->writer->writeLine(); } $this->writer->outdent(); $this->writer->writeLine('],'); } protected function writeAction($trigger, $action) { if ($action > 0) { $this->writer->writeLine(sprintf( '// on %s shift and go to state %d', $trigger, $action )); } elseif ($action < 0) { $rule = $this->grammar->getRule(-$action); $components = $rule->getComponents(); if (empty($components)) { $rhs = '/* empty */'; } else { $rhs = implode(' ', $components); } $this->writer->writeLine(sprintf( '// on %s reduce by rule %s -> %s', $trigger, $rule->getName(), $rhs )); } else { $this->writer->writeLine(sprintf( '// on %s accept the input', $trigger )); } $this->writer->writeLine(sprintf( "'%s' => %d,", $trigger, $action )); } protected function writeMiddle() { $this->writer->writeLine('],'); $this->writer->writeLine(); $this->writer->writeLine("'goto' => ["); } protected function writeGoto($n, array $map) { $this->writer->writeLine($n . ' => ['); $this->writer->indent(); foreach ($map as $sym => $dest) { $this->writer->writeLine(sprintf( '// on %s go to state %d', $sym, $dest )); $this->writer->writeLine(sprintf( "'%s' => %d,", $sym, $dest )); $this->writer->writeLine(); } $this->writer->outdent(); $this->writer->writeLine('],'); } protected function writeFooter() { $this->writer->writeLine('],'); $this->writer->outdent(); $this->writer->writeLine('];'); } } src/Parser/LALR1/Dumper/ProductionTableDumper.php000064400000004244146412213010015620 0ustar00 * @see \Dissect\Parser\LALR1\Dumper\ProductionTableDumperTest */ class ProductionTableDumper implements TableDumper { /** * {@inheritDoc} */ public function dump(array $table): string { $writer = new StringWriter(); $this->writeIntro($writer); foreach ($table['action'] as $num => $state) { $this->writeState($writer, $num, $state); $writer->write(','); } $this->writeMiddle($writer); foreach($table['goto'] as $num => $map) { $this->writeGoto($writer, $num, $map); $writer->write(','); } $this->writeOutro($writer); $writer->write("\n"); // eof newline return $writer->get(); } protected function writeIntro(StringWriter $writer) { $writer->write("["); } protected function writeState(StringWriter $writer, $num, $state) { $writer->write($num . '=>['); foreach ($state as $trigger => $action) { $this->writeAction($writer, $trigger, $action); $writer->write(','); } $writer->write(']'); } protected function writeAction(StringWriter $writer, $trigger, $action) { $writer->write(sprintf( "'%s'=>%d", $trigger, $action )); } protected function writeMiddle(StringWriter $writer) { $writer->write("],'goto'=>["); } protected function writeGoto(StringWriter $writer, $num, $map) { $writer->write($num . '=>['); foreach ($map as $trigger => $destination) { $writer->write(sprintf( "'%s'=>%d", $trigger, $destination )); $writer->write(','); } $writer->write(']'); } protected function writeOutro(StringWriter $writer) { $writer->write(']];'); } } src/Parser/LALR1/Dumper/StringWriter.php000064400000002764146412213010014015 0ustar00 */ class StringWriter { protected int $indent = 0; protected string $string = ''; /** * Appends the given string. * * @param string $string The string to write. */ public function write(string $string): void { $this->string .= $string; } /** * Gets the string as written so far. * * @return string The string. */ public function get(): string { return $this->string; } /** * Adds a level of indentation. */ public function indent(): void { $this->indent++; } /** * Removes a level of indentation. */ public function outdent(): void { $this->indent--; } /** * If a string is given, it writes * it with correct indentation and * a newline appended. When no string * is given, it adheres to the rule * that empty lines should be whitespace-free * (like vim) and doesn't append any * indentation. * * @param string|null $string The string to write. */ public function writeLine(string $string = null): void { if ($string) { $this->write(sprintf( "%s%s\n", str_repeat(' ', $this->indent * 4), $string )); } else { $this->write("\n"); } } } src/Parser/LALR1/Dumper/TableDumper.php000064400000000651146412213010013547 0ustar00 */ interface TableDumper { /** * Dumps the parse table. * * @param array $table The parse table. * * @return string The resulting string representation of the table. */ public function dump(array $table): string; } src/Parser/LALR1/Parser.php000064400000005350146412213010011344 0ustar00 * @see \Dissect\Parser\LALR1\ParserTest */ class Parser implements P\Parser { protected Grammar $grammar; protected array $parseTable; /** * Constructor. * * @param Grammar $grammar The grammar. * @param array|null $parseTable If given, the parser doesn't have to analyze the grammar. */ public function __construct(Grammar $grammar, array $parseTable = null) { $this->grammar = $grammar; if ($parseTable) { $this->parseTable = $parseTable; } else { $analyzer = new Analyzer(); $this->parseTable = $analyzer->analyze($grammar)->getParseTable(); } } /** * {@inheritDoc} */ public function parse(TokenStream $stream): mixed { $stateStack = [$currentState = 0]; $args = []; foreach ($stream as $token) { while (true) { $type = $token->getType(); if (!isset($this->parseTable['action'][$currentState][$type])) { // unexpected token throw new UnexpectedTokenException( $token, array_keys($this->parseTable['action'][$currentState]) ); } $action = $this->parseTable['action'][$currentState][$type]; if ($action > 0) { // shift $args[] = $token; $stateStack[] = $currentState = $action; break; } elseif ($action < 0) { // reduce $rule = $this->grammar->getRule(-$action); $popCount = count($rule->getComponents()); array_splice($stateStack, -$popCount); $newArgs = array_splice($args, -$popCount); if ($callback = $rule->getCallback()) { $args[] = call_user_func_array($callback, $newArgs); } else { $args[] = $newArgs[0]; } $state = $stateStack[count($stateStack) - 1]; $stateStack[] = $currentState = $this->parseTable['goto'] [$state][$rule->getName()]; } else { // accept return $args[0]; } } } return null; } } src/Parser/Parser.php000064400000001113146412213010010522 0ustar00 */ interface Parser { /** * The token type that represents an EOF. */ public const EOF_TOKEN_TYPE = '$eof'; /** * Parses a token stream and returns the semantical value * of the input. * * @param TokenStream $stream The token stream. * * @return mixed The semantical value of the input. */ public function parse(TokenStream $stream): mixed; } src/Parser/Rule.php000064400000004510146412213010010201 0ustar00 * @see \Dissect\Parser\RuleTest */ class Rule { protected int $number; protected string $name; /** * @var string[] */ protected array $components; /** * @var callable */ protected $callback = null; protected ?int $precedence = null; /** * Constructor. * * @param int $number The number of the rule in the grammar. * @param string $name The name (lhs) of the rule ("A" in "A -> a b c") * @param string[] $components The components of this rule. */ public function __construct(int $number, string $name, array $components) { $this->number = $number; $this->name = $name; $this->components = $components; } /** * Returns the number of this rule. * * @return int The number of this rule. */ public function getNumber(): int { return $this->number; } /** * Returns the name of this rule. * * @return string The name of this rule. */ public function getName(): string { return $this->name; } /** * Returns the components of this rule. * * @return string[] The components of this rule. */ public function getComponents(): array { return $this->components; } /** * Returns a component at index $index or null * if index is out of range. * * @param int $index The index. * * @return ?string The component at index $index. */ public function getComponent(int $index): ?string { if (!isset($this->components[$index])) { return null; } return $this->components[$index]; } /** * Sets the callback (the semantic value) of the rule. * * @param callable $callback The callback. */ public function setCallback(callable $callback): void { $this->callback = $callback; } public function getCallback(): ?callable { return $this->callback; } public function getPrecedence(): ?int { return $this->precedence; } public function setPrecedence($i): void { $this->precedence = $i; } } src/Util/Util.php000064400000003525146412213010007675 0ustar00 */ abstract class Util { /** * Merges two or more sets by values. * * {a, b} union {b, c} = {a, b, c} * * @return array The union of given sets. */ public static function union(array ...$arrays): array { return array_unique(call_user_func_array('array_merge', $arrays)); } /** * Determines whether two sets have a difference. * * @param array $first The first set. * @param array $second The second set. * * @return boolean Whether there is a difference. */ public static function different(array $first, array $second): bool { return count(array_diff($first, $second)) !== 0; } /** * Determines length of a UTF-8 string. * * @param string $str The string in UTF-8 encoding. * * @return int The length. */ public static function stringLength(string $str): int { return mb_strlen(mb_convert_encoding($str, 'ISO-8859-1')); } /** * Extracts a substring of a UTF-8 string. * * @param string $str The string to extract the substring from. * @param int $position The position from which to start extracting. * @param int|null $length The length of the substring. * * @return string The substring. */ public static function substring(string $str, int $position, int $length = null): string { static $lengthFunc = null; if ($lengthFunc === null) { $lengthFunc = function_exists('mb_substr') ? 'mb_substr' : 'iconv_substr'; } if ($length === null) { $length = self::stringLength($str); } return $lengthFunc($str, $position, $length, 'UTF-8'); } } tests/Lexer/AbstractLexerTest.php000064400000004450146412213010013076 0ustar00lexer = new StubLexer(); } #[\PHPUnit\Framework\Attributes\Test] public function lexShouldDelegateToExtractTokenUpdatingTheLineAndOffsetAccordingly(): void { $stream = $this->lexer->lex("ab\nc"); $this->assertSame('a', $stream->getCurrentToken()->getValue()); $this->assertSame(1, $stream->getCurrentToken()->getLine()); $stream->next(); $this->assertSame('b', $stream->getCurrentToken()->getValue()); $this->assertSame(1, $stream->getCurrentToken()->getLine()); $stream->next(); $this->assertSame("\n", $stream->getCurrentToken()->getValue()); $this->assertSame(1, $stream->getCurrentToken()->getLine()); $stream->next(); $this->assertSame('c', $stream->getCurrentToken()->getValue()); $this->assertSame(2, $stream->getCurrentToken()->getLine()); } #[\PHPUnit\Framework\Attributes\Test] public function lexShouldAppendAnEofTokenAutomatically(): void { $stream = $this->lexer->lex("abc"); $stream->seek(3); $this->assertSame(Parser::EOF_TOKEN_TYPE, $stream->getCurrentToken()->getType()); $this->assertSame(1, $stream->getCurrentToken()->getLine()); } #[\PHPUnit\Framework\Attributes\Test] public function lexShouldThrowAnExceptionOnAnUnrecognizableToken(): void { try { $this->lexer->lex("abcd"); $this->fail('Expected a RecognitionException.'); } catch (RecognitionException $e) { $this->assertSame(1, $e->getSourceLine()); } } #[\PHPUnit\Framework\Attributes\Test] public function lexShouldNormalizeLineEndingsBeforeLexing(): void { $stream = $this->lexer->lex("a\r\nb"); $this->assertSame("\n", $stream->get(1)->getValue()); } #[\PHPUnit\Framework\Attributes\Test] public function lexShouldSkipTokensIfToldToDoSo(): void { $stream = $this->lexer->lex('aeb'); $this->assertNotSame('e', $stream->get(1)->getType()); } } tests/Lexer/Recognizer/RegexRecognizerTest.php000064400000002210146412213010015534 0ustar00match('lorem ipsum', $value); $this->assertTrue($result); $this->assertNotNull($value); $this->assertSame('lorem', $value); } #[\PHPUnit\Framework\Attributes\Test] public function recognizerShouldFailAndTheValueShouldStayNull(): void { $recognizer = new RegexRecognizer('/[a-z]+/'); $result = $recognizer->match('123 456', $value); $this->assertFalse($result); $this->assertNull($value); } #[\PHPUnit\Framework\Attributes\Test] public function recognizerShouldFailIfTheMatchIsNotAtTheBeginningOfTheString(): void { $recognizer = new RegexRecognizer('/[a-z]+/'); $result = $recognizer->match('234 class', $value); $this->assertFalse($result); $this->assertNull($value); } } tests/Lexer/Recognizer/SimpleRecognizerTest.php000064400000001504146412213010015720 0ustar00match('class lorem ipsum', $value); $this->assertTrue($result); $this->assertNotNull($value); $this->assertSame('class', $value); } #[\PHPUnit\Framework\Attributes\Test] public function recognizerShouldFailAndTheValueShouldStayNull(): void { $recognizer = new SimpleRecognizer('class'); $result = $recognizer->match('lorem ipsum', $value); $this->assertFalse($result); $this->assertNull($value); } } tests/Lexer/RegexLexerTest.php000064400000001722146412213010012404 0ustar00lexer = new StubRegexLexer(); } #[\PHPUnit\Framework\Attributes\Test] public function itShouldCallGetTypeToRetrieveTokenType(): void { $stream = $this->lexer->lex('5 + 6'); $this->assertCount(4, $stream); $this->assertSame('INT', $stream->get(0)->getType()); $this->assertSame('+', $stream->get(1)->getType()); $this->assertSame(Parser::EOF_TOKEN_TYPE, $stream->get(3)->getType()); } #[\PHPUnit\Framework\Attributes\Test] public function itShouldTrackLineNumbers(): void { $stream = $this->lexer->lex("5\n+\n\n5"); $this->assertSame(2, $stream->get(1)->getLine()); $this->assertSame(4, $stream->get(2)->getLine()); } } tests/Lexer/SimpleLexerTest.php000064400000003101146412213010012554 0ustar00lexer = new SimpleLexer(); $this->lexer ->token('A', 'a') ->token('(') ->token('B', 'b') ->token(')') ->token('C', 'c') ->regex('WS', "/[ \n\t\r]+/") ->skip('WS'); } #[\PHPUnit\Framework\Attributes\Test] public function simpleLexerShouldWalkThroughTheRecognizers(): void { $stream = $this->lexer->lex('a (b) c'); $this->assertSame(6, $stream->count()); // with EOF $this->assertSame('(', $stream->get(1)->getType()); $this->assertSame(1, $stream->get(3)->getLine()); $this->assertSame('C', $stream->get(4)->getType()); } #[\PHPUnit\Framework\Attributes\Test] public function simpleLexerShouldSkipSpecifiedTokens(): void { $stream = $this->lexer->lex('a (b) c'); foreach ($stream as $token) { $this->assertNotSame('WS', $token->getType()); } } #[\PHPUnit\Framework\Attributes\Test] public function simpleLexerShouldReturnTheBestMatch(): void { $this->lexer->token('CLASS', 'class'); $this->lexer->regex('WORD', '/[a-z]+/'); $stream = $this->lexer->lex('class classloremipsum'); $this->assertSame('CLASS', $stream->getCurrentToken()->getType()); $this->assertSame('WORD', $stream->lookAhead(1)->getType()); } } tests/Lexer/StatefulLexerTest.php000064400000004367146412213010013131 0ustar00lexer = new StatefulLexer(); } #[\PHPUnit\Framework\Attributes\Test] public function addingNewTokenShouldThrowAnExceptionWhenNoStateIsBeingBuilt(): void { $this->expectExceptionMessage("Define a lexer state first."); $this->expectException(LogicException::class); $this->lexer->regex('WORD', '/[a-z]+/'); } #[\PHPUnit\Framework\Attributes\Test] public function anExceptionShouldBeThrownOnLexingWithoutAStartingState(): void { $this->expectException(LogicException::class); $this->lexer->state('root'); $this->lexer->lex('foo'); } #[\PHPUnit\Framework\Attributes\Test] public function theStateMechanismShouldCorrectlyPushAndPopStatesFromTheStack(): void { /** @noinspection PhpPossiblePolymorphicInvocationInspection */ $this->lexer->state('root') ->regex('WORD', '/[a-z]+/') ->regex('WS', "/[ \r\n\t]+/") ->token('"')->action('string') ->skip('WS'); /** @noinspection PhpPossiblePolymorphicInvocationInspection */ $this->lexer->state('string') ->regex('STRING_CONTENTS', '/(\\\\"|[^"])+/') ->token('"')->action(StatefulLexer::POP_STATE); $this->lexer->start('root'); $stream = $this->lexer->lex('foo bar "long \\" string" baz quux'); $this->assertCount(8, $stream); $this->assertSame('STRING_CONTENTS', $stream->get(3)->getType()); $this->assertSame('long \\" string', $stream->get(3)->getValue()); $this->assertSame('quux', $stream->get(6)->getValue()); } #[\PHPUnit\Framework\Attributes\Test] public function defaultActionShouldBeNop(): void { $this->lexer->state('root') ->regex('WORD', '/[a-z]+/') ->regex('WS', "/[ \r\n\t]+/") ->skip('WS'); $this->lexer->state('string'); $this->lexer->start('root'); $stream = $this->lexer->lex('foo bar'); $this->assertSame(3, $stream->count()); } } tests/Lexer/StubLexer.php000064400000001142146412213010011403 0ustar00getCurrentLine()); return $token; } protected function shouldSkipToken(Token $token): bool { return $token->getType() === 'e'; } } tests/Lexer/StubRegexLexer.php000064400000001312146412213010012375 0ustar00operators)) { return $value; } else { throw new RuntimeException(sprintf('Invalid token "%s"', $value)); } } } tests/Lexer/TokenStream/ArrayTokenStreamTest.php000064400000006432146412213010016024 0ustar00stream = new ArrayTokenStream( new CommonToken('INT', '6', 1), new CommonToken('PLUS', '+', 1), new CommonToken('INT', '5', 1), new CommonToken('MINUS', '-', 1), new CommonToken('INT', '3', 1), ); } #[\PHPUnit\Framework\Attributes\Test] public function theCursorShouldBeOnFirstTokenByDefault(): void { $this->assertSame('6', $this->stream->getCurrentToken()->getValue()); } #[\PHPUnit\Framework\Attributes\Test] public function getPositionShouldReturnCurrentPosition(): void { $this->stream->seek(2); $this->stream->next(); $this->assertSame(3, $this->stream->getPosition()); } #[\PHPUnit\Framework\Attributes\Test] public function lookAheadShouldReturnTheCorrectToken(): void { $this->assertSame('5', $this->stream->lookAhead(2)->getValue()); } #[\PHPUnit\Framework\Attributes\Test] public function lookAheadShouldThrowAnExceptionWhenInvalid(): void { $this->expectException(OutOfBoundsException::class); $this->stream->lookAhead(15); } #[\PHPUnit\Framework\Attributes\Test] public function getShouldReturnATokenByAbsolutePosition(): void { $this->assertSame('3', $this->stream->get(4)->getValue()); } #[\PHPUnit\Framework\Attributes\Test] public function getShouldThrowAnExceptionWhenInvalid(): void { $this->expectException(OutOfBoundsException::class); $this->stream->get(15); } #[\PHPUnit\Framework\Attributes\Test] public function moveShouldMoveTheCursorByToAnAbsolutePosition(): void { $this->stream->move(2); $this->assertSame('5', $this->stream->getCurrentToken()->getValue()); } #[\PHPUnit\Framework\Attributes\Test] public function moveShouldThrowAnExceptionWhenInvalid(): void { $this->expectException(OutOfBoundsException::class); $this->stream->move(15); } #[\PHPUnit\Framework\Attributes\Test] public function seekShouldMoveTheCursorByRelativeOffset(): void { $this->stream->seek(4); $this->assertSame('3', $this->stream->getCurrentToken()->getValue()); } #[\PHPUnit\Framework\Attributes\Test] public function seekShouldThrowAnExceptionWhenInvalid(): void { $this->expectException(OutOfBoundsException::class); $this->stream->seek(15); } #[\PHPUnit\Framework\Attributes\Test] public function nextShouldMoveTheCursorOneTokenAhead(): void { $this->stream->next(); $this->assertSame('PLUS', $this->stream->getCurrentToken()->getType()); $this->stream->next(); $this->assertSame('5', $this->stream->getCurrentToken()->getValue()); } #[\PHPUnit\Framework\Attributes\Test] public function nextShouldThrowAnExceptionWhenAtTheEndOfTheStream(): void { $this->expectException(OutOfBoundsException::class); $this->stream->seek(4); $this->stream->next(); } } tests/Parser/ExampleGrammar.php000064400000000407146412213010012550 0ustar00is('a', 'b', 'c') ->is('x', 'y', 'z'); $this->start('Foo'); } } tests/Parser/GrammarTest.php000064400000002471146412213010012077 0ustar00grammar = new ExampleGrammar(); } #[\PHPUnit\Framework\Attributes\Test] public function ruleAlternativesShouldHaveTheSameName(): void { $rules = $this->grammar->getRules(); $this->assertSame('Foo', $rules[1]->getName()); $this->assertSame('Foo', $rules[2]->getName()); } #[\PHPUnit\Framework\Attributes\Test] public function theGrammarShouldBeAugmentedWithAStartRule(): void { $this->assertSame( Grammar::START_RULE_NAME, $this->grammar->getStartRule()->getName() ); $this->assertSame( array('Foo'), $this->grammar->getStartRule()->getComponents() ); } #[\PHPUnit\Framework\Attributes\Test] public function shouldReturnAlternativesGroupedByName(): void { $rules = $this->grammar->getGroupedRules(); $this->assertCount(2, $rules['Foo']); } #[\PHPUnit\Framework\Attributes\Test] public function nonterminalsShouldBeDetectedFromRuleNames(): void { $this->assertTrue($this->grammar->hasNonterminal('Foo')); } } tests/Parser/LALR1/Analysis/AnalyzerTest.php000064400000014066146412213010014677 0ustar00is('a', 'S', 'b') ->is(); $grammar->start('S'); $result = $this->getAnalysisResult($grammar); $table = $result->getAutomaton()->getTransitionTable(); $this->assertSame(1, $table[0]['S']); $this->assertSame(2, $table[0]['a']); $this->assertSame(2, $table[2]['a']); $this->assertSame(3, $table[2]['S']); $this->assertSame(4, $table[3]['b']); } #[\PHPUnit\Framework\Attributes\Test] public function lookaheadShouldBeCorrectlyPumped(): void { $grammar = new Grammar(); $grammar('S') ->is('A', 'B', 'C', 'D'); $grammar('A') ->is('a'); $grammar('B') ->is('b'); $grammar('C') ->is(/* empty */); $grammar('D') ->is('d'); $grammar->start('S'); $automaton = $this->getAnalysisResult($grammar)->getAutomaton(); $this->assertSame( array(Parser::EOF_TOKEN_TYPE), $automaton->getState(1)->get(0, 1)->getLookahead() ); $this->assertSame( array('b'), $automaton->getState(3)->get(2, 1)->getLookahead() ); $this->assertSame( array('d'), $automaton->getState(4)->get(4, 0)->getLookahead() ); $this->assertSame( array('d'), $automaton->getState(5)->get(3, 1)->getLookahead() ); $this->assertSame( array(Parser::EOF_TOKEN_TYPE), $automaton->getState(7)->get(1, 4)->getLookahead() ); $this->assertSame( array(Parser::EOF_TOKEN_TYPE), $automaton->getState(8)->get(5, 1)->getLookahead() ); } #[\PHPUnit\Framework\Attributes\Test] public function parseTableShouldBeCorrectlyBuilt(): void { $grammar = new Grammar(); $grammar('S') ->is('a', 'S', 'b') ->is(/* empty */); $grammar->start('S'); $table = $this->getAnalysisResult($grammar)->getParseTable(); // shift(2) $this->assertSame(2, $table['action'][0]['a']); // reduce(S -> ) $this->assertSame(-2, $table['action'][0][Parser::EOF_TOKEN_TYPE]); // accept $this->assertSame(0, $table['action'][1][Parser::EOF_TOKEN_TYPE]); // shift(2) $this->assertSame(2, $table['action'][2]['a']); // reduce(S -> ) $this->assertSame(-2, $table['action'][2]['b']); // shift(4) $this->assertSame(4, $table['action'][3]['b']); // reduce(S -> a S b) $this->assertSame(-1, $table['action'][4]['b']); $this->assertSame(-1, $table['action'][4][Parser::EOF_TOKEN_TYPE]); $this->assertSame(1, $table['goto'][0]['S']); $this->assertSame(3, $table['goto'][2]['S']); } #[\PHPUnit\Framework\Attributes\Test] public function unexpectedConflictsShouldThrowAnException(): void { $grammar = new Grammar(); $grammar('S') ->is('a', 'b', 'C', 'd') ->is('a', 'b', 'E', 'd'); $grammar('C') ->is(/* empty */); $grammar('E') ->is(/* empty */); $grammar->start('S'); try { $this->getAnalysisResult($grammar); $this->fail('Expected an exception warning of a reduce/reduce conflict.'); } catch(ReduceReduceConflictException $e) { $this->assertSame(3, $e->getStateNumber()); $this->assertSame('d', $e->getLookahead()); $this->assertSame(3, $e->getFirstRule()->getNumber()); $this->assertSame(4, $e->getSecondRule()->getNumber()); } } #[\PHPUnit\Framework\Attributes\Test] public function expectedConflictsShouldBeRecorded(): void { $grammar = new Grammar(); $grammar('S') ->is('S', 'S', 'S') ->is('S', 'S') ->is('b'); $grammar->resolve(Grammar::ALL); $grammar->start('S'); $conflicts = $this->getAnalysisResult($grammar)->getResolvedConflicts(); $this->assertCount(4, $conflicts); $conflict = $conflicts[0]; $this->assertSame(3, $conflict['state']); $this->assertSame('b', $conflict['lookahead']); $this->assertSame(2, $conflict['rule']->getNumber()); $this->assertSame(Grammar::SHIFT, $conflict['resolution']); $conflict = $conflicts[1]; $this->assertSame(4, $conflict['state']); $this->assertSame('b', $conflict['lookahead']); $this->assertSame(1, $conflict['rule']->getNumber()); $this->assertSame(Grammar::SHIFT, $conflict['resolution']); $conflict = $conflicts[2]; $this->assertSame(4, $conflict['state']); $this->assertSame(Parser::EOF_TOKEN_TYPE, $conflict['lookahead']); $this->assertSame(1, $conflict['rules'][0]->getNumber()); $this->assertSame(2, $conflict['rules'][1]->getNumber()); $this->assertSame(Grammar::LONGER_REDUCE, $conflict['resolution']); $conflict = $conflicts[3]; $this->assertSame(4, $conflict['state']); $this->assertSame('b', $conflict['lookahead']); $this->assertSame(2, $conflict['rule']->getNumber()); $this->assertSame(Grammar::SHIFT, $conflict['resolution']); } protected function getAnalysisResult(Grammar $grammar): AnalysisResult { return $this->getAnalyzer()->analyze($grammar); } protected function getAnalyzer(): Analyzer { if ($this->analyzer === null) { $this->analyzer = new Analyzer(); } return $this->analyzer; } } tests/Parser/LALR1/Analysis/AutomatonTest.php000064400000001663146412213010015060 0ustar00automaton = new Automaton(); $this->automaton->addState(new State(0, [])); $this->automaton->addState(new State(1, [])); } #[\PHPUnit\Framework\Attributes\Test] public function addingATransitionShouldBeVisibleInTheTransitionTable(): void { $this->automaton->addTransition(0, 'a', 1); $table = $this->automaton->getTransitionTable(); $this->assertSame(1, $table[0]['a']); } #[\PHPUnit\Framework\Attributes\Test] public function aNewStateShouldBeIdentifiedByItsNumber(): void { $state = new State(2, []); $this->automaton->addState($state); $this->assertSame($state, $this->automaton->getState(2)); } } tests/Parser/LALR1/Analysis/ItemTest.php000064400000004041146412213010014000 0ustar00assertSame('b', $item->getActiveComponent()); } #[\PHPUnit\Framework\Attributes\Test] public function itemShouldBeAReduceItemIfAllComponentsHaveBeenEncountered(): void { $item = new Item(new Rule(1, 'A', ['a', 'b', 'c']), 1); $this->assertFalse($item->isReduceItem()); $item = new Item(new Rule(1, 'A', ['a', 'b', 'c']), 3); $this->assertTrue($item->isReduceItem()); } #[\PHPUnit\Framework\Attributes\Test] public function itemShouldPumpLookaheadIntoConnectedItems(): void { $item1 = new Item(new Rule(1, 'A', ['a', 'b', 'c']), 1); $item2 = new Item(new Rule(1, 'A', ['a', 'b', 'c']), 2); $item1->connect($item2); $item1->pump('d'); $this->assertContains('d', $item2->getLookahead()); } #[\PHPUnit\Framework\Attributes\Test] public function itemShouldPumpTheSameLookaheadOnlyOnce(): void { $item1 = new Item(new Rule(1, 'A', ['a', 'b', 'c']), 1); // Refactor item2 for phpunit 9 $item2 = $this->getMockBuilder(Item::class) ->setConstructorArgs([ new Rule(1, 'A', ['a', 'b', 'c']), 2, ]) ->getMock(); $item2->expects($this->once()) ->method('pump') ->with('d'); $item1->connect($item2); $item1->pump('d'); $item1->pump('d'); } #[\PHPUnit\Framework\Attributes\Test] public function getUnrecognizedComponentsShouldReturnAllComponentAfterTheDottedOne(): void { $item = new Item(new Rule(1, 'A', ['a', 'b', 'c']), 1); $this->assertSame(['c'], $item->getUnrecognizedComponents()); } } tests/Parser/LALR1/Analysis/KernelSet/KernelSetTest.php000064400000001663146412213010016701 0ustar00assertSame(array(1, 3, 6, 7), KernelSet::hashKernel(array( array(2, 1), array(1, 0), array(2, 0), array(3, 0), ))); } #[\PHPUnit\Framework\Attributes\Test] public function insertShouldInsertANewNodeIfNoIdenticalKernelExists(): void { $set = new KernelSet(); $this->assertSame(0, $set->insert([ [2, 1], ])); $this->assertSame(1, $set->insert([ [2, 2], ])); $this->assertSame(2, $set->insert([ [1, 1], ])); $this->assertSame(0, $set->insert([ [2, 1], ])); } } tests/Parser/LALR1/Analysis/StateTest.php000064400000001144146412213010014163 0ustar00assertSame($item1, $state->get(1, 0)); $item2 = new Item(new Rule(2, 'T', ['T', '+', 'F']), 0); $state->add($item2); $this->assertSame($item2, $state->get(2, 0)); } } tests/Parser/LALR1/ArithGrammar.php000064400000002120146412213010013031 0ustar00is('Expr', '+', 'Expr') ->call(fn($l, $_, $r) => $l + $r) ->is('Expr', '-', 'Expr') ->call(fn($l, $_, $r) => $l - $r) ->is('Expr', '*', 'Expr') ->call(fn($l, $_, $r) => $l * $r) ->is('Expr', '/', 'Expr') ->call(fn($l, $_, $r) => $l / $r) ->is('Expr', '**', 'Expr') ->call(fn($l, $_, $r) => pow($l, $r)) ->is('(', 'Expr', ')') ->call(fn($r, $e, $_) => $e) ->is('-', 'Expr')->prec(4) ->call(fn($_, $e) => -$e) ->is('INT') ->call(fn($i) => (int)$i->getValue()); $this->operators('+', '-')->left()->prec(1); $this->operators('*', '/')->left()->prec(2); $this->operators('**')->right()->prec(3); $this->start('Expr'); } } tests/Parser/LALR1/ArithLexer.php000064400000000760146412213010012532 0ustar00regex('INT', '/^[1-9][0-9]*/'); $this->token('('); $this->token(')'); $this->token('+'); $this->token('-'); $this->token('**'); $this->token('*'); $this->token('/'); $this->regex('WSP', "/^[ \r\n\t]+/"); $this->skip('WSP'); } } tests/Parser/LALR1/Dumper/AutomatonDumperTest.php000064400000001722146412213010015702 0ustar00analyze(new ExampleGrammar())->getAutomaton(); $this->dumper = new AutomatonDumper($automaton); } #[\PHPUnit\Framework\Attributes\Test] public function dumpDumpsTheEntireAutomaton(): void { $this->assertStringEqualsFile( __DIR__ . '/res/graphviz/automaton.dot', $this->dumper->dump() ); } #[\PHPUnit\Framework\Attributes\Test] public function dumpStateDumpsOnlyTheSpecifiedStateAndTransitions(): void { $this->assertStringEqualsFile( __DIR__ . '/res/graphviz/state.dot', $this->dumper->dumpState(2) ); } } tests/Parser/LALR1/Dumper/DebugTableDumperTest.php000064400000001214146412213010015725 0ustar00analyze($grammar); $dumper = new DebugTableDumper($grammar); $dumped = $dumper->dump($result->getParseTable()); $this->assertStringEqualsFile(__DIR__ . '/res/table/debug.php', $dumped); } } tests/Parser/LALR1/Dumper/ExampleGrammar.php000064400000000453146412213010014620 0ustar00is('a', 'S', 'b') ->is(/* empty */); $this->start('S'); } } tests/Parser/LALR1/Dumper/ProductionTableDumperTest.php000064400000001206146412213010017026 0ustar00analyze($grammar)->getParseTable(); $dumper = new ProductionTableDumper(); $dumped = $dumper->dump($table); $this->assertStringEqualsFile(__DIR__ . '/res/table/production.php', $dumped); } } tests/Parser/LALR1/Dumper/res/graphviz/automaton.dot000064400000000755146412213010016354 0ustar00digraph Automaton { rankdir="LR"; 0 [label="State 0\n\n• S\nS → • a S b\nS → • [$eof]"]; 1 [label="State 1\n\nS • [$eof]"]; 2 [label="State 2\n\nS → a • S b\nS → • a S b\nS → • [b]"]; 3 [label="State 3\n\nS → a S • b"]; 4 [label="State 4\n\nS → a S b • [$eof b]"]; 0 -> 1 [label="S"]; 0 -> 2 [label="a"]; 2 -> 3 [label="S"]; 2 -> 2 [label="a"]; 3 -> 4 [label="b"]; } tests/Parser/LALR1/Dumper/res/graphviz/state.dot000064400000000316146412213010015456 0ustar00digraph State2 { rankdir="LR"; 2 [label="State 2\n\nS → a • S b\nS → • a S b\nS → • [b]"]; 3 [label="State 3"]; 2 -> 3 [label="S"]; 2 -> 2 [label="a"]; } tests/Parser/LALR1/Dumper/res/table/debug.php000064400000001656146412213010014672 0ustar00 [ 0 => [ // on a shift and go to state 2 'a' => 2, // on $eof reduce by rule S -> /* empty */ '$eof' => -2, ], 1 => [ // on $eof accept the input '$eof' => 0, ], 2 => [ // on a shift and go to state 2 'a' => 2, // on b reduce by rule S -> /* empty */ 'b' => -2, ], 3 => [ // on b shift and go to state 4 'b' => 4, ], 4 => [ // on $eof reduce by rule S -> a S b '$eof' => -1, // on b reduce by rule S -> a S b 'b' => -1, ], ], 'goto' => [ 0 => [ // on S go to state 1 'S' => 1, ], 2 => [ // on S go to state 3 'S' => 3, ], ], ]; tests/Parser/LALR1/Dumper/res/table/production.php000064400000000245146412213010015763 0ustar00[0=>['a'=>2,'$eof'=>-2,],2=>['a'=>2,'b'=>-2,],3=>['b'=>4,],1=>['$eof'=>0,],4=>['$eof'=>-1,'b'=>-1,],],'goto'=>[0=>['S'=>1,],2=>['S'=>3,],]]; tests/Parser/LALR1/ParserTest.php000064400000003112146412213010012551 0ustar00lexer = new ArithLexer(); $this->parser = new Parser(new ArithGrammar()); } #[\PHPUnit\Framework\Attributes\Test] public function parserShouldProcessTheTokenStreamAndUseGrammarCallbacksForReductions(): void { $this->assertSame(-2, $this->parser->parse($this->lexer->lex( '-1 - 1'))); $this->assertSame(11664, $this->parser->parse($this->lexer->lex( '6 ** (1 + 1) ** 2 * (5 + 4)'))); $this->assertSame(-4, $this->parser->parse($this->lexer->lex( '3 - 5 - 2'))); $this->assertSame(262144, $this->parser->parse($this->lexer->lex( '4 ** 3 ** 2'))); } #[\PHPUnit\Framework\Attributes\Test] public function parserShouldThrowAnExceptionOnInvalidInput(): void { try { $this->parser->parse($this->lexer->lex('6 ** 5 3')); $this->fail('Expected an UnexpectedTokenException.'); } catch (UnexpectedTokenException $e) { $this->assertSame('INT', $e->getToken()->getType()); $this->assertSame(array('$eof', '+', '-', '*', '/', '**', ')'), $e->getExpected()); $this->assertSame(<<getMessage()); } } } tests/Parser/RuleTest.php000064400000000637146412213010011422 0ustar00assertSame('y', $r->getComponent(1)); $this->assertNull($r->getComponent(2)); } } tests/bootstrap.php000064400000000407146412213010010427 0ustar00add('Dissect', __DIR__);