yacc.c 57 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420242124222423242424252426242724282429243024312432243324342435243624372438243924402441244224432444244524462447244824492450245124522453245424552456245724582459246024612462246324642465246624672468246924702471247224732474247524762477247824792480248124822483248424852486248724882489249024912492249324942495249624972498249925002501250225032504250525062507250825092510251125122513251425152516251725182519252025212522252325242525252625272528252925302531253225332534253525362537253825392540254125422543254425452546254725482549255025512552255325542555255625572558255925602561256225632564256525662567256825692570257125722573257425752576257725782579258025812582258325842585258625872588258925902591259225932594259525962597259825992600260126022603260426052606260726082609261026112612261326142615261626172618261926202621262226232624262526262627262826292630263126322633263426352636263726382639264026412642264326442645264626472648264926502651265226532654265526562657265826592660266126622663266426652666266726682669267026712672267326742675267626772678267926802681268226832684268526862687268826892690269126922693269426952696269726982699270027012702270327042705270627072708270927102711271227132714271527162717271827192720272127222723272427252726272727282729273027312732273327342735273627372738273927402741274227432744274527462747274827492750275127522753275427552756275727582759276027612762276327642765276627672768276927702771277227732774277527762777277827792780278127822783278427852786278727882789279027912792279327942795279627972798279928002801280228032804280528062807280828092810281128122813281428152816281728182819282028212822282328242825282628272828282928302831283228332834283528362837283828392840284128422843284428452846284728482849285028512852285328542855285628572858285928602861286228632864286528662867286828692870287128722873287428752876287728782879288028812882288328842885288628872888288928902891289228932894289528962897289828992900290129022903290429052906290729082909291029112912291329142915291629172918291929202921292229232924292529262927292829292930293129322933293429352936293729382939294029412942294329442945294629472948294929502951295229532954
  1. /*
  2. * This file is part of the UCB release of Plan 9. It is subject to the license
  3. * terms in the LICENSE file found in the top-level directory of this
  4. * distribution and at http://akaros.cs.berkeley.edu/files/Plan9License. No
  5. * part of the UCB release of Plan 9, including this file, may be copied,
  6. * modified, propagated, or distributed except according to the terms contained
  7. * in the LICENSE file.
  8. */
  9. #include <u.h>
  10. #include <libc.h>
  11. #include <bio.h>
  12. #include <ctype.h>
  13. #define Bungetrune Bungetc /* ok for now. */
  14. /*
  15. * all these are 32 bit
  16. */
  17. #define TBITSET ((32+NTERMS)/32) /* BOTCH?? +31 */
  18. #define BIT(a,i) ((a)[(i)>>5] & (1<<((i)&037)))
  19. #define SETBIT(a,i) ((a)[(i)>>5] |= (1<<((i)&037)))
  20. #define NWORDS(n) (((n)+32)/32)
  21. #define PARSER "/sys/lib/yaccpar"
  22. #define PARSERS "/sys/lib/yaccpars"
  23. #define TEMPNAME "y.tmp.XXXXXX"
  24. #define ACTNAME "y.acts.XXXXXX"
  25. #define OFILE "tab.c"
  26. #define FILEU "output"
  27. #define FILED "tab.h"
  28. #define FILEDEBUG "debug"
  29. enum
  30. {
  31. /*
  32. * the following are adjustable
  33. * according to memory size
  34. */
  35. ACTSIZE = 40000,
  36. MEMSIZE = 40000,
  37. NSTATES = 2000,
  38. NTERMS = 511,
  39. NPROD = 1600,
  40. NNONTERM = 600,
  41. TEMPSIZE = 2000,
  42. CNAMSZ = 10000,
  43. LSETSIZE = 2400,
  44. WSETSIZE = 350,
  45. NAMESIZE = 50,
  46. NTYPES = 63,
  47. ISIZE = 400,
  48. PRIVATE = 0xE000, /* unicode private use */
  49. /* relationships which must hold:
  50. TBITSET ints must hold NTERMS+1 bits...
  51. WSETSIZE >= NNONTERM
  52. LSETSIZE >= NNONTERM
  53. TEMPSIZE >= NTERMS + NNONTERM + 1
  54. TEMPSIZE >= NSTATES
  55. */
  56. NTBASE = 010000,
  57. ERRCODE = 8190,
  58. ACCEPTCODE = 8191,
  59. NOASC = 0, /* no assoc. */
  60. LASC = 1, /* left assoc. */
  61. RASC = 2, /* right assoc. */
  62. BASC = 3, /* binary assoc. */
  63. /* flags for state generation */
  64. DONE = 0,
  65. MUSTDO = 1,
  66. MUSTLOOKAHEAD = 2,
  67. /* flags for a rule having an action, and being reduced */
  68. ACTFLAG = 04,
  69. REDFLAG = 010,
  70. /* output parser flags */
  71. YYFLAG1 = -1000,
  72. /* parse tokens */
  73. IDENTIFIER = PRIVATE,
  74. MARK,
  75. TERM,
  76. LEFT,
  77. RIGHT,
  78. BINARY,
  79. PREC,
  80. LCURLY,
  81. IDENTCOLON,
  82. NUMBER,
  83. START,
  84. TYPEDEF,
  85. TYPENAME,
  86. UNION,
  87. ENDFILE = 0,
  88. EMPTY = 1,
  89. WHOKNOWS = 0,
  90. OK = 1,
  91. NOMORE = -1000,
  92. };
  93. /* macros for getting associativity and precedence levels */
  94. #define ASSOC(i) ((i)&03)
  95. #define PLEVEL(i) (((i)>>4)&077)
  96. #define TYPE(i) (((i)>>10)&077)
  97. /* macros for setting associativity and precedence levels */
  98. #define SETASC(i,j) i |= j
  99. #define SETPLEV(i,j) i |= (j<<4)
  100. #define SETTYPE(i,j) i |= (j<<10)
  101. /* looping macros */
  102. #define TLOOP(i) for(i=1; i<=ntokens; i++)
  103. #define NTLOOP(i) for(i=0; i<=nnonter; i++)
  104. #define PLOOP(s,i) for(i=s; i<nprod; i++)
  105. #define SLOOP(i) for(i=0; i<nstate; i++)
  106. #define WSBUMP(x) x++
  107. #define WSLOOP(s,j) for(j=s; j<cwp; j++)
  108. #define ITMLOOP(i,p,q) for(q=pstate[i+1], p=pstate[i]; p<q; p++)
  109. #define SETLOOP(i) for(i=0; i<tbitset; i++)
  110. /* command to clobber tempfiles after use */
  111. #define ZAPFILE(x) if(x) remove(x)
  112. /* I/O descriptors */
  113. Biobuf* faction; /* file for saving actions */
  114. Biobuf* fdefine; /* file for #defines */
  115. Biobuf* fdebug; /* y.debug for strings for debugging */
  116. Biobuf* ftable; /* y.tab.c file */
  117. Biobuf* ftemp; /* tempfile to pass 2 */
  118. Biobuf* finput; /* input file */
  119. Biobuf* foutput; /* y.output file */
  120. /* communication variables between various I/O routines */
  121. char* infile; /* input file name */
  122. int numbval; /* value of an input number */
  123. char tokname[NAMESIZE+UTFmax+1]; /* input token name, slop for runes and 0 */
  124. /* structure declarations */
  125. typedef
  126. struct
  127. {
  128. int lset[TBITSET];
  129. } Lkset;
  130. typedef
  131. struct
  132. {
  133. int* pitem;
  134. Lkset* look;
  135. } Item;
  136. typedef
  137. struct
  138. {
  139. char* name;
  140. int value;
  141. } Symb;
  142. typedef
  143. struct
  144. {
  145. int* pitem;
  146. int flag;
  147. Lkset ws;
  148. } Wset;
  149. /* storage of names */
  150. char cnames[CNAMSZ]; /* place where token and nonterminal names are stored */
  151. int cnamsz = CNAMSZ; /* size of cnames */
  152. char* cnamp = cnames; /* place where next name is to be put in */
  153. int ndefout = 4; /* number of defined symbols output */
  154. char* tempname;
  155. char* actname;
  156. char ttempname[] = TEMPNAME;
  157. char tactname[] = ACTNAME;
  158. char* parser = PARSER;
  159. char* yydebug;
  160. /* storage of types */
  161. int ntypes; /* number of types defined */
  162. char* typeset[NTYPES]; /* pointers to type tags */
  163. /* token information */
  164. int ntokens = 0 ; /* number of tokens */
  165. Symb tokset[NTERMS];
  166. int toklev[NTERMS]; /* vector with the precedence of the terminals */
  167. /* nonterminal information */
  168. int nnonter = -1; /* the number of nonterminals */
  169. Symb nontrst[NNONTERM];
  170. int start; /* start symbol */
  171. /* assigned token type values */
  172. int extval = 0;
  173. char* ytabc = OFILE; /* name of y.tab.c */
  174. /* grammar rule information */
  175. int mem0[MEMSIZE] ; /* production storage */
  176. int* mem = mem0;
  177. int nprod = 1; /* number of productions */
  178. int* prdptr[NPROD]; /* pointers to descriptions of productions */
  179. int levprd[NPROD]; /* precedence levels for the productions */
  180. int rlines[NPROD]; /* line number for this rule */
  181. /* state information */
  182. int nstate = 0; /* number of states */
  183. Item* pstate[NSTATES+2]; /* pointers to the descriptions of the states */
  184. int tystate[NSTATES]; /* contains type information about the states */
  185. int defact[NSTATES]; /* the default actions of states */
  186. int tstates[NTERMS]; /* states generated by terminal gotos */
  187. int ntstates[NNONTERM]; /* states generated by nonterminal gotos */
  188. int mstates[NSTATES]; /* chain of overflows of term/nonterm generation lists */
  189. int lastred; /* the number of the last reduction of a state */
  190. /* lookahead set information */
  191. Lkset lkst[LSETSIZE];
  192. int nolook; /* flag to turn off lookahead computations */
  193. int tbitset; /* size of lookahead sets */
  194. int nlset = 0; /* next lookahead set index */
  195. int nolook = 0; /* flag to suppress lookahead computations */
  196. Lkset clset; /* temporary storage for lookahead computations */
  197. /* working set information */
  198. Wset wsets[WSETSIZE];
  199. Wset* cwp;
  200. /* storage for action table */
  201. int amem[ACTSIZE]; /* action table storage */
  202. int* memp = amem; /* next free action table position */
  203. int indgo[NSTATES]; /* index to the stored goto table */
  204. /* temporary vector, indexable by states, terms, or ntokens */
  205. int temp1[TEMPSIZE]; /* temporary storage, indexed by terms + ntokens or states */
  206. int lineno = 1; /* current input line number */
  207. int fatfl = 1; /* if on, error is fatal */
  208. int nerrors = 0; /* number of errors */
  209. /* statistics collection variables */
  210. int zzgoent;
  211. int zzgobest;
  212. int zzacent;
  213. int zzexcp;
  214. int zzclose;
  215. int zzrrconf;
  216. int zzsrconf;
  217. int* ggreed = lkst[0].lset;
  218. int* pgo = wsets[0].ws.lset;
  219. int* yypgo = &nontrst[0].value;
  220. int maxspr = 0; /* maximum spread of any entry */
  221. int maxoff = 0; /* maximum offset into a array */
  222. int* pmem = mem0;
  223. int* maxa;
  224. int nxdb = 0;
  225. int adb = 0;
  226. /* storage for information about the nonterminals */
  227. int** pres[NNONTERM+2]; /* vector of pointers to productions yielding each nonterminal */
  228. Lkset* pfirst[NNONTERM+2]; /* vector of pointers to first sets for each nonterminal */
  229. int pempty[NNONTERM+1]; /* vector of nonterminals nontrivially deriving e */
  230. /* random stuff picked out from between functions */
  231. int indebug = 0;
  232. Wset* zzcwp = wsets;
  233. int zzgoent = 0;
  234. int zzgobest = 0;
  235. int zzacent = 0;
  236. int zzexcp = 0;
  237. int zzclose = 0;
  238. int zzsrconf = 0;
  239. int* zzmemsz = mem0;
  240. int zzrrconf = 0;
  241. int pidebug = 0; /* debugging flag for putitem */
  242. int gsdebug = 0;
  243. int cldebug = 0; /* debugging flag for closure */
  244. int pkdebug = 0;
  245. int g2debug = 0;
  246. struct
  247. {
  248. char* name;
  249. int32_t value;
  250. } resrv[] =
  251. {
  252. "binary", BINARY,
  253. "left", LEFT,
  254. "nonassoc", BINARY,
  255. "prec", PREC,
  256. "right", RIGHT,
  257. "start", START,
  258. "term", TERM,
  259. "token", TERM,
  260. "type", TYPEDEF,
  261. "union", UNION,
  262. 0,
  263. };
  264. /* define functions */
  265. void main(int, char**);
  266. void others(void);
  267. char* chcopy(char*, char*);
  268. char* writem(int*);
  269. char* symnam(int);
  270. void summary(void);
  271. void error(char*, ...);
  272. void aryfil(int*, int, int);
  273. int setunion(int*, int*);
  274. void prlook(Lkset*);
  275. void cpres(void);
  276. void cpfir(void);
  277. int state(int);
  278. void putitem(int*, Lkset*);
  279. void cempty(void);
  280. void stagen(void);
  281. void closure(int);
  282. Lkset* flset(Lkset*);
  283. void cleantmp(void);
  284. void intr(void);
  285. void setup(int, char**);
  286. void finact(void);
  287. int defin(int, char*);
  288. void defout(int);
  289. char* cstash(char*);
  290. int32_t gettok(void);
  291. int fdtype(int);
  292. int chfind(int, char*);
  293. void cpyunion(void);
  294. void cpycode(void);
  295. int skipcom(void);
  296. void cpyact(int);
  297. void openup(char*, int, int, int, char*);
  298. void output(void);
  299. int apack(int*, int);
  300. void go2out(void);
  301. void go2gen(int);
  302. void precftn(int, int, int);
  303. void wract(int);
  304. void wrstate(int);
  305. void warray(char*, int*, int);
  306. void hideprod(void);
  307. void callopt(void);
  308. void gin(int);
  309. void stin(int);
  310. int nxti(void);
  311. void osummary(void);
  312. void aoutput(void);
  313. void arout(char*, int*, int);
  314. int gtnm(void);
  315. void
  316. main(int argc, char *argv[])
  317. {
  318. setup(argc, argv); /* initialize and read productions */
  319. tbitset = NWORDS(ntokens);
  320. cpres(); /* make table of which productions yield a given nonterminal */
  321. cempty(); /* make a table of which nonterminals can match the empty string */
  322. cpfir(); /* make a table of firsts of nonterminals */
  323. stagen(); /* generate the states */
  324. output(); /* write the states and the tables */
  325. go2out();
  326. hideprod();
  327. summary();
  328. callopt();
  329. others();
  330. exits(0);
  331. }
  332. /*
  333. * put out other arrays, copy the parsers
  334. */
  335. void
  336. others(void)
  337. {
  338. int c, i, j;
  339. finput = Bopen(parser, OREAD);
  340. if(finput == 0)
  341. error("cannot find parser %s", parser);
  342. warray("yyr1", levprd, nprod);
  343. aryfil(temp1, nprod, 0);
  344. PLOOP(1, i)
  345. temp1[i] = prdptr[i+1]-prdptr[i]-2;
  346. warray("yyr2", temp1, nprod);
  347. aryfil(temp1, nstate, -1000);
  348. TLOOP(i)
  349. for(j=tstates[i]; j!=0; j=mstates[j])
  350. temp1[j] = i;
  351. NTLOOP(i)
  352. for(j=ntstates[i]; j!=0; j=mstates[j])
  353. temp1[j] = -i;
  354. warray("yychk", temp1, nstate);
  355. warray("yydef", defact, nstate);
  356. /* put out token translation tables */
  357. /* table 1 has 0-256 */
  358. aryfil(temp1, 256, 0);
  359. c = 0;
  360. TLOOP(i) {
  361. j = tokset[i].value;
  362. if(j >= 0 && j < 256) {
  363. if(temp1[j]) {
  364. print("yacc bug -- cant have 2 different Ts with same value\n");
  365. print(" %s and %s\n", tokset[i].name, tokset[temp1[j]].name);
  366. nerrors++;
  367. }
  368. temp1[j] = i;
  369. if(j > c)
  370. c = j;
  371. }
  372. }
  373. warray("yytok1", temp1, c+1);
  374. /* table 2 has PRIVATE-PRIVATE+256 */
  375. aryfil(temp1, 256, 0);
  376. c = 0;
  377. TLOOP(i) {
  378. j = tokset[i].value - PRIVATE;
  379. if(j >= 0 && j < 256) {
  380. if(temp1[j]) {
  381. print("yacc bug -- cant have 2 different Ts with same value\n");
  382. print(" %s and %s\n", tokset[i].name, tokset[temp1[j]].name);
  383. nerrors++;
  384. }
  385. temp1[j] = i;
  386. if(j > c)
  387. c = j;
  388. }
  389. }
  390. warray("yytok2", temp1, c+1);
  391. /* table 3 has everything else */
  392. Bprint(ftable, "int32_t yytok3[] =\n{\n");
  393. c = 0;
  394. TLOOP(i) {
  395. j = tokset[i].value;
  396. if(j >= 0 && j < 256)
  397. continue;
  398. if(j >= PRIVATE && j < 256+PRIVATE)
  399. continue;
  400. Bprint(ftable, "%4d,%4d,", j, i);
  401. c++;
  402. if(c%5 == 0)
  403. Bprint(ftable, "\n");
  404. }
  405. Bprint(ftable, "%4d\n};\n", 0);
  406. /* copy parser text */
  407. while((c=Bgetrune(finput)) != Beof) {
  408. if(c == '$') {
  409. if((c = Bgetrune(finput)) != 'A')
  410. Bputrune(ftable, '$');
  411. else { /* copy actions */
  412. faction = Bopen(actname, OREAD);
  413. if(faction == 0)
  414. error("cannot reopen action tempfile");
  415. while((c=Bgetrune(faction)) != Beof)
  416. Bputrune(ftable, c);
  417. Bterm(faction);
  418. ZAPFILE(actname);
  419. c = Bgetrune(finput);
  420. }
  421. }
  422. Bputrune(ftable, c);
  423. }
  424. Bterm(ftable);
  425. }
  426. /*
  427. * copies string q into p, returning next free char ptr
  428. */
  429. char*
  430. chcopy(char* p, char* q)
  431. {
  432. int c;
  433. while(c = *q) {
  434. if(c == '"')
  435. *p++ = '\\';
  436. *p++ = c;
  437. q++;
  438. }
  439. *p = 0;
  440. return p;
  441. }
  442. /*
  443. * creates output string for item pointed to by pp
  444. */
  445. char*
  446. writem(int *pp)
  447. {
  448. int i,*p;
  449. static char sarr[ISIZE];
  450. char* q;
  451. for(p=pp; *p>0; p++)
  452. ;
  453. p = prdptr[-*p];
  454. q = chcopy(sarr, nontrst[*p-NTBASE].name);
  455. q = chcopy(q, ": ");
  456. for(;;) {
  457. *q = ' ';
  458. p++;
  459. if(p == pp)
  460. *q = '.';
  461. q++;
  462. *q = '\0';
  463. i = *p;
  464. if(i <= 0)
  465. break;
  466. q = chcopy(q, symnam(i));
  467. if(q > &sarr[ISIZE-30])
  468. error("item too big");
  469. }
  470. /* an item calling for a reduction */
  471. i = *pp;
  472. if(i < 0 ) {
  473. q = chcopy(q, " (");
  474. sprint(q, "%d)", -i);
  475. }
  476. return sarr;
  477. }
  478. /*
  479. * return a pointer to the name of symbol i
  480. */
  481. char*
  482. symnam(int i)
  483. {
  484. char* cp;
  485. cp = (i >= NTBASE)? nontrst[i-NTBASE].name: tokset[i].name;
  486. if(*cp == ' ')
  487. cp++;
  488. return cp;
  489. }
  490. /*
  491. * output the summary on y.output
  492. */
  493. void
  494. summary(void)
  495. {
  496. if(foutput != 0) {
  497. Bprint(foutput, "\n%d/%d terminals, %d/%d nonterminals\n",
  498. ntokens, NTERMS, nnonter, NNONTERM);
  499. Bprint(foutput, "%d/%d grammar rules, %d/%d states\n",
  500. nprod, NPROD, nstate, NSTATES);
  501. Bprint(foutput, "%d shift/reduce, %d reduce/reduce conflicts reported\n",
  502. zzsrconf, zzrrconf);
  503. Bprint(foutput, "%d/%d working sets used\n",
  504. (int)(zzcwp-wsets), WSETSIZE);
  505. Bprint(foutput, "memory: states,etc. %d/%d, parser %d/%d\n",
  506. (int)(zzmemsz-mem0), MEMSIZE, (int)(memp-amem), ACTSIZE);
  507. Bprint(foutput, "%d/%d distinct lookahead sets\n", nlset, LSETSIZE);
  508. Bprint(foutput, "%d extra closures\n", zzclose - 2*nstate);
  509. Bprint(foutput, "%d shift entries, %d exceptions\n", zzacent, zzexcp);
  510. Bprint(foutput, "%d goto entries\n", zzgoent);
  511. Bprint(foutput, "%d entries saved by goto default\n", zzgobest);
  512. }
  513. if(zzsrconf != 0 || zzrrconf != 0) {
  514. print("\nconflicts: ");
  515. if(zzsrconf)
  516. print("%d shift/reduce", zzsrconf);
  517. if(zzsrconf && zzrrconf)
  518. print(", ");
  519. if(zzrrconf)
  520. print("%d reduce/reduce", zzrrconf);
  521. print("\n");
  522. }
  523. if(ftemp != 0) {
  524. Bterm(ftemp);
  525. ftemp = 0;
  526. }
  527. if(fdefine != 0) {
  528. Bterm(fdefine);
  529. fdefine = 0;
  530. }
  531. }
  532. /*
  533. * write out error comment -- NEEDS WORK
  534. */
  535. void
  536. error(char *s, ...)
  537. {
  538. nerrors++;
  539. fprint(2, "\n fatal error:");
  540. fprint(2, s, (&s)[1]);
  541. fprint(2, ", %s:%d\n", infile, lineno);
  542. if(!fatfl)
  543. return;
  544. summary();
  545. cleantmp();
  546. exits("error");
  547. }
  548. /*
  549. * set elements 0 through n-1 to c
  550. */
  551. void
  552. aryfil(int *v, int n, int c)
  553. {
  554. int i;
  555. for(i=0; i<n; i++)
  556. v[i] = c;
  557. }
  558. /*
  559. * set a to the union of a and b
  560. * return 1 if b is not a subset of a, 0 otherwise
  561. */
  562. int
  563. setunion(int *a, int *b)
  564. {
  565. int i, x, sub;
  566. sub = 0;
  567. SETLOOP(i) {
  568. x = *a;
  569. *a |= *b;
  570. if(*a != x)
  571. sub = 1;
  572. a++;
  573. b++;
  574. }
  575. return sub;
  576. }
  577. void
  578. prlook(Lkset* p)
  579. {
  580. int j, *pp;
  581. pp = p->lset;
  582. if(pp == 0)
  583. Bprint(foutput, "\tNULL");
  584. else {
  585. Bprint(foutput, " { ");
  586. TLOOP(j)
  587. if(BIT(pp,j))
  588. Bprint(foutput, "%s ", symnam(j));
  589. Bprint(foutput, "}");
  590. }
  591. }
  592. /*
  593. * compute an array with the beginnings of productions yielding given nonterminals
  594. * The array pres points to these lists
  595. * the array pyield has the lists: the total size is only NPROD+1
  596. */
  597. void
  598. cpres(void)
  599. {
  600. int c, j, i, **pmem;
  601. static int *pyield[NPROD];
  602. pmem = pyield;
  603. NTLOOP(i) {
  604. c = i+NTBASE;
  605. pres[i] = pmem;
  606. fatfl = 0; /* make undefined symbols nonfatal */
  607. PLOOP(0, j)
  608. if(*prdptr[j] == c)
  609. *pmem++ = prdptr[j]+1;
  610. if(pres[i] == pmem)
  611. error("nonterminal %s not defined!", nontrst[i].name);
  612. }
  613. pres[i] = pmem;
  614. fatfl = 1;
  615. if(nerrors) {
  616. summary();
  617. cleantmp();
  618. exits("error");
  619. }
  620. if(pmem != &pyield[nprod])
  621. error("internal Yacc error: pyield %d", pmem-&pyield[nprod]);
  622. }
  623. /*
  624. * compute an array with the first of nonterminals
  625. */
  626. void
  627. cpfir(void)
  628. {
  629. int *p, **s, i, **t, ch, changes;
  630. zzcwp = &wsets[nnonter];
  631. NTLOOP(i) {
  632. aryfil(wsets[i].ws.lset, tbitset, 0);
  633. t = pres[i+1];
  634. /* initially fill the sets */
  635. for(s=pres[i]; s<t; ++s)
  636. for(p = *s; (ch = *p) > 0; ++p) {
  637. if(ch < NTBASE) {
  638. SETBIT(wsets[i].ws.lset, ch);
  639. break;
  640. }
  641. if(!pempty[ch-NTBASE])
  642. break;
  643. }
  644. }
  645. /* now, reflect transitivity */
  646. changes = 1;
  647. while(changes) {
  648. changes = 0;
  649. NTLOOP(i) {
  650. t = pres[i+1];
  651. for(s = pres[i]; s < t; ++s)
  652. for(p = *s; (ch = (*p-NTBASE)) >= 0; ++p) {
  653. changes |= setunion(wsets[i].ws.lset, wsets[ch].ws.lset);
  654. if(!pempty[ch])
  655. break;
  656. }
  657. }
  658. }
  659. NTLOOP(i)
  660. pfirst[i] = flset(&wsets[i].ws);
  661. if(!indebug)
  662. return;
  663. if(foutput != 0)
  664. NTLOOP(i) {
  665. Bprint(foutput, "\n%s: ", nontrst[i].name);
  666. prlook(pfirst[i]);
  667. Bprint(foutput, " %d\n", pempty[i]);
  668. }
  669. }
  670. /*
  671. * sorts last state,and sees if it equals earlier ones. returns state number
  672. */
  673. int
  674. state(int c)
  675. {
  676. Item *p1, *p2, *k, *l, *q1, *q2;
  677. int size1, size2, i;
  678. p1 = pstate[nstate];
  679. p2 = pstate[nstate+1];
  680. if(p1 == p2)
  681. return 0; /* null state */
  682. /* sort the items */
  683. for(k = p2-1; k > p1; k--) /* make k the biggest */
  684. for(l = k-1; l >= p1; --l)
  685. if(l->pitem > k->pitem) {
  686. int *s;
  687. Lkset *ss;
  688. s = k->pitem;
  689. k->pitem = l->pitem;
  690. l->pitem = s;
  691. ss = k->look;
  692. k->look = l->look;
  693. l->look = ss;
  694. }
  695. size1 = p2 - p1; /* size of state */
  696. for(i = (c>=NTBASE)? ntstates[c-NTBASE]: tstates[c]; i != 0; i = mstates[i]) {
  697. /* get ith state */
  698. q1 = pstate[i];
  699. q2 = pstate[i+1];
  700. size2 = q2 - q1;
  701. if(size1 != size2)
  702. continue;
  703. k = p1;
  704. for(l = q1; l < q2; l++) {
  705. if(l->pitem != k->pitem)
  706. break;
  707. k++;
  708. }
  709. if(l != q2)
  710. continue;
  711. /* found it */
  712. pstate[nstate+1] = pstate[nstate]; /* delete last state */
  713. /* fix up lookaheads */
  714. if(nolook)
  715. return i;
  716. for(l = q1, k = p1; l < q2; ++l, ++k ) {
  717. int s;
  718. SETLOOP(s)
  719. clset.lset[s] = l->look->lset[s];
  720. if(setunion(clset.lset, k->look->lset)) {
  721. tystate[i] = MUSTDO;
  722. /* register the new set */
  723. l->look = flset( &clset );
  724. }
  725. }
  726. return i;
  727. }
  728. /* state is new */
  729. if(nolook)
  730. error("yacc state/nolook error");
  731. pstate[nstate+2] = p2;
  732. if(nstate+1 >= NSTATES)
  733. error("too many states");
  734. if(c >= NTBASE) {
  735. mstates[nstate] = ntstates[c-NTBASE];
  736. ntstates[c-NTBASE] = nstate;
  737. } else {
  738. mstates[nstate] = tstates[c];
  739. tstates[c] = nstate;
  740. }
  741. tystate[nstate] = MUSTDO;
  742. return nstate++;
  743. }
  744. void
  745. putitem(int *ptr, Lkset *lptr)
  746. {
  747. Item *j;
  748. if(pidebug && foutput != 0)
  749. Bprint(foutput, "putitem(%s), state %d\n", writem(ptr), nstate);
  750. j = pstate[nstate+1];
  751. j->pitem = ptr;
  752. if(!nolook)
  753. j->look = flset(lptr);
  754. pstate[nstate+1] = ++j;
  755. if((int*)j > zzmemsz) {
  756. zzmemsz = (int*)j;
  757. if(zzmemsz >= &mem0[MEMSIZE])
  758. error("out of state space");
  759. }
  760. }
  761. /*
  762. * mark nonterminals which derive the empty string
  763. * also, look for nonterminals which don't derive any token strings
  764. */
  765. void
  766. cempty(void)
  767. {
  768. int i, *p;
  769. /* first, use the array pempty to detect productions that can never be reduced */
  770. /* set pempty to WHONOWS */
  771. aryfil(pempty, nnonter+1, WHOKNOWS);
  772. /* now, look at productions, marking nonterminals which derive something */
  773. more:
  774. PLOOP(0, i) {
  775. if(pempty[*prdptr[i] - NTBASE])
  776. continue;
  777. for(p = prdptr[i]+1; *p >= 0; ++p)
  778. if(*p >= NTBASE && pempty[*p-NTBASE] == WHOKNOWS)
  779. break;
  780. /* production can be derived */
  781. if(*p < 0) {
  782. pempty[*prdptr[i]-NTBASE] = OK;
  783. goto more;
  784. }
  785. }
  786. /* now, look at the nonterminals, to see if they are all OK */
  787. NTLOOP(i) {
  788. /* the added production rises or falls as the start symbol ... */
  789. if(i == 0)
  790. continue;
  791. if(pempty[i] != OK) {
  792. fatfl = 0;
  793. error("nonterminal %s never derives any token string", nontrst[i].name);
  794. }
  795. }
  796. if(nerrors) {
  797. summary();
  798. cleantmp();
  799. exits("error");
  800. }
  801. /* now, compute the pempty array, to see which nonterminals derive the empty string */
  802. /* set pempty to WHOKNOWS */
  803. aryfil( pempty, nnonter+1, WHOKNOWS);
  804. /* loop as int32_t as we keep finding empty nonterminals */
  805. again:
  806. PLOOP(1, i) {
  807. /* not known to be empty */
  808. if(pempty[*prdptr[i]-NTBASE] == WHOKNOWS) {
  809. for(p = prdptr[i]+1; *p >= NTBASE && pempty[*p-NTBASE] == EMPTY ; ++p)
  810. ;
  811. /* we have a nontrivially empty nonterminal */
  812. if(*p < 0) {
  813. pempty[*prdptr[i]-NTBASE] = EMPTY;
  814. /* got one ... try for another */
  815. goto again;
  816. }
  817. }
  818. }
  819. }
  820. /*
  821. * generate the states
  822. */
  823. void
  824. stagen(void)
  825. {
  826. int c, i, j, more;
  827. Wset *p, *q;
  828. /* initialize */
  829. nstate = 0;
  830. /* THIS IS FUNNY from the standpoint of portability
  831. * it represents the magic moment when the mem0 array, which has
  832. * been holding the productions, starts to hold item pointers, of a
  833. * different type...
  834. * someday, alloc should be used to allocate all this stuff... for now, we
  835. * accept that if pointers don't fit in integers, there is a problem...
  836. */
  837. pstate[0] = pstate[1] = (Item*)mem;
  838. aryfil(clset.lset, tbitset, 0);
  839. putitem(prdptr[0]+1, &clset);
  840. tystate[0] = MUSTDO;
  841. nstate = 1;
  842. pstate[2] = pstate[1];
  843. aryfil(amem, ACTSIZE, 0);
  844. /* now, the main state generation loop */
  845. for(more=1; more;) {
  846. more = 0;
  847. SLOOP(i) {
  848. if(tystate[i] != MUSTDO)
  849. continue;
  850. tystate[i] = DONE;
  851. aryfil(temp1, nnonter+1, 0);
  852. /* take state i, close it, and do gotos */
  853. closure(i);
  854. /* generate goto's */
  855. WSLOOP(wsets, p) {
  856. if(p->flag)
  857. continue;
  858. p->flag = 1;
  859. c = *(p->pitem);
  860. if(c <= 1) {
  861. if(pstate[i+1]-pstate[i] <= p-wsets)
  862. tystate[i] = MUSTLOOKAHEAD;
  863. continue;
  864. }
  865. /* do a goto on c */
  866. WSLOOP(p, q)
  867. /* this item contributes to the goto */
  868. if(c == *(q->pitem)) {
  869. putitem(q->pitem+1, &q->ws);
  870. q->flag = 1;
  871. }
  872. if(c < NTBASE)
  873. state(c); /* register new state */
  874. else
  875. temp1[c-NTBASE] = state(c);
  876. }
  877. if(gsdebug && foutput != 0) {
  878. Bprint(foutput, "%d: ", i);
  879. NTLOOP(j)
  880. if(temp1[j])
  881. Bprint(foutput, "%s %d, ",
  882. nontrst[j].name, temp1[j]);
  883. Bprint(foutput, "\n");
  884. }
  885. indgo[i] = apack(&temp1[1], nnonter-1) - 1;
  886. /* do some more */
  887. more = 1;
  888. }
  889. }
  890. }
  891. /*
  892. * generate the closure of state i
  893. */
  894. void
  895. closure(int i)
  896. {
  897. Wset *u, *v;
  898. Item *p, *q;
  899. int c, ch, work, k, *pi, **s, **t;
  900. zzclose++;
  901. /* first, copy kernel of state i to wsets */
  902. cwp = wsets;
  903. ITMLOOP(i, p, q) {
  904. cwp->pitem = p->pitem;
  905. cwp->flag = 1; /* this item must get closed */
  906. SETLOOP(k)
  907. cwp->ws.lset[k] = p->look->lset[k];
  908. WSBUMP(cwp);
  909. }
  910. /* now, go through the loop, closing each item */
  911. work = 1;
  912. while(work) {
  913. work = 0;
  914. WSLOOP(wsets, u) {
  915. if(u->flag == 0)
  916. continue;
  917. /* dot is before c */
  918. c = *(u->pitem);
  919. if(c < NTBASE) {
  920. u->flag = 0;
  921. /* only interesting case is where . is before nonterminal */
  922. continue;
  923. }
  924. /* compute the lookahead */
  925. aryfil(clset.lset, tbitset, 0);
  926. /* find items involving c */
  927. WSLOOP(u, v)
  928. if(v->flag == 1 && *(pi=v->pitem) == c) {
  929. v->flag = 0;
  930. if(nolook)
  931. continue;
  932. while((ch = *++pi) > 0) {
  933. /* terminal symbol */
  934. if(ch < NTBASE) {
  935. SETBIT(clset.lset, ch);
  936. break;
  937. }
  938. /* nonterminal symbol */
  939. setunion(clset.lset, pfirst[ch-NTBASE]->lset);
  940. if(!pempty[ch-NTBASE])
  941. break;
  942. }
  943. if(ch <= 0)
  944. setunion(clset.lset, v->ws.lset);
  945. }
  946. /*
  947. * now loop over productions derived from c
  948. * c is now nonterminal number
  949. */
  950. c -= NTBASE;
  951. t = pres[c+1];
  952. for(s = pres[c]; s < t; ++s) {
  953. /*
  954. * put these items into the closure
  955. * is the item there
  956. */
  957. WSLOOP(wsets, v)
  958. /* yes, it is there */
  959. if(v->pitem == *s) {
  960. if(nolook)
  961. goto nexts;
  962. if(setunion(v->ws.lset, clset.lset))
  963. v->flag = work = 1;
  964. goto nexts;
  965. }
  966. /* not there; make a new entry */
  967. if(cwp-wsets+1 >= WSETSIZE)
  968. error( "working set overflow");
  969. cwp->pitem = *s;
  970. cwp->flag = 1;
  971. if(!nolook) {
  972. work = 1;
  973. SETLOOP(k) cwp->ws.lset[k] = clset.lset[k];
  974. }
  975. WSBUMP(cwp);
  976. nexts:;
  977. }
  978. }
  979. }
  980. /* have computed closure; flags are reset; return */
  981. if(cwp > zzcwp)
  982. zzcwp = cwp;
  983. if(cldebug && foutput != 0) {
  984. Bprint(foutput, "\nState %d, nolook = %d\n", i, nolook);
  985. WSLOOP(wsets, u) {
  986. if(u->flag)
  987. Bprint(foutput, "flag set!\n");
  988. u->flag = 0;
  989. Bprint(foutput, "\t%s", writem(u->pitem));
  990. prlook(&u->ws);
  991. Bprint(foutput, "\n");
  992. }
  993. }
  994. }
  995. /*
  996. * decide if the lookahead set pointed to by p is known
  997. * return pointer to a perminent location for the set
  998. */
  999. Lkset*
  1000. flset(Lkset *p)
  1001. {
  1002. Lkset *q;
  1003. int *u, *v, *w, j;
  1004. for(q = &lkst[nlset]; q-- > lkst;) {
  1005. u = p->lset;
  1006. v = q->lset;
  1007. w = &v[tbitset];
  1008. while(v < w)
  1009. if(*u++ != *v++)
  1010. goto more;
  1011. /* we have matched */
  1012. return q;
  1013. more:;
  1014. }
  1015. /* add a new one */
  1016. q = &lkst[nlset++];
  1017. if(nlset >= LSETSIZE)
  1018. error("too many lookahead sets");
  1019. SETLOOP(j)
  1020. q->lset[j] = p->lset[j];
  1021. return q;
  1022. }
  1023. void
  1024. cleantmp(void)
  1025. {
  1026. ZAPFILE(actname);
  1027. ZAPFILE(tempname);
  1028. }
  1029. void
  1030. intr(void)
  1031. {
  1032. cleantmp();
  1033. exits("interrupted");
  1034. }
  1035. void
  1036. usage(void)
  1037. {
  1038. fprint(2, "usage: yacc [-Dn] [-vdS] [-o outputfile] [-s stem] grammar\n");
  1039. exits("usage");
  1040. }
  1041. void
  1042. setup(int argc, char *argv[])
  1043. {
  1044. int32_t c, t;
  1045. int i, j, lev, ty, ytab, *p;
  1046. int vflag, dflag, stem;
  1047. char actnm[8], *stemc, *s, dirbuf[128];
  1048. ytab = 0;
  1049. vflag = 0;
  1050. dflag = 0;
  1051. stem = 0;
  1052. stemc = "y";
  1053. foutput = 0;
  1054. fdefine = 0;
  1055. fdebug = 0;
  1056. ARGBEGIN{
  1057. case 'v':
  1058. case 'V':
  1059. vflag++;
  1060. break;
  1061. case 'D':
  1062. yydebug = EARGF(usage());
  1063. break;
  1064. case 'd':
  1065. dflag++;
  1066. break;
  1067. case 'o':
  1068. ytab++;
  1069. ytabc = EARGF(usage());
  1070. break;
  1071. case 's':
  1072. stem++;
  1073. stemc = ARGF();
  1074. break;
  1075. case 'S':
  1076. parser = PARSERS;
  1077. break;
  1078. default:
  1079. error("illegal option: %c", ARGC());
  1080. }ARGEND
  1081. openup(stemc, dflag, vflag, ytab, ytabc);
  1082. ftemp = Bopen(tempname = mktemp(ttempname), OWRITE);
  1083. faction = Bopen(actname = mktemp(tactname), OWRITE);
  1084. if(ftemp == 0 || faction == 0)
  1085. error("cannot open temp file");
  1086. if(argc < 1)
  1087. error("no input file");
  1088. infile = argv[0];
  1089. if(infile[0] != '/' && getwd(dirbuf, sizeof dirbuf)!=nil){
  1090. i = strlen(infile)+1+strlen(dirbuf)+1+10;
  1091. s = malloc(i);
  1092. if(s != nil){
  1093. snprint(s, i, "%s/%s", dirbuf, infile);
  1094. cleanname(s);
  1095. infile = s;
  1096. }
  1097. }
  1098. finput = Bopen(infile, OREAD);
  1099. if(finput == 0)
  1100. error("cannot open '%s'", argv[0]);
  1101. cnamp = cnames;
  1102. defin(0, "$end");
  1103. extval = PRIVATE; /* tokens start in unicode 'private use' */
  1104. defin(0, "error");
  1105. defin(1, "$accept");
  1106. defin(0, "$unk");
  1107. mem = mem0;
  1108. i = 0;
  1109. for(t = gettok(); t != MARK && t != ENDFILE;)
  1110. switch(t) {
  1111. case ';':
  1112. t = gettok();
  1113. break;
  1114. case START:
  1115. if(gettok() != IDENTIFIER)
  1116. error("bad %%start construction");
  1117. start = chfind(1, tokname);
  1118. t = gettok();
  1119. continue;
  1120. case TYPEDEF:
  1121. if(gettok() != TYPENAME)
  1122. error("bad syntax in %%type");
  1123. ty = numbval;
  1124. for(;;) {
  1125. t = gettok();
  1126. switch(t) {
  1127. case IDENTIFIER:
  1128. if((t=chfind(1, tokname)) < NTBASE) {
  1129. j = TYPE(toklev[t]);
  1130. if(j != 0 && j != ty)
  1131. error("type redeclaration of token %s",
  1132. tokset[t].name);
  1133. else
  1134. SETTYPE(toklev[t], ty);
  1135. } else {
  1136. j = nontrst[t-NTBASE].value;
  1137. if(j != 0 && j != ty)
  1138. error("type redeclaration of nonterminal %s",
  1139. nontrst[t-NTBASE].name );
  1140. else
  1141. nontrst[t-NTBASE].value = ty;
  1142. }
  1143. case ',':
  1144. continue;
  1145. case ';':
  1146. t = gettok();
  1147. default:
  1148. break;
  1149. }
  1150. break;
  1151. }
  1152. continue;
  1153. case UNION:
  1154. /* copy the union declaration to the output */
  1155. cpyunion();
  1156. t = gettok();
  1157. continue;
  1158. case LEFT:
  1159. case BINARY:
  1160. case RIGHT:
  1161. i++;
  1162. case TERM:
  1163. /* nonzero means new prec. and assoc. */
  1164. lev = t-TERM;
  1165. ty = 0;
  1166. /* get identifiers so defined */
  1167. t = gettok();
  1168. /* there is a type defined */
  1169. if(t == TYPENAME) {
  1170. ty = numbval;
  1171. t = gettok();
  1172. }
  1173. for(;;) {
  1174. switch(t) {
  1175. case ',':
  1176. t = gettok();
  1177. continue;
  1178. case ';':
  1179. break;
  1180. case IDENTIFIER:
  1181. j = chfind(0, tokname);
  1182. if(j >= NTBASE)
  1183. error("%s defined earlier as nonterminal", tokname);
  1184. if(lev) {
  1185. if(ASSOC(toklev[j]))
  1186. error("redeclaration of precedence of %s", tokname);
  1187. SETASC(toklev[j], lev);
  1188. SETPLEV(toklev[j], i);
  1189. }
  1190. if(ty) {
  1191. if(TYPE(toklev[j]))
  1192. error("redeclaration of type of %s", tokname);
  1193. SETTYPE(toklev[j],ty);
  1194. }
  1195. t = gettok();
  1196. if(t == NUMBER) {
  1197. tokset[j].value = numbval;
  1198. if(j < ndefout && j > 3)
  1199. error("please define type number of %s earlier",
  1200. tokset[j].name);
  1201. t = gettok();
  1202. }
  1203. continue;
  1204. }
  1205. break;
  1206. }
  1207. continue;
  1208. case LCURLY:
  1209. defout(0);
  1210. cpycode();
  1211. t = gettok();
  1212. continue;
  1213. default:
  1214. error("syntax error");
  1215. }
  1216. if(t == ENDFILE)
  1217. error("unexpected EOF before %%");
  1218. /* t is MARK */
  1219. Bprint(ftable, "extern int yyerrflag;\n");
  1220. Bprint(ftable, "#ifndef YYMAXDEPTH\n");
  1221. Bprint(ftable, "#define YYMAXDEPTH 150\n");
  1222. Bprint(ftable, "#endif\n" );
  1223. if(!ntypes) {
  1224. Bprint(ftable, "#ifndef YYSTYPE\n");
  1225. Bprint(ftable, "#define YYSTYPE int\n");
  1226. Bprint(ftable, "#endif\n");
  1227. }
  1228. Bprint(ftable, "YYSTYPE yylval;\n");
  1229. Bprint(ftable, "YYSTYPE yyval;\n");
  1230. prdptr[0] = mem;
  1231. /* added production */
  1232. *mem++ = NTBASE;
  1233. /* if start is 0, we will overwrite with the lhs of the first rule */
  1234. *mem++ = start;
  1235. *mem++ = 1;
  1236. *mem++ = 0;
  1237. prdptr[1] = mem;
  1238. while((t=gettok()) == LCURLY)
  1239. cpycode();
  1240. if(t != IDENTCOLON)
  1241. error("bad syntax on first rule");
  1242. if(!start)
  1243. prdptr[0][1] = chfind(1, tokname);
  1244. /* read rules */
  1245. while(t != MARK && t != ENDFILE) {
  1246. /* process a rule */
  1247. rlines[nprod] = lineno;
  1248. if(t == '|')
  1249. *mem++ = *prdptr[nprod-1];
  1250. else
  1251. if(t == IDENTCOLON) {
  1252. *mem = chfind(1, tokname);
  1253. if(*mem < NTBASE)
  1254. error("token illegal on LHS of grammar rule");
  1255. mem++;
  1256. } else
  1257. error("illegal rule: missing semicolon or | ?");
  1258. /* read rule body */
  1259. t = gettok();
  1260. more_rule:
  1261. while(t == IDENTIFIER) {
  1262. *mem = chfind(1, tokname);
  1263. if(*mem < NTBASE)
  1264. levprd[nprod] = toklev[*mem];
  1265. mem++;
  1266. t = gettok();
  1267. }
  1268. if(t == PREC) {
  1269. if(gettok() != IDENTIFIER)
  1270. error("illegal %%prec syntax");
  1271. j = chfind(2, tokname);
  1272. if(j >= NTBASE)
  1273. error("nonterminal %s illegal after %%prec",
  1274. nontrst[j-NTBASE].name);
  1275. levprd[nprod] = toklev[j];
  1276. t = gettok();
  1277. }
  1278. if(t == '=') {
  1279. levprd[nprod] |= ACTFLAG;
  1280. Bprint(faction, "\ncase %d:", nprod);
  1281. cpyact(mem-prdptr[nprod]-1);
  1282. Bprint(faction, " break;");
  1283. if((t=gettok()) == IDENTIFIER) {
  1284. /* action within rule... */
  1285. sprint(actnm, "$$%d", nprod);
  1286. /* make it a nonterminal */
  1287. j = chfind(1, actnm);
  1288. /*
  1289. * the current rule will become rule number nprod+1
  1290. * move the contents down, and make room for the null
  1291. */
  1292. for(p = mem; p >= prdptr[nprod]; --p)
  1293. p[2] = *p;
  1294. mem += 2;
  1295. /* enter null production for action */
  1296. p = prdptr[nprod];
  1297. *p++ = j;
  1298. *p++ = -nprod;
  1299. /* update the production information */
  1300. levprd[nprod+1] = levprd[nprod] & ~ACTFLAG;
  1301. levprd[nprod] = ACTFLAG;
  1302. if(++nprod >= NPROD)
  1303. error("more than %d rules", NPROD);
  1304. prdptr[nprod] = p;
  1305. /* make the action appear in the original rule */
  1306. *mem++ = j;
  1307. /* get some more of the rule */
  1308. goto more_rule;
  1309. }
  1310. }
  1311. while(t == ';')
  1312. t = gettok();
  1313. *mem++ = -nprod;
  1314. /* check that default action is reasonable */
  1315. if(ntypes && !(levprd[nprod]&ACTFLAG) && nontrst[*prdptr[nprod]-NTBASE].value) {
  1316. /* no explicit action, LHS has value */
  1317. int tempty;
  1318. tempty = prdptr[nprod][1];
  1319. if(tempty < 0)
  1320. error("must return a value, since LHS has a type");
  1321. else
  1322. if(tempty >= NTBASE)
  1323. tempty = nontrst[tempty-NTBASE].value;
  1324. else
  1325. tempty = TYPE(toklev[tempty]);
  1326. if(tempty != nontrst[*prdptr[nprod]-NTBASE].value)
  1327. error("default action causes potential type clash");
  1328. }
  1329. nprod++;
  1330. if(nprod >= NPROD)
  1331. error("more than %d rules", NPROD);
  1332. prdptr[nprod] = mem;
  1333. levprd[nprod] = 0;
  1334. }
  1335. /* end of all rules */
  1336. defout(1);
  1337. finact();
  1338. if(t == MARK) {
  1339. Bprint(ftable, "\n#line\t%d\t\"%s\"\n", lineno, infile);
  1340. while((c=Bgetrune(finput)) != Beof)
  1341. Bputrune(ftable, c);
  1342. }
  1343. Bterm(finput);
  1344. }
  1345. /*
  1346. * finish action routine
  1347. */
  1348. void
  1349. finact(void)
  1350. {
  1351. Bterm(faction);
  1352. Bprint(ftable, "#define YYEOFCODE %d\n", 1);
  1353. Bprint(ftable, "#define YYERRCODE %d\n", 2);
  1354. }
  1355. /*
  1356. * define s to be a terminal if t=0
  1357. * or a nonterminal if t=1
  1358. */
  1359. int
  1360. defin(int nt, char *s)
  1361. {
  1362. int val;
  1363. Rune rune;
  1364. val = 0;
  1365. if(nt) {
  1366. nnonter++;
  1367. if(nnonter >= NNONTERM)
  1368. error("too many nonterminals, limit %d",NNONTERM);
  1369. nontrst[nnonter].name = cstash(s);
  1370. return NTBASE + nnonter;
  1371. }
  1372. /* must be a token */
  1373. ntokens++;
  1374. if(ntokens >= NTERMS)
  1375. error("too many terminals, limit %d", NTERMS);
  1376. tokset[ntokens].name = cstash(s);
  1377. /* establish value for token */
  1378. /* single character literal */
  1379. if(s[0] == ' ') {
  1380. val = chartorune(&rune, &s[1]);
  1381. if(s[val+1] == 0) {
  1382. val = rune;
  1383. goto out;
  1384. }
  1385. }
  1386. /* escape sequence */
  1387. if(s[0] == ' ' && s[1] == '\\') {
  1388. if(s[3] == 0) {
  1389. /* single character escape sequence */
  1390. switch(s[2]) {
  1391. case 'n': val = '\n'; break;
  1392. case 'r': val = '\r'; break;
  1393. case 'b': val = '\b'; break;
  1394. case 't': val = '\t'; break;
  1395. case 'f': val = '\f'; break;
  1396. case '\'': val = '\''; break;
  1397. case '"': val = '"'; break;
  1398. case '\\': val = '\\'; break;
  1399. default: error("invalid escape");
  1400. }
  1401. goto out;
  1402. }
  1403. /* \nnn sequence */
  1404. if(s[2] >= '0' && s[2] <= '7') {
  1405. if(s[3] < '0' ||
  1406. s[3] > '7' ||
  1407. s[4] < '0' ||
  1408. s[4] > '7' ||
  1409. s[5] != 0)
  1410. error("illegal \\nnn construction");
  1411. val = 64*s[2] + 8*s[3] + s[4] - 73*'0';
  1412. if(val == 0)
  1413. error("'\\000' is illegal");
  1414. goto out;
  1415. }
  1416. error("unknown escape");
  1417. }
  1418. val = extval++;
  1419. out:
  1420. tokset[ntokens].value = val;
  1421. toklev[ntokens] = 0;
  1422. return ntokens;
  1423. }
  1424. /*
  1425. * write out the defines (at the end of the declaration section)
  1426. */
  1427. void
  1428. defout(int last)
  1429. {
  1430. int i, c;
  1431. char sar[NAMESIZE+10];
  1432. for(i=ndefout; i<=ntokens; i++) {
  1433. /* non-literals */
  1434. c = tokset[i].name[0];
  1435. if(c != ' ' && c != '$') {
  1436. Bprint(ftable, "#define %s %d\n",
  1437. tokset[i].name, tokset[i].value);
  1438. if(fdefine)
  1439. Bprint(fdefine, "#define\t%s\t%d\n",
  1440. tokset[i].name, tokset[i].value);
  1441. }
  1442. }
  1443. ndefout = ntokens+1;
  1444. if(last && fdebug) {
  1445. Bprint(fdebug, "char* yytoknames[] =\n{\n");
  1446. TLOOP(i) {
  1447. if(tokset[i].name) {
  1448. chcopy(sar, tokset[i].name);
  1449. Bprint(fdebug, "\t\"%s\",\n", sar);
  1450. continue;
  1451. }
  1452. Bprint(fdebug, "\t0,\n");
  1453. }
  1454. Bprint(fdebug, "};\n");
  1455. }
  1456. }
  1457. char*
  1458. cstash(char *s)
  1459. {
  1460. char *temp;
  1461. temp = cnamp;
  1462. do {
  1463. if(cnamp >= &cnames[cnamsz])
  1464. error("too many characters in id's and literals");
  1465. else
  1466. *cnamp++ = *s;
  1467. } while(*s++);
  1468. return temp;
  1469. }
  1470. int32_t
  1471. gettok(void)
  1472. {
  1473. int32_t c;
  1474. Rune rune;
  1475. int i, base, match, reserve;
  1476. static int peekline;
  1477. begin:
  1478. reserve = 0;
  1479. lineno += peekline;
  1480. peekline = 0;
  1481. c = Bgetrune(finput);
  1482. while(c == ' ' || c == '\n' || c == '\t' || c == '\f') {
  1483. if(c == '\n')
  1484. lineno++;
  1485. c = Bgetrune(finput);
  1486. }
  1487. /* skip comment */
  1488. if(c == '/') {
  1489. lineno += skipcom();
  1490. goto begin;
  1491. }
  1492. switch(c) {
  1493. case Beof:
  1494. return ENDFILE;
  1495. case '{':
  1496. Bungetrune(finput);
  1497. return '=';
  1498. case '<':
  1499. /* get, and look up, a type name (union member name) */
  1500. i = 0;
  1501. while((c=Bgetrune(finput)) != '>' && c >= 0 && c != '\n') {
  1502. rune = c;
  1503. c = runetochar(&tokname[i], &rune);
  1504. if(i < NAMESIZE)
  1505. i += c;
  1506. }
  1507. if(c != '>')
  1508. error("unterminated < ... > clause");
  1509. tokname[i] = 0;
  1510. for(i=1; i<=ntypes; i++)
  1511. if(!strcmp(typeset[i], tokname)) {
  1512. numbval = i;
  1513. return TYPENAME;
  1514. }
  1515. ntypes++;
  1516. numbval = ntypes;
  1517. typeset[numbval] = cstash(tokname);
  1518. return TYPENAME;
  1519. case '"':
  1520. case '\'':
  1521. match = c;
  1522. tokname[0] = ' ';
  1523. i = 1;
  1524. for(;;) {
  1525. c = Bgetrune(finput);
  1526. if(c == '\n' || c <= 0)
  1527. error("illegal or missing ' or \"" );
  1528. if(c == '\\') {
  1529. tokname[i] = '\\';
  1530. if(i < NAMESIZE)
  1531. i++;
  1532. c = Bgetrune(finput);
  1533. } else
  1534. if(c == match)
  1535. break;
  1536. rune = c;
  1537. c = runetochar(&tokname[i], &rune);
  1538. if(i < NAMESIZE)
  1539. i += c;
  1540. }
  1541. break;
  1542. case '%':
  1543. case '\\':
  1544. switch(c = Bgetrune(finput)) {
  1545. case '0': return TERM;
  1546. case '<': return LEFT;
  1547. case '2': return BINARY;
  1548. case '>': return RIGHT;
  1549. case '%':
  1550. case '\\': return MARK;
  1551. case '=': return PREC;
  1552. case '{': return LCURLY;
  1553. default: reserve = 1;
  1554. }
  1555. default:
  1556. /* number */
  1557. if(isdigit(c)) {
  1558. numbval = c-'0';
  1559. base = (c=='0')? 8: 10;
  1560. for(c = Bgetrune(finput); isdigit(c); c = Bgetrune(finput))
  1561. numbval = numbval*base + (c-'0');
  1562. Bungetrune(finput);
  1563. return NUMBER;
  1564. }
  1565. if(islower(c) || isupper(c) || c=='_' || c=='.' || c=='$') {
  1566. i = 0;
  1567. while(islower(c) || isupper(c) || isdigit(c) ||
  1568. c == '-' || c=='_' || c=='.' || c=='$') {
  1569. if(reserve && isupper(c))
  1570. c += 'a'-'A';
  1571. rune = c;
  1572. c = runetochar(&tokname[i], &rune);
  1573. if(i < NAMESIZE)
  1574. i += c;
  1575. c = Bgetrune(finput);
  1576. }
  1577. } else
  1578. return c;
  1579. Bungetrune(finput);
  1580. }
  1581. tokname[i] = 0;
  1582. /* find a reserved word */
  1583. if(reserve) {
  1584. for(c=0; resrv[c].name; c++)
  1585. if(strcmp(tokname, resrv[c].name) == 0)
  1586. return resrv[c].value;
  1587. error("invalid escape, or illegal reserved word: %s", tokname);
  1588. }
  1589. /* look ahead to distinguish IDENTIFIER from IDENTCOLON */
  1590. c = Bgetrune(finput);
  1591. while(c == ' ' || c == '\t'|| c == '\n' || c == '\f' || c == '/') {
  1592. if(c == '\n')
  1593. peekline++;
  1594. /* look for comments */
  1595. if(c == '/')
  1596. peekline += skipcom();
  1597. c = Bgetrune(finput);
  1598. }
  1599. if(c == ':')
  1600. return IDENTCOLON;
  1601. Bungetrune(finput);
  1602. return IDENTIFIER;
  1603. }
  1604. /*
  1605. * determine the type of a symbol
  1606. */
  1607. int
  1608. fdtype(int t)
  1609. {
  1610. int v;
  1611. if(t >= NTBASE)
  1612. v = nontrst[t-NTBASE].value;
  1613. else
  1614. v = TYPE(toklev[t]);
  1615. if(v <= 0)
  1616. error("must specify type for %s", (t>=NTBASE)?
  1617. nontrst[t-NTBASE].name: tokset[t].name);
  1618. return v;
  1619. }
  1620. int
  1621. chfind(int t, char *s)
  1622. {
  1623. int i;
  1624. if(s[0] == ' ')
  1625. t = 0;
  1626. TLOOP(i)
  1627. if(!strcmp(s, tokset[i].name))
  1628. return i;
  1629. NTLOOP(i)
  1630. if(!strcmp(s, nontrst[i].name))
  1631. return NTBASE+i;
  1632. /* cannot find name */
  1633. if(t > 1)
  1634. error("%s should have been defined earlier", s);
  1635. return defin(t, s);
  1636. }
  1637. /*
  1638. * copy the union declaration to the output, and the define file if present
  1639. */
  1640. void
  1641. cpyunion(void)
  1642. {
  1643. int32_t c;
  1644. int level;
  1645. Bprint(ftable, "\n#line\t%d\t\"%s\"\n", lineno, infile);
  1646. Bprint(ftable, "typedef union ");
  1647. if(fdefine != 0)
  1648. Bprint(fdefine, "\ntypedef union ");
  1649. level = 0;
  1650. for(;;) {
  1651. if((c=Bgetrune(finput)) == Beof)
  1652. error("EOF encountered while processing %%union");
  1653. Bputrune(ftable, c);
  1654. if(fdefine != 0)
  1655. Bputrune(fdefine, c);
  1656. switch(c) {
  1657. case '\n':
  1658. lineno++;
  1659. break;
  1660. case '{':
  1661. level++;
  1662. break;
  1663. case '}':
  1664. level--;
  1665. /* we are finished copying */
  1666. if(level == 0) {
  1667. Bprint(ftable, " YYSTYPE;\n");
  1668. if(fdefine != 0)
  1669. Bprint(fdefine, "\tYYSTYPE;\nextern\tYYSTYPE\tyylval;\n");
  1670. return;
  1671. }
  1672. }
  1673. }
  1674. }
  1675. /*
  1676. * copies code between \{ and \}
  1677. */
  1678. void
  1679. cpycode(void)
  1680. {
  1681. int32_t c;
  1682. c = Bgetrune(finput);
  1683. if(c == '\n') {
  1684. c = Bgetrune(finput);
  1685. lineno++;
  1686. }
  1687. Bprint(ftable, "\n#line\t%d\t\"%s\"\n", lineno, infile);
  1688. while(c != Beof) {
  1689. if(c == '\\') {
  1690. if((c=Bgetrune(finput)) == '}')
  1691. return;
  1692. Bputc(ftable, '\\');
  1693. }
  1694. if(c == '%') {
  1695. if((c=Bgetrune(finput)) == '}')
  1696. return;
  1697. Bputc(ftable, '%');
  1698. }
  1699. Bputrune(ftable, c);
  1700. if(c == '\n')
  1701. lineno++;
  1702. c = Bgetrune(finput);
  1703. }
  1704. error("eof before %%}");
  1705. }
  1706. /*
  1707. * skip over comments
  1708. * skipcom is called after reading a '/'
  1709. */
  1710. int
  1711. skipcom(void)
  1712. {
  1713. int32_t c;
  1714. int i;
  1715. /* i is the number of lines skipped */
  1716. i = 0;
  1717. c = Bgetrune(finput);
  1718. if(c == '/'){ /* C++ //: skip to end of line */
  1719. while((c = Bgetrune(finput)) != Beof)
  1720. if(c == '\n')
  1721. return 1;
  1722. }else if(c == '*'){ /* normal C comment */
  1723. while((c = Bgetrune(finput)) != Beof) {
  1724. while(c == '*')
  1725. if((c = Bgetrune(finput)) == '/')
  1726. return i;
  1727. if(c == '\n')
  1728. i++;
  1729. }
  1730. }else
  1731. error("illegal comment");
  1732. error("EOF inside comment");
  1733. return 0;
  1734. }
  1735. /*
  1736. * copy C action to the next ; or closing }
  1737. */
  1738. void
  1739. cpyact(int offset)
  1740. {
  1741. int32_t c;
  1742. int brac, match, j, s, fnd, tok;
  1743. Bprint(faction, "\n#line\t%d\t\"%s\"\n", lineno, infile);
  1744. brac = 0;
  1745. loop:
  1746. c = Bgetrune(finput);
  1747. swt:
  1748. switch(c) {
  1749. case ';':
  1750. if(brac == 0) {
  1751. Bputrune(faction, c);
  1752. return;
  1753. }
  1754. goto lcopy;
  1755. case '{':
  1756. brac++;
  1757. goto lcopy;
  1758. case '$':
  1759. s = 1;
  1760. tok = -1;
  1761. c = Bgetrune(finput);
  1762. /* type description */
  1763. if(c == '<') {
  1764. Bungetrune(finput);
  1765. if(gettok() != TYPENAME)
  1766. error("bad syntax on $<ident> clause");
  1767. tok = numbval;
  1768. c = Bgetrune(finput);
  1769. }
  1770. if(c == '$') {
  1771. Bprint(faction, "yyval");
  1772. /* put out the proper tag... */
  1773. if(ntypes) {
  1774. if(tok < 0)
  1775. tok = fdtype(*prdptr[nprod]);
  1776. Bprint(faction, ".%s", typeset[tok]);
  1777. }
  1778. goto loop;
  1779. }
  1780. if(c == '-') {
  1781. s = -s;
  1782. c = Bgetrune(finput);
  1783. }
  1784. if(isdigit(c)) {
  1785. j = 0;
  1786. while(isdigit(c)) {
  1787. j = j*10 + (c-'0');
  1788. c = Bgetrune(finput);
  1789. }
  1790. Bungetrune(finput);
  1791. j = j*s - offset;
  1792. if(j > 0)
  1793. error("Illegal use of $%d", j+offset);
  1794. dollar:
  1795. Bprint(faction, "yypt[-%d].yyv", -j);
  1796. /* put out the proper tag */
  1797. if(ntypes) {
  1798. if(j+offset <= 0 && tok < 0)
  1799. error("must specify type of $%d", j+offset);
  1800. if(tok < 0)
  1801. tok = fdtype(prdptr[nprod][j+offset]);
  1802. Bprint(faction, ".%s", typeset[tok]);
  1803. }
  1804. goto loop;
  1805. }
  1806. if(isupper(c) || islower(c) || c == '_' || c == '.') {
  1807. int tok; /* tok used oustide for type info */
  1808. /* look for $name */
  1809. Bungetrune(finput);
  1810. if(gettok() != IDENTIFIER)
  1811. error("$ must be followed by an identifier");
  1812. tok = chfind(2, tokname);
  1813. if((c = Bgetrune(finput)) != '#') {
  1814. Bungetrune(finput);
  1815. fnd = -1;
  1816. } else
  1817. if(gettok() != NUMBER) {
  1818. error("# must be followed by number");
  1819. fnd = -1;
  1820. } else
  1821. fnd = numbval;
  1822. for(j=1; j<=offset; ++j)
  1823. if(tok == prdptr[nprod][j]) {
  1824. if(--fnd <= 0) {
  1825. j -= offset;
  1826. goto dollar;
  1827. }
  1828. }
  1829. error("$name or $name#number not found");
  1830. }
  1831. Bputc(faction, '$');
  1832. if(s < 0 )
  1833. Bputc(faction, '-');
  1834. goto swt;
  1835. case '}':
  1836. brac--;
  1837. if(brac)
  1838. goto lcopy;
  1839. Bputrune(faction, c);
  1840. return;
  1841. case '/':
  1842. /* look for comments */
  1843. Bputrune(faction, c);
  1844. c = Bgetrune(finput);
  1845. if(c != '*')
  1846. goto swt;
  1847. /* it really is a comment; copy it */
  1848. Bputrune(faction, c);
  1849. c = Bgetrune(finput);
  1850. while(c >= 0) {
  1851. while(c == '*') {
  1852. Bputrune(faction, c);
  1853. if((c=Bgetrune(finput)) == '/')
  1854. goto lcopy;
  1855. }
  1856. Bputrune(faction, c);
  1857. if(c == '\n')
  1858. lineno++;
  1859. c = Bgetrune(finput);
  1860. }
  1861. error("EOF inside comment");
  1862. case '\'':
  1863. /* character constant */
  1864. match = '\'';
  1865. goto string;
  1866. case '"':
  1867. /* character string */
  1868. match = '"';
  1869. string:
  1870. Bputrune(faction, c);
  1871. while(c = Bgetrune(finput)) {
  1872. if(c == '\\') {
  1873. Bputrune(faction, c);
  1874. c = Bgetrune(finput);
  1875. if(c == '\n')
  1876. lineno++;
  1877. } else
  1878. if(c == match)
  1879. goto lcopy;
  1880. if(c == '\n')
  1881. error("newline in string or char. const.");
  1882. Bputrune(faction, c);
  1883. }
  1884. error("EOF in string or character constant");
  1885. case Beof:
  1886. error("action does not terminate");
  1887. case '\n':
  1888. lineno++;
  1889. goto lcopy;
  1890. }
  1891. lcopy:
  1892. Bputrune(faction, c);
  1893. goto loop;
  1894. }
  1895. void
  1896. openup(char *stem, int dflag, int vflag, int ytab, char *ytabc)
  1897. {
  1898. char buf[256];
  1899. if(vflag) {
  1900. snprint(buf, sizeof buf, "%s.%s", stem, FILEU);
  1901. foutput = Bopen(buf, OWRITE);
  1902. if(foutput == 0)
  1903. error("cannot open %s", buf);
  1904. }
  1905. if(yydebug) {
  1906. snprint(buf, sizeof buf, "%s.%s", stem, FILEDEBUG);
  1907. if((fdebug = Bopen(buf, OWRITE)) == 0)
  1908. error("can't open %s", buf);
  1909. }
  1910. if(dflag) {
  1911. snprint(buf, sizeof buf, "%s.%s", stem, FILED);
  1912. fdefine = Bopen(buf, OWRITE);
  1913. if(fdefine == 0)
  1914. error("can't create %s", buf);
  1915. }
  1916. if(ytab == 0)
  1917. snprint(buf, sizeof buf, "%s.%s", stem, OFILE);
  1918. else
  1919. strecpy(buf, buf+sizeof buf, ytabc);
  1920. ftable = Bopen(buf, OWRITE);
  1921. if(ftable == 0)
  1922. error("cannot open table file %s", buf);
  1923. }
  1924. /*
  1925. * print the output for the states
  1926. */
  1927. void
  1928. output(void)
  1929. {
  1930. int i, k, c;
  1931. Wset *u, *v;
  1932. Bprint(ftable, "short yyexca[] =\n{");
  1933. if(fdebug)
  1934. Bprint(fdebug, "char* yystates[] =\n{\n");
  1935. /* output the stuff for state i */
  1936. SLOOP(i) {
  1937. nolook = tystate[i]!=MUSTLOOKAHEAD;
  1938. closure(i);
  1939. /* output actions */
  1940. nolook = 1;
  1941. aryfil(temp1, ntokens+nnonter+1, 0);
  1942. WSLOOP(wsets, u) {
  1943. c = *(u->pitem);
  1944. if(c > 1 && c < NTBASE && temp1[c] == 0) {
  1945. WSLOOP(u, v)
  1946. if(c == *(v->pitem))
  1947. putitem(v->pitem+1, (Lkset*)0);
  1948. temp1[c] = state(c);
  1949. } else
  1950. if(c > NTBASE && temp1[(c -= NTBASE) + ntokens] == 0)
  1951. temp1[c+ntokens] = amem[indgo[i]+c];
  1952. }
  1953. if(i == 1)
  1954. temp1[1] = ACCEPTCODE;
  1955. /* now, we have the shifts; look at the reductions */
  1956. lastred = 0;
  1957. WSLOOP(wsets, u) {
  1958. c = *u->pitem;
  1959. /* reduction */
  1960. if(c <= 0) {
  1961. lastred = -c;
  1962. TLOOP(k)
  1963. if(BIT(u->ws.lset, k)) {
  1964. if(temp1[k] == 0)
  1965. temp1[k] = c;
  1966. else
  1967. if(temp1[k] < 0) { /* reduce/reduce conflict */
  1968. if(foutput)
  1969. Bprint(foutput,
  1970. "\n%d: reduce/reduce conflict"
  1971. " (red'ns %d and %d ) on %s",
  1972. i, -temp1[k], lastred,
  1973. symnam(k));
  1974. if(-temp1[k] > lastred)
  1975. temp1[k] = -lastred;
  1976. zzrrconf++;
  1977. } else
  1978. /* potential shift/reduce conflict */
  1979. precftn( lastred, k, i );
  1980. }
  1981. }
  1982. }
  1983. wract(i);
  1984. }
  1985. if(fdebug)
  1986. Bprint(fdebug, "};\n");
  1987. Bprint(ftable, "};\n");
  1988. Bprint(ftable, "#define YYNPROD %d\n", nprod);
  1989. Bprint(ftable, "#define YYPRIVATE %d\n", PRIVATE);
  1990. if(yydebug)
  1991. Bprint(ftable, "#define yydebug %s\n", yydebug);
  1992. }
  1993. /*
  1994. * pack state i from temp1 into amem
  1995. */
  1996. int
  1997. apack(int *p, int n)
  1998. {
  1999. int *pp, *qq, *rr, off, *q, *r;
  2000. /* we don't need to worry about checking because
  2001. * we will only look at entries known to be there...
  2002. * eliminate leading and trailing 0's
  2003. */
  2004. q = p+n;
  2005. for(pp = p, off = 0; *pp == 0 && pp <= q; ++pp, --off)
  2006. ;
  2007. /* no actions */
  2008. if(pp > q)
  2009. return 0;
  2010. p = pp;
  2011. /* now, find a place for the elements from p to q, inclusive */
  2012. r = &amem[ACTSIZE-1];
  2013. for(rr = amem; rr <= r; rr++, off++) {
  2014. for(qq = rr, pp = p; pp <= q; pp++, qq++)
  2015. if(*pp != 0)
  2016. if(*pp != *qq && *qq != 0)
  2017. goto nextk;
  2018. /* we have found an acceptable k */
  2019. if(pkdebug && foutput != 0)
  2020. Bprint(foutput, "off = %d, k = %d\n", off, (int)(rr-amem));
  2021. for(qq = rr, pp = p; pp <= q; pp++, qq++)
  2022. if(*pp) {
  2023. if(qq > r)
  2024. error("action table overflow");
  2025. if(qq > memp)
  2026. memp = qq;
  2027. *qq = *pp;
  2028. }
  2029. if(pkdebug && foutput != 0)
  2030. for(pp = amem; pp <= memp; pp += 10) {
  2031. Bprint(foutput, "\t");
  2032. for(qq = pp; qq <= pp+9; qq++)
  2033. Bprint(foutput, "%d ", *qq);
  2034. Bprint(foutput, "\n");
  2035. }
  2036. return(off);
  2037. nextk:;
  2038. }
  2039. error("no space in action table");
  2040. return 0;
  2041. }
  2042. /*
  2043. * output the gotos for the nontermninals
  2044. */
  2045. void
  2046. go2out(void)
  2047. {
  2048. int i, j, k, best, count, cbest, times;
  2049. /* mark begining of gotos */
  2050. Bprint(ftemp, "$\n");
  2051. for(i = 1; i <= nnonter; i++) {
  2052. go2gen(i);
  2053. /* find the best one to make default */
  2054. best = -1;
  2055. times = 0;
  2056. /* is j the most frequent */
  2057. for(j = 0; j <= nstate; j++) {
  2058. if(tystate[j] == 0)
  2059. continue;
  2060. if(tystate[j] == best)
  2061. continue;
  2062. /* is tystate[j] the most frequent */
  2063. count = 0;
  2064. cbest = tystate[j];
  2065. for(k = j; k <= nstate; k++)
  2066. if(tystate[k] == cbest)
  2067. count++;
  2068. if(count > times) {
  2069. best = cbest;
  2070. times = count;
  2071. }
  2072. }
  2073. /* best is now the default entry */
  2074. zzgobest += times-1;
  2075. for(j = 0; j <= nstate; j++)
  2076. if(tystate[j] != 0 && tystate[j] != best) {
  2077. Bprint(ftemp, "%d,%d,", j, tystate[j]);
  2078. zzgoent++;
  2079. }
  2080. /* now, the default */
  2081. if(best == -1)
  2082. best = 0;
  2083. zzgoent++;
  2084. Bprint(ftemp, "%d\n", best);
  2085. }
  2086. }
  2087. /*
  2088. * output the gotos for nonterminal c
  2089. */
  2090. void
  2091. go2gen(int c)
  2092. {
  2093. int i, work, cc;
  2094. Item *p, *q;
  2095. /* first, find nonterminals with gotos on c */
  2096. aryfil(temp1, nnonter+1, 0);
  2097. temp1[c] = 1;
  2098. work = 1;
  2099. while(work) {
  2100. work = 0;
  2101. PLOOP(0, i)
  2102. /* cc is a nonterminal */
  2103. if((cc=prdptr[i][1]-NTBASE) >= 0)
  2104. /* cc has a goto on c */
  2105. if(temp1[cc] != 0) {
  2106. /* thus, the left side of production i does too */
  2107. cc = *prdptr[i]-NTBASE;
  2108. if(temp1[cc] == 0) {
  2109. work = 1;
  2110. temp1[cc] = 1;
  2111. }
  2112. }
  2113. }
  2114. /* now, we have temp1[c] = 1 if a goto on c in closure of cc */
  2115. if(g2debug && foutput != 0) {
  2116. Bprint(foutput, "%s: gotos on ", nontrst[c].name);
  2117. NTLOOP(i)
  2118. if(temp1[i])
  2119. Bprint(foutput, "%s ", nontrst[i].name);
  2120. Bprint(foutput, "\n");
  2121. }
  2122. /* now, go through and put gotos into tystate */
  2123. aryfil(tystate, nstate, 0);
  2124. SLOOP(i)
  2125. ITMLOOP(i, p, q)
  2126. if((cc = *p->pitem) >= NTBASE)
  2127. /* goto on c is possible */
  2128. if(temp1[cc-NTBASE]) {
  2129. tystate[i] = amem[indgo[i]+c];
  2130. break;
  2131. }
  2132. }
  2133. /*
  2134. * decide a shift/reduce conflict by precedence.
  2135. * r is a rule number, t a token number
  2136. * the conflict is in state s
  2137. * temp1[t] is changed to reflect the action
  2138. */
  2139. void
  2140. precftn(int r, int t, int s)
  2141. {
  2142. int lp, lt, action;
  2143. lp = levprd[r];
  2144. lt = toklev[t];
  2145. if(PLEVEL(lt) == 0 || PLEVEL(lp) == 0) {
  2146. /* conflict */
  2147. if(foutput != 0)
  2148. Bprint(foutput,
  2149. "\n%d: shift/reduce conflict (shift %d(%d), red'n %d(%d)) on %s",
  2150. s, temp1[t], PLEVEL(lt), r, PLEVEL(lp), symnam(t));
  2151. zzsrconf++;
  2152. return;
  2153. }
  2154. if(PLEVEL(lt) == PLEVEL(lp))
  2155. action = ASSOC(lt);
  2156. else
  2157. if(PLEVEL(lt) > PLEVEL(lp))
  2158. action = RASC; /* shift */
  2159. else
  2160. action = LASC; /* reduce */
  2161. switch(action) {
  2162. case BASC: /* error action */
  2163. temp1[t] = ERRCODE;
  2164. break;
  2165. case LASC: /* reduce */
  2166. temp1[t] = -r;
  2167. break;
  2168. }
  2169. }
  2170. /*
  2171. * output state i
  2172. * temp1 has the actions, lastred the default
  2173. */
  2174. void
  2175. wract(int i)
  2176. {
  2177. int p, p0, p1, ntimes, tred, count, j, flag;
  2178. /* find the best choice for lastred */
  2179. lastred = 0;
  2180. ntimes = 0;
  2181. TLOOP(j) {
  2182. if(temp1[j] >= 0)
  2183. continue;
  2184. if(temp1[j]+lastred == 0)
  2185. continue;
  2186. /* count the number of appearances of temp1[j] */
  2187. count = 0;
  2188. tred = -temp1[j];
  2189. levprd[tred] |= REDFLAG;
  2190. TLOOP(p)
  2191. if(temp1[p]+tred == 0)
  2192. count++;
  2193. if(count > ntimes) {
  2194. lastred = tred;
  2195. ntimes = count;
  2196. }
  2197. }
  2198. /*
  2199. * for error recovery, arrange that, if there is a shift on the
  2200. * error recovery token, `error', that the default be the error action
  2201. */
  2202. if(temp1[2] > 0)
  2203. lastred = 0;
  2204. /* clear out entries in temp1 which equal lastred */
  2205. TLOOP(p)
  2206. if(temp1[p]+lastred == 0)
  2207. temp1[p] = 0;
  2208. wrstate(i);
  2209. defact[i] = lastred;
  2210. flag = 0;
  2211. TLOOP(p0)
  2212. if((p1=temp1[p0]) != 0) {
  2213. if(p1 < 0) {
  2214. p1 = -p1;
  2215. goto exc;
  2216. }
  2217. if(p1 == ACCEPTCODE) {
  2218. p1 = -1;
  2219. goto exc;
  2220. }
  2221. if(p1 == ERRCODE) {
  2222. p1 = 0;
  2223. exc:
  2224. if(flag++ == 0)
  2225. Bprint(ftable, "-1, %d,\n", i);
  2226. Bprint(ftable, "\t%d, %d,\n", p0, p1);
  2227. zzexcp++;
  2228. continue;
  2229. }
  2230. Bprint(ftemp, "%d,%d,", p0, p1);
  2231. zzacent++;
  2232. }
  2233. if(flag) {
  2234. defact[i] = -2;
  2235. Bprint(ftable, "\t-2, %d,\n", lastred);
  2236. }
  2237. Bprint(ftemp, "\n");
  2238. }
  2239. /*
  2240. * writes state i
  2241. */
  2242. void
  2243. wrstate(int i)
  2244. {
  2245. int j0, j1;
  2246. Item *pp, *qq;
  2247. Wset *u;
  2248. if(fdebug) {
  2249. if(lastred) {
  2250. Bprint(fdebug, " 0, /*%d*/\n", i);
  2251. } else {
  2252. Bprint(fdebug, " \"");
  2253. ITMLOOP(i, pp, qq)
  2254. Bprint(fdebug, "%s\\n", writem(pp->pitem));
  2255. if(tystate[i] == MUSTLOOKAHEAD)
  2256. WSLOOP(wsets + (pstate[i+1] - pstate[i]), u)
  2257. if(*u->pitem < 0)
  2258. Bprint(fdebug, "%s\\n", writem(u->pitem));
  2259. Bprint(fdebug, "\", /*%d*/\n", i);
  2260. }
  2261. }
  2262. if(foutput == 0)
  2263. return;
  2264. Bprint(foutput, "\nstate %d\n", i);
  2265. ITMLOOP(i, pp, qq)
  2266. Bprint(foutput, "\t%s\n", writem(pp->pitem));
  2267. if(tystate[i] == MUSTLOOKAHEAD)
  2268. /* print out empty productions in closure */
  2269. WSLOOP(wsets+(pstate[i+1]-pstate[i]), u)
  2270. if(*u->pitem < 0)
  2271. Bprint(foutput, "\t%s\n", writem(u->pitem));
  2272. /* check for state equal to another */
  2273. TLOOP(j0)
  2274. if((j1=temp1[j0]) != 0) {
  2275. Bprint(foutput, "\n\t%s ", symnam(j0));
  2276. /* shift, error, or accept */
  2277. if(j1 > 0) {
  2278. if(j1 == ACCEPTCODE)
  2279. Bprint(foutput, "accept");
  2280. else
  2281. if(j1 == ERRCODE)
  2282. Bprint(foutput, "error");
  2283. else
  2284. Bprint(foutput, "shift %d", j1);
  2285. } else
  2286. Bprint(foutput, "reduce %d (src line %d)", -j1, rlines[-j1]);
  2287. }
  2288. /* output the final production */
  2289. if(lastred)
  2290. Bprint(foutput, "\n\t. reduce %d (src line %d)\n\n",
  2291. lastred, rlines[lastred]);
  2292. else
  2293. Bprint(foutput, "\n\t. error\n\n");
  2294. /* now, output nonterminal actions */
  2295. j1 = ntokens;
  2296. for(j0 = 1; j0 <= nnonter; j0++) {
  2297. j1++;
  2298. if(temp1[j1])
  2299. Bprint(foutput, "\t%s goto %d\n", symnam(j0+NTBASE), temp1[j1]);
  2300. }
  2301. }
  2302. void
  2303. warray(char *s, int *v, int n)
  2304. {
  2305. int i;
  2306. Bprint(ftable, "short %s[] =\n{", s);
  2307. for(i=0;;) {
  2308. if(i%10 == 0)
  2309. Bprint(ftable, "\n");
  2310. Bprint(ftable, "%4d", v[i]);
  2311. i++;
  2312. if(i >= n) {
  2313. Bprint(ftable, "\n};\n");
  2314. break;
  2315. }
  2316. Bprint(ftable, ",");
  2317. }
  2318. }
  2319. /*
  2320. * in order to free up the mem and amem arrays for the optimizer,
  2321. * and still be able to output yyr1, etc., after the sizes of
  2322. * the action array is known, we hide the nonterminals
  2323. * derived by productions in levprd.
  2324. */
  2325. void
  2326. hideprod(void)
  2327. {
  2328. int i, j;
  2329. j = 0;
  2330. levprd[0] = 0;
  2331. PLOOP(1, i) {
  2332. if(!(levprd[i] & REDFLAG)) {
  2333. j++;
  2334. if(foutput != 0)
  2335. Bprint(foutput, "Rule not reduced: %s\n", writem(prdptr[i]));
  2336. }
  2337. levprd[i] = *prdptr[i] - NTBASE;
  2338. }
  2339. if(j)
  2340. print("%d rules never reduced\n", j);
  2341. }
  2342. void
  2343. callopt(void)
  2344. {
  2345. int i, *p, j, k, *q;
  2346. /* read the arrays from tempfile and set parameters */
  2347. finput = Bopen(tempname, OREAD);
  2348. if(finput == 0)
  2349. error("optimizer cannot open tempfile");
  2350. pgo[0] = 0;
  2351. temp1[0] = 0;
  2352. nstate = 0;
  2353. nnonter = 0;
  2354. for(;;) {
  2355. switch(gtnm()) {
  2356. case '\n':
  2357. nstate++;
  2358. pmem--;
  2359. temp1[nstate] = pmem - mem0;
  2360. case ',':
  2361. continue;
  2362. case '$':
  2363. break;
  2364. default:
  2365. error("bad tempfile");
  2366. }
  2367. break;
  2368. }
  2369. pmem--;
  2370. temp1[nstate] = yypgo[0] = pmem - mem0;
  2371. for(;;) {
  2372. switch(gtnm()) {
  2373. case '\n':
  2374. nnonter++;
  2375. yypgo[nnonter] = pmem-mem0;
  2376. case ',':
  2377. continue;
  2378. case -1:
  2379. break;
  2380. default:
  2381. error("bad tempfile");
  2382. }
  2383. break;
  2384. }
  2385. pmem--;
  2386. yypgo[nnonter--] = pmem - mem0;
  2387. for(i = 0; i < nstate; i++) {
  2388. k = 32000;
  2389. j = 0;
  2390. q = mem0 + temp1[i+1];
  2391. for(p = mem0 + temp1[i]; p < q ; p += 2) {
  2392. if(*p > j)
  2393. j = *p;
  2394. if(*p < k)
  2395. k = *p;
  2396. }
  2397. /* nontrivial situation */
  2398. if(k <= j) {
  2399. /* j is now the range */
  2400. /* j -= k; *//* call scj */
  2401. if(k > maxoff)
  2402. maxoff = k;
  2403. }
  2404. tystate[i] = (temp1[i+1]-temp1[i]) + 2*j;
  2405. if(j > maxspr)
  2406. maxspr = j;
  2407. }
  2408. /* initialize ggreed table */
  2409. for(i = 1; i <= nnonter; i++) {
  2410. ggreed[i] = 1;
  2411. j = 0;
  2412. /* minimum entry index is always 0 */
  2413. q = mem0 + yypgo[i+1] - 1;
  2414. for(p = mem0+yypgo[i]; p < q ; p += 2) {
  2415. ggreed[i] += 2;
  2416. if(*p > j)
  2417. j = *p;
  2418. }
  2419. ggreed[i] = ggreed[i] + 2*j;
  2420. if(j > maxoff)
  2421. maxoff = j;
  2422. }
  2423. /* now, prepare to put the shift actions into the amem array */
  2424. for(i = 0; i < ACTSIZE; i++)
  2425. amem[i] = 0;
  2426. maxa = amem;
  2427. for(i = 0; i < nstate; i++) {
  2428. if(tystate[i] == 0 && adb > 1)
  2429. Bprint(ftable, "State %d: null\n", i);
  2430. indgo[i] = YYFLAG1;
  2431. }
  2432. while((i = nxti()) != NOMORE)
  2433. if(i >= 0)
  2434. stin(i);
  2435. else
  2436. gin(-i);
  2437. /* print amem array */
  2438. if(adb > 2 )
  2439. for(p = amem; p <= maxa; p += 10) {
  2440. Bprint(ftable, "%4d ", (int)(p-amem));
  2441. for(i = 0; i < 10; ++i)
  2442. Bprint(ftable, "%4d ", p[i]);
  2443. Bprint(ftable, "\n");
  2444. }
  2445. /* write out the output appropriate to the language */
  2446. aoutput();
  2447. osummary();
  2448. ZAPFILE(tempname);
  2449. }
  2450. void
  2451. gin(int i)
  2452. {
  2453. int *p, *r, *s, *q1, *q2;
  2454. /* enter gotos on nonterminal i into array amem */
  2455. ggreed[i] = 0;
  2456. q2 = mem0+ yypgo[i+1] - 1;
  2457. q1 = mem0 + yypgo[i];
  2458. /* now, find amem place for it */
  2459. for(p = amem; p < &amem[ACTSIZE]; p++) {
  2460. if(*p)
  2461. continue;
  2462. for(r = q1; r < q2; r += 2) {
  2463. s = p + *r + 1;
  2464. if(*s)
  2465. goto nextgp;
  2466. if(s > maxa)
  2467. if((maxa = s) > &amem[ACTSIZE])
  2468. error("a array overflow");
  2469. }
  2470. /* we have found amem spot */
  2471. *p = *q2;
  2472. if(p > maxa)
  2473. if((maxa = p) > &amem[ACTSIZE])
  2474. error("a array overflow");
  2475. for(r = q1; r < q2; r += 2) {
  2476. s = p + *r + 1;
  2477. *s = r[1];
  2478. }
  2479. pgo[i] = p-amem;
  2480. if(adb > 1)
  2481. Bprint(ftable, "Nonterminal %d, entry at %d\n", i, pgo[i]);
  2482. return;
  2483. nextgp:;
  2484. }
  2485. error("cannot place goto %d\n", i);
  2486. }
  2487. void
  2488. stin(int i)
  2489. {
  2490. int *r, *s, n, flag, j, *q1, *q2;
  2491. tystate[i] = 0;
  2492. /* enter state i into the amem array */
  2493. q2 = mem0+temp1[i+1];
  2494. q1 = mem0+temp1[i];
  2495. /* find an acceptable place */
  2496. for(n = -maxoff; n < ACTSIZE; n++) {
  2497. flag = 0;
  2498. for(r = q1; r < q2; r += 2) {
  2499. if((s = *r + n + amem) < amem)
  2500. goto nextn;
  2501. if(*s == 0)
  2502. flag++;
  2503. else
  2504. if(*s != r[1])
  2505. goto nextn;
  2506. }
  2507. /* check that the position equals another only if the states are identical */
  2508. for(j=0; j<nstate; j++) {
  2509. if(indgo[j] == n) {
  2510. /* we have some disagreement */
  2511. if(flag)
  2512. goto nextn;
  2513. if(temp1[j+1]+temp1[i] == temp1[j]+temp1[i+1]) {
  2514. /* states are equal */
  2515. indgo[i] = n;
  2516. if(adb > 1)
  2517. Bprint(ftable,
  2518. "State %d: entry at %d equals state %d\n",
  2519. i, n, j);
  2520. return;
  2521. }
  2522. /* we have some disagreement */
  2523. goto nextn;
  2524. }
  2525. }
  2526. for(r = q1; r < q2; r += 2) {
  2527. if((s = *r+n+amem) >= &amem[ACTSIZE])
  2528. error("out of space in optimizer a array");
  2529. if(s > maxa)
  2530. maxa = s;
  2531. if(*s != 0 && *s != r[1])
  2532. error("clobber of a array, pos'n %d, by %d", s-amem, r[1]);
  2533. *s = r[1];
  2534. }
  2535. indgo[i] = n;
  2536. if(adb > 1)
  2537. Bprint(ftable, "State %d: entry at %d\n", i, indgo[i]);
  2538. return;
  2539. nextn:;
  2540. }
  2541. error("Error; failure to place state %d\n", i);
  2542. }
  2543. /*
  2544. * finds the next i
  2545. */
  2546. int
  2547. nxti(void)
  2548. {
  2549. int i, max, maxi;
  2550. max = 0;
  2551. maxi = 0;
  2552. for(i = 1; i <= nnonter; i++)
  2553. if(ggreed[i] >= max) {
  2554. max = ggreed[i];
  2555. maxi = -i;
  2556. }
  2557. for(i = 0; i < nstate; ++i)
  2558. if(tystate[i] >= max) {
  2559. max = tystate[i];
  2560. maxi = i;
  2561. }
  2562. if(nxdb)
  2563. Bprint(ftable, "nxti = %d, max = %d\n", maxi, max);
  2564. if(max == 0)
  2565. return NOMORE;
  2566. return maxi;
  2567. }
  2568. /*
  2569. * write summary
  2570. */
  2571. void
  2572. osummary(void)
  2573. {
  2574. int i, *p;
  2575. if(foutput == 0)
  2576. return;
  2577. i = 0;
  2578. for(p = maxa; p >= amem; p--)
  2579. if(*p == 0)
  2580. i++;
  2581. Bprint(foutput, "Optimizer space used: input %d/%d, output %d/%d\n",
  2582. (int)(pmem-mem0+1), MEMSIZE, (int)(maxa-amem+1), ACTSIZE);
  2583. Bprint(foutput, "%d table entries, %d zero\n", (int)(maxa-amem+1), i);
  2584. Bprint(foutput, "maximum spread: %d, maximum offset: %d\n", maxspr, maxoff);
  2585. }
  2586. /*
  2587. * this version is for C
  2588. * write out the optimized parser
  2589. */
  2590. void
  2591. aoutput(void)
  2592. {
  2593. Bprint(ftable, "#define\tYYLAST\t%d\n", (int)(maxa-amem+1));
  2594. arout("yyact", amem, (maxa-amem)+1);
  2595. arout("yypact", indgo, nstate);
  2596. arout("yypgo", pgo, nnonter+1);
  2597. }
  2598. void
  2599. arout(char *s, int *v, int n)
  2600. {
  2601. int i;
  2602. Bprint(ftable, "short %s[] =\n{", s);
  2603. for(i = 0; i < n;) {
  2604. if(i%10 == 0)
  2605. Bprint(ftable, "\n");
  2606. Bprint(ftable, "%4d", v[i]);
  2607. i++;
  2608. if(i == n)
  2609. Bprint(ftable, "\n};\n");
  2610. else
  2611. Bprint(ftable, ",");
  2612. }
  2613. }
  2614. /*
  2615. * read and convert an integer from the standard input
  2616. * return the terminating character
  2617. * blanks, tabs, and newlines are ignored
  2618. */
  2619. int
  2620. gtnm(void)
  2621. {
  2622. int sign, val, c;
  2623. sign = 0;
  2624. val = 0;
  2625. while((c=Bgetrune(finput)) != Beof) {
  2626. if(isdigit(c)) {
  2627. val = val*10 + c-'0';
  2628. continue;
  2629. }
  2630. if(c == '-') {
  2631. sign = 1;
  2632. continue;
  2633. }
  2634. break;
  2635. }
  2636. if(sign)
  2637. val = -val;
  2638. *pmem++ = val;
  2639. if(pmem >= &mem0[MEMSIZE])
  2640. error("out of space");
  2641. return c;
  2642. }