goll1e.go

package main

import (
	"io/ioutil"
	"fmt"
	"os"
	"container/vector"
	"utf8"
	"strings"
	"flag"
)

var dev bool

var s scanner
var terms map[string]int
var nonterms map[string]int
var unionEntries map[string]string
var typedEntries map[string]string
var defaultcode string
var prods vector.Vector
var firsts map[int]*set
var follows map[int]*set
var table [][]int
var memorizeTerms bool

var packageName string
var imports vector.StringVector

func init() {
	defaultcode = "{ $$ = $1 }"
	firsts = make(map[int]*set)
	follows = make(map[int]*set)
	terms = make(map[string]int)
	nonterms = make(map[string]int)
	unionEntries = make(map[string]string)
	typedEntries = make(map[string]string)
	terms[""] = 0
}

type production struct {
	name string
	seq  vector.Vector
	code string
}

func (self *production) String() (output string) {
	output = self.name + "["
	for i, w := range self.seq {
		word := w.(tok)
		if i > 0 {
			output += " "
		}
		output += word.text
	}
	output += "]"
	output += self.code
	return
}

func main() {
	var help bool
	flag.BoolVar(&dev, "dev", false, "include grammar developer output during parser generation and input parsing")
	flag.BoolVar(&help, "help", false, "show this message")
	flag.Parse()
	if help {
		flag.Usage()
		os.Exit(0)
	}
	filename := "stdin"
	in, out := os.Stdin, os.Stdout
	var err os.Error
	defer func() {
		if in != os.Stdin {
			in.Close()
		}
		if out != os.Stdout {
			out.Close()
		}
	}()

	if flag.NArg() > 0 {
		filename = flag.Arg(0)
		in, err = os.OpenFile(filename, os.O_RDONLY, 0)
		if nil != err {
			fmt.Println("Cannot", err)
			os.Exit(-1)
		}
	}
	content, err := ioutil.ReadAll(in)
	if nil != err {
		fmt.Println("Cannot", err)
		os.Exit(-2)
	}

	s.content = content
	parseHeader()
	parseProductions()

	if len(terms) == 1 {
		terms[""] = 0, false
	}

	computeFirsts()
	computeFollows()
	computeTable()

	if dev {
		printTermMap(terms)
		printTermMap(nonterms)
		printProductions()

		printSet(firsts, func(i int) string { return prods[i].(*production).name })
		printSet(follows, func(i int) string { return translateNonterm(i) })

		printTable()
		printTableRaw()

		printTypedEntries()
	}

	if len(table) == 0 {
		fmt.Fprintf(os.Stderr, "You must declare at least one rule in your grammar file.")
		os.Exit(-8)
	}

	if flag.NArg() > 1 {
		flags := os.O_CREATE | os.O_WRONLY | os.O_TRUNC
		out, err = os.OpenFile(flag.Arg(1), flags, 0666)
		if nil != err {
			fmt.Println("Cannot create output file", os.Args[2], ":", err)
			os.Exit(-1)
		}
	}

	printFile(out)
	out.Write(s.remainder())
	out.WriteString("\n")
}

