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