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