<NME> AnalyzerTest.php
<BEF> ADDFILE
<MSG> Automaton builder

<DFF> @@ -0,0 +1,48 @@
+<?php
+
+namespace Dissect\Parser\LALR1\Analysis;
+
+use PHPUnit_Framework_TestCase;
+use Dissect\Parser\Grammar;
+
+class AnalyzerTest extends PHPUnit_Framework_TestCase
+{
+    protected $analyzer = null;
+
+    /**
+     * @test
+     */
+    public function automatonShouldBeCorrectlyBuilt()
+    {
+        $grammar = new Grammar();
+
+        $grammar('S')
+            ->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']);
+    }
+
+    protected function getAnalysisResult(Grammar $grammar)
+    {
+        return $this->getAnalyzer()->analyze($grammar);
+    }
+
+    protected function getAnalyzer()
+    {
+        if ($this->analyzer === null) {
+            $this->analyzer = new Analyzer();
+        }
+
+        return $this->analyzer;
+    }
+}

{'commit': "diff --git a/src/Dissect/Parser/LALR1/Analysis/AnalysisResult.php b/src/Dissect/Parser/LALR1/Analysis/AnalysisResult.php\nnew file mode 100644\nindex 0000000..fd6f222\n--- /dev/null\n+++ b/src/Dissect/Parser/LALR1/Analysis/AnalysisResult.php\n@@ -0,0 +1,36 @@\n+<?php\n+\n+namespace Dissect\\Parser\\LALR1\\Analysis;\n+\n+/**\n+ * The result of a grammar analysis.\n+ *\n+ * @author Jakub Lédl <jakubledl@gmail.com>\n+ */\n+class AnalysisResult\n+{\n+    /**\n+     * @var \\Dissect\\Parser\\LALR1\\Analysis\\Automaton\n+     */\n+    protected $automaton;\n+\n+    /**\n+     * Constructor.\n+     *\n+     * @param \\Dissect\\Parser\\LALR1\\Analysis\\Automaton $automaton\n+     */\n+    public function __construct(Automaton $automaton)\n+    {\n+        $this->automaton = $automaton;\n+    }\n+\n+    /**\n+     * Returns the handle-finding FSA.\n+     *\n+     * @return \\Dissect\\Parser\\LALR1\\Analysis\\Automaton\n+     */\n+    public function getAutomaton()\n+    {\n+        return $this->automaton;\n+    }\n+}\ndiff --git a/src/Dissect/Parser/LALR1/Analysis/Analyzer.php b/src/Dissect/Parser/LALR1/Analysis/Analyzer.php\nnew file mode 100644\nindex 0000000..558f8b0\n--- /dev/null\n+++ b/src/Dissect/Parser/LALR1/Analysis/Analyzer.php\n@@ -0,0 +1,127 @@\n+<?php\n+\n+namespace Dissect\\Parser\\LALR1\\Analysis;\n+\n+use Dissect\\Parser\\Grammar;\n+use SplQueue;\n+\n+/**\n+ * Performs a grammar analysis and returns\n+ * the result.\n+ *\n+ * @author Jakub Lédl <jakubledl@gmail.com>\n+ */\n+class Analyzer\n+{\n+    /**\n+     * Performs a grammar analysis.\n+     *\n+     * @param \\Dissect\\Parser\\Grammar $grammar The grammar to analyse.\n+     *\n+     * @return \\Dissect\\Parser\\LALR1\\Analysis\\AnalysisResult The result ofthe analysis.\n+     */\n+    public function analyze(Grammar $grammar)\n+    {\n+        $automaton = $this->buildAutomaton($grammar);\n+\n+        return new AnalysisResult($automaton);\n+    }\n+\n+    /**\n+     * Builds the handle-finding FSA from the grammar.\n+     *\n+     * @param \\Dissect\\Parser\\Grammar $grammar The grammar.\n+     *\n+     * @return \\Dissect\\Parser\\LALR1\\Analysis\\Automaton The resulting automaton.\n+     */\n+    protected function buildAutomaton(Grammar $grammar)\n+    {\n+        $automaton = new Automaton();\n+        $queue = new SplQueue();\n+        $origins = array();\n+        $nextStateNumber = 0;\n+        $nonterminals = $grammar->getNonterminals();\n+        $groupedRules = $grammar->getGroupedRules();\n+\n+        // construct the initial state\n+        $state = new State($nextStateNumber++, array(\n+            new Item($grammar->getStartRule(), 0),\n+        ));\n+\n+        $queue->enqueue($state);\n+        $automaton->addState($state);\n+\n+        while (!$queue->isEmpty()) {\n+            $state = $queue->dequeue();\n+            $groupedItems = array();\n+\n+            // calculate closure\n+            $added = array();\n+            $currentItems = $state->getItems();\n+            for ($x = 0; $x < count($currentItems); $x++) {\n+                $item = $currentItems[$x];\n+                if (!$item->isReduceItem()) {\n+                    $component = $item->getActiveComponent();\n+                    $groupedItems[$component][] = $item;\n+\n+                    if (!in_array($component, $added) && in_array($component, $nonterminals)) {\n+                        // if not processed\n+\n+                        foreach (array_map(function ($rule) {\n+                            return new Item($rule, 0);\n+                        }, $groupedRules[$component]) as $newItem) {\n+                            $currentItems[] = $newItem;\n+                            $state->add($newItem);\n+                        }\n+\n+                        $added[] = $component;\n+                    }\n+                }\n+            }\n+\n+            // calculate transitions\n+            foreach ($groupedItems as $component => $items) {\n+                $currentOrigin = array();\n+\n+                foreach ($items as $item) {\n+                    $currentOrigin[$item->getRule()->getNumber()][] =\n+                        $item->getDotIndex();\n+                }\n+\n+                $n = null;\n+\n+                foreach ($origins as $number => $map) {\n+                    $match = true;\n+\n+                    foreach ($currentOrigin as $rule => &$positions) {\n+                        sort($positions);\n+                        $match = (isset($map[$rule]) && $map[$rule] == $positions) && $match;\n+                    }\n+\n+                    if ($match) {\n+                        $n = $number;\n+                        break;\n+                    }\n+                }\n+\n+                if ($n === null) {\n+                    $num = $nextStateNumber++;\n+                    $newState = new State($num, array_map(function (Item $i) {\n+                        return new Item($i->getRule(), $i->getDotIndex() + 1);\n+                    }, $items));\n+\n+                    $automaton->addState($newState);\n+                    $queue->enqueue($newState);\n+\n+                    $origins[$num] = $currentOrigin;\n+\n+                    $automaton->addTransition($state->getNumber(), $component, $num);\n+                } else {\n+                    $automaton->addTransition($state->getNumber(), $component, $n);\n+                }\n+            }\n+        }\n+\n+        return $automaton;\n+    }\n+}\ndiff --git a/tests/Dissect/Parser/LALR1/Analysis/AnalyzerTest.php b/tests/Dissect/Parser/LALR1/Analysis/AnalyzerTest.php\nnew file mode 100644\nindex 0000000..d15ed94\n--- /dev/null\n+++ b/tests/Dissect/Parser/LALR1/Analysis/AnalyzerTest.php\n@@ -0,0 +1,48 @@\n+<?php\n+\n+namespace Dissect\\Parser\\LALR1\\Analysis;\n+\n+use PHPUnit_Framework_TestCase;\n+use Dissect\\Parser\\Grammar;\n+\n+class AnalyzerTest extends PHPUnit_Framework_TestCase\n+{\n+    protected $analyzer = null;\n+\n+    /**\n+     * @test\n+     */\n+    public function automatonShouldBeCorrectlyBuilt()\n+    {\n+        $grammar = new Grammar();\n+\n+        $grammar('S')\n+            ->is('a', 'S', 'b')\n+            ->is();\n+\n+        $grammar->start('S');\n+\n+        $result = $this->getAnalysisResult($grammar);\n+        $table = $result->getAutomaton()->getTransitionTable();\n+\n+        $this->assertEquals(1, $table[0]['S']);\n+        $this->assertEquals(2, $table[0]['a']);\n+        $this->assertEquals(2, $table[2]['a']);\n+        $this->assertEquals(3, $table[2]['S']);\n+        $this->assertEquals(4, $table[3]['b']);\n+    }\n+\n+    protected function getAnalysisResult(Grammar $grammar)\n+    {\n+        return $this->getAnalyzer()->analyze($grammar);\n+    }\n+\n+    protected function getAnalyzer()\n+    {\n+        if ($this->analyzer === null) {\n+            $this->analyzer = new Analyzer();\n+        }\n+\n+        return $this->analyzer;\n+    }\n+}\n", 'commit_subject': 'Automaton builder', 'repo_name': 'jakubledl/dissect', 'committer': {'name': 'Jakub Lédl', 'email': 'f32fd2c56db897ef4e42a14812b6cb00b624c57d@gmail.com', 'time_sec': '1356132331', 'tz_offset': '60', 'date': {'seconds': '1356132331'}}, 'commit_tree': 'a9425c64855ae924748e83a2e88747ab1d0f9337', 'commit_message': 'Automaton builder\n', 'language_name': 'PHP', 'license': 'unlicense', 'hunks': "@@ -0,0 +1,48 @@\n+<?php\n+\n+namespace Dissect\\Parser\\LALR1\\Analysis;\n+\n+use PHPUnit_Framework_TestCase;\n+use Dissect\\Parser\\Grammar;\n+\n+class AnalyzerTest extends PHPUnit_Framework_TestCase\n+{\n+    protected $analyzer = null;\n+\n+    /**\n+     * @test\n+     */\n+    public function automatonShouldBeCorrectlyBuilt()\n+    {\n+        $grammar = new Grammar();\n+\n+        $grammar('S')\n+            ->is('a', 'S', 'b')\n+            ->is();\n+\n+        $grammar->start('S');\n+\n+        $result = $this->getAnalysisResult($grammar);\n+        $table = $result->getAutomaton()->getTransitionTable();\n+\n+        $this->assertEquals(1, $table[0]['S']);\n+        $this->assertEquals(2, $table[0]['a']);\n+        $this->assertEquals(2, $table[2]['a']);\n+        $this->assertEquals(3, $table[2]['S']);\n+        $this->assertEquals(4, $table[3]['b']);\n+    }\n+\n+    protected function getAnalysisResult(Grammar $grammar)\n+    {\n+        return $this->getAnalyzer()->analyze($grammar);\n+    }\n+\n+    protected function getAnalyzer()\n+    {\n+        if ($this->analyzer === null) {\n+            $this->analyzer = new Analyzer();\n+        }\n+\n+        return $this->analyzer;\n+    }\n+}\n", 'addition_count': 48, 'deletion_count': 0, 'src_file': '/dev/null', 'tgt_file': 'b/tests/Dissect/Parser/LALR1/Analysis/AnalyzerTest.php', 'file_extension': '.php', 'before_file': 'ADDFILE', 'message': 'Automaton builder\n', 'author_name': 'Jakub Lédl', 'lang': 'php'}