Add describe command to print a description file

6 files changed, 522 insertions, 172 deletions

diff --git a/cmd/vartan/compile.go b/cmd/vartan/compile.go
index 9ffd1c9..73cc5e5 100644
--- a/cmd/vartan/compile.go
+++ b/cmd/vartan/compile.go
@@ -108,7 +108,7 @@ func runCompile(cmd *cobra.Command, args []string) (retErr error) {
 	var descFileName string
 	{
 		_, grmFileName := filepath.Split(grmPath)
-		descFileName = fmt.Sprintf("%v.desc", strings.TrimSuffix(grmFileName, ".vr"))
+		descFileName = fmt.Sprintf("%v-description.json", strings.TrimSuffix(grmFileName, ".vr"))
 	}
 
 	opts := []grammar.CompileOption{
diff --git a/cmd/vartan/describe.go b/cmd/vartan/describe.go
new file mode 100644
index 0000000..d9c3b01
--- /dev/null
+++ b/cmd/vartan/describe.go
@@ -0,0 +1,241 @@
+package main
+
+import (
+	"encoding/json"
+	"fmt"
+	"io"
+	"io/ioutil"
+	"os"
+	"runtime/debug"
+	"strings"
+	"text/template"
+
+	"github.com/nihei9/vartan/spec"
+	"github.com/spf13/cobra"
+)
+
+var describeFlags = struct {
+}{}
+
+func init() {
+	cmd := &cobra.Command{
+		Use:     "describe",
+		Short:   "Print a description file in readable format",
+		Example: `  vartan describe grammar-description.json`,
+		Args:    cobra.ExactArgs(1),
+		RunE:    runDescribe,
+	}
+	rootCmd.AddCommand(cmd)
+}
+
+func runDescribe(cmd *cobra.Command, args []string) (retErr error) {
+	defer func() {
+		panicked := false
+		v := recover()
+		if v != nil {
+			err, ok := v.(error)
+			if !ok {
+				retErr = fmt.Errorf("an unexpected error occurred: %v", v)
+				fmt.Fprintf(os.Stderr, "%v:\n%v", retErr, string(debug.Stack()))
+				return
+			}
+
+			retErr = err
+			panicked = true
+		}
+
+		if retErr != nil {
+			if panicked {
+				fmt.Fprintf(os.Stderr, "%v:\n%v", retErr, string(debug.Stack()))
+			} else {
+				fmt.Fprintf(os.Stderr, "%v\n", retErr)
+			}
+		}
+	}()
+
+	desc, err := readDescription(args[0])
+	if err != nil {
+		return err
+	}
+
+	err = writeDescription(os.Stdout, desc)
+	if err != nil {
+		return err
+	}
+
+	return nil
+}
+
+func readDescription(path string) (*spec.Description, error) {
+	f, err := os.Open(path)
+	if err != nil {
+		return nil, fmt.Errorf("Cannot open the description file %s: %w", path, err)
+	}
+	defer f.Close()
+
+	d, err := ioutil.ReadAll(f)
+	if err != nil {
+		return nil, err
+	}
+
+	desc := &spec.Description{}
+	err = json.Unmarshal(d, desc)
+	if err != nil {
+		return nil, err
+	}
+
+	return desc, nil
+}
+
+const descTemplate = `# Conflicts
+
+{{ printConflictSummary . }}
+
+# Terminals
+
+{{ range slice .Terminals 1 -}}
+{{ printTerminal . }}
+{{ end }}
+# Productions
+
+{{ range slice .Productions 1 -}}
+{{ printProduction . }}
+{{ end }}
+# States
+{{ range .States }}
+## State {{ .Number }}
+
+{{ range .Kernel -}}
+{{ printItem . }}
+{{ end }}
+{{ range .Shift -}}
+{{ printShift . }}
+{{ end -}}
+{{ range .Reduce -}}
+{{ printReduce . }}
+{{ end -}}
+{{ range .GoTo -}}
+{{ printGoTo . }}
+{{ end }}
+{{ range .SRConflict -}}
+{{ printSRConflict . }}
+{{ end -}}
+{{ range .RRConflict -}}
+{{ printRRConflict . }}
+{{ end -}}
+{{ end }}`
+
+func writeDescription(w io.Writer, desc *spec.Description) error {
+	termName := func(sym int) string {
+		if desc.Terminals[sym].Alias != "" {
+			return desc.Terminals[sym].Alias
+		}
+		return desc.Terminals[sym].Name
+	}
+
+	nonTermName := func(sym int) string {
+		return desc.NonTerminals[sym].Name
+	}
+
+	fns := template.FuncMap{
+		"printConflictSummary": func(desc *spec.Description) string {
+			count := 0
+			for _, s := range desc.States {
+				count += len(s.SRConflict)
+				count += len(s.RRConflict)
+			}
+
+			if count == 1 {
+				return fmt.Sprintf("1 conflict was detected.")
+			} else if count > 1 {
+				return fmt.Sprintf("%v conflicts were detected.", count)
+			}
+			return "No conflict was detected."
+		},
+		"printTerminal": func(term spec.Terminal) string {
+			if term.Alias != "" {
+				return fmt.Sprintf("%4v %v (%v)", term.Number, term.Name, term.Alias)
+			}
+			return fmt.Sprintf("%4v %v", term.Number, term.Name)
+		},
+		"printProduction": func(prod spec.Production) string {
+			var b strings.Builder
+			fmt.Fprintf(&b, "%v →", nonTermName(prod.LHS))
+			if len(prod.RHS) > 0 {
+				for _, e := range prod.RHS {
+					if e > 0 {
+						fmt.Fprintf(&b, " %v", termName(e))
+					} else {
+						fmt.Fprintf(&b, " %v", nonTermName(e*-1))
+					}
+				}
+			} else {
+				fmt.Fprintf(&b, " ε")
+			}
+
+			return fmt.Sprintf("%4v %v", prod.Number, b.String())
+		},
+		"printItem": func(item spec.Item) string {
+			prod := desc.Productions[item.Production]
+
+			var b strings.Builder
+			fmt.Fprintf(&b, "%v →", nonTermName(prod.LHS))
+			for i, e := range prod.RHS {
+				if i == item.Dot {
+					fmt.Fprintf(&b, " ・")
+				}
+				if e > 0 {
+					fmt.Fprintf(&b, " %v", termName(e))
+				} else {
+					fmt.Fprintf(&b, " %v", nonTermName(e*-1))
+				}
+			}
+			if item.Dot >= len(prod.RHS) {
+				fmt.Fprintf(&b, " ・")
+			}
+
+			return fmt.Sprintf("%4v %v", prod.Number, b.String())
+		},
+		"printShift": func(tran spec.Transition) string {
+			return fmt.Sprintf("shift  %4v on %v", tran.State, termName(tran.Symbol))
+		},
+		"printReduce": func(reduce spec.Reduce) string {
+			var b strings.Builder
+			{
+				fmt.Fprintf(&b, "%v", termName(reduce.LookAhead[0]))
+				for _, a := range reduce.LookAhead[1:] {
+					fmt.Fprintf(&b, ", %v", termName(a))
+				}
+			}
+			return fmt.Sprintf("reduce %4v on %v", reduce.Production, b.String())
+		},
+		"printGoTo": func(tran spec.Transition) string {
+			return fmt.Sprintf("goto   %4v on %v", tran.State, nonTermName(tran.Symbol))
+		},
+		"printSRConflict": func(sr spec.SRConflict) string {
+			var adopted string
+			switch {
+			case sr.AdoptedState != nil:
+				adopted = fmt.Sprintf("shift %v", *sr.AdoptedState)
+			case sr.AdoptedProduction != nil:
+				adopted = fmt.Sprintf("reduce %v", *sr.AdoptedProduction)
+			}
+			return fmt.Sprintf("shift/reduce conflict (shift %v, reduce %v) on %v: %v adopted", sr.State, sr.Production, termName(sr.Symbol), adopted)
+		},
+		"printRRConflict": func(rr spec.RRConflict) string {
+			return fmt.Sprintf("reduce/reduce conflict (%v, %v) on %v: reduce %v adopted", rr.Production1, rr.Production2, termName(rr.Symbol), rr.AdoptedProduction)
+		},
+	}
+
+	tmpl, err := template.New("").Funcs(fns).Parse(descTemplate)
+	if err != nil {
+		return err
+	}
+
+	err = tmpl.Execute(w, desc)
+	if err != nil {
+		return err
+	}
+
+	return nil
+}
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")
diff --git a/spec/description.go b/spec/description.go
new file mode 100644
index 0000000..d2b6d3b
--- /dev/null
+++ b/spec/description.go
@@ -0,0 +1,67 @@
+package spec
+
+type Terminal struct {
+	Number    int    `json:"number"`
+	Name      string `json:"name"`
+	Anonymous bool   `json:"anonymous"`
+	Alias     string `json:"alias"`
+	Pattern   string `json:"pattern"`
+}
+
+type NonTerminal struct {
+	Number int    `json:"number"`
+	Name   string `json:"name"`
+}
+
+type Production struct {
+	Number int   `json:"number"`
+	LHS    int   `json:"lhs"`
+	RHS    []int `json:"rhs"`
+}
+
+type Item struct {
+	Production int `json:"production"`
+	Dot        int `json:"dot"`
+}
+
+type Transition struct {
+	Symbol int `json:"symbol"`
+	State  int `json:"state"`
+}
+
+type Reduce struct {
+	LookAhead  []int `json:"look_ahead"`
+	Production int   `json:"production"`
+}
+
+type SRConflict struct {
+	Symbol            int  `json:"symbol"`
+	State             int  `json:"state"`
+	Production        int  `json:"production"`
+	AdoptedState      *int `json:"adopted_state"`
+	AdoptedProduction *int `json:"adopted_production"`
+}
+
+type RRConflict struct {
+	Symbol            int `json:"symbol"`
+	Production1       int `json:"production_1"`
+	Production2       int `json:"production_2"`
+	AdoptedProduction int `json:"adopted_production"`
+}
+
+type State struct {
+	Number     int           `json:"number"`
+	Kernel     []*Item       `json:"kernel"`
+	Shift      []*Transition `json:"shift"`
+	Reduce     []*Reduce     `json:"reduce"`
+	GoTo       []*Transition `json:"goto"`
+	SRConflict []*SRConflict `json:"sr_conflict"`
+	RRConflict []*RRConflict `json:"rr_conflict"`
+}
+
+type Description struct {
+	Terminals    []*Terminal    `json:"terminals"`
+	NonTerminals []*NonTerminal `json:"non_terminals"`
+	Productions  []*Production  `json:"productions"`
+	States       []*State       `json:"states"`
+}