nc_rec 39 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. /*
  4. compile with -DNOFIRST to disable firstset optimization
  5. -DFOLLOW_OPT to enable followset optimization
  6. NOTE: Followset optimization is not
  7. supported when using -s option of LLgen
  8. -DDEBUG to print debug information
  9. */
  10. extern int LLsymb;
  11. extern int LLstartsymb;
  12. #if LL_ANSI_C
  13. void LLmessage(int);
  14. #endif
  15. struct stacks {
  16. /* Acces to the stacks is through a 'dynamic array' of pointers
  17. * to the heads. We implemented it this way to save on the number
  18. * of Malloc() calls. nr_heads is the number of heads; heads_buf_size
  19. * is the current size of heads_buf.
  20. */
  21. int nr_heads;
  22. struct stack_elt **heads_buf;
  23. int heads_buf_size;
  24. /* r_rec contains nonterminals already tried to build a new
  25. * stack with, to prevent right-recursive rules making the
  26. * process loop forever
  27. */
  28. char r_rec[(LLNNONTERMINALS + 7)/8];
  29. /* join_array contains pointers to already substituted stack
  30. * elements, so that if the same nonterminal turns up again
  31. * we can make a link
  32. */
  33. struct stack_elt *join_array[LLNNONTERMINALS];
  34. /* cleanup_buf contains pointerts to elements that can possibly
  35. * be deleted. Again this is implemented as a `growing array'.
  36. * Although it's not so clean to do it this way, it DOES save
  37. * a lot of time, mainly because much less pointer manipulation
  38. * is required, and because it's not necessary to deallocate
  39. * the buffer after each turn. Just set nr_cleanups to 0...
  40. */
  41. int nr_cleanups;
  42. int cleanup_buf_size;
  43. struct stack_elt **cleanup_buf;
  44. /* visited_buf contains pointers to elements whose flags
  45. * need to be cleared
  46. */
  47. int nr_visited;
  48. int visited_buf_size;
  49. struct stack_elt **visited_buf;
  50. /* start_seen indicates if the last prediction phase
  51. * has matched the start symbol
  52. */
  53. int start_seen;
  54. /* exp_terminals will contain the terminals that are `on top'
  55. * of the prediction graph after a prediction phase
  56. */
  57. char exp_terminals[LLSETSIZE];
  58. /* check_run_ok indicates whether a stack element can be deleted
  59. * or not
  60. */
  61. int check_run_ok;
  62. };
  63. #ifdef DEBUG
  64. static int allocates = 0;
  65. static int deallocates = 0;
  66. static int max_in_use = 0;
  67. static int edge_allocates = 0;
  68. static int edge_deallocates = 0;
  69. static int edge_max_in_use = 0;
  70. #endif
  71. static int grammar_index = 0;
  72. /* The grammar should only be build the first time we enter the
  73. * recovery routine. grammar_read == 0 indicates this has not
  74. * been done yet
  75. */
  76. static int grammar_read = 0;
  77. /* 'terminals' is an array indexed by the number of a terminal and links
  78. * all rules containing this terminal in the RHS
  79. */
  80. static struct terminal *terminals;
  81. /* 'nonterminals' is an array indexed by the number of a nonterminal
  82. * and contains all rules with this nonterminal in the LHS and links all
  83. * rules containing this nonterminal in the RHS
  84. */
  85. static struct nonterminal *nonterminals;
  86. /* These functions must be called instead of the original functions in
  87. * 'malloc.h'. They offer a checking allocation mechanism.
  88. */
  89. #if LL_ANSI_C
  90. static char *Malloc(unsigned);
  91. static char *Realloc(char*, unsigned);
  92. #else
  93. static char *Malloc();
  94. static char *Realloc();
  95. #endif
  96. /* These functions build the grammar */
  97. #if LL_ANSI_C
  98. static void init_grammar(void);
  99. static void build_grammar(void);
  100. static struct lhs *build_rule(void);
  101. static struct symbol *build_rhs(struct lhs*);
  102. static struct symbol *make_link(struct symbol*);
  103. #else
  104. static init_grammar();
  105. static build_grammar();
  106. static struct lhs *build_rule();
  107. static struct symbol *build_rhs();
  108. static struct symbol *make_link();
  109. #endif
  110. /* These functions operate on the stacks */
  111. #if LL_ANSI_C
  112. static int optimize(struct stacks*, struct symbol*, int);
  113. static void read_token(void);
  114. static void start_stack(struct stacks*, int, int);
  115. static void continuation(struct stacks*, int, int);
  116. static struct stack_elt *push_rule(struct stack_elt*, struct symbol*);
  117. static void new_head(struct stacks*, struct stack_elt*);
  118. static void to_delete(struct stacks*, struct stack_elt*);
  119. static void substitute(struct stacks*, struct stack_elt*, int);
  120. static int join(struct stacks*, struct stack_elt*, int);
  121. static int path(struct stack_elt*, struct stack_elt*);
  122. static int part_of_loop(struct stack_elt*);
  123. static void generate_heads(struct stacks*, struct stack_elt*, int);
  124. static void delete(struct stacks*, struct stack_elt*);
  125. static void hyp_run(struct stack_elt*);
  126. static void check_run(struct stacks*, struct stack_elt*);
  127. static struct stack_elt *split(struct stack_elt*);
  128. #ifdef DEBUG
  129. static void test(struct stacks*);
  130. static void dump_stack(struct stack_elt*, int);
  131. #endif
  132. static void clear_flags(struct stack_elt*, char);
  133. static void clear_gen_flags(struct stacks*);
  134. static void match_heads(struct stacks*, int);
  135. static void cleanup(struct stacks*);
  136. static void initialize(struct stacks*);
  137. static void calculate(struct stacks*, int);
  138. static void kill_stack(struct stacks *stack);
  139. void LLnc_recover(void);
  140. #else
  141. static int optimize();
  142. static read_token();
  143. static start_stack();
  144. static continuation();
  145. static struct stack_elt *push_rule();
  146. static new_head();
  147. static to_delete();
  148. static substitute();
  149. static int join();
  150. static int path();
  151. static int part_of_loop();
  152. static generate_heads();
  153. static delete();
  154. static hyp_run();
  155. static check_run();
  156. static struct stack_elt *split();
  157. static test();
  158. static dump_stack();
  159. static clear_flags();
  160. static clear_gen_flags();
  161. static match_heads();
  162. static cleanup();
  163. static initialize();
  164. static calculate();
  165. static kill_stack();
  166. LLnc_recover();
  167. #endif
  168. #if LL_ANSI_C
  169. static char *Malloc(unsigned size)
  170. #else
  171. static char *Malloc(size)
  172. unsigned size;
  173. #endif
  174. {
  175. char *p;
  176. if ((p = malloc(size)) == (char *)0) {
  177. fprintf(stderr, "fatal error: out of memory\n");
  178. exit(1);
  179. }
  180. return p;
  181. }
  182. #if LL_ANSI_C
  183. static char *Realloc(char *ptr, unsigned size)
  184. #else
  185. static char *Realloc(ptr, size)
  186. char *ptr;
  187. unsigned size;
  188. #endif
  189. {
  190. char *p;
  191. if ((p = realloc(ptr, size)) == (char *)0) {
  192. fprintf(stderr, "fatal error: out of memory\n");
  193. exit(1);
  194. }
  195. return p;
  196. }
  197. #if LL_ANSI_C
  198. static void init_grammar(void)
  199. #else
  200. static init_grammar()
  201. #endif
  202. {
  203. /* Allocate and initialize an array for terminals and nonterminals */
  204. int i;
  205. terminals = (struct terminal *)
  206. Malloc((unsigned) LLFIRST_NT * sizeof(struct terminal));
  207. for (i = 0; i < LLFIRST_NT; i++) {
  208. (terminals + i)->link = (struct symbol *)0;
  209. }
  210. nonterminals = (struct nonterminal *)
  211. Malloc((unsigned)LLNNONTERMINALS * sizeof(struct nonterminal));
  212. for (i = 0; i < LLNNONTERMINALS; i++) {
  213. (nonterminals + i)->rule = (struct lhs *)0;
  214. (nonterminals + i)->link = (struct symbol *)0;
  215. }
  216. }
  217. #if LL_ANSI_C
  218. static void build_grammar(void)
  219. #else
  220. static build_grammar()
  221. #endif
  222. {
  223. /* Build a rule for every nonterminal. The LHS must be saved first because
  224. * of the fact that the right side of an assignment statement (in C) will
  225. * be evaluated before the left side
  226. */
  227. int nt, j;
  228. init_grammar();
  229. for (j = 0; j < LLNNONTERMINALS; j++) {
  230. nt = LLgrammar[grammar_index];
  231. (nonterminals + nt - LLFIRST_NT)->rule = build_rule();
  232. }
  233. }
  234. #if LL_ANSI_C
  235. static struct lhs *build_rule(void)
  236. #else
  237. static struct lhs *build_rule()
  238. #endif
  239. {
  240. /* Build LHS and call a funcion to create RHS */
  241. struct lhs *l;
  242. int j;
  243. l = (struct lhs *)Malloc(sizeof(struct lhs));
  244. l->nr = LLgrammar[grammar_index++];
  245. /* Build first set */
  246. for (j = 0; j < LLSETSIZE; j++) {
  247. l->first[j] = LLgrammar[grammar_index++];
  248. }
  249. /* Build follow set */
  250. for (j = 0; j < LLSETSIZE; j++) {
  251. l->follow[j] = LLgrammar[grammar_index++];
  252. }
  253. l->empty = LLgrammar[grammar_index++]; /* Can NT produce empty? */
  254. l->rhs = build_rhs(l);
  255. return l;
  256. }
  257. #if LL_ANSI_C
  258. static struct symbol *build_rhs(struct lhs *l)
  259. #else
  260. static struct symbol *build_rhs(l)
  261. struct lhs *l;
  262. #endif
  263. {
  264. /* Build RHS by creating structs for all symbols including ALT and
  265. * EORULE. Also call a function for linking same terminals and
  266. * nonterminals.
  267. */
  268. struct symbol *r;
  269. r = (struct symbol *)Malloc(sizeof(struct symbol));
  270. if (LLgrammar[grammar_index] == LLALT) {
  271. grammar_index++;
  272. r->x = LLALT;
  273. r->nr = -1; /* Not applicable */
  274. r->link = (struct symbol *)0; /* Not applicable */
  275. r->next = build_rhs(l);
  276. r->lhs = l;
  277. }
  278. else if (LLgrammar[grammar_index] == LLEORULE) {
  279. grammar_index++;
  280. r->x = LLEORULE;
  281. r->nr = -1; /* Not applicable */
  282. r->link = (struct symbol *)0; /* Not applicable */
  283. r->next = (struct symbol *)0; /* Not applicable */
  284. r->lhs = l;
  285. }
  286. else if (LLgrammar[grammar_index] < LLFIRST_NT) {
  287. r->x = LLTERMINAL;
  288. r->nr = LLgrammar[grammar_index++];
  289. r->link = make_link(r);
  290. r->next = build_rhs(l);
  291. r->lhs = l;
  292. }
  293. else {
  294. r->x = LLNONTERMINAL;
  295. r->nr = LLgrammar[grammar_index++];
  296. r->link = make_link(r);
  297. r->next = build_rhs(l);
  298. r->lhs = l;
  299. }
  300. return r;
  301. }
  302. #if LL_ANSI_C
  303. static struct symbol *make_link(struct symbol *r)
  304. #else
  305. static struct symbol *make_link(r)
  306. struct symbol *r;
  307. #endif
  308. {
  309. /* Link same terminals and nonterminals. Every new symbol is appended
  310. * in front of the corresponding list for efficiency.
  311. */
  312. struct symbol *tmp;
  313. if (r->nr < LLFIRST_NT) {
  314. /* Terminal array */
  315. tmp = (terminals + r->nr)->link;
  316. (terminals + r->nr)->link = r;
  317. }
  318. else { /* Nonterminal array */
  319. tmp = (nonterminals + (r->nr - LLFIRST_NT))->link;
  320. (nonterminals + (r->nr - LLFIRST_NT))->link = r;
  321. }
  322. return tmp;
  323. }
  324. /*****************************************************************************/
  325. #if LL_ANSI_C
  326. static int optimize(struct stacks* stack, struct symbol *symb_ptr, int l_ahead)
  327. #else
  328. static int optimize(stack, symb_ptr, l_ahead)
  329. struct stacks *stack;
  330. struct symbol *symb_ptr;
  331. int l_ahead;
  332. #endif
  333. /* Return 1 if rule symb_ptr can start with terminal l_ahead, else return 0.
  334. * The array with expected terminals will also be filled in.
  335. */
  336. {
  337. struct lhs *l;
  338. int i;
  339. #ifdef NOFIRST
  340. return(1);
  341. #else
  342. if ((l_ahead <= 0) || (l_ahead == EOFILE)) return 1;
  343. switch(symb_ptr->x) {
  344. case LLTERMINAL:
  345. LLPUTIN(stack->exp_terminals, LLindex[symb_ptr->nr]);
  346. if (symb_ptr->nr != l_ahead) return 0;
  347. else return 1;/*???*/
  348. case LLNONTERMINAL:
  349. l = (nonterminals + symb_ptr->nr - LLFIRST_NT)->rule;
  350. if (LLIN(l->first, LLindex[l_ahead])) return 1;
  351. else if (l->empty) {
  352. /* Try next symbol */
  353. return optimize(stack, symb_ptr->next, l_ahead);
  354. }
  355. else {
  356. for (i = 0; i < LLSETSIZE; i++) {
  357. stack->exp_terminals[i] |= (l->first)[i];
  358. }
  359. return 0;
  360. }
  361. default:
  362. #ifndef FOLLOW_OPT
  363. return(1);
  364. #else
  365. l = (nonterminals + symb_ptr->lhs->nr - LLFIRST_NT)->rule;
  366. if (LLIN(l->follow, LLindex[l_ahead])) return 1;
  367. else {
  368. for (i = 0; i < LLSETSIZE; i++) {
  369. stack->exp_terminals[i] |= (l->follow)[i];
  370. }
  371. return 0;
  372. }
  373. #endif /*FOLLOW_OPT */
  374. }
  375. #endif /* NOFIRST */
  376. }
  377. #if LL_ANSI_C
  378. static void read_token(void)
  379. #else
  380. static read_token()
  381. #endif
  382. /* Read token and put it in global variable LLsymb, skipping
  383. * invalid tokens
  384. */
  385. {
  386. LLsymb = LL_LEXI();
  387. while (LLindex[LLsymb] < 0) {
  388. /* Skip garbage tokens */
  389. LLmessage(0);
  390. LLsymb = LL_LEXI();
  391. }
  392. }
  393. #if LL_ANSI_C
  394. static void start_stack(struct stacks *stack, int base, int l_ahead)
  395. #else
  396. static start_stack(stack, base, l_ahead)
  397. struct stacks *stack;
  398. int base, l_ahead;
  399. #endif
  400. /* Start stack on base symbol base with lookahead l_ahead */
  401. {
  402. struct stack_elt *bottom, *top;
  403. struct symbol *symb_ptr;
  404. int i;
  405. /* Find first applicable rule */
  406. symb_ptr = (terminals + base)->link;
  407. /* Now try all applicable rules */
  408. while (symb_ptr != (struct symbol *)0) {
  409. /* If the current rule cannot start with l_ahead,
  410. * try the next one
  411. */
  412. if (!optimize(stack, symb_ptr->next, l_ahead)) {
  413. symb_ptr = symb_ptr->link;
  414. continue;
  415. }
  416. if ( (symb_ptr->next->x == LLTERMINAL)
  417. || (symb_ptr->next->x == LLNONTERMINAL)
  418. ) {
  419. /* Allocate an end-of-stack */
  420. #ifdef DEBUG
  421. allocates++;
  422. if (allocates - deallocates > max_in_use) {
  423. max_in_use = allocates - deallocates;
  424. }
  425. #endif
  426. bottom = (struct stack_elt *)
  427. Malloc(sizeof(struct stack_elt));
  428. bottom->edges = (struct edge *)0;
  429. bottom->nr = LLEOSTACK;
  430. bottom->flags = 0;
  431. bottom->nr_nexts = 0;
  432. bottom->ref_count = 0;
  433. bottom->hyp_ref_count = -1;
  434. /* And use the rule to build a stack on it */
  435. top = push_rule(bottom, symb_ptr->next);
  436. /* Remember that we're now trying to match the LHS
  437. * of the used rule
  438. */
  439. bottom->matched = symb_ptr->lhs->nr;
  440. if (top->nr >= LLFIRST_NT) {
  441. substitute(stack, top, l_ahead);
  442. }
  443. else {
  444. new_head(stack, top);
  445. }
  446. /* Perhaps this only has produced an empty stack, in
  447. * that case bottom can be deallocated.
  448. */
  449. if (bottom->ref_count == 0) {
  450. to_delete(stack, bottom);
  451. }
  452. }
  453. else {
  454. /* base was the last element of the rule, so we
  455. * figure we have matched the LHS of this rule.
  456. */
  457. if (symb_ptr->lhs->nr == LLstartsymb) {
  458. stack->start_seen = 1;
  459. }
  460. continuation(stack, symb_ptr->lhs->nr, l_ahead);
  461. }
  462. symb_ptr = symb_ptr->link;
  463. }
  464. /* Reinitialize some arrays */
  465. for (i = 0; i < (LLNNONTERMINALS + 7)/8; i++) {
  466. stack->r_rec[i] = (char) 0;
  467. }
  468. for (i = 0; i < LLNNONTERMINALS; i++) {
  469. stack->join_array[i] = (struct stack_elt *)0;
  470. }
  471. /* Delete all HEAD flags */
  472. for (i = 0; i < stack->nr_heads; i++) {
  473. (*(stack->heads_buf + i))->flags &= ~LLHEAD;
  474. }
  475. /* Delete flags turned on by 'generate_heads()' */
  476. clear_gen_flags(stack);
  477. /* Try to delete elements on cleanup_buf */
  478. cleanup(stack);
  479. }
  480. #if LL_ANSI_C
  481. static void continuation(struct stacks *stack, int nt, int l_ahead)
  482. #else
  483. static continuation(stack, nt, l_ahead)
  484. struct stacks *stack;
  485. int nt, l_ahead;
  486. #endif
  487. /* We have 'eaten' a whole stack, and think we recognized nt. Now
  488. look for rules that we can proceed with, ie containing nt in the RHS.
  489. Each rule found will be developed untill a terminal is at the top
  490. of the stack.*/
  491. {
  492. struct symbol *symb_ptr;
  493. struct stack_elt *bottom, *top;
  494. /* If we've already tried this nt, don't do it again.
  495. * Otherwise we may loop forever on right-recursive rules
  496. */
  497. if (LLIN(stack->r_rec, nt - LLFIRST_NT)) return;
  498. /* Mark that we have looked for a continuation for nt */
  499. LLPUTIN(stack->r_rec, nt - LLFIRST_NT);
  500. /* Find first applicable rule */
  501. symb_ptr = (nonterminals + nt - LLFIRST_NT)->link;
  502. /* Try all applicable rules */
  503. while (symb_ptr != (struct symbol *)0) {
  504. /* If the current rule cannot start with l_ahead,
  505. * try the next one
  506. */
  507. if (!optimize(stack, symb_ptr->next, l_ahead)) {
  508. symb_ptr = symb_ptr->link;
  509. continue;
  510. }
  511. if ( (symb_ptr->next->x == LLTERMINAL)
  512. || (symb_ptr->next->x == LLNONTERMINAL)
  513. ) {
  514. #ifdef DEBUG
  515. allocates++;
  516. if (allocates - deallocates > max_in_use) {
  517. max_in_use = allocates - deallocates;
  518. }
  519. #endif
  520. bottom = (struct stack_elt *)
  521. Malloc(sizeof(struct stack_elt));
  522. bottom->edges = (struct edge *)0;
  523. bottom->nr = LLEOSTACK;
  524. bottom->flags = 0;
  525. bottom->nr_nexts = 0;
  526. bottom->ref_count = 0;
  527. bottom->hyp_ref_count = -1;
  528. /* Use the rule to build a stack on bottom */
  529. top = push_rule(bottom, symb_ptr->next);
  530. /* Remember that we're now trying to match the LHS
  531. * of the used rule
  532. */
  533. bottom->matched = symb_ptr->lhs->nr;
  534. if (top->nr >= LLFIRST_NT) {
  535. substitute(stack, top, l_ahead);
  536. }
  537. else {
  538. new_head(stack, top);
  539. }
  540. /* Perhaps this only has produced an empty stack, in
  541. * that case bottom can be deallocated.
  542. */
  543. if (bottom->ref_count == 0) {
  544. delete(stack, bottom);
  545. }
  546. }
  547. else {
  548. /* Stack is still empty */
  549. if (symb_ptr->lhs->nr == LLstartsymb) {
  550. stack->start_seen = 1;
  551. }
  552. continuation(stack, symb_ptr->lhs->nr, l_ahead);
  553. }
  554. symb_ptr = symb_ptr->link;
  555. }
  556. }
  557. #if LL_ANSI_C
  558. static struct stack_elt *push_rule(struct stack_elt *element,
  559. struct symbol *symb_ptr)
  560. #else
  561. static struct stack_elt *push_rule(element, symb_ptr)
  562. struct stack_elt *element;
  563. struct symbol *symb_ptr;
  564. #endif
  565. /* Append the rule symb_ptr to stack element 'element'. Return a
  566. * pointer to the new top of the stack
  567. */
  568. {
  569. struct stack_elt *se, *top;
  570. if ( (symb_ptr->next->x == LLTERMINAL)
  571. || (symb_ptr->next->x == LLNONTERMINAL)
  572. ) {
  573. top = push_rule(element, symb_ptr->next);
  574. }
  575. else {
  576. top = element;
  577. }
  578. #ifdef DEBUG
  579. allocates++;
  580. if (allocates - deallocates > max_in_use) {
  581. max_in_use = allocates - deallocates;
  582. }
  583. #endif
  584. se = (struct stack_elt *)Malloc(sizeof(struct stack_elt));
  585. se->flags = 0;
  586. se->nr = symb_ptr->nr;
  587. se->ref_count = 0;
  588. se->hyp_ref_count = -1;
  589. se->matched = -1;
  590. se->nr_nexts = 1;
  591. #ifdef DEBUG
  592. edge_allocates++;
  593. if (edge_allocates - edge_deallocates > edge_max_in_use) {
  594. edge_max_in_use = edge_allocates - edge_deallocates;
  595. }
  596. #endif
  597. se->edges = (struct edge *)Malloc(sizeof(struct edge));
  598. se->edges->ptr = top;
  599. se->edges->flags = 0;
  600. top->ref_count++;
  601. return se;
  602. }
  603. #if LL_ANSI_C
  604. static void new_head(struct stacks *stack, struct stack_elt *ptr)
  605. #else
  606. static new_head(stack, ptr)
  607. struct stacks *stack;
  608. struct stack_elt *ptr;
  609. #endif
  610. /* Make ptr a head of stack */
  611. {
  612. /* Is this already a head?*/
  613. if (ptr->flags & LLHEAD) return;
  614. if (stack->heads_buf_size == 0) {
  615. stack->heads_buf_size = LLHEADS_BUF_INCR;
  616. stack->heads_buf = (struct stack_elt **)
  617. Malloc(LLHEADS_BUF_INCR * sizeof(struct stack_elt *));
  618. }
  619. else if (stack->nr_heads == stack->heads_buf_size) {
  620. /* buffer full? */
  621. stack->heads_buf_size += LLHEADS_BUF_INCR;
  622. stack->heads_buf = (struct stack_elt **)
  623. Realloc((char *)
  624. stack->heads_buf, (unsigned)
  625. stack->heads_buf_size *
  626. sizeof(struct stack_elt *)
  627. );
  628. }
  629. *(stack->heads_buf + stack->nr_heads) = ptr; /* Add at the tail */
  630. stack->nr_heads++; /* Increase number of heads */
  631. ptr->flags |= LLHEAD; /* Mark it as a head */
  632. ptr->ref_count++; /* Increase reference count */
  633. LLPUTIN(stack->exp_terminals, LLindex[ptr->nr]);
  634. }
  635. #if LL_ANSI_C
  636. static void to_delete(struct stacks *stack, struct stack_elt *ptr)
  637. #else
  638. static to_delete(stack, ptr)
  639. struct stacks *stack;
  640. struct stack_elt *ptr;
  641. #endif
  642. /* Remember that ptr has to be deleted */
  643. {
  644. int i;
  645. #ifdef NOCLEAN
  646. return;
  647. #endif
  648. for (i = 0; i < stack->nr_cleanups; i++) {
  649. /* Check if already in buffer */
  650. if (*(stack->cleanup_buf + i) == ptr) return;
  651. }
  652. if (stack->cleanup_buf_size == 0) {
  653. stack->cleanup_buf_size = LLCLEANUP_BUF_INCR;
  654. stack->cleanup_buf = (struct stack_elt **)
  655. Malloc(LLCLEANUP_BUF_INCR * sizeof(struct stack_elt *));
  656. }
  657. else if (stack->nr_cleanups == stack->cleanup_buf_size) {
  658. stack->cleanup_buf_size += LLCLEANUP_BUF_INCR;
  659. stack->cleanup_buf = (struct stack_elt **)
  660. Realloc((char *) stack->cleanup_buf,
  661. (unsigned) stack->cleanup_buf_size *
  662. sizeof(struct stack_elt *));
  663. }
  664. *(stack->cleanup_buf + stack->nr_cleanups) = ptr;
  665. stack->nr_cleanups++;
  666. }
  667. #if LL_ANSI_C
  668. static void substitute(struct stacks *stack, struct stack_elt *top, int l_ahead)
  669. #else
  670. static substitute(stack, top, l_ahead)
  671. struct stacks *stack;
  672. struct stack_elt *top;
  673. int l_ahead;
  674. #endif
  675. /* This function substitutes the NT pointed to by 'top'. 'top' should be a top
  676. * of a stack
  677. */
  678. {
  679. struct symbol *symb_ptr;
  680. struct stack_elt *new_top;
  681. /* Try to join top NT */
  682. if (join(stack, top, l_ahead)) return;
  683. /* Find RHS of the rule of nonterminal 'top->nr' */
  684. symb_ptr = (nonterminals + top->nr - LLFIRST_NT)->rule->rhs;
  685. /* Mark top as dummy */
  686. top->flags |= LLDUMMY;
  687. while (1) {
  688. /* If this an empty production, search down the stack for
  689. * terminals
  690. */
  691. if ((symb_ptr->x == LLALT) || (symb_ptr->x == LLEORULE)) {
  692. generate_heads(stack, top, l_ahead);
  693. }
  694. /* Skip other empty productions, they have no effect. */
  695. while (symb_ptr->x == LLALT) {
  696. symb_ptr = symb_ptr->next;
  697. }
  698. if (symb_ptr->x == LLEORULE) {
  699. /* If there are only empty productions, the NT on top
  700. * can be deleted
  701. */
  702. if (top->ref_count == 0) {
  703. to_delete(stack, top);
  704. }
  705. return;
  706. }
  707. /* If this rule can produce 'l_ahead' on the top of the stack
  708. * substitute the nonterminal
  709. */
  710. if (optimize(stack, symb_ptr, l_ahead)) {
  711. new_top = push_rule(top, symb_ptr);
  712. /* If the new element on top is a nonterminal
  713. * substitute it, else make it a head
  714. */
  715. if (new_top->nr >= LLFIRST_NT) {
  716. substitute(stack, new_top, l_ahead);
  717. }
  718. else {
  719. new_head(stack, new_top);
  720. }
  721. }
  722. /* Search to next alternative */
  723. while ( (symb_ptr->x == LLTERMINAL)
  724. || (symb_ptr->x == LLNONTERMINAL)
  725. ) {
  726. symb_ptr = symb_ptr->next;
  727. }
  728. if (symb_ptr->x == LLEORULE) {
  729. if (top->ref_count == 0) {
  730. to_delete(stack, top);
  731. }
  732. return;
  733. }
  734. else {
  735. symb_ptr = symb_ptr->next;
  736. }
  737. }
  738. }
  739. #if LL_ANSI_C
  740. static int join(struct stacks *stack, struct stack_elt *top, int l_ahead)
  741. #else
  742. static int join(stack, top, l_ahead)
  743. struct stacks *stack;
  744. struct stack_elt *top;
  745. int l_ahead;
  746. #endif
  747. /* This function tries to connect a NT on top of a stack with another stack,
  748. * which has already substituted this NT
  749. */
  750. {
  751. struct stack_elt *se;
  752. int size;
  753. if ( (se = stack->join_array[top->nr - LLFIRST_NT]) ==
  754. (struct stack_elt *)0
  755. ) {
  756. stack->join_array[top->nr - LLFIRST_NT] = top;
  757. return 0; /* Join not possible */
  758. }
  759. else {
  760. se->nr_nexts++; /* Increase number of descendants */
  761. #ifdef DEBUG
  762. edge_allocates++;
  763. if (edge_allocates - edge_deallocates > edge_max_in_use) {
  764. edge_max_in_use = edge_allocates - edge_deallocates;
  765. }
  766. #endif
  767. /* Allocate one more pointer to descendants */
  768. size = se->nr_nexts * sizeof(struct edge);
  769. se->edges = (struct edge *)Realloc((char *) se->edges,
  770. (unsigned) size);
  771. /* Link it */
  772. (se->edges + se->nr_nexts - 1)->ptr = top->edges->ptr;
  773. (se->edges + se->nr_nexts - 1)->flags = 0;
  774. /* The successor of 'top' gets an extra predecessor.
  775. * 'top' has always only one successor because the stacks are
  776. * constructed in 'depth first' order
  777. */
  778. top->edges->ptr->ref_count++;
  779. #ifndef NOLOOPS
  780. /* If we have made a new loop find all stack elements of this
  781. * loop and mark them
  782. */
  783. if (path(top->edges->ptr, se)) {
  784. (se->edges + se->nr_nexts - 1)->flags |= LLLOOP;
  785. (se->edges + se->nr_nexts - 1)->flags |= LLYES;
  786. }
  787. clear_flags(top->edges->ptr, (LLNO | LLYES));
  788. #endif
  789. /* Check if joined NT produces empty */
  790. if ((nonterminals + se->nr - LLFIRST_NT)->rule->empty) {
  791. generate_heads(stack, top, l_ahead);
  792. }
  793. /* Deallocate top symbol */
  794. if (top->ref_count == 0) {
  795. to_delete(stack, top);
  796. }
  797. return 1;
  798. }
  799. }
  800. #ifndef NOLOOPS
  801. #if LL_ANSI_C
  802. static int path(struct stack_elt *se1, struct stack_elt *se2)
  803. #else
  804. static int path(se1, se2)
  805. struct stack_elt *se1, *se2;
  806. #endif /* LL_ANSI_C */
  807. /* If there is a path from se1 to se2 it returns 1 and marks all the paths
  808. * betweeen these two points, otherwise it returns 0. The flags LLYES and
  809. * LLNO are used for optimization. */
  810. {
  811. int i, result = 0;
  812. if (se1 == se2) return 1;
  813. for (i = 0; i < se1->nr_nexts; i++) {
  814. if ( (!((se1->edges + i)->flags & LLNO))
  815. && (!((se1->edges + i)->flags & LLLOOP_SEARCH))
  816. ) {
  817. (se1->edges + i)->flags |= LLLOOP_SEARCH;
  818. if (path((se1->edges + i)->ptr, se2)) {
  819. (se1->edges + i)->flags |= LLLOOP;
  820. result = 1;
  821. }
  822. else {
  823. (se1->edges + i)->flags |= LLNO;
  824. }
  825. (se1->edges + i)->flags &= ~LLLOOP_SEARCH;
  826. }
  827. (se1->edges + i)->flags |= LLYES;
  828. }
  829. return result;
  830. }
  831. #if LL_ANSI_C
  832. static int part_of_loop(struct stack_elt *se)
  833. #else
  834. static int part_of_loop(se)
  835. struct stack_elt *se;
  836. #endif /* LL_ANSI_C */
  837. /* Checks if 'se' belongs to a loop */
  838. {
  839. int i;
  840. for (i = 0; i < se->nr_nexts; i++) {
  841. if ((se->edges + i)->flags & LLLOOP) return 1;
  842. }
  843. return 0;
  844. }
  845. #endif /* NOLOOPS */
  846. #if LL_ANSI_C
  847. static void generate_heads(struct stacks *stack, struct stack_elt *se,
  848. int l_ahead)
  849. #else
  850. static generate_heads(stack, se, l_ahead)
  851. struct stacks *stack;
  852. struct stack_elt *se;
  853. int l_ahead;
  854. #endif
  855. /* This funcion finds all heads starting at 'se'. */
  856. {
  857. int i;
  858. struct stack_elt *next_se;
  859. for (i = 0; i < se->nr_nexts; i++) {
  860. if (!((se->edges + i)->ptr->flags & LLGEN_SEARCH)) {
  861. (se->edges + i)->ptr->flags |= LLGEN_SEARCH;
  862. next_se = (se->edges + i)->ptr;
  863. /* Remember a flag has to be cleared later */
  864. if (stack->visited_buf_size == 0) {
  865. stack->visited_buf_size = LL_VIS_INCR;
  866. stack->visited_buf = (struct stack_elt **)
  867. Malloc(LL_VIS_INCR * sizeof(struct stack_elt *));
  868. }
  869. else if (stack->nr_visited == stack->visited_buf_size) {
  870. stack->visited_buf_size += LL_VIS_INCR;
  871. stack->visited_buf = (struct stack_elt **)
  872. Realloc((char *) stack->visited_buf,
  873. (unsigned) stack->visited_buf_size *
  874. sizeof(struct stack_elt *));
  875. }
  876. *(stack->visited_buf + stack->nr_visited) = next_se;
  877. stack->nr_visited++;
  878. if (next_se->flags & LLDUMMY) {
  879. generate_heads(stack, next_se, l_ahead);
  880. }
  881. else if (next_se->nr == LLEOSTACK) {
  882. /* We have matched a nt */
  883. if (next_se->matched == LLstartsymb) {
  884. stack->start_seen = 1;
  885. }
  886. continuation(stack, next_se->matched, l_ahead);
  887. if (next_se->ref_count == 0) {
  888. to_delete(stack, next_se);
  889. }
  890. }
  891. else if (next_se->nr < LLFIRST_NT) {
  892. /* terminal */
  893. new_head(stack, next_se);
  894. }
  895. else {
  896. if (next_se->ref_count > 0) {
  897. next_se = split(next_se);
  898. }
  899. substitute(stack, next_se, l_ahead);
  900. }
  901. }
  902. }
  903. }
  904. #if LL_ANSI_C
  905. static void delete(struct stacks *stack, struct stack_elt *se)
  906. #else
  907. static delete(stack, se)
  908. struct stacks *stack;
  909. struct stack_elt *se;
  910. #endif
  911. /* This function runs down the stack(s) deleting every element which cannot be
  912. * reached anymore. */
  913. {
  914. int i;
  915. #ifdef NOCLEAN
  916. return;
  917. #endif
  918. if (se->ref_count == 0) {
  919. /* Decrease reference counts of all successors */
  920. for (i = 0; i < se->nr_nexts; i++) {
  921. if ((se->edges + i)->ptr->ref_count != 0) {
  922. (se->edges + i)->ptr->ref_count--;
  923. /* Try to delete next element */
  924. delete(stack, (se->edges + i)->ptr);
  925. }
  926. }
  927. /* If this element is saved in the join_array clear it */
  928. if (se->nr >= LLFIRST_NT) {
  929. if (stack->join_array[se->nr - LLFIRST_NT] == se) {
  930. stack->join_array[se->nr - LLFIRST_NT] =
  931. (struct stack_elt *)0;
  932. }
  933. }
  934. #ifdef DEBUG
  935. deallocates++;
  936. edge_deallocates += se->nr_nexts;
  937. #endif
  938. free((char *) se->edges);
  939. free((char *) se);
  940. }
  941. #ifndef NOLOOPS
  942. /* If this element belongs to a loop try to delete it */
  943. else if (part_of_loop(se)) {
  944. /* Do a temporary delete */
  945. hyp_run(se);
  946. /* Check it */
  947. stack->check_run_ok = 1;
  948. check_run(stack, se);
  949. /* If it can be deleted delete it */
  950. if (stack->check_run_ok) {
  951. se->ref_count = 0;
  952. delete(stack, se);
  953. }
  954. }
  955. #endif
  956. }
  957. #ifndef NOLOOPS
  958. #if LL_ANSI_C
  959. static void hyp_run(struct stack_elt *se)
  960. #else
  961. static hyp_run(se)
  962. struct stack_elt *se;
  963. #endif /* LL_ANSI_C */
  964. /* This function sets the 'hyp_ref_counts' of all elements of the loop that
  965. * 'se' belongs to to the value that 'ref_count' will get when 'se' is
  966. * deleted
  967. */
  968. {
  969. int i;
  970. struct stack_elt *next_se;
  971. for (i = 0; i < se->nr_nexts; i++) {
  972. next_se = (se->edges + i)->ptr;
  973. if ( (!((se->edges + i)->flags & LLHYP_SEARCH))
  974. && ((se->edges + i)->flags & LLLOOP)
  975. ) {
  976. (se->edges + i)->flags |= LLHYP_SEARCH;
  977. /* If this element is not yet visited initialize
  978. * 'hyp_ref_count' else decrease it by one
  979. */
  980. if (next_se->hyp_ref_count == -1) {
  981. next_se->hyp_ref_count = next_se->ref_count - 1;
  982. }
  983. else {
  984. next_se->hyp_ref_count--;
  985. }
  986. /* Continue searching */
  987. hyp_run(next_se);
  988. }
  989. }
  990. }
  991. #if LL_ANSI_C
  992. static void check_run(struct stacks *stack, struct stack_elt *se)
  993. #else
  994. static check_run(stack, se)
  995. struct stacks *stack;
  996. struct stack_elt *se;
  997. #endif /* LL_ANSI_C */
  998. /* This function checks all 'hyp_ref_counts' that 'hyp_run()' has set.
  999. * If one of them is not 0, 'check_run_ok' will be set to 0 indicating
  1000. * that 'se' cannot be deleted. 'check_run()' also resets all 'hyp_ref_counts'
  1001. */
  1002. {
  1003. int i;
  1004. if (se->hyp_ref_count > 0) {
  1005. stack->check_run_ok = 0;
  1006. }
  1007. /* Reset 'hyp_ref_count' */
  1008. se->hyp_ref_count = -1;
  1009. for (i = 0; i < se->nr_nexts; i++) {
  1010. if ((se->edges + i)->flags & LLHYP_SEARCH) {
  1011. (se->edges + i)->flags &= ~LLHYP_SEARCH;
  1012. check_run(stack, (se->edges + i)->ptr);
  1013. }
  1014. }
  1015. }
  1016. #endif /* NOLOOPS */
  1017. #if LL_ANSI_C
  1018. static struct stack_elt *split(struct stack_elt *se)
  1019. #else
  1020. static struct stack_elt *split(se)
  1021. struct stack_elt *se;
  1022. #endif
  1023. /* This function splits of a NT in de stack, and returns a pointer to it */
  1024. {
  1025. struct stack_elt *new_stack;
  1026. int i;
  1027. #ifdef DEBUG
  1028. allocates++;
  1029. if (allocates - deallocates > max_in_use) {
  1030. max_in_use = allocates - deallocates;
  1031. }
  1032. #endif
  1033. new_stack = (struct stack_elt *)Malloc(sizeof(struct stack_elt));
  1034. new_stack->flags = 0; /* Used by 'clear_gen_flags()' */
  1035. new_stack->nr = se->nr;
  1036. new_stack->ref_count = 0; /* Copy is new top */
  1037. new_stack->hyp_ref_count = -1;
  1038. new_stack->matched = -1;
  1039. new_stack->nr_nexts = se->nr_nexts;
  1040. #ifdef DEBUG
  1041. edge_allocates++;
  1042. if (edge_allocates - edge_deallocates > edge_max_in_use) {
  1043. edge_max_in_use = edge_allocates - edge_deallocates;
  1044. }
  1045. #endif
  1046. new_stack->edges = (struct edge *)
  1047. Malloc((unsigned)se->nr_nexts * sizeof(struct edge));
  1048. /* Copy gets the same successors as the original */
  1049. memcpy((char *) new_stack->edges, (char *) se->edges,
  1050. se->nr_nexts * sizeof(struct edge));
  1051. /* Each successor gets a new predecessor */
  1052. for (i = 0; i < new_stack->nr_nexts; i++) {
  1053. (new_stack->edges + i)->ptr->ref_count++;
  1054. (new_stack->edges + i)->flags = 0;
  1055. }
  1056. return new_stack;
  1057. }
  1058. #ifdef DEBUG
  1059. #if LL_ANSI_C
  1060. static void test(struct stacks *stack)
  1061. #else
  1062. static test(stack)
  1063. struct stacks *stack;
  1064. #endif
  1065. {
  1066. struct stack_elt *se;
  1067. int i;
  1068. printf("STACKS:\n");
  1069. for (i = 0; i < stack->nr_heads; i++) {
  1070. printf("%2d: ", i + 1);
  1071. if (*(stack->heads_buf + i) == (struct stack_elt *)0) {
  1072. printf("NIL\n");
  1073. continue;
  1074. }
  1075. se = *(stack->heads_buf + i);
  1076. dump_stack(se, 1);
  1077. clear_flags(se, PRINT_SEARCH);
  1078. }
  1079. }
  1080. #if LL_ANSI_C
  1081. static void dump_stack(struct stack_elt *se, int level)
  1082. #else
  1083. static dump_stack(se, level)
  1084. struct stack_elt *se;
  1085. int level;
  1086. #endif
  1087. {
  1088. int i, j;
  1089. while (se->nr != LLEOSTACK) {
  1090. if ((se->flags & LLDUMMY) && (se->nr_nexts > 1)) {
  1091. printf("[%d] <%d,%d,%d>\n",
  1092. se->nr, se->ref_count,
  1093. se->hyp_ref_count,
  1094. se->flags
  1095. );
  1096. for (j = 0; j < se->nr_nexts; j++) {
  1097. for (i = 1; i <= level; i++) {
  1098. printf(" ");
  1099. }
  1100. printf("%d: ", j + 1);
  1101. if (!((se->edges + j)->flags & PRINT_SEARCH)) {
  1102. printf(" (%d) ", (se->edges + j)->flags);
  1103. (se->edges + j)->flags |= PRINT_SEARCH;
  1104. dump_stack((se->edges+j)->ptr,level+1);
  1105. /*clear_flags((se->edges+j)->ptr,PRINT_SEARCH);*/
  1106. }
  1107. else {
  1108. printf("LOOP\n");
  1109. }
  1110. }
  1111. return;
  1112. }
  1113. else {
  1114. if (se->flags & LLDUMMY) {
  1115. printf("[%d] <%d,%d,%d> ",
  1116. se->nr,se->ref_count,
  1117. se->hyp_ref_count,
  1118. se->flags
  1119. );
  1120. }
  1121. else {
  1122. printf("%d <%d,%d,%d> ",
  1123. se->nr, se->ref_count,
  1124. se->hyp_ref_count,
  1125. se->flags
  1126. );
  1127. }
  1128. if (!(se->edges->flags & PRINT_SEARCH)) {
  1129. printf(" (%d) ", se->edges->flags);
  1130. se->edges->flags |= PRINT_SEARCH;
  1131. se = se->edges->ptr;
  1132. }
  1133. else {
  1134. printf("LOOP\n");
  1135. return;
  1136. }
  1137. }
  1138. }
  1139. printf("\n");
  1140. }
  1141. #endif
  1142. #if LL_ANSI_C
  1143. static void clear_flags(struct stack_elt *se, char flag)
  1144. #else
  1145. static clear_flags(se, flag)
  1146. struct stack_elt *se;
  1147. char flag;
  1148. #endif
  1149. /* Clears edge flag 'flag' */
  1150. {
  1151. int i;
  1152. for (i = 0; i < se->nr_nexts; i++) {
  1153. if ((se->edges + i)->flags & flag) {
  1154. (se->edges + i)->flags &= ~flag; /* clear flag */
  1155. clear_flags((se->edges + i)->ptr, flag);
  1156. }
  1157. }
  1158. }
  1159. #if LL_ANSI_C
  1160. static void clear_gen_flags(struct stacks *stack)
  1161. #else
  1162. static clear_gen_flags(stack)
  1163. struct stacks *stack;
  1164. #endif
  1165. {
  1166. int i;
  1167. for (i = 0; i < stack->nr_visited; i++) {
  1168. (*(stack->visited_buf + i))->flags &= ~(LLGEN_SEARCH);
  1169. }
  1170. stack->nr_visited = 0;
  1171. }
  1172. #if LL_ANSI_C
  1173. static void match_heads(struct stacks *stack, int symb)
  1174. #else
  1175. static match_heads(stack, symb)
  1176. struct stacks *stack;
  1177. int symb;
  1178. #endif
  1179. /* Match heads_buf against symb, leaving only matching heads,
  1180. * whilst deallocating the non-matching stacks
  1181. */
  1182. {
  1183. int i;
  1184. int old_nr_heads;
  1185. struct stack_elt **old_heads_buf;
  1186. /* Copy the 'old' heads */
  1187. old_nr_heads = stack->nr_heads;
  1188. old_heads_buf = stack->heads_buf;
  1189. /* Set heads in stack to 0 */
  1190. stack->nr_heads = 0;
  1191. stack->heads_buf_size = 0;
  1192. stack->heads_buf = (struct stack_elt **) 0;
  1193. for (i = 0; i < old_nr_heads; i++) {
  1194. if ((*(old_heads_buf + i))->nr != symb) {
  1195. /* Does not match? */
  1196. (*(old_heads_buf + i))->ref_count--;
  1197. (*(old_heads_buf + i))->flags &= ~LLHEAD;
  1198. delete(stack, *(old_heads_buf + i));
  1199. }
  1200. else { /* Matches */
  1201. if (stack->heads_buf_size == 0) {
  1202. stack->heads_buf_size = LLHEADS_BUF_INCR;
  1203. stack->heads_buf = (struct stack_elt **)
  1204. Malloc((unsigned)stack->heads_buf_size *
  1205. sizeof(struct stack_elt *));
  1206. }
  1207. else if (stack->nr_heads == stack->heads_buf_size) {
  1208. stack->heads_buf_size += LLHEADS_BUF_INCR;
  1209. stack->heads_buf = (struct stack_elt **)
  1210. Realloc((char *) stack->heads_buf,
  1211. (unsigned) stack->heads_buf_size *
  1212. sizeof(struct stack_elt *));
  1213. }
  1214. *(stack->heads_buf + stack->nr_heads) =
  1215. *(old_heads_buf + i);
  1216. stack->nr_heads++;
  1217. }
  1218. }
  1219. free((char *) old_heads_buf);
  1220. }
  1221. #if LL_ANSI_C
  1222. static void cleanup(struct stacks *stack)
  1223. #else
  1224. static cleanup(stack)
  1225. struct stacks *stack;
  1226. #endif
  1227. /* Deletes all elements in 'cleanup_buf()' */
  1228. {
  1229. int i;
  1230. for (i = 0; i < stack->nr_cleanups; i++) {
  1231. delete(stack, *(stack->cleanup_buf + i));
  1232. }
  1233. stack->nr_cleanups = 0;
  1234. }
  1235. #if LL_ANSI_C
  1236. static void initialize(struct stacks *stack)
  1237. #else
  1238. static initialize(stack)
  1239. struct stacks *stack;
  1240. #endif
  1241. /* Initializes some variables and arrays */
  1242. {
  1243. int j;
  1244. stack->nr_heads = 0;
  1245. stack->heads_buf_size = 0;
  1246. stack->heads_buf = (struct stack_elt **)0;
  1247. stack->nr_cleanups = 0;
  1248. stack->cleanup_buf_size = 0;
  1249. stack->cleanup_buf = (struct stack_elt **)0;
  1250. stack->nr_visited = 0;
  1251. stack->visited_buf_size = 0;
  1252. stack->visited_buf = (struct stack_elt **)0;
  1253. for (j = 0; j < (LLNNONTERMINALS + 7)/8; j++) {
  1254. stack->r_rec[j] = (char) 0;
  1255. }
  1256. for (j = 0; j < LLNNONTERMINALS; j++) {
  1257. stack->join_array[j] = (struct stack_elt *)0;
  1258. }
  1259. for (j = 0; j < LLSETSIZE; j++) {
  1260. stack->exp_terminals[j] = 0;
  1261. }
  1262. stack->start_seen = 0;
  1263. }
  1264. #if LL_ANSI_C
  1265. static void calculate(struct stacks *stack, int l_ahead)
  1266. #else
  1267. static calculate(stack, l_ahead)
  1268. struct stacks *stack;
  1269. int l_ahead;
  1270. #endif
  1271. /* This function finds all new heads and deletes the old heads */
  1272. {
  1273. int i;
  1274. int old_nr_heads;
  1275. struct stack_elt **old_heads_buf;
  1276. /* Make a copy of the heads */
  1277. old_nr_heads = stack->nr_heads;
  1278. old_heads_buf = stack->heads_buf;
  1279. stack->nr_heads = 0;
  1280. stack->heads_buf = (struct stack_elt **) 0;
  1281. stack->heads_buf_size = 0;
  1282. for (i = 0; i < old_nr_heads; i++) {
  1283. /* Find all new heads */
  1284. generate_heads(stack, *(old_heads_buf + i), l_ahead);
  1285. clear_gen_flags(stack);
  1286. /* Old head can be deleted now */
  1287. (*(old_heads_buf + i))->ref_count--;
  1288. delete(stack, *(old_heads_buf + i));
  1289. }
  1290. cleanup(stack);
  1291. free((char *) old_heads_buf);
  1292. /* Reinitialize some things */
  1293. for (i = 0; i < (LLNNONTERMINALS + 7)/8; i++) {
  1294. stack->r_rec[i] = (char) 0;
  1295. }
  1296. for (i = 0; i < LLNNONTERMINALS; i++) {
  1297. stack->join_array[i] = (struct stack_elt *)0;
  1298. }
  1299. /* Delete all HEAD flags */
  1300. for (i = 0; i < stack->nr_heads; i++) {
  1301. (*(stack->heads_buf + i))->flags &= ~LLHEAD;
  1302. }
  1303. }
  1304. #if LL_ANSI_C
  1305. static void kill_stack(struct stacks *stack)
  1306. #else
  1307. static kill_stack(stack)
  1308. struct stacks *stack;
  1309. #endif
  1310. {
  1311. int i;
  1312. for (i = 0; i < stack->nr_heads; i++) {
  1313. (*(stack->heads_buf + i))->ref_count--;
  1314. delete(stack, *(stack->heads_buf + i));
  1315. }
  1316. }
  1317. #if LL_ANSI_C
  1318. void LLnc_recover(void)
  1319. #else
  1320. LLnc_recover()
  1321. #endif
  1322. /* This function contains the main loop for non correcting syntax error
  1323. * recovery
  1324. */
  1325. {
  1326. int j;
  1327. int base_symb;
  1328. struct stacks stack;
  1329. int max_nr_heads;
  1330. int max_nr_good_heads;
  1331. initialize(&stack);
  1332. max_nr_heads = 0;
  1333. max_nr_good_heads = 0;
  1334. /* Grammar has to be read only once */
  1335. if (!grammar_read) {
  1336. build_grammar();
  1337. grammar_read = 1;
  1338. }
  1339. /* Read first token */
  1340. read_token();
  1341. base_symb = LLsymb;
  1342. /* Check on end of file */
  1343. if ((base_symb <= 0) || (base_symb == EOFILE)) {
  1344. if ((nonterminals + LLstartsymb - LLFIRST_NT)->rule->empty != 1
  1345. ) {
  1346. LLsymb = EOFILE;
  1347. LLmessage(0);
  1348. }
  1349. kill_stack(&stack);
  1350. return;
  1351. }
  1352. /* Read look ahead token */
  1353. read_token();
  1354. /* Now search applicable rules and starts the ball rolling */
  1355. start_stack(&stack, base_symb, LLsymb);
  1356. if (stack.nr_heads > max_nr_heads) {
  1357. max_nr_heads = stack.nr_heads;
  1358. }
  1359. /* Only matching heads are needed */
  1360. match_heads(&stack, LLsymb);
  1361. if (stack.nr_heads > max_nr_good_heads) {
  1362. max_nr_good_heads = stack.nr_heads;
  1363. }
  1364. #ifdef DEBUG
  1365. test(&stack);
  1366. #endif
  1367. /* Loop untill end of inputfile */
  1368. while ((LLsymb > 0) && (LLsymb != EOFILE)) {
  1369. /* When entering the loop LLsymb always contains the
  1370. * symbol that was used as look_ahead to construct the stacks,
  1371. * or, if optimization is OFF, it contains the symbol with
  1372. * which the current heads have been matched
  1373. */
  1374. if (stack.nr_heads == 0) {
  1375. /* No more heads left */
  1376. LLmessage(0);
  1377. /* Restart the whole thing */
  1378. initialize(&stack);
  1379. /* The look-ahead caused the empty stack, don't
  1380. * use it to start a new one !
  1381. */
  1382. read_token();
  1383. base_symb = LLsymb;
  1384. /* Check on end of file */
  1385. if ((base_symb <= 0) || (base_symb == EOFILE)) {
  1386. if ((nonterminals + LLstartsymb - LLFIRST_NT)->rule->empty != 1) {
  1387. LLsymb = EOFILE;
  1388. LLmessage(0);
  1389. }
  1390. kill_stack(&stack);
  1391. return;
  1392. }
  1393. read_token();
  1394. start_stack(&stack, base_symb, LLsymb);
  1395. if (stack.nr_heads > max_nr_heads) {
  1396. max_nr_heads = stack.nr_heads;
  1397. }
  1398. match_heads(&stack, LLsymb);
  1399. if (stack.nr_heads > max_nr_good_heads) {
  1400. max_nr_good_heads = stack.nr_heads;
  1401. }
  1402. continue;
  1403. }
  1404. /* Normal case starts here */
  1405. stack.start_seen = 0;
  1406. for (j = 0; j < LLSETSIZE; j++) {
  1407. stack.exp_terminals[j] = 0;
  1408. }
  1409. /* Read next symbol */
  1410. read_token();
  1411. /* Generate all new heads and delete old ones */
  1412. calculate(&stack, LLsymb);
  1413. /* Leave out not wanted heads */
  1414. if (stack.nr_heads > max_nr_heads) {
  1415. max_nr_heads = stack.nr_heads;
  1416. }
  1417. match_heads(&stack, LLsymb);
  1418. if (stack.nr_heads > max_nr_good_heads) {
  1419. max_nr_good_heads = stack.nr_heads;
  1420. }
  1421. #ifdef DEBUG
  1422. test(&stack);
  1423. #endif
  1424. }
  1425. /* End of file reached, check if we have seen a start symbol */
  1426. if (stack.start_seen == 1) return;
  1427. else {
  1428. LLsymb = EOFILE;
  1429. LLmessage(0);
  1430. }
  1431. kill_stack(&stack);
  1432. #ifdef DEBUG
  1433. printf("Maximum number of heads: %d\n", max_nr_heads);
  1434. printf("Maximum number of good heads: %d\n", max_nr_good_heads);
  1435. printf("Number of node allocates: %d\n", allocates);
  1436. printf("Number of node deallocates: %d\n", deallocates);
  1437. printf("Maximum number of nodes in use: %8d\n", max_in_use);
  1438. printf("Sizeof(struct stack_elt) = %8d\n", sizeof(struct stack_elt));
  1439. printf(" --------x\n");
  1440. printf(" %8d\n", max_in_use * sizeof(
  1441. struct stack_elt));
  1442. printf("Number of edge allocates: %d\n", edge_allocates);
  1443. printf("Number of edge deallocates: %d\n", edge_deallocates);
  1444. printf("Maximum number of edges in use: %8d\n", edge_max_in_use);
  1445. printf("Sizeof(struct edge) = %8d\n", sizeof(struct edge));
  1446. printf(" --------x\n");
  1447. printf(" %8d\n", edge_max_in_use * sizeof(struct edge));
  1448. #endif
  1449. }