diff options
author | EuAndreh <eu@euandre.org> | 2024-12-11 16:48:12 -0300 |
---|---|---|
committer | EuAndreh <eu@euandre.org> | 2024-12-11 16:48:12 -0300 |
commit | 27b4729bd1a57740ea68e774d58d9cb3f45c5589 (patch) | |
tree | 152ff5686ade087e29e102cbbd39c0405cb63c02 /tests/unit/grammar.go | |
parent | Consolidate packages spread across multiple files into single one (diff) | |
download | cotia-27b4729bd1a57740ea68e774d58d9cb3f45c5589.tar.gz cotia-27b4729bd1a57740ea68e774d58d9cb3f45c5589.tar.xz |
Do the same single file consolidation on tests
Diffstat (limited to 'tests/unit/grammar.go')
-rw-r--r-- | tests/unit/grammar.go | 4647 |
1 files changed, 4647 insertions, 0 deletions
diff --git a/tests/unit/grammar.go b/tests/unit/grammar.go new file mode 100644 index 0000000..3743b23 --- /dev/null +++ b/tests/unit/grammar.go @@ -0,0 +1,4647 @@ +package grammar + +import ( + "fmt" + "strings" + "testing" + + verr "urubu/error" + "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) + } + } +} + +func TestGrammarBuilderOK(t *testing.T) { + type okTest struct { + caption string + specSrc string + validate func(t *testing.T, g *Grammar) + } + + nameTests := []*okTest{ + { + caption: "the `#name` can be the same identifier as a non-terminal symbol", + specSrc: ` +#name s; + +s + : foo + ; + +foo + : 'foo'; +`, + validate: func(t *testing.T, g *Grammar) { + expected := "s" + if g.name != expected { + t.Fatalf("unexpected name: want: %v, got: %v", expected, g.name) + } + }, + }, + { + caption: "the `#name` can be the same identifier as a terminal symbol", + specSrc: ` +#name foo; + +s + : foo + ; + +foo + : 'foo'; +`, + validate: func(t *testing.T, g *Grammar) { + expected := "foo" + if g.name != expected { + t.Fatalf("unexpected name: want: %v, got: %v", expected, g.name) + } + }, + }, + { + caption: "the `#name` can be the same identifier as the error symbol", + specSrc: ` +#name error; + +s + : foo + | error + ; + +foo + : 'foo'; +`, + validate: func(t *testing.T, g *Grammar) { + expected := "error" + if g.name != expected { + t.Fatalf("unexpected name: want: %v, got: %v", expected, g.name) + } + }, + }, + { + caption: "the `#name` can be the same identifier as a fragment", + specSrc: ` +#name f; + +s + : foo + ; + +foo + : "\f{f}"; +fragment f + : 'foo'; +`, + validate: func(t *testing.T, g *Grammar) { + expected := "f" + if g.name != expected { + t.Fatalf("unexpected name: want: %v, got: %v", expected, g.name) + } + }, + }, + } + + modeTests := []*okTest{ + { + caption: "a `#mode` can be the same identifier as a non-terminal symbol", + specSrc: ` +#name test; + +s + : foo bar + ; + +foo #push s + : 'foo'; +bar #mode s + : 'bar'; +`, + validate: func(t *testing.T, g *Grammar) { + kind := "bar" + expectedMode := "s" + for _, e := range g.lexSpec.Entries { + if e.Kind.String() == kind && e.Modes[0].String() == expectedMode { + return + } + } + t.Fatalf("symbol having expected mode was not found: want: %v #mode %v", kind, expectedMode) + }, + }, + { + caption: "a `#mode` can be the same identifier as a terminal symbol", + specSrc: ` +#name test; + +s + : foo bar + ; + +foo #push bar + : 'foo'; +bar #mode bar + : 'bar'; +`, + validate: func(t *testing.T, g *Grammar) { + kind := "bar" + expectedMode := "bar" + for _, e := range g.lexSpec.Entries { + if e.Kind.String() == kind && e.Modes[0].String() == expectedMode { + return + } + } + t.Fatalf("symbol having expected mode was not found: want: %v #mode %v", kind, expectedMode) + }, + }, + { + caption: "a `#mode` can be the same identifier as the error symbol", + specSrc: ` +#name test; + +s + : foo bar + | error + ; + +foo #push error + : 'foo'; +bar #mode error + : 'bar'; +`, + validate: func(t *testing.T, g *Grammar) { + kind := "bar" + expectedMode := "error" + for _, e := range g.lexSpec.Entries { + if e.Kind.String() == kind && e.Modes[0].String() == expectedMode { + return + } + } + t.Fatalf("symbol having expected mode was not found: want: %v #mode %v", kind, expectedMode) + }, + }, + { + caption: "a `#mode` can be the same identifier as a fragment", + specSrc: ` +#name test; + +s + : foo bar + ; + +foo #push f + : "\f{f}"; +bar #mode f + : 'bar'; +fragment f + : 'foo'; +`, + validate: func(t *testing.T, g *Grammar) { + kind := "bar" + expectedMode := "f" + for _, e := range g.lexSpec.Entries { + if e.Kind.String() == kind && e.Modes[0].String() == expectedMode { + return + } + } + t.Fatalf("symbol having expected mode was not found: want: %v #mode %v", kind, expectedMode) + }, + }, + } + + precTests := []*okTest{ + { + caption: "a `#prec` allows the empty directive group", + specSrc: ` +#name test; + +#prec (); + +s + : foo + ; + +foo + : 'foo'; +`, + }, + { + caption: "a `#left` directive gives a precedence and the left associativity to specified terminal symbols", + specSrc: ` +#name test; + +#prec ( + #left foo bar +); + +s + : foo bar baz + ; + +foo + : 'foo'; +bar + : 'bar'; +baz + : 'baz'; +`, + validate: func(t *testing.T, g *Grammar) { + var fooPrec int + var fooAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("foo") + fooPrec = g.precAndAssoc.terminalPrecedence(s.Num()) + fooAssoc = g.precAndAssoc.terminalAssociativity(s.Num()) + } + if fooPrec != 1 || fooAssoc != assocTypeLeft { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 1, assocTypeLeft, fooPrec, fooAssoc) + } + var barPrec int + var barAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("bar") + barPrec = g.precAndAssoc.terminalPrecedence(s.Num()) + barAssoc = g.precAndAssoc.terminalAssociativity(s.Num()) + } + if barPrec != 1 || barAssoc != assocTypeLeft { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 1, assocTypeLeft, barPrec, barAssoc) + } + var bazPrec int + var bazAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("baz") + bazPrec = g.precAndAssoc.terminalPrecedence(s.Num()) + bazAssoc = g.precAndAssoc.terminalAssociativity(s.Num()) + } + if bazPrec != precNil || bazAssoc != assocTypeNil { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", precNil, assocTypeNil, bazPrec, bazAssoc) + } + }, + }, + { + caption: "a `#right` directive gives a precedence and the right associativity to specified terminal symbols", + specSrc: ` +#name test; + +#prec ( + #right foo bar +); + +s + : foo bar baz + ; + +foo + : 'foo'; +bar + : 'bar'; +baz + : 'baz'; +`, + validate: func(t *testing.T, g *Grammar) { + var fooPrec int + var fooAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("foo") + fooPrec = g.precAndAssoc.terminalPrecedence(s.Num()) + fooAssoc = g.precAndAssoc.terminalAssociativity(s.Num()) + } + if fooPrec != 1 || fooAssoc != assocTypeRight { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 1, assocTypeRight, fooPrec, fooAssoc) + } + var barPrec int + var barAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("bar") + barPrec = g.precAndAssoc.terminalPrecedence(s.Num()) + barAssoc = g.precAndAssoc.terminalAssociativity(s.Num()) + } + if barPrec != 1 || barAssoc != assocTypeRight { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 1, assocTypeRight, barPrec, barAssoc) + } + var bazPrec int + var bazAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("baz") + bazPrec = g.precAndAssoc.terminalPrecedence(s.Num()) + bazAssoc = g.precAndAssoc.terminalAssociativity(s.Num()) + } + if bazPrec != precNil || bazAssoc != assocTypeNil { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", precNil, assocTypeNil, bazPrec, bazAssoc) + } + }, + }, + { + caption: "an `#assign` directive gives only a precedence to specified terminal symbols", + specSrc: ` +#name test; + +#prec ( + #assign foo bar +); + +s + : foo bar baz + ; + +foo + : 'foo'; +bar + : 'bar'; +baz + : 'baz'; +`, + validate: func(t *testing.T, g *Grammar) { + var fooPrec int + var fooAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("foo") + fooPrec = g.precAndAssoc.terminalPrecedence(s.Num()) + fooAssoc = g.precAndAssoc.terminalAssociativity(s.Num()) + } + if fooPrec != 1 || fooAssoc != assocTypeNil { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 1, assocTypeNil, fooPrec, fooAssoc) + } + var barPrec int + var barAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("bar") + barPrec = g.precAndAssoc.terminalPrecedence(s.Num()) + barAssoc = g.precAndAssoc.terminalAssociativity(s.Num()) + } + if barPrec != 1 || barAssoc != assocTypeNil { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 1, assocTypeNil, barPrec, barAssoc) + } + var bazPrec int + var bazAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("baz") + bazPrec = g.precAndAssoc.terminalPrecedence(s.Num()) + bazAssoc = g.precAndAssoc.terminalAssociativity(s.Num()) + } + if bazPrec != precNil || bazAssoc != assocTypeNil { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", precNil, assocTypeNil, bazPrec, bazAssoc) + } + }, + }, + { + caption: "a production has the same precedence and associativity as the right-most terminal symbol", + specSrc: ` +#name test; + +#prec ( + #left foo +); + +s + : foo bar // This alternative has the same precedence and associativity as the right-most terminal symbol 'bar', not 'foo'. + ; + +foo + : 'foo'; +bar + : 'bar'; +`, + validate: func(t *testing.T, g *Grammar) { + var barPrec int + var barAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("bar") + barPrec = g.precAndAssoc.terminalPrecedence(s.Num()) + barAssoc = g.precAndAssoc.terminalAssociativity(s.Num()) + } + var sPrec int + var sAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("s") + ps, _ := g.productionSet.findByLHS(s) + sPrec = g.precAndAssoc.productionPredence(ps[0].num) + sAssoc = g.precAndAssoc.productionAssociativity(ps[0].num) + } + if barPrec != precNil || barAssoc != assocTypeNil { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", precNil, assocTypeNil, barPrec, barAssoc) + } + if sPrec != barPrec || sAssoc != barAssoc { + t.Fatalf("unexpected production precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", barPrec, barAssoc, sPrec, sAssoc) + } + }, + }, + { + caption: "a production has the same precedence and associativity as the right-most terminal symbol", + specSrc: ` +#name test; + +#prec ( + #left foo + #right bar +); + +s + : foo bar // This alternative has the same precedence and associativity as the right-most terminal symbol 'bar'. + ; + +foo + : 'foo'; +bar + : 'bar'; +`, + validate: func(t *testing.T, g *Grammar) { + var barPrec int + var barAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("bar") + barPrec = g.precAndAssoc.terminalPrecedence(s.Num()) + barAssoc = g.precAndAssoc.terminalAssociativity(s.Num()) + } + var sPrec int + var sAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("s") + ps, _ := g.productionSet.findByLHS(s) + sPrec = g.precAndAssoc.productionPredence(ps[0].num) + sAssoc = g.precAndAssoc.productionAssociativity(ps[0].num) + } + if barPrec != 2 || barAssoc != assocTypeRight { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 2, assocTypeRight, barPrec, barAssoc) + } + if sPrec != barPrec || sAssoc != barAssoc { + t.Fatalf("unexpected production precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", barPrec, barAssoc, sPrec, sAssoc) + } + }, + }, + { + caption: "even if a non-terminal symbol apears to a terminal symbol, a production inherits precedence and associativity from the right-most terminal symbol, not from the non-terminal symbol", + specSrc: ` +#name test; + +#prec ( + #left foo + #right bar +); + +s + : foo a // This alternative has the same precedence and associativity as the right-most terminal symbol 'foo', not 'a'. + ; +a + : bar + ; + +foo + : 'foo'; +bar + : 'bar'; +`, + validate: func(t *testing.T, g *Grammar) { + var fooPrec int + var fooAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("foo") + fooPrec = g.precAndAssoc.terminalPrecedence(s.Num()) + fooAssoc = g.precAndAssoc.terminalAssociativity(s.Num()) + } + var barPrec int + var barAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("bar") + barPrec = g.precAndAssoc.terminalPrecedence(s.Num()) + barAssoc = g.precAndAssoc.terminalAssociativity(s.Num()) + } + var aPrec int + var aAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("a") + ps, _ := g.productionSet.findByLHS(s) + aPrec = g.precAndAssoc.productionPredence(ps[0].num) + aAssoc = g.precAndAssoc.productionAssociativity(ps[0].num) + } + var sPrec int + var sAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("s") + ps, _ := g.productionSet.findByLHS(s) + sPrec = g.precAndAssoc.productionPredence(ps[0].num) + sAssoc = g.precAndAssoc.productionAssociativity(ps[0].num) + } + if fooPrec != 1 || fooAssoc != assocTypeLeft { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 1, assocTypeLeft, fooPrec, fooAssoc) + } + if barPrec != 2 || barAssoc != assocTypeRight { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 2, assocTypeRight, barPrec, barAssoc) + } + if aPrec != barPrec || aAssoc != barAssoc { + t.Fatalf("unexpected production precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", barPrec, barAssoc, aPrec, aAssoc) + } + if sPrec != fooPrec || sAssoc != fooAssoc { + t.Fatalf("unexpected production precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", fooPrec, fooAssoc, sPrec, sAssoc) + } + }, + }, + { + caption: "each alternative in the same production can have its own precedence and associativity", + specSrc: ` +#name test; + +#prec ( + #left foo + #right bar + #assign baz +); + +s + : foo + | bar + | baz + | bra + ; + +foo + : 'foo'; +bar + : 'bar'; +baz + : 'baz'; +bra + : 'bra'; +`, + validate: func(t *testing.T, g *Grammar) { + var alt1Prec int + var alt1Assoc assocType + var alt2Prec int + var alt2Assoc assocType + var alt3Prec int + var alt3Assoc assocType + var alt4Prec int + var alt4Assoc assocType + { + s, _ := g.symbolTable.ToSymbol("s") + ps, _ := g.productionSet.findByLHS(s) + alt1Prec = g.precAndAssoc.productionPredence(ps[0].num) + alt1Assoc = g.precAndAssoc.productionAssociativity(ps[0].num) + alt2Prec = g.precAndAssoc.productionPredence(ps[1].num) + alt2Assoc = g.precAndAssoc.productionAssociativity(ps[1].num) + alt3Prec = g.precAndAssoc.productionPredence(ps[2].num) + alt3Assoc = g.precAndAssoc.productionAssociativity(ps[2].num) + alt4Prec = g.precAndAssoc.productionPredence(ps[3].num) + alt4Assoc = g.precAndAssoc.productionAssociativity(ps[3].num) + } + if alt1Prec != 1 || alt1Assoc != assocTypeLeft { + t.Fatalf("unexpected production precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 1, assocTypeLeft, alt1Prec, alt1Assoc) + } + if alt2Prec != 2 || alt2Assoc != assocTypeRight { + t.Fatalf("unexpected production precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 2, assocTypeRight, alt2Prec, alt2Assoc) + } + if alt3Prec != 3 || alt3Assoc != assocTypeNil { + t.Fatalf("unexpected production precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 3, assocTypeNil, alt3Prec, alt3Assoc) + } + if alt4Prec != precNil || alt4Assoc != assocTypeNil { + t.Fatalf("unexpected production precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", precNil, assocTypeNil, alt4Prec, alt4Assoc) + } + }, + }, + { + caption: "when a production contains no terminal symbols, the production will not have precedence and associativiry", + specSrc: ` +#name test; + +#prec ( + #left foo +); + +s + : a + ; +a + : foo + ; + +foo + : 'foo'; +`, + validate: func(t *testing.T, g *Grammar) { + var fooPrec int + var fooAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("foo") + fooPrec = g.precAndAssoc.terminalPrecedence(s.Num()) + fooAssoc = g.precAndAssoc.terminalAssociativity(s.Num()) + } + var aPrec int + var aAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("a") + ps, _ := g.productionSet.findByLHS(s) + aPrec = g.precAndAssoc.productionPredence(ps[0].num) + aAssoc = g.precAndAssoc.productionAssociativity(ps[0].num) + } + var sPrec int + var sAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("s") + ps, _ := g.productionSet.findByLHS(s) + sPrec = g.precAndAssoc.productionPredence(ps[0].num) + sAssoc = g.precAndAssoc.productionAssociativity(ps[0].num) + } + if fooPrec != 1 || fooAssoc != assocTypeLeft { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 1, assocTypeLeft, fooPrec, fooAssoc) + } + if aPrec != fooPrec || aAssoc != fooAssoc { + t.Fatalf("unexpected production precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", fooPrec, fooAssoc, aPrec, aAssoc) + } + if sPrec != precNil || sAssoc != assocTypeNil { + t.Fatalf("unexpected production precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", precNil, assocTypeNil, sPrec, sAssoc) + } + }, + }, + { + caption: "the `#prec` directive applied to an alternative changes only precedence, not associativity", + specSrc: ` +#name test; + +#prec ( + #left foo +); + +s + : foo bar #prec foo + ; + +foo + : 'foo'; +bar + : 'bar'; +`, + validate: func(t *testing.T, g *Grammar) { + var fooPrec int + var fooAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("foo") + fooPrec = g.precAndAssoc.terminalPrecedence(s.Num()) + fooAssoc = g.precAndAssoc.terminalAssociativity(s.Num()) + } + var sPrec int + var sAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("s") + ps, _ := g.productionSet.findByLHS(s) + sPrec = g.precAndAssoc.productionPredence(ps[0].num) + sAssoc = g.precAndAssoc.productionAssociativity(ps[0].num) + } + if fooPrec != 1 || fooAssoc != assocTypeLeft { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 1, assocTypeLeft, fooPrec, fooAssoc) + } + if sPrec != fooPrec || sAssoc != assocTypeNil { + t.Fatalf("unexpected production precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", fooPrec, assocTypeNil, sPrec, sAssoc) + } + }, + }, + { + caption: "the `#prec` directive applied to an alternative changes only precedence, not associativity", + specSrc: ` +#name test; + +#prec ( + #left foo + #right bar +); + +s + : foo bar #prec foo + ; + +foo + : 'foo'; +bar + : 'bar'; +`, + validate: func(t *testing.T, g *Grammar) { + var fooPrec int + var fooAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("foo") + fooPrec = g.precAndAssoc.terminalPrecedence(s.Num()) + fooAssoc = g.precAndAssoc.terminalAssociativity(s.Num()) + } + var barPrec int + var barAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("bar") + barPrec = g.precAndAssoc.terminalPrecedence(s.Num()) + barAssoc = g.precAndAssoc.terminalAssociativity(s.Num()) + } + var sPrec int + var sAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("s") + ps, _ := g.productionSet.findByLHS(s) + sPrec = g.precAndAssoc.productionPredence(ps[0].num) + sAssoc = g.precAndAssoc.productionAssociativity(ps[0].num) + } + if fooPrec != 1 || fooAssoc != assocTypeLeft { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 1, assocTypeLeft, fooPrec, fooAssoc) + } + if barPrec != 2 || barAssoc != assocTypeRight { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 2, assocTypeRight, barPrec, barAssoc) + } + if sPrec != fooPrec || sAssoc != assocTypeNil { + t.Fatalf("unexpected production precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", fooPrec, assocTypeNil, sPrec, sAssoc) + } + }, + }, + { + caption: "an ordered symbol can appear in a `#left` directive", + specSrc: ` +#name test; + +#prec ( + #left $high + #right foo bar + #left $low +); + +s + : foo #prec $high + | bar #prec $low + ; + +foo + : 'foo'; +bar + : 'bar'; +`, + validate: func(t *testing.T, g *Grammar) { + var fooPrec int + var fooAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("foo") + fooPrec = g.precAndAssoc.terminalPrecedence(s.Num()) + fooAssoc = g.precAndAssoc.terminalAssociativity(s.Num()) + } + if fooPrec != 2 || fooAssoc != assocTypeRight { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 2, assocTypeRight, fooPrec, fooAssoc) + } + var barPrec int + var barAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("bar") + barPrec = g.precAndAssoc.terminalPrecedence(s.Num()) + barAssoc = g.precAndAssoc.terminalAssociativity(s.Num()) + } + if barPrec != 2 || barAssoc != assocTypeRight { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 2, assocTypeRight, barPrec, barAssoc) + } + var alt1Prec int + var alt1Assoc assocType + var alt2Prec int + var alt2Assoc assocType + { + s, _ := g.symbolTable.ToSymbol("s") + ps, _ := g.productionSet.findByLHS(s) + alt1Prec = g.precAndAssoc.productionPredence(ps[0].num) + alt1Assoc = g.precAndAssoc.productionAssociativity(ps[0].num) + alt2Prec = g.precAndAssoc.productionPredence(ps[1].num) + alt2Assoc = g.precAndAssoc.productionAssociativity(ps[1].num) + } + if alt1Prec != 1 || alt1Assoc != assocTypeNil { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 1, assocTypeNil, alt1Prec, alt1Assoc) + } + if alt2Prec != 3 || alt2Assoc != assocTypeNil { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 3, assocTypeNil, alt2Prec, alt2Assoc) + } + }, + }, + { + caption: "an ordered symbol can appear in a `#right` directive", + specSrc: ` +#name test; + +#prec ( + #right $high + #left foo bar + #right $low +); + +s + : foo #prec $high + | bar #prec $low + ; + +foo + : 'foo'; +bar + : 'bar'; +`, + validate: func(t *testing.T, g *Grammar) { + var fooPrec int + var fooAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("foo") + fooPrec = g.precAndAssoc.terminalPrecedence(s.Num()) + fooAssoc = g.precAndAssoc.terminalAssociativity(s.Num()) + } + if fooPrec != 2 || fooAssoc != assocTypeLeft { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 2, assocTypeLeft, fooPrec, fooAssoc) + } + var barPrec int + var barAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("bar") + barPrec = g.precAndAssoc.terminalPrecedence(s.Num()) + barAssoc = g.precAndAssoc.terminalAssociativity(s.Num()) + } + if barPrec != 2 || barAssoc != assocTypeLeft { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 2, assocTypeLeft, barPrec, barAssoc) + } + var alt1Prec int + var alt1Assoc assocType + var alt2Prec int + var alt2Assoc assocType + { + s, _ := g.symbolTable.ToSymbol("s") + ps, _ := g.productionSet.findByLHS(s) + alt1Prec = g.precAndAssoc.productionPredence(ps[0].num) + alt1Assoc = g.precAndAssoc.productionAssociativity(ps[0].num) + alt2Prec = g.precAndAssoc.productionPredence(ps[1].num) + alt2Assoc = g.precAndAssoc.productionAssociativity(ps[1].num) + } + if alt1Prec != 1 || alt1Assoc != assocTypeNil { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 1, assocTypeNil, alt1Prec, alt1Assoc) + } + if alt2Prec != 3 || alt2Assoc != assocTypeNil { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 3, assocTypeNil, alt2Prec, alt2Assoc) + } + }, + }, + { + caption: "an ordered symbol can appear in a `#assign` directive", + specSrc: ` +#name test; + +#prec ( + #assign $high + #left foo + #right bar + #assign $low +); + +s + : foo #prec $high + | bar #prec $low + ; + +foo + : 'foo'; +bar + : 'bar'; +`, + validate: func(t *testing.T, g *Grammar) { + var fooPrec int + var fooAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("foo") + fooPrec = g.precAndAssoc.terminalPrecedence(s.Num()) + fooAssoc = g.precAndAssoc.terminalAssociativity(s.Num()) + } + if fooPrec != 2 || fooAssoc != assocTypeLeft { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 2, assocTypeLeft, fooPrec, fooAssoc) + } + var barPrec int + var barAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("bar") + barPrec = g.precAndAssoc.terminalPrecedence(s.Num()) + barAssoc = g.precAndAssoc.terminalAssociativity(s.Num()) + } + if barPrec != 3 || barAssoc != assocTypeRight { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 3, assocTypeRight, barPrec, barAssoc) + } + var alt1Prec int + var alt1Assoc assocType + var alt2Prec int + var alt2Assoc assocType + { + s, _ := g.symbolTable.ToSymbol("s") + ps, _ := g.productionSet.findByLHS(s) + alt1Prec = g.precAndAssoc.productionPredence(ps[0].num) + alt1Assoc = g.precAndAssoc.productionAssociativity(ps[0].num) + alt2Prec = g.precAndAssoc.productionPredence(ps[1].num) + alt2Assoc = g.precAndAssoc.productionAssociativity(ps[1].num) + } + if alt1Prec != 1 || alt1Assoc != assocTypeNil { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 1, assocTypeNil, alt1Prec, alt1Assoc) + } + if alt2Prec != 4 || alt2Assoc != assocTypeNil { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 4, assocTypeNil, alt2Prec, alt2Assoc) + } + }, + }, + { + caption: "names of an ordered symbol and a terminal symbol can duplicate", + specSrc: ` +#name test; + +#prec ( + #left foo bar + #right $foo +); + +s + : foo + | bar #prec $foo + ; + +foo + : 'foo'; +bar + : 'bar'; +`, + validate: func(t *testing.T, g *Grammar) { + var fooPrec int + var fooAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("foo") + fooPrec = g.precAndAssoc.terminalPrecedence(s.Num()) + fooAssoc = g.precAndAssoc.terminalAssociativity(s.Num()) + } + var barPrec int + var barAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("bar") + barPrec = g.precAndAssoc.terminalPrecedence(s.Num()) + barAssoc = g.precAndAssoc.terminalAssociativity(s.Num()) + } + if fooPrec != 1 || fooAssoc != assocTypeLeft { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 1, assocTypeLeft, fooPrec, fooAssoc) + } + if barPrec != 1 || barAssoc != assocTypeLeft { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 1, assocTypeLeft, barPrec, barAssoc) + } + var alt1Prec int + var alt1Assoc assocType + var alt2Prec int + var alt2Assoc assocType + { + s, _ := g.symbolTable.ToSymbol("s") + ps, _ := g.productionSet.findByLHS(s) + alt1Prec = g.precAndAssoc.productionPredence(ps[0].num) + alt1Assoc = g.precAndAssoc.productionAssociativity(ps[0].num) + alt2Prec = g.precAndAssoc.productionPredence(ps[1].num) + alt2Assoc = g.precAndAssoc.productionAssociativity(ps[1].num) + } + if alt1Prec != fooPrec || alt1Assoc != fooAssoc { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", fooPrec, fooAssoc, alt1Prec, alt1Assoc) + } + if alt2Prec != 2 || alt2Assoc != assocTypeNil { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 2, assocTypeNil, alt2Prec, alt2Assoc) + } + }, + }, + { + caption: "names of an ordered symbol and a non-terminal symbol can duplicate", + specSrc: ` +#name test; + +#prec ( + #left foo bar + #right $a +); + +s + : a + | bar #prec $a + ; +a + : foo + ; + +foo + : 'foo'; +bar + : 'bar'; +`, + validate: func(t *testing.T, g *Grammar) { + var barPrec int + var barAssoc assocType + { + s, _ := g.symbolTable.ToSymbol("bar") + barPrec = g.precAndAssoc.terminalPrecedence(s.Num()) + barAssoc = g.precAndAssoc.terminalAssociativity(s.Num()) + } + if barPrec != 1 || barAssoc != assocTypeLeft { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 1, assocTypeLeft, barPrec, barAssoc) + } + var alt1Prec int + var alt1Assoc assocType + var alt2Prec int + var alt2Assoc assocType + { + s, _ := g.symbolTable.ToSymbol("s") + ps, _ := g.productionSet.findByLHS(s) + alt1Prec = g.precAndAssoc.productionPredence(ps[0].num) + alt1Assoc = g.precAndAssoc.productionAssociativity(ps[0].num) + alt2Prec = g.precAndAssoc.productionPredence(ps[1].num) + alt2Assoc = g.precAndAssoc.productionAssociativity(ps[1].num) + } + if alt1Prec != precNil || alt1Assoc != assocTypeNil { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", precNil, assocTypeNil, alt1Prec, alt1Assoc) + } + if alt2Prec != 2 || alt2Assoc != assocTypeNil { + t.Fatalf("unexpected terminal precedence and associativity: want: (prec: %v, assoc: %v), got: (prec: %v, assoc: %v)", 2, assocTypeNil, alt2Prec, alt2Assoc) + } + }, + }, + } + + var tests []*okTest + tests = append(tests, nameTests...) + tests = append(tests, modeTests...) + tests = append(tests, precTests...) + + for _, test := range tests { + t.Run(test.caption, func(t *testing.T) { + ast, err := parser.Parse(strings.NewReader(test.specSrc)) + if err != nil { + t.Fatal(err) + } + + b := GrammarBuilder{ + AST: ast, + } + g, err := b.build() + if err != nil { + t.Fatalf("unexpected error: %v", err) + } + if test.validate != nil { + test.validate(t, g) + } + }) + } +} + +func TestGrammarBuilderSpecError(t *testing.T) { + type specErrTest struct { + caption string + specSrc string + errs []error + } + + spellingInconsistenciesTests := []*specErrTest{ + { + caption: "a spelling inconsistency appears among non-terminal symbols", + specSrc: ` +#name test; + +a1 + : a_1 + ; +a_1 + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrSpellingInconsistency}, + }, + { + caption: "a spelling inconsistency appears among terminal symbols", + specSrc: ` +#name test; + +s + : foo1 foo_1 + ; + +foo1 + : 'foo1'; +foo_1 + : 'foo_1'; +`, + errs: []error{semErrSpellingInconsistency}, + }, + { + caption: "a spelling inconsistency appears among non-terminal and terminal symbols", + specSrc: ` +#name test; + +a1 + : a_1 + ; + +a_1 + : 'a_1'; +`, + errs: []error{semErrSpellingInconsistency}, + }, + { + caption: "a spelling inconsistency appears among ordered symbols whose precedence is the same", + specSrc: ` +#name test; + +#prec ( + #assign $p1 $p_1 +); + +s + : foo #prec $p1 + | bar #prec $p_1 + ; + +foo + : 'foo'; +bar + : 'bar'; +`, + errs: []error{semErrSpellingInconsistency}, + }, + { + caption: "a spelling inconsistency appears among ordered symbols whose precedence is not the same", + specSrc: ` +#name test; + +#prec ( + #assign $p1 + #assign $p_1 +); + +s + : foo #prec $p1 + | bar #prec $p_1 + ; + +foo + : 'foo'; +bar + : 'bar'; +`, + errs: []error{semErrSpellingInconsistency}, + }, + { + caption: "a spelling inconsistency appears among labels the same alternative contains", + specSrc: ` +#name test; + +s + : foo@l1 foo@l_1 + ; + +foo + : 'foo'; +`, + errs: []error{semErrSpellingInconsistency}, + }, + { + caption: "a spelling inconsistency appears among labels the same production contains", + specSrc: ` +#name test; + +s + : foo@l1 + | bar@l_1 + ; + +foo + : 'foo'; +bar + : 'bar'; +`, + errs: []error{semErrSpellingInconsistency}, + }, + { + caption: "a spelling inconsistency appears among labels different productions contain", + specSrc: ` +#name test; + +s + : foo@l1 + ; +a + : bar@l_1 + ; + +foo + : 'foo'; +bar + : 'bar'; +`, + errs: []error{semErrSpellingInconsistency}, + }, + } + + prodTests := []*specErrTest{ + { + caption: "a production `b` is unused", + specSrc: ` +#name test; + +a + : foo + ; +b + : foo + ; + +foo + : "foo"; +`, + errs: []error{semErrUnusedProduction}, + }, + { + caption: "a terminal symbol `bar` is unused", + specSrc: ` +#name test; + +s + : foo + ; + +foo + : "foo"; +bar + : "bar"; +`, + errs: []error{semErrUnusedTerminal}, + }, + { + caption: "a production `b` and terminal symbol `bar` is unused", + specSrc: ` +#name test; + +a + : foo + ; +b + : bar + ; + +foo + : "foo"; +bar + : "bar"; +`, + errs: []error{ + semErrUnusedProduction, + semErrUnusedTerminal, + }, + }, + { + caption: "a production cannot have production directives", + specSrc: ` +#name test; + +s #prec foo + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrInvalidProdDir}, + }, + { + caption: "a lexical production cannot have alternative directives", + specSrc: ` +#name test; + +s + : foo + ; + +foo + : 'foo' #skip; +`, + errs: []error{semErrInvalidAltDir}, + }, + { + caption: "a production directive must not be duplicated", + specSrc: ` +#name test; + +s + : foo + ; + +foo #skip #skip + : 'foo'; +`, + errs: []error{semErrDuplicateDir}, + }, + { + caption: "an alternative directive must not be duplicated", + specSrc: ` +#name test; + +s + : foo bar #ast foo bar #ast foo bar + ; + +foo + : 'foo'; +bar + : 'bar'; +`, + errs: []error{semErrDuplicateDir}, + }, + { + caption: "a production must not have a duplicate alternative (non-empty alternatives)", + specSrc: ` +#name test; + +s + : foo + | foo + ; + +foo + : "foo"; +`, + errs: []error{semErrDuplicateProduction}, + }, + { + caption: "a production must not have a duplicate alternative (non-empty and split alternatives)", + specSrc: ` +#name test; + +s + : foo + | a + ; +a + : bar + ; +s + : foo + ; + +foo + : "foo"; +bar + : "bar"; +`, + errs: []error{semErrDuplicateProduction}, + }, + { + caption: "a production must not have a duplicate alternative (empty alternatives)", + specSrc: ` +#name test; + +s + : foo + | a + ; +a + : + | + ; + +foo + : "foo"; +`, + errs: []error{semErrDuplicateProduction}, + }, + { + caption: "a production must not have a duplicate alternative (empty and split alternatives)", + specSrc: ` +#name test; + +s + : foo + | a + ; +a + : + | foo + ; +a + : + ; + +foo + : "foo"; +`, + errs: []error{semErrDuplicateProduction}, + }, + { + caption: "a terminal symbol and a non-terminal symbol (start symbol) are duplicates", + specSrc: ` +#name test; + +s + : foo + ; + +foo + : "foo"; +s + : "a"; +`, + errs: []error{semErrDuplicateName}, + }, + { + caption: "a terminal symbol and a non-terminal symbol (not start symbol) are duplicates", + specSrc: ` +#name test; + +s + : foo + | a + ; +a + : bar + ; + +foo + : "foo"; +bar + : "bar"; +a + : "a"; +`, + errs: []error{semErrDuplicateName}, + }, + { + caption: "an invalid top-level directive", + specSrc: ` +#name test; + +#foo; + +s + : a + ; + +a + : 'a'; +`, + errs: []error{semErrDirInvalidName}, + }, + { + caption: "a label must be unique in an alternative", + specSrc: ` +#name test; + +s + : foo@x bar@x + ; + +foo + : 'foo'; +bar + : 'bar'; +`, + errs: []error{semErrDuplicateLabel}, + }, + { + caption: "a label cannot be the same name as terminal symbols", + specSrc: ` +#name test; + +s + : foo bar@foo + ; + +foo + : 'foo'; +bar + : 'bar'; +`, + errs: []error{semErrDuplicateLabel}, + }, + { + caption: "a label cannot be the same name as non-terminal symbols", + specSrc: ` +#name test; + +s + : foo@a + | a + ; +a + : bar + ; + +foo + : 'foo'; +bar + : 'bar'; +`, + errs: []error{ + semErrInvalidLabel, + }, + }, + } + + nameDirTests := []*specErrTest{ + { + caption: "the `#name` directive is required", + specSrc: ` +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrNoGrammarName}, + }, + { + caption: "the `#name` directive needs an ID parameter", + specSrc: ` +#name; + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#name` directive cannot take a pattern parameter", + specSrc: ` +#name "test"; + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#name` directive cannot take a string parameter", + specSrc: ` +#name 'test'; + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#name` directive takes just one parameter", + specSrc: ` +#name test1 test2; + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + } + + precDirTests := []*specErrTest{ + { + caption: "the `#prec` directive needs a directive group parameter", + specSrc: ` +#name test; + +#prec; + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#prec` directive cannot take an ID parameter", + specSrc: ` +#name test; + +#prec foo; + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#prec` directive cannot take an ordered symbol parameter", + specSrc: ` +#name test; + +#prec $x; + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#prec` directive cannot take a pattern parameter", + specSrc: ` +#name test; + +#prec "foo"; + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#prec` directive cannot take a string parameter", + specSrc: ` +#name test; + +#prec 'foo'; + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#prec` directive takes just one directive group parameter", + specSrc: ` +#name test; + +#prec () (); + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + } + + leftDirTests := []*specErrTest{ + { + caption: "the `#left` directive needs ID parameters", + specSrc: ` +#name test; + +#prec ( + #left +); + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#left` directive cannot be applied to an error symbol", + specSrc: ` +#name test; + +#prec ( + #left error +); + +s + : foo semi_colon + | error semi_colon + ; + +foo + : 'foo'; +semi_colon + : ';'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#left` directive cannot take an undefined symbol", + specSrc: ` +#name test; + +#prec ( + #left x +); + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#left` directive cannot take a non-terminal symbol", + specSrc: ` +#name test; + +#prec ( + #left s +); + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#left` directive cannot take a pattern parameter", + specSrc: ` +#name test; + +#prec ( + #left "foo" +); + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#left` directive cannot take a string parameter", + specSrc: ` +#name test; + +#prec ( + #left 'foo' +); + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#left` directive cannot take a directive parameter", + specSrc: ` +#name test; + +#prec ( + #left () +); + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#left` dirctive cannot be specified multiple times for a terminal symbol", + specSrc: ` +#name test; + +#prec ( + #left foo foo +); + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDuplicateAssoc}, + }, + { + caption: "the `#left` dirctive cannot be specified multiple times for an ordered symbol", + specSrc: ` +#name test; + +#prec ( + #left $x $x +); + +s + : foo #prec $x + ; + +foo + : 'foo'; +`, + errs: []error{semErrDuplicateAssoc}, + }, + { + caption: "a terminal symbol cannot have different precedence", + specSrc: ` +#name test; + +#prec ( + #left foo + #left foo +); + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDuplicateAssoc}, + }, + { + caption: "an ordered symbol cannot have different precedence", + specSrc: ` +#name test; + +#prec ( + #left $x + #left $x +); + +s + : foo #prec $x + ; + +foo + : 'foo'; +`, + errs: []error{semErrDuplicateAssoc}, + }, + { + caption: "a terminal symbol cannot have different associativity", + specSrc: ` +#name test; + +#prec ( + #right foo + #left foo +); + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDuplicateAssoc}, + }, + { + caption: "an ordered symbol cannot have different associativity", + specSrc: ` +#name test; + +#prec ( + #right $x + #left $x +); + +s + : foo #prec $x + ; + +foo + : 'foo'; +`, + errs: []error{semErrDuplicateAssoc}, + }, + } + + rightDirTests := []*specErrTest{ + { + caption: "the `#right` directive needs ID parameters", + specSrc: ` +#name test; + +#prec ( + #right +); + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#right` directive cannot be applied to an error symbol", + specSrc: ` +#name test; + +#prec ( + #right error +); + +s + : foo semi_colon + | error semi_colon + ; + +foo + : 'foo'; +semi_colon + : ';'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#right` directive cannot take an undefined symbol", + specSrc: ` +#name test; + +#prec ( + #right x +); + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#right` directive cannot take a non-terminal symbol", + specSrc: ` +#name test; + +#prec ( + #right s +); + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#right` directive cannot take a pattern parameter", + specSrc: ` +#name test; + +#prec ( + #right "foo" +); + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#right` directive cannot take a string parameter", + specSrc: ` +#name test; + +#prec ( + #right 'foo' +); + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#right` directive cannot take a directive group parameter", + specSrc: ` +#name test; + +#prec ( + #right () +); + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#right` directive cannot be specified multiple times for a terminal symbol", + specSrc: ` +#name test; + +#prec ( + #right foo foo +); + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDuplicateAssoc}, + }, + { + caption: "the `#right` directive cannot be specified multiple times for an ordered symbol", + specSrc: ` +#name test; + +#prec ( + #right $x $x +); + +s + : foo #prec $x + ; + +foo + : 'foo'; +`, + errs: []error{semErrDuplicateAssoc}, + }, + { + caption: "a terminal symbol cannot have different precedence", + specSrc: ` +#name test; + +#prec ( + #right foo + #right foo +); + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDuplicateAssoc}, + }, + { + caption: "an ordered symbol cannot have different precedence", + specSrc: ` +#name test; + +#prec ( + #right $x + #right $x +); + +s + : foo #prec $x + ; + +foo + : 'foo'; +`, + errs: []error{semErrDuplicateAssoc}, + }, + { + caption: "a terminal symbol cannot have different associativity", + specSrc: ` +#name test; + +#prec ( + #left foo + #right foo +); + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDuplicateAssoc}, + }, + { + caption: "an ordered symbol cannot have different associativity", + specSrc: ` +#name test; + +#prec ( + #left $x + #right $x +); + +s + : foo #prec $x + ; + +foo + : 'foo'; +`, + errs: []error{semErrDuplicateAssoc}, + }, + } + + assignDirTests := []*specErrTest{ + { + caption: "the `#assign` directive needs ID parameters", + specSrc: ` +#name test; + +#prec ( + #assign +); + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#assign` directive cannot be applied to an error symbol", + specSrc: ` +#name test; + +#prec ( + #assign error +); + +s + : foo semi_colon + | error semi_colon + ; + +foo + : 'foo'; +semi_colon + : ';'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#assign` directive cannot take an undefined symbol", + specSrc: ` +#name test; + +#prec ( + #assign x +); + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#assign` directive cannot take a non-terminal symbol", + specSrc: ` +#name test; + +#prec ( + #assign s +); + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#assign` directive cannot take a pattern parameter", + specSrc: ` +#name test; + +#prec ( + #assign "foo" +); + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#assign` directive cannot take a string parameter", + specSrc: ` +#name test; + +#prec ( + #assign 'foo' +); + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#assign` directive cannot take a directive parameter", + specSrc: ` +#name test; + +#prec ( + #assign () +); + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#assign` dirctive cannot be specified multiple times for a terminal symbol", + specSrc: ` +#name test; + +#prec ( + #assign foo foo +); + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDuplicateAssoc}, + }, + { + caption: "the `#assign` dirctive cannot be specified multiple times for an ordered symbol", + specSrc: ` +#name test; + +#prec ( + #assign $x $x +); + +s + : foo #prec $x + ; + +foo + : 'foo'; +`, + errs: []error{semErrDuplicateAssoc}, + }, + { + caption: "a terminal symbol cannot have different precedence", + specSrc: ` +#name test; + +#prec ( + #assign foo + #assign foo +); + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDuplicateAssoc}, + }, + { + caption: "an ordered symbol cannot have different precedence", + specSrc: ` +#name test; + +#prec ( + #assign $x + #assign $x +); + +s + : foo #prec $x + ; + +foo + : 'foo'; +`, + errs: []error{semErrDuplicateAssoc}, + }, + { + caption: "a terminal symbol cannot have different associativity", + specSrc: ` +#name test; + +#prec ( + #assign foo + #left foo +); + +s + : foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDuplicateAssoc}, + }, + { + caption: "an ordered symbol cannot have different associativity", + specSrc: ` +#name test; + +#prec ( + #assign $x + #left $x +); + +s + : foo #prec $x + ; + +foo + : 'foo'; +`, + errs: []error{semErrDuplicateAssoc}, + }, + } + + errorSymTests := []*specErrTest{ + { + caption: "cannot use the error symbol as a non-terminal symbol", + specSrc: ` +#name test; + +s + : error + ; +error + : foo + ; + +foo: 'foo'; +`, + errs: []error{ + semErrErrSymIsReserved, + semErrDuplicateName, + }, + }, + { + caption: "cannot use the error symbol as a terminal symbol", + specSrc: ` +#name test; + +s + : error + ; + +error: 'error'; +`, + errs: []error{semErrErrSymIsReserved}, + }, + { + caption: "cannot use the error symbol as a terminal symbol, even if given the skip directive", + specSrc: ` +#name test; + +s + : foo + ; + +foo + : 'foo'; +error #skip + : 'error'; +`, + errs: []error{semErrErrSymIsReserved}, + }, + } + + astDirTests := []*specErrTest{ + { + caption: "the `#ast` directive needs ID or label prameters", + specSrc: ` +#name test; + +s + : foo #ast + ; + +foo + : "foo"; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#ast` directive cannot take an ordered symbol parameter", + specSrc: ` +#name test; + +#prec ( + #assign $x +); + +s + : foo #ast $x + ; + +foo + : "foo"; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#ast` directive cannot take a pattern parameter", + specSrc: ` +#name test; + +s + : foo #ast "foo" + ; + +foo + : "foo"; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#ast` directive cannot take a string parameter", + specSrc: ` +#name test; + +s + : foo #ast 'foo' + ; + +foo + : "foo"; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#ast` directive cannot take a directive group parameter", + specSrc: ` +#name test; + +s + : foo #ast () + ; + +foo + : "foo"; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "a parameter of the `#ast` directive must be either a symbol or a label in an alternative", + specSrc: ` +#name test; + +s + : foo bar #ast foo x + ; + +foo + : "foo"; +bar + : "bar"; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "a symbol in a different alternative cannot be a parameter of the `#ast` directive", + specSrc: ` +#name test; + +s + : foo #ast bar + | bar + ; + +foo + : "foo"; +bar + : "bar"; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "a label in a different alternative cannot be a parameter of the `#ast` directive", + specSrc: ` +#name test; + +s + : foo #ast b + | bar@b + ; + +foo + : "foo"; +bar + : "bar"; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "a symbol can appear in the `#ast` directive only once", + specSrc: ` +#name test; + +s + : foo #ast foo foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDuplicateElem}, + }, + { + caption: "a label can appear in the `#ast` directive only once", + specSrc: ` +#name test; + +s + : foo@x #ast x x + ; + +foo + : 'foo'; +`, + errs: []error{semErrDuplicateElem}, + }, + { + caption: "a symbol can appear in the `#ast` directive only once, even if the symbol has a label", + specSrc: ` +#name test; + +s + : foo@x #ast foo x + ; + +foo + : 'foo'; +`, + errs: []error{semErrDuplicateElem}, + }, + { + caption: "symbol `foo` is ambiguous because it appears in an alternative twice", + specSrc: ` +#name test; + +s + : foo foo #ast foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrAmbiguousElem}, + }, + { + caption: "symbol `foo` is ambiguous because it appears in an alternative twice, even if one of them has a label", + specSrc: ` +#name test; + +s + : foo@x foo #ast foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrAmbiguousElem}, + }, + { + caption: "the expansion operator cannot be applied to a terminal symbol", + specSrc: ` +#name test; + +s + : foo #ast foo... + ; + +foo + : "foo"; +`, + errs: []error{semErrDirInvalidParam}, + }, + } + + altPrecDirTests := []*specErrTest{ + { + caption: "the `#prec` directive needs an ID parameter or an ordered symbol parameter", + specSrc: ` +#name test; + +s + : foo #prec + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#prec` directive cannot be applied to an error symbol", + specSrc: ` +#name test; + +s + : foo #prec error + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#prec` directive cannot take an undefined symbol", + specSrc: ` +#name test; + +s + : foo #prec x + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#prec` directive cannot take a non-terminal symbol", + specSrc: ` +#name test; + +s + : a #prec b + | b + ; +a + : foo + ; +b + : bar + ; + +foo + : 'foo'; +bar + : 'bar'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#prec` directive cannot take an undefined ordered symbol parameter", + specSrc: ` +#name test; + +s + : foo #prec $x + ; + +foo + : 'foo'; +`, + errs: []error{semErrUndefinedOrdSym}, + }, + { + caption: "the `#prec` directive cannot take a pattern parameter", + specSrc: ` +#name test; + +s + : foo #prec "foo" + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#prec` directive cannot take a string parameter", + specSrc: ` +#name test; + +s + : foo #prec 'foo' + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#prec` directive cannot take a directive parameter", + specSrc: ` +#name test; + +s + : foo #prec () + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "a symbol the `#prec` directive takes must be given precedence explicitly", + specSrc: ` +#name test; + +s + : foo bar #prec foo + ; + +foo + : 'foo'; +bar + : 'bar'; +`, + errs: []error{semErrUndefinedPrec}, + }, + } + + recoverDirTests := []*specErrTest{ + { + caption: "the `#recover` directive cannot take an ID parameter", + specSrc: ` +#name test; + +s + : foo #recover foo + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#recover` directive cannot take an ordered symbol parameter", + specSrc: ` +#name test; + +#prec ( + #assign $x +); + +s + : foo #recover $x + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#recover` directive cannot take a pattern parameter", + specSrc: ` +#name test; + +s + : foo #recover "foo" + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#recover` directive cannot take a string parameter", + specSrc: ` +#name test; + +s + : foo #recover 'foo' + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#recover` directive cannot take a directive group parameter", + specSrc: ` +#name test; + +s + : foo #recover () + ; + +foo + : 'foo'; +`, + errs: []error{semErrDirInvalidParam}, + }, + } + + fragmentTests := []*specErrTest{ + { + caption: "a production cannot contain a fragment", + specSrc: ` +#name test; + +s + : f + ; + +fragment f + : 'fragment'; +`, + errs: []error{semErrUndefinedSym}, + }, + { + caption: "fragments cannot be duplicated", + specSrc: ` +#name test; + +s + : foo + ; + +foo + : "\f{f}"; +fragment f + : 'fragment 1'; +fragment f + : 'fragment 2'; +`, + errs: []error{semErrDuplicateFragment}, + }, + } + + modeDirTests := []*specErrTest{ + { + caption: "the `#mode` directive needs an ID parameter", + specSrc: ` +#name test; + +s + : foo bar + ; + +foo #push mode_1 + : 'foo'; +bar #mode + : 'bar'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#mode` directive cannot take an ordered symbol parameter", + specSrc: ` +#name test; + +#prec ( + #assign $x +); + +s + : foo bar + ; + +foo + : 'foo'; +bar #mode $x + : 'bar'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#mode` directive cannot take a pattern parameter", + specSrc: ` +#name test; + +s + : foo bar + ; + +foo #push mode_1 + : 'foo'; +bar #mode "mode_1" + : 'bar'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#mode` directive cannot take a string parameter", + specSrc: ` +#name test; + +s + : foo bar + ; + +foo #push mode_1 + : 'foo'; +bar #mode 'mode_1' + : 'bar'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#mode` directive cannot take a directive group parameter", + specSrc: ` +#name test; + +s + : foo bar + ; + +foo #push mode_1 + : 'foo'; +bar #mode () + : 'bar'; +`, + errs: []error{semErrDirInvalidParam}, + }, + } + + pushDirTests := []*specErrTest{ + { + caption: "the `#push` directive needs an ID parameter", + specSrc: ` +#name test; + +s + : foo bar + ; + +foo #push + : 'foo'; +bar #mode mode_1 + : 'bar'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#push` directive takes just one ID parameter", + specSrc: ` +#name test; + +s + : foo bar + ; + +foo #push mode_1 mode_2 + : 'foo'; +bar #mode mode_1 + : 'bar'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#push` directive cannot take an ordered symbol parameter", + specSrc: ` +#name test; + +#prec ( + #assign $x +); + +s + : foo bar + ; + +foo #push $x + : 'foo'; +bar + : 'bar'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#push` directive cannot take a pattern parameter", + specSrc: ` +#name test; + +s + : foo bar + ; + +foo #push "mode_1" + : 'foo'; +bar #mode mode_1 + : 'bar'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#push` directive cannot take a string parameter", + specSrc: ` +#name test; + +s + : foo bar + ; + +foo #push 'mode_1' + : 'foo'; +bar #mode mode_1 + : 'bar'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#push` directive cannot take a directive group parameter", + specSrc: ` +#name test; + +s + : foo bar + ; + +foo #push () + : 'foo'; +bar #mode mode_1 + : 'bar'; +`, + errs: []error{semErrDirInvalidParam}, + }, + } + + popDirTests := []*specErrTest{ + { + caption: "the `#pop` directive cannot take an ID parameter", + specSrc: ` +#name test; + +s + : foo bar baz + ; + +foo #push mode_1 + : 'foo'; +bar #mode mode_1 + : 'bar'; +baz #pop mode_1 + : 'baz'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#pop` directive cannot take an ordered symbol parameter", + specSrc: ` +#name test; + +#prec ( + #assign $x +); + +s + : foo bar baz + ; + +foo #push mode_1 + : 'foo'; +bar #mode mode_1 + : 'bar'; +baz #pop $x + : 'baz'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#pop` directive cannot take a pattern parameter", + specSrc: ` +#name test; + +s + : foo bar baz + ; + +foo #push mode_1 + : 'foo'; +bar #mode mode_1 + : 'bar'; +baz #pop "mode_1" + : 'baz'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#pop` directive cannot take a string parameter", + specSrc: ` +#name test; + +s + : foo bar baz + ; + +foo #push mode_1 + : 'foo'; +bar #mode mode_1 + : 'bar'; +baz #pop 'mode_1' + : 'baz'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#pop` directive cannot take a directive parameter", + specSrc: ` +#name test; + +s + : foo bar baz + ; + +foo #push mode_1 + : 'foo'; +bar #mode mode_1 + : 'bar'; +baz #pop () + : 'baz'; +`, + errs: []error{semErrDirInvalidParam}, + }, + } + + skipDirTests := []*specErrTest{ + { + caption: "the `#skip` directive cannot take an ID parameter", + specSrc: ` +#name test; + +s + : foo bar + ; + +foo #skip bar + : 'foo'; +bar + : 'bar'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#skip` directive cannot take an ordered symbol parameter", + specSrc: ` +#name test; + +#prec ( + #assign $x +); + +s + : foo bar + ; + +foo #skip $x + : 'foo'; +bar + : 'bar'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#skip` directive cannot take a pattern parameter", + specSrc: ` +#name test; + +s + : foo bar + ; + +foo #skip "bar" + : 'foo'; +bar + : 'bar'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#skip` directive cannot take a string parameter", + specSrc: ` +#name test; + +s + : foo bar + ; + +foo #skip 'bar' + : 'foo'; +bar + : 'bar'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "the `#skip` directive cannot take a directive group parameter", + specSrc: ` +#name test; + +s + : foo bar + ; + +foo #skip () + : 'foo'; +bar + : 'bar'; +`, + errs: []error{semErrDirInvalidParam}, + }, + { + caption: "a terminal symbol used in productions cannot have the skip directive", + specSrc: ` +#name test; + +s + : foo bar + ; + +foo #skip + : 'foo'; +bar + : 'bar'; +`, + errs: []error{semErrTermCannotBeSkipped}, + }, + } + + var tests []*specErrTest + tests = append(tests, spellingInconsistenciesTests...) + tests = append(tests, prodTests...) + tests = append(tests, nameDirTests...) + tests = append(tests, precDirTests...) + tests = append(tests, leftDirTests...) + tests = append(tests, rightDirTests...) + tests = append(tests, assignDirTests...) + tests = append(tests, errorSymTests...) + tests = append(tests, astDirTests...) + tests = append(tests, altPrecDirTests...) + tests = append(tests, recoverDirTests...) + tests = append(tests, fragmentTests...) + tests = append(tests, modeDirTests...) + tests = append(tests, pushDirTests...) + tests = append(tests, popDirTests...) + tests = append(tests, skipDirTests...) + for _, test := range tests { + t.Run(test.caption, func(t *testing.T) { + ast, err := parser.Parse(strings.NewReader(test.specSrc)) + if err != nil { + t.Fatal(err) + } + + b := GrammarBuilder{ + AST: ast, + } + _, err = b.build() + if err == nil { + t.Fatal("an expected error didn't occur") + } + specErrs, ok := err.(verr.SpecErrors) + if !ok { + t.Fatalf("unexpected error type: want: %T, got: %T: %v", verr.SpecErrors{}, err, err) + } + if len(specErrs) != len(test.errs) { + t.Fatalf("unexpected spec error count: want: %+v, got: %+v", test.errs, specErrs) + } + for _, expected := range test.errs { + for _, actual := range specErrs { + if actual.Cause == expected { + return + } + } + } + t.Fatalf("an expected spec error didn't occur: want: %v, got: %+v", test.errs, specErrs) + }) + } +} + +func TestGenLALR1Automaton(t *testing.T) { + // This grammar belongs to LALR(1) class, not SLR(1). + src := ` +#name test; + +s: l eq r | r; +l: ref r | id; +r: l; +eq: '='; +ref: '*'; +id: "[A-Za-z0-9_]+"; +` + + var gram *Grammar + var automaton *lalr1Automaton + { + 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) + } + + lr0, err := genLR0Automaton(gram.productionSet, gram.augmentedStartSymbol, gram.errorSymbol) + if err != nil { + t.Fatalf("failed to create a LR0 automaton: %v", err) + } + + firstSet, err := genFirstSet(gram.productionSet) + if err != nil { + t.Fatalf("failed to create a FIRST set: %v", err) + } + + automaton, err = genLALR1Automaton(lr0, gram.productionSet, firstSet) + if err != nil { + t.Fatalf("failed to create a LALR1 automaton: %v", err) + } + if automaton == nil { + t.Fatalf("genLALR1Automaton returns nil without any error") + } + } + + initialState := automaton.states[automaton.initialState] + if initialState == nil { + t.Errorf("failed to get an initial status: %v", automaton.initialState) + } + + genSym := newTestSymbolGenerator(t, gram.symbolTable) + genProd := newTestProductionGenerator(t, genSym) + genLR0Item := newTestLR0ItemGenerator(t, genProd) + + expectedKernels := map[int][]*lrItem{ + 0: { + withLookAhead(genLR0Item("s'", 0, "s"), symbol.SymbolEOF), + }, + 1: { + withLookAhead(genLR0Item("s'", 1, "s"), symbol.SymbolEOF), + }, + 2: { + withLookAhead(genLR0Item("s", 1, "l", "eq", "r"), symbol.SymbolEOF), + withLookAhead(genLR0Item("r", 1, "l"), symbol.SymbolEOF), + }, + 3: { + withLookAhead(genLR0Item("s", 1, "r"), symbol.SymbolEOF), + }, + 4: { + withLookAhead(genLR0Item("l", 1, "ref", "r"), genSym("eq"), symbol.SymbolEOF), + }, + 5: { + withLookAhead(genLR0Item("l", 1, "id"), genSym("eq"), symbol.SymbolEOF), + }, + 6: { + withLookAhead(genLR0Item("s", 2, "l", "eq", "r"), symbol.SymbolEOF), + }, + 7: { + withLookAhead(genLR0Item("l", 2, "ref", "r"), genSym("eq"), symbol.SymbolEOF), + }, + 8: { + withLookAhead(genLR0Item("r", 1, "l"), genSym("eq"), symbol.SymbolEOF), + }, + 9: { + withLookAhead(genLR0Item("s", 3, "l", "eq", "r"), symbol.SymbolEOF), + }, + } + + expectedStates := []*expectedLRState{ + { + kernelItems: expectedKernels[0], + nextStates: map[symbol.Symbol][]*lrItem{ + genSym("s"): expectedKernels[1], + genSym("l"): expectedKernels[2], + genSym("r"): expectedKernels[3], + genSym("ref"): expectedKernels[4], + genSym("id"): expectedKernels[5], + }, + reducibleProds: []*production{}, + }, + { + kernelItems: expectedKernels[1], + nextStates: map[symbol.Symbol][]*lrItem{}, + reducibleProds: []*production{ + genProd("s'", "s"), + }, + }, + { + kernelItems: expectedKernels[2], + nextStates: map[symbol.Symbol][]*lrItem{ + genSym("eq"): expectedKernels[6], + }, + reducibleProds: []*production{ + genProd("r", "l"), + }, + }, + { + kernelItems: expectedKernels[3], + nextStates: map[symbol.Symbol][]*lrItem{}, + reducibleProds: []*production{ + genProd("s", "r"), + }, + }, + { + kernelItems: expectedKernels[4], + nextStates: map[symbol.Symbol][]*lrItem{ + genSym("r"): expectedKernels[7], + genSym("l"): expectedKernels[8], + genSym("ref"): expectedKernels[4], + genSym("id"): expectedKernels[5], + }, + reducibleProds: []*production{}, + }, + { + kernelItems: expectedKernels[5], + nextStates: map[symbol.Symbol][]*lrItem{}, + reducibleProds: []*production{ + genProd("l", "id"), + }, + }, + { + kernelItems: expectedKernels[6], + nextStates: map[symbol.Symbol][]*lrItem{ + genSym("r"): expectedKernels[9], + genSym("l"): expectedKernels[8], + genSym("ref"): expectedKernels[4], + genSym("id"): expectedKernels[5], + }, + reducibleProds: []*production{}, + }, + { + kernelItems: expectedKernels[7], + nextStates: map[symbol.Symbol][]*lrItem{}, + reducibleProds: []*production{ + genProd("l", "ref", "r"), + }, + }, + { + kernelItems: expectedKernels[8], + nextStates: map[symbol.Symbol][]*lrItem{}, + reducibleProds: []*production{ + genProd("r", "l"), + }, + }, + { + kernelItems: expectedKernels[9], + nextStates: map[symbol.Symbol][]*lrItem{}, + reducibleProds: []*production{ + genProd("s", "l", "eq", "r"), + }, + }, + } + + testLRAutomaton(t, expectedStates, automaton.lr0Automaton) +} + +type expectedLRState struct { + kernelItems []*lrItem + nextStates map[symbol.Symbol][]*lrItem + reducibleProds []*production + emptyProdItems []*lrItem +} + +func TestGenLR0Automaton(t *testing.T) { + 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_]*"; +` + + var gram *Grammar + var automaton *lr0Automaton + { + 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) + } + + automaton, err = genLR0Automaton(gram.productionSet, gram.augmentedStartSymbol, gram.errorSymbol) + if err != nil { + t.Fatalf("failed to create a LR0 automaton: %v", err) + } + if automaton == nil { + t.Fatalf("genLR0Automaton returns nil without any error") + } + } + + initialState := automaton.states[automaton.initialState] + if initialState == nil { + t.Errorf("failed to get an initial status: %v", automaton.initialState) + } + + genSym := newTestSymbolGenerator(t, gram.symbolTable) + genProd := newTestProductionGenerator(t, genSym) + genLR0Item := newTestLR0ItemGenerator(t, genProd) + + expectedKernels := map[int][]*lrItem{ + 0: { + genLR0Item("expr'", 0, "expr"), + }, + 1: { + genLR0Item("expr'", 1, "expr"), + genLR0Item("expr", 1, "expr", "add", "term"), + }, + 2: { + genLR0Item("expr", 1, "term"), + genLR0Item("term", 1, "term", "mul", "factor"), + }, + 3: { + genLR0Item("term", 1, "factor"), + }, + 4: { + genLR0Item("factor", 1, "l_paren", "expr", "r_paren"), + }, + 5: { + genLR0Item("factor", 1, "id"), + }, + 6: { + genLR0Item("expr", 2, "expr", "add", "term"), + }, + 7: { + genLR0Item("term", 2, "term", "mul", "factor"), + }, + 8: { + genLR0Item("expr", 1, "expr", "add", "term"), + genLR0Item("factor", 2, "l_paren", "expr", "r_paren"), + }, + 9: { + genLR0Item("expr", 3, "expr", "add", "term"), + genLR0Item("term", 1, "term", "mul", "factor"), + }, + 10: { + genLR0Item("term", 3, "term", "mul", "factor"), + }, + 11: { + genLR0Item("factor", 3, "l_paren", "expr", "r_paren"), + }, + } + + expectedStates := []*expectedLRState{ + { + kernelItems: expectedKernels[0], + nextStates: map[symbol.Symbol][]*lrItem{ + genSym("expr"): expectedKernels[1], + genSym("term"): expectedKernels[2], + genSym("factor"): expectedKernels[3], + genSym("l_paren"): expectedKernels[4], + genSym("id"): expectedKernels[5], + }, + reducibleProds: []*production{}, + }, + { + kernelItems: expectedKernels[1], + nextStates: map[symbol.Symbol][]*lrItem{ + genSym("add"): expectedKernels[6], + }, + reducibleProds: []*production{ + genProd("expr'", "expr"), + }, + }, + { + kernelItems: expectedKernels[2], + nextStates: map[symbol.Symbol][]*lrItem{ + genSym("mul"): expectedKernels[7], + }, + reducibleProds: []*production{ + genProd("expr", "term"), + }, + }, + { + kernelItems: expectedKernels[3], + nextStates: map[symbol.Symbol][]*lrItem{}, + reducibleProds: []*production{ + genProd("term", "factor"), + }, + }, + { + kernelItems: expectedKernels[4], + nextStates: map[symbol.Symbol][]*lrItem{ + genSym("expr"): expectedKernels[8], + genSym("term"): expectedKernels[2], + genSym("factor"): expectedKernels[3], + genSym("l_paren"): expectedKernels[4], + genSym("id"): expectedKernels[5], + }, + reducibleProds: []*production{}, + }, + { + kernelItems: expectedKernels[5], + nextStates: map[symbol.Symbol][]*lrItem{}, + reducibleProds: []*production{ + genProd("factor", "id"), + }, + }, + { + kernelItems: expectedKernels[6], + nextStates: map[symbol.Symbol][]*lrItem{ + genSym("term"): expectedKernels[9], + genSym("factor"): expectedKernels[3], + genSym("l_paren"): expectedKernels[4], + genSym("id"): expectedKernels[5], + }, + reducibleProds: []*production{}, + }, + { + kernelItems: expectedKernels[7], + nextStates: map[symbol.Symbol][]*lrItem{ + genSym("factor"): expectedKernels[10], + genSym("l_paren"): expectedKernels[4], + genSym("id"): expectedKernels[5], + }, + reducibleProds: []*production{}, + }, + { + kernelItems: expectedKernels[8], + nextStates: map[symbol.Symbol][]*lrItem{ + genSym("add"): expectedKernels[6], + genSym("r_paren"): expectedKernels[11], + }, + reducibleProds: []*production{}, + }, + { + kernelItems: expectedKernels[9], + nextStates: map[symbol.Symbol][]*lrItem{ + genSym("mul"): expectedKernels[7], + }, + reducibleProds: []*production{ + genProd("expr", "expr", "add", "term"), + }, + }, + { + kernelItems: expectedKernels[10], + nextStates: map[symbol.Symbol][]*lrItem{}, + reducibleProds: []*production{ + genProd("term", "term", "mul", "factor"), + }, + }, + { + kernelItems: expectedKernels[11], + nextStates: map[symbol.Symbol][]*lrItem{}, + reducibleProds: []*production{ + genProd("factor", "l_paren", "expr", "r_paren"), + }, + }, + } + + testLRAutomaton(t, expectedStates, automaton) +} + +func TestLR0AutomatonContainingEmptyProduction(t *testing.T) { + src := ` +#name test; + +s + : foo bar + ; +foo + : + ; +bar + : b + | + ; + +b: "bar"; +` + + var gram *Grammar + var automaton *lr0Automaton + { + 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) + } + + automaton, err = genLR0Automaton(gram.productionSet, gram.augmentedStartSymbol, gram.errorSymbol) + if err != nil { + t.Fatalf("failed to create a LR0 automaton: %v", err) + } + if automaton == nil { + t.Fatalf("genLR0Automaton returns nil without any error") + } + } + + initialState := automaton.states[automaton.initialState] + if initialState == nil { + t.Errorf("failed to get an initial status: %v", automaton.initialState) + } + + genSym := newTestSymbolGenerator(t, gram.symbolTable) + genProd := newTestProductionGenerator(t, genSym) + genLR0Item := newTestLR0ItemGenerator(t, genProd) + + expectedKernels := map[int][]*lrItem{ + 0: { + genLR0Item("s'", 0, "s"), + }, + 1: { + genLR0Item("s'", 1, "s"), + }, + 2: { + genLR0Item("s", 1, "foo", "bar"), + }, + 3: { + genLR0Item("s", 2, "foo", "bar"), + }, + 4: { + genLR0Item("bar", 1, "b"), + }, + } + + expectedStates := []*expectedLRState{ + { + kernelItems: expectedKernels[0], + nextStates: map[symbol.Symbol][]*lrItem{ + genSym("s"): expectedKernels[1], + genSym("foo"): expectedKernels[2], + }, + reducibleProds: []*production{ + genProd("foo"), + }, + emptyProdItems: []*lrItem{ + genLR0Item("foo", 0), + }, + }, + { + kernelItems: expectedKernels[1], + nextStates: map[symbol.Symbol][]*lrItem{}, + reducibleProds: []*production{ + genProd("s'", "s"), + }, + }, + { + kernelItems: expectedKernels[2], + nextStates: map[symbol.Symbol][]*lrItem{ + genSym("bar"): expectedKernels[3], + genSym("b"): expectedKernels[4], + }, + reducibleProds: []*production{ + genProd("bar"), + }, + emptyProdItems: []*lrItem{ + genLR0Item("bar", 0), + }, + }, + { + kernelItems: expectedKernels[3], + nextStates: map[symbol.Symbol][]*lrItem{}, + reducibleProds: []*production{ + genProd("s", "foo", "bar"), + }, + }, + { + kernelItems: expectedKernels[4], + nextStates: map[symbol.Symbol][]*lrItem{}, + reducibleProds: []*production{ + genProd("bar", "b"), + }, + }, + } + + testLRAutomaton(t, expectedStates, automaton) +} + +func testLRAutomaton(t *testing.T, expected []*expectedLRState, automaton *lr0Automaton) { + if len(automaton.states) != len(expected) { + t.Errorf("state count is mismatched; want: %v, got: %v", len(expected), len(automaton.states)) + } + + for i, eState := range expected { + t.Run(fmt.Sprintf("state #%v", i), func(t *testing.T) { + k, err := newKernel(eState.kernelItems) + if err != nil { + t.Fatalf("failed to create a kernel item: %v", err) + } + + state, ok := automaton.states[k.id] + if !ok { + t.Fatalf("a kernel was not found: %v", k.id) + } + + // test look-ahead symbols + { + if len(state.kernel.items) != len(eState.kernelItems) { + t.Errorf("kernels is mismatched; want: %v, got: %v", len(eState.kernelItems), len(state.kernel.items)) + } + for _, eKItem := range eState.kernelItems { + var kItem *lrItem + for _, it := range state.kernel.items { + if it.id != eKItem.id { + continue + } + kItem = it + break + } + if kItem == nil { + t.Fatalf("kernel item not found; want: %v, got: %v", eKItem.id, kItem.id) + } + + if len(kItem.lookAhead.symbols) != len(eKItem.lookAhead.symbols) { + t.Errorf("look-ahead symbols are mismatched; want: %v symbols, got: %v symbols", len(eKItem.lookAhead.symbols), len(kItem.lookAhead.symbols)) + } + + for eSym := range eKItem.lookAhead.symbols { + if _, ok := kItem.lookAhead.symbols[eSym]; !ok { + t.Errorf("look-ahead symbol not found: %v", eSym) + } + } + } + } + + // test next states + { + if len(state.next) != len(eState.nextStates) { + t.Errorf("next state count is mismcthed; want: %v, got: %v", len(eState.nextStates), len(state.next)) + } + for eSym, eKItems := range eState.nextStates { + nextStateKernel, err := newKernel(eKItems) + if err != nil { + t.Fatalf("failed to create a kernel item: %v", err) + } + nextState, ok := state.next[eSym] + if !ok { + t.Fatalf("next state was not found; state: %v, symbol: %v (%v)", state.id, "expr", eSym) + } + if nextState != nextStateKernel.id { + t.Fatalf("a kernel ID of the next state is mismatched; want: %v, got: %v", nextStateKernel.id, nextState) + } + } + } + + // test reducible productions + { + if len(state.reducible) != len(eState.reducibleProds) { + t.Errorf("reducible production count is mismatched; want: %v, got: %v", len(eState.reducibleProds), len(state.reducible)) + } + for _, eProd := range eState.reducibleProds { + if _, ok := state.reducible[eProd.id]; !ok { + t.Errorf("reducible production was not found: %v", eProd.id) + } + } + + if len(state.emptyProdItems) != len(eState.emptyProdItems) { + t.Errorf("empty production item is mismatched; want: %v, got: %v", len(eState.emptyProdItems), len(state.emptyProdItems)) + } + for _, eItem := range eState.emptyProdItems { + found := false + for _, item := range state.emptyProdItems { + if item.id != eItem.id { + continue + } + found = true + break + } + if !found { + t.Errorf("empty production item not found: %v", eItem.id) + } + } + } + }) + } +} + +type expectedState struct { + kernelItems []*lrItem + acts map[symbol.Symbol]testActionEntry + goTos map[symbol.Symbol][]*lrItem +} + +func TestGenLALRParsingTable(t *testing.T) { + src := ` +#name test; + +s: l eq r | r; +l: ref r | id; +r: l; +eq: '='; +ref: '*'; +id: "[A-Za-z0-9_]+"; +` + + var ptab *ParsingTable + var automaton *lalr1Automaton + var gram *Grammar + var nonTermCount int + var termCount int + { + 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) + } + first, err := genFirstSet(gram.productionSet) + if err != nil { + t.Fatal(err) + } + lr0, err := genLR0Automaton(gram.productionSet, gram.augmentedStartSymbol, gram.errorSymbol) + if err != nil { + t.Fatal(err) + } + automaton, err = genLALR1Automaton(lr0, gram.productionSet, first) + if err != nil { + t.Fatal(err) + } + + nonTermTexts, err := gram.symbolTable.NonTerminalTexts() + if err != nil { + t.Fatal(err) + } + termTexts, err := gram.symbolTable.TerminalTexts() + if err != nil { + t.Fatal(err) + } + nonTermCount = len(nonTermTexts) + termCount = len(termTexts) + + lalr := &lrTableBuilder{ + automaton: automaton.lr0Automaton, + prods: gram.productionSet, + termCount: termCount, + nonTermCount: nonTermCount, + symTab: gram.symbolTable, + } + ptab, err = lalr.build() + if err != nil { + t.Fatalf("failed to create a LALR parsing table: %v", err) + } + if ptab == nil { + t.Fatal("genLALRParsingTable returns nil without any error") + } + } + + genSym := newTestSymbolGenerator(t, gram.symbolTable) + genProd := newTestProductionGenerator(t, genSym) + genLR0Item := newTestLR0ItemGenerator(t, genProd) + + expectedKernels := map[int][]*lrItem{ + 0: { + withLookAhead(genLR0Item("s'", 0, "s"), symbol.SymbolEOF), + }, + 1: { + withLookAhead(genLR0Item("s'", 1, "s"), symbol.SymbolEOF), + }, + 2: { + withLookAhead(genLR0Item("s", 1, "l", "eq", "r"), symbol.SymbolEOF), + withLookAhead(genLR0Item("r", 1, "l"), symbol.SymbolEOF), + }, + 3: { + withLookAhead(genLR0Item("s", 1, "r"), symbol.SymbolEOF), + }, + 4: { + withLookAhead(genLR0Item("l", 1, "ref", "r"), genSym("eq"), symbol.SymbolEOF), + }, + 5: { + withLookAhead(genLR0Item("l", 1, "id"), genSym("eq"), symbol.SymbolEOF), + }, + 6: { + withLookAhead(genLR0Item("s", 2, "l", "eq", "r"), symbol.SymbolEOF), + }, + 7: { + withLookAhead(genLR0Item("l", 2, "ref", "r"), genSym("eq"), symbol.SymbolEOF), + }, + 8: { + withLookAhead(genLR0Item("r", 1, "l"), genSym("eq"), symbol.SymbolEOF), + }, + 9: { + withLookAhead(genLR0Item("s", 3, "l", "eq", "r"), symbol.SymbolEOF), + }, + } + + expectedStates := []expectedState{ + { + kernelItems: expectedKernels[0], + acts: map[symbol.Symbol]testActionEntry{ + genSym("ref"): { + ty: ActionTypeShift, + nextState: expectedKernels[4], + }, + genSym("id"): { + ty: ActionTypeShift, + nextState: expectedKernels[5], + }, + }, + goTos: map[symbol.Symbol][]*lrItem{ + genSym("s"): expectedKernels[1], + genSym("l"): expectedKernels[2], + genSym("r"): expectedKernels[3], + }, + }, + { + kernelItems: expectedKernels[1], + acts: map[symbol.Symbol]testActionEntry{ + symbol.SymbolEOF: { + ty: ActionTypeReduce, + production: genProd("s'", "s"), + }, + }, + }, + { + kernelItems: expectedKernels[2], + acts: map[symbol.Symbol]testActionEntry{ + genSym("eq"): { + ty: ActionTypeShift, + nextState: expectedKernels[6], + }, + symbol.SymbolEOF: { + ty: ActionTypeReduce, + production: genProd("r", "l"), + }, + }, + }, + { + kernelItems: expectedKernels[3], + acts: map[symbol.Symbol]testActionEntry{ + symbol.SymbolEOF: { + ty: ActionTypeReduce, + production: genProd("s", "r"), + }, + }, + }, + { + kernelItems: expectedKernels[4], + acts: map[symbol.Symbol]testActionEntry{ + genSym("ref"): { + ty: ActionTypeShift, + nextState: expectedKernels[4], + }, + genSym("id"): { + ty: ActionTypeShift, + nextState: expectedKernels[5], + }, + }, + goTos: map[symbol.Symbol][]*lrItem{ + genSym("r"): expectedKernels[7], + genSym("l"): expectedKernels[8], + }, + }, + { + kernelItems: expectedKernels[5], + acts: map[symbol.Symbol]testActionEntry{ + genSym("eq"): { + ty: ActionTypeReduce, + production: genProd("l", "id"), + }, + symbol.SymbolEOF: { + ty: ActionTypeReduce, + production: genProd("l", "id"), + }, + }, + }, + { + kernelItems: expectedKernels[6], + acts: map[symbol.Symbol]testActionEntry{ + genSym("ref"): { + ty: ActionTypeShift, + nextState: expectedKernels[4], + }, + genSym("id"): { + ty: ActionTypeShift, + nextState: expectedKernels[5], + }, + }, + goTos: map[symbol.Symbol][]*lrItem{ + genSym("l"): expectedKernels[8], + genSym("r"): expectedKernels[9], + }, + }, + { + kernelItems: expectedKernels[7], + acts: map[symbol.Symbol]testActionEntry{ + genSym("eq"): { + ty: ActionTypeReduce, + production: genProd("l", "ref", "r"), + }, + symbol.SymbolEOF: { + ty: ActionTypeReduce, + production: genProd("l", "ref", "r"), + }, + }, + }, + { + kernelItems: expectedKernels[8], + acts: map[symbol.Symbol]testActionEntry{ + genSym("eq"): { + ty: ActionTypeReduce, + production: genProd("r", "l"), + }, + symbol.SymbolEOF: { + ty: ActionTypeReduce, + production: genProd("r", "l"), + }, + }, + }, + { + kernelItems: expectedKernels[9], + acts: map[symbol.Symbol]testActionEntry{ + symbol.SymbolEOF: { + ty: ActionTypeReduce, + production: genProd("s", "l", "eq", "r"), + }, + }, + }, + } + + t.Run("initial state", func(t *testing.T) { + iniState := findStateByNum(automaton.states, ptab.InitialState) + if iniState == nil { + t.Fatalf("the initial state was not found: #%v", ptab.InitialState) + } + eIniState, err := newKernel(expectedKernels[0]) + if err != nil { + t.Fatalf("failed to create a kernel item: %v", err) + } + if iniState.id != eIniState.id { + t.Fatalf("the initial state is mismatched; want: %v, got: %v", eIniState.id, iniState.id) + } + }) + + for i, eState := range expectedStates { + t.Run(fmt.Sprintf("#%v", i), func(t *testing.T) { + k, err := newKernel(eState.kernelItems) + if err != nil { + t.Fatalf("failed to create a kernel item: %v", err) + } + state, ok := automaton.states[k.id] + if !ok { + t.Fatalf("state was not found: #%v", 0) + } + + testAction(t, &eState, state, ptab, automaton.lr0Automaton, gram, termCount) + testGoTo(t, &eState, state, ptab, automaton.lr0Automaton, nonTermCount) + }) + } +} + +func testAction(t *testing.T, expectedState *expectedState, state *lrState, ptab *ParsingTable, automaton *lr0Automaton, gram *Grammar, termCount int) { + nonEmptyEntries := map[symbol.SymbolNum]struct{}{} + for eSym, eAct := range expectedState.acts { + nonEmptyEntries[eSym.Num()] = struct{}{} + + ty, stateNum, prodNum := ptab.getAction(state.num, eSym.Num()) + if ty != eAct.ty { + t.Fatalf("action type is mismatched; want: %v, got: %v", eAct.ty, ty) + } + switch eAct.ty { + case ActionTypeShift: + eNextState, err := newKernel(eAct.nextState) + if err != nil { + t.Fatal(err) + } + nextState := findStateByNum(automaton.states, stateNum) + if nextState == nil { + t.Fatalf("state was not found; state: #%v", stateNum) + } + if nextState.id != eNextState.id { + t.Fatalf("next state is mismatched; symbol: %v, want: %v, got: %v", eSym, eNextState.id, nextState.id) + } + case ActionTypeReduce: + prod := findProductionByNum(gram.productionSet, prodNum) + if prod == nil { + t.Fatalf("production was not found: #%v", prodNum) + } + if prod.id != eAct.production.id { + t.Fatalf("production is mismatched; symbol: %v, want: %v, got: %v", eSym, eAct.production.id, prod.id) + } + } + } + for symNum := 0; symNum < termCount; symNum++ { + if _, checked := nonEmptyEntries[symbol.SymbolNum(symNum)]; checked { + continue + } + ty, stateNum, prodNum := ptab.getAction(state.num, symbol.SymbolNum(symNum)) + if ty != ActionTypeError { + t.Errorf("unexpected ACTION entry; state: #%v, symbol: #%v, action type: %v, next state: #%v, prodction: #%v", state.num, symNum, ty, stateNum, prodNum) + } + } +} + +func testGoTo(t *testing.T, expectedState *expectedState, state *lrState, ptab *ParsingTable, automaton *lr0Automaton, nonTermCount int) { + nonEmptyEntries := map[symbol.SymbolNum]struct{}{} + for eSym, eGoTo := range expectedState.goTos { + nonEmptyEntries[eSym.Num()] = struct{}{} + + eNextState, err := newKernel(eGoTo) + if err != nil { + t.Fatal(err) + } + ty, stateNum := ptab.getGoTo(state.num, eSym.Num()) + if ty != GoToTypeRegistered { + t.Fatalf("GOTO entry was not found; state: #%v, symbol: #%v", state.num, eSym) + } + nextState := findStateByNum(automaton.states, stateNum) + if nextState == nil { + t.Fatalf("state was not found: #%v", stateNum) + } + if nextState.id != eNextState.id { + t.Fatalf("next state is mismatched; symbol: %v, want: %v, got: %v", eSym, eNextState.id, nextState.id) + } + } + for symNum := 0; symNum < nonTermCount; symNum++ { + if _, checked := nonEmptyEntries[symbol.SymbolNum(symNum)]; checked { + continue + } + ty, _ := ptab.getGoTo(state.num, symbol.SymbolNum(symNum)) + if ty != GoToTypeError { + t.Errorf("unexpected GOTO entry; state: #%v, symbol: #%v", state.num, symNum) + } + } +} + +type testActionEntry struct { + ty ActionType + nextState []*lrItem + production *production +} + +func findStateByNum(states map[kernelID]*lrState, num stateNum) *lrState { + for _, state := range states { + if state.num == num { + return state + } + } + return nil +} + +func findProductionByNum(prods *productionSet, num productionNum) *production { + for _, prod := range prods.getAllProductions() { + if prod.num == num { + return prod + } + } + return nil +} + +type testSymbolGenerator func(text string) symbol.Symbol + +func newTestSymbolGenerator(t *testing.T, symTab *symbol.SymbolTableReader) testSymbolGenerator { + return func(text string) symbol.Symbol { + t.Helper() + + sym, ok := symTab.ToSymbol(text) + if !ok { + t.Fatalf("symbol was not found: %v", text) + } + return sym + } +} + +type testProductionGenerator func(lhs string, rhs ...string) *production + +func newTestProductionGenerator(t *testing.T, genSym testSymbolGenerator) testProductionGenerator { + return func(lhs string, rhs ...string) *production { + t.Helper() + + rhsSym := []symbol.Symbol{} + for _, text := range rhs { + rhsSym = append(rhsSym, genSym(text)) + } + prod, err := newProduction(genSym(lhs), rhsSym) + if err != nil { + t.Fatalf("failed to create a production: %v", err) + } + + return prod + } +} + +type testLR0ItemGenerator func(lhs string, dot int, rhs ...string) *lrItem + +func newTestLR0ItemGenerator(t *testing.T, genProd testProductionGenerator) testLR0ItemGenerator { + return func(lhs string, dot int, rhs ...string) *lrItem { + t.Helper() + + prod := genProd(lhs, rhs...) + item, err := newLR0Item(prod, dot) + if err != nil { + t.Fatalf("failed to create a LR0 item: %v", err) + } + + return item + } +} + +func withLookAhead(item *lrItem, lookAhead ...symbol.Symbol) *lrItem { + if item.lookAhead.symbols == nil { + item.lookAhead.symbols = map[symbol.Symbol]struct{}{} + } + + for _, a := range lookAhead { + item.lookAhead.symbols[a] = struct{}{} + } + + return item +} |