2 Derived from Inferno's utils/iyacc/yacc.c
3 http://code.google.com/p/inferno-os/source/browse/utils/iyacc/yacc.c
5 This copyright NOTICE applies to all files in this directory and
6 subdirectories, unless another copyright notice appears in a given
7 file or subdirectory. If you take substantial code from this software to use in
8 other programs, you must somehow include with it an appropriate
9 copyright notice that includes the copyright notice and the other
10 notices below. It is fine (and often tidier) to do that in a separate
11 file such as NOTICE, LICENCE or COPYING.
13 Copyright © 1994-1999 Lucent Technologies Inc. All rights reserved.
14 Portions Copyright © 1995-1997 C H Forsyth (forsyth@terzarima.net)
15 Portions Copyright © 1997-1999 Vita Nuova Limited
16 Portions Copyright © 2000-2007 Vita Nuova Holdings Limited (www.vitanuova.com)
17 Portions Copyright © 2004,2006 Bruce Ellis
18 Portions Copyright © 2005-2007 C H Forsyth (forsyth@terzarima.net)
19 Revisions Copyright © 2000-2007 Lucent Technologies Inc. and others
20 Portions Copyright © 2009 The Go Authors. All rights reserved.
22 Permission is hereby granted, free of charge, to any person obtaining a copy
23 of this software and associated documentation files (the "Software"), to deal
24 in the Software without restriction, including without limitation the rights
25 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
26 copies of the Software, and to permit persons to whom the Software is
27 furnished to do so, subject to the following conditions:
29 The above copyright notice and this permission notice shall be included in
30 all copies or substantial portions of the Software.
32 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
33 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
34 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
35 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
36 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
37 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
44 // major difference is lack of stem ("y" variable)
60 // the following are adjustable
61 // according to memory size
67 SYMINC = 50 // increase for non-term or term
68 RULEINC = 50 // increase for max rule length prodptr[i]
69 PRODINC = 100 // increase for productions prodptr
70 WSETINC = 50 // increase for working sets wsets
71 STATEINC = 200 // increase for states statemem
73 PRIVATE = 0xE000 // unicode private use
75 // relationships which must hold:
76 // TEMPSIZE >= NTERMS + NNONTERM + 1;
77 // TEMPSIZE >= NSTATES;
84 TOKSTART = 4 //index of first defined token
87 // no, left, right, binary assoc.
95 // flags for state generation
102 // flags for a rule having an action, and being reduced
104 ACTFLAG = 1 << (iota + 2)
108 // output parser flags
113 IDENTIFIER = PRIVATE + iota
136 // macros for getting associativity and precedence levels
137 func ASSOC(i int) int { return i & 3 }
139 func PLEVEL(i int) int { return (i >> 4) & 077 }
141 func TYPE(i int) int { return (i >> 10) & 077 }
143 // macros for setting associativity and precedence levels
144 func SETASC(i, j int) int { return i | j }
146 func SETPLEV(i, j int) int { return i | (j << 4) }
148 func SETTYPE(i, j int) int { return i | (j << 10) }
151 var finput *bufio.Reader // input file
152 var stderr *bufio.Writer
153 var ftable *bufio.Writer // y.go file
154 var fcode = &bytes.Buffer{} // saved code
155 var foutput *bufio.Writer // y.output file
157 var fmtImported bool // output file has recorded an import of "fmt"
159 var oflag string // -o [y.go] - y.go file
160 var vflag string // -v [y.output] - y.output file
161 var lflag bool // -l - disable line directives
162 var prefix string // name prefix for identifiers, default yy
165 flag.StringVar(&oflag, "o", "y.go", "parser output")
166 flag.StringVar(&prefix, "p", "yy", "name prefix to use in generated code")
167 flag.StringVar(&vflag, "v", "y.output", "create parsing tables")
168 flag.BoolVar(&lflag, "l", false, "disable line directives")
171 var initialstacksize = 16
173 // communication variables between various I/O routines
174 var infile string // input file name
175 var numbval int // value of an input number
176 var tokname string // input token name, slop for runes and 0
179 // structure declarations
184 off int // offset within the production
185 first int // first term or non-term in item
186 prodno int // production number for sorting
207 var ntypes int // number of types defined
208 var typeset = make(map[int]string) // pointers to type tags
212 var ntokens = 0 // number of tokens
214 var toklev []int // vector with the precedence of the terminals
216 // nonterminal information
218 var nnonter = -1 // the number of nonterminals
220 var start int // start symbol
224 var nstate = 0 // number of states
225 var pstate = make([]int, NSTATES+2) // index into statemem to the descriptions of the states
227 var tystate = make([]int, NSTATES) // contains type information about the states
228 var tstates []int // states generated by terminal gotos
229 var ntstates []int // states generated by nonterminal gotos
230 var mstates = make([]int, NSTATES) // chain of overflows of term/nonterm generation lists
231 var lastred int // number of last reduction of a state
232 var defact = make([]int, NSTATES) // default actions of states
234 // lookahead set information
236 var nolook = 0 // flag to turn off lookahead computations
237 var tbitset = 0 // size of lookahead sets
238 var clset Lkset // temporary storage for lookahead computations
240 // working set information
245 // storage for action table
247 var amem []int // action table storage
248 var memp int // next free action table position
249 var indgo = make([]int, NSTATES) // index to the stored goto table
251 // temporary vector, indexable by states, terms, or ntokens
253 var temp1 = make([]int, TEMPSIZE) // temporary storage, indexed by terms + ntokens or states
254 var lineno = 1 // current input line number
255 var fatfl = 1 // if on, error is fatal
256 var nerrors = 0 // number of errors
258 // assigned token type values
262 // grammar rule information
264 var nprod = 1 // number of productions
265 var prdptr [][]int // pointers to descriptions of productions
266 var levprd []int // precedence levels for the productions
267 var rlines []int // line number for this rule
269 // statistics collection variables
287 var maxspr int // maximum spread of any entry
288 var maxoff int // maximum offset into a array
291 // storage for information about the nonterminals
293 var pres [][][]int // vector of pointers to productions yielding each nonterminal
295 var pempty []int // vector of nonterminals nontrivially deriving e
297 // random stuff picked out from between functions
299 var indebug = 0 // debugging flag for cpfir
300 var pidebug = 0 // debugging flag for putitem
301 var gsdebug = 0 // debugging flag for stagen
302 var cldebug = 0 // debugging flag for closure
303 var pkdebug = 0 // debugging flag for apack
304 var g2debug = 0 // debugging for go2gen
305 var adb = 0 // debugging for callopt
315 {"nonassoc", BINARY},
348 setup() // initialize and read productions
350 tbitset = (ntokens + 32) / 32
351 cpres() // make table of which productions yield a given nonterminal
352 cempty() // make a table of which nonterminals can match the empty string
353 cpfir() // make a table of firsts of nonterminals
355 stagen() // generate the states
357 yypgo = make([][]int, nnonter+1)
358 optst = make([][]int, nstate)
359 output() // write the states and the tables
375 stderr = bufio.NewWriter(os.Stderr)
379 if flag.NArg() != 1 {
382 if initialstacksize < 1 {
383 // never set so cannot happen
384 fmt.Fprintf(stderr, "yacc: stack size too small\n")
387 yaccpar = strings.Replace(yaccpartext, "$$", prefix, -1)
390 fmt.Fprintf(ftable, "// Code generated by goyacc %s. DO NOT EDIT.\n", strings.Join(os.Args[1:], " "))
393 extval = PRIVATE // tokens start in unicode 'private use'
405 errorf("syntax error tok=%v", t-PRIVATE)
416 errorf("bad %%start construction")
418 start = chfind(1, tokname)
428 if t != IDENTIFIER && t != IDENTCOLON {
429 errorf("bad syntax in %%error")
431 tokens = append(tokens, tokname)
436 if gettok() != IDENTIFIER {
437 errorf("bad syntax in %%error")
439 errors = append(errors, Error{lno, tokens, tokname})
444 errorf("bad syntax in %%type")
451 t = chfind(1, tokname)
454 if j != 0 && j != ty {
455 errorf("type redeclaration of token %s",
458 toklev[t] = SETTYPE(toklev[t], ty)
461 j = nontrst[t-NTBASE].value
462 if j != 0 && j != ty {
463 errorf("type redeclaration of nonterminal %v",
464 nontrst[t-NTBASE].name)
466 nontrst[t-NTBASE].value = ty
481 case LEFT, BINARY, RIGHT, TERM:
482 // nonzero means new prec. and assoc.
489 // get identifiers so defined
492 // there is a type defined
507 j = chfind(0, tokname)
509 errorf("%v defined earlier as nonterminal", tokname)
512 if ASSOC(toklev[j]) != 0 {
513 errorf("redeclaration of precedence of %v", tokname)
515 toklev[j] = SETASC(toklev[j], lev)
516 toklev[j] = SETPLEV(toklev[j], i)
519 if TYPE(toklev[j]) != 0 {
520 errorf("redeclaration of type of %v", tokname)
522 toklev[j] = SETTYPE(toklev[j], ty)
526 tokset[j].value = numbval
543 errorf("unexpected EOF before %%")
546 fmt.Fprintf(fcode, "switch %snt {\n", prefix)
549 prdptr[0] = []int{NTBASE, start, 1, 0}
552 curprod := make([]int, RULEINC)
555 errorf("bad syntax on first rule")
559 prdptr[0][1] = chfind(1, tokname)
563 // put into prdptr array in the format
565 // followed by id's of terminals and non-terminals
566 // followed by -nprod
568 for t != MARK && t != ENDFILE {
572 rlines[nprod] = lineno
575 curprod[mem] = prdptr[nprod-1][0]
577 } else if t == IDENTCOLON {
578 curprod[mem] = chfind(1, tokname)
579 if curprod[mem] < NTBASE {
580 lerrorf(ruleline, "token illegal on LHS of grammar rule")
584 lerrorf(ruleline, "illegal rule: missing semicolon or | ?")
590 for t == IDENTIFIER {
591 curprod[mem] = chfind(1, tokname)
592 if curprod[mem] < NTBASE {
593 levprd[nprod] = toklev[curprod[mem]]
596 if mem >= len(curprod) {
597 ncurprod := make([]int, mem+RULEINC)
598 copy(ncurprod, curprod)
604 if gettok() != IDENTIFIER {
605 lerrorf(ruleline, "illegal %%prec syntax")
607 j = chfind(2, tokname)
609 lerrorf(ruleline, "nonterminal "+nontrst[j-NTBASE].name+" illegal after %%prec")
611 levprd[nprod] = toklev[j]
617 levprd[nprod] |= ACTFLAG
618 fmt.Fprintf(fcode, "\n\tcase %v:", nprod)
619 fmt.Fprintf(fcode, "\n\t\t%sDollar = %sS[%spt-%v:%spt+1]", prefix, prefix, prefix, mem-1, prefix)
622 // action within rule...
625 // make it a nonterminal
626 j = chfind(1, fmt.Sprintf("$$%v", nprod))
629 // the current rule will become rule number nprod+1
630 // enter null production for action
632 prdptr[nprod] = make([]int, 2)
634 prdptr[nprod][1] = -nprod
636 // update the production information
639 levprd[nprod] = levprd[nprod-1] & ^ACTFLAG
640 levprd[nprod-1] = ACTFLAG
641 rlines[nprod] = lineno
643 // make the action appear in the original rule
646 if mem >= len(curprod) {
647 ncurprod := make([]int, mem+RULEINC)
648 copy(ncurprod, curprod)
657 curprod[mem] = -nprod
660 // check that default action is reasonable
661 if ntypes != 0 && (levprd[nprod]&ACTFLAG) == 0 &&
662 nontrst[curprod[0]-NTBASE].value != 0 {
663 // no explicit action, LHS has value
666 lerrorf(ruleline, "must return a value, since LHS has a type")
668 if tempty >= NTBASE {
669 tempty = nontrst[tempty-NTBASE].value
671 tempty = TYPE(toklev[tempty])
673 if tempty != nontrst[curprod[0]-NTBASE].value {
674 lerrorf(ruleline, "default action causes potential type clash")
678 prdptr[nprod] = make([]int, mem)
679 copy(prdptr[nprod], curprod)
685 if TEMPSIZE < ntokens+nnonter+1 {
686 errorf("too many tokens (%d) or non-terminals (%d)", ntokens, nnonter)
691 // dump out the prefix code
694 fmt.Fprintf(fcode, "\n\t}")
696 // put out non-literal terminals
697 for i := TOKSTART; i <= ntokens; i++ {
699 if !tokset[i].noconst {
700 fmt.Fprintf(ftable, "const %v = %v\n", tokset[i].name, tokset[i].value)
704 // put out names of tokens
705 ftable.WriteRune('\n')
706 fmt.Fprintf(ftable, "var %sToknames = [...]string{\n", prefix)
707 for i := 1; i <= ntokens; i++ {
708 fmt.Fprintf(ftable, "\t%q,\n", tokset[i].name)
710 fmt.Fprintf(ftable, "}\n")
712 // put out names of states.
713 // commented out to avoid a huge table just for debugging.
714 // re-enable to have the names in the binary.
715 ftable.WriteRune('\n')
716 fmt.Fprintf(ftable, "var %sStatenames = [...]string{\n", prefix)
717 // for i:=TOKSTART; i<=ntokens; i++ {
718 // fmt.Fprintf(ftable, "\t%q,\n", tokset[i].name);
720 fmt.Fprintf(ftable, "}\n")
722 ftable.WriteRune('\n')
723 fmt.Fprintf(ftable, "const %sEofCode = 1\n", prefix)
724 fmt.Fprintf(ftable, "const %sErrCode = 2\n", prefix)
725 fmt.Fprintf(ftable, "const %sInitialStackSize = %v\n", prefix, initialstacksize)
728 // copy any postfix code
732 fmt.Fprintf(ftable, "\n//line %v:%v\n", infile, lineno)
745 // allocate enough room to hold another production
751 aprod := make([][]int, nn)
752 alevprd := make([]int, nn)
753 arlines := make([]int, nn)
756 copy(alevprd, levprd)
757 copy(arlines, rlines)
766 // define s to be a terminal if nt==0
767 // or a nonterminal if nt==1
769 func defin(nt int, s string) int {
773 if nnonter >= len(nontrst) {
774 anontrst := make([]Symb, nnonter+SYMINC)
775 copy(anontrst, nontrst)
778 nontrst[nnonter] = Symb{name: s}
779 return NTBASE + nnonter
784 if ntokens >= len(tokset) {
785 nn := ntokens + SYMINC
786 atokset := make([]Symb, nn)
787 atoklev := make([]int, nn)
789 copy(atoklev, toklev)
790 copy(atokset, tokset)
795 tokset[ntokens].name = s
798 // establish value for token
799 // single character literal
800 if s[0] == '\'' || s[0] == '"' {
801 q, err := strconv.Unquote(s)
803 errorf("invalid token: %s", err)
807 errorf("character token too long: %s", s)
811 errorf("token value 0 is illegal")
813 tokset[ntokens].noconst = true
818 tokset[ntokens].noconst = true
822 tokset[ntokens].value = val
837 for c == ' ' || c == '\n' || c == '\t' || c == '\v' || c == '\r' {
844 // skip comment -- fix
854 fmt.Printf(">>> ENDFILE %v\n", lineno)
861 fmt.Printf(">>> ={ %v\n", lineno)
866 // get, and look up, a type name (union member name)
868 for c != '>' && c != EOF && c != '\n' {
874 errorf("unterminated < ... > clause")
877 for i = 1; i <= ntypes; i++ {
878 if typeset[i] == tokname {
881 fmt.Printf(">>> TYPENAME old <%v> %v\n", tokname, lineno)
888 typeset[numbval] = tokname
890 fmt.Printf(">>> TYPENAME new <%v> %v\n", tokname, lineno)
899 if c == '\n' || c == EOF {
900 errorf("illegal or missing ' or \"")
903 tokname += string('\\')
905 } else if c == match {
907 fmt.Printf(">>> IDENTIFIER \"%v\" %v\n", tokname, lineno)
920 fmt.Printf(">>> MARK %%%% %v\n", lineno)
925 fmt.Printf(">>> PREC %%= %v\n", lineno)
930 fmt.Printf(">>> LCURLY %%{ %v\n", lineno)
936 // find a reserved word
937 for i := range resrv {
938 if tokname == resrv[i].name {
940 fmt.Printf(">>> %%%v %v %v\n", tokname,
941 resrv[i].value-PRIVATE, lineno)
943 return resrv[i].value
946 errorf("invalid escape, or illegal reserved word: %v", tokname)
948 case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
949 numbval = int(c - '0')
955 numbval = numbval*10 + int(c-'0')
959 fmt.Printf(">>> NUMBER %v %v\n", numbval, lineno)
964 if isword(c) || c == '.' || c == '$' {
969 fmt.Printf(">>> OPERATOR %v %v\n", string(c), lineno)
974 // look ahead to distinguish IDENTIFIER from IDENTCOLON
976 for c == ' ' || c == '\t' || c == '\n' || c == '\v' || c == '\r' || c == '/' {
982 peekline += skipcom()
988 fmt.Printf(">>> IDENTCOLON %v: %v\n", tokname, lineno)
995 fmt.Printf(">>> IDENTIFIER %v %v\n", tokname, lineno)
1000 func getword(c rune) {
1002 for isword(c) || isdigit(c) || c == '.' || c == '$' {
1003 tokname += string(c)
1006 ungetrune(finput, c)
1010 // determine the type of a symbol
1012 func fdtype(t int) int {
1017 v = nontrst[t-NTBASE].value
1018 s = nontrst[t-NTBASE].name
1024 errorf("must specify type for %v", s)
1029 func chfind(t int, s string) int {
1030 if s[0] == '"' || s[0] == '\'' {
1033 for i := 0; i <= ntokens; i++ {
1034 if s == tokset[i].name {
1038 for i := 0; i <= nnonter; i++ {
1039 if s == nontrst[i].name {
1046 errorf("%v should have been defined earlier", s)
1052 // copy the union declaration to the output, and the define file if present
1057 fmt.Fprintf(ftable, "\n//line %v:%v\n", infile, lineno)
1059 fmt.Fprintf(ftable, "type %sSymType struct", prefix)
1065 c := getrune(finput)
1067 errorf("EOF encountered while processing %%union")
1075 fmt.Fprintf(ftable, "\n\tyys int")
1085 fmt.Fprintf(ftable, "\n\n")
1089 // saves code between %{ and %}
1090 // adds an import for __fmt__ the first time
1095 c := getrune(finput)
1101 fmt.Fprintf(ftable, "\n//line %v:%v\n", infile, lineno)
1103 // accumulate until %}
1104 code := make([]rune, 0, 1024)
1109 emitcode(code, lno+1)
1112 code = append(code, '%')
1114 code = append(code, c)
1121 errorf("eof before %%}")
1125 // emits code saved up from between %{ and %}
1126 // called by cpycode
1127 // adds an import for __yyfmt__ after the package clause
1129 func emitcode(code []rune, lineno int) {
1130 for i, line := range lines(code) {
1132 if !fmtImported && isPackageClause(line) {
1133 fmt.Fprintln(ftable, `import __yyfmt__ "fmt"`)
1135 fmt.Fprintf(ftable, "//line %v:%v\n\t\t", infile, lineno+i)
1143 // does this line look like a package clause? not perfect: might be confused by early comments.
1145 func isPackageClause(line []rune) bool {
1146 line = skipspace(line)
1148 // must be big enough.
1149 if len(line) < len("package X\n") {
1153 // must start with "package"
1154 for i, r := range []rune("package") {
1159 line = skipspace(line[len("package"):])
1161 // must have another identifier.
1162 if len(line) == 0 || (!unicode.IsLetter(line[0]) && line[0] != '_') {
1166 if !unicode.IsLetter(line[0]) && !unicode.IsDigit(line[0]) && line[0] != '_' {
1171 line = skipspace(line)
1173 // eol, newline, or comment must follow
1177 if line[0] == '\r' || line[0] == '\n' {
1181 return line[0] == '/' && (line[1] == '/' || line[1] == '*')
1187 // skip initial spaces
1189 func skipspace(line []rune) []rune {
1191 if line[0] != ' ' && line[0] != '\t' {
1200 // break code into lines
1202 func lines(code []rune) [][]rune {
1203 l := make([][]rune, 0, 100)
1205 // one line per loop
1207 for i = range code {
1208 if code[i] == '\n' {
1212 l = append(l, code[:i+1])
1219 // writes code to ftable
1221 func writecode(code []rune) {
1222 for _, r := range code {
1228 // skip over comments
1229 // skipcom is called after reading a '/'
1231 func skipcom() int {
1232 c := getrune(finput)
1240 errorf("EOF inside comment")
1244 errorf("illegal comment")
1247 nl := 0 // lines skipped
1271 // copy action to the next ; or closing }
1273 func cpyact(curprod []int, max int) {
1276 fmt.Fprintf(fcode, "\n//line %v:%v", infile, lineno)
1278 fmt.Fprint(fcode, "\n\t\t")
1285 c := getrune(finput)
1305 ungetrune(finput, c)
1306 if gettok() != TYPENAME {
1307 errorf("bad syntax on $<ident> clause")
1313 fmt.Fprintf(fcode, "%sVAL", prefix)
1315 // put out the proper tag...
1318 tok = fdtype(curprod[0])
1320 fmt.Fprintf(fcode, ".%v", typeset[tok])
1331 j = j*10 + int(c-'0')
1334 ungetrune(finput, c)
1337 errorf("Illegal use of $%v", j)
1339 } else if isword(c) || c == '.' {
1341 ungetrune(finput, c)
1342 if gettok() != IDENTIFIER {
1343 errorf("$ must be followed by an identifier")
1345 tokn := chfind(2, tokname)
1349 ungetrune(finput, c)
1350 } else if gettok() != NUMBER {
1351 errorf("@ must be followed by number")
1355 for j = 1; j < max; j++ {
1356 if tokn == curprod[j] {
1364 errorf("$name or $name@number not found")
1367 fcode.WriteRune('$')
1369 fcode.WriteRune('-')
1371 ungetrune(finput, c)
1374 fmt.Fprintf(fcode, "%sDollar[%v]", prefix, j)
1376 // put out the proper tag
1378 if j <= 0 && tok < 0 {
1379 errorf("must specify type of $%v", j)
1382 tok = fdtype(curprod[j])
1384 fmt.Fprintf(fcode, ".%v", typeset[tok])
1397 nc := getrune(finput)
1398 if nc != '/' && nc != '*' {
1399 ungetrune(finput, nc)
1410 if nc == '/' { // end of // comment
1413 case c == '*' && nc == '*': // end of /* comment?
1414 nnc := getrune(finput)
1416 fcode.WriteRune('*')
1417 fcode.WriteRune('/')
1420 ungetrune(finput, nnc)
1425 errorf("EOF inside comment")
1428 // character string or constant
1439 } else if c == match {
1443 errorf("newline in string or char const")
1448 errorf("EOF in string or character constant")
1452 errorf("action does not terminate")
1455 fmt.Fprint(fcode, "\n\t")
1465 infile = flag.Arg(0)
1466 finput = open(infile)
1468 errorf("cannot open %v", infile)
1473 foutput = create(vflag)
1475 errorf("can't create file %v", vflag)
1483 ftable = create(oflag)
1485 errorf("can't create file %v", oflag)
1491 // return a pointer to the name of symbol i
1493 func symnam(i int) string {
1497 s = nontrst[i-NTBASE].name
1505 // set elements 0 through n-1 to c
1507 func aryfil(v []int, n, c int) {
1508 for i := 0; i < n; i++ {
1514 // compute an array with the beginnings of productions yielding given nonterminals
1515 // The array pres points to these lists
1516 // the array pyield has the lists: the total size is only NPROD+1
1519 pres = make([][][]int, nnonter+1)
1520 curres := make([][]int, nprod)
1523 for j := 0; j <= nnonter; j++ {
1524 fmt.Printf("nnonter[%v] = %v\n", j, nontrst[j].name)
1526 for j := 0; j < nprod; j++ {
1527 fmt.Printf("prdptr[%v][0] = %v+NTBASE\n", j, prdptr[j][0]-NTBASE)
1531 fatfl = 0 // make undefined symbols nonfatal
1532 for i := 0; i <= nnonter; i++ {
1535 for j := 0; j < nprod; j++ {
1536 if prdptr[j][0] == c {
1537 curres[n] = prdptr[j][1:]
1542 errorf("nonterminal %v not defined", nontrst[i].name)
1545 pres[i] = make([][]int, n)
1546 copy(pres[i], curres)
1556 // mark nonterminals which derive the empty string
1557 // also, look for nonterminals which don't derive any token strings
1563 pempty = make([]int, nnonter+1)
1565 // first, use the array pempty to detect productions that can never be reduced
1566 // set pempty to WHONOWS
1567 aryfil(pempty, nnonter+1, WHOKNOWS)
1569 // now, look at productions, marking nonterminals which derive something
1572 for i = 0; i < nprod; i++ {
1574 if pempty[prd[0]-NTBASE] != 0 {
1578 for p = 1; p < np; p++ {
1579 if prd[p] >= NTBASE && pempty[prd[p]-NTBASE] == WHOKNOWS {
1583 // production can be derived
1585 pempty[prd[0]-NTBASE] = OK
1592 // now, look at the nonterminals, to see if they are all OK
1593 for i = 0; i <= nnonter; i++ {
1594 // the added production rises or falls as the start symbol ...
1598 if pempty[i] != OK {
1600 errorf("nonterminal " + nontrst[i].name + " never derives any token string")
1609 // now, compute the pempty array, to see which nonterminals derive the empty string
1610 // set pempty to WHOKNOWS
1611 aryfil(pempty, nnonter+1, WHOKNOWS)
1613 // loop as long as we keep finding empty nonterminals
1618 for i = 1; i < nprod; i++ {
1619 // not known to be empty
1621 if pempty[prd[0]-NTBASE] != WHOKNOWS {
1625 for p = 1; p < np; p++ {
1626 if prd[p] < NTBASE || pempty[prd[p]-NTBASE] != EMPTY {
1631 // we have a nontrivially empty nonterminal
1632 pempty[prd[0]-NTBASE] = EMPTY
1634 // got one ... try for another
1642 // compute an array with the first of nonterminals
1645 var s, n, p, np, ch, i int
1649 wsets = make([]Wset, nnonter+WSETINC)
1650 pfirst = make([]Lkset, nnonter+1)
1651 for i = 0; i <= nnonter; i++ {
1652 wsets[i].ws = mkset()
1657 // initially fill the sets
1658 for s = 0; s < n; s++ {
1661 for p = 0; p < np; p++ {
1664 setbit(pfirst[i], ch)
1667 if pempty[ch-NTBASE] == 0 {
1674 // now, reflect transitivity
1678 for i = 0; i <= nnonter; i++ {
1681 for s = 0; s < n; s++ {
1684 for p = 0; p < np; p++ {
1685 ch = prd[p] - NTBASE
1689 changes |= setunion(pfirst[i], pfirst[ch])
1690 if pempty[ch] == 0 {
1702 for i = 0; i <= nnonter; i++ {
1703 fmt.Fprintf(foutput, "\n%v: %v %v\n",
1704 nontrst[i].name, pfirst[i], pempty[i])
1710 // generate the states
1715 tstates = make([]int, ntokens+1) // states generated by terminal gotos
1716 ntstates = make([]int, nnonter+1) // states generated by nonterminal gotos
1717 amem = make([]int, ACTSIZE)
1723 aryfil(clset, tbitset, 0)
1724 putitem(Pitem{prdptr[0], 0, 0, 0}, clset)
1727 pstate[2] = pstate[1]
1730 // now, the main state generation loop
1731 // first pass generates all of the states
1732 // later passes fix up lookahead
1733 // could be sped up a lot by remembering
1734 // results of the first pass rather than recomputing
1737 for more := 1; more != 0; first = 0 {
1739 for i := 0; i < nstate; i++ {
1740 if tystate[i] != MUSTDO {
1745 aryfil(temp1, nnonter+1, 0)
1747 // take state i, close it, and do gotos
1751 for p := 0; p < cwp; p++ {
1759 if pstate[i+1]-pstate[i] <= p {
1760 tystate[i] = MUSTLOOKAHEAD
1766 putitem(wsets[p].pitem, wsets[p].ws)
1767 for q := p + 1; q < cwp; q++ {
1768 // this item contributes to the goto
1769 if c == wsets[q].pitem.first {
1770 putitem(wsets[q].pitem, wsets[q].ws)
1776 state(c) // register new state
1778 temp1[c-NTBASE] = state(c)
1782 if gsdebug != 0 && foutput != nil {
1783 fmt.Fprintf(foutput, "%v: ", i)
1784 for j := 0; j <= nnonter; j++ {
1786 fmt.Fprintf(foutput, "%v %v,", nontrst[j].name, temp1[j])
1789 fmt.Fprintf(foutput, "\n")
1793 indgo[i] = apack(temp1[1:], nnonter-1) - 1
1802 // generate the closure of state i
1804 func closure(i int) {
1807 // first, copy kernel of state i to wsets
1810 for p := pstate[i]; p < q; p++ {
1811 wsets[cwp].pitem = statemem[p].pitem
1812 wsets[cwp].flag = 1 // this item must get closed
1813 copy(wsets[cwp].ws, statemem[p].look)
1817 // now, go through the loop, closing each item
1821 for u := 0; u < cwp; u++ {
1822 if wsets[u].flag == 0 {
1827 c := wsets[u].pitem.first
1830 // only interesting case is where . is before nonterminal
1834 // compute the lookahead
1835 aryfil(clset, tbitset, 0)
1837 // find items involving c
1838 for v := u; v < cwp; v++ {
1839 if wsets[v].flag != 1 || wsets[v].pitem.first != c {
1842 pi := wsets[v].pitem.prod
1843 ipi := wsets[v].pitem.off + 1
1859 // nonterminal symbol
1860 setunion(clset, pfirst[ch-NTBASE])
1861 if pempty[ch-NTBASE] == 0 {
1868 setunion(clset, wsets[v].ws)
1873 // now loop over productions derived from c
1875 curres := pres[c-NTBASE]
1879 // initially fill the sets
1880 for s := 0; s < n; s++ {
1884 // put these items into the closure
1885 // is the item there
1887 for v := 0; v < cwp; v++ {
1889 if wsets[v].pitem.off == 0 &&
1890 aryeq(wsets[v].pitem.prod, prd) != 0 {
1892 setunion(wsets[v].ws, clset) != 0 {
1900 // not there; make a new entry
1901 if cwp >= len(wsets) {
1902 awsets := make([]Wset, cwp+WSETINC)
1906 wsets[cwp].pitem = Pitem{prd, 0, prd[0], -prd[len(prd)-1]}
1908 wsets[cwp].ws = mkset()
1911 copy(wsets[cwp].ws, clset)
1918 // have computed closure; flags are reset; return
1919 if cldebug != 0 && foutput != nil {
1920 fmt.Fprintf(foutput, "\nState %v, nolook = %v\n", i, nolook)
1921 for u := 0; u < cwp; u++ {
1922 if wsets[u].flag != 0 {
1923 fmt.Fprintf(foutput, "flag set\n")
1926 fmt.Fprintf(foutput, "\t%v", writem(wsets[u].pitem))
1928 fmt.Fprintf(foutput, "\n")
1934 // sorts last state,and sees if it equals earlier ones. returns state number
1936 func state(c int) int {
1938 p1 := pstate[nstate]
1939 p2 := pstate[nstate+1]
1941 return 0 // null state
1946 for k = p1 + 1; k < p2; k++ { // make k the biggest
1947 for l = k; l > p1; l-- {
1948 if statemem[l].pitem.prodno < statemem[l-1].pitem.prodno ||
1949 statemem[l].pitem.prodno == statemem[l-1].pitem.prodno &&
1950 statemem[l].pitem.off < statemem[l-1].pitem.off {
1952 statemem[l] = statemem[l-1]
1960 size1 := p2 - p1 // size of state
1964 i = ntstates[c-NTBASE]
1970 for ; i != 0; i = mstates[i] {
1979 for l = q1; l < q2; l++ {
1980 if aryeq(statemem[l].pitem.prod, statemem[k].pitem.prod) == 0 ||
1981 statemem[l].pitem.off != statemem[k].pitem.off {
1988 pstate[nstate+1] = pstate[nstate] // delete last state
1990 // fix up lookaheads
1995 for l = q1; l < q2; l++ {
1996 if setunion(statemem[l].look, statemem[k].look) != 0 {
2007 errorf("yacc state/nolook error")
2009 pstate[nstate+2] = p2
2010 if nstate+1 >= NSTATES {
2011 errorf("too many states")
2014 mstates[nstate] = ntstates[c-NTBASE]
2015 ntstates[c-NTBASE] = nstate
2017 mstates[nstate] = tstates[c]
2020 tystate[nstate] = MUSTDO
2025 func putitem(p Pitem, set Lkset) {
2027 p.first = p.prod[p.off]
2029 if pidebug != 0 && foutput != nil {
2030 fmt.Fprintf(foutput, "putitem(%v), state %v\n", writem(p), nstate)
2032 j := pstate[nstate+1]
2033 if j >= len(statemem) {
2034 asm := make([]Item, j+STATEINC)
2038 statemem[j].pitem = p
2042 statemem[j].look = s
2045 pstate[nstate+1] = j
2049 // creates output string for item pointed to by pp
2051 func writem(pp Pitem) string {
2055 q := chcopy(nontrst[prdptr[pp.prodno][0]-NTBASE].name) + ": "
2058 pi := aryeq(p, prdptr[pp.prodno])
2072 q += chcopy(symnam(i))
2075 // an item calling for a reduction
2078 q += fmt.Sprintf(" (%v)", -i)
2085 // pack state i from temp1 into amem
2087 func apack(p []int, n int) int {
2089 // we don't need to worry about checking because
2090 // we will only look at entries known to be there...
2091 // eliminate leading and trailing 0's
2095 for ; pp <= n && p[pp] == 0; pp++ {
2103 for ; n > pp && p[n] == 0; n-- {
2107 // now, find a place for the elements from p to q, inclusive
2108 r := len(amem) - len(p)
2111 for rr := 0; rr <= r; rr++ {
2113 for pp = 0; pp < len(p); pp++ {
2115 if p[pp] != amem[qq] && amem[qq] != 0 {
2122 // we have found an acceptable k
2123 if pkdebug != 0 && foutput != nil {
2124 fmt.Fprintf(foutput, "off = %v, k = %v\n", off+rr, rr)
2127 for pp = 0; pp < len(p); pp++ {
2136 if pkdebug != 0 && foutput != nil {
2137 for pp = 0; pp <= memp; pp += 10 {
2138 fmt.Fprintf(foutput, "\n")
2139 for qq = pp; qq <= pp+9; qq++ {
2140 fmt.Fprintf(foutput, "%v ", amem[qq])
2142 fmt.Fprintf(foutput, "\n")
2147 errorf("no space in action table")
2152 // print the output for the states
2158 fmt.Fprintf(ftable, "\n//line yacctab:1")
2160 fmt.Fprintf(ftable, "\nvar %sExca = [...]int{\n", prefix)
2162 if len(errors) > 0 {
2163 stateTable = make([]Row, nstate)
2168 // output the stuff for state i
2169 for i := 0; i < nstate; i++ {
2171 if tystate[i] != MUSTLOOKAHEAD {
2178 aryfil(temp1, ntokens+nnonter+1, 0)
2179 for u = 0; u < cwp; u++ {
2180 c = wsets[u].pitem.first
2181 if c > 1 && c < NTBASE && temp1[c] == 0 {
2182 for v = u; v < cwp; v++ {
2183 if c == wsets[v].pitem.first {
2184 putitem(wsets[v].pitem, noset)
2188 } else if c > NTBASE {
2190 if temp1[c+ntokens] == 0 {
2191 temp1[c+ntokens] = amem[indgo[i]+c]
2196 temp1[1] = ACCEPTCODE
2199 // now, we have the shifts; look at the reductions
2201 for u = 0; u < cwp; u++ {
2202 c = wsets[u].pitem.first
2210 for k := 0; k <= ntokens; k++ {
2211 if bitset(us, k) == 0 {
2216 } else if temp1[k] < 0 { // reduce/reduce conflict
2218 fmt.Fprintf(foutput,
2219 "\n %v: reduce/reduce conflict (red'ns "+
2221 i, -temp1[k], lastred, symnam(k))
2223 if -temp1[k] > lastred {
2228 // potential shift/reduce conflict
2229 precftn(lastred, k, i)
2236 fmt.Fprintf(ftable, "}\n")
2237 ftable.WriteRune('\n')
2238 fmt.Fprintf(ftable, "const %sPrivate = %v\n", prefix, PRIVATE)
2242 // decide a shift/reduce conflict by precedence.
2243 // r is a rule number, t a token number
2244 // the conflict is in state s
2245 // temp1[t] is changed to reflect the action
2247 func precftn(r, t, s int) {
2252 if PLEVEL(lt) == 0 || PLEVEL(lp) == 0 {
2255 fmt.Fprintf(foutput,
2256 "\n%v: shift/reduce conflict (shift %v(%v), red'n %v(%v)) on %v",
2257 s, temp1[t], PLEVEL(lt), r, PLEVEL(lp), symnam(t))
2262 if PLEVEL(lt) == PLEVEL(lp) {
2264 } else if PLEVEL(lt) > PLEVEL(lp) {
2265 action = RASC // shift
2270 case BASC: // error action
2272 case LASC: // reduce
2279 // temp1 has the actions, lastred the default
2284 // find the best choice for lastred
2287 for j := 0; j <= ntokens; j++ {
2291 if temp1[j]+lastred == 0 {
2294 // count the number of appearances of temp1[j]
2297 levprd[tred] |= REDFLAG
2298 for p = 0; p <= ntokens; p++ {
2299 if temp1[p]+tred == 0 {
2310 // for error recovery, arrange that, if there is a shift on the
2311 // error recovery token, `error', that the default be the error action
2317 // clear out entries in temp1 which equal lastred
2318 // count entries in optst table
2320 for p = 0; p <= ntokens; p++ {
2322 if p1+lastred == 0 {
2326 if p1 > 0 && p1 != ACCEPTCODE && p1 != ERRCODE {
2334 os := make([]int, n*2)
2336 for p = 0; p <= ntokens; p++ {
2341 } else if p1 == ACCEPTCODE {
2343 } else if p1 == ERRCODE {
2354 fmt.Fprintf(ftable, "\t-1, %v,\n", i)
2357 fmt.Fprintf(ftable, "\t%v, %v,\n", p, p1)
2363 fmt.Fprintf(ftable, "\t-2, %v,\n", lastred)
2371 func wrstate(i int) {
2375 if len(errors) > 0 {
2376 actions := append([]int(nil), temp1...)
2377 defaultAction := ERRCODE
2379 defaultAction = -lastred
2381 stateTable[i] = Row{actions, defaultAction}
2387 fmt.Fprintf(foutput, "\nstate %v\n", i)
2389 for pp = pstate[i]; pp < qq; pp++ {
2390 fmt.Fprintf(foutput, "\t%v\n", writem(statemem[pp].pitem))
2392 if tystate[i] == MUSTLOOKAHEAD {
2393 // print out empty productions in closure
2394 for u = pstate[i+1] - pstate[i]; u < cwp; u++ {
2395 if wsets[u].pitem.first < 0 {
2396 fmt.Fprintf(foutput, "\t%v\n", writem(wsets[u].pitem))
2401 // check for state equal to another
2402 for j0 = 0; j0 <= ntokens; j0++ {
2405 fmt.Fprintf(foutput, "\n\t%v ", symnam(j0))
2407 // shift, error, or accept
2409 if j1 == ACCEPTCODE {
2410 fmt.Fprintf(foutput, "accept")
2411 } else if j1 == ERRCODE {
2412 fmt.Fprintf(foutput, "error")
2414 fmt.Fprintf(foutput, "shift %v", j1)
2417 fmt.Fprintf(foutput, "reduce %v (src line %v)", -j1, rlines[-j1])
2422 // output the final production
2424 fmt.Fprintf(foutput, "\n\t. reduce %v (src line %v)\n\n",
2425 lastred, rlines[lastred])
2427 fmt.Fprintf(foutput, "\n\t. error\n\n")
2430 // now, output nonterminal actions
2432 for j0 = 1; j0 <= nnonter; j0++ {
2435 fmt.Fprintf(foutput, "\t%v goto %v\n", symnam(j0+NTBASE), temp1[j1])
2441 // output the gotos for the nontermninals
2444 for i := 1; i <= nnonter; i++ {
2447 // find the best one to make default
2451 // is j the most frequent
2452 for j := 0; j < nstate; j++ {
2453 if tystate[j] == 0 {
2456 if tystate[j] == best {
2460 // is tystate[j] the most frequent
2463 for k := j; k < nstate; k++ {
2464 if tystate[k] == cbest {
2474 // best is now the default entry
2475 zzgobest += times - 1
2477 for j := 0; j < nstate; j++ {
2478 if tystate[j] != 0 && tystate[j] != best {
2482 goent := make([]int, 2*n+1)
2484 for j := 0; j < nstate; j++ {
2485 if tystate[j] != 0 && tystate[j] != best {
2488 goent[n] = tystate[j]
2506 // output the gotos for nonterminal c
2508 func go2gen(c int) {
2511 // first, find nonterminals with gotos on c
2512 aryfil(temp1, nnonter+1, 0)
2517 for i = 0; i < nprod; i++ {
2518 // cc is a nonterminal with a goto on c
2519 cc = prdptr[i][1] - NTBASE
2520 if cc >= 0 && temp1[cc] != 0 {
2521 // thus, the left side of production i does too
2522 cc = prdptr[i][0] - NTBASE
2531 // now, we have temp1[c] = 1 if a goto on c in closure of cc
2532 if g2debug != 0 && foutput != nil {
2533 fmt.Fprintf(foutput, "%v: gotos on ", nontrst[c].name)
2534 for i = 0; i <= nnonter; i++ {
2536 fmt.Fprintf(foutput, "%v ", nontrst[i].name)
2539 fmt.Fprintf(foutput, "\n")
2542 // now, go through and put gotos into tystate
2543 aryfil(tystate, nstate, 0)
2544 for i = 0; i < nstate; i++ {
2546 for p = pstate[i]; p < q; p++ {
2547 cc = statemem[p].pitem.first
2549 // goto on c is possible
2550 if temp1[cc-NTBASE] != 0 {
2551 tystate[i] = amem[indgo[i]+c]
2560 // in order to free up the mem and amem arrays for the optimizer,
2561 // and still be able to output yyr1, etc., after the sizes of
2562 // the action array is known, we hide the nonterminals
2563 // derived by productions in levprd.
2568 for i := 1; i < nprod; i++ {
2569 if (levprd[i] & REDFLAG) == 0 {
2571 fmt.Fprintf(foutput, "Rule not reduced: %v\n",
2572 writem(Pitem{prdptr[i], 0, 0, i}))
2574 fmt.Printf("rule %v never reduced\n", writem(Pitem{prdptr[i], 0, 0, i}))
2577 levprd[i] = prdptr[i][0] - NTBASE
2580 fmt.Printf("%v rules never reduced\n", nred)
2585 var j, k, p, q, i int
2588 pgo = make([]int, nnonter+1)
2592 for i = 0; i < nstate; i++ {
2597 for p = 0; p < q; p += 2 {
2606 // nontrivial situation
2608 // j is now the range
2609 // j -= k; // call scj
2614 tystate[i] = q + 2*j
2620 // initialize ggreed table
2621 ggreed = make([]int, nnonter+1)
2622 for i = 1; i <= nnonter; i++ {
2626 // minimum entry index is always 0
2629 for p = 0; p < q; p += 2 {
2635 ggreed[i] = ggreed[i] + 2*j
2641 // now, prepare to put the shift actions into the amem array
2642 for i = 0; i < ACTSIZE; i++ {
2646 for i = 0; i < nstate; i++ {
2647 if tystate[i] == 0 && adb > 1 {
2648 fmt.Fprintf(ftable, "State %v: null\n", i)
2665 for p = 0; p <= maxa; p += 10 {
2666 fmt.Fprintf(ftable, "%v ", p)
2667 for i = 0; i < 10; i++ {
2668 fmt.Fprintf(ftable, "%v ", amem[p+i])
2670 ftable.WriteRune('\n')
2684 for i := 1; i <= nnonter; i++ {
2685 if ggreed[i] >= max {
2690 for i := 0; i < nstate; i++ {
2691 if tystate[i] >= max {
2705 // enter gotos on nonterminal i into array amem
2711 // now, find amem place for it
2713 for p := 0; p < ACTSIZE; p++ {
2717 for r := 0; r < nq; r += 2 {
2721 if maxa >= ACTSIZE {
2722 errorf("a array overflow")
2730 // we have found amem spot
2735 for r := 0; r < nq; r += 2 {
2741 fmt.Fprintf(ftable, "Nonterminal %v, entry at %v\n", i, pgo[i])
2745 errorf("cannot place goto %v\n", i)
2753 // enter state i into the amem array
2758 // find an acceptable place
2759 for n := -maxoff; n < ACTSIZE; n++ {
2761 for r := 0; r < nq; r += 2 {
2763 if s < 0 || s > ACTSIZE {
2768 } else if amem[s] != q[r+1] {
2773 // check the position equals another only if the states are identical
2774 for j := 0; j < nstate; j++ {
2777 // we have some disagreement
2781 if nq == len(optst[j]) {
2786 fmt.Fprintf(ftable, "State %v: entry at"+
2787 "%v equals state %v\n",
2793 // we have some disagreement
2798 for r := 0; r < nq; r += 2 {
2803 if amem[s] != 0 && amem[s] != q[r+1] {
2804 errorf("clobber of a array, pos'n %v, by %v", s, q[r+1])
2810 fmt.Fprintf(ftable, "State %v: entry at %v\n", i, indgo[i])
2814 errorf("Error; failure to place state %v", i)
2818 // this version is for limbo
2819 // write out the optimized parser
2822 ftable.WriteRune('\n')
2823 fmt.Fprintf(ftable, "const %sLast = %v\n", prefix, maxa+1)
2824 arout("Act", amem, maxa+1)
2825 arout("Pact", indgo, nstate)
2826 arout("Pgo", pgo, nnonter+1)
2830 // put out other arrays, copy the parsers
2835 arout("R1", levprd, nprod)
2836 aryfil(temp1, nprod, 0)
2839 //yyr2 is the number of rules for each production
2841 for i = 1; i < nprod; i++ {
2842 temp1[i] = len(prdptr[i]) - 2
2844 arout("R2", temp1, nprod)
2846 aryfil(temp1, nstate, -1000)
2847 for i = 0; i <= ntokens; i++ {
2848 for j := tstates[i]; j != 0; j = mstates[j] {
2852 for i = 0; i <= nnonter; i++ {
2853 for j = ntstates[i]; j != 0; j = mstates[j] {
2857 arout("Chk", temp1, nstate)
2858 arout("Def", defact, nstate)
2860 // put out token translation tables
2861 // table 1 has 0-256
2862 aryfil(temp1, 256, 0)
2864 for i = 1; i <= ntokens; i++ {
2866 if j >= 0 && j < 256 {
2868 fmt.Print("yacc bug -- cannot have 2 different Ts with same value\n")
2869 fmt.Printf(" %s and %s\n", tokset[i].name, tokset[temp1[j]].name)
2878 for i = 0; i <= c; i++ {
2883 arout("Tok1", temp1, c+1)
2885 // table 2 has PRIVATE-PRIVATE+256
2886 aryfil(temp1, 256, 0)
2888 for i = 1; i <= ntokens; i++ {
2889 j = tokset[i].value - PRIVATE
2890 if j >= 0 && j < 256 {
2892 fmt.Print("yacc bug -- cannot have 2 different Ts with same value\n")
2893 fmt.Printf(" %s and %s\n", tokset[i].name, tokset[temp1[j]].name)
2902 arout("Tok2", temp1, c+1)
2904 // table 3 has everything else
2905 ftable.WriteRune('\n')
2906 fmt.Fprintf(ftable, "var %sTok3 = [...]int{\n\t", prefix)
2908 for i = 1; i <= ntokens; i++ {
2910 if j >= 0 && j < 256 {
2913 if j >= PRIVATE && j < 256+PRIVATE {
2918 ftable.WriteRune(' ')
2920 fmt.Fprintf(ftable, "%d, %d,", j, i)
2923 fmt.Fprint(ftable, "\n\t")
2927 ftable.WriteRune(' ')
2929 fmt.Fprintf(ftable, "%d,\n}\n", 0)
2931 // Custom error messages.
2932 fmt.Fprintf(ftable, "\n")
2933 fmt.Fprintf(ftable, "var %sErrorMessages = [...]struct {\n", prefix)
2934 fmt.Fprintf(ftable, "\tstate int\n")
2935 fmt.Fprintf(ftable, "\ttoken int\n")
2936 fmt.Fprintf(ftable, "\tmsg string\n")
2937 fmt.Fprintf(ftable, "}{\n")
2938 for _, error := range errors {
2939 lineno = error.lineno
2940 state, token := runMachine(error.tokens)
2941 fmt.Fprintf(ftable, "\t{%v, %v, %s},\n", state, token, error.msg)
2943 fmt.Fprintf(ftable, "}\n")
2946 ch := getrune(finput)
2948 ftable.WriteRune(ch)
2949 ch = getrune(finput)
2954 fmt.Fprintf(ftable, "\n//line yaccpar:1\n")
2957 parts := strings.SplitN(yaccpar, prefix+"run()", 2)
2958 fmt.Fprintf(ftable, "%v", parts[0])
2959 ftable.Write(fcode.Bytes())
2960 fmt.Fprintf(ftable, "%v", parts[1])
2963 func runMachine(tokens []string) (state, token int) {
2970 token = chfind(2, tokens[i])
2974 row := stateTable[state]
2977 if token >= NTBASE {
2978 c = token - NTBASE + ntokens
2980 action := row.actions[c]
2982 action = row.defaultAction
2986 case action == ACCEPTCODE:
2987 errorf("tokens are accepted")
2989 case action == ERRCODE:
2990 if token >= NTBASE {
2991 errorf("error at non-terminal token %s", symnam(token))
2995 // Shift to state action.
2996 stack = append(stack, state)
3001 // Reduce by production -action.
3002 prod := prdptr[-action]
3003 if rhsLen := len(prod) - 2; rhsLen > 0 {
3004 n := len(stack) - rhsLen
3016 func arout(s string, v []int, n int) {
3018 ftable.WriteRune('\n')
3019 fmt.Fprintf(ftable, "var %v = [...]int{", s)
3020 for i := 0; i < n; i++ {
3022 fmt.Fprintf(ftable, "\n\t")
3024 ftable.WriteRune(' ')
3026 fmt.Fprintf(ftable, "%d,", v[i])
3028 fmt.Fprintf(ftable, "\n}\n")
3032 // output the summary on y.output
3036 fmt.Fprintf(foutput, "\n%v terminals, %v nonterminals\n", ntokens, nnonter+1)
3037 fmt.Fprintf(foutput, "%v grammar rules, %v/%v states\n", nprod, nstate, NSTATES)
3038 fmt.Fprintf(foutput, "%v shift/reduce, %v reduce/reduce conflicts reported\n", zzsrconf, zzrrconf)
3039 fmt.Fprintf(foutput, "%v working sets used\n", len(wsets))
3040 fmt.Fprintf(foutput, "memory: parser %v/%v\n", memp, ACTSIZE)
3041 fmt.Fprintf(foutput, "%v extra closures\n", zzclose-2*nstate)
3042 fmt.Fprintf(foutput, "%v shift entries, %v exceptions\n", zzacent, zzexcp)
3043 fmt.Fprintf(foutput, "%v goto entries\n", zzgoent)
3044 fmt.Fprintf(foutput, "%v entries saved by goto default\n", zzgobest)
3046 if zzsrconf != 0 || zzrrconf != 0 {
3047 fmt.Printf("\nconflicts: ")
3049 fmt.Printf("%v shift/reduce", zzsrconf)
3051 if zzsrconf != 0 && zzrrconf != 0 {
3055 fmt.Printf("%v reduce/reduce", zzrrconf)
3062 // write optimizer summary
3069 for p := maxa; p >= 0; p-- {
3075 fmt.Fprintf(foutput, "Optimizer space used: output %v/%v\n", maxa+1, ACTSIZE)
3076 fmt.Fprintf(foutput, "%v table entries, %v zero\n", maxa+1, i)
3077 fmt.Fprintf(foutput, "maximum spread: %v, maximum offset: %v\n", maxspr, maxoff)
3081 // copies and protects "'s in q
3083 func chcopy(q string) string {
3087 for i = 0; i < len(q); i++ {
3097 fmt.Fprintf(stderr, "usage: yacc [-o output] [-v parsetable] input\n")
3101 func bitset(set Lkset, bit int) int { return set[bit>>5] & (1 << uint(bit&31)) }
3103 func setbit(set Lkset, bit int) { set[bit>>5] |= (1 << uint(bit&31)) }
3105 func mkset() Lkset { return make([]int, tbitset) }
3108 // set a to the union of a and b
3109 // return 1 if b is not a subset of a, 0 otherwise
3111 func setunion(a, b []int) int {
3113 for i := 0; i < tbitset; i++ {
3124 func prlook(p Lkset) {
3126 fmt.Fprintf(foutput, "\tNULL")
3129 fmt.Fprintf(foutput, " { ")
3130 for j := 0; j <= ntokens; j++ {
3131 if bitset(p, j) != 0 {
3132 fmt.Fprintf(foutput, "%v ", symnam(j))
3135 fmt.Fprintf(foutput, "}")
3143 func isdigit(c rune) bool { return c >= '0' && c <= '9' }
3145 func isword(c rune) bool {
3146 return c >= 0xa0 || c == '_' || (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')
3150 // return 1 if 2 arrays are equal
3151 // return 0 if not equal
3153 func aryeq(a []int, b []int) int {
3158 for ll := 0; ll < n; ll++ {
3166 func getrune(f *bufio.Reader) rune {
3170 if peekrune == EOF {
3178 c, n, err := f.ReadRune()
3183 errorf("read error: %v", err)
3185 //fmt.Printf("rune = %v n=%v\n", string(c), n);
3189 func ungetrune(f *bufio.Reader, c rune) {
3191 panic("ungetc - not finput")
3194 panic("ungetc - 2nd unget")
3199 func open(s string) *bufio.Reader {
3200 fi, err := os.Open(s)
3202 errorf("error opening %v: %v", s, err)
3204 //fmt.Printf("open %v\n", s);
3205 return bufio.NewReader(fi)
3208 func create(s string) *bufio.Writer {
3209 fo, err := os.Create(s)
3211 errorf("error creating %v: %v", s, err)
3213 //fmt.Printf("create %v mode %v\n", s);
3214 return bufio.NewWriter(fo)
3218 // write out error comment
3220 func lerrorf(lineno int, s string, v ...interface{}) {
3222 fmt.Fprintf(stderr, s, v...)
3223 fmt.Fprintf(stderr, ": %v:%v\n", infile, lineno)
3230 func errorf(s string, v ...interface{}) {
3231 lerrorf(lineno, s, v...)
3234 func exit(status int) {
3252 src, err := ioutil.ReadFile(oflag)
3256 src, err = format.Source(src)
3260 ioutil.WriteFile(oflag, src, 0666)
3263 var yaccpar string // will be processed version of yaccpartext: s/$$/prefix/g
3265 /* parser for yacc output */
3269 $$ErrorVerbose = false
3272 type $$Lexer interface {
3273 Lex(lval *$$SymType) int
3277 type $$Parser interface {
3282 type $$ParserImpl struct {
3284 stack [$$InitialStackSize]$$SymType
3288 func (p *$$ParserImpl) Lookahead() int {
3292 func $$NewParser() $$Parser {
3293 return &$$ParserImpl{}
3296 const $$Flag = -1000
3298 func $$Tokname(c int) string {
3299 if c >= 1 && c-1 < len($$Toknames) {
3300 if $$Toknames[c-1] != "" {
3301 return $$Toknames[c-1]
3304 return __yyfmt__.Sprintf("tok-%v", c)
3307 func $$Statname(s int) string {
3308 if s >= 0 && s < len($$Statenames) {
3309 if $$Statenames[s] != "" {
3310 return $$Statenames[s]
3313 return __yyfmt__.Sprintf("state-%v", s)
3316 func $$ErrorMessage(state, lookAhead int) string {
3319 if !$$ErrorVerbose {
3320 return "syntax error"
3323 for _, e := range $$ErrorMessages {
3324 if e.state == state && e.token == lookAhead {
3325 return "syntax error: " + e.msg
3329 res := "syntax error: unexpected " + $$Tokname(lookAhead)
3331 // To match Bison, suggest at most four expected tokens.
3332 expected := make([]int, 0, 4)
3334 // Look for shiftable tokens.
3335 base := $$Pact[state]
3336 for tok := TOKSTART; tok-1 < len($$Toknames); tok++ {
3337 if n := base + tok; n >= 0 && n < $$Last && $$Chk[$$Act[n]] == tok {
3338 if len(expected) == cap(expected) {
3341 expected = append(expected, tok)
3345 if $$Def[state] == -2 {
3347 for $$Exca[i] != -1 || $$Exca[i+1] != state {
3351 // Look for tokens that we accept or reduce.
3352 for i += 2; $$Exca[i] >= 0; i += 2 {
3354 if tok < TOKSTART || $$Exca[i+1] == 0 {
3357 if len(expected) == cap(expected) {
3360 expected = append(expected, tok)
3363 // If the default action is to accept or reduce, give up.
3364 if $$Exca[i+1] != 0 {
3369 for i, tok := range expected {
3371 res += ", expecting "
3375 res += $$Tokname(tok)
3380 func $$lex1(lex $$Lexer, lval *$$SymType) (char, token int) {
3382 char = lex.Lex(lval)
3387 if char < len($$Tok1) {
3388 token = $$Tok1[char]
3391 if char >= $$Private {
3392 if char < $$Private+len($$Tok2) {
3393 token = $$Tok2[char-$$Private]
3397 for i := 0; i < len($$Tok3); i += 2 {
3407 token = $$Tok2[1] /* unknown char */
3410 __yyfmt__.Printf("lex %s(%d)\n", $$Tokname(token), uint(char))
3415 func $$Parse($$lex $$Lexer) int {
3416 return $$NewParser().Parse($$lex)
3419 func ($$rcvr *$$ParserImpl) Parse($$lex $$Lexer) int {
3422 var $$Dollar []$$SymType
3423 _ = $$Dollar // silence set and not used
3424 $$S := $$rcvr.stack[:]
3426 Nerrs := 0 /* number of errors */
3427 Errflag := 0 /* error recovery flag */
3430 $$token := -1 // $$rcvr.char translated into internal numbering
3432 // Make sure we report no lookahead when not parsing.
3447 /* put a state and value onto the stack */
3449 __yyfmt__.Printf("char %v in %v\n", $$Tokname($$token), $$Statname($$state))
3453 if $$p >= len($$S) {
3454 nyys := make([]$$SymType, len($$S)*2)
3459 $$S[$$p].yys = $$state
3462 $$n = $$Pact[$$state]
3464 goto $$default /* simple state */
3466 if $$rcvr.char < 0 {
3467 $$rcvr.char, $$token = $$lex1($$lex, &$$rcvr.lval)
3470 if $$n < 0 || $$n >= $$Last {
3474 if $$Chk[$$n] == $$token { /* valid shift */
3486 /* default state action */
3487 $$n = $$Def[$$state]
3489 if $$rcvr.char < 0 {
3490 $$rcvr.char, $$token = $$lex1($$lex, &$$rcvr.lval)
3493 /* look through exception table */
3496 if $$Exca[xi+0] == -1 && $$Exca[xi+1] == $$state {
3501 for xi += 2; ; xi += 2 {
3503 if $$n < 0 || $$n == $$token {
3513 /* error ... attempt to resume parsing */
3515 case 0: /* brand new error */
3516 $$lex.Error($$ErrorMessage($$state, $$token))
3519 __yyfmt__.Printf("%s", $$Statname($$state))
3520 __yyfmt__.Printf(" saw %s\n", $$Tokname($$token))
3524 case 1, 2: /* incompletely recovered error ... try again */
3527 /* find a state where "error" is a legal shift action */
3529 $$n = $$Pact[$$S[$$p].yys] + $$ErrCode
3530 if $$n >= 0 && $$n < $$Last {
3531 $$state = $$Act[$$n] /* simulate a shift of "error" */
3532 if $$Chk[$$state] == $$ErrCode {
3537 /* the current p has no shift on "error", pop stack */
3539 __yyfmt__.Printf("error recovery pops state %d\n", $$S[$$p].yys)
3543 /* there is no state on the stack with an error shift ... abort */
3546 case 3: /* no shift yet; clobber input char */
3548 __yyfmt__.Printf("error recovery discards %s\n", $$Tokname($$token))
3550 if $$token == $$EofCode {
3555 goto $$newstate /* try again in the same state */
3559 /* reduction by production $$n */
3561 __yyfmt__.Printf("reduce %v in:\n\t%v\n", $$n, $$Statname($$state))
3566 _ = $$pt // guard against "declared and not used"
3569 // $$p is now the index of $0. Perform the default action. Iff the
3570 // reduced production is ε, $1 is possibly out of range.
3571 if $$p+1 >= len($$S) {
3572 nyys := make([]$$SymType, len($$S)*2)
3578 /* consult goto table to find next state */
3581 $$j := $$g + $$S[$$p].yys + 1
3584 $$state = $$Act[$$g]
3586 $$state = $$Act[$$j]
3587 if $$Chk[$$state] != -$$n {
3588 $$state = $$Act[$$g]
3591 // dummy call; replaced with literal code
3593 goto $$stack /* stack new state and value */