From a138b50ee1e687704aca0719d1e7a68be8709110 Mon Sep 17 00:00:00 2001 From: Ken Thompson Date: Thu, 10 Sep 2009 13:19:46 -0700 Subject: [PATCH] goyacc command written in (c-style) go produces go source parser R=rsc OCL=34522 CL=34522 --- src/cmd/goyacc/Makefile | 12 + src/cmd/goyacc/goyacc.go | 3543 ++++++++++++++++++++++++++++++++++++++ 2 files changed, 3555 insertions(+) create mode 100644 src/cmd/goyacc/Makefile create mode 100644 src/cmd/goyacc/goyacc.go diff --git a/src/cmd/goyacc/Makefile b/src/cmd/goyacc/Makefile new file mode 100644 index 0000000000..cca46c3e8b --- /dev/null +++ b/src/cmd/goyacc/Makefile @@ -0,0 +1,12 @@ +# Copyright 2009 The Go Authors. All rights reserved. +# Use of this source code is governed by a BSD-style +# license that can be found in the LICENSE file. + +include $(GOROOT)/src/Make.$(GOARCH) + +TARG=goyacc +GOFILES=\ + goyacc.go\ + +include $(GOROOT)/src/Make.cmd + diff --git a/src/cmd/goyacc/goyacc.go b/src/cmd/goyacc/goyacc.go new file mode 100644 index 0000000000..480d34e4b4 --- /dev/null +++ b/src/cmd/goyacc/goyacc.go @@ -0,0 +1,3543 @@ +/* +Derived from Inferno's utils/iyacc/yacc.c +http://code.google.com/p/inferno-os/source/browse/utils/iyacc/yacc.c + +This copyright NOTICE applies to all files in this directory and +subdirectories, unless another copyright notice appears in a given +file or subdirectory. If you take substantial code from this software to use in +other programs, you must somehow include with it an appropriate +copyright notice that includes the copyright notice and the other +notices below. It is fine (and often tidier) to do that in a separate +file such as NOTICE, LICENCE or COPYING. + + Copyright © 1994-1999 Lucent Technologies Inc. All rights reserved. + Portions Copyright © 1995-1997 C H Forsyth (forsyth@terzarima.net) + Portions Copyright © 1997-1999 Vita Nuova Limited + Portions Copyright © 2000-2007 Vita Nuova Holdings Limited (www.vitanuova.com) + Portions Copyright © 2004,2006 Bruce Ellis + Portions Copyright © 2005-2007 C H Forsyth (forsyth@terzarima.net) + Revisions Copyright © 2000-2007 Lucent Technologies Inc. and others + Portions Copyright © 2009 The Go Authors. All rights reserved. + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN +THE SOFTWARE. +*/ + +package main + +// yacc +// major difference is lack of stem ("y" variable) +// + +import +( + "flag"; + "io"; + "fmt"; + "bufio"; + "os"; +) + +// the following are adjustable +// according to memory size +const +( + ACTSIZE = 30000; + NSTATES = 2000; + TEMPSIZE = 2000; + + SYMINC = 50; // increase for non-term or term + RULEINC = 50; // increase for max rule length prodptr[i] + PRODINC = 100; // increase for productions prodptr + WSETINC = 50; // increase for working sets wsets + STATEINC = 200; // increase for states statemem + + NAMESIZE = 50; + NTYPES = 63; + ISIZE = 400; + + PRIVATE = 0xE000; // unicode private use + +// relationships which must hold: +// TEMPSIZE >= NTERMS + NNONTERM + 1; +// TEMPSIZE >= NSTATES; +// + + NTBASE = 010000; + ERRCODE = 8190; + ACCEPTCODE = 8191; + YYLEXUNK = 3; + TOKSTART = 4; //index of first defined token +) + +// no, left, right, binary assoc. +const +( + NOASC = iota; + LASC; + RASC; + BASC; +) + +// flags for state generation +const +( + DONE = iota; + MUSTDO; + MUSTLOOKAHEAD; +) + +// flags for a rule having an action, and being reduced +const +( + ACTFLAG = 1<<(iota+2); + REDFLAG; +) + +// output parser flags +const YYFLAG = -1000 + +// parse tokens +const +( + IDENTIFIER = PRIVATE+iota; + MARK; + TERM; + LEFT; + RIGHT; + BINARY; + PREC; + LCURLY; + IDENTCOLON; + NUMBER; + START; + TYPEDEF; + TYPENAME; + UNION; +) + +const ENDFILE = 0 +const EMPTY = 1 +const WHOKNOWS = 0 +const OK = 1 +const NOMORE = -1000 + +// macros for getting associativity and precedence levels +func +ASSOC(i int) int +{ + return i & 3; +} + +func +PLEVEL(i int) int +{ + return (i >> 4) & 077; +} + +func +TYPE(i int) int +{ + return (i >> 10) & 077; +} + +// macros for setting associativity and precedence levels +func +SETASC(i, j int) int +{ + return i | j; +} + +func +SETPLEV(i, j int) int +{ + return i | (j << 4); +} + +func +SETTYPE(i, j int) int +{ + return i | (j << 10); +} + +// I/O descriptors +var finput *bufio.Reader // input file +var stderr *bufio.Writer +var ftable *bufio.Writer // y.go file +var foutput *bufio.Writer // y.output file + +var oflag string // -o [y.go] - y.go file +var vflag string // -v [y.output] - y.output file +var lflag bool // -l - disable line directives + +var stacksize = 200 + +// communication variables between various I/O routines +var infile string // input file name +var numbval int // value of an input number +var tokname string // input token name, slop for runes and 0 +var tokflag = false; + +// structure declarations +type Lkset []int + +type Pitem +struct +{ + prod []int; + off int; // offset within the production + first int; // first term or non-term in item + prodno int; // production number for sorting +} + +type Item +struct +{ + pitem Pitem; + look Lkset; +} + +type Symb +struct +{ + name string; + value int; +} + +type Wset +struct +{ + pitem Pitem; + flag int; + ws Lkset; +} + +// storage of types +var ntypes int // number of types defined +var typeset [NTYPES]string // pointers to type tags + +// token information + +var ntokens = 0 // number of tokens +var tokset []Symb +var toklev []int // vector with the precedence of the terminals + +// nonterminal information + +var nnonter = -1 // the number of nonterminals +var nontrst []Symb +var start int // start symbol + +// state information + +var nstate = 0 // number of states +var pstate = make([]int, NSTATES+2) // index into statemem to the descriptions of the states +var statemem []Item +var tystate = make([]int, NSTATES) // contains type information about the states +var tstates []int // states generated by terminal gotos +var ntstates []int // states generated by nonterminal gotos +var mstates = make([]int, NSTATES) // chain of overflows of term/nonterm generation lists +var lastred int // number of last reduction of a state +var defact = make([]int, NSTATES) // default actions of states + +// lookahead set information + +var lkst []Lkset +var nolook = 0 // flag to turn off lookahead computations +var tbitset = 0 // size of lookahead sets +var clset Lkset // temporary storage for lookahead computations + +// working set information + +var wsets []Wset +var cwp int + +// storage for action table + +var amem []int // action table storage +var memp int // next free action table position +var indgo = make([]int, NSTATES) // index to the stored goto table + +// temporary vector, indexable by states, terms, or ntokens + +var temp1 = make([]int, TEMPSIZE) // temporary storage, indexed by terms + ntokens or states +var lineno = 1 // current input line number +var fatfl = 1 // if on, error is fatal +var nerrors = 0 // number of errors + +// assigned token type values + +var extval = 0 + +// grammar rule information + +var nprod = 1 // number of productions +var prdptr [][]int // pointers to descriptions of productions +var levprd []int // precedence levels for the productions +var rlines []int // line number for this rule + +// statistics collection variables + +var zzgoent = 0 +var zzgobest = 0 +var zzacent = 0 +var zzexcp = 0 +var zzclose = 0 +var zzrrconf = 0 +var zzsrconf = 0 +var zzstate = 0 + +// optimizer arrays + +var yypgo [][]int +var optst [][]int +var ggreed []int +var pgo []int + +var maxspr int // maximum spread of any entry +var maxoff int // maximum offset into a array +var maxa int + +// storage for information about the nonterminals + +var pres [][][]int // vector of pointers to productions yielding each nonterminal +var pfirst []Lkset +var pempty []int // vector of nonterminals nontrivially deriving e + +// random stuff picked out from between functions + +var indebug = 0 // debugging flag for cpfir +var pidebug = 0 // debugging flag for putitem +var gsdebug = 0 // debugging flag for stagen +var cldebug = 0 // debugging flag for closure +var pkdebug = 0 // debugging flag for apack +var g2debug = 0 // debugging for go2gen +var adb = 0 // debugging for callopt + +type Resrv +struct +{ + name string; + value int; +} + +var resrv = +[]Resrv { + Resrv{"binary", BINARY}, + Resrv{"left", LEFT}, + Resrv{"nonassoc", BINARY}, + Resrv{"prec", PREC}, + Resrv{"right", RIGHT}, + Resrv{"start", START}, + Resrv{"term", TERM}, + Resrv{"token", TERM}, + Resrv{"type", TYPEDEF}, + Resrv{"union", UNION}, + Resrv{"struct", UNION} +} + +var zznewstate = 0 +const EOF = -1 +const UTFmax = 0x3f + +func +main() +{ + + setup(); // initialize and read productions + + tbitset = (ntokens+32)/32; + cpres(); // make table of which productions yield a given nonterminal + cempty(); // make a table of which nonterminals can match the empty string + cpfir(); // make a table of firsts of nonterminals + + stagen(); // generate the states + + yypgo = make([][]int, nnonter+1); + optst = make([][]int, nstate); + output(); // write the states and the tables + go2out(); + + hideprod(); + summary(); + + callopt(); + + others(); + + exit(0); +} + +func +setup() +{ + var j, ty int; + + stderr = bufio.NewWriter(os.NewFile(2, "stderr")); + foutput = nil; + + flag.StringVar(&oflag, "o", "", "parser output"); + flag.StringVar(&vflag, "v", "", "create parsing tables"); + flag.BoolVar(&lflag, "l", false, "disable line directives"); + + flag.Parse(); + if flag.NArg() != 1 { + usage(); + } + if stacksize < 1 { + // never set so cannot happen + fmt.Fprintf(stderr, "yacc: stack size too small\n"); + usage(); + } + openup(); + + defin(0, "$end"); + extval = PRIVATE; // tokens start in unicode 'private use' + defin(0, "error"); + defin(1, "$accept"); + defin(0, "$unk"); + i := 0; + + t := gettok(); + + outer: + for { + switch t { + default: + error("syntax error tok=%v", t-PRIVATE); + + case MARK,ENDFILE: + break outer; + + case ';': + + case START: + t = gettok(); + if t != IDENTIFIER { + error("bad %%start construction"); + } + start = chfind(1, tokname); + + case TYPEDEF: + t = gettok(); + if t != TYPENAME { + error("bad syntax in %%type"); + } + ty = numbval; + for { + t = gettok(); + switch t { + case IDENTIFIER: + t = chfind(1, tokname); + if t < NTBASE { + j = TYPE(toklev[t]); + if(j != 0 && j != ty) { + error("type redeclaration of token ", + tokset[t].name); + } else + toklev[t] = SETTYPE(toklev[t], ty); + } else { + j = nontrst[t-NTBASE].value; + if(j != 0 && j != ty) { + error("type redeclaration of nonterminal %v", + nontrst[t-NTBASE].name); + } else + nontrst[t-NTBASE].value = ty; + } + continue; + + case ',': + continue; + } + break; + } + continue; + + case UNION: + cpyunion(); + + case LEFT,BINARY,RIGHT,TERM: + // nonzero means new prec. and assoc. + lev := t-TERM; + if lev != 0 { + i++; + } + ty = 0; + + // get identifiers so defined + t = gettok(); + + // there is a type defined + if t == TYPENAME { + ty = numbval; + t = gettok(); + } + for { + switch t { + case ',': + t = gettok(); + continue; + + case';': + break; + + case IDENTIFIER: + j = chfind(0, tokname); + if j >= NTBASE { + error("%v defined earlier as nonterminal", tokname); + } + if lev != 0 { + if ASSOC(toklev[j]) != 0 { + error("redeclaration of precedence of %v", tokname); + } + toklev[j] = SETASC(toklev[j], lev); + toklev[j] = SETPLEV(toklev[j], i); + } + if ty != 0 { + if TYPE(toklev[j]) != 0 { + error("redeclaration of type of %v", tokname); + } + toklev[j] = SETTYPE(toklev[j], ty); + } + t = gettok(); + if t == NUMBER { + tokset[j].value = numbval; + t = gettok(); + } + + continue; + } + break; + } + continue; + + case LCURLY: + cpycode(); + } + t = gettok(); + } + + if t == ENDFILE { + error("unexpected EOF before %%"); + } + + // put out non-literal terminals + for i:=TOKSTART; i<=ntokens; i++ { + // non-literals + c := tokset[i].name[0]; + if c != ' ' && c != '$' { + fmt.Fprintf(ftable, "const\t%v\t= %v\n", tokset[i].name, tokset[i].value); + } + } + + // put out names of token names + fmt.Fprintf(ftable, "var\tToknames\t =[]string {\n"); + for i:=TOKSTART; i<=ntokens; i++ { + fmt.Fprintf(ftable, "\t\"%v\",\n", tokset[i].name); + } + fmt.Fprintf(ftable, "}\n"); + + // put out names of state names + fmt.Fprintf(ftable, "var\tStatenames\t =[]string {\n"); +// for i:=TOKSTART; i<=ntokens; i++ { +// fmt.Fprintf(ftable, "\t\"%v\",\n", tokset[i].name); +// } + fmt.Fprintf(ftable, "}\n"); + + fmt.Fprintf(ftable, "\nfunc\n"); + fmt.Fprintf(ftable, "yyrun(p int, yypt int) {\n"); + fmt.Fprintf(ftable, "switch p {\n"); + + moreprod(); + prdptr[0] = []int{NTBASE,start,1,0}; + + nprod = 1; + curprod := make([]int, RULEINC); + t = gettok(); + if t != IDENTCOLON { + error("bad syntax on first rule"); + } + + if start == 0 { + prdptr[0][1] = chfind(1, tokname); + } + + // read rules + // put into prdptr array in the format + // target + // followed by id's of terminals and non-terminals + // followd by -nprod + + for t != MARK && t != ENDFILE { + mem := 0; + + // process a rule + rlines[nprod] = lineno; + if t == '|' { + curprod[mem] = prdptr[nprod-1][0]; + mem++; + } else + if t == IDENTCOLON { + curprod[mem] = chfind(1, tokname); + if curprod[mem] < NTBASE { + error("token illegal on LHS of grammar rule"); + } + mem++; + } else + error("illegal rule: missing semicolon or | ?"); + + // read rule body + t = gettok(); + for { + for t == IDENTIFIER { + curprod[mem] = chfind(1, tokname); + if curprod[mem] < NTBASE { + levprd[nprod] = toklev[curprod[mem]]; + } + mem++; + if mem >= len(curprod) { + ncurprod := make([]int, mem+RULEINC); + for ll:=0; ll= NTBASE { + error("nonterminal "+nontrst[j-NTBASE].name+" illegal after %%prec"); + } + levprd[nprod] = toklev[j]; + t = gettok(); + } + if t != '=' { + break; + } + levprd[nprod] |= ACTFLAG; + fmt.Fprintf(ftable, "\ncase %v:", nprod); + cpyact(curprod, mem); + + // action within rule... + t = gettok(); + if t == IDENTIFIER { + // make it a nonterminal + j = chfind(1, fmt.Sprintf("$$%v",nprod)); + + // + // the current rule will become rule number nprod+1 + // enter null production for action + // + prdptr[nprod] = make([]int, 2); + prdptr[nprod][0] = j; + prdptr[nprod][1] = -nprod; + + // update the production information + nprod++; + moreprod(); + levprd[nprod] = levprd[nprod-1] & ^ACTFLAG; + levprd[nprod-1] = ACTFLAG; + rlines[nprod] = lineno; + + // make the action appear in the original rule + curprod[mem] = j; + mem++; + if mem >= len(curprod) { + ncurprod := make([]int, mem+RULEINC); + for ll:=0; ll= NTBASE { + tempty = nontrst[tempty-NTBASE].value; + } else + tempty = TYPE(toklev[tempty]); + if tempty != nontrst[curprod[0]-NTBASE].value { + error("default action causes potential type clash"); + } + fmt.Fprintf(ftable, "\ncase %v:", nprod); + fmt.Fprintf(ftable, "\n\tYYVAL.%v = YYS[yypt-0].%v;", + typeset[tempty], typeset[tempty]); + } + moreprod(); + prdptr[nprod] = make([]int, mem); + for ll:=0; ll= n { + nn := n+PRODINC; + aprod := make([][]int, nn); + alevprd := make([]int, nn); + arlines := make([]int, nn); + + for ll:=0; ll= len(nontrst) { + anontrst := make([]Symb, nnonter+SYMINC); + for ll:=0; ll= len(tokset) { + nn := ntokens+SYMINC; + atokset := make([]Symb, nn); + atoklev := make([]int, nn); + + for ll:=0; ll= '0' && c <= '9': + c -= '0'; + case c >= 'a' && c <= 'f': + c -= 'a' - 10; + case c >= 'A' && c <= 'F': + c -= 'A' - 10; + default: + error("illegal \\unnnn construction"); + } + val = val * 16 + c; + s = s[1:len(s)]; + } + if val == 0 { + error("'\\u0000' is illegal"); + } + } else + error("unknown escape"); + } else { + val = extval; + extval++; + } + + tokset[ntokens].value = val; + return ntokens; +} + +var peekline = 0; +func +gettok() int +{ + var i, match, c int; + + tokname = ""; + for { + lineno += peekline; + peekline = 0; + c = getrune(finput); + for c == ' ' || c == '\n' || c == '\t' || c == '\v' || c == '\r' { + if c == '\n' { + lineno++; + } + c = getrune(finput); + } + + // skip comment -- fix + if c != '/' { + break; + } + lineno += skipcom(); + } + + switch c { + case EOF: + if tokflag { + fmt.Printf(">>> ENDFILE %v\n", lineno); + } + return ENDFILE; + + case '{': + ungetrune(finput, c); + if tokflag { + fmt.Printf(">>> ={ %v\n", lineno); + } + return '='; + + case '<': + // get, and look up, a type name (union member name) + c = getrune(finput); + for c != '>' && c != EOF && c != '\n' { + tokname += string(c); + c = getrune(finput); + } + + if c != '>' { + error("unterminated < ... > clause"); + } + + for i=1; i<=ntypes; i++ { + if typeset[i] == tokname { + numbval = i; + if tokflag { + fmt.Printf(">>> TYPENAME old <%v> %v\n", tokname, lineno); + } + return TYPENAME; + } + } + ntypes++; + numbval = ntypes; + typeset[numbval] = tokname; + if tokflag { + fmt.Printf(">>> TYPENAME new <%v> %v\n", tokname, lineno); + } + return TYPENAME; + + case '"', '\'': + match = c; + tokname = " "; + for { + c = getrune(finput); + if c == '\n' || c == EOF { + error("illegal or missing ' or \"" ); + } + if c == '\\' { + tokname += string('\\'); + c = getrune(finput); + } else + if c == match { + if tokflag { + fmt.Printf(">>> IDENTIFIER \"%v\" %v\n", tokname, lineno); + } + return IDENTIFIER; + } + tokname += string(c); + } + + case '%': + c = getrune(finput); + switch c { + case '%': + if tokflag { + fmt.Printf(">>> MARK %%%% %v\n", lineno); + } + return MARK; + case '=': + if tokflag { + fmt.Printf(">>> PREC %%= %v\n", lineno); + } + return PREC; + case '{': + if tokflag { + fmt.Printf(">>> LCURLY %%{ %v\n", lineno); + } + return LCURLY; + } + + getword(c); + // find a reserved word + for c=0; c < len(resrv); c++ { + if tokname == resrv[c].name { + if tokflag { + fmt.Printf(">>> %%%v %v %v\n", tokname, + resrv[c].value-PRIVATE, lineno); + } + return resrv[c].value; + } + } + error("invalid escape, or illegal reserved word: %v", tokname); + + case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9': + numbval = c - '0'; + for { + c = getrune(finput); + if !isdigit(c) { + break; + } + numbval = numbval*10 + c-'0'; + } + ungetrune(finput, c); + if tokflag { + fmt.Printf(">>> NUMBER %v %v\n", numbval, lineno); + } + return NUMBER; + + default: + if isword(c) || c == '.' || c == '$' { + getword(c); + break; + } + if tokflag { + fmt.Printf(">>> OPERATOR %v %v\n", string(c), lineno); + } + return c; + } + + // look ahead to distinguish IDENTIFIER from IDENTCOLON + c = getrune(finput); + for c == ' ' || c == '\t' || c == '\n' || c == '\v' || c == '\r' || c == '/' { + if c == '\n' { + peekline++; + } + // look for comments + if c == '/' { + peekline += skipcom(); + } + c = getrune(finput); + } + if c == ':' { + if tokflag { + fmt.Printf(">>> IDENTCOLON %v: %v\n", tokname, lineno); + } + return IDENTCOLON; + } + + ungetrune(finput, c); + if tokflag { + fmt.Printf(">>> IDENTIFIER %v %v\n", tokname, lineno); + } + return IDENTIFIER; +} + +func +getword(c int) +{ + tokname = ""; + for isword(c) || isdigit(c) || c == '_' || c == '.' || c == '$' { + tokname += string(c); + c = getrune(finput); + } + ungetrune(finput, c); +} + +// +// determine the type of a symbol +// +func +fdtype(t int) int +{ + var v int; + var s string; + + if t >= NTBASE { + v = nontrst[t-NTBASE].value; + s = nontrst[t-NTBASE].name; + } else { + v = TYPE(toklev[t]); + s = tokset[t].name; + } + if v <= 0 { + error("must specify type for %v", s); + } + return v; +} + +func +chfind(t int, s string) int +{ + if s[0] == ' ' { + t = 0; + } + for i:=0; i<=ntokens; i++ { + if s == tokset[i].name { + return i; + } + } + for i:=0; i<=nnonter; i++ { + if s == nontrst[i].name { + return NTBASE+i; + } + } + + // cannot find name + if t > 1 { + error("%v should have been defined earlier", s); + } + return defin(t, s); +} + +// +// copy the union declaration to the output, and the define file if present +// +func +cpyunion() +{ + + if !lflag { + fmt.Fprintf(ftable, "\n//line %v %v\n", lineno, infile); + } + fmt.Fprintf(ftable, "type\tYYSTYPE\tstruct"); + + level := 0; + + out: + for { + c := getrune(finput); + if c == EOF { + error("EOF encountered while processing %%union"); + } + putrune(ftable, c); + switch(c) { + case '\n': + lineno++; + case '{': + if level == 0 { + fmt.Fprintf(ftable, "\n\tyys\tint;"); + } + level++; + case '}': + level--; + if level == 0 { + break out; + } + } + } + fmt.Fprintf(ftable, "\n"); + fmt.Fprintf(ftable, "var\tyylval\tYYSTYPE\n"); + fmt.Fprintf(ftable, "var\tYYVAL\tYYSTYPE\n"); + fmt.Fprintf(ftable, "var\tYYS\t[%v]YYSTYPE\n", stacksize); +} + +// +// saves code between %{ and %} +// +func +cpycode() +{ + lno := lineno; + + c := getrune(finput); + if c == '\n' { + c = getrune(finput); + lineno++; + } + if !lflag { + fmt.Fprintf(ftable, "\n//line %v %v\n", lineno, infile); + } + for c != EOF { + if c == '%' { + c = getrune(finput); + if c == '}' { + return; + } + putrune(ftable, '%'); + } + putrune(ftable, c); + if c == '\n' { + lineno++; + } + c = getrune(finput); + } + lineno = lno; + error("eof before %%}"); +} + +//func +//addcode(k int, s string) +//{ +// for i := 0; i < len(s); i++ { +// addcodec(k, int(s[i])); +// } +//} + +//func +//addcodec(k, c int) +//{ +// if codehead == nil || k != codetail.kind || codetail.ndata >= NCode { +// cd := new(Code); +// cd.kind = k; +// cd.data = make([]byte, NCode+UTFmax); +// cd.ndata = 0; +// cd.next = nil; +// +// if codehead == nil { +// codehead = cd; +// } else +// codetail.next = cd; +// codetail = cd; +// } +// +////!! codetail.ndata += sys->char2byte(c, codetail.data, codetail.ndata); +//} + +//func +//dumpcode(til int) +//{ +// for ; codehead != nil; codehead = codehead.next { +// if codehead.kind == til { +// return; +// } +// if write(ftable, codehead.data, codehead.ndata) != codehead.ndata { +// error("can't write output file"); +// } +// } +//} + +// +// write out the module declaration and any token info +// +//func +//dumpmod() +//{ +// +// for ; codehead != nil; codehead = codehead.next { +// if codehead.kind != CodeMod { +// break; +// } +// if write(ftable, codehead.data, codehead.ndata) != codehead.ndata { +// error("can't write output file"); +// } +// } +// +// for i:=TOKSTART; i<=ntokens; i++ { +// // non-literals +// c := tokset[i].name[0]; +// if c != ' ' && c != '$' { +// fmt.Fprintf(ftable, "vonst %v %v\n", +// tokset[i].name, tokset[i].value); +// } +// } +// +//} + +// +// skip over comments +// skipcom is called after reading a '/' +// +func +skipcom() int +{ + var c int; + + c = getrune(finput); + if c == '/' { + for c != EOF { + if c == '\n' { + return 1; + } + c = getrune(finput); + } + error("EOF inside comment"); + return 0; + } + if c != '*' { + error("illegal comment"); + } + + nl := 0; // lines skipped + c = getrune(finput); + + l1: + switch c { + case '*': + c = getrune(finput); + if c == '/' { + break; + } + goto l1; + + case '\n': + nl++; + fallthrough; + + default: + c = getrune(finput); + goto l1; + } + return nl; +} + +func +dumpprod(curprod []int, max int) +{ + fmt.Printf("\n"); + for i:=0; i clause"); + } + tok = numbval; + c = getrune(finput); + } + if c == '$' { + fmt.Fprintf(ftable, "YYVAL"); + + // put out the proper tag... + if ntypes != 0 { + if tok < 0 { + tok = fdtype(curprod[0]); + } + fmt.Fprintf(ftable, ".%v", typeset[tok]); + } + continue loop; + } + if c == '-' { + s = -s; + c = getrune(finput); + } + j := 0; + if isdigit(c) { + for isdigit(c) { + j = j*10 + c-'0'; + c = getrune(finput); + } + ungetrune(finput, c); + j = j*s; + if j >= max { + error("Illegal use of $%v", j); + } + } else + if isword(c) || c == '_' || c == '.' { + // look for $name + ungetrune(finput, c); + if gettok() != IDENTIFIER { + error("$ must be followed by an identifier"); + } + tokn := chfind(2, tokname); + fnd := -1; + c = getrune(finput); + if c != '@' { + ungetrune(finput, c); + } else + if gettok() != NUMBER { + error("@ must be followed by number"); + } else + fnd = numbval; + for j=1; j= max { + error("$name or $name@number not found"); + } + } else { + putrune(ftable, '$'); + if s < 0 { + putrune(ftable, '-'); + } + ungetrune(finput, c); + continue loop; + } + fmt.Fprintf(ftable, "YYS[yypt-%v]", max-j-1); + + // put out the proper tag + if ntypes != 0 { + if j <= 0 && tok < 0 { + error("must specify type of $%v", j); + } + if tok < 0 { + tok = fdtype(curprod[j]); + } + fmt.Fprintf(ftable, ".%v", typeset[tok]); + } + continue loop; + + case '}': + brac--; + if brac != 0 { + break; + } + putrune(ftable, c); + return; + + case '/': + // a comment + putrune(ftable, c); + c = getrune(finput); + for c != EOF { + if c == '\n' { + lineno++; + break swt; + } + putrune(ftable, c); + c = getrune(finput); + } + error("EOF inside comment"); + + case '\'', '"': + // character string or constant + match := c; + putrune(ftable, c); + c = getrune(finput); + for c != EOF { + if c == '\\' { + putrune(ftable, c); + c = getrune(finput); + if c == '\n' { + lineno++; + } + } else + if c == match { + break swt; + } + if c == '\n' { + error("newline in string or char const"); + } + putrune(ftable, c); + c = getrune(finput); + } + error("EOF in string or character constant"); + + case EOF: + lineno = lno; + error("action does not terminate"); + + case '\n': + lineno++; + } + + putrune(ftable, c); + } +} + +func +openup() +{ + var buf string; + + infile = flag.Arg(0); + finput = open(infile); + if(finput == nil) { + error("cannot open %v", infile); + } + + foutput = nil; + if vflag != "" { + foutput = create(vflag, 0666); + if foutput == nil { + error("can't create file %v", vflag); + } + } + + ftable = nil; + if oflag == "" { + oflag = "y.go"; + } + ftable = create(oflag, 0666); + if ftable == nil { + error("can't create file %v", oflag); + } + +} + +// +// return a pointer to the name of symbol i +// +func +symnam(i int) string +{ + var s string; + + if i >= NTBASE { + s = nontrst[i-NTBASE].name; + } else + s = tokset[i].name; + if s[0] == ' ' { + s = s[1:len(s)]; + } + return s; +} + +// +// set elements 0 through n-1 to c +// +func +aryfil(v []int, n, c int) +{ + for i:=0; i= NTBASE && pempty[prd[p]-NTBASE] == WHOKNOWS { + break; + } + } + // production can be derived + if p == np { + pempty[prd[0]-NTBASE] = OK; + continue more; + } + } + break; + } + + // now, look at the nonterminals, to see if they are all OK + for i=0; i<=nnonter; i++ { + // the added production rises or falls as the start symbol ... + if i == 0 { + continue; + } + if pempty[i] != OK { + fatfl = 0; + error("nonterminal " + nontrst[i].name + " never derives any token string"); + } + } + + if nerrors != 0 { + summary(); + exit(1); + } + + // now, compute the pempty array, to see which nonterminals derive the empty string + // set pempty to WHOKNOWS + aryfil(pempty, nnonter+1, WHOKNOWS); + + // loop as long as we keep finding empty nonterminals + + again: + for { + next: + for i=1; i 0 { + // terminal symbol + if ch < NTBASE { + setbit(clset, ch); + break; + } + + // nonterminal symbol + setunion(clset, pfirst[ch-NTBASE]); + if pempty[ch-NTBASE] == 0 { + break; + } + ch = pi[ipi]; + ipi++; + } + if ch <= 0 { + setunion(clset, wsets[v].ws); + } + } + + // + // now loop over productions derived from c + // + curres := pres[c-NTBASE]; + n := len(curres); + + nexts: + // initially fill the sets + for s := 0; s < n; s++ { + prd := curres[s]; + + // + // put these items into the closure + // is the item there + // + for v:=0; v= len(wsets) { + awsets := make([]Wset, cwp+WSETINC); + for ll:=0; ll p1; l-- { + if(statemem[l].pitem.prodno < statemem[l-1].pitem.prodno || + statemem[l].pitem.prodno == statemem[l-1].pitem.prodno && + statemem[l].pitem.off < statemem[l-1].pitem.off) { + s := statemem[l]; + statemem[l] = statemem[l-1]; + statemem[l-1] = s; + } else + break; + } + } + + size1 := p2 - p1; // size of state + + var i int; + if c >= NTBASE { + i = ntstates[c-NTBASE]; + } else + i = tstates[c]; + + look: + for ; i != 0; i = mstates[i] { + // get ith state + q1 := pstate[i]; + q2 := pstate[i+1]; + size2 := q2 - q1; + if size1 != size2 { + continue; + } + k = p1; + for l = q1; l < q2; l++ { + if aryeq(statemem[l].pitem.prod, statemem[k].pitem.prod) == 0 || + statemem[l].pitem.off != statemem[k].pitem.off { + continue look; + } + k++; + } + + // found it + pstate[nstate+1] = pstate[nstate]; // delete last state + + // fix up lookaheads + if nolook != 0 { + return i; + } + k = p1; + for l = q1; l < q2; l++ { + if setunion(statemem[l].look, statemem[k].look) != 0 { + tystate[i] = MUSTDO; + } + k++; + } + return i; + } + + // state is new + zznewstate++; + if nolook != 0 { + error("yacc state/nolook error"); + } + pstate[nstate+2] = p2; + if nstate+1 >= NSTATES { + error("too many states"); + } + if c >= NTBASE { + mstates[nstate] = ntstates[c-NTBASE]; + ntstates[c-NTBASE] = nstate; + } else { + mstates[nstate] = tstates[c]; + tstates[c] = nstate; + } + tystate[nstate] = MUSTDO; + nstate++; + return nstate-1; +} + +func +putitem(p Pitem, set Lkset) +{ + p.off++; + p.first = p.prod[p.off]; + + if pidebug != 0 && foutput != nil { + fmt.Fprintf(foutput, "putitem(%v), state %v\n", writem(p), nstate); + } + j := pstate[nstate+1]; + if j >= len(statemem) { + asm := make([]Item, j+STATEINC); + for ll:=0; ll n { + return 0; + } + for ; n > pp && p[n] == 0; n-- { + } + p = p[pp:n+1]; + + // now, find a place for the elements from p to q, inclusive + r := len(amem) - len(p); + + nextk: + for rr := 0; rr <= r; rr++ { + qq := rr; + for pp = 0; pp < len(p); pp++ { + if p[pp] != 0 { + if p[pp] != amem[qq] && amem[qq] != 0 { + continue nextk; + } + } + qq++; + } + + // we have found an acceptable k + if pkdebug != 0 && foutput != nil { + fmt.Fprintf(foutput, "off = %v, k = %v\n", off+rr, rr); + } + qq = rr; + for pp = 0; pp < len(p); pp++ { + if p[pp] != 0 { + if qq > memp { + memp = qq; + } + amem[qq] = p[pp]; + } + qq++; + } + if pkdebug != 0 && foutput != nil { + for pp = 0; pp <= memp; pp += 10 { + fmt.Fprintf(foutput, "\n"); + for qq = pp; qq <= pp+9; qq++ { + fmt.Fprintf(foutput, "%v ", amem[qq]); + } + fmt.Fprintf(foutput, "\n"); + } + } + return off + rr; + } + error("no space in action table"); + return 0; +} + +// +// print the output for the states +// +func +output() +{ + var c, u, v int; + + fmt.Fprintf(ftable, "var\tYYEXCA = []int {\n"); + + noset := mkset(); + + // output the stuff for state i + for i:=0; i 1 && c < NTBASE && temp1[c] == 0 { + for v=u; v NTBASE { + c -= NTBASE; + if temp1[c + ntokens] == 0 { + temp1[c+ntokens] = amem[indgo[i]+c]; + } + } + } + if i == 1 { + temp1[1] = ACCEPTCODE; + } + + // now, we have the shifts; look at the reductions + lastred = 0; + for u=0; u 0 { + continue; + } + lastred = -c; + us := wsets[u].ws; + for k:=0; k<=ntokens; k++ { + if bitset(us, k) == 0 { + continue; + } + if temp1[k] == 0 { + temp1[k] = c; + } else + if temp1[k] < 0 { // reduce/reduce conflict + if foutput != nil { + fmt.Fprintf(foutput, + "\n %v: reduce/reduce conflict (red'ns " + "%v and %v) on %v", + i, -temp1[k], lastred, symnam(k)); + } + if -temp1[k] > lastred { + temp1[k] = -lastred; + } + zzrrconf++; + } else + // potential shift/reduce conflict + precftn(lastred, k, i); + } + } + wract(i); + } + + fmt.Fprintf(ftable, "}\n"); + fmt.Fprintf(ftable, "const\tYYNPROD\t= %v\n", nprod); + fmt.Fprintf(ftable, "const\tYYPRIVATE\t= %v\n", PRIVATE); + fmt.Fprintf(ftable, "var\tYYTOKENNAMES []string\n"); + fmt.Fprintf(ftable, "var\tYYSTATES\n[]string\n"); +} + +// +// decide a shift/reduce conflict by precedence. +// r is a rule number, t a token number +// the conflict is in state s +// temp1[t] is changed to reflect the action +// +func +precftn(r, t, s int) +{ + var action int; + + lp := levprd[r]; + lt := toklev[t]; + if PLEVEL(lt) == 0 || PLEVEL(lp) == 0 { + // conflict + if foutput != nil { + fmt.Fprintf(foutput, + "\n%v: shift/reduce conflict (shift %v(%v), red'n %v(%v)) on %v", + s, temp1[t], PLEVEL(lt), r, PLEVEL(lp), symnam(t)); + } + zzsrconf++; + return; + } + if PLEVEL(lt) == PLEVEL(lp) { + action = ASSOC(lt); + } else + if PLEVEL(lt) > PLEVEL(lp) { + action = RASC; // shift + } else + action = LASC; // reduce + switch action { + case BASC: // error action + temp1[t] = ERRCODE; + case LASC: // reduce + temp1[t] = -r; + } +} + +// +// output state i +// temp1 has the actions, lastred the default +// +func +wract(i int) +{ + var p, p1 int; + + // find the best choice for lastred + lastred = 0; + ntimes := 0; + for j:=0; j<=ntokens; j++ { + if temp1[j] >= 0 { + continue; + } + if temp1[j]+lastred == 0 { + continue; + } + // count the number of appearances of temp1[j] + count := 0; + tred := -temp1[j]; + levprd[tred] |= REDFLAG; + for p=0; p<=ntokens; p++ { + if temp1[p]+tred == 0 { + count++; + } + } + if count > ntimes { + lastred = tred; + ntimes = count; + } + } + + // + // for error recovery, arrange that, if there is a shift on the + // error recovery token, `error', that the default be the error action + // + if temp1[2] > 0 { + lastred = 0; + } + + // clear out entries in temp1 which equal lastred + // count entries in optst table + n := 0; + for p=0; p<=ntokens; p++ { + p1 = temp1[p]; + if p1+lastred == 0 { + temp1[p] = 0; + p1 = 0; + } + if p1 > 0 && p1 != ACCEPTCODE && p1 != ERRCODE { + n++; + } + } + + wrstate(i); + defact[i] = lastred; + flag := 0; + os := make([]int, n*2); + n = 0; + for p=0; p<=ntokens; p++ { + p1 = temp1[p]; + if p1 != 0 { + if p1 < 0 { + p1 = -p1; + } else + if p1 == ACCEPTCODE { + p1 = -1; + } else + if p1 == ERRCODE { + p1 = 0; + } else { + os[n] = p; + n++; + os[n] = p1; + n++; + zzacent++; + continue; + } + if flag == 0 { + fmt.Fprintf(ftable, "-1, %v,\n", i); + } + flag++; + fmt.Fprintf(ftable, "\t%v, %v,\n", p, p1); + zzexcp++; + } + } + if flag != 0 { + defact[i] = -2; + fmt.Fprintf(ftable, "\t-2, %v,\n", lastred); + } + optst[i] = os; +} + +// +// writes state i +// +func +wrstate(i int) +{ + var j0, j1, u int; + var pp, qq int; + + if foutput == nil { + return; + } + fmt.Fprintf(foutput, "\nstate %v\n", i); + qq = pstate[i+1]; + for pp=pstate[i]; pp 0 { + if j1 == ACCEPTCODE { + fmt.Fprintf(foutput, "accept"); + } else + if j1 == ERRCODE { + fmt.Fprintf(foutput, "error"); + } else + fmt.Fprintf(foutput, "shift %v", j1); + } else + fmt.Fprintf(foutput, "reduce %v (src line %v)", -j1, rlines[-j1]); + } + } + + // output the final production + if lastred != 0 { + fmt.Fprintf(foutput, "\n\t. reduce %v (src line %v)\n\n", + lastred, rlines[lastred]); + } else + fmt.Fprintf(foutput, "\n\t. error\n\n"); + + // now, output nonterminal actions + j1 = ntokens; + for j0 = 1; j0 <= nnonter; j0++ { + j1++; + if temp1[j1] != 0 { + fmt.Fprintf(foutput, "\t%v goto %v\n", symnam(j0+NTBASE), temp1[j1]); + } + } +} + +// +// output the gotos for the nontermninals +// +func +go2out() +{ + for i := 1; i <= nnonter; i++ { + go2gen(i); + + // find the best one to make default + best := -1; + times := 0; + + // is j the most frequent + for j := 0; j < nstate; j++ { + if tystate[j] == 0 { + continue; + } + if tystate[j] == best { + continue; + } + + // is tystate[j] the most frequent + count := 0; + cbest := tystate[j]; + for k := j; k < nstate; k++ { + if tystate[k] == cbest { + count++; + } + } + if count > times { + best = cbest; + times = count; + } + } + + // best is now the default entry + zzgobest += times-1; + n := 0; + for j := 0; j < nstate; j++ { + if tystate[j] != 0 && tystate[j] != best { + n++; + } + } + goent := make([]int, 2*n+1); + n = 0; + for j := 0; j < nstate; j++ { + if tystate[j] != 0 && tystate[j] != best { + goent[n] = j; + n++; + goent[n] = tystate[j]; + n++; + zzgoent++; + } + } + + // now, the default + if best == -1 { + best = 0; + } + + zzgoent++; + goent[n] = best; + yypgo[i] = goent; + } +} + +// +// output the gotos for nonterminal c +// +func +go2gen(c int) +{ + var i, cc, p, q int; + + // first, find nonterminals with gotos on c + aryfil(temp1, nnonter+1, 0); + temp1[c] = 1; + work := 1; + for work != 0 { + work = 0; + for i=0; i= 0 && temp1[cc] != 0 { + // thus, the left side of production i does too + cc = prdptr[i][0]-NTBASE; + if temp1[cc] == 0 { + work = 1; + temp1[cc] = 1; + } + } + } + } + + // now, we have temp1[c] = 1 if a goto on c in closure of cc + if g2debug != 0 && foutput != nil { + fmt.Fprintf(foutput, "%v: gotos on ", nontrst[c].name); + for i=0; i<=nnonter; i++ { + if temp1[i] != 0 { + fmt.Fprintf(foutput, "%v ", nontrst[i].name); + } + } + fmt.Fprintf(foutput, "\n"); + } + + // now, go through and put gotos into tystate + aryfil(tystate, nstate, 0); + for i=0; i= NTBASE { + // goto on c is possible + if temp1[cc-NTBASE] != 0 { + tystate[i] = amem[indgo[i]+c]; + break; + } + } + } + } +} + +// +// in order to free up the mem and amem arrays for the optimizer, +// and still be able to output yyr1, etc., after the sizes of +// the action array is known, we hide the nonterminals +// derived by productions in levprd. +// +func +hideprod() +{ + nred := 0; + levprd[0] = 0; + for i:=1; i j { + j = v[p]; + } + if v[p] < k { + k = v[p]; + } + } + + // nontrivial situation + if k <= j { + // j is now the range +// j -= k; // call scj + if k > maxoff { + maxoff = k; + } + } + tystate[i] = q + 2*j; + if j > maxspr { + maxspr = j; + } + } + + // initialize ggreed table + ggreed = make([]int, nnonter+1); + for i = 1; i <= nnonter; i++ { + ggreed[i] = 1; + j = 0; + + // minimum entry index is always 0 + v = yypgo[i]; + q = len(v) - 1; + for p = 0; p < q ; p += 2 { + ggreed[i] += 2; + if v[p] > j { + j = v[p]; + } + } + ggreed[i] = ggreed[i] + 2*j; + if j > maxoff { + maxoff = j; + } + } + + // now, prepare to put the shift actions into the amem array + for i = 0; i < ACTSIZE; i++ { + amem[i] = 0; + } + maxa = 0; + for i = 0; i < nstate; i++ { + if tystate[i] == 0 && adb > 1 { + fmt.Fprintf(ftable, "State %v: null\n", i); + } + indgo[i] = YYFLAG; + } + + i = nxti(); + for i != NOMORE { + if i >= 0 { + stin(i); + } else + gin(-i); + i = nxti(); + } + + // print amem array + if adb > 2 { + for p = 0; p <= maxa; p += 10 { + fmt.Fprintf(ftable, "%v ", p); + for i = 0; i < 10; i++ { + fmt.Fprintf(ftable, "%v ", amem[p+i]); + } + putrune(ftable, '\n'); + } + } + + aoutput(); + osummary(); +} + +// +// finds the next i +// +func +nxti() int +{ + max := 0; + maxi := 0; + for i := 1; i <= nnonter; i++ { + if ggreed[i] >= max { + max = ggreed[i]; + maxi = -i; + } + } + for i := 0; i < nstate; i++ { + if tystate[i] >= max { + max = tystate[i]; + maxi = i; + } + } + if max == 0 { + return NOMORE; + } + return maxi; +} + +func +gin(i int) +{ + var s int; + + // enter gotos on nonterminal i into array amem + ggreed[i] = 0; + + q := yypgo[i]; + nq := len(q) - 1; + + // now, find amem place for it + nextgp: + for p := 0; p < ACTSIZE; p++ { + if amem[p] != 0 { + continue; + } + for r := 0; r < nq; r += 2 { + s = p + q[r] + 1; + if s > maxa { + maxa = s; + if maxa >= ACTSIZE { + error("a array overflow"); + } + } + if amem[s] != 0 { + continue nextgp; + } + } + + // we have found amem spot + amem[p] = q[nq]; + if p > maxa { + maxa = p; + } + for r := 0; r < nq; r += 2 { + s = p + q[r] + 1; + amem[s] = q[r+1]; + } + pgo[i] = p; + if adb > 1 { + fmt.Fprintf(ftable, "Nonterminal %v, entry at %v\n", i, pgo[i]); + } + return; + } + error("cannot place goto %v\n", i); +} + +func +stin(i int) +{ + var s int; + + tystate[i] = 0; + + // enter state i into the amem array + q := optst[i]; + nq := len(q); + + nextn: + // find an acceptable place + for n := -maxoff; n < ACTSIZE; n++ { + flag := 0; + for r := 0; r < nq; r += 2 { + s = q[r] + n; + if s < 0 || s > ACTSIZE { + continue nextn; + } + if amem[s] == 0 { + flag++; + } else + if amem[s] != q[r+1] { + continue nextn; + } + } + + // check the position equals another only if the states are identical + for j:=0; j 1 { + fmt.Fprintf(ftable, "State %v: entry at" + "%v equals state %v\n", i, n, j); + } + return; + } + + // we have some disagreement + continue nextn; + } + } + + for r := 0; r < nq; r += 2 { + s = q[r] + n; + if s > maxa { + maxa = s; + } + if amem[s] != 0 && amem[s] != q[r+1] { + error("clobber of a array, pos'n %v, by %v", s, q[r+1]); + } + amem[s] = q[r+1]; + } + indgo[i] = n; + if adb > 1 { + fmt.Fprintf(ftable, "State %v: entry at %v\n", i, indgo[i]); + } + return; + } + error("Error; failure to place state %v", i); +} + +// +// this version is for limbo +// write out the optimized parser +// +func +aoutput() +{ + fmt.Fprintf(ftable, "const\tYYLAST\t= %v\n",maxa+1); + arout("YYACT", amem, maxa+1); + arout("YYPACT", indgo, nstate); + arout("YYPGO", pgo, nnonter+1); +} + +// +// put out other arrays, copy the parsers +// +func +others() +{ + var i, j int; + + arout("YYR1", levprd, nprod); + aryfil(temp1, nprod, 0); + + // + //yyr2 is the number of rules for each production + // + for i=1; i= 0 && j < 256 { + if temp1[j] != 0 { + print("yacc bug -- cant have 2 different Ts with same value\n"); + print(" %s and %s\n", tokset[i].name, tokset[temp1[j]].name); + nerrors++; + } + temp1[j] = i; + if j > c { + c = j; + } + } + } + for i = 0; i <= c; i++ { + if temp1[i] == 0 { + temp1[i] = YYLEXUNK; + } + } + arout("YYTOK1", temp1, c+1); + + // table 2 has PRIVATE-PRIVATE+256 + aryfil(temp1, 256, 0); + c = 0; + for i=1; i<=ntokens; i++ { + j = tokset[i].value - PRIVATE; + if j >= 0 && j < 256 { + if temp1[j] != 0 { + print("yacc bug -- cant have 2 different Ts with same value\n"); + print(" %s and %s\n", tokset[i].name, tokset[temp1[j]].name); + nerrors++; + } + temp1[j] = i; + if j > c { + c = j; + } + } + } + arout("YYTOK2", temp1, c+1); + + // table 3 has everything else + fmt.Fprintf(ftable, "var\tYYTOK3\t= []int {\n"); + c = 0; + for i=1; i<=ntokens; i++ { + j = tokset[i].value; + if j >= 0 && j < 256 { + continue; + } + if j >= PRIVATE && j < 256+PRIVATE { + continue; + } + + fmt.Fprintf(ftable, "%4d,%4d,", j, i); + c++; + if c%5 == 0 { + putrune(ftable, '\n'); + } + } + fmt.Fprintf(ftable, "%4d\n };\n", 0); + + // copy parser text + c = getrune(finput); + for c != EOF { + putrune(ftable, c); + c = getrune(finput); + } + + // copy yaccpar + fmt.Fprintf(ftable, "%v", yaccpar); +} + +func +arout(s string, v []int, n int) +{ + fmt.Fprintf(ftable, "var\t%v\t= []int {\n", s); + for i := 0; i < n; i++ { + if i%10 == 0 { + putrune(ftable, '\n'); + } + fmt.Fprintf(ftable, "%4d", v[i]); + putrune(ftable, ','); + } + fmt.Fprintf(ftable, "\n};\n"); +} + +// +// output the summary on y.output +// +func +summary() +{ + if(foutput != nil) { + fmt.Fprintf(foutput, "\n%v terminals, %v nonterminals\n", ntokens, nnonter+1); + fmt.Fprintf(foutput, "%v grammar rules, %v/%v states\n", nprod, nstate, NSTATES); + fmt.Fprintf(foutput, "%v shift/reduce, %v reduce/reduce conflicts reported\n", zzsrconf, zzrrconf); + fmt.Fprintf(foutput, "%v working sets used\n", len(wsets)); + fmt.Fprintf(foutput, "memory: parser %v/%v\n", memp, ACTSIZE); + fmt.Fprintf(foutput, "%v extra closures\n", zzclose - 2*nstate); + fmt.Fprintf(foutput, "%v shift entries, %v exceptions\n", zzacent, zzexcp); + fmt.Fprintf(foutput, "%v goto entries\n", zzgoent); + fmt.Fprintf(foutput, "%v entries saved by goto default\n", zzgobest); + } + if zzsrconf != 0 || zzrrconf != 0 { + fmt.Printf("\nconflicts: "); + if zzsrconf != 0 { + fmt.Printf("%v shift/reduce", zzsrconf); + } + if zzsrconf != 0 && zzrrconf != 0 { + fmt.Printf(", "); + } + if zzrrconf != 0 { + fmt.Printf("%v reduce/reduce", zzrrconf); + } + fmt.Printf("\n"); + } +} + +// +// write optimizer summary +// +func +osummary() +{ + if foutput == nil { + return; + } + i := 0; + for p := maxa; p >= 0; p-- { + if amem[p] == 0 { + i++; + } + } + + fmt.Fprintf(foutput, "Optimizer space used: output %v/%v\n", maxa+1, ACTSIZE); + fmt.Fprintf(foutput, "%v table entries, %v zero\n", maxa+1, i); + fmt.Fprintf(foutput, "maximum spread: %v, maximum offset: %v\n", maxspr, maxoff); +} + +// +// copies and protects "'s in q +// +func +chcopy(q string) string +{ + s := ""; + i := 0; + j := 0; + for i = 0; i < len(q); i++ { + if q[i] == '"' { + s += q[j:i] + "\\"; + j = i; + } + } + return s + q[j:i]; +} + +func +usage() +{ + fmt.Fprintf(stderr, "usage: gacc [-o output] [-v parsetable] input\n"); + exit(1); +} + +func +bitset(set Lkset, bit int) int +{ + return set[bit>>5] & (1<>5] |= (1<= '0' && c <= '9'; +} + +func +isword(c int) bool +{ + return c >= 0xa0 || (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'); +} + +func +mktemp(t string) string +{ + return t; +} + +// +// return 1 if 2 arrays are equal +// return 0 if not equal +// +func +aryeq(a []int, b[]int) int +{ + n := len(a); + if len(b) != n { + return 0; + } + for ll:=0; ll 0 && yyc <= len(Toknames) { + if Toknames[yyc-1] != "" { + return Toknames[yyc-1]; + } + } + return fmt.Sprintf("tok-%v", yyc); +} + +func +Statname(yys int) string +{ + if yys >= 0 && yys < len(Statenames) { + if Statenames[yys] != "" { + return Statenames[yys]; + } + } + return fmt.Sprintf("state-%v", yys); +} + +func +lex1() int +{ + var yychar int; + var c int; + + yychar = Lex(); + if yychar <= 0 { + c = YYTOK1[0]; + goto out; + } + if yychar < len(YYTOK1) { + c = YYTOK1[yychar]; + goto out; + } + if yychar >= YYPRIVATE { + if yychar < YYPRIVATE+len(YYTOK2) { + c = YYTOK2[yychar-YYPRIVATE]; + goto out; + } + } + for i:=0; i= 3 { + fmt.Printf("lex %.4lux %s\n", yychar, Tokname(c)); + } + return c; +} + +func +Parse() int +{ + var yyj, yystate, yyn, yyg, yyxi, yyp int; + var yychar int; + var yypt, yynt int; + + yystate = 0; + yychar = -1; + Nerrs = 0; + Errflag = 0; + yyp = -1; + goto yystack; + +ret0: + return 0; + +ret1: + return 1; + +yystack: + /* put a state and value onto the stack */ + if Debug >= 4 { + fmt.Printf("char %v in %v", Tokname(yychar), Statname(yystate)); + } + + yyp++; + if yyp >= len(YYS) { + Error("yacc stack overflow"); + goto ret1; + } + YYS[yyp] = YYVAL; + YYS[yyp].yys = yystate; + +yynewstate: + yyn = YYPACT[yystate]; + if yyn <= YYFLAG { + goto yydefault; /* simple state */ + } + if yychar < 0 { + yychar = lex1(); + } + yyn += yychar; + if yyn < 0 || yyn >= YYLAST { + goto yydefault; + } + yyn = YYACT[yyn]; + if YYCHK[yyn] == yychar { /* valid shift */ + yychar = -1; + YYVAL = yylval; + yystate = yyn; + if Errflag > 0 { + Errflag--; + } + goto yystack; + } + +yydefault: + /* default state action */ + yyn = YYDEF[yystate]; + if yyn == -2 { + if yychar < 0 { + yychar = lex1(); + } + + /* look through exception table */ + for yyxi=0;; yyxi+=2 { + if YYEXCA[yyxi+0] == -1 && YYEXCA[yyxi+1] == yystate { + break; + } + } + for yyxi += 2;; yyxi += 2 { + yyn = YYEXCA[yyxi+0]; + if yyn < 0 || yyn == yychar { + break; + } + } + yyn = YYEXCA[yyxi+1]; + if yyn < 0 { + goto ret0; + } + } + if yyn == 0 { + /* error ... attempt to resume parsing */ + switch Errflag { + case 0: /* brand new error */ + Error("syntax error"); + Nerrs++; + if Debug >= 1 { + fmt.Printf("%s", Statname(yystate)); + fmt.Printf("saw %s\n", Tokname(yychar)); + } + fallthrough; + + case 1,2: /* incompletely recovered error ... try again */ + Errflag = 3; + + /* find a state where "error" is a legal shift action */ + for yyp >= len(YYS) { + yyn = YYPACT[YYS[yyp].yys] + YYERRCODE; + if yyn >= 0 && yyn < YYLAST { + yystate = YYACT[yyn]; /* simulate a shift of "error" */ + if YYCHK[yystate] == YYERRCODE { + goto yystack; + } + } + + /* the current yyp has no shift onn "error", pop stack */ + if Debug >= 2 { + fmt.Printf("error recovery pops state %d, uncovers %d\n", + YYS[yyp].yys, YYS[yyp-1].yys ); + } + yyp--; + } + /* there is no state on the stack with an error shift ... abort */ + goto ret1; + + case 3: /* no shift yet; clobber input char */ + if Debug >= 2 { + fmt.Printf("error recovery discards %s\n", Tokname(yychar)); + } + if yychar == YYEOFCODE { + goto ret1; + } + yychar = -1; + goto yynewstate; /* try again in the same state */ + } + } + + /* reduction by production yyn */ + if Debug >= 2 { + fmt.Printf("reduce %v in:\n\t%v", yyn, Statname(yystate)); + } + + yynt = yyn; + yypt = yyp; + + yyp -= YYR2[yyn]; + YYVAL = YYS[yyp+1]; + + /* consult goto table to find next state */ + yyn = YYR1[yyn]; + yyg = YYPGO[yyn]; + yyj = yyg + YYS[yyp].yys + 1; + + if yyj >= YYLAST { + yystate = YYACT[yyg]; + } else { + yystate = YYACT[yyj]; + if YYCHK[yystate] != -yyn { + yystate = YYACT[yyg]; + } + } + + yyrun(yynt, yypt); + goto yystack; /* stack new state and value */ +} +` -- 2.48.1