From 94e2400aa8e6017165ab22ba5f2f70a6d0682f63 Mon Sep 17 00:00:00 2001 From: Ryo Nihei Date: Sat, 21 Aug 2021 16:18:56 +0900 Subject: Resolve conflicts by default rules When a shift/reduce conflict occurred, we prioritize the shift action, and when a reduce/reduce conflict occurred, we prioritize the production defined earlier in the grammar file. --- grammar/parsing_table_builder.go | 466 --------------------------------------- 1 file changed, 466 deletions(-) delete mode 100644 grammar/parsing_table_builder.go (limited to 'grammar/parsing_table_builder.go') diff --git a/grammar/parsing_table_builder.go b/grammar/parsing_table_builder.go deleted file mode 100644 index 82b0d34..0000000 --- a/grammar/parsing_table_builder.go +++ /dev/null @@ -1,466 +0,0 @@ -package grammar - -import ( - "fmt" - "io" - "strings" -) - -type ActionType string - -const ( - ActionTypeShift = ActionType("shift") - ActionTypeReduce = ActionType("reduce") - ActionTypeError = ActionType("error") -) - -type actionEntry int - -const actionEntryEmpty = actionEntry(0) - -func newShiftActionEntry(state stateNum) actionEntry { - return actionEntry(state * -1) -} - -func newReduceActionEntry(prod productionNum) actionEntry { - return actionEntry(prod) -} - -func (e actionEntry) isEmpty() bool { - return e == actionEntryEmpty -} - -func (e actionEntry) describe() (ActionType, stateNum, productionNum) { - if e == actionEntryEmpty { - return ActionTypeError, stateNumInitial, productionNumNil - } - if e < 0 { - return ActionTypeShift, stateNum(e * -1), productionNumNil - } - return ActionTypeReduce, stateNumInitial, productionNum(e) -} - -type GoToType string - -const ( - GoToTypeRegistered = GoToType("registered") - GoToTypeError = GoToType("error") -) - -type goToEntry uint - -const goToEntryEmpty = goToEntry(0) - -func newGoToEntry(state stateNum) goToEntry { - return goToEntry(state) -} - -func (e goToEntry) isEmpty() bool { - return e == goToEntryEmpty -} - -func (e goToEntry) describe() (GoToType, stateNum) { - if e == goToEntryEmpty { - return GoToTypeError, stateNumInitial - } - return GoToTypeRegistered, stateNum(e) -} - -type conflict interface { - conflict() -} - -type shiftReduceConflict struct { - state stateNum - sym symbol - nextState stateNum - prodNum productionNum -} - -func (c *shiftReduceConflict) conflict() { -} - -type reduceReduceConflict struct { - state stateNum - sym symbol - prodNum1 productionNum - prodNum2 productionNum -} - -func (c *reduceReduceConflict) conflict() { -} - -var ( - _ conflict = &shiftReduceConflict{} - _ conflict = &reduceReduceConflict{} -) - -type ParsingTable struct { - actionTable []actionEntry - goToTable []goToEntry - stateCount int - terminalCount int - nonTerminalCount int - expectedTerminals [][]int - - InitialState stateNum -} - -func (t *ParsingTable) getAction(state stateNum, sym symbolNum) (ActionType, stateNum, productionNum) { - pos := state.Int()*t.terminalCount + sym.Int() - return t.actionTable[pos].describe() -} - -func (t *ParsingTable) getGoTo(state stateNum, sym symbolNum) (GoToType, stateNum) { - pos := state.Int()*t.nonTerminalCount + sym.Int() - return t.goToTable[pos].describe() -} - -func (t *ParsingTable) writeShiftAction(state stateNum, sym symbol, nextState stateNum) conflict { - pos := state.Int()*t.terminalCount + sym.num().Int() - act := t.actionTable[pos] - if !act.isEmpty() { - ty, _, p := act.describe() - if ty == ActionTypeReduce { - return &shiftReduceConflict{ - state: state, - sym: sym, - nextState: nextState, - prodNum: p, - } - } - } - t.actionTable[pos] = newShiftActionEntry(nextState) - - return nil -} - -func (t *ParsingTable) writeReduceAction(state stateNum, sym symbol, prod productionNum) conflict { - pos := state.Int()*t.terminalCount + sym.num().Int() - act := t.actionTable[pos] - if !act.isEmpty() { - ty, s, p := act.describe() - if ty == ActionTypeReduce && p != prod { - return &reduceReduceConflict{ - state: state, - sym: sym, - prodNum1: p, - prodNum2: prod, - } - } - return &shiftReduceConflict{ - state: state, - sym: sym, - nextState: s, - prodNum: prod, - } - } - t.actionTable[pos] = newReduceActionEntry(prod) - - return nil -} - -func (t *ParsingTable) writeGoTo(state stateNum, sym symbol, nextState stateNum) { - pos := state.Int()*t.nonTerminalCount + sym.num().Int() - t.goToTable[pos] = newGoToEntry(nextState) -} - -type lrTableBuilder struct { - automaton *lr0Automaton - prods *productionSet - termCount int - nonTermCount int - symTab *symbolTable - sym2AnonPat map[symbol]string - - conflicts []conflict -} - -func (b *lrTableBuilder) 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 { - reducibleProd, ok := b.prods.findByID(prodID) - if !ok { - return nil, fmt.Errorf("reducible production not found: %v", prodID) - } - - var reducibleItem *lrItem - for _, item := range state.items { - if item.prod != reducibleProd.id { - continue - } - - reducibleItem = item - break - } - if reducibleItem == nil { - for _, item := range state.emptyProdItems { - if item.prod != reducibleProd.id { - continue - } - - reducibleItem = item - break - } - if reducibleItem == nil { - return nil, fmt.Errorf("reducible item not found; state: %v, production: %v", state.num, reducibleProd.num) - } - } - - for a := range reducibleItem.lookAhead.symbols { - eTerms = append(eTerms, a.num().Int()) - - c := ptab.writeReduceAction(state.num, a, reducibleProd.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 -} - -func (b *lrTableBuilder) write(w io.Writer) { - conflicts := map[stateNum][]conflict{} - for _, con := range b.conflicts { - switch c := con.(type) { - case *shiftReduceConflict: - conflicts[c.state] = append(conflicts[c.state], c) - case *reduceReduceConflict: - conflicts[c.state] = append(conflicts[c.state], c) - } - } - - fmt.Fprintf(w, "# Conflicts\n\n") - - if len(b.conflicts) > 0 { - fmt.Fprintf(w, "%v conflics:\n\n", len(b.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, 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, b.symbolToText(c.sym)) - } - } - fmt.Fprintf(w, "\n") - } else { - fmt.Fprintf(w, "no conflicts\n\n") - } - - fmt.Fprintf(w, "# Terminals\n\n") - - termSyms := b.symTab.terminalSymbols() - - fmt.Fprintf(w, "%v symbols:\n\n", len(termSyms)) - - for _, sym := range termSyms { - text, ok := b.symTab.toText(sym) - if !ok { - text = fmt.Sprintf("", sym) - } - if strings.HasPrefix(text, "_") { - fmt.Fprintf(w, "%4v %v: \"%v\"\n", sym.num(), text, b.sym2AnonPat[sym]) - } else { - fmt.Fprintf(w, "%4v %v\n", sym.num(), text) - } - } - - fmt.Fprintf(w, "\n") - - fmt.Fprintf(w, "# Productions\n\n") - - fmt.Fprintf(w, "%v productions:\n\n", len(b.prods.getAllProductions())) - - 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(b.automaton.states)) - - for _, state := range b.automaton.states { - fmt.Fprintf(w, "state %v\n", state.num) - for _, item := range state.items { - prod, ok := b.prods.findByID(item.prod) - if !ok { - fmt.Fprintf(w, "\n") - continue - } - fmt.Fprintf(w, " %v\n", b.productionToString(prod, item.dot)) - } - - fmt.Fprintf(w, "\n") - - var shiftRecs []string - var reduceRecs []string - var gotoRecs []string - var accRec string - { - for sym, kID := range state.next { - nextState := b.automaton.states[kID] - if sym.isTerminal() { - 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, b.symbolToText(sym))) - } - } - - for prodID := range state.reducible { - prod, ok := b.prods.findByID(prodID) - if !ok { - reduceRecs = append(reduceRecs, "") - continue - } - if prod.lhs.isStart() { - accRec = "accept on " - continue - } - - 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 { - reduceRecs = append(reduceRecs, "") - continue - } - } - for a := range reducibleItem.lookAhead.symbols { - reduceRecs = append(reduceRecs, fmt.Sprintf("reduce %4v on %v", prod.num, b.symbolToText(a))) - } - } - } - - if len(shiftRecs) > 0 || len(reduceRecs) > 0 { - for _, rec := range shiftRecs { - fmt.Fprintf(w, " %v\n", rec) - } - for _, rec := range reduceRecs { - fmt.Fprintf(w, " %v\n", rec) - } - fmt.Fprintf(w, "\n") - } - if len(gotoRecs) > 0 { - for _, rec := range gotoRecs { - fmt.Fprintf(w, " %v\n", rec) - } - fmt.Fprintf(w, "\n") - } - if accRec != "" { - fmt.Fprintf(w, " %v\n\n", accRec) - } - - cons, ok := conflicts[state.num] - if ok { - 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, b.symbolToText(c.sym)) - case *reduceReduceConflict: - 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") - } - } -} - -func (b *lrTableBuilder) productionToString(prod *production, dot int) string { - var w strings.Builder - fmt.Fprintf(&w, "%v →", b.symbolToText(prod.lhs)) - for n, rhs := range prod.rhs { - if n == dot { - fmt.Fprintf(&w, " ・") - } - fmt.Fprintf(&w, " %v", b.symbolToText(rhs)) - } - if dot == len(prod.rhs) { - fmt.Fprintf(&w, " ・") - } - - return w.String() -} - -func (b *lrTableBuilder) symbolToText(sym symbol) string { - if sym.isNil() { - return "" - } - if sym.isEOF() { - return "" - } - - text, ok := b.symTab.toText(sym) - if !ok { - return fmt.Sprintf("", sym) - } - - if strings.HasPrefix(text, "_") { - pat, ok := b.sym2AnonPat[sym] - if !ok { - return fmt.Sprintf("", text) - } - - return fmt.Sprintf(`"%v"`, pat) - } - - return text -} -- cgit v1.2.3