diff options
-rw-r--r-- | README.md | 2 | ||||
-rw-r--r-- | cmd/vartan/compile.go | 16 | ||||
-rw-r--r-- | cmd/vartan/show.go | 6 | ||||
-rw-r--r-- | driver/conflict_test.go | 2 | ||||
-rw-r--r-- | driver/lac_test.go | 2 | ||||
-rw-r--r-- | driver/parser.go | 9 | ||||
-rw-r--r-- | driver/parser_test.go | 117 | ||||
-rw-r--r-- | driver/semantic_action_test.go | 2 | ||||
-rw-r--r-- | driver/spec.go | 4 | ||||
-rw-r--r-- | driver/syntax_error_test.go | 2 | ||||
-rw-r--r-- | driver/template.go | 5 | ||||
-rw-r--r-- | grammar/follow.go | 145 | ||||
-rw-r--r-- | grammar/follow_test.go | 204 | ||||
-rw-r--r-- | grammar/grammar.go | 49 | ||||
-rw-r--r-- | grammar/parsing_table.go | 2 | ||||
-rw-r--r-- | grammar/parsing_table_test.go | 386 | ||||
-rw-r--r-- | grammar/slr1.go | 61 | ||||
-rw-r--r-- | grammar/slr1_test.go | 233 | ||||
-rw-r--r-- | spec/description.go | 1 | ||||
-rw-r--r-- | spec/grammar.go | 1 |
20 files changed, 67 insertions, 1182 deletions
@@ -1,6 +1,6 @@ # vartan -vartan is a parser generator for golang and supports LALR(1) and SLR(1). vartan also provides a command to perform syntax analysis to allow easy debugging of your grammar. +vartan is an LALR(1) parser generator for golang. vartan also provides a command to perform syntax analysis to allow easy debugging of your grammar. [](https://github.com/nihei9/vartan/actions/workflows/test.yml) diff --git a/cmd/vartan/compile.go b/cmd/vartan/compile.go index e2b5f56..7e594a8 100644 --- a/cmd/vartan/compile.go +++ b/cmd/vartan/compile.go @@ -16,7 +16,6 @@ import ( var compileFlags = struct { output *string - class *string }{} func init() { @@ -28,7 +27,6 @@ func init() { RunE: runCompile, } compileFlags.output = cmd.Flags().StringP("output", "o", "", "output file path (default stdout)") - compileFlags.class = cmd.Flags().StringP("class", "", "lalr", "LALR or SLR") rootCmd.AddCommand(cmd) } @@ -92,19 +90,7 @@ func runCompile(cmd *cobra.Command, args []string) (retErr error) { reportFileName = fmt.Sprintf("%v-report.json", strings.TrimSuffix(grmFileName, ".vartan")) } - opts := []grammar.CompileOption{ - grammar.EnableReporting(reportFileName), - } - switch strings.ToLower(*compileFlags.class) { - case "slr": - opts = append(opts, grammar.SpecifyClass(grammar.ClassSLR)) - case "lalr": - opts = append(opts, grammar.SpecifyClass(grammar.ClassLALR)) - default: - return fmt.Errorf("invalid class: %v", *compileFlags.class) - } - - cgram, err := grammar.Compile(gram, opts...) + cgram, err := grammar.Compile(gram, grammar.EnableReporting(reportFileName)) if err != nil { return err } diff --git a/cmd/vartan/show.go b/cmd/vartan/show.go index 7b112d9..7c2482c 100644 --- a/cmd/vartan/show.go +++ b/cmd/vartan/show.go @@ -60,11 +60,7 @@ func readReport(path string) (*spec.Report, error) { return report, nil } -const reportTemplate = `# Class - -{{ .Class }} - -# Conflicts +const reportTemplate = `# Conflicts {{ printConflictSummary . }} diff --git a/driver/conflict_test.go b/driver/conflict_test.go index e767e5b..1a1199b 100644 --- a/driver/conflict_test.go +++ b/driver/conflict_test.go @@ -499,7 +499,7 @@ assign: '='; t.Fatal(err) } - cg, err := grammar.Compile(g, grammar.SpecifyClass(grammar.ClassSLR)) + cg, err := grammar.Compile(g) if err != nil { t.Fatal(err) } diff --git a/driver/lac_test.go b/driver/lac_test.go index 3cee765..e612b13 100644 --- a/driver/lac_test.go +++ b/driver/lac_test.go @@ -56,7 +56,7 @@ d: 'd'; t.Fatal(err) } - gram, err := grammar.Compile(g, grammar.SpecifyClass(grammar.ClassLALR)) + gram, err := grammar.Compile(g) if err != nil { t.Fatal(err) } diff --git a/driver/parser.go b/driver/parser.go index dbebec3..14e9752 100644 --- a/driver/parser.go +++ b/driver/parser.go @@ -5,9 +5,6 @@ import ( ) type Grammar interface { - // Class returns a class of grammar. - Class() string - // InitialState returns the initial state of a parser. InitialState() int @@ -88,7 +85,7 @@ type SyntaxError struct { type ParserOption func(p *Parser) error -// DisableLAC disables LAC (lookahead correction). When the grammar has the LALR class, LAC is enabled by default. +// DisableLAC disables LAC (lookahead correction). LAC is enabled by default. func DisableLAC() ParserOption { return func(p *Parser) error { p.disableLAC = true @@ -121,10 +118,6 @@ func NewParser(toks TokenStream, gram Grammar, opts ...ParserOption) (*Parser, e stateStack: &stateStack{}, } - if p.gram.Class() != "lalr" { - p.disableLAC = true - } - for _, opt := range opts { err := opt(p) if err != nil { diff --git a/driver/parser_test.go b/driver/parser_test.go index dc1c141..65958bc 100644 --- a/driver/parser_test.go +++ b/driver/parser_test.go @@ -725,70 +725,63 @@ bar: 'bar'; }, } - classes := []grammar.Class{ - grammar.ClassSLR, - grammar.ClassLALR, - } - for i, tt := range tests { - for _, class := range classes { - t.Run(fmt.Sprintf("#%v", i), func(t *testing.T) { - ast, err := spec.Parse(strings.NewReader(tt.specSrc)) - if err != nil { - t.Fatal(err) - } - - b := grammar.GrammarBuilder{ - AST: ast, - } - g, err := b.Build() - if err != nil { - t.Fatal(err) - } - - cg, err := grammar.Compile(g, grammar.SpecifyClass(class)) - if err != nil { - t.Fatal(err) - } - - toks, err := NewTokenStream(cg, strings.NewReader(tt.src)) - if err != nil { - t.Fatal(err) - } - - gram := NewGrammar(cg) - tb := NewDefaultSyntaxTreeBuilder() - var opt []ParserOption - switch { - case tt.ast != nil: - opt = append(opt, SemanticAction(NewASTActionSet(gram, tb))) - case tt.cst != nil: - opt = append(opt, SemanticAction(NewCSTActionSet(gram, tb))) - } - p, err := NewParser(toks, gram, opt...) - if err != nil { - t.Fatal(err) - } - - err = p.Parse() - if err != nil { - t.Fatal(err) - } - - if !tt.synErr && len(p.SyntaxErrors()) > 0 { - for _, synErr := range p.SyntaxErrors() { - t.Fatalf("unexpected syntax errors occurred: %v", synErr) - } - } - - switch { - case tt.ast != nil: - testTree(t, tb.Tree(), tt.ast) - case tt.cst != nil: - testTree(t, tb.Tree(), tt.cst) + t.Run(fmt.Sprintf("#%v", i), func(t *testing.T) { + ast, err := spec.Parse(strings.NewReader(tt.specSrc)) + if err != nil { + t.Fatal(err) + } + + b := grammar.GrammarBuilder{ + AST: ast, + } + g, err := b.Build() + if err != nil { + t.Fatal(err) + } + + cg, err := grammar.Compile(g) + if err != nil { + t.Fatal(err) + } + + toks, err := NewTokenStream(cg, strings.NewReader(tt.src)) + if err != nil { + t.Fatal(err) + } + + gram := NewGrammar(cg) + tb := NewDefaultSyntaxTreeBuilder() + var opt []ParserOption + switch { + case tt.ast != nil: + opt = append(opt, SemanticAction(NewASTActionSet(gram, tb))) + case tt.cst != nil: + opt = append(opt, SemanticAction(NewCSTActionSet(gram, tb))) + } + p, err := NewParser(toks, gram, opt...) + if err != nil { + t.Fatal(err) + } + + err = p.Parse() + if err != nil { + t.Fatal(err) + } + + if !tt.synErr && len(p.SyntaxErrors()) > 0 { + for _, synErr := range p.SyntaxErrors() { + t.Fatalf("unexpected syntax errors occurred: %v", synErr) } - }) - } + } + + switch { + case tt.ast != nil: + testTree(t, tb.Tree(), tt.ast) + case tt.cst != nil: + testTree(t, tb.Tree(), tt.cst) + } + }) } } diff --git a/driver/semantic_action_test.go b/driver/semantic_action_test.go index ad58780..d0e769e 100644 --- a/driver/semantic_action_test.go +++ b/driver/semantic_action_test.go @@ -194,7 +194,7 @@ char t.Fatal(err) } - gram, err := grammar.Compile(g, grammar.SpecifyClass(grammar.ClassLALR)) + gram, err := grammar.Compile(g) if err != nil { t.Fatal(err) } diff --git a/driver/spec.go b/driver/spec.go index 6127e73..195cb8c 100644 --- a/driver/spec.go +++ b/driver/spec.go @@ -12,10 +12,6 @@ func NewGrammar(g *spec.CompiledGrammar) *grammarImpl { } } -func (g *grammarImpl) Class() string { - return g.g.ParsingTable.Class -} - func (g *grammarImpl) InitialState() int { return g.g.ParsingTable.InitialState } diff --git a/driver/syntax_error_test.go b/driver/syntax_error_test.go index 93cf637..c49d804 100644 --- a/driver/syntax_error_test.go +++ b/driver/syntax_error_test.go @@ -126,7 +126,7 @@ c t.Fatal(err) } - gram, err := grammar.Compile(g, grammar.SpecifyClass(grammar.ClassLALR)) + gram, err := grammar.Compile(g) if err != nil { t.Fatal(err) } diff --git a/driver/template.go b/driver/template.go index aa1fbd3..459b6e0 100644 --- a/driver/template.go +++ b/driver/template.go @@ -49,7 +49,6 @@ func GenParser(cgram *spec.CompiledGrammar, pkgName string) ([]byte, error) { var b strings.Builder err = t.Execute(&b, map[string]interface{}{ - "class": cgram.ParsingTable.Class, "initialState": cgram.ParsingTable.InitialState, "startProduction": cgram.ParsingTable.StartProduction, "terminalCount": cgram.ParsingTable.TerminalCount, @@ -167,10 +166,6 @@ func NewGrammar() *grammarImpl { } } -func (g *grammarImpl) Class() string { - return "{{ .class }}" -} - func (g *grammarImpl) InitialState() int { return {{ .initialState }} } 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) -} diff --git a/spec/description.go b/spec/description.go index 4102455..552840a 100644 --- a/spec/description.go +++ b/spec/description.go @@ -66,7 +66,6 @@ type State struct { } type Report struct { - Class string `json:"class"` Terminals []*Terminal `json:"terminals"` NonTerminals []*NonTerminal `json:"non_terminals"` Productions []*Production `json:"productions"` diff --git a/spec/grammar.go b/spec/grammar.go index bf14d86..e3c87d1 100644 --- a/spec/grammar.go +++ b/spec/grammar.go @@ -23,7 +23,6 @@ type Maleeni struct { } type ParsingTable struct { - Class string `json:"class"` Action []int `json:"action"` GoTo []int `json:"goto"` StateCount int `json:"state_count"` |