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