aboutsummaryrefslogtreecommitdiff
path: root/grammar/parsing_table_builder.go
diff options
context:
space:
mode:
Diffstat (limited to 'grammar/parsing_table_builder.go')
-rw-r--r--grammar/parsing_table_builder.go201
1 files changed, 46 insertions, 155 deletions
diff --git a/grammar/parsing_table_builder.go b/grammar/parsing_table_builder.go
index e209c94..82b0d34 100644
--- a/grammar/parsing_table_builder.go
+++ b/grammar/parsing_table_builder.go
@@ -165,8 +165,8 @@ func (t *ParsingTable) writeGoTo(state stateNum, sym symbol, nextState stateNum)
t.goToTable[pos] = newGoToEntry(nextState)
}
-type lalrTableBuilder struct {
- automaton *lalr1Automaton
+type lrTableBuilder struct {
+ automaton *lr0Automaton
prods *productionSet
termCount int
nonTermCount int
@@ -176,7 +176,7 @@ type lalrTableBuilder struct {
conflicts []conflict
}
-func (b *lalrTableBuilder) build() (*ParsingTable, error) {
+func (b *lrTableBuilder) build() (*ParsingTable, error) {
var ptab *ParsingTable
{
initialState := b.automaton.states[b.automaton.initialState]
@@ -262,104 +262,9 @@ func (b *lalrTableBuilder) build() (*ParsingTable, error) {
return ptab, nil
}
-type slrTableBuilder struct {
- automaton *lr0Automaton
- prods *productionSet
- follow *followSet
- termCount int
- nonTermCount int
- symTab *symbolTable
- sym2AnonPat map[symbol]string
-
- conflicts []conflict
-}
-
-func (b *slrTableBuilder) build() (*ParsingTable, error) {
- var ptab *ParsingTable
- {
- initialState := b.automaton.states[b.automaton.initialState]
- ptab = &ParsingTable{
- actionTable: make([]actionEntry, len(b.automaton.states)*b.termCount),
- goToTable: make([]goToEntry, len(b.automaton.states)*b.nonTermCount),
- stateCount: len(b.automaton.states),
- terminalCount: b.termCount,
- nonTerminalCount: b.nonTermCount,
- expectedTerminals: make([][]int, len(b.automaton.states)),
- InitialState: initialState.num,
- }
- }
-
- var conflicts []conflict
- for _, state := range b.automaton.states {
- var eTerms []int
-
- for sym, kID := range state.next {
- nextState := b.automaton.states[kID]
- if sym.isTerminal() {
- eTerms = append(eTerms, sym.num().Int())
-
- c := ptab.writeShiftAction(state.num, sym, nextState.num)
- if c != nil {
- conflicts = append(conflicts, c)
- continue
- }
- } else {
- ptab.writeGoTo(state.num, sym, nextState.num)
- }
- }
-
- for prodID := range state.reducible {
- prod, _ := b.prods.findByID(prodID)
- flw, err := b.follow.find(prod.lhs)
- if err != nil {
- return nil, err
- }
- for sym := range flw.symbols {
- eTerms = append(eTerms, sym.num().Int())
-
- c := ptab.writeReduceAction(state.num, sym, prod.num)
- if c != nil {
- conflicts = append(conflicts, c)
- continue
- }
- }
- if flw.eof {
- eTerms = append(eTerms, symbolEOF.num().Int())
-
- c := ptab.writeReduceAction(state.num, symbolEOF, prod.num)
- if c != nil {
- conflicts = append(conflicts, c)
- continue
- }
- }
- }
-
- ptab.expectedTerminals[state.num] = eTerms
- }
-
- b.conflicts = conflicts
-
- if len(conflicts) > 0 {
- return nil, fmt.Errorf("%v conflicts", len(conflicts))
- }
-
- return ptab, nil
-}
-
-type descriptionWriter struct {
- automaton *lr0Automaton
- prods *productionSet
- follow *followSet
- termCount int
- nonTermCount int
- symTab *symbolTable
- sym2AnonPat map[symbol]string
- conflicts []conflict
-}
-
-func (dw *descriptionWriter) write(w io.Writer) {
+func (b *lrTableBuilder) write(w io.Writer) {
conflicts := map[stateNum][]conflict{}
- for _, con := range dw.conflicts {
+ for _, con := range b.conflicts {
switch c := con.(type) {
case *shiftReduceConflict:
conflicts[c.state] = append(conflicts[c.state], c)
@@ -370,15 +275,15 @@ func (dw *descriptionWriter) write(w io.Writer) {
fmt.Fprintf(w, "# Conflicts\n\n")
- if len(dw.conflicts) > 0 {
- fmt.Fprintf(w, "%v conflics:\n\n", len(dw.conflicts))
+ if len(b.conflicts) > 0 {
+ fmt.Fprintf(w, "%v conflics:\n\n", len(b.conflicts))
- for _, conflict := range dw.conflicts {
+ for _, conflict := range b.conflicts {
switch c := conflict.(type) {
case *shiftReduceConflict:
- fmt.Fprintf(w, "%v: shift/reduce conflict (shift %v, reduce %v) on %v\n", c.state, c.nextState, c.prodNum, dw.symbolToText(c.sym))
+ fmt.Fprintf(w, "%v: shift/reduce conflict (shift %v, reduce %v) on %v\n", c.state, c.nextState, c.prodNum, b.symbolToText(c.sym))
case *reduceReduceConflict:
- fmt.Fprintf(w, "%v: reduce/reduce conflict (reduce %v and %v) on %v\n", c.state, c.prodNum1, c.prodNum2, dw.symbolToText(c.sym))
+ fmt.Fprintf(w, "%v: reduce/reduce conflict (reduce %v and %v) on %v\n", c.state, c.prodNum1, c.prodNum2, b.symbolToText(c.sym))
}
}
fmt.Fprintf(w, "\n")
@@ -388,17 +293,17 @@ func (dw *descriptionWriter) write(w io.Writer) {
fmt.Fprintf(w, "# Terminals\n\n")
- termSyms := dw.symTab.terminalSymbols()
+ termSyms := b.symTab.terminalSymbols()
fmt.Fprintf(w, "%v symbols:\n\n", len(termSyms))
for _, sym := range termSyms {
- text, ok := dw.symTab.toText(sym)
+ text, ok := b.symTab.toText(sym)
if !ok {
text = fmt.Sprintf("<symbol not found: %v>", sym)
}
if strings.HasPrefix(text, "_") {
- fmt.Fprintf(w, "%4v %v: \"%v\"\n", sym.num(), text, dw.sym2AnonPat[sym])
+ fmt.Fprintf(w, "%4v %v: \"%v\"\n", sym.num(), text, b.sym2AnonPat[sym])
} else {
fmt.Fprintf(w, "%4v %v\n", sym.num(), text)
}
@@ -408,25 +313,25 @@ func (dw *descriptionWriter) write(w io.Writer) {
fmt.Fprintf(w, "# Productions\n\n")
- fmt.Fprintf(w, "%v productions:\n\n", len(dw.prods.getAllProductions()))
+ fmt.Fprintf(w, "%v productions:\n\n", len(b.prods.getAllProductions()))
- for _, prod := range dw.prods.getAllProductions() {
- fmt.Fprintf(w, "%4v %v\n", prod.num, dw.productionToString(prod, -1))
+ for _, prod := range b.prods.getAllProductions() {
+ fmt.Fprintf(w, "%4v %v\n", prod.num, b.productionToString(prod, -1))
}
fmt.Fprintf(w, "\n# States\n\n")
- fmt.Fprintf(w, "%v states:\n\n", len(dw.automaton.states))
+ fmt.Fprintf(w, "%v states:\n\n", len(b.automaton.states))
- for _, state := range dw.automaton.states {
+ for _, state := range b.automaton.states {
fmt.Fprintf(w, "state %v\n", state.num)
for _, item := range state.items {
- prod, ok := dw.prods.findByID(item.prod)
+ prod, ok := b.prods.findByID(item.prod)
if !ok {
fmt.Fprintf(w, "<production not found>\n")
continue
}
- fmt.Fprintf(w, " %v\n", dw.productionToString(prod, item.dot))
+ fmt.Fprintf(w, " %v\n", b.productionToString(prod, item.dot))
}
fmt.Fprintf(w, "\n")
@@ -437,16 +342,16 @@ func (dw *descriptionWriter) write(w io.Writer) {
var accRec string
{
for sym, kID := range state.next {
- nextState := dw.automaton.states[kID]
+ nextState := b.automaton.states[kID]
if sym.isTerminal() {
- shiftRecs = append(shiftRecs, fmt.Sprintf("shift %4v on %v", nextState.num, dw.symbolToText(sym)))
+ shiftRecs = append(shiftRecs, fmt.Sprintf("shift %4v on %v", nextState.num, b.symbolToText(sym)))
} else {
- gotoRecs = append(gotoRecs, fmt.Sprintf("goto %4v on %v", nextState.num, dw.symbolToText(sym)))
+ gotoRecs = append(gotoRecs, fmt.Sprintf("goto %4v on %v", nextState.num, b.symbolToText(sym)))
}
}
for prodID := range state.reducible {
- prod, ok := dw.prods.findByID(prodID)
+ prod, ok := b.prods.findByID(prodID)
if !ok {
reduceRecs = append(reduceRecs, "<production not found>")
continue
@@ -456,21 +361,17 @@ func (dw *descriptionWriter) write(w io.Writer) {
continue
}
- if dw.follow != nil {
- flw, err := dw.follow.find(prod.lhs)
- if err != nil {
- reduceRecs = append(reduceRecs, fmt.Sprintf("%v", err))
+ var reducibleItem *lrItem
+ for _, item := range state.items {
+ if item.prod != prodID {
continue
}
- for sym := range flw.symbols {
- reduceRecs = append(reduceRecs, fmt.Sprintf("reduce %4v on %v", prod.num, dw.symbolToText(sym)))
- }
- if flw.eof {
- reduceRecs = append(reduceRecs, fmt.Sprintf("reduce %4v on <EOF>", prod.num))
- }
- } else {
- var reducibleItem *lrItem
- for _, item := range state.items {
+
+ reducibleItem = item
+ break
+ }
+ if reducibleItem == nil {
+ for _, item := range state.emptyProdItems {
if item.prod != prodID {
continue
}
@@ -479,23 +380,13 @@ func (dw *descriptionWriter) write(w io.Writer) {
break
}
if reducibleItem == nil {
- for _, item := range state.emptyProdItems {
- if item.prod != prodID {
- continue
- }
-
- reducibleItem = item
- break
- }
- if reducibleItem == nil {
- reduceRecs = append(reduceRecs, "<item not found>")
- continue
- }
- }
- for a := range reducibleItem.lookAhead.symbols {
- reduceRecs = append(reduceRecs, fmt.Sprintf("reduce %4v on %v", prod.num, dw.symbolToText(a)))
+ reduceRecs = append(reduceRecs, "<item not found>")
+ continue
}
}
+ for a := range reducibleItem.lookAhead.symbols {
+ reduceRecs = append(reduceRecs, fmt.Sprintf("reduce %4v on %v", prod.num, b.symbolToText(a)))
+ }
}
}
@@ -523,9 +414,9 @@ func (dw *descriptionWriter) write(w io.Writer) {
for _, con := range cons {
switch c := con.(type) {
case *shiftReduceConflict:
- fmt.Fprintf(w, " shift/reduce conflict (shift %v, reduce %v) on %v\n", c.nextState, c.prodNum, dw.symbolToText(c.sym))
+ fmt.Fprintf(w, " shift/reduce conflict (shift %v, reduce %v) on %v\n", c.nextState, c.prodNum, b.symbolToText(c.sym))
case *reduceReduceConflict:
- fmt.Fprintf(w, " reduce/reduce conflict (reduce %v and %v) on %v\n", c.prodNum1, c.prodNum2, dw.symbolToText(c.sym))
+ fmt.Fprintf(w, " reduce/reduce conflict (reduce %v and %v) on %v\n", c.prodNum1, c.prodNum2, b.symbolToText(c.sym))
}
}
fmt.Fprintf(w, "\n")
@@ -533,14 +424,14 @@ func (dw *descriptionWriter) write(w io.Writer) {
}
}
-func (dw *descriptionWriter) productionToString(prod *production, dot int) string {
+func (b *lrTableBuilder) productionToString(prod *production, dot int) string {
var w strings.Builder
- fmt.Fprintf(&w, "%v →", dw.symbolToText(prod.lhs))
+ fmt.Fprintf(&w, "%v →", b.symbolToText(prod.lhs))
for n, rhs := range prod.rhs {
if n == dot {
fmt.Fprintf(&w, " ・")
}
- fmt.Fprintf(&w, " %v", dw.symbolToText(rhs))
+ fmt.Fprintf(&w, " %v", b.symbolToText(rhs))
}
if dot == len(prod.rhs) {
fmt.Fprintf(&w, " ・")
@@ -549,7 +440,7 @@ func (dw *descriptionWriter) productionToString(prod *production, dot int) strin
return w.String()
}
-func (dw *descriptionWriter) symbolToText(sym symbol) string {
+func (b *lrTableBuilder) symbolToText(sym symbol) string {
if sym.isNil() {
return "<NULL>"
}
@@ -557,13 +448,13 @@ func (dw *descriptionWriter) symbolToText(sym symbol) string {
return "<EOF>"
}
- text, ok := dw.symTab.toText(sym)
+ text, ok := b.symTab.toText(sym)
if !ok {
return fmt.Sprintf("<symbol not found: %v>", sym)
}
if strings.HasPrefix(text, "_") {
- pat, ok := dw.sym2AnonPat[sym]
+ pat, ok := b.sym2AnonPat[sym]
if !ok {
return fmt.Sprintf("<pattern not found: %v>", text)
}
generated by cgit v1.2.3 (git 2.49.0) at 2025-07-12 23:17:12 +0000