aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorRyo Nihei <nihei.dev@gmail.com>2022-11-06 17:30:48 +0900
committerRyo Nihei <nihei.dev@gmail.com>2022-11-06 17:31:52 +0900
commita84350cc4a213b74fdd592e8b9eeeb6079d0f5ff (patch)
treee3f6191c06863cddf642c8e769ba732d13866d89
parentMove the skip table from lexer-related data to parser-related data (diff)
downloadcotia-a84350cc4a213b74fdd592e8b9eeeb6079d0f5ff.tar.gz
cotia-a84350cc4a213b74fdd592e8b9eeeb6079d0f5ff.tar.xz
Split SymbolTable's APIs into reader/writer
-rw-r--r--grammar/first_test.go2
-rw-r--r--grammar/grammar.go179
-rw-r--r--grammar/parsing_table.go2
-rw-r--r--grammar/symbol.go88
-rw-r--r--grammar/symbol_test.go30
-rw-r--r--grammar/test_helper_test.go2
6 files changed, 171 insertions, 132 deletions
diff --git a/grammar/first_test.go b/grammar/first_test.go
index 5f128cc..21ee4df 100644
--- a/grammar/first_test.go
+++ b/grammar/first_test.go
@@ -183,7 +183,7 @@ func genActualFirst(t *testing.T, src string) (*firstSet, *Grammar) {
return fst, gram
}
-func genExpectedFirstEntry(t *testing.T, symbols []string, empty bool, symTab *symbolTable) *firstEntry {
+func genExpectedFirstEntry(t *testing.T, symbols []string, empty bool, symTab *symbolTableReader) *firstEntry {
t.Helper()
entry := newFirstEntry()
diff --git a/grammar/grammar.go b/grammar/grammar.go
index cd0dfa9..50272e0 100644
--- a/grammar/grammar.go
+++ b/grammar/grammar.go
@@ -87,7 +87,7 @@ type Grammar struct {
productionSet *productionSet
augmentedStartSymbol symbol
errorSymbol symbol
- symbolTable *symbolTable
+ symbolTable *symbolTableReader
astActions map[productionID][]*astActionEntry
precAndAssoc *precAndAssoc
@@ -138,12 +138,17 @@ func (b *GrammarBuilder) Build() (*Grammar, error) {
return nil, b.errs
}
- symTabAndLexSpec, err := b.genSymbolTableAndLexSpec(b.AST)
+ symTab, ss, err := b.genSymbolTable(b.AST)
if err != nil {
return nil, err
}
- prodsAndActs, err := b.genProductionsAndActions(b.AST, symTabAndLexSpec)
+ lexSpec, err := b.genLexSpec(b.AST)
+ if err != nil {
+ return nil, err
+ }
+
+ prodsAndActs, err := b.genProductionsAndActions(b.AST, symTab.reader(), ss.errSym, ss.augStartSym, ss.startSym)
if err != nil {
return nil, err
}
@@ -151,7 +156,7 @@ func (b *GrammarBuilder) Build() (*Grammar, error) {
return nil, b.errs
}
- pa, err := b.genPrecAndAssoc(symTabAndLexSpec.symTab, symTabAndLexSpec.errSym, prodsAndActs)
+ pa, err := b.genPrecAndAssoc(symTab.reader(), ss.errSym, prodsAndActs)
if err != nil {
return nil, err
}
@@ -166,7 +171,7 @@ func (b *GrammarBuilder) Build() (*Grammar, error) {
// When a terminal symbol that cannot be reached from the start symbol has the skip directive,
// the compiler treats its terminal as a used symbol, not unused.
- for _, sym := range symTabAndLexSpec.skip {
+ for _, sym := range lexSpec.skip {
s := sym.String()
if _, ok := syms.unusedTerminals[s]; !ok {
prod := syms.usedTerminals[s]
@@ -204,16 +209,16 @@ func (b *GrammarBuilder) Build() (*Grammar, error) {
return nil, b.errs
}
- symTabAndLexSpec.lexSpec.Name = specName
+ lexSpec.lexSpec.Name = specName
return &Grammar{
name: specName,
- lexSpec: symTabAndLexSpec.lexSpec,
- skipLexKinds: symTabAndLexSpec.skip,
+ lexSpec: lexSpec.lexSpec,
+ skipLexKinds: lexSpec.skip,
productionSet: prodsAndActs.prods,
augmentedStartSymbol: prodsAndActs.augStartSym,
- errorSymbol: symTabAndLexSpec.errSym,
- symbolTable: symTabAndLexSpec.symTab,
+ errorSymbol: ss.errSym,
+ symbolTable: symTab.reader(),
astActions: prodsAndActs.astActs,
recoverProductions: prodsAndActs.recoverProds,
precAndAssoc: pa,
@@ -380,30 +385,29 @@ func collectUserDefinedIDsFromDirective(dir *spec.DirectiveNode) []string {
return ids
}
-type symbolTableAndLexSpec struct {
- symTab *symbolTable
- lexSpec *mlspec.LexSpec
- errSym symbol
- skip []mlspec.LexKindName
+type symbols struct {
+ errSym symbol
+ augStartSym symbol
+ startSym symbol
}
-func (b *GrammarBuilder) genSymbolTableAndLexSpec(root *spec.RootNode) (*symbolTableAndLexSpec, error) {
+func (b *GrammarBuilder) genSymbolTable(root *spec.RootNode) (*symbolTable, *symbols, error) {
symTab := newSymbolTable()
- entries := []*mlspec.LexEntry{}
+ w := symTab.writer()
+ r := symTab.reader()
// We need to register the reserved symbol before registering others.
var errSym symbol
{
- sym, err := symTab.registerTerminalSymbol(reservedSymbolNameError)
+ sym, err := w.registerTerminalSymbol(reservedSymbolNameError)
if err != nil {
- return nil, err
+ return nil, nil, err
}
errSym = sym
}
- skipKinds := []mlspec.LexKindName{}
for _, prod := range root.LexProductions {
- if sym, exist := symTab.toSymbol(prod.LHS); exist {
+ if sym, exist := r.toSymbol(prod.LHS); exist {
if sym == errSym {
b.errs = append(b.errs, &verr.SpecError{
Cause: semErrErrSymIsReserved,
@@ -422,11 +426,77 @@ func (b *GrammarBuilder) genSymbolTableAndLexSpec(root *spec.RootNode) (*symbolT
continue
}
- _, err := symTab.registerTerminalSymbol(prod.LHS)
+ _, err := w.registerTerminalSymbol(prod.LHS)
if err != nil {
- return nil, err
+ return nil, nil, err
+ }
+ }
+
+ startProd := root.Productions[0]
+ augStartText := fmt.Sprintf("%s'", startProd.LHS)
+ var err error
+ augStartSym, err := w.registerStartSymbol(augStartText)
+ if err != nil {
+ return nil, nil, err
+ }
+ if augStartSym == errSym {
+ b.errs = append(b.errs, &verr.SpecError{
+ Cause: semErrErrSymIsReserved,
+ Row: startProd.Pos.Row,
+ Col: startProd.Pos.Col,
+ })
+ }
+
+ startSym, err := w.registerNonTerminalSymbol(startProd.LHS)
+ if err != nil {
+ return nil, nil, err
+ }
+ if startSym == errSym {
+ b.errs = append(b.errs, &verr.SpecError{
+ Cause: semErrErrSymIsReserved,
+ Row: startProd.Pos.Row,
+ Col: startProd.Pos.Col,
+ })
+ }
+
+ for _, prod := range root.Productions {
+ sym, err := w.registerNonTerminalSymbol(prod.LHS)
+ if err != nil {
+ return nil, nil, err
+ }
+ if sym.isTerminal() {
+ b.errs = append(b.errs, &verr.SpecError{
+ Cause: semErrDuplicateName,
+ Detail: prod.LHS,
+ Row: prod.Pos.Row,
+ Col: prod.Pos.Col,
+ })
+ }
+ if sym == errSym {
+ b.errs = append(b.errs, &verr.SpecError{
+ Cause: semErrErrSymIsReserved,
+ Row: prod.Pos.Row,
+ Col: prod.Pos.Col,
+ })
}
+ }
+
+ return symTab, &symbols{
+ errSym: errSym,
+ augStartSym: augStartSym,
+ startSym: startSym,
+ }, nil
+}
+
+type lexSpec struct {
+ lexSpec *mlspec.LexSpec
+ skip []mlspec.LexKindName
+}
+func (b *GrammarBuilder) genLexSpec(root *spec.RootNode) (*lexSpec, error) {
+ entries := []*mlspec.LexEntry{}
+ skipKinds := []mlspec.LexKindName{}
+ for _, prod := range root.LexProductions {
entry, skip, specErr, err := genLexEntry(prod)
if err != nil {
return nil, err
@@ -461,13 +531,11 @@ func (b *GrammarBuilder) genSymbolTableAndLexSpec(root *spec.RootNode) (*symbolT
})
}
- return &symbolTableAndLexSpec{
- symTab: symTab,
+ return &lexSpec{
lexSpec: &mlspec.LexSpec{
Entries: entries,
},
- errSym: errSym,
- skip: skipKinds,
+ skip: skipKinds,
}, nil
}
@@ -587,10 +655,7 @@ type productionsAndActions struct {
recoverProds map[productionID]struct{}
}
-func (b *GrammarBuilder) genProductionsAndActions(root *spec.RootNode, symTabAndLexSpec *symbolTableAndLexSpec) (*productionsAndActions, error) {
- symTab := symTabAndLexSpec.symTab
- errSym := symTabAndLexSpec.errSym
-
+func (b *GrammarBuilder) genProductionsAndActions(root *spec.RootNode, symTab *symbolTableReader, errSym symbol, augStartSym symbol, startSym symbol) (*productionsAndActions, error) {
if len(root.Productions) == 0 {
b.errs = append(b.errs, &verr.SpecError{
Cause: semErrNoProduction,
@@ -599,40 +664,12 @@ func (b *GrammarBuilder) genProductionsAndActions(root *spec.RootNode, symTabAnd
}
prods := newProductionSet()
- var augStartSym symbol
astActs := map[productionID][]*astActionEntry{}
prodPrecsTerm := map[productionID]symbol{}
prodPrecsOrdSym := map[productionID]string{}
prodPrecPoss := map[productionID]*spec.Position{}
recoverProds := map[productionID]struct{}{}
- startProd := root.Productions[0]
- augStartText := fmt.Sprintf("%s'", startProd.LHS)
- var err error
- augStartSym, err = symTab.registerStartSymbol(augStartText)
- if err != nil {
- return nil, err
- }
- if augStartSym == errSym {
- b.errs = append(b.errs, &verr.SpecError{
- Cause: semErrErrSymIsReserved,
- Row: startProd.Pos.Row,
- Col: startProd.Pos.Col,
- })
- }
-
- startSym, err := symTab.registerNonTerminalSymbol(startProd.LHS)
- if err != nil {
- return nil, err
- }
- if startSym == errSym {
- b.errs = append(b.errs, &verr.SpecError{
- Cause: semErrErrSymIsReserved,
- Row: startProd.Pos.Row,
- Col: startProd.Pos.Col,
- })
- }
-
p, err := newProduction(augStartSym, []symbol{
startSym,
})
@@ -643,28 +680,6 @@ func (b *GrammarBuilder) genProductionsAndActions(root *spec.RootNode, symTabAnd
prods.append(p)
for _, prod := range root.Productions {
- sym, err := symTab.registerNonTerminalSymbol(prod.LHS)
- if err != nil {
- return nil, err
- }
- if sym.isTerminal() {
- b.errs = append(b.errs, &verr.SpecError{
- Cause: semErrDuplicateName,
- Detail: prod.LHS,
- Row: prod.Pos.Row,
- Col: prod.Pos.Col,
- })
- }
- if sym == errSym {
- b.errs = append(b.errs, &verr.SpecError{
- Cause: semErrErrSymIsReserved,
- Row: prod.Pos.Row,
- Col: prod.Pos.Col,
- })
- }
- }
-
- for _, prod := range root.Productions {
lhsSym, ok := symTab.toSymbol(prod.LHS)
if !ok {
// All symbols are assumed to be pre-detected, so it's a bug if we cannot find them here.
@@ -965,7 +980,7 @@ func (b *GrammarBuilder) genProductionsAndActions(root *spec.RootNode, symTabAnd
}, nil
}
-func (b *GrammarBuilder) genPrecAndAssoc(symTab *symbolTable, errSym symbol, prodsAndActs *productionsAndActions) (*precAndAssoc, error) {
+func (b *GrammarBuilder) genPrecAndAssoc(symTab *symbolTableReader, errSym symbol, prodsAndActs *productionsAndActions) (*precAndAssoc, error) {
termPrec := map[symbolNum]int{}
termAssoc := map[symbolNum]assocType{}
ordSymPrec := map[string]int{}
diff --git a/grammar/parsing_table.go b/grammar/parsing_table.go
index 1eaf63d..93033a3 100644
--- a/grammar/parsing_table.go
+++ b/grammar/parsing_table.go
@@ -151,7 +151,7 @@ type lrTableBuilder struct {
prods *productionSet
termCount int
nonTermCount int
- symTab *symbolTable
+ symTab *symbolTableReader
precAndAssoc *precAndAssoc
conflicts []conflict
diff --git a/grammar/symbol.go b/grammar/symbol.go
index 6e357bb..9eba032 100644
--- a/grammar/symbol.go
+++ b/grammar/symbol.go
@@ -162,6 +162,14 @@ type symbolTable struct {
termNum symbolNum
}
+type symbolTableWriter struct {
+ *symbolTable
+}
+
+type symbolTableReader struct {
+ *symbolTable
+}
+
func newSymbolTable() *symbolTable {
return &symbolTable{
text2Sym: map[string]symbol{
@@ -183,58 +191,70 @@ func newSymbolTable() *symbolTable {
}
}
-func (t *symbolTable) registerStartSymbol(text string) (symbol, error) {
- t.text2Sym[text] = symbolStart
- t.sym2Text[symbolStart] = text
- t.nonTermTexts[symbolStart.num().Int()] = text
+func (t *symbolTable) writer() *symbolTableWriter {
+ return &symbolTableWriter{
+ symbolTable: t,
+ }
+}
+
+func (t *symbolTable) reader() *symbolTableReader {
+ return &symbolTableReader{
+ symbolTable: t,
+ }
+}
+
+func (w *symbolTableWriter) registerStartSymbol(text string) (symbol, error) {
+ w.text2Sym[text] = symbolStart
+ w.sym2Text[symbolStart] = text
+ w.nonTermTexts[symbolStart.num().Int()] = text
return symbolStart, nil
}
-func (t *symbolTable) registerNonTerminalSymbol(text string) (symbol, error) {
- if sym, ok := t.text2Sym[text]; ok {
+func (w *symbolTableWriter) registerNonTerminalSymbol(text string) (symbol, error) {
+ if sym, ok := w.text2Sym[text]; ok {
return sym, nil
}
- sym, err := newSymbol(symbolKindNonTerminal, false, t.nonTermNum)
+ sym, err := newSymbol(symbolKindNonTerminal, false, w.nonTermNum)
if err != nil {
return symbolNil, err
}
- t.nonTermNum++
- t.text2Sym[text] = sym
- t.sym2Text[sym] = text
- t.nonTermTexts = append(t.nonTermTexts, text)
+ w.nonTermNum++
+ w.text2Sym[text] = sym
+ w.sym2Text[sym] = text
+ w.nonTermTexts = append(w.nonTermTexts, text)
return sym, nil
}
-func (t *symbolTable) registerTerminalSymbol(text string) (symbol, error) {
- if sym, ok := t.text2Sym[text]; ok {
+func (w *symbolTableWriter) registerTerminalSymbol(text string) (symbol, error) {
+ if sym, ok := w.text2Sym[text]; ok {
return sym, nil
}
- sym, err := newSymbol(symbolKindTerminal, false, t.termNum)
+ sym, err := newSymbol(symbolKindTerminal, false, w.termNum)
if err != nil {
return symbolNil, err
}
- t.termNum++
- t.text2Sym[text] = sym
- t.sym2Text[sym] = text
- t.termTexts = append(t.termTexts, text)
+ w.termNum++
+ w.text2Sym[text] = sym
+ w.sym2Text[sym] = text
+ w.termTexts = append(w.termTexts, text)
return sym, nil
}
-func (t *symbolTable) toSymbol(text string) (symbol, bool) {
- if sym, ok := t.text2Sym[text]; ok {
+func (r *symbolTableReader) toSymbol(text string) (symbol, bool) {
+ if sym, ok := r.text2Sym[text]; ok {
return sym, true
}
return symbolNil, false
}
-func (t *symbolTable) toText(sym symbol) (string, bool) {
- text, ok := t.sym2Text[sym]
+func (r *symbolTableReader) toText(sym symbol) (string, bool) {
+ text, ok := r.sym2Text[sym]
return text, ok
}
-func (t *symbolTable) terminalSymbols() []symbol {
- syms := make([]symbol, 0, t.termNum.Int()-terminalNumMin.Int())
- for sym := range t.sym2Text {
+func (r *symbolTableReader) terminalSymbols() []symbol {
+ syms := make([]symbol, 0, r.termNum.Int()-terminalNumMin.Int())
+ for sym := range r.sym2Text {
if !sym.isTerminal() || sym.isNil() {
continue
}
@@ -246,16 +266,16 @@ func (t *symbolTable) terminalSymbols() []symbol {
return syms
}
-func (t *symbolTable) terminalTexts() ([]string, error) {
- if t.termNum == terminalNumMin {
+func (r *symbolTableReader) terminalTexts() ([]string, error) {
+ if r.termNum == terminalNumMin {
return nil, fmt.Errorf("symbol table has no terminals")
}
- return t.termTexts, nil
+ return r.termTexts, nil
}
-func (t *symbolTable) nonTerminalSymbols() []symbol {
- syms := make([]symbol, 0, t.nonTermNum.Int()-nonTerminalNumMin.Int())
- for sym := range t.sym2Text {
+func (r *symbolTableReader) nonTerminalSymbols() []symbol {
+ syms := make([]symbol, 0, r.nonTermNum.Int()-nonTerminalNumMin.Int())
+ for sym := range r.sym2Text {
if !sym.isNonTerminal() || sym.isNil() {
continue
}
@@ -267,9 +287,9 @@ func (t *symbolTable) nonTerminalSymbols() []symbol {
return syms
}
-func (t *symbolTable) nonTerminalTexts() ([]string, error) {
- if t.nonTermNum == nonTerminalNumMin || t.nonTermTexts[symbolStart.num().Int()] == "" {
+func (r *symbolTableReader) nonTerminalTexts() ([]string, error) {
+ if r.nonTermNum == nonTerminalNumMin || r.nonTermTexts[symbolStart.num().Int()] == "" {
return nil, fmt.Errorf("symbol table has no terminals or no start symbol")
}
- return t.nonTermTexts, nil
+ return r.nonTermTexts, nil
}
diff --git a/grammar/symbol_test.go b/grammar/symbol_test.go
index 747def9..b9bcbdf 100644
--- a/grammar/symbol_test.go
+++ b/grammar/symbol_test.go
@@ -4,15 +4,16 @@ import "testing"
func TestSymbol(t *testing.T) {
tab := newSymbolTable()
- _, _ = tab.registerStartSymbol("expr'")
- _, _ = tab.registerNonTerminalSymbol("expr")
- _, _ = tab.registerNonTerminalSymbol("term")
- _, _ = tab.registerNonTerminalSymbol("factor")
- _, _ = tab.registerTerminalSymbol("id")
- _, _ = tab.registerTerminalSymbol("add")
- _, _ = tab.registerTerminalSymbol("mul")
- _, _ = tab.registerTerminalSymbol("l_paren")
- _, _ = tab.registerTerminalSymbol("r_paren")
+ w := tab.writer()
+ _, _ = w.registerStartSymbol("expr'")
+ _, _ = w.registerNonTerminalSymbol("expr")
+ _, _ = w.registerNonTerminalSymbol("term")
+ _, _ = w.registerNonTerminalSymbol("factor")
+ _, _ = w.registerTerminalSymbol("id")
+ _, _ = w.registerTerminalSymbol("add")
+ _, _ = w.registerTerminalSymbol("mul")
+ _, _ = w.registerTerminalSymbol("l_paren")
+ _, _ = w.registerTerminalSymbol("r_paren")
nonTermTexts := []string{
"", // Nil
@@ -80,12 +81,13 @@ func TestSymbol(t *testing.T) {
}
for _, tt := range tests {
t.Run(tt.text, func(t *testing.T) {
- sym, ok := tab.toSymbol(tt.text)
+ r := tab.reader()
+ sym, ok := r.toSymbol(tt.text)
if !ok {
t.Fatalf("symbol was not found")
}
testSymbolProperty(t, sym, tt.isNil, tt.isStart, tt.isEOF, tt.isNonTerminal, tt.isTerminal)
- text, ok := tab.toText(sym)
+ text, ok := r.toText(sym)
if !ok {
t.Fatalf("text was not found")
}
@@ -104,7 +106,8 @@ func TestSymbol(t *testing.T) {
})
t.Run("texts of non-terminals", func(t *testing.T) {
- ts, err := tab.nonTerminalTexts()
+ r := tab.reader()
+ ts, err := r.nonTerminalTexts()
if err != nil {
t.Fatal(err)
}
@@ -119,7 +122,8 @@ func TestSymbol(t *testing.T) {
})
t.Run("texts of terminals", func(t *testing.T) {
- ts, err := tab.terminalTexts()
+ r := tab.reader()
+ ts, err := r.terminalTexts()
if err != nil {
t.Fatal(err)
}
diff --git a/grammar/test_helper_test.go b/grammar/test_helper_test.go
index cf9da2b..1dcdede 100644
--- a/grammar/test_helper_test.go
+++ b/grammar/test_helper_test.go
@@ -4,7 +4,7 @@ import "testing"
type testSymbolGenerator func(text string) symbol
-func newTestSymbolGenerator(t *testing.T, symTab *symbolTable) testSymbolGenerator {
+func newTestSymbolGenerator(t *testing.T, symTab *symbolTableReader) testSymbolGenerator {
return func(text string) symbol {
t.Helper()