lalr.c 42 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900
  1. /*++
  2. Copyright (c) 2016 Minoca Corp.
  3. This file is licensed under the terms of the GNU General Public License
  4. version 3. Alternative licensing terms are available. Contact
  5. info@minocacorp.com for details. See the LICENSE file at the root of this
  6. project for complete licensing information.
  7. Module Name:
  8. lalr.c
  9. Abstract:
  10. This module implements the production of an LALR(1) parser from an LR(0)
  11. state machine.
  12. Author:
  13. Evan Green 17-Apr-2016
  14. Environment:
  15. Build
  16. --*/
  17. //
  18. // ------------------------------------------------------------------- Includes
  19. //
  20. #include "yygenp.h"
  21. #include <assert.h>
  22. #include <string.h>
  23. //
  24. // ---------------------------------------------------------------- Definitions
  25. //
  26. typedef struct _YYGEN_LOOKBACK YYGEN_LOOKBACK, *PYYGEN_LOOKBACK;
  27. /*++
  28. Structure Description:
  29. This structure maps a lookahead symbol back to the list of gotos that use
  30. it.
  31. Members:
  32. Next - Supplies a pointer to the next lookback in the set.
  33. Goto - Supplies the goto index the lookback is referring to.
  34. --*/
  35. struct _YYGEN_LOOKBACK {
  36. PYYGEN_LOOKBACK Next;
  37. YY_GOTO_INDEX Goto;
  38. };
  39. /*++
  40. Structure Description:
  41. This structure contains the working state for the LALR generator.
  42. Members:
  43. MaxRightLength - Stores the number of elements in the longest right hand
  44. side of any rule.
  45. TokenSetSize - Stores the number of 32-bit words needed to represent a
  46. bitmap of all the terminals.
  47. GotoCount - Stores the number of gotos.
  48. GotoFollows - Stores the FOLLOW set of gotos, which is an array of token
  49. bitmaps indexed by goto. It shows for any goto the set of terminals
  50. that can come after the destination of the goto is found.
  51. Infinity - Stores a value greater than any possible goto number for the
  52. purposes of graph traversal.
  53. GotoVertex - Stores an array mapping each goto index to its corresponding
  54. vertex. 0 is not valid.
  55. Vertices - Stores the array of graph vertices.
  56. Top - Stores the current count of graph vertices.
  57. Relations - Stores an array of arrays of goto indices, indicating the
  58. relations between graph vertices for each goto index.
  59. Includes - Stores the set of relations to include in the follow set,
  60. indexed by goto index.
  61. Lookback - Stores an array of optional pointers to lookback sets, running
  62. parallel to the lookahead sets and lookahead rule arrays. It shows
  63. which gotos use that lookahead.
  64. StartGoto - Stores the goto index associated with the start symbol.
  65. --*/
  66. typedef struct _YYGEN_LALR_CONTEXT {
  67. ULONG MaxRightLength;
  68. ULONG TokenSetSize;
  69. YY_GOTO_INDEX GotoCount;
  70. PULONG GotoFollows;
  71. YY_GOTO_INDEX Infinity;
  72. PYY_GOTO_INDEX GotoVertex;
  73. PYY_GOTO_INDEX Vertices;
  74. YY_GOTO_INDEX Top;
  75. PYY_GOTO_INDEX *Relations;
  76. PYY_GOTO_INDEX *Includes;
  77. PYYGEN_LOOKBACK *Lookback;
  78. YY_GOTO_INDEX StartGoto;
  79. } YYGEN_LALR_CONTEXT, *PYYGEN_LALR_CONTEXT;
  80. //
  81. // ------------------------------------------------------ Data Type Definitions
  82. //
  83. //
  84. // ----------------------------------------------- Internal Function Prototypes
  85. //
  86. YY_STATUS
  87. YypInitializeLalrContext (
  88. PYYGEN_CONTEXT Context,
  89. PYYGEN_LALR_CONTEXT Lalr
  90. );
  91. VOID
  92. YypDestroyLalrContext (
  93. PYYGEN_CONTEXT Context,
  94. PYYGEN_LALR_CONTEXT Lalr
  95. );
  96. YY_STATUS
  97. YypInitializeLookaheads (
  98. PYYGEN_CONTEXT Context,
  99. PYYGEN_LALR_CONTEXT Lalr
  100. );
  101. YY_STATUS
  102. YypSetGotoMap (
  103. PYYGEN_CONTEXT Context,
  104. PYYGEN_LALR_CONTEXT Lalr
  105. );
  106. YY_STATUS
  107. YypInitializeFollows (
  108. PYYGEN_CONTEXT Context,
  109. PYYGEN_LALR_CONTEXT Lalr
  110. );
  111. YY_STATUS
  112. YypBuildRelations (
  113. PYYGEN_CONTEXT Context,
  114. PYYGEN_LALR_CONTEXT Lalr
  115. );
  116. YY_STATUS
  117. YypAddLookbackEdge (
  118. PYYGEN_CONTEXT Context,
  119. PYYGEN_LALR_CONTEXT Lalr,
  120. YY_STATE_INDEX State,
  121. YY_RULE_INDEX Rule,
  122. YY_GOTO_INDEX Goto
  123. );
  124. YY_STATUS
  125. YypComputeFollowSet (
  126. PYYGEN_CONTEXT Context,
  127. PYYGEN_LALR_CONTEXT Lalr
  128. );
  129. VOID
  130. YypComputeLookaheads (
  131. PYYGEN_CONTEXT Context,
  132. PYYGEN_LALR_CONTEXT Lalr
  133. );
  134. YY_STATUS
  135. YypBuildDigraph (
  136. PYYGEN_CONTEXT Context,
  137. PYYGEN_LALR_CONTEXT Lalr,
  138. PYY_GOTO_INDEX *Relations
  139. );
  140. VOID
  141. YypTraverseDigraph (
  142. PYYGEN_CONTEXT Context,
  143. PYYGEN_LALR_CONTEXT Lalr,
  144. YY_GOTO_INDEX GotoIndex
  145. );
  146. PYY_GOTO_INDEX *
  147. YypTranspose (
  148. PYY_GOTO_INDEX *Relations,
  149. YY_GOTO_INDEX Count
  150. );
  151. YY_GOTO_INDEX
  152. YypFindGoto (
  153. PYYGEN_CONTEXT Context,
  154. YY_STATE_INDEX State,
  155. YY_VALUE Symbol
  156. );
  157. VOID
  158. YypPrintGotoMap (
  159. PYYGEN_CONTEXT Context,
  160. PYYGEN_LALR_CONTEXT Lalr
  161. );
  162. VOID
  163. YypPrintTokenBitmapArray (
  164. PYYGEN_CONTEXT Context,
  165. PULONG BitmapArray,
  166. YY_VALUE Count
  167. );
  168. VOID
  169. YypPrintIncludes (
  170. PYYGEN_CONTEXT Context,
  171. PYYGEN_LALR_CONTEXT Lalr
  172. );
  173. //
  174. // -------------------------------------------------------------------- Globals
  175. //
  176. //
  177. // ------------------------------------------------------------------ Functions
  178. //
  179. YY_STATUS
  180. YypGenerateLalr (
  181. PYYGEN_CONTEXT Context
  182. )
  183. /*++
  184. Routine Description:
  185. This routine generates an LALR(1) state machine based on an LR(0) state
  186. machine.
  187. Arguments:
  188. Context - Supplies a pointer to the generator context.
  189. Return Value:
  190. YY status.
  191. --*/
  192. {
  193. YYGEN_LALR_CONTEXT Lalr;
  194. YY_STATUS YyStatus;
  195. memset(&Lalr, 0, sizeof(YYGEN_LALR_CONTEXT));
  196. YyStatus = YypInitializeLalrContext(Context, &Lalr);
  197. if (YyStatus != YyStatusSuccess) {
  198. goto GenerateLalrEnd;
  199. }
  200. YyStatus = YypSetGotoMap(Context, &Lalr);
  201. if (YyStatus != YyStatusSuccess) {
  202. goto GenerateLalrEnd;
  203. }
  204. YyStatus = YypInitializeFollows(Context, &Lalr);
  205. if (YyStatus != YyStatusSuccess) {
  206. goto GenerateLalrEnd;
  207. }
  208. YyStatus = YypBuildRelations(Context, &Lalr);
  209. if (YyStatus != YyStatusSuccess) {
  210. goto GenerateLalrEnd;
  211. }
  212. YyStatus = YypComputeFollowSet(Context, &Lalr);
  213. if (YyStatus != YyStatusSuccess) {
  214. goto GenerateLalrEnd;
  215. }
  216. YypComputeLookaheads(Context, &Lalr);
  217. GenerateLalrEnd:
  218. YypDestroyLalrContext(Context, &Lalr);
  219. return YyStatus;
  220. }
  221. //
  222. // --------------------------------------------------------- Internal Functions
  223. //
  224. YY_STATUS
  225. YypInitializeLalrContext (
  226. PYYGEN_CONTEXT Context,
  227. PYYGEN_LALR_CONTEXT Lalr
  228. )
  229. /*++
  230. Routine Description:
  231. This routine allocates arrays needed for LALR generation.
  232. Arguments:
  233. Context - Supplies a pointer to the generator context.
  234. Lalr - Supplies a pointer to the zeroed out LALR context.
  235. Return Value:
  236. YY status.
  237. --*/
  238. {
  239. PYY_ITEM_INDEX Items;
  240. PYY_ITEM_INDEX ItemsEnd;
  241. PYYGEN_REDUCTIONS Reductions;
  242. ULONG RuleLength;
  243. PYYGEN_SHIFTS Shifts;
  244. PYYGEN_STATE State;
  245. YY_STATE_INDEX StateCount;
  246. YY_STATUS YyStatus;
  247. YyStatus = YyStatusNoMemory;
  248. Lalr->TokenSetSize = YYGEN_BITMAP_WORD_COUNT(Context->TokenCount);
  249. //
  250. // Create flattened arrays of states, accessing symbols, shifts, and
  251. // reductions indexed by state.
  252. //
  253. StateCount = Context->StateCount;
  254. Context->StateTable = YypAllocate(StateCount * sizeof(PYYGEN_STATE));
  255. if (Context->StateTable == NULL) {
  256. goto InitializeLalrContextEnd;
  257. }
  258. Context->AccessingSymbol = YypAllocate(StateCount * sizeof(YY_VALUE));
  259. if (Context->AccessingSymbol == NULL) {
  260. goto InitializeLalrContextEnd;
  261. }
  262. Context->ShiftTable = YypAllocate(StateCount * sizeof(PYYGEN_SHIFTS));
  263. if (Context->ShiftTable == NULL) {
  264. goto InitializeLalrContextEnd;
  265. }
  266. Context->ReductionTable =
  267. YypAllocate(StateCount * sizeof(YYGEN_REDUCTIONS));
  268. if (Context->ReductionTable == NULL) {
  269. goto InitializeLalrContextEnd;
  270. }
  271. State = Context->FirstState;
  272. StateCount = 0;
  273. while (State != NULL) {
  274. Context->StateTable[State->Number] = State;
  275. Context->AccessingSymbol[State->Number] = State->AccessingSymbol;
  276. State = State->Next;
  277. StateCount += 1;
  278. }
  279. assert(StateCount == Context->StateCount);
  280. Shifts = Context->FirstShift;
  281. while (Shifts != NULL) {
  282. Context->ShiftTable[Shifts->Number] = Shifts;
  283. Shifts = Shifts->Next;
  284. }
  285. Reductions = Context->FirstReduction;
  286. while (Reductions != NULL) {
  287. Context->ReductionTable[Reductions->Number] = Reductions;
  288. Reductions = Reductions->Next;
  289. }
  290. //
  291. // Figure out the maximum right hand side length.
  292. //
  293. Items = Context->Items;
  294. ItemsEnd = Context->Items + Context->ItemCount;
  295. RuleLength = 0;
  296. while (Items < ItemsEnd) {
  297. if (*Items >= 0) {
  298. RuleLength += 1;
  299. } else {
  300. if (RuleLength > Lalr->MaxRightLength) {
  301. Lalr->MaxRightLength = RuleLength;
  302. }
  303. RuleLength = 0;
  304. }
  305. Items += 1;
  306. }
  307. YyStatus = YypInitializeLookaheads(Context, Lalr);
  308. if (YyStatus != YyStatusSuccess) {
  309. goto InitializeLalrContextEnd;
  310. }
  311. YyStatus = YyStatusSuccess;
  312. InitializeLalrContextEnd:
  313. return YyStatus;
  314. }
  315. VOID
  316. YypDestroyLalrContext (
  317. PYYGEN_CONTEXT Context,
  318. PYYGEN_LALR_CONTEXT Lalr
  319. )
  320. /*++
  321. Routine Description:
  322. This routine frees memory allocated in the given LALR context.
  323. Arguments:
  324. Context - Supplies a pointer to the application context.
  325. Lalr - Supplies a pointer to the LALR context.
  326. Return Value:
  327. None.
  328. --*/
  329. {
  330. YY_VALUE Count;
  331. YY_VALUE Index;
  332. PYYGEN_LOOKBACK Lookback;
  333. PYYGEN_LOOKBACK Next;
  334. if (Lalr->GotoFollows != NULL) {
  335. YypFree(Lalr->GotoFollows);
  336. }
  337. if (Lalr->GotoVertex != NULL) {
  338. YypFree(Lalr->GotoVertex);
  339. }
  340. if (Lalr->Vertices != NULL) {
  341. YypFree(Lalr->Vertices);
  342. }
  343. assert(Lalr->Relations == NULL);
  344. if (Lalr->Includes != NULL) {
  345. for (Index = 0; Index < Lalr->GotoCount; Index += 1) {
  346. if (Lalr->Includes[Index] != NULL) {
  347. YypFree(Lalr->Includes[Index]);
  348. }
  349. }
  350. YypFree(Lalr->Includes);
  351. }
  352. if (Lalr->Lookback != NULL) {
  353. Count = Context->Lookaheads[Context->StateCount];
  354. for (Index = 0; Index < Count; Index += 1) {
  355. Lookback = Lalr->Lookback[Index];
  356. while (Lookback != NULL) {
  357. Next = Lookback->Next;
  358. YypFree(Lookback);
  359. Lookback = Next;
  360. }
  361. }
  362. YypFree(Lalr->Lookback);
  363. }
  364. return;
  365. }
  366. YY_STATUS
  367. YypInitializeLookaheads (
  368. PYYGEN_CONTEXT Context,
  369. PYYGEN_LALR_CONTEXT Lalr
  370. )
  371. /*++
  372. Routine Description:
  373. This routine allocates the lookahead arrays and initializes parts of them.
  374. Arguments:
  375. Context - Supplies a pointer to the generator context.
  376. Lalr - Supplies a pointer to the LALR context.
  377. Return Value:
  378. YY status.
  379. --*/
  380. {
  381. ULONG Count;
  382. YY_RULE_INDEX ReductionIndex;
  383. PYYGEN_REDUCTIONS Reductions;
  384. YY_STATE_INDEX State;
  385. YY_STATUS YyStatus;
  386. YyStatus = YyStatusNoMemory;
  387. Context->Lookaheads =
  388. YypAllocate((Context->StateCount + 1) * sizeof(YY_VALUE));
  389. if (Context->Lookaheads == NULL) {
  390. goto InitializeLookaheadsEnd;
  391. }
  392. //
  393. // Set indices and count how many total reductions there are.
  394. //
  395. Count = 0;
  396. for (State = 0; State < Context->StateCount; State += 1) {
  397. Context->Lookaheads[State] = Count;
  398. Reductions = Context->ReductionTable[State];
  399. if (Reductions != NULL) {
  400. Count += Reductions->Count;
  401. }
  402. }
  403. Context->Lookaheads[State] = Count;
  404. Context->LookaheadSets =
  405. YypAllocate((Count * Lalr->TokenSetSize) * sizeof(ULONG));
  406. if (Context->LookaheadSets == NULL) {
  407. goto InitializeLookaheadsEnd;
  408. }
  409. Context->LookaheadRule = YypAllocate(Count * sizeof(YY_RULE_INDEX));
  410. if (Context->LookaheadRule == NULL) {
  411. goto InitializeLookaheadsEnd;
  412. }
  413. Lalr->Lookback = YypAllocate(Count * sizeof(PYYGEN_LOOKBACK));
  414. if (Lalr->Lookback == NULL) {
  415. goto InitializeLookaheadsEnd;
  416. }
  417. //
  418. // Initialize the lookahead rule numbers.
  419. //
  420. Count = 0;
  421. for (State = 0; State < Context->StateCount; State += 1) {
  422. Context->Lookaheads[State] = Count;
  423. Reductions = Context->ReductionTable[State];
  424. if (Reductions != NULL) {
  425. for (ReductionIndex = 0;
  426. ReductionIndex < Reductions->Count;
  427. ReductionIndex += 1) {
  428. Context->LookaheadRule[Count] =
  429. Reductions->Rules[ReductionIndex];
  430. Count += 1;
  431. }
  432. }
  433. }
  434. YyStatus = YyStatusSuccess;
  435. InitializeLookaheadsEnd:
  436. return YyStatus;
  437. }
  438. YY_STATUS
  439. YypSetGotoMap (
  440. PYYGEN_CONTEXT Context,
  441. PYYGEN_LALR_CONTEXT Lalr
  442. )
  443. /*++
  444. Routine Description:
  445. This routine expands the shifts of each state out into gotos.
  446. Arguments:
  447. Context - Supplies a pointer to the generator context.
  448. Lalr - Supplies a pointer to the LALR context.
  449. Return Value:
  450. YY status.
  451. --*/
  452. {
  453. YY_STATE_INDEX DestinationState;
  454. YY_VALUE Goal;
  455. YY_GOTO_INDEX GotoIndex;
  456. PYY_GOTO_INDEX GotoMap;
  457. YY_VALUE ShiftIndex;
  458. PYYGEN_SHIFTS Shifts;
  459. YY_VALUE Symbol;
  460. YY_VALUE TokenCount;
  461. PYY_GOTO_INDEX WorkingMap;
  462. YY_STATUS YyStatus;
  463. YyStatus = YyStatusNoMemory;
  464. GotoMap = NULL;
  465. TokenCount = Context->TokenCount;
  466. //
  467. // Allocate the goto map array and a working array used during construction.
  468. // Allocate an extra slot because many functions use GotoMap[myindex + 1] as
  469. // their terminating bound.
  470. //
  471. WorkingMap = YypAllocate(
  472. (Context->NonTerminalCount + 1) * sizeof(YY_GOTO_INDEX));
  473. if (WorkingMap == NULL) {
  474. goto SetGotoMapEnd;
  475. }
  476. GotoMap = YypAllocate(
  477. (Context->NonTerminalCount + 1) * sizeof(YY_GOTO_INDEX));
  478. if (GotoMap == NULL) {
  479. goto SetGotoMapEnd;
  480. }
  481. //
  482. // The gotos are created by going through all the shifts. Start by counting
  483. // them, and figuring the size for each symbol bucket.
  484. //
  485. Lalr->GotoCount = 0;
  486. Shifts = Context->FirstShift;
  487. while (Shifts != NULL) {
  488. //
  489. // Go backwards to get all the non-terminals only.
  490. //
  491. for (ShiftIndex = Shifts->Count - 1; ShiftIndex >= 0; ShiftIndex -= 1) {
  492. DestinationState = Shifts->States[ShiftIndex];
  493. Symbol = Context->AccessingSymbol[DestinationState];
  494. if (Symbol < TokenCount) {
  495. break;
  496. }
  497. if (Lalr->GotoCount >= YY_MAX_GOTOS) {
  498. YyStatus = YyStatusTooManyItems;
  499. goto SetGotoMapEnd;
  500. }
  501. Lalr->GotoCount += 1;
  502. //
  503. // Count for each shift symbol how many gotos transition on it.
  504. //
  505. GotoMap[Symbol - TokenCount] += 1;
  506. }
  507. Shifts = Shifts->Next;
  508. }
  509. //
  510. // Now convert those counts into indices into one big array. The working
  511. // map will be the current index for a symbol array.
  512. //
  513. GotoIndex = 0;
  514. for (Symbol = 0; Symbol < Context->NonTerminalCount; Symbol += 1) {
  515. WorkingMap[Symbol] = GotoIndex;
  516. GotoIndex += GotoMap[Symbol];
  517. }
  518. //
  519. // Copy it to the goto map.
  520. //
  521. for (Symbol = 0; Symbol < Context->NonTerminalCount; Symbol += 1) {
  522. GotoMap[Symbol] = WorkingMap[Symbol];
  523. }
  524. WorkingMap[Symbol] = Lalr->GotoCount;
  525. GotoMap[Symbol] = Lalr->GotoCount;
  526. //
  527. // Allocate the from and to state arrays that actually describe the gotos.
  528. //
  529. assert(GotoIndex == Lalr->GotoCount);
  530. Context->FromState = YypAllocate(GotoIndex * sizeof(YY_STATE_INDEX));
  531. if (Context->FromState == NULL) {
  532. goto SetGotoMapEnd;
  533. }
  534. Context->ToState = YypAllocate(GotoIndex * sizeof(YY_STATE_INDEX));
  535. if (Context->ToState == NULL) {
  536. goto SetGotoMapEnd;
  537. }
  538. //
  539. // Now go through again and set the from and to states corresponding to the
  540. // shifts.
  541. //
  542. Goal = Context->Items[1];
  543. Shifts = Context->FirstShift;
  544. while (Shifts != NULL) {
  545. for (ShiftIndex = Shifts->Count - 1; ShiftIndex >= 0; ShiftIndex -= 1) {
  546. DestinationState = Shifts->States[ShiftIndex];
  547. Symbol = Context->AccessingSymbol[DestinationState];
  548. if (Symbol < TokenCount) {
  549. break;
  550. }
  551. GotoIndex = WorkingMap[Symbol - TokenCount];
  552. //
  553. // Remember the goto for the final state, as it needs to get an EOF
  554. // set in the initial follow set.
  555. //
  556. if (Symbol == Goal) {
  557. Lalr->StartGoto = GotoIndex;
  558. }
  559. WorkingMap[Symbol - TokenCount] += 1;
  560. Context->FromState[GotoIndex] = Shifts->Number;
  561. Context->ToState[GotoIndex] = DestinationState;
  562. }
  563. Shifts = Shifts->Next;
  564. }
  565. YyStatus = YyStatusSuccess;
  566. Context->GotoMap = GotoMap;
  567. if ((Context->Flags & YYGEN_FLAG_DEBUG) != 0) {
  568. YypPrintGotoMap(Context, Lalr);
  569. }
  570. GotoMap = NULL;
  571. SetGotoMapEnd:
  572. if (GotoMap != NULL) {
  573. YypFree(GotoMap);
  574. }
  575. if (WorkingMap != NULL) {
  576. YypFree(WorkingMap);
  577. }
  578. return YyStatus;
  579. }
  580. YY_STATUS
  581. YypInitializeFollows (
  582. PYYGEN_CONTEXT Context,
  583. PYYGEN_LALR_CONTEXT Lalr
  584. )
  585. /*++
  586. Routine Description:
  587. This routine performs some initialization of the FOLLOW set.
  588. Arguments:
  589. Context - Supplies a pointer to the generator context.
  590. Lalr - Supplies a pointer to the LALR context.
  591. Return Value:
  592. YY status.
  593. --*/
  594. {
  595. ULONG CopyIndex;
  596. PYY_GOTO_INDEX EdgeCopy;
  597. ULONG EdgeCount;
  598. PYY_GOTO_INDEX Edges;
  599. YY_GOTO_INDEX GotoIndex;
  600. PYY_GOTO_INDEX *Reads;
  601. PULONG Row;
  602. YY_VALUE ShiftCount;
  603. ULONG ShiftIndex;
  604. PYYGEN_SHIFTS Shifts;
  605. YY_STATE_INDEX State;
  606. YY_VALUE Symbol;
  607. ULONG WordCount;
  608. YY_STATUS YyStatus;
  609. YyStatus = YyStatusNoMemory;
  610. Edges = NULL;
  611. Reads = NULL;
  612. WordCount = Lalr->GotoCount * Lalr->TokenSetSize;
  613. Lalr->GotoFollows = YypAllocate(WordCount * sizeof(ULONG));
  614. if (Lalr->GotoFollows == NULL) {
  615. goto InitializeFirstsEnd;
  616. }
  617. Reads = YypAllocate(Lalr->GotoCount * sizeof(PYY_GOTO_INDEX));
  618. if (Reads == NULL) {
  619. goto InitializeFirstsEnd;
  620. }
  621. Edges = YypAllocate(Lalr->GotoCount * sizeof(YY_GOTO_INDEX));
  622. if (Edges == NULL) {
  623. goto InitializeFirstsEnd;
  624. }
  625. //
  626. // Loop through every goto, initializing the token bitmap for that row in
  627. // the lookahead graph.
  628. //
  629. EdgeCount = 0;
  630. Row = Lalr->GotoFollows;
  631. for (GotoIndex = 0; GotoIndex < Lalr->GotoCount; GotoIndex += 1) {
  632. //
  633. // Go through all the shifts out of the destination state. Add the
  634. // shift tokens that shift out of the destination state to the bitmap.
  635. //
  636. State = Context->ToState[GotoIndex];
  637. Shifts = Context->ShiftTable[State];
  638. if (Shifts != NULL) {
  639. ShiftCount = Shifts->Count;
  640. for (ShiftIndex = 0; ShiftIndex < ShiftCount; ShiftIndex += 1) {
  641. //
  642. // Get the symbol that shifts out of the state.
  643. //
  644. Symbol = Context->AccessingSymbol[Shifts->States[ShiftIndex]];
  645. //
  646. // Stop at the first non-terminal.
  647. //
  648. if (Symbol >= Context->TokenCount) {
  649. break;
  650. }
  651. YYGEN_BITMAP_SET(Row, Symbol);
  652. }
  653. //
  654. // Now for the non-terminal shifts. For those non-terminal shifts
  655. // that are nullable (empty), add the goto edge out of that state
  656. // to the current list of edges, since they will have to be
  657. // traversed through to find the actual first symbol.
  658. //
  659. while (ShiftIndex < ShiftCount) {
  660. Symbol = Context->AccessingSymbol[Shifts->States[ShiftIndex]];
  661. assert(Symbol >= Context->TokenCount);
  662. if (Context->Nullable[Symbol] != FALSE) {
  663. Edges[EdgeCount] = YypFindGoto(Context, State, Symbol);
  664. EdgeCount += 1;
  665. }
  666. ShiftIndex += 1;
  667. }
  668. //
  669. // If there were any edges, add the edges to the list of edges to
  670. // traverse.
  671. //
  672. if (EdgeCount != 0) {
  673. EdgeCopy = YypAllocate((EdgeCount + 1) * sizeof(YY_GOTO_INDEX));
  674. if (EdgeCopy == NULL) {
  675. goto InitializeFirstsEnd;
  676. }
  677. Reads[GotoIndex] = EdgeCopy;
  678. for (CopyIndex = 0; CopyIndex < EdgeCount; CopyIndex += 1) {
  679. EdgeCopy[CopyIndex] = Edges[CopyIndex];
  680. }
  681. EdgeCopy[EdgeCount] = -1;
  682. EdgeCount = 0;
  683. }
  684. }
  685. Row += Lalr->TokenSetSize;
  686. }
  687. //
  688. // The goto for the starting symbol is followed by EOF.
  689. //
  690. Row = Lalr->GotoFollows + (Lalr->StartGoto * Lalr->TokenSetSize);
  691. YYGEN_BITMAP_SET(Row, 0);
  692. //
  693. // Traverse through the empty states to figure out the terminals that
  694. // follow after that.
  695. //
  696. YyStatus = YypBuildDigraph(Context, Lalr, Reads);
  697. if ((Context->Flags & YYGEN_FLAG_DEBUG) != 0) {
  698. printf("\nInitial Follows:");
  699. YypPrintTokenBitmapArray(Context, Lalr->GotoFollows, Lalr->GotoCount);
  700. }
  701. InitializeFirstsEnd:
  702. for (GotoIndex = 0; GotoIndex < Lalr->GotoCount; GotoIndex += 1) {
  703. if (Reads[GotoIndex] != NULL) {
  704. YypFree(Reads[GotoIndex]);
  705. }
  706. }
  707. if (Reads != NULL) {
  708. YypFree(Reads);
  709. }
  710. if (Edges != NULL) {
  711. YypFree(Edges);
  712. }
  713. return YyStatus;
  714. }
  715. YY_STATUS
  716. YypBuildRelations (
  717. PYYGEN_CONTEXT Context,
  718. PYYGEN_LALR_CONTEXT Lalr
  719. )
  720. /*++
  721. Routine Description:
  722. This routine builds the includes graph.
  723. Arguments:
  724. Context - Supplies a pointer to the generator context.
  725. Lalr - Supplies a pointer to the LALR context.
  726. Return Value:
  727. YY status.
  728. --*/
  729. {
  730. YY_STATE_INDEX CurrentState;
  731. PYY_GOTO_INDEX Destination;
  732. BOOL Done;
  733. ULONG EdgeCount;
  734. PYY_GOTO_INDEX Edges;
  735. YY_STATE_INDEX FromState;
  736. YY_VALUE FromSymbol;
  737. YY_GOTO_INDEX GotoIndex;
  738. PYY_VALUE Items;
  739. YY_VALUE LeftSide;
  740. ULONG Length;
  741. YY_VALUE RightSymbol;
  742. YY_RULE_INDEX RuleIndex;
  743. ULONG ShiftIndex;
  744. PYYGEN_SHIFTS Shifts;
  745. PYY_GOTO_INDEX Source;
  746. PYY_STATE_INDEX States;
  747. PYY_GOTO_INDEX *TransposedIncludes;
  748. YY_STATUS YyStatus;
  749. YyStatus = YyStatusNoMemory;
  750. Edges = NULL;
  751. States = NULL;
  752. Lalr->Includes = YypAllocate(Lalr->GotoCount * sizeof(PYY_GOTO_INDEX));
  753. if (Lalr->Includes == NULL) {
  754. goto BuildRelationsEnd;
  755. }
  756. Edges = YypAllocate((Lalr->GotoCount + 1) * sizeof(YY_GOTO_INDEX));
  757. if (Edges == NULL) {
  758. goto BuildRelationsEnd;
  759. }
  760. States = YypAllocate((Lalr->MaxRightLength + 1) * sizeof(YY_STATE_INDEX));
  761. if (States == NULL) {
  762. goto BuildRelationsEnd;
  763. }
  764. //
  765. // Loop through all the gotos.
  766. //
  767. for (GotoIndex = 0; GotoIndex < Lalr->GotoCount; GotoIndex += 1) {
  768. EdgeCount = 0;
  769. FromState = Context->FromState[GotoIndex];
  770. FromSymbol = Context->AccessingSymbol[Context->ToState[GotoIndex]];
  771. //
  772. // Loop through every rule in the production for the from state.
  773. //
  774. RuleIndex = Context->Derives[FromSymbol];
  775. LeftSide = Context->Rules[RuleIndex].LeftSide;
  776. do {
  777. Length = 1;
  778. States[0] = FromState;
  779. CurrentState = FromState;
  780. //
  781. // Loop through all the right hand side items for this rule.
  782. // Generate the array of states that represents seeing each of
  783. // these items.
  784. //
  785. Items = Context->Items + Context->Rules[RuleIndex].RightSide;
  786. while (*Items >= 0) {
  787. RightSymbol = *Items;
  788. //
  789. // Find the next state from the current one that is entered via
  790. // the current right hand side symbol.
  791. //
  792. Shifts = Context->ShiftTable[CurrentState];
  793. for (ShiftIndex = 0;
  794. ShiftIndex < Shifts->Count;
  795. ShiftIndex += 1) {
  796. CurrentState = Shifts->States[ShiftIndex];
  797. if (Context->AccessingSymbol[CurrentState] == RightSymbol) {
  798. break;
  799. }
  800. }
  801. States[Length] = CurrentState;
  802. Length += 1;
  803. Items += 1;
  804. }
  805. //
  806. // Add a lookback edge which says that the final state reached for
  807. // a particular rule corresponds to this goto.
  808. //
  809. YyStatus = YypAddLookbackEdge(Context,
  810. Lalr,
  811. CurrentState,
  812. RuleIndex,
  813. GotoIndex);
  814. if (YyStatus != YyStatusSuccess) {
  815. goto BuildRelationsEnd;
  816. }
  817. //
  818. // Now go through that sequence of states backwards. While the
  819. // last state is empty, add an edge to traverse later.
  820. //
  821. Length -= 1;
  822. do {
  823. Done = TRUE;
  824. Items -= 1;
  825. RightSymbol = *Items;
  826. if (RightSymbol >= Context->TokenCount) {
  827. Length -= 1;
  828. CurrentState = States[Length];
  829. Edges[EdgeCount] = YypFindGoto(Context,
  830. CurrentState,
  831. RightSymbol);
  832. EdgeCount += 1;
  833. if ((Context->Nullable[RightSymbol] != FALSE) &&
  834. (Length > 0)) {
  835. Done = FALSE;
  836. }
  837. }
  838. } while (Done == FALSE);
  839. RuleIndex += 1;
  840. } while (LeftSide == Context->Rules[RuleIndex].LeftSide);
  841. //
  842. // Save the edges to be traversed.
  843. //
  844. if (EdgeCount != 0) {
  845. Destination = YypAllocate((EdgeCount + 1) * sizeof(YY_GOTO_INDEX));
  846. if (Destination == NULL) {
  847. YyStatus = YyStatusNoMemory;
  848. goto BuildRelationsEnd;
  849. }
  850. Lalr->Includes[GotoIndex] = Destination;
  851. Source = Edges;
  852. while (EdgeCount != 0) {
  853. *Destination = *Source;
  854. Destination += 1;
  855. Source += 1;
  856. EdgeCount -= 1;
  857. }
  858. *Destination = -1;
  859. }
  860. }
  861. TransposedIncludes = YypTranspose(Lalr->Includes, Lalr->GotoCount);
  862. if (TransposedIncludes == NULL) {
  863. YyStatus = YyStatusNoMemory;
  864. goto BuildRelationsEnd;
  865. }
  866. //
  867. // Destroy the old includes and replace with the transposed one.
  868. //
  869. for (GotoIndex = 0; GotoIndex < Lalr->GotoCount; GotoIndex += 1) {
  870. if (Lalr->Includes[GotoIndex] != NULL) {
  871. YypFree(Lalr->Includes[GotoIndex]);
  872. }
  873. }
  874. YypFree(Lalr->Includes);
  875. Lalr->Includes = TransposedIncludes;
  876. if ((Context->Flags & YYGEN_FLAG_DEBUG) != 0) {
  877. YypPrintIncludes(Context, Lalr);
  878. }
  879. YyStatus = YyStatusSuccess;
  880. BuildRelationsEnd:
  881. if (Edges != NULL) {
  882. YypFree(Edges);
  883. }
  884. if (States != NULL) {
  885. YypFree(States);
  886. }
  887. return YyStatus;
  888. }
  889. YY_STATUS
  890. YypAddLookbackEdge (
  891. PYYGEN_CONTEXT Context,
  892. PYYGEN_LALR_CONTEXT Lalr,
  893. YY_STATE_INDEX State,
  894. YY_RULE_INDEX Rule,
  895. YY_GOTO_INDEX Goto
  896. )
  897. /*++
  898. Routine Description:
  899. This routine adds a lookback edge for the given state and rule number.
  900. Arguments:
  901. Context - Supplies a pointer to the generator context.
  902. Lalr - Supplies a pointer to the LALR context.
  903. State - Supplies the state index to add the lookback under.
  904. Rule - Supplies the rule index within the state to add the lookback under.
  905. Goto - Supplies the goto number adding the lookback.
  906. Return Value:
  907. YY status.
  908. --*/
  909. {
  910. YY_VALUE Index;
  911. PYYGEN_LOOKBACK Lookback;
  912. for (Index = Context->Lookaheads[State];
  913. Index < Context->Lookaheads[State + 1];
  914. Index += 1) {
  915. if (Context->LookaheadRule[Index] == Rule) {
  916. break;
  917. }
  918. }
  919. assert(Index != Context->Lookaheads[State + 1]);
  920. Lookback = YypAllocate(sizeof(YYGEN_LOOKBACK));
  921. if (Lookback == NULL) {
  922. return YyStatusNoMemory;
  923. }
  924. Lookback->Goto = Goto;
  925. Lookback->Next = Lalr->Lookback[Index];
  926. Lalr->Lookback[Index] = Lookback;
  927. return YyStatusSuccess;
  928. }
  929. YY_STATUS
  930. YypComputeFollowSet (
  931. PYYGEN_CONTEXT Context,
  932. PYYGEN_LALR_CONTEXT Lalr
  933. )
  934. /*++
  935. Routine Description:
  936. This routine computes the FOLLOW set for all non-terminal symbols.
  937. Arguments:
  938. Context - Supplies a pointer to the generator context.
  939. Lalr - Supplies a pointer to the LALR context.
  940. Return Value:
  941. YY Status.
  942. --*/
  943. {
  944. YY_STATUS YyStatus;
  945. YyStatus = YypBuildDigraph(Context, Lalr, Lalr->Includes);
  946. if ((Context->Flags & YYGEN_FLAG_DEBUG) != 0) {
  947. printf("\nFollows:");
  948. YypPrintTokenBitmapArray(Context, Lalr->GotoFollows, Lalr->GotoCount);
  949. }
  950. return YyStatus;
  951. }
  952. VOID
  953. YypComputeLookaheads (
  954. PYYGEN_CONTEXT Context,
  955. PYYGEN_LALR_CONTEXT Lalr
  956. )
  957. /*++
  958. Routine Description:
  959. This routine computes lookahead set based on the FOLLOWS and relations.
  960. Arguments:
  961. Context - Supplies a pointer to the generator context.
  962. Lalr - Supplies a pointer to the LALR context.
  963. Return Value:
  964. None.
  965. --*/
  966. {
  967. YY_VALUE Count;
  968. PULONG Destination;
  969. PULONG End;
  970. YY_VALUE Index;
  971. PYYGEN_LOOKBACK Lookback;
  972. PULONG Row;
  973. PULONG Source;
  974. Row = Context->LookaheadSets;
  975. Count = Context->Lookaheads[Context->StateCount];
  976. for (Index = 0; Index < Count; Index += 1) {
  977. End = Row + Lalr->TokenSetSize;
  978. //
  979. // OR in the follow sets from the gotos in the lookbacks to this follow
  980. // set.
  981. //
  982. Lookback = Lalr->Lookback[Index];
  983. while (Lookback != NULL) {
  984. Destination = Row;
  985. Source = Lalr->GotoFollows + (Lookback->Goto * Lalr->TokenSetSize);
  986. while (Destination < End) {
  987. *Destination |= *Source;
  988. Destination += 1;
  989. Source += 1;
  990. }
  991. Lookback = Lookback->Next;
  992. }
  993. //
  994. // Move to the next row for the next lookahead set.
  995. //
  996. Row = End;
  997. }
  998. if ((Context->Flags & YYGEN_FLAG_DEBUG) != 0) {
  999. printf("\nLookaheads:");
  1000. YypPrintTokenBitmapArray(Context,
  1001. Context->LookaheadSets,
  1002. Context->StateCount);
  1003. }
  1004. return;
  1005. }
  1006. YY_STATUS
  1007. YypBuildDigraph (
  1008. PYYGEN_CONTEXT Context,
  1009. PYYGEN_LALR_CONTEXT Lalr,
  1010. PYY_GOTO_INDEX *Relations
  1011. )
  1012. /*++
  1013. Routine Description:
  1014. This routine builds a directed graph from an array of edges.
  1015. Arguments:
  1016. Context - Supplies a pointer to the generator context.
  1017. Lalr - Supplies a pointer to the LALR context.
  1018. Relations - Supplies the array of relations. Each element is an array of
  1019. nodes that are reachable from that given index.
  1020. Return Value:
  1021. YY status.
  1022. --*/
  1023. {
  1024. YY_GOTO_INDEX GotoIndex;
  1025. YY_STATUS YyStatus;
  1026. YyStatus = YyStatusNoMemory;
  1027. Lalr->Relations = Relations;
  1028. Lalr->Infinity = Lalr->GotoCount + 2;
  1029. if (Lalr->GotoVertex == NULL) {
  1030. Lalr->GotoVertex =
  1031. YypAllocate((Lalr->GotoCount + 1) * sizeof(YY_GOTO_INDEX));
  1032. if (Lalr->GotoVertex == NULL) {
  1033. goto BuildDigraphEnd;
  1034. }
  1035. }
  1036. if (Lalr->Vertices == NULL) {
  1037. Lalr->Vertices =
  1038. YypAllocate((Lalr->GotoCount + 1) * sizeof(YY_GOTO_INDEX));
  1039. if (Lalr->Vertices == NULL) {
  1040. goto BuildDigraphEnd;
  1041. }
  1042. }
  1043. //
  1044. // Reset the index array to indicate no vertices have been visited.
  1045. //
  1046. Lalr->Top = 0;
  1047. for (GotoIndex = 0; GotoIndex < Lalr->GotoCount; GotoIndex += 1) {
  1048. Lalr->GotoVertex[GotoIndex] = 0;
  1049. }
  1050. //
  1051. // Traverse each goto array. Watch out that the traverse function didn't
  1052. // recurse and traverse that index itself.
  1053. //
  1054. for (GotoIndex = 0; GotoIndex < Lalr->GotoCount; GotoIndex += 1) {
  1055. if ((Lalr->GotoVertex[GotoIndex] == 0) &&
  1056. (Relations[GotoIndex] != NULL)) {
  1057. YypTraverseDigraph(Context, Lalr, GotoIndex);
  1058. }
  1059. }
  1060. YyStatus = YyStatusSuccess;
  1061. BuildDigraphEnd:
  1062. Lalr->Relations = NULL;
  1063. return YyStatus;
  1064. }
  1065. VOID
  1066. YypTraverseDigraph (
  1067. PYYGEN_CONTEXT Context,
  1068. PYYGEN_LALR_CONTEXT Lalr,
  1069. YY_GOTO_INDEX GotoIndex
  1070. )
  1071. /*++
  1072. Routine Description:
  1073. This routine traverses a vertex in the digraph.
  1074. Arguments:
  1075. Context - Supplies a pointer to the generator context.
  1076. Lalr - Supplies a pointer to the LALR context.
  1077. GotoIndex - Supplies the goto index to traverse edges for.
  1078. Return Value:
  1079. None.
  1080. --*/
  1081. {
  1082. PULONG Base;
  1083. PULONG Destination;
  1084. YY_GOTO_INDEX Edge;
  1085. PYY_GOTO_INDEX Edges;
  1086. PULONG End;
  1087. YY_GOTO_INDEX Height;
  1088. PULONG Source;
  1089. //
  1090. // Create a new vertex for this goto.
  1091. //
  1092. Lalr->Top += 1;
  1093. Lalr->Vertices[Lalr->Top] = GotoIndex;
  1094. Lalr->GotoVertex[GotoIndex] = Lalr->Top;
  1095. Height = Lalr->Top;
  1096. //
  1097. // Get the FOLLOW token bitmap for this goto index.
  1098. //
  1099. Base = Lalr->GotoFollows + (GotoIndex * Lalr->TokenSetSize);
  1100. End = Base + Lalr->TokenSetSize;
  1101. Edges = Lalr->Relations[GotoIndex];
  1102. if (Edges != NULL) {
  1103. while (*Edges >= 0) {
  1104. Edge = *Edges;
  1105. Edges += 1;
  1106. //
  1107. // If this is a never before explored goto, go explore it.
  1108. //
  1109. if (Lalr->GotoVertex[Edge] == 0) {
  1110. YypTraverseDigraph(Context, Lalr, Edge);
  1111. }
  1112. //
  1113. // If the vertex for the goto being explored is farther that the
  1114. // destination, then set the vertex for this goto to the edges
  1115. // vertex. Meaning if this is reachable faster, use the faster
  1116. // route.
  1117. //
  1118. if (Lalr->GotoVertex[GotoIndex] > Lalr->GotoVertex[Edge]) {
  1119. Lalr->GotoVertex[GotoIndex] = Lalr->GotoVertex[Edge];
  1120. }
  1121. //
  1122. // Absorb the follows of the reachable edge.
  1123. //
  1124. Destination = Base;
  1125. Source = Lalr->GotoFollows + (Edge * Lalr->TokenSetSize);
  1126. while (Destination < End) {
  1127. *Destination |= *Source;
  1128. Destination += 1;
  1129. Source += 1;
  1130. }
  1131. }
  1132. }
  1133. //
  1134. // If this vertex only expanded outwards and did not have any edges
  1135. // pointing backwards towards previous edges, then remove those vertices,
  1136. // since they'll never be more useful than this one. Also propagate the
  1137. // follow set of this one out to those dead ones.
  1138. //
  1139. if (Lalr->GotoVertex[GotoIndex] == Height) {
  1140. while (TRUE) {
  1141. Edge = Lalr->Vertices[Lalr->Top];
  1142. Lalr->Top -= 1;
  1143. Lalr->GotoVertex[Edge] = Lalr->Infinity;
  1144. if (Edge == GotoIndex) {
  1145. break;
  1146. }
  1147. Source = Base;
  1148. Destination = Lalr->GotoFollows + (Edge * Lalr->TokenSetSize);
  1149. while (Source < End) {
  1150. *Destination = *Source;
  1151. Destination += 1;
  1152. Source += 1;
  1153. }
  1154. }
  1155. }
  1156. return;
  1157. }
  1158. PYY_GOTO_INDEX *
  1159. YypTranspose (
  1160. PYY_GOTO_INDEX *Relations,
  1161. YY_GOTO_INDEX Count
  1162. )
  1163. /*++
  1164. Routine Description:
  1165. This routine transposes the relations array.
  1166. Arguments:
  1167. Relations - Supplies an array of goto index arrays to transpose.
  1168. Count - Supplies the number of gotos.
  1169. Return Value:
  1170. Returns the transposed arrays on success.
  1171. NULL on allocation failure.
  1172. --*/
  1173. {
  1174. PYY_GOTO_INDEX *Current;
  1175. ULONG EdgeCount;
  1176. PULONG EdgeCounts;
  1177. PYY_GOTO_INDEX Edges;
  1178. YY_GOTO_INDEX Index;
  1179. PYY_GOTO_INDEX *NewRelations;
  1180. YY_STATUS YyStatus;
  1181. YyStatus = YyStatusNoMemory;
  1182. NewRelations = NULL;
  1183. Current = NULL;
  1184. EdgeCounts = YypAllocate(Count * sizeof(ULONG));
  1185. if (EdgeCounts == NULL) {
  1186. goto TransposeEnd;
  1187. }
  1188. //
  1189. // Count how many times each goto appears.
  1190. //
  1191. for (Index = 0; Index < Count; Index += 1) {
  1192. Edges = Relations[Index];
  1193. if (Edges != NULL) {
  1194. while (*Edges >= 0) {
  1195. EdgeCounts[*Edges] += 1;
  1196. Edges += 1;
  1197. }
  1198. }
  1199. }
  1200. NewRelations = YypAllocate(Count * sizeof(PYY_GOTO_INDEX));
  1201. if (NewRelations == NULL) {
  1202. goto TransposeEnd;
  1203. }
  1204. Current = YypAllocate(Count * sizeof(PYY_GOTO_INDEX));
  1205. if (Current == NULL) {
  1206. goto TransposeEnd;
  1207. }
  1208. //
  1209. // Allocate the inner arrays now that the sizes of each are known.
  1210. //
  1211. for (Index = 0; Index < Count; Index += 1) {
  1212. EdgeCount = EdgeCounts[Index];
  1213. if (EdgeCount > 0) {
  1214. NewRelations[Index] =
  1215. YypAllocate((EdgeCount + 1) * sizeof(YY_GOTO_INDEX));
  1216. if (NewRelations[Index] == NULL) {
  1217. goto TransposeEnd;
  1218. }
  1219. Current[Index] = NewRelations[Index];
  1220. NewRelations[Index][EdgeCount] = -1;
  1221. }
  1222. }
  1223. //
  1224. // Fill in the arrays.
  1225. //
  1226. for (Index = 0; Index < Count; Index += 1) {
  1227. Edges = Relations[Index];
  1228. if (Edges != NULL) {
  1229. while (*Edges >= 0) {
  1230. *(Current[*Edges]) = Index;
  1231. Current[*Edges] += 1;
  1232. Edges += 1;
  1233. }
  1234. }
  1235. }
  1236. YyStatus = YyStatusSuccess;
  1237. TransposeEnd:
  1238. if (YyStatus != YyStatusSuccess) {
  1239. if (NewRelations != NULL) {
  1240. for (Index = 0; Index < Count; Index += 1) {
  1241. if (NewRelations[Index] != NULL) {
  1242. YypFree(NewRelations[Index]);
  1243. }
  1244. }
  1245. YypFree(NewRelations);
  1246. NewRelations = NULL;
  1247. }
  1248. }
  1249. if (EdgeCounts != NULL) {
  1250. YypFree(EdgeCounts);
  1251. }
  1252. if (Current != NULL) {
  1253. YypFree(Current);
  1254. }
  1255. return NewRelations;
  1256. }
  1257. YY_GOTO_INDEX
  1258. YypFindGoto (
  1259. PYYGEN_CONTEXT Context,
  1260. YY_STATE_INDEX State,
  1261. YY_VALUE Symbol
  1262. )
  1263. /*++
  1264. Routine Description:
  1265. This routine finds the goto corresponding to the given source (from) state
  1266. and symbol.
  1267. Arguments:
  1268. Context - Supplies a pointer to the generator context.
  1269. State - Supplies the index of the source state of the goto.
  1270. Symbol - Supplies the symbol the state uses to transition.
  1271. Return Value:
  1272. Returns the goto index corresponding to the given state and symbol.
  1273. --*/
  1274. {
  1275. YY_STATE_INDEX FromState;
  1276. YY_GOTO_INDEX High;
  1277. YY_GOTO_INDEX Low;
  1278. YY_GOTO_INDEX Middle;
  1279. //
  1280. // The goto map starts at the first non-terminal.
  1281. //
  1282. Symbol -= Context->TokenCount;
  1283. //
  1284. // Throw a little binary search in there to make it jazzy.
  1285. //
  1286. Low = Context->GotoMap[Symbol];
  1287. High = Context->GotoMap[Symbol + 1];
  1288. while (TRUE) {
  1289. assert(Low <= High);
  1290. Middle = (Low + High) / 2;
  1291. FromState = Context->FromState[Middle];
  1292. if (FromState == State) {
  1293. return Middle;
  1294. } else if (FromState < State) {
  1295. Low = Middle + 1;
  1296. } else {
  1297. High = Middle - 1;
  1298. }
  1299. }
  1300. //
  1301. // Execution never gets here.
  1302. //
  1303. assert(FALSE);
  1304. return YY_MAX_GOTOS;
  1305. }
  1306. VOID
  1307. YypPrintGotoMap (
  1308. PYYGEN_CONTEXT Context,
  1309. PYYGEN_LALR_CONTEXT Lalr
  1310. )
  1311. /*++
  1312. Routine Description:
  1313. This routine prints the initial goto map.
  1314. Arguments:
  1315. Context - Supplies a pointer to the generator context.
  1316. Lalr - Supplies a pointer to the LALR context.
  1317. Return Value:
  1318. None.
  1319. --*/
  1320. {
  1321. YY_STATE_INDEX Destination;
  1322. YY_GOTO_INDEX Index;
  1323. printf("\nGoto map:\n");
  1324. for (Index = 0; Index < Lalr->GotoCount; Index += 1) {
  1325. Destination = Context->ToState[Index];
  1326. printf(" %d: %d -> %d via %s\n",
  1327. Index,
  1328. Context->FromState[Index],
  1329. Destination,
  1330. Context->Elements[Context->AccessingSymbol[Destination]].Name);
  1331. }
  1332. return;
  1333. }
  1334. VOID
  1335. YypPrintTokenBitmapArray (
  1336. PYYGEN_CONTEXT Context,
  1337. PULONG BitmapArray,
  1338. YY_VALUE Count
  1339. )
  1340. /*++
  1341. Routine Description:
  1342. This routine prints an array of token bitmaps.
  1343. Arguments:
  1344. Context - Supplies a pointer to the generator context.
  1345. BitmapArray - Supplies a pointer to the array of token bitmaps.
  1346. Count - Supplies the number of elements in the (outer) array.
  1347. Return Value:
  1348. None.
  1349. --*/
  1350. {
  1351. YY_GOTO_INDEX Index;
  1352. PULONG Row;
  1353. ULONG RowSize;
  1354. YY_VALUE Symbol;
  1355. RowSize = YYGEN_BITMAP_WORD_COUNT(Context->TokenCount);
  1356. Row = BitmapArray;
  1357. for (Index = 0; Index < Count; Index += 1) {
  1358. printf("\n %d:", Index);
  1359. for (Symbol = 0; Symbol < Context->TokenCount; Symbol += 1) {
  1360. if (YYGEN_BITMAP_IS_SET(Row, Symbol)) {
  1361. printf("%s ", Context->Elements[Symbol].Name);
  1362. }
  1363. }
  1364. Row += RowSize;
  1365. }
  1366. printf("\n");
  1367. return;
  1368. }
  1369. VOID
  1370. YypPrintIncludes (
  1371. PYYGEN_CONTEXT Context,
  1372. PYYGEN_LALR_CONTEXT Lalr
  1373. )
  1374. /*++
  1375. Routine Description:
  1376. This routine prints the includes array.
  1377. Arguments:
  1378. Context - Supplies a pointer to the generator context.
  1379. Lalr - Supplies a pointer to the LALR context.
  1380. Return Value:
  1381. None.
  1382. --*/
  1383. {
  1384. PYY_GOTO_INDEX Array;
  1385. YY_GOTO_INDEX Outer;
  1386. printf("\nIncludes:");
  1387. for (Outer = 0; Outer < Lalr->GotoCount; Outer += 1) {
  1388. Array = Lalr->Includes[Outer];
  1389. if (Array == NULL) {
  1390. continue;
  1391. }
  1392. printf("\n %d: ", Outer);
  1393. while (*Array >= 0) {
  1394. printf("%d ", *Array);
  1395. Array += 1;
  1396. }
  1397. }
  1398. printf("\n");
  1399. return;
  1400. }