func printFile(out *os.File) {
	out.WriteString("// Autogenerated by goll1e, a LL(1) parser generator for the Go programming language.\n")
	out.WriteString("package ")
	out.WriteString(packageName)
	out.WriteString("\n\n")
	out.WriteString("import (\n")
	out.WriteString("\t\"container/vector\"\n")
	for _, port := range imports {
		if port == "container/vector" {
			continue
		}
		out.WriteString("\t\"")
		out.WriteString(port)
		out.WriteString("\"\n")
	}
	out.WriteString(")\n\n")

	out.WriteString("type yystype struct {\n")
	for k, v := range unionEntries {
		out.WriteString("\t")
		out.WriteString(k)
		out.WriteString(" ")
		out.WriteString(v)
		out.WriteString("\n")
	}
	out.WriteString("}\n")

	out.WriteString("var yytable = [")
	out.WriteString(fmt.Sprint(len(table)))
	out.WriteString("][")
	out.WriteString(fmt.Sprint(len(table[0])))
	out.WriteString("]int {\n")
	for r := 0; r < len(table); r++ {
		out.WriteString("\t[")
		out.WriteString(fmt.Sprint(len(table[0])))
		out.WriteString("]int{")
		for c := 0; c < len(table[0]); c++ {
			out.WriteString(fmt.Sprint(table[r][c]))
			out.WriteString(",")
		}
		out.WriteString("},\n")
	}
	out.WriteString("}\n")

	maxChar := 0
	out.WriteString("var yycharmap = map[int]int {\n")
	for token, i := range terms {
		if i == 0 || token[0] != '\'' {
			continue
		}
		char, _ := utf8.DecodeRuneInString(token[1:])
		if char > maxChar {
			maxChar = char
		}
		out.WriteString("\t")
		out.WriteString(token)
		out.WriteString(":")
		out.WriteString(fmt.Sprint(i))
		out.WriteString(",\n")
	}
	out.WriteString("}\n")

	maxChar++
	maxToken := maxChar + len(terms) + 1
	out.WriteString("const (\n")
	out.WriteString("\tyyMINTOKEN int = ")
	out.WriteString(fmt.Sprint(maxChar))
	out.WriteString("\n")
	for token, i := range terms {
		if i == 0 || token[0] == '\'' {
			continue
		}
		out.WriteString("\t")
		out.WriteString(token)
		out.WriteString(" = ")
		out.WriteString(fmt.Sprint(i + maxChar))
		out.WriteString("\n")
	}
	out.WriteString("\tyyMAXTOKEN = ")
	out.WriteString(fmt.Sprint(maxToken))
	out.WriteString("\n")
	out.WriteString("\tyyUSER = ")
	out.WriteString(fmt.Sprint(maxToken + len(prods) + 1))
	out.WriteString("\n")
	out.WriteString(")\n")

	out.WriteString("var yyprods = [")
	out.WriteString(fmt.Sprint(len(prods)))
	out.WriteString("][]int {\n")
	for _, p := range prods {
		prod := p.(*production)
		out.WriteString("\t[")
		out.WriteString("]int{")
		for _, t := range prod.seq {
			token := t.(tok)
			switch token.ttype {
			case term:
				if token.text[0] == '\'' {
					r, _ := utf8.DecodeRuneInString(token.text[1:])
					out.WriteString(fmt.Sprint(r))
				} else {
					out.WriteString(fmt.Sprint(terms[token.text] + maxChar))
				}
			case nonterm:
				out.WriteString(fmt.Sprint(nonterms[token.text] + maxToken + 1))
			}
			out.WriteString(",")
		}
		out.WriteString("},\n")
	}
	out.WriteString("}\n")

	out.WriteString("func yyrunrule(i int, act *yystype, yyres vector.Vector) {\n")
	out.WriteString("	switch i {\n")
	for i, p := range prods {
		prod := p.(*production)
		if len(prod.code) == 0 {
			continue
		}
		out.WriteString("	case ")
		out.WriteString(fmt.Sprint(i))
		out.WriteString(":\n")
		code := strings.Replace(prod.code, "$$", "act."+typedEntries[prod.name], -1)
		for i, t := range prod.seq {
			d := i + 1
			token := t.(tok)
			switch token.ttype {
			case term, nonterm:
				ph := fmt.Sprintf("$%d", d)
				suffix := typedEntries[token.text]
				rep := fmt.Sprintf("yyres[len(yyres) - %d].(*yystype).%s", d, suffix)
				code = strings.Replace(code, ph, rep, -1)
			}
		}
		out.WriteString(code)
		out.WriteString("\n")
	}
	out.WriteString("	}\n")
	out.WriteString("}\n")

	outputType := unionEntries[typedEntries[translateNonterm(0)]]

	out.WriteString("func yytranslate(t int, eof int) int {\n" +
		"	if t == eof {return 0}\n" +
		"	if t >= yyMAXTOKEN {return t - yyMAXTOKEN - 1}\n" +
		"	if t <= yyMINTOKEN {return yycharmap[t]}\n" +
		"	return t - yyMINTOKEN\n" +
		"}\n" +
		"func yyparse(eof int, nextWord func(v *yystype)int) (output bool, result " + outputType + ") {\n" +
		"	curyys := &yystype{}\n" +
		"	var yyres vector.Vector\n" +
		"	var inputs vector.IntVector\n" +
		"	var values vector.Vector\n" +
		"	word := nextWord(curyys)\n" +
		"	if(word > yyMINTOKEN && word < yyMAXTOKEN) {values.Push(curyys)}\n" +
		"	curyys = &yystype{}\n" +
		"	var stack vector.IntVector\n" +
		"	stack.Push(eof)\n" +
		"	stack.Push(0)\n" +
		"	stack.Push(" + fmt.Sprint(maxToken+1) + ")\n" +
		"	tos := stack.Last()\n" +
		"	for true {\n")
	if dev {
		out.WriteString("		fmt.Println(\"WORD: \", word)\n" +
			"		fmt.Println(\"TOS:  \", tos)\n" +
			"		fmt.Println(\"STACK:\", stack)\n")
	}
	out.WriteString("		if tos == eof && word == eof {output = true; break}\n" +
		"		if (tos < yyMAXTOKEN) || tos == eof {\n" +
		"			if tos == word {\n")
	if dev {
		out.WriteString("				fmt.Println(\"Matched on terminal:\", word)\n")
	}
	out.WriteString("				inputs.Push(tos)\n" +
		"				stack.Pop()\n" +
		"				stack.Pop()\n" +
		"				word = nextWord(curyys)\n" +
		"				if(word > yyMINTOKEN && word < yyMAXTOKEN) {values.Push(curyys)}\n" +
		"				curyys = &yystype{}\n" +
		"				tos = stack.Last()\n" +
		"			} else {break}\n" +
		"		} else {\n" +
		"			row, col := yytranslate(tos, eof), yytranslate(word, eof)\n" +
		"			ruleNumber := yytable[row][col]\n" +
		"			if ruleNumber == -1 {break /* Inform of error. */}\n" +
		"			inputs.Push(ruleNumber + yyMAXTOKEN)\n" +
		"			stack.Pop()\n" +
		"			stack.Pop()\n")
	if dev {
		out.WriteString("			fmt.Println(\"Row, Col:\", row, col)\n" +
			"			fmt.Println(\"Rule Number\", ruleNumber)\n")
	}
	out.WriteString("			for i := len(yyprods[ruleNumber]) - 1;\n" +
		"				i >= 0;\n" +
		"				i-- {\n" +
		"				stack.Push(-1)\n" +
		"				stack.Push(yyprods[ruleNumber][i])\n" +
		"			}\n" +
		"			tos = stack.Last()\n" +
		"		}\n" +
		"	}\n")
	if dev {
		out.WriteString("	fmt.Println(\"WORD: \", word)\n" +
			"	fmt.Println(\"TOS:  \", tos)\n" +
			"	fmt.Println(\"STACK:\", stack)\n")
	}
	out.WriteString("	if output {\n" +
		"		for len(inputs) > 0 {\n" +
		"			r := inputs.Pop()\n")
	if dev {
		out.WriteString("			fmt.Println(\"Working result:\", r)\n")
	}
	out.WriteString("			if r < yyMINTOKEN {\n")
	if dev {
		out.WriteString("				fmt.Println(\"Result is literal. Pushing nil.\")\n")
	}
	out.WriteString("				yyres.Push(nil)\n" +
		"				continue\n" +
		"			}\n" +
		"			if r < yyMAXTOKEN {\n" +
		"				value := values.Pop()\n")
	if dev {
		out.WriteString("				fmt.Println(\"Result is token. Pushing\", value)\n")
	}
	out.WriteString("				yyres.Push(value)\n" +
		"				continue\n" +
		"			}\n")
	if dev {
		out.WriteString("			fmt.Println(\"Result is rule number\", r - yyMAXTOKEN)\n" +
			"			fmt.Print(\"RES: \")\n" +
			"			for _, v := range yyres {\n" +
			"				fmt.Print(v, \" \")\n" +
			"			}\n" +
			"			fmt.Print(\"\\n\")\n")
	}
	out.WriteString("			ruleNumber := r - yyMAXTOKEN\n" +
		"			v := &yystype{}\n" +
		"			yyrunrule(ruleNumber, v, yyres)\n" +
		"			numTokens := len(yyprods[ruleNumber])\n" +
		"			for i := 0; i < numTokens; i++ {\n" +
		"				yyres.Pop()\n" +
		"			}\n" +
		"			yyres.Push(v)\n" +
		"		}\n" +
		"		result = yyres[0].(*yystype)." + typedEntries[translateNonterm(0)] + "\n" +
		"	}\n" +
		"	return\n" +
		"}\n")

	out.WriteString("\n")
}