.gitignore 0000644 00000000044 14476011371 0006536 0 ustar 00 vendor/
composer.phar
composer.lock
.travis.yml 0000644 00000000216 14476011371 0006660 0 ustar 00 language: php
php:
- 5.3
- 5.4
before_script:
- wget http://getcomposer.org/composer.phar
- php composer.phar dump-autoload
CHANGELOG.md 0000644 00000000243 14476011371 0006360 0 ustar 00 Changelog
=========
1.0.1 (2013-01-29)
------------------
- 2b40f94: Fixed an invalid format in the CLI
1.0.0 (2013-01-15)
------------------
- First release.
README.md 0000644 00000001227 14476011371 0006031 0 ustar 00 # Welcome to Dissect!
- [master](https://github.com/jakubledl/dissect/tree/master) [](https://travis-ci.org/jakubledl/dissect) - this branch always contains the last stable version.
- [develop](https://github.com/jakubledl/dissect) [](https://travis-ci.org/jakubledl/dissect) - the unstable development branch.
Dissect is a set of tools for lexical and syntactical analysis written
in pure PHP.
Documentation?
--------------
[Here][docs].
[docs]: https://github.com/jakubledl/dissect/blob/master/docs/index.md
TODO.md 0000644 00000000712 14476011371 0005637 0 ustar 00 Goals
=====
1.1
---
- Optional operator precedence support (à la *yacc*, *bison*).
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) - ✔
UNLICENSE 0000644 00000002256 14476011371 0006025 0 ustar 00 This is free and unencumbered software released into the public domain.
Anyone is free to copy, modify, publish, use, compile, sell, or
distribute this software, either in source code form or as a compiled
binary, for any purpose, commercial or non-commercial, and by any
means.
In jurisdictions that recognize copyright laws, the author
of this software dedicates any and all copyright interest in the
software to the public domain. I make this dedication for the benefit
of the public at large and to the detriment of our heirs and
successors. I intend this dedication to be an overt act of
relinquishment in perpetuity of all present and future rights to this
software under copyright law.
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 NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHOR 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.
For more information, please refer to
bin/dissect 0000755 00000000074 14476011371 0006705 0 ustar 00 #!/usr/bin/env php
run();
composer.json 0000644 00000001223 14476011371 0007270 0 ustar 00 {
"name": "jakubledl/dissect",
"description": "Lexing and parsing in pure PHP",
"keywords": ["lexing", "parsing", "ast", "parser"],
"homepage": "https://github.com/jakubledl/dissect",
"license": "unlicense",
"authors": [
{
"name": "Jakub Lédl",
"email": "jakubledl@gmail.com"
}
],
"require": {
"php": ">=5.3.3"
},
"require-dev": {
"symfony/console": "~2.1"
},
"suggest": {
"symfony/console": "for the command-line tool"
},
"bin": ["bin/dissect.php", "bin/dissect"],
"autoload": {
"psr-0": { "Dissect": ["src/"] }
}
}
docs/ast.md 0000644 00000007447 14476011371 0006625 0 ustar 00 Building 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.md 0000644 00000005620 14476011371 0006574 0 ustar 00 The 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:
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.md 0000644 00000005141 14476011371 0007313 0 ustar 00 Describing 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')
...
```
Expressions
-----------
A grammar for very basic mathematical expressions is described in the
[chapter on parsing][arith]. It would require extensive modifications to allow
for other operators, function calls, unary operators, ternary
operator(s), but there's a lot of grammars for practical programming
languages on the internet that you can take inspiration from.
For starters, 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.md 0000644 00000003361 14476011371 0007134 0 ustar 00 Welcome 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)
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.md 0000644 00000012766 14476011371 0007324 0 ustar 00 Lexical analysis with Dissect
=============================
There are two classes for lexical analysis in Dissect, both under the
namespace `Dissect\Lexer`: `SimpleLexer` and `StatefulLexer`.
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 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.
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/Dissect/Lexer/TokenStream/TokenStream.php
[parsing]: parsing.md
docs/parsing.md 0000644 00000024551 14476011371 0007474 0 ustar 00 Parsing 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();
```
There's more to specifying mathematical expression than would seem,
because there are two concepts to consider:
1. Operator precedence
2. Operator associativity
The operator problem is usually solved in these steps:
1. Create a hierarchy of your operators.
2. Start creating rules from the lowest-precedence one to the
highest-precedence one, each "level" will reference rules
in the one above it.
3. The highest operator will reference an atomic, nondividable
expression, which in our case is an `INT` or a parenthesised
expression.
The lowest-precedence operator in our grammar is `+`, so we will start
with two rules for `Additive`:
```php
$this('Additive')
->is('Additive', '+', 'Multiplicative')
->call(function ($l, $_, $r) {
return $l + $r;
})
->is('Multiplicative');
```
Here we say "an additive expression is an additive expression plus a
multiplicative expression, or simply a multiplicative expression.
Note that we've taken care of associativity too: the first rule for
`Additive` is left-recursive, which means that an input like this:
2 + 7 + 3
will be interpreted as
(2 + 7) + 3
which is exactly what we want to achieve.
Let's take care of `Multiplicative` the same way:
```php
$this('Multiplicative')
->is('Multiplicative', '*', 'Power')
->call(function ($l, $_, $r) {
return $l * $r;
})
->is('Power');
```
Again, we'll do the same for `Power`, but notice that we've made it
right-recursive, since when we say
2 ** 3 ** 4
we want it to mean
2 ** (3 ** 4)
```php
$this('Power')
->is('Primary', '**', 'Power')
->call(function ($l, $_, $r) {
return pow($left, $right);
})
->is('Primary');
```
We've reached the highest-precedence operator, so now we have to define
what a `Primary` expression is:
```php
$this('Primary')
->is('(', 'Additive', ')')
->call(function ($_, $e, $_) {
return $e;
})
->is('INT')
->call(function ($int) {
return (int)$int->getValue();
});
```
Note that the callback for the last rule recieves a token, that is, a
`Dissect\Lexer\Token` object, so we have to "unwrap" the value from it.
Now we just specify a start rule:
```php
$this->start('Additive');
```
and parse away:
```php
use Dissect\Parser\LALR1\Parser;
$parser = new Parser(new ArithGrammar());
$stream = $lexer->lex('6 ** (1 + 1) ** 2 * (5 + 4)');
echo $parser->parse($stream);
// => 11664
```
### 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 3 commonly used ways of resolving such conflicts and Dissect allows you to
combine them any way you want:
1. On a shift/reduce conflict, always shift. This is represented by
the constant `Grammar::SHIFT` and is so common that Dissect enables
it by default.
2. 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.
3. 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::LONGER_REDUCE);
```
There are two other constants: `Grammar::NONE` that forbids any
conflicts in the grammar and `Grammar::ALL`, which is a combination
of all the 3 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.png 0000644 00000036340 14476011371 0007556 0 ustar 00 PNG
IHDR K n bKGD IDATxw\SOv3B@r "SeBq -8X
jW+uU*(ZŁ" ) ! rsOr_{r ((x @ R* Qd!E* Qd!E* Qd߾}g kkk @n·SԮ. 0l;d1 p * 2 OaX+Ν;7oD* kWTT<~fIIIXϰ~gҥK'O>~A (3`b2PᠻL&S(N@PfX# ̰vA ps @PP֎@ 3L҉D"IIIqppSVV2~A (3L'|cǎ>7D!}82L}82L
@pD!b 6477644X, sss"q~fx]uuuqqqgϞN>}z@@ٳxhQ˥ֶe33={_|ɓ'7nylmm]Jp#FؿGGyyysp-jkkPPOOӧO
sʵkn/m!O.\^|ׅ7 իW\.ӳR B RE[n}w{///{ PXWVVN>=>>
.UUUvvvΝC=D6(¹\i*++?.ᖒ۷oϘ1 .D=Df(ccc/^SGGGɭ]6..HSSSrk,Q@7775*$$$&&---f:r*!c{ehTUU_ ?^XXMD6(Z lݺu(r$ Z Q>̙3x<~ʕp?s粳/^d]]] 6t+@Evp'N̟?_EEEOp
_~)%ޫVN t@BAAQg2{ AC QxVVք #J?7rG! TP/ϟ?;wkkk9 NKK Fh4
4rH===%%%GEEرlp
onn...0aB߿+))))))..f2555]]]TSS777 3f̘1cF mggw9J]n]CC A#rjo #FKNN)q !!!qqq/_622ڶm/0[ꦦW^ 4immݴiL{@ׯ_R([cTxԩSq8˛v2,^,k$ãkw絴LLL/c+++ }:fggL݁(2x߰a@8q R TUUVH]ׯ'+R$!#E,[D"]tIz(*l6ohiiiXHQ۶mqqqҫBaXXHk>ɓG Yb4X,̙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*** 8 N__JfCђ*<55:wIRRRSPP㝜&O|ϟˠG ZݻwǏ *oAAAnn. Ǐ gfffdddeedkkk{{{{{{333CCCccc&aEeee~e~~>RVV8q
*$K^͛'YQ?BBB֖rJdϹ .))_6l A|e˰r`QZZziӦQ( 1c,Xpї/_X,Օ}ȑQF ( :d2QDXt)F!111S#wo7777nP;BͶmېx ! $x=w\PP:a 8p*W'OxsPFHTٳg 5k _ڥ Y(JBBH̙3d
!D"QUU5<<<--Mn(h"痚J]1bfΜ)b`ggWXzyyy
!H#F
_}JJJG ȁLn}(//WVV駟vD`X ?k̙3nnn IxWS+J-))nr
*EP.]Z\\ܧ@!:^VVqe _ݿXuuNPPP}}-[ | G
<-O?TZZ É366&ϟ?#ʚ7o H4119{9QxCCN_~xU.]@ X) = [j //"3|tvvwYUn:4&:
̹s玝 @XxFd '⥲GVՕ' ?~ȬƂ x x :t֖u)fddgN hkk&qHNN ۠n
A|___ @XXo$HHDVxaa!Hާ|nhh LKK AƳgp8իWvDvp8͛7pŋ755a,SXXn._|DH Cz a2VVV?Dbo$ZSxb ;w"qMw LPP0[ZZ|}})ʩSE ?~L& {.cZ3//o7 ӵkr}樨(di1S,;;@ H={4++Os)...))?~|``(H$ #33k_ÇӦM\Rgee RSS%
Lr)ShjjN:ǽ YYY=|uHCC#44dΝ;WUU5::O1.`nn_\.w4baHoRB秡+}/^ ~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/ܹኊDZDEE 9RnC
%_cdžKc%<< ,xiDa2x<^7.**JB#;}_Xr%֛7o/ Dᵵd2(
>>>~~~ҮEfCjjj'NV9 · N: g嵄 ?~\CCA~1؆"$^zUlh # y 2쿈u cҤI(mmmǎ ^MEOOJG,V߾} (r└ cTTT(Hfyҳ/xh]LLL+9w
066% {4))IUUf ̛7 ?~q-X`ʕUUUW\R]'IwÇ 3f D"+Gɓ' ˗/ X!8 @jj 74 CB nرc͛d2_|9zh қV%%%#*@ \x-' 0k,<4" >|ϟ7nܨN&-,,v)K0
sΑHE? ?PRRx 44-$=== >|۷L@,X0j(EZƃ
]]]Ƌ-
h} df%Lё榪~xFF\E)(( \tiHl6;11 U8{//_>eeH1LJ76mbiax葯/377?x`CC FCCCLLp̻ ƬgxݻF
^}||x 9rx/rEAAAXXJP(AAAl6kfoܸHP %7WS("G ; 7n 8 "}Ν+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̪ `ĈF IDAT)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>͐s XK?Uw7n+W 0 CvÇSNUUU2 ?5kȑ#dfpppMM iVz oE :O2&L 6:^VVqe _-B T*]:::$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+** 8 N__ybeen$Aӽ.]*GEAAƌ`G|bƇ#G5
@PO~!)}i}~'T @zz: `AAAcǎ UUU77UV:u˗b,% տ+NCC#88uuuXrΝ
Br 8p
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߾=vX qb4Ax(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ߎ" gpF A˲]~:`JKK CʼnAmEDbP(7ABbdgggV!Z[[t-[$12Gssq#dlݺ˗UUU>>> QFdA 7nlooѣKB7a&I"$W❎D G ڭ-6W\nh{S G:>PSSS{ZmA@ /b D ;w
D!===T*Y Hs45}! r \{nTrqqqJJJC'%%%C>C{Jhd>]n `߾}O* -;@~~~ȧH [633n,^ի@䍄< #1nܸ, ij 읦H$r{(MMbdd( ѿ'OpSN!3KKK> zohmmUUU=x Z7 pvv_s1&f0,ӧkOl@"YSSӬ>Ugff<4GkkߑH斖/_>nܸ!Ir_x x!֎ɇ x%12G]]
O1.`nn_\.ϒU 9< Beeep\!քXXX\zuA3̧Ob,\Džf 3fӧ|,MWKԑn~Bk}ϒS^^N$%䓢""HÇoHwT+͛8 N6o͜0d QOOOri4bLBnnP"^y===_|loV7RxSS4[beeSqܦ&KKK777Dx 1 nr(1tAyyb7sPZZZ\]]
>| W^OOCBB$m<߃BLፍ
܁xr<9͞zzz;w H,))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")dAפkr~~~ K.
f'&&:;; ,`0֬Y#ACIU---
LB =z <ЀGcff$̾( idn|:h5*|ƍVH
¨T*B
JMM6}ƍ@
^XX(Y<6&_ U)333+++///// @"
MMM̌ pT*UIIg XWWW___SSSWWW^^d2L l6 UKKKmT "K 8p 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_[[ٳPAZqwwwmx^ ӳ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--M65E8 Ndd$@8~8־@%dX~-L>y* B477S($}(x lٲgϞ 9rD"ɬv9`֬YH
[[[݁(^f͚/^p yI222! 9sdff=yD g֭_}_~ahhGE]JǏvrr4i/|RSS3mڴ} =zܹsHFe hΨ B ?~\CCZ`x ?tttzzzG,_| ? ;v, Ao1\.bmF"\\\&INp8 \
r-D"EGG? ;::^ kP&;;uʕX{ȅlll222Μ9s% #GX,B%K899hׯ_ 8p@UUk "nڴIYY4..nfTرcv2 G#TWWYBXXX ?~ kDd]VMMX{ȯ>|zje˖
= sscǎuuuadX#
Gݲe N'~~~ ˛#@H{{{bbS222͛a/q@ .^ + > %(**KLL,))1223gϤId6F]VVvݛ7oqkʔ)AAAAAA$@0$#'''))ڵki... Ŋ\۷o={yR6yٳgϞ=[6!1
Q]]vΝ $ѣ̌z'v@CCCUUUiiKKKKJJ>}D&mll<==M0B QxoJJJJJJx+D
/E[[jooG2wuu p81c5LƬa(S[[d2kjj>~X]]][[pZZZl6RFQ(%%#G뛙 ΰP82luu!E* Qd f rQ{E IENDB` phpunit.xml 0000644 00000000647 14476011371 0006770 0 ustar 00
./tests
./src
src/Dissect/Console/Application.php 0000644 00000002451 14476011371 0013315 0 ustar 00
*/
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)
{
return 'dissect';
}
protected function getDefaultCommands()
{
$default = parent::getDefaultCommands();
$default[] = new Command\DissectCommand();
return $default;
}
public function getDefinition()
{
return new InputDefinition(array(
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/Dissect/Console/Command/DissectCommand.php 0000644 00000015415 14476011371 0015331 0 ustar 00 setName('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)
{
$class = strtr(
$input->getArgument('grammar-class'),
'/',
'\\'
);
$formatter = $this->getHelperSet()->get('formatter');
$output->writeln('Analyzing...');
$output->writeln('');
if (!class_exists($class)) {
$output->writeln(array(
$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();
$automaton = null;
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) {
$output->writeln(array(
$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)) {
$output->writeln(array(
$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)
{
$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/Dissect/Lexer/AbstractLexer.php 0000644 00000004567 14476011371 0013304 0 ustar 00
*/
abstract class AbstractLexer implements Lexer
{
/**
* @var int
*/
private $line = 1;
/**
* Returns the current line.
*
* @return int The current line.
*/
protected function getCurrentLine()
{
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.
*
* @return \Dissect\Lexer\Token|null The extracted token or null.
*/
abstract protected function extractToken($string);
/**
* Should given token be skipped?
*
* @param \Dissect\Lexer\Token $token The token to evaluate.
*
* @return boolean Whether to skip the token.
*/
abstract protected function shouldSkipToken(Token $token);
/**
* {@inheritDoc}
*/
public function lex($string)
{
// normalize line endings
$string = strtr($string, array("\r\n" => "\n", "\r" => "\n"));
$tokens = array();
$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/Dissect/Lexer/CommonToken.php 0000644 00000001726 14476011371 0012764 0 ustar 00
*/
class CommonToken implements Token
{
/**
* @var mixed
*/
protected $type;
/**
* @var string
*/
protected $value;
/**
* @var int
*/
protected $line;
/**
* Constructor.
*
* @param mixed $type The type of the token.
* @param string $value The token value.
* @param int $line The line.
*/
public function __construct($type, $value, $line)
{
$this->type = $type;
$this->value = $value;
$this->line = $line;
}
/**
* {@inheritDoc}
*/
public function getType()
{
return $this->type;
}
/**
* {@inheritDoc}
*/
public function getValue()
{
return $this->value;
}
/**
* {@inheritDoc}
*/
public function getLine()
{
return $this->line;
}
}
src/Dissect/Lexer/Exception/RecognitionException.php 0000644 00000001354 14476011371 0016625 0 ustar 00
*/
class RecognitionException extends RuntimeException
{
protected $sourceLine;
/**
* Constructor.
*
* @param int $line The line in the source.
*/
public function __construct($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()
{
return $this->sourceLine;
}
}
src/Dissect/Lexer/Lexer.php 0000644 00000001061 14476011371 0011602 0 ustar 00
*/
interface Lexer
{
/**
* Lexes the given string, returning a token stream.
*
* @param string $string The string to lex.
*
* @throws \Dissect\Lexer\Exception\RecognitionException
* When unable to extract more tokens from the string.
*
* @return \Dissect\Lexer\TokenStream\TokenStream The resulting token stream.
*/
public function lex($string);
}
src/Dissect/Lexer/Recognizer/Recognizer.php 0000644 00000001147 14476011371 0014746 0 ustar 00
*/
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, &$result);
}
src/Dissect/Lexer/Recognizer/RegexRecognizer.php 0000644 00000001345 14476011371 0015741 0 ustar 00
*/
class RegexRecognizer implements Recognizer
{
protected $regex;
/**
* Constructor.
*
* @param string $regex The regex to use in the match.
*/
public function __construct($regex)
{
$this->regex = $regex;
}
/**
* {@inheritDoc}
*/
public function match($string, &$result)
{
$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/Dissect/Lexer/Recognizer/SimpleRecognizer.php 0000644 00000001260 14476011371 0016114 0 ustar 00
*/
class SimpleRecognizer implements Recognizer
{
protected $string;
/**
* Constructor.
*
* @param string $string The string to match by.
*/
public function __construct($string)
{
$this->string = $string;
}
/**
* {@inheritDoc}
*/
public function match($string, &$result)
{
if (strncmp($string, $this->string, strlen($this->string)) === 0) {
$result = $this->string;
return true;
}
return false;
}
}
src/Dissect/Lexer/SimpleLexer.php 0000644 00000005040 14476011371 0012755 0 ustar 00
*/
class SimpleLexer extends AbstractLexer
{
/**
* @var array
*/
protected $skipTokens = array();
/**
* @var array
*/
protected $recognizers = array();
/**
* 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 $value The value to be recognized.
*
* @return \Dissect\Lexer\SimpleLexer This instance for fluent interface.
*/
public function token($type, $value = null)
{
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.
*
* @return \Dissect\Lexer\SimpleLexer This instance for fluent interface.
*/
public function regex($type, $regex)
{
$this->recognizers[$type] = new RegexRecognizer($regex);
return $this;
}
/**
* Marks the token types given as arguments to be skipped.
*
* @param mixed $type,... Unlimited number of token types.
*
* @return \Dissect\Lexer\SimpleLexer This instance for fluent interface.
*/
public function skip()
{
$this->skipTokens = func_get_args();
return $this;
}
/**
* {@inheritDoc}
*/
protected function shouldSkipToken(Token $token)
{
return in_array($token->getType(), $this->skipTokens);
}
/**
* {@inheritDoc}
*/
protected function extractToken($string)
{
$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/Dissect/Lexer/StatefulLexer.php 0000644 00000012641 14476011371 0013320 0 ustar 00
*/
class StatefulLexer extends AbstractLexer
{
protected $states = array();
protected $stateStack = array();
protected $stateBeingBuilt = null;
protected $typeBeingBuilt = null;
/**
* Signifies that no action should be taken on encountering a token.
*/
const NO_ACTION = 0;
/**
* Indicates that a state should be popped of the state stack on
* encountering a token.
*/
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 $value The value to be recognized.
*
* @return \Dissect\Lexer\SimpleLexer This instance for fluent interface.
*/
public function token($type, $value = null)
{
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.
*
* @return \Dissect\Lexer\SimpleLexer This instance for fluent interface.
*/
public function regex($type, $regex)
{
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 $type,... Unlimited number of token types.
*
* @return \Dissect\Lexer\SimpleLexer This instance for fluent interface.
*/
public function skip()
{
if ($this->stateBeingBuilt === null) {
throw new LogicException("Define a lexer state first.");
}
$this->states[$this->stateBeingBuilt]['skip_tokens'] = func_get_args();
return $this;
}
/**
* Registers a new lexer state.
*
* @param string $state The new state name.
*
* @return \Dissect\Lexer\SimpleLexer This instance for fluent interface.
*/
public function state($state)
{
$this->stateBeingBuilt = $state;
$this->states[$state] = array(
'recognizers' => array(),
'actions' => array(),
'skip_tokens' => array(),
);
return $this;
}
/**
* Sets the starting state for the lexer.
*
* @param string $state The name of the starting state.
*
* @return \Dissect\Lexer\SimpleLexer This instance for fluent interface.
*/
public function start($state)
{
$this->stateStack[] = $state;
return $this;
}
/**
* Sets an action for the token type that is currently being built.
*
* @param mixed $action The action to take.
*
* @return \Dissect\Lexer\SimpleLexer This instance for fluent interface.
*/
public function action($action)
{
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)
{
$state = $this->states[$this->stateStack[count($this->stateStack) - 1]];
return in_array($token->getType(), $state['skip_tokens']);
}
/**
* {@inheritDoc}
*/
protected function extractToken($string)
{
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) {
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/Dissect/Lexer/Token.php 0000644 00000001021 14476011371 0011577 0 ustar 00
*/
interface Token
{
/**
* Returns the token type.
*
* @return mixed The token type.
*/
public function getType();
/**
* Returns the token value.
*
* @return string The token value.
*/
public function getValue();
/**
* Returns the line on which the token was found.
*
* @return int The line.
*/
public function getLine();
}
src/Dissect/Lexer/TokenStream/ArrayTokenStream.php 0000644 00000004452 14476011371 0016221 0 ustar 00
*/
class ArrayTokenStream implements TokenStream
{
/**
* @var \Dissect\Lexer\Token[]
*/
protected $tokens;
/**
* @var int
*/
protected $position = 0;
/**
* Constructor.
*
* @param \Dissect\Lexer\Token[] $tokens The tokens in this stream.
*/
public function __construct(array $tokens)
{
$this->tokens = $tokens;
}
/**
* {@inheritDoc}
*/
public function getPosition()
{
return $this->position;
}
/**
* {@inheritDoc}
*/
public function getCurrentToken()
{
return $this->tokens[$this->position];
}
/**
* {@inheritDoc}
*/
public function lookAhead($n)
{
if (isset($this->tokens[$this->position + $n])) {
return $this->tokens[$this->position + $n];
}
throw new OutOfBoundsException('Invalid look-ahead.');
}
/**
* {@inheritDoc}
*/
public function get($n)
{
if (isset($this->tokens[$n])) {
return $this->tokens[$n];
}
throw new OutOfBoundsException('Invalid index.');
}
/**
* {@inheritDoc}
*/
public function move($n)
{
if (!isset($this->tokens[$n])) {
throw new OutOfBoundsException('Invalid index to move to.');
}
$this->position = $n;
}
/**
* {@inheritDoc}
*/
public function seek($n)
{
if (!isset($this->tokens[$this->position + $n])) {
throw new OutOfBoundsException('Invalid seek.');
}
$this->position += $n;
}
/**
* {@inheritDoc}
*/
public function next()
{
if (!isset($this->tokens[$this->position + 1])) {
throw new OutOfBoundsException('Attempting to move beyond the end of the stream.');
}
$this->position++;
}
/**
* @return int
*/
public function count()
{
return count($this->tokens);
}
/**
* @return \ArrayIterator
*/
public function getIterator()
{
return new ArrayIterator($this->tokens);
}
}
src/Dissect/Lexer/TokenStream/TokenStream.php 0000644 00000003402 14476011371 0015214 0 ustar 00
*/
interface TokenStream extends Countable, IteratorAggregate
{
/**
* Returns the current position in the stream.
*
* @return int The current position in the stream.
*/
public function getPosition();
/**
* Retrieves the current token.
*
* @return \Dissect\Lexer\Token The current token.
*/
public function getCurrentToken();
/**
* Returns a look-ahead token. Negative values are allowed
* and serve as look-behind.
*
* @param int $n The look-ahead.
*
* @throws \OutOfBoundsException If current position + $n is out of range.
*
* @return \Dissect\Lexer\Token The lookahead token.
*/
public function lookAhead($n);
/**
* Returns the token at absolute position $n.
*
* @param int $n The position.
*
* @throws \OutOfBoundsException If $n is out of range.
*
* @return \Dissect\Lexer\Token The token at position $n.
*/
public function get($n);
/**
* Moves the cursor to the absolute position $n.
*
* @param int $n The position.
*
* @throws \OutOfBoundsException If $n is out of range.
*/
public function move($n);
/**
* Moves the cursor by $n, relative to the current position.
*
* @param int $n The seek.
*
* @throws \OutOfBoundsException If current position + $n is out of range.
*/
public function seek($n);
/**
* Moves the cursor to the next token.
*
* @throws \OutOfBoundsException If at the end of the stream.
*/
public function next();
}
src/Dissect/Node/CommonNode.php 0000644 00000004453 14476011371 0012377 0 ustar 00
*/
class CommonNode implements Node
{
/**
* @var array
*/
protected $nodes;
/**
* @var array
*/
protected $attributes;
/**
* Constructor.
*
* @param array $attributes The attributes of this node.
* @param array $children The children of this node.
*/
public function __construct(array $attributes = array(), array $nodes = array())
{
$this->attributes = $attributes;
$this->nodes = $nodes;
}
/**
* {@inheritDoc}
*/
public function getNodes()
{
return $this->nodes;
}
/**
* {@inheritDoc}
*/
public function hasNode($key)
{
return isset($this->nodes[$key]);
}
/**
* {@inheritDoc}
*/
public function getNode($key)
{
if (!isset($this->children[$key])) {
throw new RuntimeException(sprintf('No child node "%s" exists.', $key));
}
return $this->nodes[$key];
}
/**
* {@inheritDoc}
*/
public function setNode($key, Node $child)
{
$this->children[$key] = $child;
}
/**
* {@inheritDoc}
*/
public function removeNode($key)
{
unset($this->children[$key]);
}
/**
* {@inheritDoc}
*/
public function getAttributes()
{
return $this->attributes;
}
/**
* {@inheritDoc}
*/
public function hasAttribute($key)
{
return isset($this->attributes[$key]);
}
/**
* {@inheritDoc}
*/
public function getAttribute($key)
{
if (!isset($this->attributes[$key])) {
throw new RuntimeException(sprintf('No attribute "%s" exists.', $key));
}
return $this->attributes[$key];
}
/**
* {@inheritDoc}
*/
public function setAttribute($key, $value)
{
$this->attributes[$key] = $value;
}
/**
* {@inheritDoc}
*/
public function removeAttribute($key)
{
unset($this->attributes[$key]);
}
public function count()
{
return count($this->children);
}
public function getIterator()
{
return new ArrayIterator($this->children);
}
}
src/Dissect/Node/Node.php 0000644 00000004224 14476011371 0011222 0 ustar 00
*/
interface Node extends Countable, IteratorAggregate
{
/**
* Returns the children of this node.
*
* @return array The children belonging to this node.
*/
public function getNodes();
/**
* 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($name);
/**
* Returns a child node specified by $name.
*
* @param int|string $name The name of the node.
*
* @return \Dissect\Node\Node The child node specified by $name.
*
* @throws \RuntimeException When no child node named $name exists.
*/
public function getNode($name);
/**
* Sets a child node.
*
* @param string $name The name.
* @param \Dissect\Node\Node $node The new child node.
*/
public function setNode($name, Node $child);
/**
* Removes a child node by name.
*
* @param string $name The name.
*/
public function removeNode($name);
/**
* Returns all attributes of this node.
*
* @return array The attributes.
*/
public function getAttributes();
/**
* 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($key);
/**
* 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($key);
/**
* Sets an attribute by key.
*
* @param string $key The key.
* @param mixed $value The new value.
*/
public function setAttribute($key, $value);
/**
* Removes an attribute by key.
*
* @param string $key The key.
*/
public function removeAttribute($key);
}
src/Dissect/Parser/Exception/UnexpectedTokenException.php 0000644 00000002774 14476011371 0017636 0 ustar 00
*/
class UnexpectedTokenException extends RuntimeException
{
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.
*
* @return \Dissect\Lexer\Token The unexpected token.
*/
public function getToken()
{
return $this->token;
}
/**
* Returns the expected token types.
*
* @return string[] The expected token types.
*/
public function getExpected()
{
return $this->expected;
}
}
src/Dissect/Parser/Grammar.php 0000644 00000011006 14476011371 0012266 0 ustar 00
*/
class Grammar
{
/**
* The name given to the rule the grammar is augmented with
* when start() is called.
*/
const START_RULE_NAME = '$start';
/**
* The epsilon symbol signifies an empty production.
*/
const EPSILON = '$epsilon';
/**
* @var \Dissect\Parser\Rule[]
*/
protected $rules = array();
/**
* @var array
*/
protected $groupedRules = array();
/**
* @var int
*/
protected $nextRuleNumber = 1;
/**
* @var int
*/
protected $conflictsMode = self::SHIFT;
/**
* @var string
*/
protected $currentNonterminal;
/**
* @var \Dissect\Parser\Rule
*/
protected $currentRule;
/**
* Signifies that the parser should not resolve any
* grammar conflicts.
*/
const NONE = 0;
/**
* Signifies that the parser should resolve
* shift/reduce conflicts by always shifting.
*/
const SHIFT = 1;
/**
* Signifies that the parser should resolve
* reduce/reduce conflicts by reducing with
* the longer rule.
*/
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.
*/
const EARLIER_REDUCE = 4;
/**
* Signifies that the parser should automatically
* resolve all grammar conflicts.
*/
const ALL = 7;
public function __invoke($nonterminal)
{
$this->currentNonterminal = $nonterminal;
return $this;
}
/**
* Defines an alternative for a grammar rule.
*
* @param string... The components of the rule.
*
* @return \Dissect\Parser\Grammar This instance.
*/
public function is()
{
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, func_get_args());
$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 \Dissect\Parser\Grammar This instance.
*/
public function call($callback)
{
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 \Dissect\Parser\Rule[] The rules.
*/
public function getRules()
{
return $this->rules;
}
public function getRule($number)
{
return $this->rules[$number];
}
/**
* Returns the nonterminal symbols of this grammar.
*
* @return string[] The nonterminals.
*/
public function getNonterminals()
{
return $this->nonterminals;
}
/**
* Returns rules grouped by nonterminal name.
*
* @return array The rules grouped by nonterminal name.
*/
public function getGroupedRules()
{
return $this->groupedRules;
}
/**
* Sets a start rule for this grammar.
*
* @param string The name of the start rule.
*/
public function start($name)
{
$this->rules[0] = new Rule(0, self::START_RULE_NAME, array($name));
}
/**
* Returns the augmented start rule. For internal use only.
*
* @return \Dissect\Parser\Rule The start rule.
*/
public function getStartRule()
{
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($mode)
{
$this->conflictsMode = $mode;
}
/**
* Returns the conflict resolution mode for this grammar.
*
* @return int The bitmask of the resolution mode.
*/
public function getConflictsMode()
{
return $this->conflictsMode;
}
}
src/Dissect/Parser/LALR1/Analysis/AnalysisResult.php 0000644 00000002714 14476011371 0016266 0 ustar 00
*/
class AnalysisResult
{
/**
* @var \Dissect\Parser\LALR1\Analysis\Automaton
*/
protected $automaton;
/**
* @var array
*/
protected $parseTable;
/**
* @var array
*/
protected $resolvedConflicts;
/**
* Constructor.
*
* @param array $parseTable The parse table.
* @param \Dissect\Parser\LALR1\Analysis\Automaton $automaton
* @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.
*
* @return \Dissect\Parser\LALR1\Analysis\Automaton
*/
public function getAutomaton()
{
return $this->automaton;
}
/**
* Returns the resulting parse table.
*
* @return array The parse table.
*/
public function getParseTable()
{
return $this->parseTable;
}
/**
* Returns an array of resolved parse table conflicts.
*
* @return array The conflicts.
*/
public function getResolvedConflicts()
{
return $this->resolvedConflicts;
}
}
src/Dissect/Parser/LALR1/Analysis/Analyzer.php 0000644 00000046173 14476011371 0015100 0 ustar 00
*/
class Analyzer
{
/**
* Performs a grammar analysis.
*
* @param \Dissect\Parser\Grammar $grammar The grammar to analyse.
*
* @return \Dissect\Parser\LALR1\Analysis\AnalysisResult The result ofthe analysis.
*/
public function analyze(Grammar $grammar)
{
$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 \Dissect\Parser\Grammar $grammar The grammar.
*
* @return \Dissect\Parser\LALR1\Analysis\Automaton The resulting automaton.
*/
protected function buildAutomaton(Grammar $grammar)
{
// the eventual automaton
$automaton = new Automaton();
// the queue of states that need processing
$queue = new SplQueue();
// holds the origins of different states.
// an origin is a map 'rule number' -> 'unsorted rule positions'
$origins = array();
// states are numbered sequentially
$nextStateNumber = 0;
// 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 = array();
// the item from which the whole automaton
// is deriveed
$initialItem = new Item($grammar->getStartRule(), 0);
// construct the initial state
$state = new State($nextStateNumber++, array($initialItem));
// the initial item automatically has EOF
// as its lookahead
$pumpings[] = array($initialItem, array(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 = array();
// calculate closure
$added = array();
$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 (array_key_exists($component, $groupedRules)) {
// calculate lookahead
$lookahead = array();
$cs = $item->getUnrecognizedComponents();
foreach ($cs as $i => $c) {
if (!array_key_exists($c, $groupedRules)) {
// if terminal, add it and break the loop
$lookahead = Util::union($lookahead, array($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[] = array($newItem, $lookahead);
}
}
}
// mark the component as processed
$added[] = $component;
}
}
// calculate transitions
foreach ($groupedItems as $thisComponent => $theseItems) {
$currentOrigin = array();
foreach ($theseItems as $thisItem) {
// calculate the origin of the state that
// would result by the transition from this
// state by $thisComponent
$currentOrigin[$thisItem->getRule()->getNumber()][] =
$thisItem->getDotIndex();
}
$n = null;
foreach ($origins as $number => $map) {
$match = true;
// the origins match iff the rules are same
foreach ($currentOrigin as $ruleNum => $positions) {
if (count($currentOrigin) !== count($map)
|| !isset($map[$ruleNum])
// the comparison of positions is order-insensitive
|| (array_diff($map[$ruleNum], $positions) !== array_diff($positions, $map[$ruleNum]))) {
$match = false;
break;
}
}
if ($match) {
// if there was a match, the state already exists
// and is identified by $number
$n = $number;
break;
}
}
if ($n === null) {
// no match, we have to create a new state
$num = $nextStateNumber++;
$newState = new State($num, array_map(function (Item $i) {
$new = new Item($i->getRule(), $i->getDotIndex() + 1);
// if there's a transition from state a to state b by
// x, the rules A -> foo . x in state a and
// A -> foo x . in state b are connected
$i->connect($new);
return $new;
}, $theseItems));
$automaton->addState($newState);
$queue->enqueue($newState);
// store the origin of the new state
$origins[$num] = $currentOrigin;
$automaton->addTransition($state->getNumber(), $thisComponent, $num);
} else {
// if there was a match, we have to extract
// the following items from the existing state
$automaton->addTransition($state->getNumber(), $thisComponent, $n);
// which is this one
$nextState = $automaton->getState($n);
foreach ($theseItems as $thisItem) {
$thisItem->connect(
$nextState->get(
$thisItem->getRule()->getNumber(),
$thisItem->getDotIndex() + 1
)
);
}
}
}
}
// 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.
*
* @param \Dissect\Parser\LALR1\Analysis\Automaton $automaton
*
* @return array The parse table.
*/
protected function buildParseTable(Automaton $automaton, Grammar $grammar)
{
$nonterminals = array_keys($grammar->getGroupedRules());
$conflictsMode = $grammar->getConflictsMode();
$conflicts = array();
// initialize the table
$table = array(
'action' => array(),
'goto' => array(),
);
foreach ($automaton->getTransitionTable() as $num => $transitions) {
foreach ($transitions as $trigger => $destination) {
if (!in_array($trigger, $nonterminals)) {
// 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] = array();
}
foreach ($state->getItems() as $item) {
if ($item->isReduceItem()) {
$ruleNumber = $item->getRule()->getNumber();
foreach ($item->getLookahead() as $token) {
if (array_key_exists($token, $table['action'][$num])) {
// conflict
$instruction = $table['action'][$num][$token];
if ($instruction > 0) {
// s/r
if ($conflictsMode & Grammar::SHIFT) {
$conflicts[] = array(
'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 = array($originalRule, $newRule);
$conflicts[] = array(
'state' => $num,
'lookahead' => $token,
'rules' => $resolvedRules,
'resolution' => Grammar::LONGER_REDUCE,
);
continue;
} elseif ($count2 > $count1) {
// new rule is longer
$table['action'][$num][$token] = -$ruleNumber;
$resolvedRules = array($newRule, $originalRule);
$conflicts[] = array(
'state' => $num,
'lookahead' => $token,
'rules' => $resolvedRules,
'resolution' => Grammar::LONGER_REDUCE,
);
continue;
}
}
if ($conflictsMode & Grammar::EARLIER_REDUCE) {
if (-$instruction < $ruleNumber) {
// original rule was earlier
$resolvedRules = array($originalRule, $newRule);
$conflicts[] = array(
'state' => $num,
'lookahead' => $token,
'rules' => $resolvedRules,
'resolution' => Grammar::EARLIER_REDUCE,
);
continue;
} else {
// new rule was earlier
$table['action'][$num][$token] = -$ruleNumber;
$conflicts[] = array(
'state' => $num,
'lookahead' => $token,
'rules' => $resolvedRules,
'resolution' => Grammar::EARLIER_REDUCE,
);
$resolvedRules = array($newRule, $originalRule);
continue;
}
}
// everything failed, throw an exception
throw new ReduceReduceConflictException(
$num,
$originalRule,
$newRule,
$token,
$automaton
);
}
}
$table['action'][$num][$token] = -$ruleNumber;
}
}
}
}
return array($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)
{
// initialize
$firstSets = array();
foreach (array_keys($rules) as $lhs) {
$firstSets[$lhs] = array();
}
do {
$changes = false;
foreach ($rules as $lhs => $ruleArray) {
foreach ($ruleArray as $rule) {
$components = $rule->getComponents();
$new = array();
if (empty($components)) {
$new = array(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, array($component));
break;
}
}
}
if (Util::different($new, $firstSets[$lhs])) {
$firstSets[$lhs] = Util::union($firstSets[$lhs], $new);
$changes = true;
}
}
}
} while ($changes);
return $firstSets;
}
}
src/Dissect/Parser/LALR1/Analysis/Automaton.php 0000644 00000003445 14476011371 0015255 0 ustar 00
*/
class Automaton
{
/**
* @var array
*/
protected $states = array();
/**
* @var array
*/
protected $transitionTable = array();
/**
* Adds a new automaton state.
*
* @param \Dissect\Parser\LALR1\Analysis\State $state The new state.
*/
public function addState(State $state)
{
$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($origin, $label, $dest)
{
$this->transitionTable[$origin][$label] = $dest;
}
/**
* Returns a state by its number.
*
* @param int $number The state number.
*
* @return \Dissect\Parser\LALR1\Analysis\State The requested state.
*/
public function getState($number)
{
return $this->states[$number];
}
/**
* Does this automaton have a state identified by $number?
*
* @return boolean
*/
public function hasState($number)
{
return isset($this->states[$number]);
}
/**
* Returns all states in this FSA.
*
* @return array The states of this FSA.
*/
public function getStates()
{
return $this->states;
}
/**
* Returns the transition table for this automaton.
*
* @return array The transition table.
*/
public function getTransitionTable()
{
return $this->transitionTable;
}
}
src/Dissect/Parser/LALR1/Analysis/Exception/ConflictException.php 0000644 00000001671 14476011371 0020663 0 ustar 00
*/
class ConflictException extends LogicException
{
protected $state;
protected $automaton;
public function __construct($message, $state, Automaton $automaton)
{
parent::__construct($message);
$this->state = $state;
$this->automaton = $automaton;
}
/**
* Returns the number of the inadequate state.
*
* @return int
*/
public function getStateNumber()
{
return $this->state;
}
/**
* Returns the faulty automaton.
*
* @return \Dissect\Parser\LALR1\Analysis\Automaton
*/
public function getAutomaton()
{
return $this->automaton;
}
}
src/Dissect/Parser/LALR1/Analysis/Exception/ReduceReduceConflictException.php 0000644 00000005263 14476011371 0023144 0 ustar 00
*/
class ReduceReduceConflictException extends ConflictException
{
/**
* The exception message template.
*/
const MESSAGE = << %s
vs:
%d. %s -> %s
(on lookahead "%s" in state %d). Restructure your grammar or choose a conflict resolution mode.
EOT;
/**
* @var \Dissect\Parser\Rule
*/
protected $firstRule;
/**
* @var \Dissect\Parser\Rule
*/
protected $secondRule;
/**
* @var string
*/
protected $lookahead;
/**
* Constructor.
*
* @param int $state The number of the inadequate state.
* @param \Dissect\Parser\Rule $firstRule The first conflicting grammar rule.
* @param \Dissect\Parser\Rule $secondRule The second conflicting grammar rule.
* @param string $lookahead The conflicting lookahead.
* @param \Dissect\Parser\LALR1\Analysis\Automaton $automaton The faulty automaton.
*/
public function __construct($state, Rule $firstRule, Rule $secondRule, $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 \Dissect\Parser\Rule The first conflicting rule.
*/
public function getFirstRule()
{
return $this->firstRule;
}
/**
* Returns the second conflicting rule.
*
* @return \Dissect\Parser\Rule The second conflicting rule.
*/
public function getSecondRule()
{
return $this->secondRule;
}
/**
* Returns the conflicting lookahead.
*
* @return string The conflicting lookahead.
*/
public function getLookahead()
{
return $this->lookahead;
}
}
src/Dissect/Parser/LALR1/Analysis/Exception/ShiftReduceConflictException.php 0000644 00000003623 14476011371 0023010 0 ustar 00
*/
class ShiftReduceConflictException extends ConflictException
{
/**
* The exception message template.
*/
const MESSAGE = << %s
(on lookahead "%s" in state %d). Restructure your grammar or choose a conflict resolution mode.
EOT;
/**
* @var \Dissect\Parser\Rule
*/
protected $rule;
/**
* @var string
*/
protected $lookahead;
/**
* Constructor.
*
* @param \Dissect\Parser\Rule $rule The conflicting grammar rule.
* @param string $lookahead The conflicting lookahead to shift.
* @param \Dissect\Parser\LALR1\Analysis\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 \Dissect\Parser\Rule The conflicting rule.
*/
public function getRule()
{
return $this->rule;
}
/**
* Returns the conflicting lookahead.
*
* @return string The conflicting lookahead.
*/
public function getLookahead()
{
return $this->lookahead;
}
}
src/Dissect/Parser/LALR1/Analysis/Item.php 0000644 00000007107 14476011371 0014203 0 ustar 00
* 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
*/
class Item
{
/**
* @var \Dissect\Parser\Rule
*/
protected $rule;
/**
* @var int
*/
protected $dotIndex;
/**
* @var array
*/
protected $lookahead = array();
/**
* @var array
*/
protected $connected = array();
/**
* Constructor.
*
* @param \Dissect\Parser\Rule $rule The rule of this item.
* @param int $dotIndex The index of the dot in this item.
*/
public function __construct(Rule $rule, $dotIndex)
{
$this->rule = $rule;
$this->dotIndex = $dotIndex;
}
/**
* Returns the dot index of this item.
*
* @return int The dot index.
*/
public function getDotIndex()
{
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()
{
return $this->rule->getComponent($this->dotIndex);
}
/**
* Returns the rule of this item.
*
* @return \Dissect\Parser\Rule The rule.
*/
public function getRule()
{
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()
{
return $this->dotIndex === count($this->rule->getComponents());
}
/**
* Connects two items with a lookahead pumping channel.
*
* @param \Dissect\Parser\LALR1\Analysis\Item $i The item.
*/
public function connect(Item $i)
{
$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($lookahead)
{
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)
{
foreach ($lookahead as $l) {
$this->pump($l);
}
}
/**
* Returns the computed lookahead for this item.
*
* @return string[] The lookahead symbols.
*/
public function getLookahead()
{
return $this->lookahead;
}
/**
* Returns all components that haven't been recognized
* so far.
*
* @return array The unrecognized components.
*/
public function getUnrecognizedComponents()
{
return array_slice($this->rule->getComponents(), $this->dotIndex + 1);
}
}
src/Dissect/Parser/LALR1/Analysis/State.php 0000644 00000003317 14476011371 0014364 0 ustar 00
*/
class State
{
/**
* @var array
*/
protected $items = array();
/**
* @var array
*/
protected $itemMap = array();
/**
* @var int
*/
protected $number;
/**
* Constructor.
*
* @param int $number The number identifying this state.
* @param array $items The initial items of this state.
*/
public function __construct($number, array $items)
{
$this->number = $number;
foreach ($items as $item) {
$this->add($item);
}
}
/**
* Adds a new item to this state.
*
* @param \Dissect\Parser\LALR1\Analysis\Item $item The new item.
*/
public function add(Item $item)
{
$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 \Dissect\Parser\LALR1\Analysis\Item The item.
*/
public function get($ruleNumber, $dotIndex)
{
return $this->itemMap[$ruleNumber][$dotIndex];
}
/**
* Returns the number identifying this state.
*
* @return int
*/
public function getNumber()
{
return $this->number;
}
/**
* Returns an array of items constituting this state.
*
* @return array The items.
*/
public function getItems()
{
return $this->items;
}
}
src/Dissect/Parser/LALR1/Dumper/AutomatonDumper.php 0000644 00000010000 14476011371 0016064 0 ustar 00
*/
class AutomatonDumper
{
protected $automaton;
/**
* Constructor.
*
* @param \Dissect\Parser\LALR1\Analysis\Automaton $automaton
*/
public function __construct(Automaton $automaton)
{
$this->automaton = $automaton;
}
/**
* Dumps the entire automaton.
*
* @return string The automaton encoded in DOT.
*/
public function dump()
{
$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($n)
{
$writer = new StringWriter();
$this->writeHeader($writer, $n);
$writer->writeLine();
$this->writeState($writer, $this->automaton->getState($n));
$table = $this->automaton->getTransitionTable();
$row = isset($table[$n]) ? $table[$n] : array();
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)
{
$writer->writeLine(sprintf(
'digraph %s {',
$stateNumber ? 'State' . $stateNumber : 'Automaton'
));
$writer->indent();
$writer->writeLine('rankdir="LR";');
}
protected function writeState(StringWriter $writer, State $state, $full = true)
{
$n = $state->getNumber();
$string = sprintf(
'%d [label="State %d',
$n,
$n
);
if ($full) {
$string .= '\n\n';
$items = array();
foreach ($state->getItems() as $item) {
$items[] = $this->formatItem($item);
}
$string .= implode('\n', $items);
}
$string .= '"];';
$writer->writeLine($string);
}
protected function formatItem(Item $item)
{
$rule = $item->getRule();
$components = $rule->getComponents();
// the dot
array_splice($components, $item->getDotIndex(), 0, array('•'));
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)
{
$writer->writeLine('}');
}
}
src/Dissect/Parser/LALR1/Dumper/DebugTableDumper.php 0000644 00000010471 14476011371 0016127 0 ustar 00
*/
class DebugTableDumper implements TableDumper
{
/**
* @var \Dissect\Parser\Grammar
*/
protected $grammar;
/**
* @var \Dissect\Parser\LALR1\Dumper\StringWriter
*/
protected $writer;
/**
* @var boolean
*/
protected $written = false;
/**
* Constructor.
*
* @param \Dissect\Parser\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)
{
// 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 array(');
$this->writer->indent();
$this->writer->writeLine("'action' => array(");
}
protected function writeState($n, array $state)
{
$this->writer->writeLine((string)$n . ' => array(');
$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' => array(");
}
protected function writeGoto($n, array $map)
{
$this->writer->writeLine((string)$n . ' => array(');
$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/Dissect/Parser/LALR1/Dumper/ProductionTableDumper.php 0000644 00000004154 14476011371 0017230 0 ustar 00
*/
class ProductionTableDumper implements TableDumper
{
/**
* {@inheritDoc}
*/
public function dump(array $table)
{
$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("array(");
}
protected function writeState(StringWriter $writer, $num, $state)
{
$writer->write((string)$num . '=>array(');
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'=>array(");
}
protected function writeGoto(StringWriter $writer, $num, $map)
{
$writer->write((string)$num . '=>array(');
foreach ($map as $trigger => $destination) {
$writer->write(sprintf(
"'%s'=>%d",
$trigger,
$destination
));
$writer->write(',');
}
$writer->write(')');
}
protected function writeOutro(StringWriter $writer)
{
$writer->write('));');
}
}
src/Dissect/Parser/LALR1/Dumper/StringWriter.php 0000644 00000002634 14476011371 0015421 0 ustar 00
*/
class StringWriter
{
protected $indent = 0;
protected $string = '';
/**
* Appends the given string.
*
* @param string $string The string to write.
*/
public function write($string)
{
$this->string .= $string;
}
/**
* Gets the string as written so far.
*
* @return string The string.
*/
public function get()
{
return $this->string;
}
/**
* Adds a level of indentation.
*/
public function indent()
{
$this->indent++;
}
/**
* Removes a level of indentation.
*/
public function outdent()
{
$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 $string The string to write.
*/
public function writeLine($string = null)
{
if ($string) {
$this->write(sprintf(
"%s%s\n",
str_repeat(' ', $this->indent * 4),
$string
));
} else {
$this->write("\n");
}
}
}
src/Dissect/Parser/LALR1/Dumper/TableDumper.php 0000644 00000000607 14476011371 0015160 0 ustar 00
*/
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);
}
src/Dissect/Parser/LALR1/Parser.php 0000644 00000005313 14476011371 0012753 0 ustar 00
*/
class Parser implements P\Parser
{
/**
* @var \Dissect\Parser\Grammar
*/
protected $grammar;
/**
* @var array
*/
protected $parseTable;
/**
* Constructor.
*
* @param \Dissect\Parser\Grammar $grammar The grammar.
* @param array $parseTable If given, the parser doesn't have to analyze the grammar.
*/
public function __construct(P\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)
{
$stateStack = array($currentState = 0);
$args = array();
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];
}
}
}
}
}
src/Dissect/Parser/Parser.php 0000644 00000001076 14476011371 0012142 0 ustar 00
*/
interface Parser
{
/**
* The token type that represents an EOF.
*/
const EOF_TOKEN_TYPE = '$eof';
/**
* Parses a token stream and returns the semantical value
* of the input.
*
* @param \Dissect\Lexer\TokenStream\TokenStream $stream The token stream.
*
* @return mixed The semantical value of the input.
*/
public function parse(TokenStream $stream);
}
src/Dissect/Parser/Rule.php 0000644 00000004036 14476011371 0011614 0 ustar 00
*/
class Rule
{
/**
* @var int
*/
protected $number;
/**
* @var string
*/
protected $name;
/**
* @var string[]
*/
protected $components;
/**
* @var callable
*/
protected $callback = 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($number, $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()
{
return $this->number;
}
/**
* Returns the name of this rule.
*
* @return string The name of this rule.
*/
public function getName()
{
return $this->name;
}
/**
* Returns the components of this rule.
*
* @return string[] The components of this rule.
*/
public function getComponents()
{
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($index)
{
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($callback)
{
$this->callback = $callback;
}
public function getCallback()
{
return $this->callback;
}
}
src/Dissect/Util/Util.php 0000644 00000003345 14476011371 0011305 0 ustar 00
*/
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()
{
return array_unique(call_user_func_array('array_merge', func_get_args()));
}
/**
* 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)
{
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($str)
{
return strlen(utf8_decode($str));
}
/**
* 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 $length The length of the substring.
*
* @return string The substring.
*/
public static function substring($str, $position, $length = null)
{
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/Dissect/Lexer/AbstractLexerTest.php 0000644 00000004315 14476011371 0014506 0 ustar 00 lexer = new StubLexer();
}
/**
* @test
*/
public function lexShouldDelegateToExtractTokenUpdatingTheLineAndOffsetAccordingly()
{
$stream = $this->lexer->lex("ab\nc");
$this->assertEquals('a', $stream->getCurrentToken()->getValue());
$this->assertEquals(1, $stream->getCurrentToken()->getLine());
$stream->next();
$this->assertEquals('b', $stream->getCurrentToken()->getValue());
$this->assertEquals(1, $stream->getCurrentToken()->getLine());
$stream->next();
$this->assertEquals("\n", $stream->getCurrentToken()->getValue());
$this->assertEquals(1, $stream->getCurrentToken()->getLine());
$stream->next();
$this->assertEquals('c', $stream->getCurrentToken()->getValue());
$this->assertEquals(2, $stream->getCurrentToken()->getLine());
}
/**
* @test
*/
public function lexShouldAppendAnEofTokenAutomatically()
{
$stream = $this->lexer->lex("abc");
$stream->seek(3);
$this->assertEquals(Parser::EOF_TOKEN_TYPE, $stream->getCurrentToken()->getType());
$this->assertEquals(1, $stream->getCurrentToken()->getLine());
}
/**
* @test
*/
public function lexShouldThrowAnExceptionOnAnUnrecognizableToken()
{
try {
$stream = $this->lexer->lex("abcd");
$this->fail('Expected a RecognitionException.');
} catch (RecognitionException $e) {
$this->assertEquals(1, $e->getSourceLine());
}
}
/**
* @test
*/
public function lexShouldNormalizeLineEndingsBeforeLexing()
{
$stream = $this->lexer->lex("a\r\nb");
$this->assertEquals("\n", $stream->get(1)->getValue());
}
/**
* @test
*/
public function lexShouldSkipTokensIfToldToDoSo()
{
$stream = $this->lexer->lex('aeb');
$this->assertNotEquals('e', $stream->get(1)->getType());
}
}
tests/Dissect/Lexer/Recognizer/RegexRecognizerTest.php 0000644 00000002111 14476011371 0017144 0 ustar 00 match('lorem ipsum', $value);
$this->assertTrue($result);
$this->assertNotNull($value);
$this->assertEquals('lorem', $value);
}
/**
* @test
*/
public function recognizerShouldFailAndTheValueShouldStayNull()
{
$recognizer = new RegexRecognizer('/[a-z]+/');
$result = $recognizer->match('123 456', $value);
$this->assertFalse($result);
$this->assertNull($value);
}
/**
* @test
*/
public function recognizerShouldFailIfTheMatchIsNotAtTheBeginningOfTheString()
{
$recognizer = new RegexRecognizer('/[a-z]+/');
$result = $recognizer->match('234 class', $value);
$this->assertFalse($result);
$this->assertNull($value);
}
}
tests/Dissect/Lexer/Recognizer/SimpleRecognizerTest.php 0000644 00000001430 14476011371 0017326 0 ustar 00 match('class lorem ipsum', $value);
$this->assertTrue($result);
$this->assertNotNull($value);
$this->assertEquals('class', $value);
}
/**
* @test
*/
public function recognizerShouldFailAndTheValueShouldStayNull()
{
$recognizer = new SimpleRecognizer('class');
$result = $recognizer->match('lorem ipsum', $value);
$this->assertFalse($result);
$this->assertNull($value);
}
}
tests/Dissect/Lexer/SimpleLexerTest.php 0000644 00000003131 14476011371 0014167 0 ustar 00 lexer = new SimpleLexer();
$this->lexer
->token('A', 'a')
->token('(')
->token('B', 'b')
->token(')')
->token('C', 'c')
->regex('WS', "/[ \n\t\r]+/")
->skip('WS');
}
/**
* @test
*/
public function simpleLexerShouldWalkThroughTheRecognizers()
{
$stream = $this->lexer->lex('a (b) c');
$this->assertEquals(6, $stream->count()); // with EOF
$this->assertEquals('(', $stream->get(1)->getType());
$this->assertEquals(1, $stream->get(3)->getLine());
$this->assertEquals('C', $stream->get(4)->getType());
}
/**
* @test
*/
public function simpleLexerShouldSkipSpecifiedTokens()
{
$stream = $this->lexer->lex('a (b) c');
foreach ($stream as $token) {
$this->assertNotEquals('WS', $token->getType());
}
}
/**
* @test
*/
public function simpleLexerShouldReturnTheBestMatch()
{
$this->lexer->token('CLASS', 'class');
$this->lexer->regex('WORD', '/[a-z]+/');
$stream = $this->lexer->lex('class classloremipsum');
$this->assertEquals('CLASS', $stream->getCurrentToken()->getType());
$this->assertEquals('WORD', $stream->lookAhead(1)->getType());
}
}
tests/Dissect/Lexer/StatefulLexerTest.php 0000644 00000004053 14476011371 0014531 0 ustar 00 lexer = new StatefulLexer();
}
/**
* @test
* @expectedException LogicException
* @expectedExceptionMessage Define a lexer state first.
*/
public function addingNewTokenShouldThrowAnExceptionWhenNoStateIsBeingBuilt()
{
$this->lexer->regex('WORD', '/[a-z]+/');
}
/**
* @test
* @expectedException LogicException
*/
public function anExceptionShouldBeThrownOnLexingWithoutAStartingState()
{
$this->lexer->state('root');
$this->lexer->lex('foo');
}
/**
* @test
*/
public function theStateMechanismShouldCorrectlyPushAndPopStatesFromTheStack()
{
$this->lexer->state('root')
->regex('WORD', '/[a-z]+/')
->regex('WS', "/[ \r\n\t]+/")
->token('"')->action('string')
->skip('WS');
$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->assertEquals('STRING_CONTENTS', $stream->get(3)->getType());
$this->assertEquals('long \\" string', $stream->get(3)->getValue());
$this->assertEquals('quux', $stream->get(6)->getValue());
}
/**
* @test
*/
public function defaultActionShouldBeNop()
{
$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->assertEquals(3, $stream->count());
}
}
tests/Dissect/Lexer/StubLexer.php 0000644 00000001025 14476011371 0013013 0 ustar 00 getCurrentLine());
return $token;
}
protected function shouldSkipToken(Token $t)
{
return $t->getType() === 'e';
}
}
tests/Dissect/Lexer/TokenStream/ArrayTokenStreamTest.php 0000644 00000005725 14476011371 0017440 0 ustar 00 stream = new ArrayTokenStream(array(
new CommonToken('INT', '6', 1, 1),
new CommonToken('PLUS', '+', 1, 3),
new CommonToken('INT', '5', 1, 5),
new CommonToken('MINUS', '-', 1, 7),
new CommonToken('INT', '3', 1, 9),
));
}
/**
* @test
*/
public function theCursorShouldBeOnFirstTokenByDefault()
{
$this->assertEquals('6', $this->stream->getCurrentToken()->getValue());
}
/**
* @test
*/
public function getPositionShouldReturnCurrentPosition()
{
$this->stream->seek(2);
$this->stream->next();
$this->assertEquals(3, $this->stream->getPosition());
}
/**
* @test
*/
public function lookAheadShouldReturnTheCorrectToken()
{
$this->assertEquals('5', $this->stream->lookAhead(2)->getValue());
}
/**
* @test
* @expectedException OutOfBoundsException
*/
public function lookAheadShouldThrowAnExceptionWhenInvalid()
{
$this->stream->lookAhead(15);
}
/**
* @test
*/
public function getShouldReturnATokenByAbsolutePosition()
{
$this->assertEquals('3', $this->stream->get(4)->getValue());
}
/**
* @test
* @expectedException OutOfBoundsException
*/
public function getShouldThrowAnExceptionWhenInvalid()
{
$this->stream->get(15);
}
/**
* @test
*/
public function moveShouldMoveTheCursorByToAnAbsolutePosition()
{
$this->stream->move(2);
$this->assertEquals('5', $this->stream->getCurrentToken()->getValue());
}
/**
* @test
* @expectedException OutOfBoundsException
*/
public function moveShouldThrowAnExceptionWhenInvalid()
{
$this->stream->move(15);
}
/**
* @test
*/
public function seekShouldMoveTheCursorByRelativeOffset()
{
$this->stream->seek(4);
$this->assertEquals('3', $this->stream->getCurrentToken()->getValue());
}
/**
* @test
* @expectedException OutOfBoundsException
*/
public function seekShouldThrowAnExceptionWhenInvalid()
{
$this->stream->seek(15);
}
/**
* @test
*/
public function nextShouldMoveTheCursorOneTokenAhead()
{
$this->stream->next();
$this->assertEquals('PLUS', $this->stream->getCurrentToken()->getType());
$this->stream->next();
$this->assertEquals('5', $this->stream->getCurrentToken()->getValue());
}
/**
* @test
* @expectedException OutOfBoundsException
*/
public function nextShouldThrowAnExceptionWhenAtTheEndOfTheStream()
{
$this->stream->seek(4);
$this->stream->next();
}
}
tests/Dissect/Parser/ExampleGrammar.php 0000644 00000000355 14476011371 0014162 0 ustar 00 is('a', 'b', 'c')
->is('x', 'y', 'z');
$this->start('Foo');
}
}
tests/Dissect/Parser/GrammarTest.php 0000644 00000002054 14476011371 0013504 0 ustar 00 grammar = new ExampleGrammar();
}
/**
* @test
*/
public function ruleAlternativesShouldHaveTheSameName()
{
$rules = $this->grammar->getRules();
$this->assertEquals('Foo', $rules[1]->getName());
$this->assertEquals('Foo', $rules[2]->getName());
}
/**
* @test
*/
public function theGrammarShouldBeAugmentedWithAStartRule()
{
$this->assertEquals(
Grammar::START_RULE_NAME,
$this->grammar->getStartRule()->getName()
);
$this->assertEquals(
array('Foo'),
$this->grammar->getStartRule()->getComponents()
);
}
/**
* @test
*/
public function shouldReturnAlternativesGroupedByName()
{
$rules = $this->grammar->getGroupedRules();
$this->assertCount(2, $rules['Foo']);
}
}
tests/Dissect/Parser/LALR1/Analysis/AnalyzerTest.php 0000644 00000014011 14476011371 0016275 0 ustar 00 is('a', 'S', 'b')
->is();
$grammar->start('S');
$result = $this->getAnalysisResult($grammar);
$table = $result->getAutomaton()->getTransitionTable();
$this->assertEquals(1, $table[0]['S']);
$this->assertEquals(2, $table[0]['a']);
$this->assertEquals(2, $table[2]['a']);
$this->assertEquals(3, $table[2]['S']);
$this->assertEquals(4, $table[3]['b']);
}
/**
* @test
*/
public function lookaheadShouldBeCorrectlyPumped()
{
$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->assertEquals(
array(Parser::EOF_TOKEN_TYPE),
$automaton->getState(1)->get(0, 1)->getLookahead()
);
$this->assertEquals(
array('b'),
$automaton->getState(3)->get(2, 1)->getLookahead()
);
$this->assertEquals(
array('d'),
$automaton->getState(4)->get(4, 0)->getLookahead()
);
$this->assertEquals(
array('d'),
$automaton->getState(5)->get(3, 1)->getLookahead()
);
$this->assertEquals(
array(Parser::EOF_TOKEN_TYPE),
$automaton->getState(7)->get(1, 4)->getLookahead()
);
$this->assertEquals(
array(Parser::EOF_TOKEN_TYPE),
$automaton->getState(8)->get(5, 1)->getLookahead()
);
}
/**
* @test
*/
public function parseTableShouldBeCorrectlyBuilt()
{
$grammar = new Grammar();
$grammar('S')
->is('a', 'S', 'b')
->is(/* empty */);
$grammar->start('S');
$table = $this->getAnalysisResult($grammar)->getParseTable();
// shift(2)
$this->assertEquals(2, $table['action'][0]['a']);
// reduce(S -> )
$this->assertEquals(-2, $table['action'][0][Parser::EOF_TOKEN_TYPE]);
// accept
$this->assertEquals(0, $table['action'][1][Parser::EOF_TOKEN_TYPE]);
// shift(2)
$this->assertEquals(2, $table['action'][2]['a']);
// reduce(S -> )
$this->assertEquals(-2, $table['action'][2]['b']);
// shift(4)
$this->assertEquals(4, $table['action'][3]['b']);
// reduce(S -> a S b)
$this->assertEquals(-1, $table['action'][4]['b']);
$this->assertEquals(-1, $table['action'][4][Parser::EOF_TOKEN_TYPE]);
$this->assertEquals(1, $table['goto'][0]['S']);
$this->assertEquals(3, $table['goto'][2]['S']);
}
/**
* @test
*/
public function unexpectedConflictsShouldThrowAnException()
{
$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 {
$result = $this->getAnalysisResult($grammar);
$this->fail('Expected an exception warning of a reduce/reduce conflict.');
} catch(ReduceReduceConflictException $e) {
$this->assertEquals(3, $e->getStateNumber());
$this->assertEquals('d', $e->getLookahead());
$this->assertEquals(3, $e->getFirstRule()->getNumber());
$this->assertEquals(4, $e->getSecondRule()->getNumber());
}
}
/**
* @test
*/
public function expectedConflictsShouldBeRecorded()
{
$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->assertEquals(3, $conflict['state']);
$this->assertEquals('b', $conflict['lookahead']);
$this->assertEquals(2, $conflict['rule']->getNumber());
$this->assertEquals(Grammar::SHIFT, $conflict['resolution']);
$conflict = $conflicts[1];
$this->assertEquals(4, $conflict['state']);
$this->assertEquals('b', $conflict['lookahead']);
$this->assertEquals(1, $conflict['rule']->getNumber());
$this->assertEquals(Grammar::SHIFT, $conflict['resolution']);
$conflict = $conflicts[2];
$this->assertEquals(4, $conflict['state']);
$this->assertEquals(Parser::EOF_TOKEN_TYPE, $conflict['lookahead']);
$this->assertEquals(1, $conflict['rules'][0]->getNumber());
$this->assertEquals(2, $conflict['rules'][1]->getNumber());
$this->assertEquals(Grammar::LONGER_REDUCE, $conflict['resolution']);
$conflict = $conflicts[3];
$this->assertEquals(4, $conflict['state']);
$this->assertEquals('b', $conflict['lookahead']);
$this->assertEquals(2, $conflict['rule']->getNumber());
$this->assertEquals(Grammar::SHIFT, $conflict['resolution']);
}
protected function getAnalysisResult(Grammar $grammar)
{
return $this->getAnalyzer()->analyze($grammar);
}
protected function getAnalyzer()
{
if ($this->analyzer === null) {
$this->analyzer = new Analyzer();
}
return $this->analyzer;
}
}
tests/Dissect/Parser/LALR1/Analysis/AutomatonTest.php 0000644 00000001606 14476011371 0016465 0 ustar 00 automaton = new Automaton();
$this->automaton->addState(new State(0, array()));
$this->automaton->addState(new State(1, array()));
}
/**
* @test
*/
public function addingATransitionShouldBeVisibleInTheTransitionTable()
{
$this->automaton->addTransition(0, 'a', 1);
$table = $this->automaton->getTransitionTable();
$this->assertEquals(1, $table[0]['a']);
}
/**
* @test
*/
public function aNewStateShouldBeIdentifiedByItsNumber()
{
$state = new State(2, array());
$this->automaton->addState($state);
$this->assertSame($state, $this->automaton->getState(2));
}
}
tests/Dissect/Parser/LALR1/Analysis/ItemTest.php 0000644 00000003762 14476011371 0015421 0 ustar 00 assertEquals('b', $item->getActiveComponent());
}
/**
* @test
*/
public function itemShouldBeAReduceItemIfAllComponentsHaveBeenEncountered()
{
$item = new Item(new Rule(1, 'A', array('a', 'b', 'c')), 1);
$this->assertFalse($item->isReduceItem());
$item = new Item(new Rule(1, 'A', array('a', 'b', 'c')), 3);
$this->assertTrue($item->isReduceItem());
}
/**
* @test
*/
public function itemShouldPumpLookaheadIntoConnectedItems()
{
$item1 = new Item(new Rule(1, 'A', array('a', 'b', 'c')), 1);
$item2 = new Item(new Rule(1, 'A', array('a', 'b', 'c')), 2);
$item1->connect($item2);
$item1->pump('d');
$this->assertContains('d', $item2->getLookahead());
}
/**
* @test
*/
public function itemShouldPumpTheSameLookaheadOnlyOnce()
{
$item1 = new Item(new Rule(1, 'A', array('a', 'b', 'c')), 1);
$item2 = $this->getMock(
'Dissect\\Parser\\LALR1\\Analysis\\Item',
array('pump'),
array(
new Rule(1, 'A', array('a', 'b', 'c')),
2,
)
);
$item2->expects($this->once())
->method('pump')
->with($this->equalTo('d'));
$item1->connect($item2);
$item1->pump('d');
$item1->pump('d');
}
/**
* @test
*/
public function getUnrecognizedComponentsShouldReturnAllComponentAfterTheDottedOne()
{
$item = new Item(new Rule(1, 'A', array('a', 'b', 'c')), 1);
$this->assertEquals(array('c'), $item->getUnrecognizedComponents());
}
}
tests/Dissect/Parser/LALR1/Analysis/StateTest.php 0000644 00000001123 14476011371 0015570 0 ustar 00 assertSame($item1, $state->get(1, 0));
$item2 = new Item(new Rule(2, 'T', array('T', '+', 'F')), 0);
$state->add($item2);
$this->assertSame($item2, $state->get(2, 0));
}
}
tests/Dissect/Parser/LALR1/ArithGrammar.php 0000644 00000002037 14476011371 0014450 0 ustar 00 is('Additive', '+', 'Multiplicative')
->call(function ($l, $_, $r) {
return $l + $r;
})
->is('Multiplicative');
$this('Multiplicative')
->is('Multiplicative', '*', 'Power')
->call(function ($l, $_, $r) {
return $l * $r;
})
->is('Power');
$this('Power')
->is('Primary', '**', 'Power')
->call(function ($l, $_, $r) {
return pow($l, $r);
})
->is('Primary');
$this('Primary')
->is('INT')
->call(function ($i) {
return (int)$i->getValue();
})
->is('(', 'Additive', ')')
->call(function ($_, $e, $_) {
return $e;
});
$this->start('Additive');
}
}
tests/Dissect/Parser/LALR1/ArithLexer.php 0000644 00000000640 14476011371 0014137 0 ustar 00 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');
}
}
tests/Dissect/Parser/LALR1/Dumper/AutomatonDumperTest.php 0000644 00000001616 14476011371 0017314 0 ustar 00 analyze(new ExampleGrammar())->getAutomaton();
$this->dumper = new AutomatonDumper($automaton);
}
/**
* @test
*/
public function dumpDumpsTheEntireAutomaton()
{
$this->assertStringEqualsFile(
__DIR__ . '/res/graphviz/automaton.dot',
$this->dumper->dump()
);
}
/**
* @test
*/
public function dumpStateDumpsOnlyTheSpecifiedStateAndTransitions()
{
$this->assertStringEqualsFile(
__DIR__ . '/res/graphviz/state.dot',
$this->dumper->dumpState(2)
);
}
}
tests/Dissect/Parser/LALR1/Dumper/DebugTableDumperTest.php 0000644 00000001161 14476011371 0017336 0 ustar 00 analyze($grammar);
$dumper = new DebugTableDumper($grammar);
$dumped = $dumper->dump($result->getParseTable());
$this->assertStringEqualsFile(__DIR__ . '/res/table/debug.php', $dumped);
}
}
tests/Dissect/Parser/LALR1/Dumper/ExampleGrammar.php 0000644 00000000421 14476011371 0016223 0 ustar 00 is('a', 'S', 'b')
->is(/* empty */);
$this->start('S');
}
}
tests/Dissect/Parser/LALR1/Dumper/ProductionTableDumperTest.php 0000644 00000001153 14476011371 0020437 0 ustar 00 analyze($grammar)->getParseTable();
$dumper = new ProductionTableDumper();
$dumped = $dumper->dump($table);
$this->assertStringEqualsFile(__DIR__ . '/res/table/production.php', $dumped);
}
}
tests/Dissect/Parser/LALR1/Dumper/res/graphviz/automaton.dot 0000644 00000000755 14476011371 0017764 0 ustar 00 digraph 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/Dissect/Parser/LALR1/Dumper/res/graphviz/state.dot 0000644 00000000316 14476011371 0017066 0 ustar 00 digraph 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/Dissect/Parser/LALR1/Dumper/res/table/debug.php 0000644 00000001740 14476011371 0016274 0 ustar 00 array(
0 => array(
// on a shift and go to state 2
'a' => 2,
// on $eof reduce by rule S -> /* empty */
'$eof' => -2,
),
1 => array(
// on $eof accept the input
'$eof' => 0,
),
2 => array(
// on a shift and go to state 2
'a' => 2,
// on b reduce by rule S -> /* empty */
'b' => -2,
),
3 => array(
// on b shift and go to state 4
'b' => 4,
),
4 => array(
// on $eof reduce by rule S -> a S b
'$eof' => -1,
// on b reduce by rule S -> a S b
'b' => -1,
),
),
'goto' => array(
0 => array(
// on S go to state 1
'S' => 1,
),
2 => array(
// on S go to state 3
'S' => 3,
),
),
);
tests/Dissect/Parser/LALR1/Dumper/res/table/production.php 0000644 00000000327 14476011371 0017374 0 ustar 00 array(0=>array('a'=>2,'$eof'=>-2,),2=>array('a'=>2,'b'=>-2,),3=>array('b'=>4,),1=>array('$eof'=>0,),4=>array('$eof'=>-1,'b'=>-1,),),'goto'=>array(0=>array('S'=>1,),2=>array('S'=>3,),));
tests/Dissect/Parser/LALR1/ParserTest.php 0000644 00000002320 14476011371 0014161 0 ustar 00 lexer = new ArithLexer();
$this->parser = new Parser(new ArithGrammar());
}
/**
* @test
*/
public function parserShouldProcessTheTokenStreamAndUseGrammarCallbacksForReductions()
{
$this->assertEquals(11664, $this->parser->parse($this->lexer->lex(
'6 ** (1 + 1) ** 2 * (5 + 4)')));
}
/**
* @test
*/
public function parserShouldThrowAnExceptionOnInvalidInput()
{
try {
$this->parser->parse($this->lexer->lex('6 ** 5 3'));
$this->fail('Expected an UnexpectedTokenException.');
} catch (UnexpectedTokenException $e) {
$this->assertEquals('INT', $e->getToken()->getType());
$this->assertEquals(array('$eof', '+', '*', '**', ')'), $e->getExpected());
$this->assertEquals(<<getMessage());
}
}
}
tests/Dissect/Parser/RuleTest.php 0000644 00000000613 14476011371 0013024 0 ustar 00 assertEquals('y', $r->getComponent(1));
$this->assertNull($r->getComponent(2));
}
}
tests/bootstrap.php 0000644 00000000355 14476011371 0010443 0 ustar 00 add('Dissect', __DIR__);