aboutsummaryrefslogtreecommitdiff
path: root/grammar
diff options
context:
space:
mode:
Diffstat (limited to 'grammar')
-rw-r--r--grammar/follow.go145
-rw-r--r--grammar/follow_test.go204
-rw-r--r--grammar/grammar.go49
-rw-r--r--grammar/parsing_table.go2
-rw-r--r--grammar/parsing_table_test.go386
-rw-r--r--grammar/slr1.go61
-rw-r--r--grammar/slr1_test.go233
7 files changed, 4 insertions, 1076 deletions
diff --git a/grammar/follow.go b/grammar/follow.go
deleted file mode 100644
index 67e5f70..0000000
--- a/grammar/follow.go
+++ /dev/null
@@ -1,145 +0,0 @@
-package grammar
-
-import (
- "fmt"
-)
-
-type followEntry struct {
- symbols map[symbol]struct{}
- eof bool
-}
-
-func newFollowEntry() *followEntry {
- return &followEntry{
- symbols: map[symbol]struct{}{},
- eof: false,
- }
-}
-
-func (e *followEntry) add(sym symbol) bool {
- if _, ok := e.symbols[sym]; ok {
- return false
- }
- e.symbols[sym] = struct{}{}
- return true
-}
-
-func (e *followEntry) addEOF() bool {
- if !e.eof {
- e.eof = true
- return true
- }
- return false
-}
-
-func (e *followEntry) merge(fst *firstEntry, flw *followEntry) bool {
- changed := false
-
- if fst != nil {
- for sym := range fst.symbols {
- added := e.add(sym)
- if added {
- changed = true
- }
- }
- }
-
- if flw != nil {
- for sym := range flw.symbols {
- added := e.add(sym)
- if added {
- changed = true
- }
- }
- if flw.eof {
- added := e.addEOF()
- if added {
- changed = true
- }
- }
- }
-
- return changed
-}
-
-type followSet struct {
- set map[symbol]*followEntry
-}
-
-func newFollow(prods *productionSet) *followSet {
- flw := &followSet{
- set: map[symbol]*followEntry{},
- }
- for _, prod := range prods.getAllProductions() {
- if _, ok := flw.set[prod.lhs]; ok {
- continue
- }
- flw.set[prod.lhs] = newFollowEntry()
- }
- return flw
-}
-
-func (flw *followSet) find(sym symbol) (*followEntry, error) {
- e, ok := flw.set[sym]
- if !ok {
- return nil, fmt.Errorf("an entry of FOLLOW was not found; symbol: %s", sym)
- }
- return e, nil
-}
-
-func genFollowSet(prods *productionSet, first *firstSet) (*followSet, error) {
- ntsyms := map[symbol]struct{}{}
- for _, prod := range prods.getAllProductions() {
- if _, ok := ntsyms[prod.lhs]; ok {
- continue
- }
- ntsyms[prod.lhs] = struct{}{}
- }
-
- follow := newFollow(prods)
- for {
- more := false
- for ntsym := range ntsyms {
- e, err := follow.find(ntsym)
- if err != nil {
- return nil, err
- }
- if ntsym.isStart() {
- changed := e.addEOF()
- if changed {
- more = true
- }
- }
- for _, prod := range prods.getAllProductions() {
- for i, sym := range prod.rhs {
- if sym != ntsym {
- continue
- }
- fst, err := first.find(prod, i+1)
- if err != nil {
- return nil, err
- }
- changed := e.merge(fst, nil)
- if changed {
- more = true
- }
- if fst.empty {
- flw, err := follow.find(prod.lhs)
- if err != nil {
- return nil, err
- }
- changed := e.merge(nil, flw)
- if changed {
- more = true
- }
- }
- }
- }
- }
- if !more {
- break
- }
- }
-
- return follow, nil
-}
diff --git a/grammar/follow_test.go b/grammar/follow_test.go
deleted file mode 100644
index 719582f..0000000
--- a/grammar/follow_test.go
+++ /dev/null
@@ -1,204 +0,0 @@
-package grammar
-
-import (
- "strings"
- "testing"
-
- "github.com/nihei9/vartan/spec"
-)
-
-type follow struct {
- nonTermText string
- symbols []string
- eof bool
-}
-
-func TestFollowSet(t *testing.T) {
- tests := []struct {
- caption string
- src string
- follow []follow
- }{
- {
- 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_]*";
-`,
- follow: []follow{
- {nonTermText: "expr'", symbols: []string{}, eof: true},
- {nonTermText: "expr", symbols: []string{"add", "r_paren"}, eof: true},
- {nonTermText: "term", symbols: []string{"add", "mul", "r_paren"}, eof: true},
- {nonTermText: "factor", symbols: []string{"add", "mul", "r_paren"}, eof: true},
- },
- },
- {
- caption: "productions contain an empty start production",
- src: `
-#name test;
-
-s
- :
- ;
-`,
- follow: []follow{
- {nonTermText: "s'", symbols: []string{}, eof: true},
- {nonTermText: "s", symbols: []string{}, eof: true},
- },
- },
- {
- caption: "productions contain an empty production",
- src: `
-#name test;
-
-s
- : foo
- ;
-foo
- :
-;
-`,
- follow: []follow{
- {nonTermText: "s'", symbols: []string{}, eof: true},
- {nonTermText: "s", symbols: []string{}, eof: true},
- {nonTermText: "foo", symbols: []string{}, eof: true},
- },
- },
- {
- caption: "a start production contains a non-empty alternative and empty alternative",
- src: `
-#name test;
-
-s
- : foo
- |
- ;
-foo: "foo";
-`,
- follow: []follow{
- {nonTermText: "s'", symbols: []string{}, eof: true},
- {nonTermText: "s", symbols: []string{}, eof: true},
- },
- },
- {
- caption: "a production contains non-empty alternative and empty alternative",
- src: `
-#name test;
-
-s
- : foo
- ;
-foo
- : bar
- |
- ;
-bar: "bar";
-`,
- follow: []follow{
- {nonTermText: "s'", symbols: []string{}, eof: true},
- {nonTermText: "s", symbols: []string{}, eof: true},
- {nonTermText: "foo", symbols: []string{}, eof: true},
- },
- },
- }
- for _, tt := range tests {
- t.Run(tt.caption, func(t *testing.T) {
- flw, gram := genActualFollow(t, tt.src)
-
- for _, ttFollow := range tt.follow {
- sym, ok := gram.symbolTable.toSymbol(ttFollow.nonTermText)
- if !ok {
- t.Fatalf("a symbol '%v' was not found", ttFollow.nonTermText)
- }
-
- actualFollow, err := flw.find(sym)
- if err != nil {
- t.Fatalf("failed to get a FOLLOW entry; non-terminal symbol: %v (%v), error: %v", ttFollow.nonTermText, sym, err)
- }
-
- expectedFollow := genExpectedFollowEntry(t, ttFollow.symbols, ttFollow.eof, gram.symbolTable)
-
- testFollow(t, actualFollow, expectedFollow)
- }
- })
- }
-}
-
-func genActualFollow(t *testing.T, src string) (*followSet, *Grammar) {
- 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)
- }
- fst, err := genFirstSet(gram.productionSet)
- if err != nil {
- t.Fatal(err)
- }
- flw, err := genFollowSet(gram.productionSet, fst)
- if err != nil {
- t.Fatal(err)
- }
- if flw == nil {
- t.Fatal("genFollow returned nil without any error")
- }
-
- return flw, gram
-}
-
-func genExpectedFollowEntry(t *testing.T, symbols []string, eof bool, symTab *symbolTable) *followEntry {
- t.Helper()
-
- entry := newFollowEntry()
- if eof {
- entry.addEOF()
- }
- for _, sym := range symbols {
- symID, _ := symTab.toSymbol(sym)
- if symID.isNil() {
- t.Fatalf("a symbol '%v' was not found", sym)
- }
-
- entry.add(symID)
- }
-
- return entry
-}
-
-func testFollow(t *testing.T, actual, expected *followEntry) {
- if actual.eof != expected.eof {
- t.Errorf("eof is mismatched; want: %v, got: %v", expected.eof, actual.eof)
- }
-
- if len(actual.symbols) != len(expected.symbols) {
- t.Fatalf("unexpected symbol count of a FOLLOW entry; want: %v, got: %v", expected.symbols, actual.symbols)
- }
-
- for eSym := range expected.symbols {
- if _, ok := actual.symbols[eSym]; !ok {
- t.Fatalf("invalid FOLLOW entry; want: %v, got: %v", expected.symbols, actual.symbols)
- }
- }
-}
diff --git a/grammar/grammar.go b/grammar/grammar.go
index 410236b..368ede6 100644
--- a/grammar/grammar.go
+++ b/grammar/grammar.go
@@ -1286,16 +1286,8 @@ func (b *GrammarBuilder) genPrecAndAssoc(symTab *symbolTable, errSym symbol, pro
}, nil
}
-type Class string
-
-const (
- ClassSLR Class = "SLR(1)"
- ClassLALR Class = "LALR(1)"
-)
-
type compileConfig struct {
reportFileName string
- class Class
}
type CompileOption func(config *compileConfig)
@@ -1306,16 +1298,8 @@ func EnableReporting(fileName string) CompileOption {
}
}
-func SpecifyClass(class Class) CompileOption {
- return func(config *compileConfig) {
- config.class = class
- }
-}
-
func Compile(gram *Grammar, opts ...CompileOption) (*spec.CompiledGrammar, error) {
- config := &compileConfig{
- class: ClassLALR,
- }
+ config := &compileConfig{}
for _, opt := range opts {
opt(config)
}
@@ -1385,39 +1369,15 @@ func Compile(gram *Grammar, opts ...CompileOption) (*spec.CompiledGrammar, error
return nil, err
}
- var class string
- var automaton *lr0Automaton
- switch config.class {
- case ClassSLR:
- class = "slr"
-
- followSet, err := genFollowSet(gram.productionSet, firstSet)
- if err != nil {
- return nil, err
- }
-
- slr1, err := genSLR1Automaton(lr0, gram.productionSet, followSet)
- if err != nil {
- return nil, err
- }
-
- automaton = slr1.lr0Automaton
- case ClassLALR:
- class = "lalr"
-
+ var tab *ParsingTable
+ {
lalr1, err := genLALR1Automaton(lr0, gram.productionSet, firstSet)
if err != nil {
return nil, err
}
- automaton = lalr1.lr0Automaton
- }
-
- var tab *ParsingTable
- {
b := &lrTableBuilder{
- class: config.class,
- automaton: automaton,
+ automaton: lalr1.lr0Automaton,
prods: gram.productionSet,
termCount: len(terms),
nonTermCount: len(nonTerms),
@@ -1520,7 +1480,6 @@ func Compile(gram *Grammar, opts ...CompileOption) (*spec.CompiledGrammar, error
},
},
ParsingTable: &spec.ParsingTable{
- Class: class,
Action: action,
GoTo: goTo,
StateCount: tab.stateCount,
diff --git a/grammar/parsing_table.go b/grammar/parsing_table.go
index 57badd5..fd490b0 100644
--- a/grammar/parsing_table.go
+++ b/grammar/parsing_table.go
@@ -147,7 +147,6 @@ func (t *ParsingTable) writeGoTo(state stateNum, sym symbol, nextState stateNum)
}
type lrTableBuilder struct {
- class Class
automaton *lr0Automaton
prods *productionSet
termCount int
@@ -553,7 +552,6 @@ func (b *lrTableBuilder) genReport(tab *ParsingTable, gram *Grammar) (*spec.Repo
}
return &spec.Report{
- Class: string(b.class),
Terminals: terms,
NonTerminals: nonTerms,
Productions: prods,
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 {
diff --git a/grammar/slr1.go b/grammar/slr1.go
deleted file mode 100644
index b11a66f..0000000
--- a/grammar/slr1.go
+++ /dev/null
@@ -1,61 +0,0 @@
-package grammar
-
-import "fmt"
-
-type slr1Automaton struct {
- *lr0Automaton
-}
-
-func genSLR1Automaton(lr0 *lr0Automaton, prods *productionSet, follow *followSet) (*slr1Automaton, error) {
- for _, state := range lr0.states {
- for prodID := range state.reducible {
- prod, ok := prods.findByID(prodID)
- if !ok {
- return nil, fmt.Errorf("reducible production not found: %v", prodID)
- }
-
- flw, err := follow.find(prod.lhs)
- if err != nil {
- return nil, err
- }
-
- var reducibleItem *lrItem
- for _, item := range state.items {
- if item.prod != prodID {
- continue
- }
-
- reducibleItem = item
- break
- }
- if reducibleItem == nil {
- for _, item := range state.emptyProdItems {
- if item.prod != prodID {
- continue
- }
-
- reducibleItem = item
- break
- }
- if reducibleItem == nil {
- return nil, fmt.Errorf("reducible item not found; state: %v, production: %v", state.num, prodID)
- }
- }
-
- if reducibleItem.lookAhead.symbols == nil {
- reducibleItem.lookAhead.symbols = map[symbol]struct{}{}
- }
-
- for sym := range flw.symbols {
- reducibleItem.lookAhead.symbols[sym] = struct{}{}
- }
- if flw.eof {
- reducibleItem.lookAhead.symbols[symbolEOF] = struct{}{}
- }
- }
- }
-
- return &slr1Automaton{
- lr0Automaton: lr0,
- }, nil
-}
diff --git a/grammar/slr1_test.go b/grammar/slr1_test.go
deleted file mode 100644
index 6748802..0000000
--- a/grammar/slr1_test.go
+++ /dev/null
@@ -1,233 +0,0 @@
-package grammar
-
-import (
- "strings"
- "testing"
-
- "github.com/nihei9/vartan/spec"
-)
-
-func TestGenSLR1Automaton(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 *slr1Automaton
- {
- 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)
- }
-
- 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)
- }
-
- followSet, err := genFollowSet(gram.productionSet, firstSet)
- if err != nil {
- t.Fatalf("failed to create a FOLLOW set: %v", err)
- }
-
- automaton, err = genSLR1Automaton(lr0, gram.productionSet, followSet)
- if err != nil {
- t.Fatalf("failed to create a SLR1 automaton: %v", err)
- }
- if automaton == nil {
- t.Fatalf("genSLR1Automaton 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: {
- withLookAhead(genLR0Item("expr'", 1, "expr"), symbolEOF),
- genLR0Item("expr", 1, "expr", "add", "term"),
- },
- 2: {
- withLookAhead(genLR0Item("expr", 1, "term"), genSym("add"), genSym("r_paren"), symbolEOF),
- genLR0Item("term", 1, "term", "mul", "factor"),
- },
- 3: {
- withLookAhead(genLR0Item("term", 1, "factor"), genSym("add"), genSym("mul"), genSym("r_paren"), symbolEOF),
- },
- 4: {
- genLR0Item("factor", 1, "l_paren", "expr", "r_paren"),
- },
- 5: {
- withLookAhead(genLR0Item("factor", 1, "id"), genSym("add"), genSym("mul"), genSym("r_paren"), symbolEOF),
- },
- 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: {
- withLookAhead(genLR0Item("expr", 3, "expr", "add", "term"), genSym("add"), genSym("r_paren"), symbolEOF),
- genLR0Item("term", 1, "term", "mul", "factor"),
- },
- 10: {
- withLookAhead(genLR0Item("term", 3, "term", "mul", "factor"), genSym("add"), genSym("mul"), genSym("r_paren"), symbolEOF),
- },
- 11: {
- withLookAhead(genLR0Item("factor", 3, "l_paren", "expr", "r_paren"), genSym("add"), genSym("mul"), genSym("r_paren"), symbolEOF),
- },
- }
-
- expectedStates := []*expectedLRState{
- {
- kernelItems: expectedKernels[0],
- nextStates: map[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][]*lrItem{
- genSym("add"): expectedKernels[6],
- },
- reducibleProds: []*production{
- genProd("expr'", "expr"),
- },
- },
- {
- kernelItems: expectedKernels[2],
- nextStates: map[symbol][]*lrItem{
- genSym("mul"): expectedKernels[7],
- },
- reducibleProds: []*production{
- genProd("expr", "term"),
- },
- },
- {
- kernelItems: expectedKernels[3],
- nextStates: map[symbol][]*lrItem{},
- reducibleProds: []*production{
- genProd("term", "factor"),
- },
- },
- {
- kernelItems: expectedKernels[4],
- nextStates: map[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][]*lrItem{},
- reducibleProds: []*production{
- genProd("factor", "id"),
- },
- },
- {
- kernelItems: expectedKernels[6],
- nextStates: map[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][]*lrItem{
- genSym("factor"): expectedKernels[10],
- genSym("l_paren"): expectedKernels[4],
- genSym("id"): expectedKernels[5],
- },
- reducibleProds: []*production{},
- },
- {
- kernelItems: expectedKernels[8],
- nextStates: map[symbol][]*lrItem{
- genSym("add"): expectedKernels[6],
- genSym("r_paren"): expectedKernels[11],
- },
- reducibleProds: []*production{},
- },
- {
- kernelItems: expectedKernels[9],
- nextStates: map[symbol][]*lrItem{
- genSym("mul"): expectedKernels[7],
- },
- reducibleProds: []*production{
- genProd("expr", "expr", "add", "term"),
- },
- },
- {
- kernelItems: expectedKernels[10],
- nextStates: map[symbol][]*lrItem{},
- reducibleProds: []*production{
- genProd("term", "term", "mul", "factor"),
- },
- },
- {
- kernelItems: expectedKernels[11],
- nextStates: map[symbol][]*lrItem{},
- reducibleProds: []*production{
- genProd("factor", "l_paren", "expr", "r_paren"),
- },
- },
- }
-
- testLRAutomaton(t, expectedStates, automaton.lr0Automaton)
-}
generated by cgit v1.2.3 (git 2.49.0) at 2025-07-13 17:49:51 +0000