aboutsummaryrefslogtreecommitdiff
path: root/grammar
diff options
context:
space:
mode:
Diffstat (limited to 'grammar')
-rw-r--r--grammar/grammar.go13
-rw-r--r--grammar/parsing_table.go357
-rw-r--r--grammar/symbol.go14
3 files changed, 213 insertions, 171 deletions
diff --git a/grammar/grammar.go b/grammar/grammar.go
index 2f5f3f8..edfb6af 100644
--- a/grammar/grammar.go
+++ b/grammar/grammar.go
@@ -1,6 +1,7 @@
package grammar
import (
+ "encoding/json"
"fmt"
"os"
"strings"
@@ -1027,6 +1028,11 @@ func Compile(gram *Grammar, opts ...CompileOption) (*spec.CompiledGrammar, error
return nil, err
}
+ desc, err := b.genDescription(tab, gram)
+ if err != nil {
+ return nil, err
+ }
+
if config.descriptionFileName != "" {
f, err := os.OpenFile(config.descriptionFileName, os.O_WRONLY|os.O_CREATE|os.O_TRUNC, 0644)
if err != nil {
@@ -1034,7 +1040,12 @@ func Compile(gram *Grammar, opts ...CompileOption) (*spec.CompiledGrammar, error
}
defer f.Close()
- b.writeDescription(f, tab)
+ d, err := json.Marshal(desc)
+ if err != nil {
+ return nil, err
+ }
+
+ f.Write(d)
}
if len(b.conflicts) > 0 {
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
}
diff --git a/grammar/symbol.go b/grammar/symbol.go
index 136e909..3a7dfb6 100644
--- a/grammar/symbol.go
+++ b/grammar/symbol.go
@@ -249,6 +249,20 @@ func (t *symbolTable) terminalTexts() ([]string, error) {
return t.termTexts, nil
}
+func (t *symbolTable) nonTerminalSymbols() []symbol {
+ syms := make([]symbol, 0, t.nonTermNum.Int()-nonTerminalNumMin.Int())
+ for sym := range t.sym2Text {
+ if !sym.isNonTerminal() || sym.isNil() {
+ continue
+ }
+ syms = append(syms, sym)
+ }
+ sort.Slice(syms, func(i, j int) bool {
+ return syms[i] < syms[j]
+ })
+ return syms
+}
+
func (t *symbolTable) nonTerminalTexts() ([]string, error) {
if t.nonTermNum == nonTerminalNumMin || t.nonTermTexts[symbolStart.num().Int()] == "" {
return nil, fmt.Errorf("symbol table has no terminals or no start symbol")
generated by cgit v1.2.3 (git 2.49.0) at 2025-07-22 02:32:39 +0000