packages/sql-parser/tests/Unit/Automaton/LookaheadSetsTest.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\Bitset;
12use SqlParser\Automaton\ClosureIndex;
13use SqlParser\Automaton\Digraph;
14use SqlParser\Automaton\LookaheadSets;
15use SqlParser\Automaton\Lr0Automaton;
16use SqlParser\Automaton\Lr0Builder;
17use SqlParser\Automaton\NullableSet;
18use SqlParser\Grammar\Grammar;
19use SqlParser\Grammar\GrammarBuilder;
20use SqlParser\Grammar\Rule;
21use SqlParser\Grammar\SymbolTable;
22
23#[CoversClass(LookaheadSets::class)]
24#[UsesClass(Bitset::class)]
25#[UsesClass(ClosureIndex::class)]
26#[UsesClass(Digraph::class)]
27#[UsesClass(Lr0Automaton::class)]
28#[UsesClass(Lr0Builder::class)]
29#[UsesClass(NullableSet::class)]
30#[UsesClass(Grammar::class)]
31#[UsesClass(GrammarBuilder::class)]
32#[UsesClass(Rule::class)]
33#[UsesClass(SymbolTable::class)]
34#[Small]
35final class LookaheadSetsTest extends TestCase
36{
37    public function testOfFollowsTheTextbookGrammar(): void
38    {
39        $builder = new GrammarBuilder();
40        $builder->terminal('id');
41        $builder->terminal('+');
42        $builder->terminal('*');
43        $builder->terminal('(');
44        $builder->terminal(')');
45        $builder->rule('E', ['E', '+', 'T']);
46        $builder->rule('E', ['T']);
47        $builder->rule('T', ['T', '*', 'F']);
48        $builder->rule('T', ['F']);
49        $builder->rule('F', ['(', 'E', ')']);
50        $builder->rule('F', ['id']);
51        $grammar = $builder->build();
52        $automaton = (new Lr0Builder())->build($grammar);
53        $lookaheads = new LookaheadSets($grammar, $automaton, new NullableSet($grammar));
54        $symbols = $grammar->symbols;
55        $afterId = $automaton->transition(0, $symbols->id('id') ?? -1) ?? -1;
56        $afterT = $automaton->transition(0, $symbols->id('T') ?? -1) ?? -1;
57
58        self::assertSame([0, $symbols->id('+'), $symbols->id('*'), $symbols->id(')')], Bitset::members($lookaheads->of($afterId)[6]));
59        self::assertSame([0, $symbols->id('+'), $symbols->id(')')], Bitset::members($lookaheads->of($afterT)[2]));
60        self::assertSame([], $lookaheads->of(99));
61    }
62
63    public function testReads(): void
64    {
65        $builder = new GrammarBuilder();
66        $builder->terminal('A');
67        $builder->terminal('B');
68        $builder->rule('s', ['x', 'opt', 'B']);
69        $builder->rule('x', ['A']);
70        $builder->rule('opt', []);
71        $grammar = $builder->build();
72        $automaton = (new Lr0Builder())->build($grammar);
73        $afterX = $automaton->transition(0, $grammar->symbols->id('x') ?? -1) ?? -1;
74        $nodes = [0 => [$grammar->symbols->id('s') ?? -1 => 0, $grammar->symbols->id('x') ?? -1 => 1], $afterX => [$grammar->symbols->id('opt') ?? -1 => 2]];
75        [$sets, $reads] = (new LookaheadSets($grammar, $automaton, new NullableSet($grammar)))->reads($automaton, $nodes, $grammar->symbols->terminalCount(), new NullableSet($grammar));
76
77        self::assertSame([0], Bitset::members($sets[0]));
78        self::assertSame([], Bitset::members($sets[1]));
79        self::assertSame([1 => [2]], $reads);
80        self::assertSame([$grammar->symbols->id('B')], Bitset::members($sets[2]));
81    }
82
83    public function testOfReadsThroughNullableNonterminals(): void
84    {
85        $builder = new GrammarBuilder();
86        $builder->terminal('A');
87        $builder->terminal('B');
88        $builder->rule('s', ['x', 'opt', 'B']);
89        $builder->rule('x', ['A']);
90        $builder->rule('opt', []);
91        $builder->rule('opt', ['A']);
92        $grammar = $builder->build();
93        $automaton = (new Lr0Builder())->build($grammar);
94        $lookaheads = new LookaheadSets($grammar, $automaton, new NullableSet($grammar));
95        $afterA = $automaton->transition(0, $grammar->symbols->id('A') ?? -1) ?? -1;
96
97        self::assertSame([$grammar->symbols->id('A'), $grammar->symbols->id('B')], Bitset::members($lookaheads->of($afterA)[2]));
98    }
99}
100