gopls/cmd/goyacc/yacc.go

1	/*
2	Derived from Inferno's utils/iyacc/yacc.c
3	http://code.google.com/p/inferno-os/source/browse/utils/iyacc/yacc.c
4
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.
12
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.
21
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:
28
29	The above copyright notice and this permission notice shall be included in
30	all copies or substantial portions of the Software.
31
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
38	THE SOFTWARE.
39	*/
40
41	package main
42
43	// yacc
44	// major difference is lack of stem ("y" variable)
45	//
46
47	import (
48	"bufio"
49	"bytes"
50	"flag"
51	"fmt"
52	"go/format"
53	"io/ioutil"
54	"math"
55	"os"
56	"strconv"
57	"strings"
58	"unicode"
59	)
60
61	// the following are adjustable
62	// according to memory size
63	const (
64	ACTSIZE = 240000
65	NSTATES = 16000
66	TEMPSIZE = 16000
67
68	SYMINC = 50 // increase for non-term or term
69	RULEINC = 50 // increase for max rule length prodptr[i]
70	PRODINC = 100 // increase for productions prodptr
71	WSETINC = 50 // increase for working sets wsets
72	STATEINC = 200 // increase for states statemem
73
74	PRIVATE = 0xE000 // unicode private use
75
76	// relationships which must hold:
77	// TEMPSIZE >= NTERMS + NNONTERM + 1;
78	// TEMPSIZE >= NSTATES;
79	//
80
81	NTBASE = 010000
82	ERRCODE = 8190
83	ACCEPTCODE = 8191
84	YYLEXUNK = 3
85	TOKSTART = 4 //index of first defined token
86	)
87
88	// no, left, right, binary assoc.
89	const (
90	NOASC = iota
91	LASC
92	RASC
93	BASC
94	)
95
96	// flags for state generation
97	const (
98	DONE = iota
99	MUSTDO
100	MUSTLOOKAHEAD
101	)
102
103	// flags for a rule having an action, and being reduced
104	const (
105	ACTFLAG = 1 << (iota + 2)
106	REDFLAG
107	)
108
109	// output parser flags
110	const yyFlag = -1000
111
112	// parse tokens
113	const (
114	IDENTIFIER = PRIVATE + iota
115	MARK
116	TERM
117	LEFT
118	RIGHT
119	BINARY
120	PREC
121	LCURLY
122	IDENTCOLON
123	NUMBER
124	START
125	TYPEDEF
126	TYPENAME
127	UNION
128	ERROR
129	)
130
131	const ENDFILE = 0
132	const EMPTY = 1
133	const WHOKNOWS = 0
134	const OK = 1
135	const NOMORE = -1000
136
137	// macros for getting associativity and precedence levels
138	func ASSOC(i int) int { return i & 3 }
139
140	func PLEVEL(i int) int { return (i >> 4) & 077 }
141
142	func TYPE(i int) int { return (i >> 10) & 077 }
143
144	// macros for setting associativity and precedence levels
145	func SETASC(i, j int) int { return i \| j }
146
147	func SETPLEV(i, j int) int { return i \| (j << 4) }
148
149	func SETTYPE(i, j int) int { return i \| (j << 10) }
150
151	// I/O descriptors
152	var finput *bufio.Reader // input file
153	var stderr *bufio.Writer
154	var ftable *bufio.Writer // y.go file
155	var fcode = &bytes.Buffer{} // saved code
156	var foutput *bufio.Writer // y.output file
157
158	var fmtImported bool // output file has recorded an import of "fmt"
159
160	var oflag string // -o [y.go] - y.go file
161	var vflag string // -v [y.output] - y.output file
162	var lflag bool // -l - disable line directives
163	var prefix string // name prefix for identifiers, default yy
164
165	func init() {
166	flag.StringVar(&oflag, "o", "y.go", "parser output")
167	flag.StringVar(&prefix, "p", "yy", "name prefix to use in generated code")
168	flag.StringVar(&vflag, "v", "y.output", "create parsing tables")
169	flag.BoolVar(&lflag, "l", false, "disable line directives")
170	}
171
172	var initialstacksize = 16
173
174	// communication variables between various I/O routines
175	var infile string // input file name
176	var numbval int // value of an input number
177	var tokname string // input token name, slop for runes and 0
178	var tokflag = false
179
180	// structure declarations
181	type Lkset []int
182
183	type Pitem struct {
184	prod []int
185	off int // offset within the production
186	first int // first term or non-term in item
187	prodno int // production number for sorting
188	}
189
190	type Item struct {
191	pitem Pitem
192	look Lkset
193	}
194
195	type Symb struct {
196	name string
197	noconst bool
198	value int
199	}
200
201	type Wset struct {
202	pitem Pitem
203	flag int
204	ws Lkset
205	}
206
207	// storage of types
208	var ntypes int // number of types defined
209	var typeset = make(map[int]string) // pointers to type tags
210
211	// token information
212
213	var ntokens = 0 // number of tokens
214	var tokset []Symb
215	var toklev []int // vector with the precedence of the terminals
216
217	// nonterminal information
218
219	var nnonter = -1 // the number of nonterminals
220	var nontrst []Symb
221	var start int // start symbol
222
223	// state information
224
225	var nstate = 0 // number of states
226	var pstate = make([]int, NSTATES+2) // index into statemem to the descriptions of the states
227	var statemem []Item
228	var tystate = make([]int, NSTATES) // contains type information about the states
229	var tstates []int // states generated by terminal gotos
230	var ntstates []int // states generated by nonterminal gotos
231	var mstates = make([]int, NSTATES) // chain of overflows of term/nonterm generation lists
232	var lastred int // number of last reduction of a state
233	var defact = make([]int, NSTATES) // default actions of states
234
235	// lookahead set information
236
237	var nolook = 0 // flag to turn off lookahead computations
238	var tbitset = 0 // size of lookahead sets
239	var clset Lkset // temporary storage for lookahead computations
240
241	// working set information
242
243	var wsets []Wset
244	var cwp int
245
246	// storage for action table
247
248	var amem []int // action table storage
249	var memp int // next free action table position
250	var indgo = make([]int, NSTATES) // index to the stored goto table
251
252	// temporary vector, indexable by states, terms, or ntokens
253
254	var temp1 = make([]int, TEMPSIZE) // temporary storage, indexed by terms + ntokens or states
255	var lineno = 1 // current input line number
256	var fatfl = 1 // if on, error is fatal
257	var nerrors = 0 // number of errors
258
259	// assigned token type values
260
261	var extval = 0
262
263	// grammar rule information
264
265	var nprod = 1 // number of productions
266	var prdptr [][]int // pointers to descriptions of productions
267	var levprd []int // precedence levels for the productions
268	var rlines []int // line number for this rule
269
270	// statistics collection variables
271
272	var zzgoent = 0
273	var zzgobest = 0
274	var zzacent = 0
275	var zzexcp = 0
276	var zzclose = 0
277	var zzrrconf = 0
278	var zzsrconf = 0
279	var zzstate = 0
280
281	// optimizer arrays
282
283	var yypgo [][]int
284	var optst [][]int
285	var ggreed []int
286	var pgo []int
287
288	var maxspr int // maximum spread of any entry
289	var maxoff int // maximum offset into a array
290	var maxa int
291
292	// storage for information about the nonterminals
293
294	var pres [][][]int // vector of pointers to productions yielding each nonterminal
295	var pfirst []Lkset
296	var pempty []int // vector of nonterminals nontrivially deriving e
297
298	// random stuff picked out from between functions
299
300	var indebug = 0 // debugging flag for cpfir
301	var pidebug = 0 // debugging flag for putitem
302	var gsdebug = 0 // debugging flag for stagen
303	var cldebug = 0 // debugging flag for closure
304	var pkdebug = 0 // debugging flag for apack
305	var g2debug = 0 // debugging for go2gen
306	var adb = 0 // debugging for callopt
307
308	type Resrv struct {
309	name string
310	value int
311	}
312
313	var resrv = []Resrv{
314	{"binary", BINARY},
315	{"left", LEFT},
316	{"nonassoc", BINARY},
317	{"prec", PREC},
318	{"right", RIGHT},
319	{"start", START},
320	{"term", TERM},
321	{"token", TERM},
322	{"type", TYPEDEF},
323	{"union", UNION},
324	{"struct", UNION},
325	{"error", ERROR},
326	}
327
328	type Error struct {
329	lineno int
330	tokens []string
331	msg string
332	}
333
334	var errors []Error
335
336	type Row struct {
337	actions []int
338	defaultAction int
339	}
340
341	var stateTable []Row
342
343	var zznewstate = 0
344
345	const EOF = -1
346
347	func main() {
348
349	setup() // initialize and read productions
350
351	tbitset = (ntokens + 32) / 32
352	cpres() // make table of which productions yield a given nonterminal
353	cempty() // make a table of which nonterminals can match the empty string
354	cpfir() // make a table of firsts of nonterminals
355
356	stagen() // generate the states
357
358	yypgo = make([][]int, nnonter+1)
359	optst = make([][]int, nstate)
360	output() // write the states and the tables
361	go2out()
362
363	hideprod()
364	summary()
365
366	callopt()
367
368	others()
369
370	exit(0)
371	}
372
373	func setup() {
374	var j, ty int
375
376	stderr = bufio.NewWriter(os.Stderr)
377	foutput = nil
378
379	flag.Parse()
380	if flag.NArg() != 1 {
381	usage()
382	}
383	if initialstacksize < 1 {
384	// never set so cannot happen
385	fmt.Fprintf(stderr, "yacc: stack size too small\n")
386	usage()
387	}
388	yaccpar = strings.Replace(yaccpartext, "$$", prefix, -1)
389	openup()
390
391	fmt.Fprintf(ftable, "// Code generated by goyacc %s. DO NOT EDIT.\n", strings.Join(os.Args[1:], " "))
392
393	defin(0, "$end")
394	extval = PRIVATE // tokens start in unicode 'private use'
395	defin(0, "error")
396	defin(1, "$accept")
397	defin(0, "$unk")
398	i := 0
399
400	t := gettok()
401
402	outer:
403	for {
404	switch t {
405	default:
406	errorf("syntax error tok=%v", t-PRIVATE)
407
408	case MARK, ENDFILE:
409	break outer
410
411	case ';':
412	// Do nothing.
413
414	case START:
415	t = gettok()
416	if t != IDENTIFIER {
417	errorf("bad %%start construction")
418	}
419	start = chfind(1, tokname)
420
421	case ERROR:
422	lno := lineno
423	var tokens []string
424	for {
425	t := gettok()
426	if t == ':' {
427	break
428	}
429	if t != IDENTIFIER && t != IDENTCOLON {
430	errorf("bad syntax in %%error")
431	}
432	tokens = append(tokens, tokname)
433	if t == IDENTCOLON {
434	break
435	}
436	}
437	if gettok() != IDENTIFIER {
438	errorf("bad syntax in %%error")
439	}
440	errors = append(errors, Error{lno, tokens, tokname})
441
442	case TYPEDEF:
443	t = gettok()
444	if t != TYPENAME {
445	errorf("bad syntax in %%type")
446	}
447	ty = numbval
448	for {
449	t = gettok()
450	switch t {
451	case IDENTIFIER:
452	t = chfind(1, tokname)
453	if t < NTBASE {
454	j = TYPE(toklev[t])
455	if j != 0 && j != ty {
456	errorf("type redeclaration of token %s",
457	tokset[t].name)
458	} else {
459	toklev[t] = SETTYPE(toklev[t], ty)
460	}
461	} else {
462	j = nontrst[t-NTBASE].value
463	if j != 0 && j != ty {
464	errorf("type redeclaration of nonterminal %v",
465	nontrst[t-NTBASE].name)
466	} else {
467	nontrst[t-NTBASE].value = ty
468	}
469	}
470	continue
471
472	case ',':
473	continue
474	}
475	break
476	}
477	continue
478
479	case UNION:
480	cpyunion()
481
482	case LEFT, BINARY, RIGHT, TERM:
483	// nonzero means new prec. and assoc.
484	lev := t - TERM
485	if lev != 0 {
486	i++
487	}
488	ty = 0
489
490	// get identifiers so defined
491	t = gettok()
492
493	// there is a type defined
494	if t == TYPENAME {
495	ty = numbval
496	t = gettok()
497	}
498	for {
499	switch t {
500	case ',':
501	t = gettok()
502	continue
503
504	case ';':
505	// Do nothing.
506
507	case IDENTIFIER:
508	j = chfind(0, tokname)
509	if j >= NTBASE {
510	errorf("%v defined earlier as nonterminal", tokname)
511	}
512	if lev != 0 {
513	if ASSOC(toklev[j]) != 0 {
514	errorf("redeclaration of precedence of %v", tokname)
515	}
516	toklev[j] = SETASC(toklev[j], lev)
517	toklev[j] = SETPLEV(toklev[j], i)
518	}
519	if ty != 0 {
520	if TYPE(toklev[j]) != 0 {
521	errorf("redeclaration of type of %v", tokname)
522	}
523	toklev[j] = SETTYPE(toklev[j], ty)
524	}
525	t = gettok()
526	if t == NUMBER {
527	tokset[j].value = numbval
528	t = gettok()
529	}
530
531	continue
532	}
533	break
534	}
535	continue
536
537	case LCURLY:
538	cpycode()
539	}
540	t = gettok()
541	}
542
543	if t == ENDFILE {
544	errorf("unexpected EOF before %%")
545	}
546
547	fmt.Fprintf(fcode, "switch %snt {\n", prefix)
548
549	moreprod()
550	prdptr[0] = []int{NTBASE, start, 1, 0}
551
552	nprod = 1
553	curprod := make([]int, RULEINC)
554	t = gettok()
555	if t != IDENTCOLON {
556	errorf("bad syntax on first rule")
557	}
558
559	if start == 0 {
560	prdptr[0][1] = chfind(1, tokname)
561	}
562
563	// read rules
564	// put into prdptr array in the format
565	// target
566	// followed by id's of terminals and non-terminals
567	// followed by -nprod
568
569	for t != MARK && t != ENDFILE {
570	mem := 0
571
572	// process a rule
573	rlines[nprod] = lineno
574	ruleline := lineno
575	if t == '\|' {
576	curprod[mem] = prdptr[nprod-1][0]
577	mem++
578	} else if t == IDENTCOLON {
579	curprod[mem] = chfind(1, tokname)
580	if curprod[mem] < NTBASE {
581	lerrorf(ruleline, "token illegal on LHS of grammar rule")
582	}
583	mem++
584	} else {
585	lerrorf(ruleline, "illegal rule: missing semicolon or \| ?")
586	}
587
588	// read rule body
589	t = gettok()
590	for {
591	for t == IDENTIFIER {
592	curprod[mem] = chfind(1, tokname)
593	if curprod[mem] < NTBASE {
594	levprd[nprod] = toklev[curprod[mem]]
595	}
596	mem++
597	if mem >= len(curprod) {
598	ncurprod := make([]int, mem+RULEINC)
599	copy(ncurprod, curprod)
600	curprod = ncurprod
601	}
602	t = gettok()
603	}
604	if t == PREC {
605	if gettok() != IDENTIFIER {
606	lerrorf(ruleline, "illegal %%prec syntax")
607	}
608	j = chfind(2, tokname)
609	if j >= NTBASE {
610	lerrorf(ruleline, "nonterminal "+nontrst[j-NTBASE].name+" illegal after %%prec")
611	}
612	levprd[nprod] = toklev[j]
613	t = gettok()
614	}
615	if t != '=' {
616	break
617	}
618	levprd[nprod] \|= ACTFLAG
619	fmt.Fprintf(fcode, "\n\tcase %v:", nprod)
620	fmt.Fprintf(fcode, "\n\t\t%sDollar = %sS[%spt-%v:%spt+1]", prefix, prefix, prefix, mem-1, prefix)
621	cpyact(curprod, mem)
622
623	// action within rule...
624	t = gettok()
625	if t == IDENTIFIER {
626	// make it a nonterminal
627	j = chfind(1, fmt.Sprintf("$$%v", nprod))
628
629	//
630	// the current rule will become rule number nprod+1
631	// enter null production for action
632	//
633	prdptr[nprod] = make([]int, 2)
634	prdptr[nprod][0] = j
635	prdptr[nprod][1] = -nprod
636
637	// update the production information
638	nprod++
639	moreprod()
640	levprd[nprod] = levprd[nprod-1] & ^ACTFLAG
641	levprd[nprod-1] = ACTFLAG
642	rlines[nprod] = lineno
643
644	// make the action appear in the original rule
645	curprod[mem] = j
646	mem++
647	if mem >= len(curprod) {
648	ncurprod := make([]int, mem+RULEINC)
649	copy(ncurprod, curprod)
650	curprod = ncurprod
651	}
652	}
653	}
654
655	for t == ';' {
656	t = gettok()
657	}
658	curprod[mem] = -nprod
659	mem++
660
661	// check that default action is reasonable
662	if ntypes != 0 && (levprd[nprod]&ACTFLAG) == 0 &&
663	nontrst[curprod[0]-NTBASE].value != 0 {
664	// no explicit action, LHS has value
665	tempty := curprod[1]
666	if tempty < 0 {
667	lerrorf(ruleline, "must return a value, since LHS has a type")
668	}
669	if tempty >= NTBASE {
670	tempty = nontrst[tempty-NTBASE].value
671	} else {
672	tempty = TYPE(toklev[tempty])
673	}
674	if tempty != nontrst[curprod[0]-NTBASE].value {
675	lerrorf(ruleline, "default action causes potential type clash")
676	}
677	}
678	moreprod()
679	prdptr[nprod] = make([]int, mem)
680	copy(prdptr[nprod], curprod)
681	nprod++
682	moreprod()
683	levprd[nprod] = 0
684	}
685
686	if TEMPSIZE < ntokens+nnonter+1 {
687	errorf("too many tokens (%d) or non-terminals (%d)", ntokens, nnonter)
688	}
689
690	//
691	// end of all rules
692	// dump out the prefix code
693	//
694
695	fmt.Fprintf(fcode, "\n\t}")
696
697	// put out non-literal terminals
698	for i := TOKSTART; i <= ntokens; i++ {
699	// non-literals
700	if !tokset[i].noconst {
701	fmt.Fprintf(ftable, "const %v = %v\n", tokset[i].name, tokset[i].value)
702	}
703	}
704
705	// put out names of tokens
706	ftable.WriteRune('\n')
707	fmt.Fprintf(ftable, "var %sToknames = [...]string{\n", prefix)
708	for i := 1; i <= ntokens; i++ {
709	fmt.Fprintf(ftable, "\t%q,\n", tokset[i].name)
710	}
711	fmt.Fprintf(ftable, "}\n")
712
713	// put out names of states.
714	// commented out to avoid a huge table just for debugging.
715	// re-enable to have the names in the binary.
716	ftable.WriteRune('\n')
717	fmt.Fprintf(ftable, "var %sStatenames = [...]string{\n", prefix)
718	// for i:=TOKSTART; i<=ntokens; i++ {
719	// fmt.Fprintf(ftable, "\t%q,\n", tokset[i].name);
720	// }
721	fmt.Fprintf(ftable, "}\n")
722
723	ftable.WriteRune('\n')
724	fmt.Fprintf(ftable, "const %sEofCode = 1\n", prefix)
725	fmt.Fprintf(ftable, "const %sErrCode = 2\n", prefix)
726	fmt.Fprintf(ftable, "const %sInitialStackSize = %v\n", prefix, initialstacksize)
727
728	//
729	// copy any postfix code
730	//
731	if t == MARK {
732	if !lflag {
733	fmt.Fprintf(ftable, "\n//line %v:%v\n", infile, lineno)
734	}
735	for {
736	c := getrune(finput)
737	if c == EOF {
738	break
739	}
740	ftable.WriteRune(c)
741	}
742	}
743	}
744
745	// allocate enough room to hold another production
746	func moreprod() {
747	n := len(prdptr)
748	if nprod >= n {
749	nn := n + PRODINC
750	aprod := make([][]int, nn)
751	alevprd := make([]int, nn)
752	arlines := make([]int, nn)
753
754	copy(aprod, prdptr)
755	copy(alevprd, levprd)
756	copy(arlines, rlines)
757
758	prdptr = aprod
759	levprd = alevprd
760	rlines = arlines
761	}
762	}
763
764	// define s to be a terminal if nt==0
765	// or a nonterminal if nt==1
766	func defin(nt int, s string) int {
767	val := 0
768	if nt != 0 {
769	nnonter++
770	if nnonter >= len(nontrst) {
771	anontrst := make([]Symb, nnonter+SYMINC)
772	copy(anontrst, nontrst)
773	nontrst = anontrst
774	}
775	nontrst[nnonter] = Symb{name: s}
776	return NTBASE + nnonter
777	}
778
779	// must be a token
780	ntokens++
781	if ntokens >= len(tokset) {
782	nn := ntokens + SYMINC
783	atokset := make([]Symb, nn)
784	atoklev := make([]int, nn)
785
786	copy(atoklev, toklev)
787	copy(atokset, tokset)
788
789	tokset = atokset
790	toklev = atoklev
791	}
792	tokset[ntokens].name = s
793	toklev[ntokens] = 0
794
795	// establish value for token
796	// single character literal
797	if s[0] == '\'' \|\| s[0] == '"' {
798	q, err := strconv.Unquote(s)
799	if err != nil {
800	errorf("invalid token: %s", err)
801	}
802	rq := []rune(q)
803	if len(rq) != 1 {
804	errorf("character token too long: %s", s)
805	}
806	val = int(rq[0])
807	if val == 0 {
808	errorf("token value 0 is illegal")
809	}
810	tokset[ntokens].noconst = true
811	} else {
812	val = extval
813	extval++
814	if s[0] == '$' {
815	tokset[ntokens].noconst = true
816	}
817	}
818
819	tokset[ntokens].value = val
820	return ntokens
821	}
822
823	var peekline = 0
824
825	func gettok() int {
826	var i int
827	var match, c rune
828
829	tokname = ""
830	for {
831	lineno += peekline
832	peekline = 0
833	c = getrune(finput)
834	for c == ' ' \|\| c == '\n' \|\| c == '\t' \|\| c == '\v' \|\| c == '\r' {
835	if c == '\n' {
836	lineno++
837	}
838	c = getrune(finput)
839	}
840
841	// skip comment -- fix
842	if c != '/' {
843	break
844	}
845	lineno += skipcom()
846	}
847
848	switch c {
849	case EOF:
850	if tokflag {
851	fmt.Printf(">>> ENDFILE %v\n", lineno)
852	}
853	return ENDFILE
854
855	case '{':
856	ungetrune(finput, c)
857	if tokflag {
858	fmt.Printf(">>> ={ %v\n", lineno)
859	}
860	return '='
861
862	case '<':
863	// get, and look up, a type name (union member name)
864	c = getrune(finput)
865	for c != '>' && c != EOF && c != '\n' {
866	tokname += string(c)
867	c = getrune(finput)
868	}
869
870	if c != '>' {
871	errorf("unterminated < ... > clause")
872	}
873
874	for i = 1; i <= ntypes; i++ {
875	if typeset[i] == tokname {
876	numbval = i
877	if tokflag {
878	fmt.Printf(">>> TYPENAME old <%v> %v\n", tokname, lineno)
879	}
880	return TYPENAME
881	}
882	}
883	ntypes++
884	numbval = ntypes
885	typeset[numbval] = tokname
886	if tokflag {
887	fmt.Printf(">>> TYPENAME new <%v> %v\n", tokname, lineno)
888	}
889	return TYPENAME
890
891	case '"', '\'':
892	match = c
893	tokname = string(c)
894	for {
895	c = getrune(finput)
896	if c == '\n' \|\| c == EOF {
897	errorf("illegal or missing ' or \"")
898	}
899	if c == '\\' {
900	tokname += string('\\')
901	c = getrune(finput)
902	} else if c == match {
903	if tokflag {
904	fmt.Printf(">>> IDENTIFIER \"%v\" %v\n", tokname, lineno)
905	}
906	tokname += string(c)
907	return IDENTIFIER
908	}
909	tokname += string(c)
910	}
911
912	case '%':
913	c = getrune(finput)
914	switch c {
915	case '%':
916	if tokflag {
917	fmt.Printf(">>> MARK %%%% %v\n", lineno)
918	}
919	return MARK
920	case '=':
921	if tokflag {
922	fmt.Printf(">>> PREC %%= %v\n", lineno)
923	}
924	return PREC
925	case '{':
926	if tokflag {
927	fmt.Printf(">>> LCURLY %%{ %v\n", lineno)
928	}
929	return LCURLY
930	}
931
932	getword(c)
933	// find a reserved word
934	for i := range resrv {
935	if tokname == resrv[i].name {
936	if tokflag {
937	fmt.Printf(">>> %%%v %v %v\n", tokname,
938	resrv[i].value-PRIVATE, lineno)
939	}
940	return resrv[i].value
941	}
942	}
943	errorf("invalid escape, or illegal reserved word: %v", tokname)
944
945	case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
946	numbval = int(c - '0')
947	for {
948	c = getrune(finput)
949	if !isdigit(c) {
950	break
951	}
952	numbval = numbval*10 + int(c-'0')
953	}
954	ungetrune(finput, c)
955	if tokflag {
956	fmt.Printf(">>> NUMBER %v %v\n", numbval, lineno)
957	}
958	return NUMBER
959
960	default:
961	if isword(c) \|\| c == '.' \|\| c == '$' {
962	getword(c)
963	break
964	}
965	if tokflag {
966	fmt.Printf(">>> OPERATOR %v %v\n", string(c), lineno)
967	}
968	return int(c)
969	}
970
971	// look ahead to distinguish IDENTIFIER from IDENTCOLON
972	c = getrune(finput)
973	for c == ' ' \|\| c == '\t' \|\| c == '\n' \|\| c == '\v' \|\| c == '\r' \|\| c == '/' {
974	if c == '\n' {
975	peekline++
976	}
977	// look for comments
978	if c == '/' {
979	peekline += skipcom()
980	}
981	c = getrune(finput)
982	}
983	if c == ':' {
984	if tokflag {
985	fmt.Printf(">>> IDENTCOLON %v: %v\n", tokname, lineno)
986	}
987	return IDENTCOLON
988	}
989
990	ungetrune(finput, c)
991	if tokflag {
992	fmt.Printf(">>> IDENTIFIER %v %v\n", tokname, lineno)
993	}
994	return IDENTIFIER
995	}
996
997	func getword(c rune) {
998	tokname = ""
999	for isword(c) \|\| isdigit(c) \|\| c == '.' \|\| c == '$' {
1000	tokname += string(c)
1001	c = getrune(finput)
1002	}
1003	ungetrune(finput, c)
1004	}
1005
1006	// determine the type of a symbol
1007	func fdtype(t int) int {
1008	var v int
1009	var s string
1010
1011	if t >= NTBASE {
1012	v = nontrst[t-NTBASE].value
1013	s = nontrst[t-NTBASE].name
1014	} else {
1015	v = TYPE(toklev[t])
1016	s = tokset[t].name
1017	}
1018	if v <= 0 {
1019	errorf("must specify type for %v", s)
1020	}
1021	return v
1022	}
1023
1024	func chfind(t int, s string) int {
1025	if s[0] == '"' \|\| s[0] == '\'' {
1026	t = 0
1027	}
1028	for i := 0; i <= ntokens; i++ {
1029	if s == tokset[i].name {
1030	return i
1031	}
1032	}
1033	for i := 0; i <= nnonter; i++ {
1034	if s == nontrst[i].name {
1035	return NTBASE + i
1036	}
1037	}
1038
1039	// cannot find name
1040	if t > 1 {
1041	errorf("%v should have been defined earlier", s)
1042	}
1043	return defin(t, s)
1044	}
1045
1046	// copy the union declaration to the output, and the define file if present
1047	func cpyunion() {
1048
1049	if !lflag {
1050	fmt.Fprintf(ftable, "\n//line %v:%v\n", infile, lineno)
1051	}
1052	fmt.Fprintf(ftable, "type %sSymType struct", prefix)
1053
1054	level := 0
1055
1056	out:
1057	for {
1058	c := getrune(finput)
1059	if c == EOF {
1060	errorf("EOF encountered while processing %%union")
1061	}
1062	ftable.WriteRune(c)
1063	switch c {
1064	case '\n':
1065	lineno++
1066	case '{':
1067	if level == 0 {
1068	fmt.Fprintf(ftable, "\n\tyys int")
1069	}
1070	level++
1071	case '}':
1072	level--
1073	if level == 0 {
1074	break out
1075	}
1076	}
1077	}
1078	fmt.Fprintf(ftable, "\n\n")
1079	}
1080
1081	// saves code between %{ and %}
1082	// adds an import for __fmt__ the first time
1083	func cpycode() {
1084	lno := lineno
1085
1086	c := getrune(finput)
1087	if c == '\n' {
1088	c = getrune(finput)
1089	lineno++
1090	}
1091	if !lflag {
1092	fmt.Fprintf(ftable, "\n//line %v:%v\n", infile, lineno)
1093	}
1094	// accumulate until %}
1095	code := make([]rune, 0, 1024)
1096	for c != EOF {
1097	if c == '%' {
1098	c = getrune(finput)
1099	if c == '}' {
1100	emitcode(code, lno+1)
1101	return
1102	}
1103	code = append(code, '%')
1104	}
1105	code = append(code, c)
1106	if c == '\n' {
1107	lineno++
1108	}
1109	c = getrune(finput)
1110	}
1111	lineno = lno
1112	errorf("eof before %%}")
1113	}
1114
1115	// emits code saved up from between %{ and %}
1116	// called by cpycode
1117	// adds an import for __yyfmt__ after the package clause
1118	func emitcode(code []rune, lineno int) {
1119	for i, line := range lines(code) {
1120	writecode(line)
1121	if !fmtImported && isPackageClause(line) {
1122	fmt.Fprintln(ftable, `import __yyfmt__ "fmt"`)
1123	if !lflag {
1124	fmt.Fprintf(ftable, "//line %v:%v\n\t\t", infile, lineno+i)
1125	}
1126	fmtImported = true
1127	}
1128	}
1129	}
1130
1131	// does this line look like a package clause? not perfect: might be confused by early comments.
1132	func isPackageClause(line []rune) bool {
1133	line = skipspace(line)
1134
1135	// must be big enough.
1136	if len(line) < len("package X\n") {
1137	return false
1138	}
1139
1140	// must start with "package"
1141	for i, r := range []rune("package") {
1142	if line[i] != r {
1143	return false
1144	}
1145	}
1146	line = skipspace(line[len("package"):])
1147
1148	// must have another identifier.
1149	if len(line) == 0 \|\| (!unicode.IsLetter(line[0]) && line[0] != '_') {
1150	return false
1151	}
1152	for len(line) > 0 {
1153	if !unicode.IsLetter(line[0]) && !unicode.IsDigit(line[0]) && line[0] != '_' {
1154	break
1155	}
1156	line = line[1:]
1157	}
1158	line = skipspace(line)
1159
1160	// eol, newline, or comment must follow
1161	if len(line) == 0 {
1162	return true
1163	}
1164	if line[0] == '\r' \|\| line[0] == '\n' {
1165	return true
1166	}
1167	if len(line) >= 2 {
1168	return line[0] == '/' && (line[1] == '/' \|\| line[1] == '*')
1169	}
1170	return false
1171	}
1172
1173	// skip initial spaces
1174	func skipspace(line []rune) []rune {
1175	for len(line) > 0 {
1176	if line[0] != ' ' && line[0] != '\t' {
1177	break
1178	}
1179	line = line[1:]
1180	}
1181	return line
1182	}
1183
1184	// break code into lines
1185	func lines(code []rune) [][]rune {
1186	l := make([][]rune, 0, 100)
1187	for len(code) > 0 {
1188	// one line per loop
1189	var i int
1190	for i = range code {
1191	if code[i] == '\n' {
1192	break
1193	}
1194	}
1195	l = append(l, code[:i+1])
1196	code = code[i+1:]
1197	}
1198	return l
1199	}
1200
1201	// writes code to ftable
1202	func writecode(code []rune) {
1203	for _, r := range code {
1204	ftable.WriteRune(r)
1205	}
1206	}
1207
1208	// skip over comments
1209	// skipcom is called after reading a '/'
1210	func skipcom() int {
1211	c := getrune(finput)
1212	if c == '/' {
1213	for c != EOF {
1214	if c == '\n' {
1215	return 1
1216	}
1217	c = getrune(finput)
1218	}
1219	errorf("EOF inside comment")
1220	return 0
1221	}
1222	if c != '*' {
1223	errorf("illegal comment")
1224	}
1225
1226	nl := 0 // lines skipped
1227	c = getrune(finput)
1228
1229	l1:
1230	switch c {
1231	case '*':
1232	c = getrune(finput)
1233	if c == '/' {
1234	break
1235	}
1236	goto l1
1237
1238	case '\n':
1239	nl++
1240	fallthrough
1241
1242	default:
1243	c = getrune(finput)
1244	goto l1
1245	}
1246	return nl
1247	}
1248
1249	// copy action to the next ; or closing }
1250	func cpyact(curprod []int, max int) {
1251
1252	if !lflag {
1253	fmt.Fprintf(fcode, "\n//line %v:%v", infile, lineno)
1254	}
1255	fmt.Fprint(fcode, "\n\t\t")
1256
1257	lno := lineno
1258	brac := 0
1259
1260	loop:
1261	for {
1262	c := getrune(finput)
1263
1264	swt:
1265	switch c {
1266	case ';':
1267	if brac == 0 {
1268	fcode.WriteRune(c)
1269	return
1270	}
1271
1272	case '{':
1273	brac++
1274
1275	case '$':
1276	s := 1
1277	tok := -1
1278	c = getrune(finput)
1279
1280	// type description
1281	if c == '<' {
1282	ungetrune(finput, c)
1283	if gettok() != TYPENAME {
1284	errorf("bad syntax on $<ident> clause")
1285	}
1286	tok = numbval
1287	c = getrune(finput)
1288	}
1289	if c == '$' {
1290	fmt.Fprintf(fcode, "%sVAL", prefix)
1291
1292	// put out the proper tag...
1293	if ntypes != 0 {
1294	if tok < 0 {
1295	tok = fdtype(curprod[0])
1296	}
1297	fmt.Fprintf(fcode, ".%v", typeset[tok])
1298	}
1299	continue loop
1300	}
1301	if c == '-' {
1302	s = -s
1303	c = getrune(finput)
1304	}
1305	j := 0
1306	if isdigit(c) {
1307	for isdigit(c) {
1308	j = j*10 + int(c-'0')
1309	c = getrune(finput)
1310	}
1311	ungetrune(finput, c)
1312	j = j * s
1313	if j >= max {
1314	errorf("Illegal use of $%v", j)
1315	}
1316	} else if isword(c) \|\| c == '.' {
1317	// look for $name
1318	ungetrune(finput, c)
1319	if gettok() != IDENTIFIER {
1320	errorf("$ must be followed by an identifier")
1321	}
1322	tokn := chfind(2, tokname)
1323	fnd := -1
1324	c = getrune(finput)
1325	if c != '@' {
1326	ungetrune(finput, c)
1327	} else if gettok() != NUMBER {
1328	errorf("@ must be followed by number")
1329	} else {
1330	fnd = numbval
1331	}
1332	for j = 1; j < max; j++ {
1333	if tokn == curprod[j] {
1334	fnd--
1335	if fnd <= 0 {
1336	break
1337	}
1338	}
1339	}
1340	if j >= max {
1341	errorf("$name or $name@number not found")
1342	}
1343	} else {
1344	fcode.WriteRune('$')
1345	if s < 0 {
1346	fcode.WriteRune('-')
1347	}
1348	ungetrune(finput, c)
1349	continue loop
1350	}
1351	fmt.Fprintf(fcode, "%sDollar[%v]", prefix, j)
1352
1353	// put out the proper tag
1354	if ntypes != 0 {
1355	if j <= 0 && tok < 0 {
1356	errorf("must specify type of $%v", j)
1357	}
1358	if tok < 0 {
1359	tok = fdtype(curprod[j])
1360	}
1361	fmt.Fprintf(fcode, ".%v", typeset[tok])
1362	}
1363	continue loop
1364
1365	case '}':
1366	brac--
1367	if brac != 0 {
1368	break
1369	}
1370	fcode.WriteRune(c)
1371	return
1372
1373	case '/':
1374	nc := getrune(finput)
1375	if nc != '/' && nc != '*' {
1376	ungetrune(finput, nc)
1377	break
1378	}
1379	// a comment
1380	fcode.WriteRune(c)
1381	fcode.WriteRune(nc)
1382	c = getrune(finput)
1383	for c != EOF {
1384	switch {
1385	case c == '\n':
1386	lineno++
1387	if nc == '/' { // end of // comment
1388	break swt
1389	}
1390	case c == '' && nc == '': // end of /* comment?
1391	nnc := getrune(finput)
1392	if nnc == '/' {
1393	fcode.WriteRune('*')
1394	fcode.WriteRune('/')
1395	continue loop
1396	}
1397	ungetrune(finput, nnc)
1398	}
1399	fcode.WriteRune(c)
1400	c = getrune(finput)
1401	}
1402	errorf("EOF inside comment")
1403
1404	case '\'', '"':
1405	// character string or constant
1406	match := c
1407	fcode.WriteRune(c)
1408	c = getrune(finput)
1409	for c != EOF {
1410	if c == '\\' {
1411	fcode.WriteRune(c)
1412	c = getrune(finput)
1413	if c == '\n' {
1414	lineno++
1415	}
1416	} else if c == match {
1417	break swt
1418	}
1419	if c == '\n' {
1420	errorf("newline in string or char const")
1421	}
1422	fcode.WriteRune(c)
1423	c = getrune(finput)
1424	}
1425	errorf("EOF in string or character constant")
1426
1427	case EOF:
1428	lineno = lno
1429	errorf("action does not terminate")
1430
1431	case '\n':
1432	fmt.Fprint(fcode, "\n\t")
1433	lineno++
1434	continue loop
1435	}
1436
1437	fcode.WriteRune(c)
1438	}
1439	}
1440
1441	func openup() {
1442	infile = flag.Arg(0)
1443	finput = open(infile)
1444	if finput == nil {
1445	errorf("cannot open %v", infile)
1446	}
1447
1448	foutput = nil
1449	if vflag != "" {
1450	foutput = create(vflag)
1451	if foutput == nil {
1452	errorf("can't create file %v", vflag)
1453	}
1454	}
1455
1456	ftable = nil
1457	if oflag == "" {
1458	oflag = "y.go"
1459	}
1460	ftable = create(oflag)
1461	if ftable == nil {
1462	errorf("can't create file %v", oflag)
1463	}
1464
1465	}
1466
1467	// return a pointer to the name of symbol i
1468	func symnam(i int) string {
1469	var s string
1470
1471	if i >= NTBASE {
1472	s = nontrst[i-NTBASE].name
1473	} else {
1474	s = tokset[i].name
1475	}
1476	return s
1477	}
1478
1479	// set elements 0 through n-1 to c
1480	func aryfil(v []int, n, c int) {
1481	for i := 0; i < n; i++ {
1482	v[i] = c
1483	}
1484	}
1485
1486	// compute an array with the beginnings of productions yielding given nonterminals
1487	// The array pres points to these lists
1488	// the array pyield has the lists: the total size is only NPROD+1
1489	func cpres() {
1490	pres = make([][][]int, nnonter+1)
1491	curres := make([][]int, nprod)
1492
1493	if false {
1494	for j := 0; j <= nnonter; j++ {
1495	fmt.Printf("nnonter[%v] = %v\n", j, nontrst[j].name)
1496	}
1497	for j := 0; j < nprod; j++ {
1498	fmt.Printf("prdptr[%v][0] = %v+NTBASE\n", j, prdptr[j][0]-NTBASE)
1499	}
1500	}
1501
1502	fatfl = 0 // make undefined symbols nonfatal
1503	for i := 0; i <= nnonter; i++ {
1504	n := 0
1505	c := i + NTBASE
1506	for j := 0; j < nprod; j++ {
1507	if prdptr[j][0] == c {
1508	curres[n] = prdptr[j][1:]
1509	n++
1510	}
1511	}
1512	if n == 0 {
1513	errorf("nonterminal %v not defined", nontrst[i].name)
1514	continue
1515	}
1516	pres[i] = make([][]int, n)
1517	copy(pres[i], curres)
1518	}
1519	fatfl = 1
1520	if nerrors != 0 {
1521	summary()
1522	exit(1)
1523	}
1524	}
1525
1526	// mark nonterminals which derive the empty string
1527	// also, look for nonterminals which don't derive any token strings
1528	func cempty() {
1529	var i, p, np int
1530	var prd []int
1531
1532	pempty = make([]int, nnonter+1)
1533
1534	// first, use the array pempty to detect productions that can never be reduced
1535	// set pempty to WHONOWS
1536	aryfil(pempty, nnonter+1, WHOKNOWS)
1537
1538	// now, look at productions, marking nonterminals which derive something
1539	more:
1540	for {
1541	for i = 0; i < nprod; i++ {
1542	prd = prdptr[i]
1543	if pempty[prd[0]-NTBASE] != 0 {
1544	continue
1545	}
1546	np = len(prd) - 1
1547	for p = 1; p < np; p++ {
1548	if prd[p] >= NTBASE && pempty[prd[p]-NTBASE] == WHOKNOWS {
1549	break
1550	}
1551	}
1552	// production can be derived
1553	if p == np {
1554	pempty[prd[0]-NTBASE] = OK
1555	continue more
1556	}
1557	}
1558	break
1559	}
1560
1561	// now, look at the nonterminals, to see if they are all OK
1562	for i = 0; i <= nnonter; i++ {
1563	// the added production rises or falls as the start symbol ...
1564	if i == 0 {
1565	continue
1566	}
1567	if pempty[i] != OK {
1568	fatfl = 0
1569	errorf("nonterminal " + nontrst[i].name + " never derives any token string")
1570	}
1571	}
1572
1573	if nerrors != 0 {
1574	summary()
1575	exit(1)
1576	}
1577
1578	// now, compute the pempty array, to see which nonterminals derive the empty string
1579	// set pempty to WHOKNOWS
1580	aryfil(pempty, nnonter+1, WHOKNOWS)
1581
1582	// loop as long as we keep finding empty nonterminals
1583
1584	again:
1585	for {
1586	next:
1587	for i = 1; i < nprod; i++ {
1588	// not known to be empty
1589	prd = prdptr[i]
1590	if pempty[prd[0]-NTBASE] != WHOKNOWS {
1591	continue
1592	}
1593	np = len(prd) - 1
1594	for p = 1; p < np; p++ {
1595	if prd[p] < NTBASE \|\| pempty[prd[p]-NTBASE] != EMPTY {
1596	continue next
1597	}
1598	}
1599
1600	// we have a nontrivially empty nonterminal
1601	pempty[prd[0]-NTBASE] = EMPTY
1602
1603	// got one ... try for another
1604	continue again
1605	}
1606	return
1607	}
1608	}
1609
1610	// compute an array with the first of nonterminals
1611	func cpfir() {
1612	var s, n, p, np, ch, i int
1613	var curres [][]int
1614	var prd []int
1615
1616	wsets = make([]Wset, nnonter+WSETINC)
1617	pfirst = make([]Lkset, nnonter+1)
1618	for i = 0; i <= nnonter; i++ {
1619	wsets[i].ws = mkset()
1620	pfirst[i] = mkset()
1621	curres = pres[i]
1622	n = len(curres)
1623
1624	// initially fill the sets
1625	for s = 0; s < n; s++ {
1626	prd = curres[s]
1627	np = len(prd) - 1
1628	for p = 0; p < np; p++ {
1629	ch = prd[p]
1630	if ch < NTBASE {
1631	setbit(pfirst[i], ch)
1632	break
1633	}
1634	if pempty[ch-NTBASE] == 0 {
1635	break
1636	}
1637	}
1638	}
1639	}
1640
1641	// now, reflect transitivity
1642	changes := 1
1643	for changes != 0 {
1644	changes = 0
1645	for i = 0; i <= nnonter; i++ {
1646	curres = pres[i]
1647	n = len(curres)
1648	for s = 0; s < n; s++ {
1649	prd = curres[s]
1650	np = len(prd) - 1
1651	for p = 0; p < np; p++ {
1652	ch = prd[p] - NTBASE
1653	if ch < 0 {
1654	break
1655	}
1656	changes \|= setunion(pfirst[i], pfirst[ch])
1657	if pempty[ch] == 0 {
1658	break
1659	}
1660	}
1661	}
1662	}
1663	}
1664
1665	if indebug == 0 {
1666	return
1667	}
1668	if foutput != nil {
1669	for i = 0; i <= nnonter; i++ {
1670	fmt.Fprintf(foutput, "\n%v: %v %v\n",
1671	nontrst[i].name, pfirst[i], pempty[i])
1672	}
1673	}
1674	}
1675
1676	// generate the states
1677	func stagen() {
1678	// initialize
1679	nstate = 0
1680	tstates = make([]int, ntokens+1) // states generated by terminal gotos
1681	ntstates = make([]int, nnonter+1) // states generated by nonterminal gotos
1682	amem = make([]int, ACTSIZE)
1683	memp = 0
1684
1685	clset = mkset()
1686	pstate[0] = 0
1687	pstate[1] = 0
1688	aryfil(clset, tbitset, 0)
1689	putitem(Pitem{prdptr[0], 0, 0, 0}, clset)
1690	tystate[0] = MUSTDO
1691	nstate = 1
1692	pstate[2] = pstate[1]
1693
1694	//
1695	// now, the main state generation loop
1696	// first pass generates all of the states
1697	// later passes fix up lookahead
1698	// could be sped up a lot by remembering
1699	// results of the first pass rather than recomputing
1700	//
1701	first := 1
1702	for more := 1; more != 0; first = 0 {
1703	more = 0
1704	for i := 0; i < nstate; i++ {
1705	if tystate[i] != MUSTDO {
1706	continue
1707	}
1708
1709	tystate[i] = DONE
1710	aryfil(temp1, nnonter+1, 0)
1711
1712	// take state i, close it, and do gotos
1713	closure(i)
1714
1715	// generate goto's
1716	for p := 0; p < cwp; p++ {
1717	pi := wsets[p]
1718	if pi.flag != 0 {
1719	continue
1720	}
1721	wsets[p].flag = 1
1722	c := pi.pitem.first
1723	if c <= 1 {
1724	if pstate[i+1]-pstate[i] <= p {
1725	tystate[i] = MUSTLOOKAHEAD
1726	}
1727	continue
1728	}
1729
1730	// do a goto on c
1731	putitem(wsets[p].pitem, wsets[p].ws)
1732	for q := p + 1; q < cwp; q++ {
1733	// this item contributes to the goto
1734	if c == wsets[q].pitem.first {
1735	putitem(wsets[q].pitem, wsets[q].ws)
1736	wsets[q].flag = 1
1737	}
1738	}
1739
1740	if c < NTBASE {
1741	state(c) // register new state
1742	} else {
1743	temp1[c-NTBASE] = state(c)
1744	}
1745	}
1746
1747	if gsdebug != 0 && foutput != nil {
1748	fmt.Fprintf(foutput, "%v: ", i)
1749	for j := 0; j <= nnonter; j++ {
1750	if temp1[j] != 0 {
1751	fmt.Fprintf(foutput, "%v %v,", nontrst[j].name, temp1[j])
1752	}
1753	}
1754	fmt.Fprintf(foutput, "\n")
1755	}
1756
1757	if first != 0 {
1758	indgo[i] = apack(temp1[1:], nnonter-1) - 1
1759	}
1760
1761	more++
1762	}
1763	}
1764	}
1765
1766	// generate the closure of state i
1767	func closure(i int) {
1768	zzclose++
1769
1770	// first, copy kernel of state i to wsets
1771	cwp = 0
1772	q := pstate[i+1]
1773	for p := pstate[i]; p < q; p++ {
1774	wsets[cwp].pitem = statemem[p].pitem
1775	wsets[cwp].flag = 1 // this item must get closed
1776	copy(wsets[cwp].ws, statemem[p].look)
1777	cwp++
1778	}
1779
1780	// now, go through the loop, closing each item
1781	work := 1
1782	for work != 0 {
1783	work = 0
1784	for u := 0; u < cwp; u++ {
1785	if wsets[u].flag == 0 {
1786	continue
1787	}
1788
1789	// dot is before c
1790	c := wsets[u].pitem.first
1791	if c < NTBASE {
1792	wsets[u].flag = 0
1793	// only interesting case is where . is before nonterminal
1794	continue
1795	}
1796
1797	// compute the lookahead
1798	aryfil(clset, tbitset, 0)
1799
1800	// find items involving c
1801	for v := u; v < cwp; v++ {
1802	if wsets[v].flag != 1 \|\| wsets[v].pitem.first != c {
1803	continue
1804	}
1805	pi := wsets[v].pitem.prod
1806	ipi := wsets[v].pitem.off + 1
1807
1808	wsets[v].flag = 0
1809	if nolook != 0 {
1810	continue
1811	}
1812
1813	ch := pi[ipi]
1814	ipi++
1815	for ch > 0 {
1816	// terminal symbol
1817	if ch < NTBASE {
1818	setbit(clset, ch)
1819	break
1820	}
1821
1822	// nonterminal symbol
1823	setunion(clset, pfirst[ch-NTBASE])
1824	if pempty[ch-NTBASE] == 0 {
1825	break
1826	}
1827	ch = pi[ipi]
1828	ipi++
1829	}
1830	if ch <= 0 {
1831	setunion(clset, wsets[v].ws)
1832	}
1833	}
1834
1835	//
1836	// now loop over productions derived from c
1837	//
1838	curres := pres[c-NTBASE]
1839	n := len(curres)
1840
1841	nexts:
1842	// initially fill the sets
1843	for s := 0; s < n; s++ {
1844	prd := curres[s]
1845
1846	//
1847	// put these items into the closure
1848	// is the item there
1849	//
1850	for v := 0; v < cwp; v++ {
1851	// yes, it is there
1852	if wsets[v].pitem.off == 0 &&
1853	aryeq(wsets[v].pitem.prod, prd) != 0 {
1854	if nolook == 0 &&
1855	setunion(wsets[v].ws, clset) != 0 {
1856	wsets[v].flag = 1
1857	work = 1
1858	}
1859	continue nexts
1860	}
1861	}
1862
1863	// not there; make a new entry
1864	if cwp >= len(wsets) {
1865	awsets := make([]Wset, cwp+WSETINC)
1866	copy(awsets, wsets)
1867	wsets = awsets
1868	}
1869	wsets[cwp].pitem = Pitem{prd, 0, prd[0], -prd[len(prd)-1]}
1870	wsets[cwp].flag = 1
1871	wsets[cwp].ws = mkset()
1872	if nolook == 0 {
1873	work = 1
1874	copy(wsets[cwp].ws, clset)
1875	}
1876	cwp++
1877	}
1878	}
1879	}
1880
1881	// have computed closure; flags are reset; return
1882	if cldebug != 0 && foutput != nil {
1883	fmt.Fprintf(foutput, "\nState %v, nolook = %v\n", i, nolook)
1884	for u := 0; u < cwp; u++ {
1885	if wsets[u].flag != 0 {
1886	fmt.Fprintf(foutput, "flag set\n")
1887	}
1888	wsets[u].flag = 0
1889	fmt.Fprintf(foutput, "\t%v", writem(wsets[u].pitem))
1890	prlook(wsets[u].ws)
1891	fmt.Fprintf(foutput, "\n")
1892	}
1893	}
1894	}
1895
1896	// sorts last state,and sees if it equals earlier ones. returns state number
1897	func state(c int) int {
1898	zzstate++
1899	p1 := pstate[nstate]
1900	p2 := pstate[nstate+1]
1901	if p1 == p2 {
1902	return 0 // null state
1903	}
1904
1905	// sort the items
1906	var k, l int
1907	for k = p1 + 1; k < p2; k++ { // make k the biggest
1908	for l = k; l > p1; l-- {
1909	if statemem[l].pitem.prodno < statemem[l-1].pitem.prodno \|\|
1910	statemem[l].pitem.prodno == statemem[l-1].pitem.prodno &&
1911	statemem[l].pitem.off < statemem[l-1].pitem.off {
1912	s := statemem[l]
1913	statemem[l] = statemem[l-1]
1914	statemem[l-1] = s
1915	} else {
1916	break
1917	}
1918	}
1919	}
1920
1921	size1 := p2 - p1 // size of state
1922
1923	var i int
1924	if c >= NTBASE {
1925	i = ntstates[c-NTBASE]
1926	} else {
1927	i = tstates[c]
1928	}
1929
1930	look:
1931	for ; i != 0; i = mstates[i] {
1932	// get ith state
1933	q1 := pstate[i]
1934	q2 := pstate[i+1]
1935	size2 := q2 - q1
1936	if size1 != size2 {
1937	continue
1938	}
1939	k = p1
1940	for l = q1; l < q2; l++ {
1941	if aryeq(statemem[l].pitem.prod, statemem[k].pitem.prod) == 0 \|\|
1942	statemem[l].pitem.off != statemem[k].pitem.off {
1943	continue look
1944	}
1945	k++
1946	}
1947
1948	// found it
1949	pstate[nstate+1] = pstate[nstate] // delete last state
1950
1951	// fix up lookaheads
1952	if nolook != 0 {
1953	return i
1954	}
1955	k = p1
1956	for l = q1; l < q2; l++ {
1957	if setunion(statemem[l].look, statemem[k].look) != 0 {
1958	tystate[i] = MUSTDO
1959	}
1960	k++
1961	}
1962	return i
1963	}
1964
1965	// state is new
1966	zznewstate++
1967	if nolook != 0 {
1968	errorf("yacc state/nolook error")
1969	}
1970	pstate[nstate+2] = p2
1971	if nstate+1 >= NSTATES {
1972	errorf("too many states")
1973	}
1974	if c >= NTBASE {
1975	mstates[nstate] = ntstates[c-NTBASE]
1976	ntstates[c-NTBASE] = nstate
1977	} else {
1978	mstates[nstate] = tstates[c]
1979	tstates[c] = nstate
1980	}
1981	tystate[nstate] = MUSTDO
1982	nstate++
1983	return nstate - 1
1984	}
1985
1986	func putitem(p Pitem, set Lkset) {
1987	p.off++
1988	p.first = p.prod[p.off]
1989
1990	if pidebug != 0 && foutput != nil {
1991	fmt.Fprintf(foutput, "putitem(%v), state %v\n", writem(p), nstate)
1992	}
1993	j := pstate[nstate+1]
1994	if j >= len(statemem) {
1995	asm := make([]Item, j+STATEINC)
1996	copy(asm, statemem)
1997	statemem = asm
1998	}
1999	statemem[j].pitem = p
2000	if nolook == 0 {
2001	s := mkset()
2002	copy(s, set)
2003	statemem[j].look = s
2004	}
2005	j++
2006	pstate[nstate+1] = j
2007	}
2008
2009	// creates output string for item pointed to by pp
2010	func writem(pp Pitem) string {
2011	var i int
2012
2013	p := pp.prod
2014	q := chcopy(nontrst[prdptr[pp.prodno][0]-NTBASE].name) + ": "
2015	npi := pp.off
2016
2017	pi := aryeq(p, prdptr[pp.prodno])
2018
2019	for {
2020	c := ' '
2021	if pi == npi {
2022	c = '.'
2023	}
2024	q += string(c)
2025
2026	i = p[pi]
2027	pi++
2028	if i <= 0 {
2029	break
2030	}
2031	q += chcopy(symnam(i))
2032	}
2033
2034	// an item calling for a reduction
2035	i = p[npi]
2036	if i < 0 {
2037	q += fmt.Sprintf(" (%v)", -i)
2038	}
2039
2040	return q
2041	}
2042
2043	// pack state i from temp1 into amem
2044	func apack(p []int, n int) int {
2045	//
2046	// we don't need to worry about checking because
2047	// we will only look at entries known to be there...
2048	// eliminate leading and trailing 0's
2049	//
2050	off := 0
2051	pp := 0
2052	for ; pp <= n && p[pp] == 0; pp++ {
2053	off--
2054	}
2055
2056	// no actions
2057	if pp > n {
2058	return 0
2059	}
2060	for ; n > pp && p[n] == 0; n-- {
2061	}
2062	p = p[pp : n+1]
2063
2064	// now, find a place for the elements from p to q, inclusive
2065	r := len(amem) - len(p)
2066
2067	nextk:
2068	for rr := 0; rr <= r; rr++ {
2069	qq := rr
2070	for pp = 0; pp < len(p); pp++ {
2071	if p[pp] != 0 {
2072	if p[pp] != amem[qq] && amem[qq] != 0 {
2073	continue nextk
2074	}
2075	}
2076	qq++
2077	}
2078
2079	// we have found an acceptable k
2080	if pkdebug != 0 && foutput != nil {
2081	fmt.Fprintf(foutput, "off = %v, k = %v\n", off+rr, rr)
2082	}
2083	qq = rr
2084	for pp = 0; pp < len(p); pp++ {
2085	if p[pp] != 0 {
2086	if qq > memp {
2087	memp = qq
2088	}
2089	amem[qq] = p[pp]
2090	}
2091	qq++
2092	}
2093	if pkdebug != 0 && foutput != nil {
2094	for pp = 0; pp <= memp; pp += 10 {
2095	fmt.Fprintf(foutput, "\n")
2096	for qq = pp; qq <= pp+9; qq++ {
2097	fmt.Fprintf(foutput, "%v ", amem[qq])
2098	}
2099	fmt.Fprintf(foutput, "\n")
2100	}
2101	}
2102	return off + rr
2103	}
2104	errorf("no space in action table")
2105	return 0
2106	}
2107
2108	// print the output for the states
2109	func output() {
2110	var c, u, v int
2111
2112	if !lflag {
2113	fmt.Fprintf(ftable, "\n//line yacctab:1")
2114	}
2115	var actions []int
2116
2117	if len(errors) > 0 {
2118	stateTable = make([]Row, nstate)
2119	}
2120
2121	noset := mkset()
2122
2123	// output the stuff for state i
2124	for i := 0; i < nstate; i++ {
2125	nolook = 0
2126	if tystate[i] != MUSTLOOKAHEAD {
2127	nolook = 1
2128	}
2129	closure(i)
2130
2131	// output actions
2132	nolook = 1
2133	aryfil(temp1, ntokens+nnonter+1, 0)
2134	for u = 0; u < cwp; u++ {
2135	c = wsets[u].pitem.first
2136	if c > 1 && c < NTBASE && temp1[c] == 0 {
2137	for v = u; v < cwp; v++ {
2138	if c == wsets[v].pitem.first {
2139	putitem(wsets[v].pitem, noset)
2140	}
2141	}
2142	temp1[c] = state(c)
2143	} else if c > NTBASE {
2144	c -= NTBASE
2145	if temp1[c+ntokens] == 0 {
2146	temp1[c+ntokens] = amem[indgo[i]+c]
2147	}
2148	}
2149	}
2150	if i == 1 {
2151	temp1[1] = ACCEPTCODE
2152	}
2153
2154	// now, we have the shifts; look at the reductions
2155	lastred = 0
2156	for u = 0; u < cwp; u++ {
2157	c = wsets[u].pitem.first
2158
2159	// reduction
2160	if c > 0 {
2161	continue
2162	}
2163	lastred = -c
2164	us := wsets[u].ws
2165	for k := 0; k <= ntokens; k++ {
2166	if bitset(us, k) == 0 {
2167	continue
2168	}
2169	if temp1[k] == 0 {
2170	temp1[k] = c
2171	} else if temp1[k] < 0 { // reduce/reduce conflict
2172	if foutput != nil {
2173	fmt.Fprintf(foutput,
2174	"\n %v: reduce/reduce conflict (red'ns "+
2175	"%v and %v) on %v",
2176	i, -temp1[k], lastred, symnam(k))
2177	}
2178	if -temp1[k] > lastred {
2179	temp1[k] = -lastred
2180	}
2181	zzrrconf++
2182	} else {
2183	// potential shift/reduce conflict
2184	precftn(lastred, k, i)
2185	}
2186	}
2187	}
2188	actions = addActions(actions, i)
2189	}
2190
2191	arrayOutColumns("Exca", actions, 2, false)
2192	fmt.Fprintf(ftable, "\n")
2193	ftable.WriteRune('\n')
2194	fmt.Fprintf(ftable, "const %sPrivate = %v\n", prefix, PRIVATE)
2195	}
2196
2197	// decide a shift/reduce conflict by precedence.
2198	// r is a rule number, t a token number
2199	// the conflict is in state s
2200	// temp1[t] is changed to reflect the action
2201	func precftn(r, t, s int) {
2202	action := NOASC
2203
2204	lp := levprd[r]
2205	lt := toklev[t]
2206	if PLEVEL(lt) == 0 \|\| PLEVEL(lp) == 0 {
2207	// conflict
2208	if foutput != nil {
2209	fmt.Fprintf(foutput,
2210	"\n%v: shift/reduce conflict (shift %v(%v), red'n %v(%v)) on %v",
2211	s, temp1[t], PLEVEL(lt), r, PLEVEL(lp), symnam(t))
2212	}
2213	zzsrconf++
2214	return
2215	}
2216	if PLEVEL(lt) == PLEVEL(lp) {
2217	action = ASSOC(lt)
2218	} else if PLEVEL(lt) > PLEVEL(lp) {
2219	action = RASC // shift
2220	} else {
2221	action = LASC
2222	} // reduce
2223	switch action {
2224	case BASC: // error action
2225	temp1[t] = ERRCODE
2226	case LASC: // reduce
2227	temp1[t] = -r
2228	}
2229	}
2230
2231	// output state i
2232	// temp1 has the actions, lastred the default
2233	func addActions(act []int, i int) []int {
2234	var p, p1 int
2235
2236	// find the best choice for lastred
2237	lastred = 0
2238	ntimes := 0
2239	for j := 0; j <= ntokens; j++ {
2240	if temp1[j] >= 0 {
2241	continue
2242	}
2243	if temp1[j]+lastred == 0 {
2244	continue
2245	}
2246	// count the number of appearances of temp1[j]
2247	count := 0
2248	tred := -temp1[j]
2249	levprd[tred] \|= REDFLAG
2250	for p = 0; p <= ntokens; p++ {
2251	if temp1[p]+tred == 0 {
2252	count++
2253	}
2254	}
2255	if count > ntimes {
2256	lastred = tred
2257	ntimes = count
2258	}
2259	}
2260
2261	//
2262	// for error recovery, arrange that, if there is a shift on the
2263	// error recovery token, `error', that the default be the error action
2264	//
2265	if temp1[2] > 0 {
2266	lastred = 0
2267	}
2268
2269	// clear out entries in temp1 which equal lastred
2270	// count entries in optst table
2271	n := 0
2272	for p = 0; p <= ntokens; p++ {
2273	p1 = temp1[p]
2274	if p1+lastred == 0 {
2275	temp1[p] = 0
2276	p1 = 0
2277	}
2278	if p1 > 0 && p1 != ACCEPTCODE && p1 != ERRCODE {
2279	n++
2280	}
2281	}
2282
2283	wrstate(i)
2284	defact[i] = lastred
2285	flag := 0
2286	os := make([]int, n*2)
2287	n = 0
2288	for p = 0; p <= ntokens; p++ {
2289	p1 = temp1[p]
2290	if p1 != 0 {
2291	if p1 < 0 {
2292	p1 = -p1
2293	} else if p1 == ACCEPTCODE {
2294	p1 = -1
2295	} else if p1 == ERRCODE {
2296	p1 = 0
2297	} else {
2298	os[n] = p
2299	n++
2300	os[n] = p1
2301	n++
2302	zzacent++
2303	continue
2304	}
2305	if flag == 0 {
2306	act = append(act, -1, i)
2307	}
2308	flag++
2309	act = append(act, p, p1)
2310	zzexcp++
2311	}
2312	}
2313	if flag != 0 {
2314	defact[i] = -2
2315	act = append(act, -2, lastred)
2316	}
2317	optst[i] = os
2318	return act
2319	}
2320
2321	// writes state i
2322	func wrstate(i int) {
2323	var j0, j1, u int
2324	var pp, qq int
2325
2326	if len(errors) > 0 {
2327	actions := append([]int(nil), temp1...)
2328	defaultAction := ERRCODE
2329	if lastred != 0 {
2330	defaultAction = -lastred
2331	}
2332	stateTable[i] = Row{actions, defaultAction}
2333	}
2334
2335	if foutput == nil {
2336	return
2337	}
2338	fmt.Fprintf(foutput, "\nstate %v\n", i)
2339	qq = pstate[i+1]
2340	for pp = pstate[i]; pp < qq; pp++ {
2341	fmt.Fprintf(foutput, "\t%v\n", writem(statemem[pp].pitem))
2342	}
2343	if tystate[i] == MUSTLOOKAHEAD {
2344	// print out empty productions in closure
2345	for u = pstate[i+1] - pstate[i]; u < cwp; u++ {
2346	if wsets[u].pitem.first < 0 {
2347	fmt.Fprintf(foutput, "\t%v\n", writem(wsets[u].pitem))
2348	}
2349	}
2350	}
2351
2352	// check for state equal to another
2353	for j0 = 0; j0 <= ntokens; j0++ {
2354	j1 = temp1[j0]
2355	if j1 != 0 {
2356	fmt.Fprintf(foutput, "\n\t%v ", symnam(j0))
2357
2358	// shift, error, or accept
2359	if j1 > 0 {
2360	if j1 == ACCEPTCODE {
2361	fmt.Fprintf(foutput, "accept")
2362	} else if j1 == ERRCODE {
2363	fmt.Fprintf(foutput, "error")
2364	} else {
2365	fmt.Fprintf(foutput, "shift %v", j1)
2366	}
2367	} else {
2368	fmt.Fprintf(foutput, "reduce %v (src line %v)", -j1, rlines[-j1])
2369	}
2370	}
2371	}
2372
2373	// output the final production
2374	if lastred != 0 {
2375	fmt.Fprintf(foutput, "\n\t. reduce %v (src line %v)\n\n",
2376	lastred, rlines[lastred])
2377	} else {
2378	fmt.Fprintf(foutput, "\n\t. error\n\n")
2379	}
2380
2381	// now, output nonterminal actions
2382	j1 = ntokens
2383	for j0 = 1; j0 <= nnonter; j0++ {
2384	j1++
2385	if temp1[j1] != 0 {
2386	fmt.Fprintf(foutput, "\t%v goto %v\n", symnam(j0+NTBASE), temp1[j1])
2387	}
2388	}
2389	}
2390
2391	// output the gotos for the nontermninals
2392	func go2out() {
2393	for i := 1; i <= nnonter; i++ {
2394	go2gen(i)
2395
2396	// find the best one to make default
2397	best := -1
2398	times := 0
2399
2400	// is j the most frequent
2401	for j := 0; j < nstate; j++ {
2402	if tystate[j] == 0 {
2403	continue
2404	}
2405	if tystate[j] == best {
2406	continue
2407	}
2408
2409	// is tystate[j] the most frequent
2410	count := 0
2411	cbest := tystate[j]
2412	for k := j; k < nstate; k++ {
2413	if tystate[k] == cbest {
2414	count++
2415	}
2416	}
2417	if count > times {
2418	best = cbest
2419	times = count
2420	}
2421	}
2422
2423	// best is now the default entry
2424	zzgobest += times - 1
2425	n := 0
2426	for j := 0; j < nstate; j++ {
2427	if tystate[j] != 0 && tystate[j] != best {
2428	n++
2429	}
2430	}
2431	goent := make([]int, 2*n+1)
2432	n = 0
2433	for j := 0; j < nstate; j++ {
2434	if tystate[j] != 0 && tystate[j] != best {
2435	goent[n] = j
2436	n++
2437	goent[n] = tystate[j]
2438	n++
2439	zzgoent++
2440	}
2441	}
2442
2443	// now, the default
2444	if best == -1 {
2445	best = 0
2446	}
2447
2448	zzgoent++
2449	goent[n] = best
2450	yypgo[i] = goent
2451	}
2452	}
2453
2454	// output the gotos for nonterminal c
2455	func go2gen(c int) {
2456	var i, cc, p, q int
2457
2458	// first, find nonterminals with gotos on c
2459	aryfil(temp1, nnonter+1, 0)
2460	temp1[c] = 1
2461	work := 1
2462	for work != 0 {
2463	work = 0
2464	for i = 0; i < nprod; i++ {
2465	// cc is a nonterminal with a goto on c
2466	cc = prdptr[i][1] - NTBASE
2467	if cc >= 0 && temp1[cc] != 0 {
2468	// thus, the left side of production i does too
2469	cc = prdptr[i][0] - NTBASE
2470	if temp1[cc] == 0 {
2471	work = 1
2472	temp1[cc] = 1
2473	}
2474	}
2475	}
2476	}
2477
2478	// now, we have temp1[c] = 1 if a goto on c in closure of cc
2479	if g2debug != 0 && foutput != nil {
2480	fmt.Fprintf(foutput, "%v: gotos on ", nontrst[c].name)
2481	for i = 0; i <= nnonter; i++ {
2482	if temp1[i] != 0 {
2483	fmt.Fprintf(foutput, "%v ", nontrst[i].name)
2484	}
2485	}
2486	fmt.Fprintf(foutput, "\n")
2487	}
2488
2489	// now, go through and put gotos into tystate
2490	aryfil(tystate, nstate, 0)
2491	for i = 0; i < nstate; i++ {
2492	q = pstate[i+1]
2493	for p = pstate[i]; p < q; p++ {
2494	cc = statemem[p].pitem.first
2495	if cc >= NTBASE {
2496	// goto on c is possible
2497	if temp1[cc-NTBASE] != 0 {
2498	tystate[i] = amem[indgo[i]+c]
2499	break
2500	}
2501	}
2502	}
2503	}
2504	}
2505
2506	// in order to free up the mem and amem arrays for the optimizer,
2507	// and still be able to output yyr1, etc., after the sizes of
2508	// the action array is known, we hide the nonterminals
2509	// derived by productions in levprd.
2510	func hideprod() {
2511	nred := 0
2512	levprd[0] = 0
2513	for i := 1; i < nprod; i++ {
2514	if (levprd[i] & REDFLAG) == 0 {
2515	if foutput != nil {
2516	fmt.Fprintf(foutput, "Rule not reduced: %v\n",
2517	writem(Pitem{prdptr[i], 0, 0, i}))
2518	}
2519	fmt.Printf("rule %v never reduced\n", writem(Pitem{prdptr[i], 0, 0, i}))
2520	nred++
2521	}
2522	levprd[i] = prdptr[i][0] - NTBASE
2523	}
2524	if nred != 0 {
2525	fmt.Printf("%v rules never reduced\n", nred)
2526	}
2527	}
2528
2529	func callopt() {
2530	var j, k, p, q, i int
2531	var v []int
2532
2533	pgo = make([]int, nnonter+1)
2534	pgo[0] = 0
2535	maxoff = 0
2536	maxspr = 0
2537	for i = 0; i < nstate; i++ {
2538	k = 32000
2539	j = 0
2540	v = optst[i]
2541	q = len(v)
2542	for p = 0; p < q; p += 2 {
2543	if v[p] > j {
2544	j = v[p]
2545	}
2546	if v[p] < k {
2547	k = v[p]
2548	}
2549	}
2550
2551	// nontrivial situation
2552	if k <= j {
2553	// j is now the range
2554	// j -= k; // call scj
2555	if k > maxoff {
2556	maxoff = k
2557	}
2558	}
2559	tystate[i] = q + 2*j
2560	if j > maxspr {
2561	maxspr = j
2562	}
2563	}
2564
2565	// initialize ggreed table
2566	ggreed = make([]int, nnonter+1)
2567	for i = 1; i <= nnonter; i++ {
2568	ggreed[i] = 1
2569	j = 0
2570
2571	// minimum entry index is always 0
2572	v = yypgo[i]
2573	q = len(v) - 1
2574	for p = 0; p < q; p += 2 {
2575	ggreed[i] += 2
2576	if v[p] > j {
2577	j = v[p]
2578	}
2579	}
2580	ggreed[i] = ggreed[i] + 2*j
2581	if j > maxoff {
2582	maxoff = j
2583	}
2584	}
2585
2586	// now, prepare to put the shift actions into the amem array
2587	for i = 0; i < ACTSIZE; i++ {
2588	amem[i] = 0
2589	}
2590	maxa = 0
2591	for i = 0; i < nstate; i++ {
2592	if tystate[i] == 0 && adb > 1 {
2593	fmt.Fprintf(ftable, "State %v: null\n", i)
2594	}
2595	indgo[i] = yyFlag
2596	}
2597
2598	i = nxti()
2599	for i != NOMORE {
2600	if i >= 0 {
2601	stin(i)
2602	} else {
2603	gin(-i)
2604	}
2605	i = nxti()
2606	}
2607
2608	// print amem array
2609	if adb > 2 {
2610	for p = 0; p <= maxa; p += 10 {
2611	fmt.Fprintf(ftable, "%v ", p)
2612	for i = 0; i < 10; i++ {
2613	fmt.Fprintf(ftable, "%v ", amem[p+i])
2614	}
2615	ftable.WriteRune('\n')
2616	}
2617	}
2618
2619	aoutput()
2620	osummary()
2621	}
2622
2623	// finds the next i
2624	func nxti() int {
2625	max := 0
2626	maxi := 0
2627	for i := 1; i <= nnonter; i++ {
2628	if ggreed[i] >= max {
2629	max = ggreed[i]
2630	maxi = -i
2631	}
2632	}
2633	for i := 0; i < nstate; i++ {
2634	if tystate[i] >= max {
2635	max = tystate[i]
2636	maxi = i
2637	}
2638	}
2639	if max == 0 {
2640	return NOMORE
2641	}
2642	return maxi
2643	}
2644
2645	func gin(i int) {
2646	var s int
2647
2648	// enter gotos on nonterminal i into array amem
2649	ggreed[i] = 0
2650
2651	q := yypgo[i]
2652	nq := len(q) - 1
2653
2654	// now, find amem place for it
2655	nextgp:
2656	for p := 0; p < ACTSIZE; p++ {
2657	if amem[p] != 0 {
2658	continue
2659	}
2660	for r := 0; r < nq; r += 2 {
2661	s = p + q[r] + 1
2662	if s > maxa {
2663	maxa = s
2664	if maxa >= ACTSIZE {
2665	errorf("a array overflow")
2666	}
2667	}
2668	if amem[s] != 0 {
2669	continue nextgp
2670	}
2671	}
2672
2673	// we have found amem spot
2674	amem[p] = q[nq]
2675	if p > maxa {
2676	maxa = p
2677	}
2678	for r := 0; r < nq; r += 2 {
2679	s = p + q[r] + 1
2680	amem[s] = q[r+1]
2681	}
2682	pgo[i] = p
2683	if adb > 1 {
2684	fmt.Fprintf(ftable, "Nonterminal %v, entry at %v\n", i, pgo[i])
2685	}
2686	return
2687	}
2688	errorf("cannot place goto %v\n", i)
2689	}
2690
2691	func stin(i int) {
2692	var s int
2693
2694	tystate[i] = 0
2695
2696	// enter state i into the amem array
2697	q := optst[i]
2698	nq := len(q)
2699
2700	nextn:
2701	// find an acceptable place
2702	for n := -maxoff; n < ACTSIZE; n++ {
2703	flag := 0
2704	for r := 0; r < nq; r += 2 {
2705	s = q[r] + n
2706	if s < 0 \|\| s > ACTSIZE {
2707	continue nextn
2708	}
2709	if amem[s] == 0 {
2710	flag++
2711	} else if amem[s] != q[r+1] {
2712	continue nextn
2713	}
2714	}
2715
2716	// check the position equals another only if the states are identical
2717	for j := 0; j < nstate; j++ {
2718	if indgo[j] == n {
2719
2720	// we have some disagreement
2721	if flag != 0 {
2722	continue nextn
2723	}
2724	if nq == len(optst[j]) {
2725
2726	// states are equal
2727	indgo[i] = n
2728	if adb > 1 {
2729	fmt.Fprintf(ftable, "State %v: entry at"+
2730	"%v equals state %v\n",
2731	i, n, j)
2732	}
2733	return
2734	}
2735
2736	// we have some disagreement
2737	continue nextn
2738	}
2739	}
2740
2741	for r := 0; r < nq; r += 2 {
2742	s = q[r] + n
2743	if s > maxa {
2744	maxa = s
2745	}
2746	if amem[s] != 0 && amem[s] != q[r+1] {
2747	errorf("clobber of a array, pos'n %v, by %v", s, q[r+1])
2748	}
2749	amem[s] = q[r+1]
2750	}
2751	indgo[i] = n
2752	if adb > 1 {
2753	fmt.Fprintf(ftable, "State %v: entry at %v\n", i, indgo[i])
2754	}
2755	return
2756	}
2757	errorf("Error; failure to place state %v", i)
2758	}
2759
2760	// this version is for limbo
2761	// write out the optimized parser
2762	func aoutput() {
2763	ftable.WriteRune('\n')
2764	fmt.Fprintf(ftable, "const %sLast = %v\n", prefix, maxa+1)
2765	arout("Act", amem, maxa+1)
2766	arout("Pact", indgo, nstate)
2767	arout("Pgo", pgo, nnonter+1)
2768	}
2769
2770	// put out other arrays, copy the parsers
2771	func others() {
2772	var i, j int
2773
2774	arout("R1", levprd, nprod)
2775	aryfil(temp1, nprod, 0)
2776
2777	//
2778	//yyr2 is the number of rules for each production
2779	//
2780	for i = 1; i < nprod; i++ {
2781	temp1[i] = len(prdptr[i]) - 2
2782	}
2783	arout("R2", temp1, nprod)
2784
2785	aryfil(temp1, nstate, -1000)
2786	for i = 0; i <= ntokens; i++ {
2787	for j := tstates[i]; j != 0; j = mstates[j] {
2788	temp1[j] = i
2789	}
2790	}
2791	for i = 0; i <= nnonter; i++ {
2792	for j = ntstates[i]; j != 0; j = mstates[j] {
2793	temp1[j] = -i
2794	}
2795	}
2796	arout("Chk", temp1, nstate)
2797	arrayOutColumns("Def", defact[:nstate], 10, false)
2798
2799	// put out token translation tables
2800	// table 1 has 0-256
2801	aryfil(temp1, 256, 0)
2802	c := 0
2803	for i = 1; i <= ntokens; i++ {
2804	j = tokset[i].value
2805	if j >= 0 && j < 256 {
2806	if temp1[j] != 0 {
2807	fmt.Print("yacc bug -- cannot have 2 different Ts with same value\n")
2808	fmt.Printf(" %s and %s\n", tokset[i].name, tokset[temp1[j]].name)
2809	nerrors++
2810	}
2811	temp1[j] = i
2812	if j > c {
2813	c = j
2814	}
2815	}
2816	}
2817	for i = 0; i <= c; i++ {
2818	if temp1[i] == 0 {
2819	temp1[i] = YYLEXUNK
2820	}
2821	}
2822	arout("Tok1", temp1, c+1)
2823
2824	// table 2 has PRIVATE-PRIVATE+256
2825	aryfil(temp1, 256, 0)
2826	c = 0
2827	for i = 1; i <= ntokens; i++ {
2828	j = tokset[i].value - PRIVATE
2829	if j >= 0 && j < 256 {
2830	if temp1[j] != 0 {
2831	fmt.Print("yacc bug -- cannot have 2 different Ts with same value\n")
2832	fmt.Printf(" %s and %s\n", tokset[i].name, tokset[temp1[j]].name)
2833	nerrors++
2834	}
2835	temp1[j] = i
2836	if j > c {
2837	c = j
2838	}
2839	}
2840	}
2841	arout("Tok2", temp1, c+1)
2842
2843	// table 3 has everything else
2844	ftable.WriteRune('\n')
2845	var v []int
2846	for i = 1; i <= ntokens; i++ {
2847	j = tokset[i].value
2848	if j >= 0 && j < 256 {
2849	continue
2850	}
2851	if j >= PRIVATE && j < 256+PRIVATE {
2852	continue
2853	}
2854
2855	v = append(v, j, i)
2856	}
2857	v = append(v, 0)
2858	arout("Tok3", v, len(v))
2859	fmt.Fprintf(ftable, "\n")
2860
2861	// Custom error messages.
2862	fmt.Fprintf(ftable, "\n")
2863	fmt.Fprintf(ftable, "var %sErrorMessages = [...]struct {\n", prefix)
2864	fmt.Fprintf(ftable, "\tstate int\n")
2865	fmt.Fprintf(ftable, "\ttoken int\n")
2866	fmt.Fprintf(ftable, "\tmsg string\n")
2867	fmt.Fprintf(ftable, "}{\n")
2868	for _, error := range errors {
2869	lineno = error.lineno
2870	state, token := runMachine(error.tokens)
2871	fmt.Fprintf(ftable, "\t{%v, %v, %s},\n", state, token, error.msg)
2872	}
2873	fmt.Fprintf(ftable, "}\n")
2874
2875	// copy parser text
2876	ch := getrune(finput)
2877	for ch != EOF {
2878	ftable.WriteRune(ch)
2879	ch = getrune(finput)
2880	}
2881
2882	// copy yaccpar
2883	if !lflag {
2884	fmt.Fprintf(ftable, "\n//line yaccpar:1\n")
2885	}
2886
2887	parts := strings.SplitN(yaccpar, prefix+"run()", 2)
2888	fmt.Fprintf(ftable, "%v", parts[0])
2889	ftable.Write(fcode.Bytes())
2890	fmt.Fprintf(ftable, "%v", parts[1])
2891	}
2892
2893	func runMachine(tokens []string) (state, token int) {
2894	var stack []int
2895	i := 0
2896	token = -1
2897
2898	Loop:
2899	if token < 0 {
2900	token = chfind(2, tokens[i])
2901	i++
2902	}
2903
2904	row := stateTable[state]
2905
2906	c := token
2907	if token >= NTBASE {
2908	c = token - NTBASE + ntokens
2909	}
2910	action := row.actions[c]
2911	if action == 0 {
2912	action = row.defaultAction
2913	}
2914
2915	switch {
2916	case action == ACCEPTCODE:
2917	errorf("tokens are accepted")
2918	return
2919	case action == ERRCODE:
2920	if token >= NTBASE {
2921	errorf("error at non-terminal token %s", symnam(token))
2922	}
2923	return
2924	case action > 0:
2925	// Shift to state action.
2926	stack = append(stack, state)
2927	state = action
2928	token = -1
2929	goto Loop
2930	default:
2931	// Reduce by production -action.
2932	prod := prdptr[-action]
2933	if rhsLen := len(prod) - 2; rhsLen > 0 {
2934	n := len(stack) - rhsLen
2935	state = stack[n]
2936	stack = stack[:n]
2937	}
2938	if token >= 0 {
2939	i--
2940	}
2941	token = prod[0]
2942	goto Loop
2943	}
2944	}
2945
2946	func minMax(v []int) (min, max int) {
2947	if len(v) == 0 {
2948	return
2949	}
2950	min = v[0]
2951	max = v[0]
2952	for _, i := range v {
2953	if i < min {
2954	min = i
2955	}
2956	if i > max {
2957	max = i
2958	}
2959	}
2960	return
2961	}
2962
2963	// return the smaller integral base type to store the values in v
2964	func minType(v []int, allowUnsigned bool) (typ string) {
2965	typ = "int"
2966	typeLen := 8
2967	min, max := minMax(v)
2968	checkType := func(name string, size, minType, maxType int) {
2969	if min >= minType && max <= maxType && typeLen > size {
2970	typ = name
2971	typeLen = size
2972	}
2973	}
2974	checkType("int32", 4, math.MinInt32, math.MaxInt32)
2975	checkType("int16", 2, math.MinInt16, math.MaxInt16)
2976	checkType("int8", 1, math.MinInt8, math.MaxInt8)
2977	if allowUnsigned {
2978	// Do not check for uint32, not worth and won't compile on 32 bit systems
2979	checkType("uint16", 2, 0, math.MaxUint16)
2980	checkType("uint8", 1, 0, math.MaxUint8)
2981	}
2982	return
2983	}
2984
2985	func arrayOutColumns(s string, v []int, columns int, allowUnsigned bool) {
2986	s = prefix + s
2987	ftable.WriteRune('\n')
2988	minType := minType(v, allowUnsigned)
2989	fmt.Fprintf(ftable, "var %v = [...]%s{", s, minType)
2990	for i, val := range v {
2991	if i%columns == 0 {
2992	fmt.Fprintf(ftable, "\n\t")
2993	} else {
2994	ftable.WriteRune(' ')
2995	}
2996	fmt.Fprintf(ftable, "%d,", val)
2997	}
2998	fmt.Fprintf(ftable, "\n}\n")
2999	}
3000
3001	func arout(s string, v []int, n int) {
3002	arrayOutColumns(s, v[:n], 10, true)
3003	}
3004
3005	// output the summary on y.output
3006	func summary() {
3007	if foutput != nil {
3008	fmt.Fprintf(foutput, "\n%v terminals, %v nonterminals\n", ntokens, nnonter+1)
3009	fmt.Fprintf(foutput, "%v grammar rules, %v/%v states\n", nprod, nstate, NSTATES)
3010	fmt.Fprintf(foutput, "%v shift/reduce, %v reduce/reduce conflicts reported\n", zzsrconf, zzrrconf)
3011	fmt.Fprintf(foutput, "%v working sets used\n", len(wsets))
3012	fmt.Fprintf(foutput, "memory: parser %v/%v\n", memp, ACTSIZE)
3013	fmt.Fprintf(foutput, "%v extra closures\n", zzclose-2*nstate)
3014	fmt.Fprintf(foutput, "%v shift entries, %v exceptions\n", zzacent, zzexcp)
3015	fmt.Fprintf(foutput, "%v goto entries\n", zzgoent)
3016	fmt.Fprintf(foutput, "%v entries saved by goto default\n", zzgobest)
3017	}
3018	if zzsrconf != 0 \|\| zzrrconf != 0 {
3019	fmt.Printf("\nconflicts: ")
3020	if zzsrconf != 0 {
3021	fmt.Printf("%v shift/reduce", zzsrconf)
3022	}
3023	if zzsrconf != 0 && zzrrconf != 0 {
3024	fmt.Printf(", ")
3025	}
3026	if zzrrconf != 0 {
3027	fmt.Printf("%v reduce/reduce", zzrrconf)
3028	}
3029	fmt.Printf("\n")
3030	}
3031	}
3032
3033	// write optimizer summary
3034	func osummary() {
3035	if foutput == nil {
3036	return
3037	}
3038	i := 0
3039	for p := maxa; p >= 0; p-- {
3040	if amem[p] == 0 {
3041	i++
3042	}
3043	}
3044
3045	fmt.Fprintf(foutput, "Optimizer space used: output %v/%v\n", maxa+1, ACTSIZE)
3046	fmt.Fprintf(foutput, "%v table entries, %v zero\n", maxa+1, i)
3047	fmt.Fprintf(foutput, "maximum spread: %v, maximum offset: %v\n", maxspr, maxoff)
3048	}
3049
3050	// copies and protects "'s in q
3051	func chcopy(q string) string {
3052	s := ""
3053	i := 0
3054	j := 0
3055	for i = 0; i < len(q); i++ {
3056	if q[i] == '"' {
3057	s += q[j:i] + "\\"
3058	j = i
3059	}
3060	}
3061	return s + q[j:i]
3062	}
3063
3064	func usage() {
3065	fmt.Fprintf(stderr, "usage: yacc [-o output] [-v parsetable] input\n")
3066	exit(1)
3067	}
3068
3069	func bitset(set Lkset, bit int) int { return set[bit>>5] & (1 << uint(bit&31)) }
3070
3071	func setbit(set Lkset, bit int) { set[bit>>5] \|= (1 << uint(bit&31)) }
3072
3073	func mkset() Lkset { return make([]int, tbitset) }
3074
3075	// set a to the union of a and b
3076	// return 1 if b is not a subset of a, 0 otherwise
3077	func setunion(a, b []int) int {
3078	sub := 0
3079	for i := 0; i < tbitset; i++ {
3080	x := a[i]
3081	y := x \| b[i]
3082	a[i] = y
3083	if y != x {
3084	sub = 1
3085	}
3086	}
3087	return sub
3088	}
3089
3090	func prlook(p Lkset) {
3091	if p == nil {
3092	fmt.Fprintf(foutput, "\tNULL")
3093	return
3094	}
3095	fmt.Fprintf(foutput, " { ")
3096	for j := 0; j <= ntokens; j++ {
3097	if bitset(p, j) != 0 {
3098	fmt.Fprintf(foutput, "%v ", symnam(j))
3099	}
3100	}
3101	fmt.Fprintf(foutput, "}")
3102	}
3103
3104	// utility routines
3105	var peekrune rune
3106
3107	func isdigit(c rune) bool { return c >= '0' && c <= '9' }
3108
3109	func isword(c rune) bool {
3110	return c >= 0xa0 \|\| c == '_' \|\| (c >= 'a' && c <= 'z') \|\| (c >= 'A' && c <= 'Z')
3111	}
3112
3113	// return 1 if 2 arrays are equal
3114	// return 0 if not equal
3115	func aryeq(a []int, b []int) int {
3116	n := len(a)
3117	if len(b) != n {
3118	return 0
3119	}
3120	for ll := 0; ll < n; ll++ {
3121	if a[ll] != b[ll] {
3122	return 0
3123	}
3124	}
3125	return 1
3126	}
3127
3128	func getrune(f *bufio.Reader) rune {
3129	var r rune
3130
3131	if peekrune != 0 {
3132	if peekrune == EOF {
3133	return EOF
3134	}
3135	r = peekrune
3136	peekrune = 0
3137	return r
3138	}
3139
3140	c, n, err := f.ReadRune()
3141	if n == 0 {
3142	return EOF
3143	}
3144	if err != nil {
3145	errorf("read error: %v", err)
3146	}
3147	//fmt.Printf("rune = %v n=%v\n", string(c), n);
3148	return c
3149	}
3150
3151	func ungetrune(f *bufio.Reader, c rune) {
3152	if f != finput {
3153	panic("ungetc - not finput")
3154	}
3155	if peekrune != 0 {
3156	panic("ungetc - 2nd unget")
3157	}
3158	peekrune = c
3159	}
3160
3161	func open(s string) *bufio.Reader {
3162	fi, err := os.Open(s)
3163	if err != nil {
3164	errorf("error opening %v: %v", s, err)
3165	}
3166	//fmt.Printf("open %v\n", s);
3167	return bufio.NewReader(fi)
3168	}
3169
3170	func create(s string) *bufio.Writer {
3171	fo, err := os.Create(s)
3172	if err != nil {
3173	errorf("error creating %v: %v", s, err)
3174	}
3175	//fmt.Printf("create %v mode %v\n", s);
3176	return bufio.NewWriter(fo)
3177	}
3178
3179	// write out error comment
3180	func lerrorf(lineno int, s string, v ...interface{}) {
3181	nerrors++
3182	fmt.Fprintf(stderr, s, v...)
3183	fmt.Fprintf(stderr, ": %v:%v\n", infile, lineno)
3184	if fatfl != 0 {
3185	summary()
3186	exit(1)
3187	}
3188	}
3189
3190	func errorf(s string, v ...interface{}) {
3191	lerrorf(lineno, s, v...)
3192	}
3193
3194	func exit(status int) {
3195	if ftable != nil {
3196	ftable.Flush()
3197	ftable = nil
3198	gofmt()
3199	}
3200	if foutput != nil {
3201	foutput.Flush()
3202	foutput = nil
3203	}
3204	if stderr != nil {
3205	stderr.Flush()
3206	stderr = nil
3207	}
3208	os.Exit(status)
3209	}
3210
3211	func gofmt() {
3212	src, err := ioutil.ReadFile(oflag)
3213	if err != nil {
3214	return
3215	}
3216	src, err = format.Source(src)
3217	if err != nil {
3218	return
3219	}
3220	ioutil.WriteFile(oflag, src, 0666)
3221	}
3222
3223	var yaccpar string // will be processed version of yaccpartext: s/$$/prefix/g
3224	var yaccpartext = `
3225	/* parser for yacc output */
3226
3227	var (
3228	$$Debug = 0
3229	$$ErrorVerbose = false
3230	)
3231
3232	type $$Lexer interface {
3233	Lex(lval *$$SymType) int
3234	Error(s string)
3235	}
3236
3237	type $$Parser interface {
3238	Parse($$Lexer) int
3239	Lookahead() int
3240	}
3241
3242	type $$ParserImpl struct {
3243	lval $$SymType
3244	stack [$$InitialStackSize]$$SymType
3245	char int
3246	}
3247
3248	func (p *$$ParserImpl) Lookahead() int {
3249	return p.char
3250	}
3251
3252	func $$NewParser() $$Parser {
3253	return &$$ParserImpl{}
3254	}
3255
3256	const $$Flag = -1000
3257
3258	func $$Tokname(c int) string {
3259	if c >= 1 && c-1 < len($$Toknames) {
3260	if $$Toknames[c-1] != "" {
3261	return $$Toknames[c-1]
3262	}
3263	}
3264	return __yyfmt__.Sprintf("tok-%v", c)
3265	}
3266
3267	func $$Statname(s int) string {
3268	if s >= 0 && s < len($$Statenames) {
3269	if $$Statenames[s] != "" {
3270	return $$Statenames[s]
3271	}
3272	}
3273	return __yyfmt__.Sprintf("state-%v", s)
3274	}
3275
3276	func $$ErrorMessage(state, lookAhead int) string {
3277	const TOKSTART = 4
3278
3279	if !$$ErrorVerbose {
3280	return "syntax error"
3281	}
3282
3283	for _, e := range $$ErrorMessages {
3284	if e.state == state && e.token == lookAhead {
3285	return "syntax error: " + e.msg
3286	}
3287	}
3288
3289	res := "syntax error: unexpected " + $$Tokname(lookAhead)
3290
3291	// To match Bison, suggest at most four expected tokens.
3292	expected := make([]int, 0, 4)
3293
3294	// Look for shiftable tokens.
3295	base := int($$Pact[state])
3296	for tok := TOKSTART; tok-1 < len($$Toknames); tok++ {
3297	if n := base + tok; n >= 0 && n < $$Last && int($$Chk[int($$Act[n])]) == tok {
3298	if len(expected) == cap(expected) {
3299	return res
3300	}
3301	expected = append(expected, tok)
3302	}
3303	}
3304
3305	if $$Def[state] == -2 {
3306	i := 0
3307	for $$Exca[i] != -1 \|\| int($$Exca[i+1]) != state {
3308	i += 2
3309	}
3310
3311	// Look for tokens that we accept or reduce.
3312	for i += 2; $$Exca[i] >= 0; i += 2 {
3313	tok := int($$Exca[i])
3314	if tok < TOKSTART \|\| $$Exca[i+1] == 0 {
3315	continue
3316	}
3317	if len(expected) == cap(expected) {
3318	return res
3319	}
3320	expected = append(expected, tok)
3321	}
3322
3323	// If the default action is to accept or reduce, give up.
3324	if $$Exca[i+1] != 0 {
3325	return res
3326	}
3327	}
3328
3329	for i, tok := range expected {
3330	if i == 0 {
3331	res += ", expecting "
3332	} else {
3333	res += " or "
3334	}
3335	res += $$Tokname(tok)
3336	}
3337	return res
3338	}
3339
3340	func $$lex1(lex $$Lexer, lval *$$SymType) (char, token int) {
3341	token = 0
3342	char = lex.Lex(lval)
3343	if char <= 0 {
3344	token = int($$Tok1[0])
3345	goto out
3346	}
3347	if char < len($$Tok1) {
3348	token = int($$Tok1[char])
3349	goto out
3350	}
3351	if char >= $$Private {
3352	if char < $$Private+len($$Tok2) {
3353	token = int($$Tok2[char-$$Private])
3354	goto out
3355	}
3356	}
3357	for i := 0; i < len($$Tok3); i += 2 {
3358	token = int($$Tok3[i+0])
3359	if token == char {
3360	token = int($$Tok3[i+1])
3361	goto out
3362	}
3363	}
3364
3365	out:
3366	if token == 0 {
3367	token = int($$Tok2[1]) /* unknown char */
3368	}
3369	if $$Debug >= 3 {
3370	__yyfmt__.Printf("lex %s(%d)\n", $$Tokname(token), uint(char))
3371	}
3372	return char, token
3373	}
3374
3375	func $$Parse($$lex $$Lexer) int {
3376	return $$NewParser().Parse($$lex)
3377	}
3378
3379	func ($$rcvr *$$ParserImpl) Parse($$lex $$Lexer) int {
3380	var $$n int
3381	var $$VAL $$SymType
3382	var $$Dollar []$$SymType
3383	_ = $$Dollar // silence set and not used
3384	$$S := $$rcvr.stack[:]
3385
3386	Nerrs := 0 /* number of errors */
3387	Errflag := 0 /* error recovery flag */
3388	$$state := 0
3389	$$rcvr.char = -1
3390	$$token := -1 // $$rcvr.char translated into internal numbering
3391	defer func() {
3392	// Make sure we report no lookahead when not parsing.
3393	$$state = -1
3394	$$rcvr.char = -1
3395	$$token = -1
3396	}()
3397	$$p := -1
3398	goto $$stack
3399
3400	ret0:
3401	return 0
3402
3403	ret1:
3404	return 1
3405
3406	$$stack:
3407	/* put a state and value onto the stack */
3408	if $$Debug >= 4 {
3409	__yyfmt__.Printf("char %v in %v\n", $$Tokname($$token), $$Statname($$state))
3410	}
3411
3412	$$p++
3413	if $$p >= len($$S) {
3414	nyys := make([]$$SymType, len($$S)*2)
3415	copy(nyys, $$S)
3416	$$S = nyys
3417	}
3418	$$S[$$p] = $$VAL
3419	$$S[$$p].yys = $$state
3420
3421	$$newstate:
3422	$$n = int($$Pact[$$state])
3423	if $$n <= $$Flag {
3424	goto $$default /* simple state */
3425	}
3426	if $$rcvr.char < 0 {
3427	$$rcvr.char, $$token = $$lex1($$lex, &$$rcvr.lval)
3428	}
3429	$$n += $$token
3430	if $$n < 0 \|\| $$n >= $$Last {
3431	goto $$default
3432	}
3433	$$n = int($$Act[$$n])
3434	if int($$Chk[$$n]) == $$token { /* valid shift */
3435	$$rcvr.char = -1
3436	$$token = -1
3437	$$VAL = $$rcvr.lval
3438	$$state = $$n
3439	if Errflag > 0 {
3440	Errflag--
3441	}
3442	goto $$stack
3443	}
3444
3445	$$default:
3446	/* default state action */
3447	$$n = int($$Def[$$state])
3448	if $$n == -2 {
3449	if $$rcvr.char < 0 {
3450	$$rcvr.char, $$token = $$lex1($$lex, &$$rcvr.lval)
3451	}
3452
3453	/* look through exception table */
3454	xi := 0
3455	for {
3456	if $$Exca[xi+0] == -1 && int($$Exca[xi+1]) == $$state {
3457	break
3458	}
3459	xi += 2
3460	}
3461	for xi += 2; ; xi += 2 {
3462	$$n = int($$Exca[xi+0])
3463	if $$n < 0 \|\| $$n == $$token {
3464	break
3465	}
3466	}
3467	$$n = int($$Exca[xi+1])
3468	if $$n < 0 {
3469	goto ret0
3470	}
3471	}
3472	if $$n == 0 {
3473	/* error ... attempt to resume parsing */
3474	switch Errflag {
3475	case 0: /* brand new error */
3476	$$lex.Error($$ErrorMessage($$state, $$token))
3477	Nerrs++
3478	if $$Debug >= 1 {
3479	__yyfmt__.Printf("%s", $$Statname($$state))
3480	__yyfmt__.Printf(" saw %s\n", $$Tokname($$token))
3481	}
3482	fallthrough
3483
3484	case 1, 2: /* incompletely recovered error ... try again */
3485	Errflag = 3
3486
3487	/* find a state where "error" is a legal shift action */
3488	for $$p >= 0 {
3489	$$n = int($$Pact[$$S[$$p].yys]) + $$ErrCode
3490	if $$n >= 0 && $$n < $$Last {
3491	$$state = int($$Act[$$n]) /* simulate a shift of "error" */
3492	if int($$Chk[$$state]) == $$ErrCode {
3493	goto $$stack
3494	}
3495	}
3496
3497	/* the current p has no shift on "error", pop stack */
3498	if $$Debug >= 2 {
3499	__yyfmt__.Printf("error recovery pops state %d\n", $$S[$$p].yys)
3500	}
3501	$$p--
3502	}
3503	/* there is no state on the stack with an error shift ... abort */
3504	goto ret1
3505
3506	case 3: /* no shift yet; clobber input char */
3507	if $$Debug >= 2 {
3508	__yyfmt__.Printf("error recovery discards %s\n", $$Tokname($$token))
3509	}
3510	if $$token == $$EofCode {
3511	goto ret1
3512	}
3513	$$rcvr.char = -1
3514	$$token = -1
3515	goto $$newstate /* try again in the same state */
3516	}
3517	}
3518
3519	/* reduction by production $$n */
3520	if $$Debug >= 2 {
3521	__yyfmt__.Printf("reduce %v in:\n\t%v\n", $$n, $$Statname($$state))
3522	}
3523
3524	$$nt := $$n
3525	$$pt := $$p
3526	_ = $$pt // guard against "declared and not used"
3527
3528	$$p -= int($$R2[$$n])
3529	// $$p is now the index of $0. Perform the default action. Iff the
3530	// reduced production is ε, $1 is possibly out of range.
3531	if $$p+1 >= len($$S) {
3532	nyys := make([]$$SymType, len($$S)*2)
3533	copy(nyys, $$S)
3534	$$S = nyys
3535	}
3536	$$VAL = $$S[$$p+1]
3537
3538	/* consult goto table to find next state */
3539	$$n = int($$R1[$$n])
3540	$$g := int($$Pgo[$$n])
3541	$$j := $$g + $$S[$$p].yys + 1
3542
3543	if $$j >= $$Last {
3544	$$state = int($$Act[$$g])
3545	} else {
3546	$$state = int($$Act[$$j])
3547	if int($$Chk[$$state]) != -$$n {
3548	$$state = int($$Act[$$g])
3549	}
3550	}
3551	// dummy call; replaced with literal code
3552	$$run()
3553	goto $$stack /* stack new state and value */
3554	}
3555	`
3556