aboutsummaryrefslogtreecommitdiff
path: root/grammar/parsing_table_test.go
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--grammar/parsing_table_test.go386
1 files changed, 0 insertions, 386 deletions
diff --git a/grammar/parsing_table_test.go b/grammar/parsing_table_test.go
index 4ce8455..a699728 100644
--- a/grammar/parsing_table_test.go
+++ b/grammar/parsing_table_test.go
@@ -286,392 +286,6 @@ id: "[A-Za-z0-9_]+";
}
}
-func TestGenSLRParsingTable(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 ptab *ParsingTable
- var automaton *slr1Automaton
- var gram *Grammar
- var nonTermCount int
- var termCount int
- {
- ast, err := spec.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)
- }
- follow, err := genFollowSet(gram.productionSet, first)
- if err != nil {
- t.Fatal(err)
- }
- lr0, err := genLR0Automaton(gram.productionSet, gram.augmentedStartSymbol, gram.errorSymbol)
- if err != nil {
- t.Fatal(err)
- }
- automaton, err = genSLR1Automaton(lr0, gram.productionSet, follow)
- 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)
-
- slr := &lrTableBuilder{
- automaton: automaton.lr0Automaton,
- prods: gram.productionSet,
- termCount: termCount,
- nonTermCount: nonTermCount,
- symTab: gram.symbolTable,
- }
- ptab, err = slr.build()
- if err != nil {
- t.Fatalf("failed to create a SLR parsing table: %v", err)
- }
- if ptab == nil {
- t.Fatal("genSLRParsingTable returns nil without any error")
- }
- }
-
- 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 := []expectedState{
- {
- kernelItems: expectedKernels[0],
- acts: map[symbol]testActionEntry{
- genSym("l_paren"): {
- ty: ActionTypeShift,
- nextState: expectedKernels[4],
- },
- genSym("id"): {
- ty: ActionTypeShift,
- nextState: expectedKernels[5],
- },
- },
- goTos: map[symbol][]*lrItem{
- genSym("expr"): expectedKernels[1],
- genSym("term"): expectedKernels[2],
- genSym("factor"): expectedKernels[3],
- },
- },
- {
- kernelItems: expectedKernels[1],
- acts: map[symbol]testActionEntry{
- genSym("add"): {
- ty: ActionTypeShift,
- nextState: expectedKernels[6],
- },
- symbolEOF: {
- ty: ActionTypeReduce,
- production: genProd("expr'", "expr"),
- },
- },
- },
- {
- kernelItems: expectedKernels[2],
- acts: map[symbol]testActionEntry{
- genSym("add"): {
- ty: ActionTypeReduce,
- production: genProd("expr", "term"),
- },
- genSym("mul"): {
- ty: ActionTypeShift,
- nextState: expectedKernels[7],
- },
- genSym("r_paren"): {
- ty: ActionTypeReduce,
- production: genProd("expr", "term"),
- },
- symbolEOF: {
- ty: ActionTypeReduce,
- production: genProd("expr", "term"),
- },
- },
- },
- {
- kernelItems: expectedKernels[3],
- acts: map[symbol]testActionEntry{
- genSym("add"): {
- ty: ActionTypeReduce,
- production: genProd("term", "factor"),
- },
- genSym("mul"): {
- ty: ActionTypeReduce,
- production: genProd("term", "factor"),
- },
- genSym("r_paren"): {
- ty: ActionTypeReduce,
- production: genProd("term", "factor"),
- },
- symbolEOF: {
- ty: ActionTypeReduce,
- production: genProd("term", "factor"),
- },
- },
- },
- {
- kernelItems: expectedKernels[4],
- acts: map[symbol]testActionEntry{
- genSym("l_paren"): {
- ty: ActionTypeShift,
- nextState: expectedKernels[4],
- },
- genSym("id"): {
- ty: ActionTypeShift,
- nextState: expectedKernels[5],
- },
- },
- goTos: map[symbol][]*lrItem{
- genSym("expr"): expectedKernels[8],
- genSym("term"): expectedKernels[2],
- genSym("factor"): expectedKernels[3],
- },
- },
- {
- kernelItems: expectedKernels[5],
- acts: map[symbol]testActionEntry{
- genSym("add"): {
- ty: ActionTypeReduce,
- production: genProd("factor", "id"),
- },
- genSym("mul"): {
- ty: ActionTypeReduce,
- production: genProd("factor", "id"),
- },
- genSym("r_paren"): {
- ty: ActionTypeReduce,
- production: genProd("factor", "id"),
- },
- symbolEOF: {
- ty: ActionTypeReduce,
- production: genProd("factor", "id"),
- },
- },
- },
- {
- kernelItems: expectedKernels[6],
- acts: map[symbol]testActionEntry{
- genSym("l_paren"): {
- ty: ActionTypeShift,
- nextState: expectedKernels[4],
- },
- genSym("id"): {
- ty: ActionTypeShift,
- nextState: expectedKernels[5],
- },
- },
- goTos: map[symbol][]*lrItem{
- genSym("term"): expectedKernels[9],
- genSym("factor"): expectedKernels[3],
- },
- },
- {
- kernelItems: expectedKernels[7],
- acts: map[symbol]testActionEntry{
- genSym("l_paren"): {
- ty: ActionTypeShift,
- nextState: expectedKernels[4],
- },
- genSym("id"): {
- ty: ActionTypeShift,
- nextState: expectedKernels[5],
- },
- },
- goTos: map[symbol][]*lrItem{
- genSym("factor"): expectedKernels[10],
- },
- },
- {
- kernelItems: expectedKernels[8],
- acts: map[symbol]testActionEntry{
- genSym("add"): {
- ty: ActionTypeShift,
- nextState: expectedKernels[6],
- },
- genSym("r_paren"): {
- ty: ActionTypeShift,
- nextState: expectedKernels[11],
- },
- },
- },
- {
- kernelItems: expectedKernels[9],
- acts: map[symbol]testActionEntry{
- genSym("add"): {
- ty: ActionTypeReduce,
- production: genProd("expr", "expr", "add", "term"),
- },
- genSym("mul"): {
- ty: ActionTypeShift,
- nextState: expectedKernels[7],
- },
- genSym("r_paren"): {
- ty: ActionTypeReduce,
- production: genProd("expr", "expr", "add", "term"),
- },
- symbolEOF: {
- ty: ActionTypeReduce,
- production: genProd("expr", "expr", "add", "term"),
- },
- },
- },
- {
- kernelItems: expectedKernels[10],
- acts: map[symbol]testActionEntry{
- genSym("add"): {
- ty: ActionTypeReduce,
- production: genProd("term", "term", "mul", "factor"),
- },
- genSym("mul"): {
- ty: ActionTypeReduce,
- production: genProd("term", "term", "mul", "factor"),
- },
- genSym("r_paren"): {
- ty: ActionTypeReduce,
- production: genProd("term", "term", "mul", "factor"),
- },
- symbolEOF: {
- ty: ActionTypeReduce,
- production: genProd("term", "term", "mul", "factor"),
- },
- },
- },
- {
- kernelItems: expectedKernels[11],
- acts: map[symbol]testActionEntry{
- genSym("add"): {
- ty: ActionTypeReduce,
- production: genProd("factor", "l_paren", "expr", "r_paren"),
- },
- genSym("mul"): {
- ty: ActionTypeReduce,
- production: genProd("factor", "l_paren", "expr", "r_paren"),
- },
- genSym("r_paren"): {
- ty: ActionTypeReduce,
- production: genProd("factor", "l_paren", "expr", "r_paren"),
- },
- symbolEOF: {
- ty: ActionTypeReduce,
- production: genProd("factor", "l_paren", "expr", "r_paren"),
- },
- },
- },
- }
-
- 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[symbolNum]struct{}{}
for eSym, eAct := range expectedState.acts {
generated by cgit v1.2.3 (git 2.49.0) at 2025-07-13 22:40:05 +0000