packages/sql-parser/tests/Unit/Automaton/Lr0BuilderTest.php

1<?php
2
3declare(strict_types=1);
4
5namespace Tests\Unit\Automaton;
6
7use PHPUnit\Framework\Attributes\CoversClass;
8use PHPUnit\Framework\Attributes\Small;
9use PHPUnit\Framework\Attributes\UsesClass;
10use PHPUnit\Framework\TestCase;
11use SqlParser\Automaton\ClosureIndex;
12use SqlParser\Automaton\Lr0Automaton;
13use SqlParser\Automaton\Lr0Builder;
14use SqlParser\Grammar\Grammar;
15use SqlParser\Grammar\GrammarBuilder;
16use SqlParser\Grammar\Rule;
17use SqlParser\Grammar\SymbolTable;
18
19#[CoversClass(Lr0Builder::class)]
20#[UsesClass(ClosureIndex::class)]
21#[UsesClass(Lr0Automaton::class)]
22#[UsesClass(Grammar::class)]
23#[UsesClass(GrammarBuilder::class)]
24#[UsesClass(Rule::class)]
25#[UsesClass(SymbolTable::class)]
26#[Small]
27final class Lr0BuilderTest extends TestCase
28{
29    public function testBuildDiscoversEveryStateOfTheTextbookGrammar(): void
30    {
31        $builder = new GrammarBuilder();
32        $builder->terminal('id');
33        $builder->terminal('+');
34        $builder->terminal('*');
35        $builder->terminal('(');
36        $builder->terminal(')');
37        $builder->rule('E', ['E', '+', 'T']);
38        $builder->rule('E', ['T']);
39        $builder->rule('T', ['T', '*', 'F']);
40        $builder->rule('T', ['F']);
41        $builder->rule('F', ['(', 'E', ')']);
42        $builder->rule('F', ['id']);
43        $grammar = $builder->build();
44        $automaton = (new Lr0Builder())->build($grammar);
45        $symbols = $grammar->symbols;
46
47        self::assertSame(13, $automaton->stateCount());
48        self::assertSame([0], $automaton->kernels[0]);
49        self::assertNotNull($automaton->transition(0, $symbols->id('E') ?? -1));
50        self::assertNotNull($automaton->transition(0, $symbols->id('id') ?? -1));
51        self::assertSame([6], $automaton->reductions[$automaton->transition(0, $symbols->id('id') ?? -1)]);
52    }
53
54    public function testBuildCompletesEmptyRulesInTheClosure(): void
55    {
56        $builder = new GrammarBuilder();
57        $builder->terminal('A');
58        $builder->rule('s', ['opt', 'A']);
59        $builder->rule('opt', []);
60        $builder->rule('opt', ['A']);
61        $grammar = $builder->build();
62        $automaton = (new Lr0Builder())->build($grammar);
63
64        self::assertSame([2], $automaton->reductions[0]);
65        self::assertSame([], $automaton->transitions[$automaton->transition($automaton->transition(0, $grammar->symbols->id('opt') ?? -1) ?? -1, $grammar->symbols->id('A') ?? -1) ?? -1]);
66    }
67}
68