diff options
Diffstat (limited to 'tests/unit/grammar/first_test.go')
| -rw-r--r-- | tests/unit/grammar/first_test.go | 219 |
1 files changed, 219 insertions, 0 deletions
diff --git a/tests/unit/grammar/first_test.go b/tests/unit/grammar/first_test.go new file mode 100644 index 0000000..9625ef6 --- /dev/null +++ b/tests/unit/grammar/first_test.go @@ -0,0 +1,219 @@ +package grammar + +import ( + "strings" + "testing" + + "urubu/grammar/symbol" + "urubu/spec/grammar/parser" +) + +type first struct { + lhs string + num int + dot int + symbols []string + empty bool +} + +func TestGenFirst(t *testing.T) { + tests := []struct { + caption string + src string + first []first + }{ + { + caption: "productions contain only non-empty productions", + src: ` +#name test; + +expr + : expr add term + | term + ; +term + : term mul factor + | factor + ; +factor + : l_paren expr r_paren + | id + ; +add: "\+"; +mul: "\*"; +l_paren: "\("; +r_paren: "\)"; +id: "[A-Za-z_][0-9A-Za-z_]*"; +`, + first: []first{ + {lhs: "expr'", num: 0, dot: 0, symbols: []string{"l_paren", "id"}}, + {lhs: "expr", num: 0, dot: 0, symbols: []string{"l_paren", "id"}}, + {lhs: "expr", num: 0, dot: 1, symbols: []string{"add"}}, + {lhs: "expr", num: 0, dot: 2, symbols: []string{"l_paren", "id"}}, + {lhs: "expr", num: 1, dot: 0, symbols: []string{"l_paren", "id"}}, + {lhs: "term", num: 0, dot: 0, symbols: []string{"l_paren", "id"}}, + {lhs: "term", num: 0, dot: 1, symbols: []string{"mul"}}, + {lhs: "term", num: 0, dot: 2, symbols: []string{"l_paren", "id"}}, + {lhs: "term", num: 1, dot: 0, symbols: []string{"l_paren", "id"}}, + {lhs: "factor", num: 0, dot: 0, symbols: []string{"l_paren"}}, + {lhs: "factor", num: 0, dot: 1, symbols: []string{"l_paren", "id"}}, + {lhs: "factor", num: 0, dot: 2, symbols: []string{"r_paren"}}, + {lhs: "factor", num: 1, dot: 0, symbols: []string{"id"}}, + }, + }, + { + caption: "productions contain the empty start production", + src: ` +#name test; + +s + : + ; +`, + first: []first{ + {lhs: "s'", num: 0, dot: 0, symbols: []string{}, empty: true}, + {lhs: "s", num: 0, dot: 0, symbols: []string{}, empty: true}, + }, + }, + { + caption: "productions contain an empty production", + src: ` +#name test; + +s + : foo bar + ; +foo + : + ; +bar: "bar"; +`, + first: []first{ + {lhs: "s'", num: 0, dot: 0, symbols: []string{"bar"}, empty: false}, + {lhs: "s", num: 0, dot: 0, symbols: []string{"bar"}, empty: false}, + {lhs: "foo", num: 0, dot: 0, symbols: []string{}, empty: true}, + }, + }, + { + caption: "a start production contains a non-empty alternative and empty alternative", + src: ` +#name test; + +s + : foo + | + ; +foo: "foo"; +`, + first: []first{ + {lhs: "s'", num: 0, dot: 0, symbols: []string{"foo"}, empty: true}, + {lhs: "s", num: 0, dot: 0, symbols: []string{"foo"}}, + {lhs: "s", num: 1, dot: 0, symbols: []string{}, empty: true}, + }, + }, + { + caption: "a production contains non-empty alternative and empty alternative", + src: ` +#name test; + +s + : foo + ; +foo + : bar + | + ; +bar: "bar"; +`, + first: []first{ + {lhs: "s'", num: 0, dot: 0, symbols: []string{"bar"}, empty: true}, + {lhs: "s", num: 0, dot: 0, symbols: []string{"bar"}, empty: true}, + {lhs: "foo", num: 0, dot: 0, symbols: []string{"bar"}}, + {lhs: "foo", num: 1, dot: 0, symbols: []string{}, empty: true}, + }, + }, + } + for _, tt := range tests { + t.Run(tt.caption, func(t *testing.T) { + fst, gram := genActualFirst(t, tt.src) + + for _, ttFirst := range tt.first { + lhsSym, ok := gram.symbolTable.ToSymbol(ttFirst.lhs) + if !ok { + t.Fatalf("a symbol was not found; symbol: %v", ttFirst.lhs) + } + + prod, ok := gram.productionSet.findByLHS(lhsSym) + if !ok { + t.Fatalf("a production was not found; LHS: %v (%v)", ttFirst.lhs, lhsSym) + } + + actualFirst, err := fst.find(prod[ttFirst.num], ttFirst.dot) + if err != nil { + t.Fatalf("failed to get a FIRST set; LHS: %v (%v), num: %v, dot: %v, error: %v", ttFirst.lhs, lhsSym, ttFirst.num, ttFirst.dot, err) + } + + expectedFirst := genExpectedFirstEntry(t, ttFirst.symbols, ttFirst.empty, gram.symbolTable) + + testFirst(t, actualFirst, expectedFirst) + } + }) + } +} + +func genActualFirst(t *testing.T, src string) (*firstSet, *Grammar) { + ast, err := parser.Parse(strings.NewReader(src)) + if err != nil { + t.Fatal(err) + } + b := GrammarBuilder{ + AST: ast, + } + gram, err := b.build() + if err != nil { + t.Fatal(err) + } + fst, err := genFirstSet(gram.productionSet) + if err != nil { + t.Fatal(err) + } + if fst == nil { + t.Fatal("genFiest returned nil without any error") + } + + return fst, gram +} + +func genExpectedFirstEntry(t *testing.T, symbols []string, empty bool, symTab *symbol.SymbolTableReader) *firstEntry { + t.Helper() + + entry := newFirstEntry() + if empty { + entry.addEmpty() + } + for _, sym := range symbols { + symSym, ok := symTab.ToSymbol(sym) + if !ok { + t.Fatalf("a symbol was not found; symbol: %v", sym) + } + entry.add(symSym) + } + + return entry +} + +func testFirst(t *testing.T, actual, expected *firstEntry) { + if actual.empty != expected.empty { + t.Errorf("empty is mismatched\nwant: %v\ngot: %v", expected.empty, actual.empty) + } + + if len(actual.symbols) != len(expected.symbols) { + t.Fatalf("invalid FIRST set\nwant: %+v\ngot: %+v", expected.symbols, actual.symbols) + } + + for eSym := range expected.symbols { + if _, ok := actual.symbols[eSym]; !ok { + t.Fatalf("invalid FIRST set\nwant: %+v\ngot: %+v", expected.symbols, actual.symbols) + } + } +} |