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