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 }