diff options
author | Ryo Nihei <nihei.dev@gmail.com> | 2022-11-06 17:30:48 +0900 |
---|---|---|
committer | Ryo Nihei <nihei.dev@gmail.com> | 2022-11-06 17:31:52 +0900 |
commit | a84350cc4a213b74fdd592e8b9eeeb6079d0f5ff (patch) | |
tree | e3f6191c06863cddf642c8e769ba732d13866d89 | |
parent | Move the skip table from lexer-related data to parser-related data (diff) | |
download | cotia-a84350cc4a213b74fdd592e8b9eeeb6079d0f5ff.tar.gz cotia-a84350cc4a213b74fdd592e8b9eeeb6079d0f5ff.tar.xz |
Split SymbolTable's APIs into reader/writer
-rw-r--r-- | grammar/first_test.go | 2 | ||||
-rw-r--r-- | grammar/grammar.go | 179 | ||||
-rw-r--r-- | grammar/parsing_table.go | 2 | ||||
-rw-r--r-- | grammar/symbol.go | 88 | ||||
-rw-r--r-- | grammar/symbol_test.go | 30 | ||||
-rw-r--r-- | grammar/test_helper_test.go | 2 |
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() |