diff options
Diffstat (limited to 'grammar/parsing_table.go')
| -rw-r--r-- | grammar/parsing_table.go | 357 |
1 files changed, 187 insertions, 170 deletions
diff --git a/grammar/parsing_table.go b/grammar/parsing_table.go index b6d9484..fe5a619 100644 --- a/grammar/parsing_table.go +++ b/grammar/parsing_table.go @@ -2,9 +2,9 @@ package grammar import ( "fmt" - "io" "sort" - "strings" + + "github.com/nihei9/vartan/spec" ) type ActionType string @@ -318,217 +318,234 @@ func (b *lrTableBuilder) resolveConflict(sym symbolNum, prod productionNum) Acti return ActionTypeReduce } -func (b *lrTableBuilder) writeDescription(w io.Writer, tab *ParsingTable) { - 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) +func (b *lrTableBuilder) genDescription(tab *ParsingTable, gram *Grammar) (*spec.Description, error) { + var terms []*spec.Terminal + { + termSyms := b.symTab.terminalSymbols() + terms = make([]*spec.Terminal, len(termSyms)+2) + + terms[symbolEOF.num()] = &spec.Terminal{ + Number: symbolEOF.num().Int(), + Name: "<eof>", } - } - fmt.Fprintf(w, "# Conflicts\n\n") + for _, sym := range termSyms { + name, ok := b.symTab.toText(sym) + if !ok { + return nil, fmt.Errorf("failed to generate terminals: symbol not found: %v", sym) + } - if len(b.conflicts) > 0 { - fmt.Fprintf(w, "%v conflics:\n\n", len(b.conflicts)) + term := &spec.Terminal{ + Number: sym.num().Int(), + Name: name, + Alias: gram.kindAliases[sym], + } - 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)) + pat, ok := b.sym2AnonPat[sym] + if ok { + term.Anonymous = true + term.Pattern = pat } + + terms[sym.num()] = term } - 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)) + var nonTerms []*spec.NonTerminal + { + nonTermSyms := b.symTab.nonTerminalSymbols() + nonTerms = make([]*spec.NonTerminal, len(nonTermSyms)+1) + for _, sym := range nonTermSyms { + name, ok := b.symTab.toText(sym) + if !ok { + return nil, fmt.Errorf("failed to generate non-terminals: symbol not found: %v", sym) + } - for _, sym := range termSyms { - 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, b.sym2AnonPat[sym]) - } else { - fmt.Fprintf(w, "%4v %v\n", sym.num(), text) + nonTerms[sym.num()] = &spec.NonTerminal{ + Number: sym.num().Int(), + Name: name, + } } } - fmt.Fprintf(w, "\n") - - fmt.Fprintf(w, "# Productions\n\n") - - fmt.Fprintf(w, "%v productions:\n\n", len(b.prods.getAllProductions())) + var prods []*spec.Production + { + ps := gram.productionSet.getAllProductions() + prods = make([]*spec.Production, len(ps)+1) + for _, p := range ps { + rhs := make([]int, len(p.rhs)) + for i, e := range p.rhs { + if e.isTerminal() { + rhs[i] = e.num().Int() + } else { + rhs[i] = e.num().Int() * -1 + } + } - for _, prod := range b.prods.getAllProductions() { - fmt.Fprintf(w, "%4v %v\n", prod.num, b.productionToString(prod, -1)) + prods[p.num.Int()] = &spec.Production{ + Number: p.num.Int(), + LHS: p.lhs.num().Int(), + RHS: rhs, + } + } } - fmt.Fprintf(w, "\n# States\n\n") + var states []*spec.State + { + srConflicts := map[stateNum][]*shiftReduceConflict{} + rrConflicts := map[stateNum][]*reduceReduceConflict{} + for _, con := range b.conflicts { + switch c := con.(type) { + case *shiftReduceConflict: + srConflicts[c.state] = append(srConflicts[c.state], c) + case *reduceReduceConflict: + rrConflicts[c.state] = append(rrConflicts[c.state], c) + } + } - fmt.Fprintf(w, "%v states:\n\n", len(b.automaton.states)) + states = make([]*spec.State, len(b.automaton.states)) + for _, s := range b.automaton.states { + kernel := make([]*spec.Item, len(s.items)) + for i, item := range s.items { + p, ok := b.prods.findByID(item.prod) + if !ok { + return nil, fmt.Errorf("failed to generate states: production of kernel item not found: %v", item.prod) + } - 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, "<production not found>\n") - continue + kernel[i] = &spec.Item{ + Production: p.num.Int(), + Dot: item.dot, + } } - fmt.Fprintf(w, " %v\n", b.productionToString(prod, item.dot)) - } - fmt.Fprintf(w, "\n") + sort.Slice(kernel, func(i, j int) bool { + if kernel[i].Production < kernel[j].Production { + return true + } + if kernel[i].Production > kernel[j].Production { + return false + } + return kernel[i].Dot < kernel[j].Dot + }) - var shiftRecs []string - var reduceRecs []string - var gotoRecs []string - var accRec string - { - for sym, kID := range state.next { + var shift []*spec.Transition + var goTo []*spec.Transition + for sym, kID := range s.next { nextState := b.automaton.states[kID] if sym.isTerminal() { - shiftRecs = append(shiftRecs, fmt.Sprintf("shift %4v on %v", nextState.num, b.symbolToText(sym))) + shift = append(shift, &spec.Transition{ + Symbol: sym.num().Int(), + State: nextState.num.Int(), + }) } else { - gotoRecs = append(gotoRecs, fmt.Sprintf("goto %4v on %v", nextState.num, b.symbolToText(sym))) + goTo = append(goTo, &spec.Transition{ + Symbol: sym.num().Int(), + State: nextState.num.Int(), + }) } } - for prodID := range state.reducible { - prod, ok := b.prods.findByID(prodID) - if !ok { - reduceRecs = append(reduceRecs, "<production not found>") + sort.Slice(shift, func(i, j int) bool { + return shift[i].State < shift[j].State + }) + + sort.Slice(goTo, func(i, j int) bool { + return goTo[i].State < goTo[j].State + }) + + var reduce []*spec.Reduce + for _, item := range s.items { + if !item.reducible { continue } - if prod.lhs.isStart() { - accRec = "accept on <EOF>" - continue + + syms := make([]int, len(item.lookAhead.symbols)) + i := 0 + for a := range item.lookAhead.symbols { + syms[i] = a.num().Int() + i++ } - var reducibleItem *lrItem - for _, item := range state.items { - if item.prod != prodID { - continue - } + sort.Slice(syms, func(i, j int) bool { + return syms[i] < syms[j] + }) - reducibleItem = item - break + prod, ok := gram.productionSet.findByID(item.prod) + if !ok { + return nil, fmt.Errorf("failed to generate states: reducible production not found: %v", item.prod) } - 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, b.symbolToText(a))) - } - } - } + reduce = append(reduce, &spec.Reduce{ + LookAhead: syms, + Production: prod.num.Int(), + }) - 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) + sort.Slice(reduce, func(i, j int) bool { + return reduce[i].Production < reduce[j].Production + }) } - 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 { - syms := map[symbol]struct{}{} - 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)) - syms[c.sym] = struct{}{} - case *reduceReduceConflict: - fmt.Fprintf(w, " reduce/reduce conflict (reduce %v and %v) on %v\n", c.prodNum1, c.prodNum2, b.symbolToText(c.sym)) - syms[c.sym] = struct{}{} - } - } - for sym := range syms { - ty, s, p := tab.getAction(state.num, sym.num()) - switch ty { - case ActionTypeShift: - fmt.Fprintf(w, " adopted shift %4v on %v\n", s, b.symbolToText(sym)) - case ActionTypeReduce: - fmt.Fprintf(w, " adopted reduce %4v on %v\n", p, b.symbolToText(sym)) + sr := []*spec.SRConflict{} + rr := []*spec.RRConflict{} + { + for _, c := range srConflicts[s.num] { + conflict := &spec.SRConflict{ + Symbol: c.sym.num().Int(), + State: c.nextState.Int(), + Production: c.prodNum.Int(), + } + + ty, s, p := tab.getAction(s.num, c.sym.num()) + switch ty { + case ActionTypeShift: + n := s.Int() + conflict.AdoptedState = &n + case ActionTypeReduce: + n := p.Int() + conflict.AdoptedProduction = &n + } + + sr = append(sr, conflict) } - } - 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, " ・") - } + sort.Slice(sr, func(i, j int) bool { + return sr[i].Symbol < sr[j].Symbol + }) - return w.String() -} + for _, c := range rrConflicts[s.num] { + conflict := &spec.RRConflict{ + Symbol: c.sym.num().Int(), + Production1: c.prodNum1.Int(), + Production2: c.prodNum2.Int(), + } -func (b *lrTableBuilder) symbolToText(sym symbol) string { - if sym.isNil() { - return "<NULL>" - } - if sym.isEOF() { - return "<EOF>" - } + _, _, p := tab.getAction(s.num, c.sym.num()) + conflict.AdoptedProduction = p.Int() - text, ok := b.symTab.toText(sym) - if !ok { - return fmt.Sprintf("<symbol not found: %v>", sym) - } + rr = append(rr, conflict) + } - if strings.HasPrefix(text, "_") { - pat, ok := b.sym2AnonPat[sym] - if !ok { - return fmt.Sprintf("<pattern not found: %v>", text) - } + sort.Slice(rr, func(i, j int) bool { + return rr[i].Symbol < rr[j].Symbol + }) + } - return fmt.Sprintf(`"%v"`, pat) + states[s.num.Int()] = &spec.State{ + Number: s.num.Int(), + Kernel: kernel, + Shift: shift, + Reduce: reduce, + GoTo: goTo, + SRConflict: sr, + RRConflict: rr, + } + } } - return text + return &spec.Description{ + Terminals: terms, + NonTerminals: nonTerms, + Productions: prods, + States: states, + }, nil } |