vovan-ve/lr0-parser

LR(0) parser with state table generator for any LR(0) grammar

v2.0.1 2018-10-30 02:26 UTC

Requires

• php: ^7.1
• ext-json: *
• lib-pcre: *
• vovan-ve/array-dumper: ~1.0.0

Requires (Dev)

• phpunit/phpunit: ^7.0

MIT

• Vovan-VE

README

This package contains LR(0) parser to parse texts according to custom LR(0) grammar.

Synopsis

See also following example in examples/.

use VovanVE\parser\actions\ActionsMadeMap;
use VovanVE\parser\Parser;

$grammar = <<<'_END'
    Goal        : Sum $
    Sum(add)    : Sum "+" Product
    Sum(sub)    : Sum "-" Product
    Sum(P)      : Product
    Product(mul): Product "*" Value
    Product(div): Product "/" Value
    Product(V)  : Value
    Value(neg)  : "-" Value
    Value       : "+" Value
    Value       : "(" Sum ")"
    Value       : int
    int         : /\d+/

    -ws         : /\s+/
    -mod        : 'u'
_END;

$parser = new Parser($grammar);

$actions = new ActionsMadeMap([
    'int' => function ($content) { return (int)$content; },

    'Value' => Parser::ACTION_BUBBLE_THE_ONLY,
    'Value(neg)' => function ($v) { return -$v; },

    'Product(V)' => Parser::ACTION_BUBBLE_THE_ONLY,
    'Product(mul)' => function ($a, $b) { return $a * $b; },
    'Product(div)' => function ($a, $b) { return $a / $b; },

    'Sum(P)' => Parser::ACTION_BUBBLE_THE_ONLY,
    'Sum(add)' => function ($a, $b) { return $a + $b; },
    'Sum(sub)' => function ($a, $b) { return $a - $b; },
]);

$tree = $parser->parse('2 * (-10 + 33) - 4', $actions);

echo 'Result is ', $tree->made(), PHP_EOL;
echo 'Tree:', PHP_EOL;
echo $tree->dumpAsString();

Output:

Result is 42
Tree:
 `- Sum(sub)
     `- Sum(P)
     |   `- Product(mul)
     |       `- Product(V)
     |       |   `- Value
     |       |       `- int <2>
     |       `- Value
     |           `- Sum(add)
     |               `- Sum(P)
     |               |   `- Product(V)
     |               |       `- Value(neg)
     |               |           `- Value
     |               |               `- int <10>
     |               `- Product(V)
     |                   `- Value
     |                       `- int <33>
     `- Product(V)
         `- Value
             `- int <4>

Description

This package contains:

• Lexer to parse input string into tokens. There is separate Lexer configurable by regexps.
• Grammar object to describe a grammar of a language.
• Parsing table to let parser to switch states with respect to grammar.
• LR(0) parser itself. It parse input string for AST using the table.

First this package was made just to apply the theory in practice. It may easily be used for small grammars to parse small source codes. But later I did apply it in my another package.

Installation

Install through composer:

composer require vovan-ve/lr0-parser

or add to require section in your composer.json:

"vovan-ve/lr0-parser": "~2.0.0"

Theory

LR parser.

License

This package is under MIT License