aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--README.md2
-rw-r--r--cmd/vartan/compile.go16
-rw-r--r--cmd/vartan/show.go6
-rw-r--r--driver/conflict_test.go2
-rw-r--r--driver/lac_test.go2
-rw-r--r--driver/parser.go9
-rw-r--r--driver/parser_test.go117
-rw-r--r--driver/semantic_action_test.go2
-rw-r--r--driver/spec.go4
-rw-r--r--driver/syntax_error_test.go2
-rw-r--r--driver/template.go5
-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
-rw-r--r--spec/description.go1
-rw-r--r--spec/grammar.go1
20 files changed, 67 insertions, 1182 deletions
diff --git a/README.md b/README.md
index 644bbd9..900fa28 100644
--- a/README.md
+++ b/README.md
@@ -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.
[![Test](https://github.com/nihei9/vartan/actions/workflows/test.yml/badge.svg?branch=main)](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"`
generated by cgit v1.2.3 (git 2.49.0) at 2025-07-12 23:00:04 +0000