home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / oxcc1433.zip / SRC / PARSER.C < prev    next >
C/C++ Source or Header  |  1995-10-18  |  43KB  |  1,824 lines
  1. /* parser.c -- derived from the `LALR' parser written by Paul Mann */
  2.  
  3. #define CLASS Parser
  4.  
  5. #include <oxbow.h>
  6.  
  7. object CLASS;
  8.  
  9. instanceVars {
  10.     PG pg;
  11. };
  12. #define HOWBIG 1
  13. #define DEBUG 1
  14.  
  15. #if HOWBIG
  16. static int maxXX_parse;
  17. static int maxSS_parse;
  18. static int maxSS_lex;
  19. static int maxNS_parse;
  20. static int maxLS_parse;
  21. static int maxRS_parse;
  22. #endif
  23.  
  24.  
  25. /* Built in standard actions */
  26. static void nullaction();
  27. static void classify();
  28. static void require();
  29. static void doline();
  30. static void dyntoken();
  31.  
  32. static void LoadParserPointers();
  33.  
  34. /* some imported functions */
  35. char *strchr();
  36. char *strrchr();
  37. int atol();
  38. int _strcpy(void *dst, const void *src);
  39. void *strcpy(void *dst, const void *src);
  40. void *strcat(void *dst, const void *src);
  41. void *memcpy(void *dst, const void *src, int len);
  42.  
  43.  
  44. /* All chunk types have the same number of bytes */
  45.  
  46. #define ASTCHUNK (pg->astchunk)
  47. #define SYMBOLCHUNK (pg->symbolchunk)
  48. #define TEXTCHUNK (pg->textchunk)
  49. #define ASTSIZE (pg->astsize)
  50.  
  51.  
  52. typedef struct _key
  53. {
  54.     unsigned long key;
  55.     unsigned long hv;
  56. } KEY, *KEYP;
  57.  
  58. typedef struct _psym
  59. {/* Fits in a minimal sized AST node */
  60.     unsigned short dat[4];        /* 8 bytes */
  61.     KEY cat;                    /* 8 bytes */
  62.     struct _psym *next;            /* 4 bytes */
  63. } Psym, *PsymP;
  64.  
  65. typedef struct _pbuf
  66. {/* parser symbol table struct */
  67.     int    size;
  68.     void *lastbin;    /* for DelLast */
  69.     int headbin;    /* for seq access */
  70.     PsymP headptr;    /* ditto */
  71.     PG *wpg;
  72.     PsymP bins[0];
  73. } *PbufP;
  74.  
  75. void *
  76. NewParserSymTable(PG *pg, int size)
  77. {
  78. PbufP buf = callocC(pg->category, 1, size*sizeof(PsymP) + sizeof(struct _pbuf));
  79.     buf->size = size;
  80.     buf->wpg = pg;
  81.     return buf;
  82. }
  83.  
  84. cmethod vobject
  85. New(object self, char *language, int astsize)
  86. {
  87. void *lfile;
  88. char lodname[200];
  89. char filename[40];
  90. char *cp;
  91. PTABLE *pp;
  92. LTABLE *lp;
  93. long *symbase;
  94. char *symptr;
  95. char buf[100];
  96. Item item;
  97. int i;
  98. object instance;
  99. PG *pg;
  100. int oldload = 0;
  101. AstP fnode;
  102.  
  103.     if(IsaClass(self))
  104.         instance  = cSuper(gNew)(self);
  105.     else {
  106.         instance = self;
  107.     }
  108.     pg = (PG *)ivPtr(instance);
  109.     pg->category = NewMallocCategory();
  110.  
  111.     strcpy(pg->language, language);
  112.     strcpy(filename, language);
  113.     strcat(filename, ".lod");
  114.  
  115.     if((cf_find_file("oxlib.cff", lodname)))
  116.     {/* The archive file */
  117.         strcat(lodname, "/language/");
  118.         strcat(lodname, filename);
  119.     } else {
  120.         pg->errors = 1;
  121.         return instance;
  122.     }
  123.     if(cfqget(MEMTEMP, filename, strlen(filename), &item, 8) == FOUND)
  124.     {/* Parser tables for this language have been loaded earlier */
  125.         pg->lod_table = item.a1;
  126.         oldload = 1;
  127.     }
  128.     else
  129.     {/* Load the parser tables for this language */
  130.         if((lfile = cfopen(lodname, F_STAT, NULL)))
  131.         {
  132.         int size;
  133.             size = cfseek(lfile, 0, S_END);
  134.             pg->lod_table = malloc(size);
  135.             cfseek(lfile, 0, S_SET);
  136.             cfread(lfile, pg->lod_table, size);
  137.             cfclose(lfile);
  138.             item.item = 0;
  139.             item.a1 = pg->lod_table;
  140.             cfinsert(MEMTEMP, filename, strlen(filename), &item);
  141.         }
  142.         else {
  143.             pg->errors = 2;
  144.             return instance;
  145.         }
  146.     }
  147.  
  148.     /* using the size of the caller's AST node, compute suitable chunks */
  149.  
  150.     if(astsize < sizeof(AST_NODE))
  151.         astsize = sizeof(AST_NODE);
  152.  
  153.     if(astsize & 3)
  154.         astsize += 4-(astsize&3);
  155.  
  156.     ASTCHUNK = 8184/astsize;
  157.     TEXTCHUNK = ASTCHUNK * astsize;
  158.     SYMBOLCHUNK = TEXTCHUNK / 4;
  159.     ASTSIZE = astsize;
  160.     
  161.     /* Parser table init */
  162.     pg->ptab = callocC(pg->category, 1, sizeof(PTABLE));    
  163.     pp = pg->ptab;
  164.     pp->pg = pg;
  165.     LoadParserPointers(pp, pg->lod_table, 1);
  166.     pp->linksize = SYMBOLCHUNK;
  167.     pp->link = callocC(pg->category, 1, SYMBOLCHUNK*sizeof(void*));
  168.  
  169.  
  170.     /* Lexer table init */
  171.     pg->ltab = callocC(pg->category, 1, sizeof(LTABLE));
  172.     lp = pg->ltab;
  173.     lp->pg = pg;
  174.     LoadParserPointers(lp, (LODTABLE *)(((char *)pg->lod_table) + pg->lod_table->next), 0);
  175.  
  176.     /* Action pointers, applies to both parser and lexer */
  177.     pg->n_actions = lp->n_actions;    /* lexer has the best action count */
  178.     pg->ACTIONS = (PACTIONS)lp->ACTIONS;
  179.     pg->ACTIONSTRINGS = lp->ACTIONSTRINGS;
  180.  
  181.     /* Allocate the initial ast space */
  182.     pg->pat.free = callocC(pg->category, 1, ASTCHUNK*astsize);    
  183.     pg->pat.freecnt = pg->pat.cnt = ASTCHUNK;
  184.     fnode = pg->pat.free;
  185.     for(i = 0; i < ASTCHUNK-1; ++i)
  186.     {
  187.         fnode->down = (AstP)(((char*)fnode)+ASTSIZE);
  188.         fnode = fnode->down;
  189.     }
  190.  
  191.     /* Allocate and initialize the parser symbol table */
  192.     PARSERSYMBOLS = callocC(pg->category, 1, SYMBOLCHUNK*sizeof(PARSER_SYMBOL));
  193.     pg->symhandle = NewParserSymTable(pg, 2003);
  194.  
  195.     /* Allocate and initialize the first text accumulation chunk */
  196.     pg->chunkbase = callocC(pg->category, 1, TEXTCHUNK);
  197.     pg->chunkend = pg->chunkbase+TEXTCHUNK-1;
  198.     pg->symbase = pg->chunkbase+4;
  199.     pg->symend = pg->symbase;
  200.  
  201.     /* Enter all the terminal symbols of the grammar */
  202.     symbase = pp->G_symbol;
  203.     symptr = (char *)symbase;
  204.  
  205.     for(i = 0; i < pp->n_terms; ++i)
  206.     {
  207.         NewParserSymbol(pg, symptr+symbase[i]);
  208.     }
  209.  
  210.     /* Set the values for the automatic node ids */
  211.     {
  212.     int    symnum = -1;
  213.     int symval;
  214.     int subsym = 0;
  215.     char *cp = NULL;
  216.         for(i = 0; i < pp->n_rules; ++i)
  217.         {
  218.         long *vp;    /* assume callers node ids are sizeof(long) */
  219.             if(pp->PL[i] & PL_MAKENODE)
  220.             {
  221.                 if(pp->Head[i] != symnum)
  222.                 {
  223.                     subsym = 0;
  224.                     symnum = pp->Head[i];
  225.                     cp = symptr + symbase[symnum];
  226.                 }
  227.                 /* e.g. _cInitDeclarator_0 */
  228.                 cfsprintf(buf, "_%s%s_%d", pg->language, cp, subsym);
  229.  
  230.                 /* use dynamic linker here */
  231.                 symval = (symnum<<6) | subsym;
  232.                 if((vp = oxlink_find_bare_symb(buf)) != NULL)
  233.                 {/* vp is now the address of the symbol in caller memory */
  234.                     *vp = symval;  /* caller defined a global symbol he wants */
  235.                 }
  236.                 ++subsym;
  237.             }
  238.         }
  239.     }
  240.     /* Set up the function pointers for actions */
  241.     if(!oldload)
  242.     {/* THIS WOULD WORK WITHOUT TESTING FOR 'oldload', just saving time */
  243.     PACTIONS pa = pg->ACTIONS;
  244.     char *cp;
  245.     int mask;
  246.     int j;
  247.  
  248.         for(i = 0; i < pg->n_actions; ++i, ++pa)
  249.         {
  250.         /* 
  251.             pa->func is initially set to an offset into ACTIONSTRINGS 
  252.                     convert it into a function pointer
  253.         */
  254.             cp = pg->ACTIONSTRINGS + (int)pa->func; /* funcname is first entry */
  255.             if(!strcmp(cp, "classify"))
  256.                 pa->func = classify;
  257.             else if(!strcmp(cp, "require"))
  258.                 pa->func = require;
  259.             else if(!strcmp(cp, "doline"))
  260.                 pa->func = doline;
  261.             else if(!strcmp(cp, "dyntoken"))
  262.                 pa->func = dyntoken;
  263.             else
  264.             {/* Concoct the real user action name and find the function */
  265.                 /* e.g. _dosomething_ada_ */
  266.                 cfsprintf(buf, "_%s_%s_", cp, pg->language);
  267.                 if((pa->func = oxlink_find_bare_func(buf)) == NULL)
  268.                 {/* Not already in core */
  269.                     if((pa->func = oxlink_load_bare_symb(buf, 1)) == NULL)
  270.                     {/* And can't load it from the archive, punt to nothing */
  271.                         pa->func = nullaction;
  272.                     }
  273.                 }
  274.             }
  275.             /* 
  276.                 Set up the args:
  277.                 arg[0] contains a bitmask in the high order 16 bits
  278.                     and argcnt in the low 16 bits 
  279.             */
  280.             mask = (pa->args[0] & 0xffff0000) >> 16;
  281.             pa->args[0] &= 0x0000ffff;
  282.             for(j = 1; j <= pa->args[0]; ++j)
  283.             {
  284.                 if(mask & 1)
  285.                 {/* This arg is really a pointer to a string */
  286.                     pa->args[j] += (int)pg->ACTIONSTRINGS;
  287.                 }
  288.                 mask >>= 1;
  289.             }
  290.         }
  291.     }
  292.     /* Set a few constants */
  293.     pg->parsecnt = 2;
  294.     pg->ROOT = 0;
  295.     pg->root = 0;
  296.     pg->line_numb = 1;
  297.     pg->line_char = 0;
  298. #if HOWBIG
  299.     maxXX_parse = 
  300.         maxSS_parse =
  301.             maxSS_lex =
  302.                 maxNS_parse =
  303.                     maxLS_parse = 
  304.                         maxRS_parse = 0;
  305. #endif
  306.     return instance;
  307. }
  308. imethod void
  309. Dispose(object self)
  310. {
  311. PG *pg = (PG *)ivPtr(self);
  312.  
  313.     freecat(pg->category);
  314.     super(gDispose)(self);
  315. }
  316.  
  317.  
  318. static unsigned short bitlist[16] = {
  319.             0x0001, 0x0002, 0x0004, 0x0008, 0x0010, 0x0020, 0x0040, 0x0080,
  320.             0x0100, 0x0200, 0x0400, 0x0800, 0x1000, 0x2000, 0x4000, 0x8000
  321.     };
  322. #define BITSET(a,b,c) ( a[b+(c>>4)] & bitlist[c&0xf] )
  323.  
  324. static int
  325. do_parse (PTABLE *ptab)
  326. {
  327. short i, x;
  328. short *r;
  329. short rule;
  330. unsigned base;
  331. short state;
  332. int token;
  333. short stacktop, *SS;
  334. PG *pg;
  335. int rulesize;
  336. int debug;
  337. int xx;
  338. AstP *link;
  339. int lexindx;
  340.  
  341. /* NESTED SUBROUTINE Make AST node and/or call semantic action. */
  342.  
  343. static void attach ()
  344. {
  345. int k, i, j;
  346. AstP np, lp, p;
  347. int rulesize;
  348. AstP newnode;
  349. int savxx;
  350. short *pxx;
  351.  
  352.     rulesize = ptab->PL[rule] & 0x000f;
  353.     if(rulesize == 15)
  354.         rulesize = -1;
  355.  
  356.     ptab->NS -= rulesize;         /* Reduce the stack.        */
  357.     ptab->LS -= rulesize;
  358.  
  359.     for (k=0,np=0,i=rulesize; i >= 0; i--) /* Look at each tail spot.  */
  360.     {
  361.         if (ptab->NS[i])    /* If node pointer there.   */
  362.         {
  363.         int xxx;
  364.             k++;                            /* Active node marker.  */
  365.             p = ptab->NS[i];                /* Last node in chain */
  366.             xxx = ptab->LS[i];
  367.  
  368.             if (np)                            /* If one waiting.          */
  369.             {
  370.                 lp = link[xxx];
  371.                 lp->down = np;                /* Connect last to next.    */
  372.                 link[xxx] = link[savxx];    /* Move link */
  373. #if DEBUG
  374. if(debug)cfprintf("Parse: Set DOWN at %x to %x\n", lp, np);
  375. #endif
  376.             }
  377.             np = p;                            /* Get this ones address.    */
  378.             savxx = xxx;
  379.         }
  380.     }
  381.     if (ptab->PL [rule] & PL_MAKENODE)
  382.     {
  383.       newnode = NewAstNode(pg,(ptab->Head[rule]<<6)|(rule-ptab->rBase[rule]),0);
  384.         if(!pg->ROOT)
  385.             pg->ROOT = newnode;
  386.  
  387.         if (k > 0)
  388.         {/* Make branch */
  389.             newnode->right = np;            /* Pointer to child.        */
  390.             newnode->fileno = (unsigned char)pg->line_file; /* current file */
  391.             newnode->colno = (unsigned char)pg->line_char; /* column of text */
  392.             newnode->lineno = (unsigned short)pg->line_numb;/* Line number. */
  393.             if (np == pg->ROOT) {
  394.                 pg->ROOT = newnode; /* Root points to parent.   */
  395. #if DEBUG
  396. if(debug)cfprintf("Parse: Reset ROOT to %x\n", newnode);
  397. #endif
  398.             }
  399. #if DEBUG
  400. if(debug)cfprintf("Parse: New Branch at %x %s_%d  right=%x down=%x\n",
  401.     newnode,GetH_symbol(pg, ptab->Head[rule]),rule-ptab->rBase[rule],np, newnode->down);
  402. #endif
  403.         }
  404.         else
  405.         {/* Make leaf */
  406.         int lookback = (pg->LSP-lexindx)&3;
  407.             newnode->Tindx = pg->L_stack[lookback+1];    /* Terminal type */
  408.             newnode->symb = pg->L_stack[lookback];        /* Symnum */
  409.             newnode->fileno = (unsigned char)pg->line_file; /* current file */
  410.             newnode->colno = (unsigned char)pg->line_char; /* column of text */
  411.             newnode->lineno = (unsigned short)pg->line_numb;/* Line number. */
  412. #if DEBUG
  413. if(debug)cfprintf("Parse: New Leaf at %x %s_%d right=%x down=%x\n", 
  414.     newnode,GetH_symbol(pg, ptab->Head[rule]),rule-ptab->rBase[rule], newnode->right, newnode->down);
  415. #endif
  416.         }
  417.  
  418.         /* Prevent the unconstrained growth of the link array */
  419.         for(pxx = ptab->LStop, xx = 0; pxx <= ptab->LS; ++pxx)
  420.         {
  421.             if(*pxx > xx)
  422.                 xx = *pxx;
  423.         }
  424.  
  425.         if(++xx == ptab->linksize)
  426.         {/* Extend the link array */
  427.             ptab->linksize += SYMBOLCHUNK;
  428.             link = reallocC(pg->category, link, ptab->linksize*sizeof(int));
  429.             ptab->link = link;
  430.         }
  431.         np = newnode; 
  432.         link[xx] = np;
  433.     }
  434.     *(ptab->NS) = np;
  435.     *(ptab->LS) = xx;
  436.  
  437. #if HOWBIG
  438.     if(xx > maxXX_parse)
  439.         maxXX_parse = xx;
  440. #endif
  441.  
  442. /* Call actions for a rule */
  443.     if (ptab->PL [rule] & PL_ACTION)        /* Call action?             */
  444.     {
  445.     PACTIONS ap = &pg->ACTIONS[(ptab->PL[rule]>>7)&511];
  446. #if DEBUG
  447. if(debug)cfprintf("Parse: Call Action for rule:%d\n", rule);
  448. #endif
  449.         ptab->node = np;
  450.         pg->actionerr = NULL;
  451.         (*ap->func) (pg, ap->args); /* Call action.             */
  452.  
  453.         if (ptab->PL [rule] & PL_DELTREE)     /* Delete the subtree?      */
  454.         {
  455. #if DEBUG
  456. if(debug)cfprintf("Parse: Prune Tree at rule:%d\n",rule);
  457. #endif
  458.             *(ptab->NS) = 0;  /* Reset np to 0.           */
  459.             PruneAstTree(pg, np, 0, 0); /* Get rid of all nodes including root */
  460.             pg->ROOT = np;        /* will be next node allocated */
  461.         }
  462.     }
  463. }/* END attach() */
  464. /* NESTED SUBROUTINE */
  465. static int procrules()
  466. {
  467.     /* Attach all currently known rules to the ast */
  468.     ptab->rule = rule;
  469.     for (r = ptab->RStop; r < ptab->Rs; )
  470.     {
  471.         rule = *r++;
  472.         if(rule < 0)
  473.         {/* Shift occured */
  474.             *(++(ptab->NS)) = (AstP)0; /* Set node pointer to zero. */
  475.             *(++(ptab->LS)) = 0;
  476.             lexindx -= 2;    /* lex symbol is one token closer */
  477.         }
  478.         else
  479.         {
  480.             attach ();                    /* Attach node to AST.      */
  481.             if(pg->actionerr) {
  482. #if DEBUG
  483. if(debug)cfprintf("PARSE action error exit\n");
  484. #endif
  485.                 return 1;
  486.             }
  487.         }
  488.     }
  489.     ptab->Rs = ptab->RStop;            /* Reset reduction stk ptr. */
  490.  
  491. #if HOWBIG
  492.     if((ptab->NS - ptab->NStop) > maxNS_parse)
  493.             maxNS_parse = ptab->NS - ptab->NStop;
  494.     if((ptab->LS - ptab->LStop) > maxLS_parse)
  495.         maxLS_parse = ptab->LS - ptab->LStop;
  496. #endif
  497.     return 0;
  498. } /* END: procrules */
  499.  
  500. /* do_parse */
  501.     pg = ptab->pg;
  502.     SS = ptab->SS;
  503.     state = ptab->state;
  504.     token = ptab->token;
  505.     link = ptab->link;
  506.     xx = ptab->xx;
  507.     debug = pg->debug & 1;
  508.     lexindx = 4;
  509. #if DEBUG
  510. if(debug)cfprintf("ParseSTART: state=%d token=%d\n", state, token);
  511. #endif
  512. Scan:
  513.     if(token < 0)
  514.     {
  515.         if(procrules())
  516.             return -1;
  517.         /* get new token */
  518.         ptab->state = state;
  519.         ptab->SS = SS;
  520.         ptab->xx = xx;
  521.         return(0);
  522.     }
  523.  
  524.  /* Test for Shift, and Shift-Reduce */
  525.  
  526.     base = state * ptab->bitwords;
  527.     if(BITSET(ptab->M_bits, base, token))
  528.     {
  529.         x = ptab->MT_tran[ ptab->MT_beg[state] + ptab->token];
  530.         *++(SS) = state;                 /* Put state on parse stack.*/
  531. #if HOWBIG
  532.         if((SS - ptab->SStop) > maxSS_parse)
  533.             maxSS_parse = SS - ptab->SStop;
  534. #endif
  535.         if (SS >= ptab->SSmax)     /* If parse stack too large.*/
  536.         {
  537.             cfprintf("Parse: stack overflow \n");
  538.             OXPORT_crash("");
  539.         }
  540.         *ptab->Rs++ = -1;                /* Mark reduction stack as shifted */
  541.         token = -1;                        /* Indicate token consumed   */
  542.         if(x > 0)
  543.         {
  544.             state = x;
  545. #if DEBUG
  546. if(debug)cfprintf("Parse: shift to state %d\n", state);
  547. #endif
  548.             goto Scan;        /* Shift only */
  549.         }
  550.         /* --- REDUCE -----------------------*/
  551.  
  552. Neg:    rule = -x;                              /* Make positive.           */
  553. Reduce:
  554.         rulesize = ptab->PL [rule] & 0x000f;
  555.         if(rulesize == 15)
  556.             rulesize = -1;
  557.         SS -= rulesize;
  558.         if(rulesize == -1)
  559.         {
  560.             *SS = state;                       /* Stack current state.     */
  561.         }
  562.         stacktop = *SS;
  563.         *ptab->Rs++ = rule;
  564. #if HOWBIG
  565.         if((ptab->Rs - ptab->RStop) > maxRS_parse)
  566.             maxRS_parse = ptab->Rs - ptab->RStop;
  567. #endif
  568. #if DEBUG
  569. if(debug)cfprintf("Parse: stack rule %d, new state is %d head=%d\n",
  570.                                 rule, stacktop, ptab->Head[rule]);
  571. #endif
  572.         /* Check for goal */
  573.         if(rule == 0)
  574.         {
  575.             if(procrules())
  576.                 return -1;
  577.             pg->root = pg->ROOT;
  578. #if DEBUG
  579. if(debug)cfprintf("PARSE DONE rootnode=%x\n", pg->root);
  580. #endif
  581.             return 1;
  582.         }
  583.  
  584.         /* Check non terminal transitions for current state */
  585.  
  586.         base = stacktop * ptab->bitwords;
  587.         if(BITSET(ptab->M_bits, base, ptab->Head[rule]))
  588.         {
  589.             x = ptab->MN_tran[ptab->MN_beg[stacktop]+(ptab->Head[rule]-ptab->n_terms)];
  590.             if(x > 0)
  591.             {
  592.                 state = x;
  593. #if DEBUG
  594. if(debug)cfprintf("Parse: NT trans to state %d\n", state);
  595. #endif
  596.                 goto Scan;
  597.             }
  598. #if DEBUG
  599. if(debug)cfprintf("Parse: NT reduce to rule %d, state=%d\n",-x, stacktop);
  600. #endif
  601.                 goto Neg;
  602.         }
  603. #if DEBUG
  604. if(debug)cfprintf("Parse: NO nt tran for state %d\n",stacktop);
  605. #endif
  606.         goto Scan;
  607.  
  608.     }/* END of shift/reduce test */
  609.  
  610.     /* Check for pure reductions */
  611. #if DEBUG
  612. if(debug)cfprintf("Parse: check reductions for state %d\n", state);
  613. #endif
  614.     rule = ptab->D_red [state];
  615.     if(rule >= 0)    {
  616. #if DEBUG
  617. if(debug)cfprintf("Parse: use default reduction to rule %d\n", rule);
  618. #endif
  619.         goto Reduce;   /* Default reduction       */
  620.     }
  621.     if (rule == -32767)
  622.     {
  623.         ptab->state = state;
  624.         ptab->token = token;
  625.         ptab->SS = SS;
  626.         ptab->xx = xx;
  627. #if DEBUG
  628. if(debug)cfprintf("PARSE error exit\n");
  629. #endif
  630.         return(-1);
  631.     }
  632.  
  633.       /* Check multiple reductions */
  634. #if DEBUG
  635. if(debug)cfprintf("Parse: check multiple reductions in state %d\n", state);
  636. #endif
  637.     for (i = ptab->R_start [state]; i < ptab->R_start [state+1]; i++)
  638.     {
  639.         if (ptab->R_symbol [i] == token)            /* Found?     */
  640.         {
  641.             rule = ptab->R_prod [i];
  642. #if DEBUG
  643. if(debug)cfprintf("Parse: multiple reduction to rule %d token=%d\n", rule, token);
  644. #endif
  645.             goto Reduce;
  646.         }  
  647.     }
  648.     rule = -rule;                                /* Multiple default.      */
  649. #if DEBUG
  650. if(debug)cfprintf("Parse: use multiple default rule %d\n", rule);
  651. #endif
  652.     goto Reduce;
  653.  
  654. }/* END OF do_parse() */
  655.  
  656. /* THIS LEXER USES PARSER STYLE TABLES [Improve me NDC] */
  657. static void
  658. new_chunk(PG *pg, char tok)
  659. {
  660. long *tempbase;
  661. int chunksize;
  662.  
  663.     if(pg->symbase == pg->chunkbase+4)
  664.     {/* The whole current chunk is worthless (monster symbol spans a chunk) */
  665.         tempbase = *(long**)pg->chunkbase; /* pointer to prev chunk */
  666.         freeC(pg->category, pg->chunkbase);
  667.         pg->chunkbase = (char *)tempbase;
  668.     }
  669.     /* Compute size of new chunk */
  670.     if(pg->symspot >= TEXTCHUNK-5)
  671.          chunksize = pg->symspot+TEXTCHUNK+5;
  672.     else chunksize = TEXTCHUNK;
  673.  
  674.      tempbase = mallocC(pg->category, chunksize);
  675.     *tempbase = (long)pg->chunkbase;    /* pointer to prev chunk */
  676.     pg->chunkbase = (char*)tempbase;
  677.     pg->chunkend = pg->chunkbase+chunksize-1;
  678.     memcpy(pg->chunkbase+4, pg->symbase, pg->symspot);
  679.     pg->symbase = pg->chunkbase+4;
  680.     pg->symend = pg->symbase+pg->symspot;
  681.     *pg->symend++ = tok;
  682.     *pg->symend = 0;
  683.     ((char*)&pg->symhash)[pg->symspot++ & 3] ^= tok; /* running hash */
  684. }
  685. static inline void
  686. add_token(PG *pg, char tok)
  687. {
  688.     if(pg->symend < pg->chunkend) {
  689.         *pg->symend++ = tok;
  690.         *pg->symend = 0;
  691.         ((char*)&pg->symhash)[pg->symspot++ & 3] ^= tok; /* running hash */
  692.     }
  693.     else new_chunk(pg, tok);
  694. }
  695. static int
  696. do_lex (LTABLE *ltab)
  697. {
  698. short i, x;
  699. short rule;
  700. unsigned base;
  701. short state;
  702. int token;
  703. short stacktop;
  704. short *SS;
  705. PG *pg;
  706. int rulesize;
  707. int debug;
  708.  
  709.     pg = ltab->pg;
  710.     SS = ltab->SS;
  711.     state = ltab->state;
  712.     token = ltab->token;
  713.     debug = pg->debug & 2;
  714. #if DEBUG
  715. if(debug)cfprintf("LexSTART: char %c (0x%x)\n", token, token);
  716. #endif
  717. Scan:
  718.     if(token < 0)
  719.     {/* get new token */
  720.         ltab->state = state;
  721.         ltab->token = token;
  722.         ltab->SS = SS;
  723. #if DEBUG
  724. if(debug)cfprintf("Lex: return for next char\n");
  725. #endif
  726.         return(0);
  727.     }
  728.  
  729.     /* Test for Shift, and Shift-Reduce */
  730.  
  731.     base = state * ltab->bitwords;
  732.     if(BITSET(ltab->M_bits, base, token))
  733.     {
  734.         x = ltab->MT_tran[ ltab->MT_beg[state] + ltab->token];
  735.         *++(SS) = state;                 /* Put state on parse stack.*/
  736. #if 0
  737. #if HOWBIG
  738.         if((SS - ltab->SStop) > maxSS_lex)
  739.             maxSS_lex = SS - ltab->SStop;
  740. #endif
  741.         if (SS >= ltab->SSmax)     /* If parse stack too large.*/
  742.         {
  743.             cfprintf("Lex: stack overflow \n");
  744.             OXPORT_crash("");
  745.         }
  746. #endif
  747.         /* Put char in textchunk */
  748.  
  749.         add_token(pg, token);
  750. #if DEBUG
  751. if(debug)cfprintf("Lex consume char\n");
  752. #endif
  753.         token = -1;                          /* Indicate token consumed   */
  754.         if(x > 0)
  755.         {
  756.             state = x;
  757. #if DEBUG
  758. if(debug)cfprintf("Lex: shift to state %d\n", state);
  759. #endif
  760.             goto Scan;        /* Shift only */
  761.         }
  762.         /* --- REDUCE -----------------------*/
  763.  
  764. Neg:    rule = -x;                              /* Make positive.           */
  765. Reduce:
  766.         rulesize = ltab->PL [rule] & 0x000f;
  767.         if(rulesize == 15)
  768.             rulesize = -1;
  769.         SS -= rulesize;
  770.         if(rulesize == -1)
  771.         {
  772.             *SS = state;                       /* Stack current state.     */
  773.         }
  774.         stacktop = *SS;
  775. #if DEBUG
  776. if(debug)cfprintf("Lex: reduce to rule %d, new state is %d head=%d\n",
  777.                                 rule, stacktop, ltab->Head[rule]);
  778. #endif
  779.         if(rule <= ltab->TM)
  780.         {
  781.             ltab->lextoken = ltab->LGT[rule];
  782.             state = 0;
  783.             SS = ltab->SStop;
  784.             if(ltab->lextoken > 0)
  785.             {
  786. #if DEBUG
  787. if(debug)cfprintf("Lex: add symbol %s\n", pg->symbase);
  788. #endif
  789.                 pg->L_stack[pg->LSP] = NewParserSymbol(pg, pg->symbase);
  790.  
  791.                 ltab->state = state;
  792.                 ltab->SS = SS;
  793.                 ltab->token = token;
  794.                 ltab->rule = rule;
  795.                 if(ltab->PL [rule] & PL_ACTION)
  796.                 {
  797.                 PACTIONS ap = &pg->ACTIONS[(ltab->PL[rule]>>7)&511];  
  798.                     (*ap->func) (pg, ap->args);
  799.                 }
  800.  
  801.                 if(ltab->lextoken > 0) {
  802. #if DEBUG
  803. if(debug)cfprintf("Lex: exit with token=%d\n", ltab->lextoken);
  804. #endif
  805.                     pg->LSP = (pg->LSP+1) & 3;
  806.                     pg->L_stack[pg->LSP] = ltab->lextoken;
  807.                     pg->LSP = (pg->LSP+1) & 3;
  808.                     
  809.                     return    ltab->lextoken;
  810.                 }
  811.                 else 
  812.                 {/* Token was cancelled by action */
  813.                     goto Scan;
  814.                 }
  815.             }
  816.             else
  817.             {/* IGNORE rule */
  818. #if DEBUG
  819. if(debug)cfprintf("Lex: ignore rule %d\n", rule);
  820. #endif
  821.                 pg->symend = pg->symbase;
  822.                 pg->symhash = 0;
  823.                 pg->symspot = 0;
  824.                 goto Scan;
  825.             }
  826.         }
  827.         /* Check non terminal transitions for current state */
  828.  
  829.         base = stacktop * ltab->bitwords;
  830.         if(BITSET(ltab->M_bits, base, ltab->Head[rule]))
  831.         {
  832.             x = ltab->MN_tran[ltab->MN_beg[stacktop]+(ltab->Head[rule]-ltab->n_terms)];
  833.             if(x > 0)
  834.             {
  835.                 state = x;
  836. #if DEBUG
  837. if(debug)cfprintf("Lex: NT trans to state %d\n", state);
  838. #endif
  839.                 goto Scan;
  840.             }
  841. #if DEBUG
  842. if(debug)cfprintf("Lex: NT reduce to rule %d, state=%d\n",-x, stacktop);
  843. #endif
  844.                 goto Neg;
  845.         }
  846. #if DEBUG
  847. if(debug)cfprintf("Lex: NO nt tran for state %d\n",stacktop);
  848. #endif
  849.         goto Scan;
  850.  
  851.     }/* END of shift/reduce test */
  852.  
  853.     /* Check for pure reductions */
  854. #if DEBUG
  855. if(debug)cfprintf("Lex: check reductions for state %d\n", state);
  856. #endif
  857.     rule = ltab->D_red [state];
  858.     if(rule >= 0)    goto Reduce;   /* Default reduction       */
  859.     if (rule == -32767)
  860.     {
  861.         pg->symspot = 0;
  862.         pg->symhash = 0;
  863.         pg->symend = pg->symbase;
  864.         ltab->state = 0;
  865.         ltab->SS = ltab->SStop;
  866. #if DEBUG
  867. if(debug)cfprintf("Lex: return ERROR\n");
  868. #endif
  869.         return(-1);
  870.     }
  871. #if DEBUG
  872. if(debug)cfprintf("Lex: Check multiple reductions in state %d\n", state);
  873. #endif
  874.       /* Check multiple reductions */
  875.     for (i = ltab->R_start [state]; i < ltab->R_start [state+1]; i++)
  876.     {
  877.         if (ltab->R_symbol [i] == token)            /* Found?              */
  878.         {
  879.             rule = ltab->R_prod [i];
  880. #if DEBUG
  881. if(debug)cfprintf("Lex: multiple reduction to rule %d token=%d\n", rule, token);
  882. #endif
  883.             goto Reduce;
  884.         }  
  885.     }
  886.     rule = -rule;                                /* Multiple default.      */
  887. #if DEBUG
  888. if(debug)cfprintf("Lex: use multiple default rule %d\n", rule);
  889. #endif
  890.     goto Reduce;
  891.  
  892. }/* END OF do_lex() */
  893.  
  894. static short
  895. read_object(void *obj, PG *pg)
  896. {
  897.     if(pg->obj_inbufcnt <= 0) {
  898.         pg->obj_inbufsize = 
  899.             pg->obj_inbufcnt = (*pg->readfunc)(obj, pg->obj_inbuf, 128);
  900.     }
  901.     if(pg->obj_inbufcnt > 0 )
  902.         return pg->obj_inbuf[pg->obj_inbufsize - pg->obj_inbufcnt--];
  903.     return -1;
  904. }
  905.  
  906. imethod int
  907. Parse(object self, void *is, char *filename)
  908. {
  909. PG *pg = (PG *)ivPtr(self);
  910. LTABLE *lp = pg->ltab; 
  911. PTABLE *pp = pg->ptab;
  912. int    debug = pg->debug & 4;
  913. int isobject;
  914.  
  915.     pg->in_file = is;
  916.     if(IsObj((object)is))
  917.     {
  918.         isobject = 1;
  919.         pg->readfunc = (void*)imiPointer((object)is, gRead);
  920.     }
  921.     else
  922.         isobject = 0;
  923.  
  924.     for(;;)
  925.     {
  926.     short lextoken = 0;
  927.     int result;
  928.         /* Run the lexer */
  929.         while(lextoken == 0)
  930.         {
  931.             if(lp->token < 0)
  932.             {
  933. newchr:
  934.                 if(isobject)
  935.                     lp->token = read_object(is, pg);
  936.                 else
  937.                     lp->token = cfgetc(((cfFILE*)is));
  938.  
  939.                 if(lp->token == 0)
  940.                     goto newchr;
  941.                 if(lp->token < 0)
  942.                 {/* EOF */
  943.                     lp->token = 0;
  944.                 }
  945.                 else lp->token &= lp->maxtoken;
  946.                 if(lp->token == '\n')
  947.                 {
  948.                     ++pg->line_numb;
  949.                     pg->line_char = 0;
  950. if(debug)
  951. cfeprintf("\n");
  952.                 }
  953.                 else if(lp->token == '\r')
  954.                 {
  955.                     goto newchr;
  956.                 }
  957.                 else
  958.                 {
  959.                     ++pg->line_char;
  960. if(debug)
  961. cfeprintf("%c", lp->token);
  962.                 }
  963.             }
  964.             lextoken = do_lex(lp);
  965.             if(lextoken < 0)
  966.             {
  967.                 return(lextoken);
  968.             }
  969.         }
  970.         /* Run the parser */
  971.         pp->token = lextoken;
  972.         result = do_parse(pp);
  973.         if(result)
  974.         {
  975.             if(result < 0)
  976.             {
  977.                 return(1);
  978.             }
  979.             else
  980.             {
  981.                 if(pg->root == 0)
  982.                     return 2;
  983.                 return(0);
  984.             }
  985.         }
  986.     }
  987. }
  988.  
  989. InitMethod()
  990. {
  991.     if (CLASS)
  992.         return;
  993.     CLASS = gNew(Class, cName, ivSize, 0, END);
  994.     
  995.     cMethod(New);
  996.     iMethod(New);
  997.  
  998.     iMethod(Parse);
  999.     iMethod(Dispose);
  1000.     iMethodFor(gDeepDispose, Dispose);
  1001.     iMethodFor(gGCDispose, Dispose);
  1002.  
  1003.     gDontCollect(CLASS);
  1004. }
  1005. /* COMMON STUFF */
  1006.  
  1007. static void
  1008. LoadParserPointers(void *yp, LODTABLE *lp, int notlex)
  1009. {
  1010. char *xp = (char *) lp;
  1011. PTABLE *pp = yp;
  1012. #define SPOINTER(a) ((short *)(xp + lp->a))
  1013. #define CPOINTER(a) ((char *)(xp + lp->a))
  1014. #define LPOINTER(a) ((long *)(xp + lp->a))
  1015. #define VALUE(a) ((short)(lp->a))
  1016.  
  1017.     pp->D_red = SPOINTER(t_D_red);
  1018.     pp->R_start = SPOINTER(t_R_start);
  1019.     pp->R_symbol = SPOINTER(t_R_symbol);
  1020.     pp->R_prod = SPOINTER(t_R_prod);
  1021.     pp->Head = SPOINTER(t_Head);
  1022.     pp->rBase = SPOINTER(t_rBase);
  1023.     pp->MT_beg = SPOINTER(t_MT_beg);
  1024.     pp->MT_tran = SPOINTER(t_MT_tran);
  1025.     pp->MN_beg = SPOINTER(t_MN_beg);
  1026.     pp->MN_tran = SPOINTER(t_MN_tran);
  1027.     pp->M_bits = SPOINTER(t_M_bits);
  1028.     pp->LGT = SPOINTER(t_LGT);
  1029.  
  1030.     pp->G_symbol = LPOINTER(t_G_symbol);
  1031.     pp->PL = SPOINTER(t_PL);
  1032.     pp->ACTIONS = LPOINTER(t_ACTIONS);
  1033.     pp->ACTIONSTRINGS = CPOINTER(t_ACTIONSTRINGS);
  1034.     pp->bitwords = VALUE(bitwords);
  1035.     pp->n_terms = VALUE(n_terms);
  1036.     pp->n_vars = VALUE(n_vars);
  1037.     pp->n_symbs = VALUE(n_symbs);
  1038.     pp->n_states = VALUE(n_states);
  1039.     pp->n_rules = VALUE(n_rules);
  1040.     pp->n_actions = VALUE(n_actions);
  1041.     pp->TM = VALUE(TM);
  1042.     pp->maxtoken = VALUE(maxtoken);
  1043.     pp->token = '\n';
  1044.  
  1045.     pp->SS = pp->SStop;
  1046.     pp->SSmax = pp->SStop + PARSER_STKSIZE - 2;
  1047.     if(notlex)
  1048.     {
  1049.         pp->NS = pp->NStop;
  1050.         pp->LS = pp->LStop;
  1051.         pp->Rs = pp->RStop;
  1052.     }
  1053. }
  1054.  
  1055. /* ========== Access to the parser file stack (nested includes) ==== */
  1056. void
  1057. ParserPush(PG *pg, int data)
  1058. {
  1059.     if(pg->fstack_depth < 64)
  1060.     {
  1061.         pg->fstack[pg->fstack_depth++] = data;
  1062.     }
  1063. }
  1064. int
  1065. ParserPop(PG *pg)
  1066. {
  1067.     if(pg->fstack_depth > 0)
  1068.     {
  1069.         return pg->fstack[--pg->fstack_depth];
  1070.     }
  1071.     return 0;
  1072. }
  1073. int
  1074. ParserStackdepth(PG *pg)
  1075. {
  1076.     return pg->fstack_depth;
  1077. }
  1078. /* ================ END access to the parser file stack ================= */
  1079.  
  1080. static void
  1081. hash(void *key, KEY *cat)
  1082. {
  1083.     cat->key = *((unsigned long *)key);
  1084.     cat->hv = (cat->key * 1103515245UL) + 12345;
  1085. }
  1086. static int
  1087. lookup(PG *pg, char *name, void *result)
  1088. {
  1089. char *cp = name;
  1090. unsigned long myhash = 0;
  1091. unsigned int symspot = 0;
  1092. PsymP sp;
  1093. KEY cat;
  1094. PbufP tbl = pg->symhandle;
  1095.  
  1096.     while(*cp) {
  1097.         ((char*)&myhash)[symspot++ & 3] ^= *cp++;
  1098.     }
  1099.     hash(&myhash, &cat);
  1100.     if((sp = tbl->bins[cat.hv % tbl->size]))
  1101.     {
  1102.       do
  1103.       {
  1104.             if(        sp->cat.hv == cat.hv
  1105.                 &&    sp->cat.key == cat.key)
  1106.             {
  1107.                 /* Do final string check */
  1108.                 if(       sp->dat[1] != symspot
  1109.                     || strcmp(PARSERSYMBOLS[sp->dat[0]].name, name))
  1110.                 {
  1111.                     continue;
  1112.                 }
  1113.                 *((PsymP *)result) = sp;
  1114.                 return 1;
  1115.             }
  1116.       } while((sp = sp->next));
  1117.     }
  1118.     return 0;
  1119. }
  1120. int
  1121. NewParserSymbol(PG *pg, const char *name)
  1122. {
  1123. KEY cat;
  1124. PsymP *binp;
  1125. PsymP sp;
  1126. PbufP tbl = pg->symhandle;
  1127. int symnum;
  1128.  
  1129.     if(name != pg->symbase)
  1130.     {/* From outside, add this symbol to the textchunk */
  1131.     const char *cp = name;
  1132.         while(*cp)
  1133.             add_token(pg, *cp++);
  1134.     }
  1135.     hash(&pg->symhash, &cat);
  1136.  
  1137.     binp = &(tbl->bins[cat.hv % tbl->size]);
  1138.  
  1139.     if((sp = *binp))
  1140.     {
  1141.         do
  1142.         {
  1143.             if(        sp->cat.hv == cat.hv
  1144.                 &&    sp->cat.key == cat.key)
  1145.             {
  1146.                 /* Do final string check */
  1147.                 if(       sp->dat[1] != pg->symspot
  1148.                     || strcmp(PARSERSYMBOLS[sp->dat[0]].name, name))
  1149.                 {
  1150.                     continue;    /* NO MATCH */
  1151.                 }
  1152.  
  1153.                 /* FOUND */
  1154.                 /* Flush the string which was built up in the text chunk */
  1155.                 pg->symend = pg->symbase;
  1156.                 pg->symspot = 0;
  1157.                 pg->symhash = 0;
  1158.  
  1159.                 /* Return data stored in the symbol table */
  1160.                 pg->lastsymnum = sp->dat[0];
  1161.                 pg->lastclass = sp->dat[2];
  1162.                 return sp->dat[0];
  1163.             }
  1164.         } while((sp = sp->next));
  1165.     }
  1166.  
  1167.     /* NOT FOUND, ENTER A NEW SYMBOL */
  1168.     symnum = pg->pst.cnt;
  1169.     if(symnum && ((symnum % SYMBOLCHUNK) == 0))
  1170.     {/* Allocate more contiguous symbol string pointer space */
  1171.         PARSERSYMBOLS = reallocC(pg->category, PARSERSYMBOLS, 
  1172.           (symnum*sizeof(PARSER_SYMBOL))+(SYMBOLCHUNK*sizeof(PARSER_SYMBOL)));
  1173.     }
  1174.     /* link new symbol to front of bin */
  1175.     sp = (PsymP)NewAstNode(pg, 0, 0);
  1176.     if((sp->next = *binp) != 0)
  1177.         ++pg->hashdups;
  1178.     *binp = sp;
  1179.     tbl->lastbin = binp;    /* used for DelLastParserSymbol */
  1180.  
  1181.     /* Put data in symbol chunk */
  1182.     sp->dat[0] = symnum;        /* symbol number */
  1183.     sp->dat[1] = pg->symspot;    /* length of symbol */
  1184.     sp->cat = cat;                /* hashing info */
  1185.  
  1186.     /* Accept the string which was built up in the text chunk */
  1187.     PARSERSYMBOLS[symnum].name = pg->symbase; /* save pointer to the string */
  1188.     pg->pst.cnt += 1;
  1189.     pg->totsymlen += pg->symspot+1;
  1190.  
  1191.     pg->symbase = ++pg->symend;
  1192.     pg->symspot = 0;
  1193.     pg->symhash = 0;
  1194.  
  1195.     /* Return new data */
  1196.     pg->lastsymnum = symnum;
  1197.     pg->lastclass = 0;
  1198.     return symnum;
  1199. }
  1200. void
  1201. DelLastParserSymbol(PG *pg)
  1202. {
  1203.     if(pg->pst.cnt > 0)
  1204.     {
  1205.     void *binp;
  1206.         if((binp = ((PbufP)pg->symhandle)->lastbin))
  1207.         {
  1208.         PsymP p = *((PsymP *)binp);
  1209.             pg->totsymlen -= p->dat[1]+1;
  1210.             pg->pst.cnt -= 1;
  1211.             *((PsymP *)binp) = p->next;
  1212.             FreeAstNode(pg, (AstP)p);
  1213.             ((PbufP)pg->symhandle)->lastbin = 0;
  1214.         }
  1215.     }
  1216. }
  1217. char *
  1218. GetH_symbol(PG *pg, int numb)
  1219. {
  1220. PTABLE *pp = pg->ptab;
  1221. long *symbase = pp->G_symbol;
  1222. char *symptr = (char *)symbase;
  1223.  
  1224.     return symptr + symbase[numb];
  1225. }
  1226. AstP
  1227. NewAstNode(PG *pg, int id, int symb)
  1228. {
  1229. AstP node;
  1230.     if(pg->pat.freecnt > 0)
  1231.     {
  1232.         node = pg->pat.free;
  1233.         pg->pat.free = node->down;
  1234.         node->down = 0;
  1235.     }
  1236.     else
  1237.     {
  1238.     int i;
  1239.     AstP fnode;
  1240.         node = callocC(pg->category, 1, ASTCHUNK*ASTSIZE);
  1241.         pg->pat.cnt += ASTCHUNK;
  1242.         pg->pat.freecnt = ASTCHUNK;
  1243.         pg->pat.free = (AstP)(((char*)node)+ASTSIZE);
  1244.         fnode = (AstP)(((char*)node)+ASTSIZE);
  1245.         for(i = 1; i < ASTCHUNK-1; ++i)
  1246.         {
  1247.             fnode->down = (AstP)(((char*)fnode)+ASTSIZE);
  1248.             fnode = fnode->down;
  1249.         }
  1250.     }
  1251.     node->id = id;
  1252.     node->symb = symb;
  1253.     --pg->pat.freecnt;
  1254.     return node;
  1255. }
  1256. void
  1257. FreeAstNode(PG *pg, AstP node)
  1258. {
  1259.     if(node > ASTMINADDR)
  1260.     {
  1261.         memclr(node, ASTSIZE);
  1262.         node->down = pg->pat.free;
  1263.         pg->pat.free = node;
  1264.         ++pg->pat.freecnt;
  1265.     }
  1266. }
  1267. void
  1268. PruneAstTree(PG *pg, AstP root, int preserve_root, const AstP top)
  1269. {
  1270. ASTVARS(256);
  1271. int at_top = 1;
  1272.  
  1273.     if(root > ASTMINADDR)
  1274.     {
  1275.         if(top > ASTMINADDR)
  1276.             at_top = 0;
  1277.         curnode = root;
  1278.         MARK(stack);
  1279.         while(curnode = BOTTOMUP(curnode)) {
  1280.             if(!at_top)
  1281.             {
  1282.                 if(curnode == top) {
  1283.                     at_top = 1;
  1284.                     continue;
  1285.                 }
  1286.             }
  1287.             if(preserve_root && curnode == root)
  1288.                 break;
  1289.             if(at_top)
  1290.                 FreeAstNode(pg, curnode);
  1291.         }
  1292.     }
  1293. }
  1294.  
  1295.  
  1296. /*--- Print Abstract Syntax Tree - courtesy of Paul Mann ------------------ */
  1297.  
  1298. static void
  1299. prt_node (char *indent, AstP node, PG *pg, void *file, int ptrs)
  1300. {
  1301. char *nodename;
  1302.  
  1303.     if(node->id == 0)
  1304.         nodename = "NullNode";
  1305.     else
  1306.         nodename = GetH_symbol(pg, node->id>>6);
  1307.  
  1308.     if(ptrs) {
  1309.         if(node->right < ASTMINADDR)        
  1310.             (*pg->writefunc) (file, "  %6x  %6d  %6x %s%s_%d",
  1311.                   node, node->lineno, node->down, indent, nodename, node->id & 0x3f);
  1312.         else
  1313.             (*pg->writefunc) (file, "  %6x  %6x  %6x %s%s_%d",
  1314.                   node, node->right, node->down, indent, nodename, node->id & 0x3f);
  1315.     }
  1316.     else
  1317.         (*pg->writefunc) (file, "%s%s_%d", indent, nodename, node->id & 0x3f);
  1318.     
  1319.     if (node->symb > 0)
  1320.     {
  1321.     char *symbname = PARSERSYMBOLS [node->symb].name;
  1322.  
  1323.         if(symbname)
  1324.         {
  1325.             if(*symbname != EOF_MARK)
  1326.                 (*pg->writefunc) (file, " %s", symbname);
  1327.             if(node->Tindx)
  1328.             {
  1329.                 symbname = PARSERSYMBOLS [node->Tindx].name;
  1330.                 (*pg->writefunc) (file, "   %s", symbname);
  1331.             }
  1332.         }
  1333.         else (*pg->writefunc) (file, " [%d]", node->symb);
  1334.     }
  1335.     (*pg->writefunc) (file, "\n");
  1336. }
  1337. static void
  1338. traverse (char *indent, AstP node, PG *pg, void *file, int ptrs)
  1339. {
  1340.       while (node->down)
  1341.       {
  1342.          strcat (indent, "├─");
  1343.          prt_node (indent, node, pg, file, ptrs);
  1344.          indent [strlen(indent)-2] = 0;          /* BACK UP */
  1345.          if (node->right > ASTMINADDR)
  1346.          {
  1347.             strcat (indent, "│ ");
  1348.             traverse (indent, node->right, pg, file, ptrs);
  1349.             indent [strlen(indent)-2] = 0; /* BACK UP */
  1350.          }
  1351.          node = node->down;
  1352.       }
  1353.  
  1354.    /* Last node on this level. */
  1355.       strcat (indent, "└─");
  1356.       prt_node (indent, node, pg, file, ptrs);
  1357.       indent [strlen(indent)-2] = 0;
  1358.       if (node->right > ASTMINADDR)
  1359.       {
  1360.          strcat (indent, "· ");
  1361.          traverse (indent, node->right, pg, file, ptrs);
  1362.          indent [strlen(indent)-2] = 0;
  1363.       }
  1364. }
  1365.  
  1366. void 
  1367. PrintAst (PG *pg, const AstP root, void *file, int ptrs)
  1368. {
  1369. char indent [512];
  1370. indent[0] = '\0';
  1371.  
  1372.       if(IsObj(file))
  1373.       {
  1374.         pg->writefunc = (void*)imiPointer((object)file, gPrintf);
  1375.       }
  1376.       else
  1377.       {
  1378.         pg->writefunc = (void*)cffprintf;
  1379.       }
  1380.       if (root)
  1381.       {
  1382.         if(ptrs) (*pg->writefunc) (file, "    numb   right    down\n");
  1383.          traverse (indent, root, pg, file, ptrs);
  1384.       }
  1385.       else (*pg->writefunc) (file, " No AST available.\n");
  1386.       (*pg->writefunc) (file, "\n");
  1387. }
  1388.  
  1389.  
  1390. #if HOWBIG
  1391. void
  1392. HowBigAst(PG *pg, void *file)
  1393. {
  1394.     if(IsObj(file))
  1395.     {
  1396.         pg->writefunc = (void*)imiPointer((object)file, gPrintf);
  1397.     }
  1398.     else pg->writefunc = (void*)cffprintf;
  1399.  
  1400.     (*pg->writefunc) (file,"xx=%d SSp=%d SSl=%d NS=%d LS=%d RS=%d\nn_nodes=%d nsyms=%d hdups=%d\n",
  1401.         maxXX_parse, maxSS_parse, maxSS_lex, maxNS_parse,
  1402.         maxLS_parse, maxRS_parse, pg->pat.cnt - pg->pat.freecnt,
  1403.         pg->pst.cnt - pg->ptab->n_terms, pg->hashdups);
  1404. }
  1405. #endif
  1406.  
  1407. /*---  Scan Within an AST from the top down ------------------------------ */
  1408. #define PUSH(sp) (*(++(*sp)))
  1409. #define POP(sp) (*((*sp)--))
  1410. AstP
  1411. AstTopDown(AstP **sp, const AstP curnode, PG *pg)
  1412. {
  1413. AstP temp;
  1414.  
  1415.     if(curnode <= ASTMINADDR)
  1416.     {
  1417.         if((temp = STACKTOP(sp)))
  1418.         {
  1419.             if(NODEDOWN(STACKTOP(sp)))
  1420.               STACKTOP(sp) = NODEDOWN(STACKTOP(sp));
  1421.             else (void)POP(sp);
  1422.         }
  1423.         else (void)POP(sp);
  1424.     }
  1425.     else if(NODERIGHT(curnode) > ASTMINADDR)
  1426.     {
  1427.         if(NODEDOWN(NODERIGHT(curnode)))
  1428.           PUSH(sp) = NODEDOWN(NODERIGHT(curnode));
  1429.         temp = NODERIGHT(curnode);
  1430.     }
  1431.     else 
  1432.     {
  1433.         if((temp = POP(sp))) {/* Keep these braces, compiler opti bug */
  1434.           if(NODEDOWN(temp)) {
  1435.             PUSH(sp) = NODEDOWN(temp);
  1436.           }
  1437.         }
  1438.     }
  1439.     if(temp > ASTMINADDR)
  1440.     {
  1441.         if(temp->id == pg->blockinID)
  1442.             pg->blocklevel++;
  1443.         else if(temp->id == pg->blockoutID)
  1444.             pg->blocklevel--;
  1445.     }
  1446.     return temp;
  1447. }
  1448. /*--- Scan Within an AST from the bottom up ------------------------------- */
  1449. /* Subroutine for bottom up */
  1450. static __inline__ AstP
  1451. bu_follow(AstP **sp, AstP curnode)
  1452. {
  1453.     if(NODEDOWN(curnode))
  1454.       PUSH(sp) = NODEDOWN(curnode);
  1455.     if(NODERIGHT(curnode) > ASTMINADDR)
  1456.       return NODERIGHT(curnode);
  1457.     return POP(sp);
  1458. }
  1459.  
  1460. AstP
  1461. AstBottomUp(AstP **sp, const AstP start_node, PG *pg)
  1462. {
  1463. AstP temp;
  1464.     if(STACKTOP(sp) == (AstP)0)
  1465.     {/* First entry from a MARK(sp), find the bottom of this thread */
  1466.     AstP *stack;
  1467.     AstP *nexts = calloc(1, 4000);
  1468.     AstP curnode = start_node;
  1469.     AstP stop_node = NODEDOWN(start_node);
  1470.  
  1471.         PUSH(sp) = (AstP)-1;    /* Mark the top */
  1472.         stack = nexts;
  1473.         *stack++ = (AstP)0;
  1474.         for(;;)
  1475.         {
  1476.             curnode = bu_follow(&stack, curnode);
  1477.             if(curnode == (AstP)0 || curnode == stop_node)
  1478.                 break;
  1479.             PUSH(sp) = curnode;
  1480.         }
  1481.         free(nexts);
  1482.     }
  1483.     if(STACKTOP(sp) == (AstP)-1)
  1484.     {/* Hit the mark */
  1485.         (void)POP(sp);    /* Clear it -- next should (better!) be a 0 */
  1486.     }
  1487.     temp = POP(sp);
  1488.     if(temp > ASTMINADDR)
  1489.     {
  1490.         if(temp->id == pg->blockinID)
  1491.             pg->blocklevel--;
  1492.         else if(temp->id == pg->blockoutID)
  1493.             pg->blocklevel++;
  1494.     }
  1495.     return temp;
  1496. }
  1497. int
  1498. AstPackSize(PG *pg)
  1499. {
  1500. int    astsize = ASTSIZE*(pg->pat.cnt-pg->pat.freecnt);
  1501. int    symptrsize = pg->pst.cnt*sizeof(PARSER_SYMBOL);
  1502. int bufsize = sizeof(PG) + symptrsize + astsize + pg->totsymlen;
  1503.  
  1504.     bufsize += (bufsize&3) ? 4-(bufsize&3) : 0;
  1505.     return bufsize;
  1506. }
  1507. void *
  1508. PackAst(PG *pg, void *buf)
  1509. {
  1510. ASTVARS(256);
  1511. PG *pk;
  1512. int astsize;
  1513. int symptrsize;
  1514. AstP pnode;
  1515. PARSER_SYMBOL *pptr;
  1516. char *ptext; 
  1517. int i, xx, recovered;
  1518. AstP ddstack[256];
  1519. AstP *dstack = ddstack;
  1520.  
  1521.     astsize = ASTSIZE*(pg->pat.cnt-pg->pat.freecnt);
  1522.     symptrsize = pg->pst.cnt*sizeof(PARSER_SYMBOL);
  1523.     pk = buf;
  1524.     if(pk == NULL)
  1525.     {
  1526.     int bufsize = 
  1527.         sizeof(PG) + symptrsize + astsize + pg->totsymlen;
  1528.  
  1529.         bufsize += (bufsize&3) ? 4-(bufsize&3) : 0;
  1530.         pk = calloc(1,bufsize);
  1531.     }
  1532.     memcpy(pk, pg, sizeof(PG));
  1533.     pk->pat.freecnt = 0;
  1534.     pk->pat.free = 0;
  1535.     pnode = (AstP)((char*)pk + sizeof(PG));                /* ast nodes */
  1536.     pptr = (PARSER_SYMBOL*)((char *)pnode + astsize);    /* symbol pointers */
  1537.     ptext = (char *)pptr + symptrsize;                     /* symbol text */
  1538.     pk->pst.ptr = pptr;
  1539.     pk->root = pnode;
  1540.  
  1541.     /* MOVE THE SYMBOL POINTERS AND STRINGS */
  1542.     for(i = 0; i < pg->pst.cnt; ++i)
  1543.     {
  1544.         pptr[i].name = ptext;
  1545.         xx = _strcpy(ptext, pg->pst.ptr[i].name);
  1546.         ptext += xx + 1;
  1547.     }
  1548.  
  1549.     /* MOVE THE NODES */
  1550.     MARKAST;
  1551.     recovered = 0;
  1552.     curnode = pg->root;
  1553.     *pnode = *curnode;
  1554.  
  1555.     if(curnode->down)
  1556.         *(++dstack) = pnode;
  1557.     if(curnode->right > ASTMINADDR) {
  1558.         pnode->right = pnode+1;
  1559.         ++pnode;
  1560.     }
  1561.     else {
  1562.         ++pnode;
  1563.         recovered = 1;
  1564.     }
  1565.     while(DOWNAST)
  1566.     {
  1567.         *pnode = *curnode;
  1568.         if(recovered) {
  1569.         AstP prev = *dstack--;
  1570.             prev->down = pnode;
  1571.             recovered = 0;
  1572.         }
  1573.         if(curnode->down) {
  1574.             *(++dstack) = pnode;
  1575.         }
  1576.         if(curnode->right > ASTMINADDR) {
  1577.             pnode->right = pnode+1;
  1578.             ++pnode;
  1579.         } else {
  1580.             ++pnode;
  1581.             recovered = 1;
  1582.         }
  1583.     }
  1584.     return pk;
  1585. }
  1586.  
  1587. /* ----- PARSER ACTIONS AVAILABLE TO GRAMMAR WRITERS ----- */
  1588.  
  1589. /*
  1590.     Standard action which does nothing.
  1591. */
  1592. static void
  1593. nullaction(PG *pg, long *args)
  1594. {
  1595.     return;
  1596. }
  1597. /*
  1598.     Standard action to classify a symbol -- called from the parser
  1599.     arg[0] is the argcnt;
  1600.     arg[1] is the type of branch to look for (terminal index)
  1601.     arg[2] is an optional branch(1) to the right (nodeid)
  1602.     arg[3] is an alternate optional branch(2) to the right (nodeid)
  1603.     arg[4] if branch(1) branch again if encountered (nodeid)
  1604.     arg[5] if branch(1) terminate here and check leaf (nodeid)
  1605.     arg[6] is the type of leaf to look for    (terminal index)
  1606.     arg[7] is the classification to apply
  1607.     arg[8] is the sub classification (a shift count)
  1608.  
  1609.     Apply the classification codes to the high 32 bits of the
  1610.     symbol item in the database.
  1611. */
  1612. static void
  1613. classify(PG *pg, long *args)
  1614. {
  1615. AstP curnode = pg->ptab->node;
  1616. AstP inode;
  1617.  
  1618.     if(args[0] != 8)
  1619.     {
  1620.         pg->actionerr = "classify: incorrect number of args.";
  1621.         return;
  1622.     }
  1623.     if((curnode = curnode->right) < ASTMINADDR)
  1624.         return;
  1625.     if(curnode->Tindx != args[1])
  1626.         return;
  1627.  
  1628.     while(curnode && (curnode = curnode->down))
  1629.     {
  1630.       if ((curnode->id & 0xffc0) == args[2])
  1631.       {/* InitDeclarator */
  1632.         inode = curnode->right;
  1633.         do {
  1634.           if(inode->id == args[4])    /* ParenDeclarator */
  1635.               inode = inode->right;
  1636.           if(inode->id == args[5])    /* DeclID */
  1637.           {
  1638.           unsigned short *item;
  1639.             if(lookup(pg, PARSERSYMBOLS[inode->symb].name, &item))
  1640.             {
  1641.               if(item[2] == 0)
  1642.               {    /* don't re-classify */
  1643.                 item[2] = (unsigned short)args[7];/* class */
  1644.                 item[3] |= (unsigned short)(1<<(args[8]-args[7]-1));/* sub-class */
  1645.               }
  1646.             }
  1647.             else
  1648.             {
  1649.               pg->actionerr = "classify: symbol not found.";
  1650.             }
  1651.           }
  1652.         } while((inode = inode->down));
  1653.       }
  1654.       else if ((curnode->id & 0xffc0) == args[3])
  1655.       {/* TypeAgain */
  1656.          inode = curnode->right;
  1657.         do {
  1658.           if(inode->Tindx == args[6])    /* <identifier> */
  1659.           {
  1660.           unsigned short *item;
  1661.             if(lookup(pg, PARSERSYMBOLS[inode->symb].name, &item))
  1662.             {
  1663.               if(item[2] == 0)
  1664.               {    /* don't re-classify */
  1665.                 item[2] = (unsigned short)args[7];/* class */
  1666.                 item[3] |= (unsigned short)(1<<(args[8]-args[7]-1));/* sub-class */
  1667.               }
  1668.             }
  1669.             else
  1670.             {
  1671.               pg->actionerr = "classify: symbol not found.";
  1672.             }
  1673.           }
  1674.         } while((inode = inode->down));
  1675.       }
  1676.       else continue;
  1677.     } 
  1678. }
  1679.  
  1680. /*
  1681.     Standard action to require a particular subclass of a classified symbol.
  1682. */
  1683. static void
  1684. require(PG *pg, long *args)
  1685. {
  1686. AstP curnode = pg->ptab->node;
  1687. int ok = 0;
  1688.  
  1689.     if(args[0] != 2)
  1690.     {
  1691.         pg->actionerr = "require: incorrect number of args.";
  1692.         return;
  1693.     }
  1694.  
  1695.     if(curnode->Tindx == args[1])
  1696.     {
  1697.         ok = 1;
  1698.     }
  1699.     else
  1700.     {
  1701.         if((curnode = curnode->right) > ASTMINADDR)
  1702.             if(curnode->Tindx == args[1])
  1703.                 ok = 1;
  1704.     }
  1705.     while(ok)
  1706.     {
  1707.     unsigned short *item;
  1708.         if(lookup(pg, PARSERSYMBOLS[curnode->symb].name, &item))
  1709.         {
  1710.             if(item[2] == (unsigned short)args[1])
  1711.             {
  1712.                 if(!(item[3] & (unsigned short)(1<<(args[2]-args[1]-1))))
  1713.                     pg->actionerr = "require: symbol not member of subclass.";
  1714.             }
  1715.             else
  1716.             {
  1717.                 pg->actionerr = "require: symbol not classified correctly.";
  1718.             }
  1719.         }
  1720.         else
  1721.         {
  1722.             pg->actionerr = "require: symbol not found.";
  1723.         }
  1724.         break;
  1725.     }
  1726.     if(!ok)
  1727.     {
  1728.         pg->actionerr = "require: invalid ast configuration.";
  1729.     }
  1730. }
  1731. /*
  1732.     Standard lexical action to handle the '#line' directive.
  1733.     #line 123 "filename" [flagchar] [identchar]
  1734. */
  1735. static void
  1736. doline(PG *pg, long *args)
  1737. {
  1738. char *lnbeg;
  1739. char *fnbeg;
  1740. char *fnend;
  1741. int newfile = 0;
  1742.  
  1743.     pg->ltab->lextoken = 0;    /* kill the token */
  1744.     lnbeg = strchr(PARSERSYMBOLS[pg->lastsymnum].name, 'e');
  1745.     DelLastParserSymbol(pg); /* The whole line was entered as a symbol */
  1746.     if(lnbeg)
  1747.     {
  1748.       pg->line_numb = atol(++lnbeg);        /* Current line number */
  1749.       if((fnbeg = strchr(lnbeg, '"')))        /* Check for filename */
  1750.       {
  1751.         if((fnend = strrchr(fnbeg+1, '"')))
  1752.         {          
  1753.         char *flbeg = fnend+1;
  1754.  
  1755.           while(*flbeg && !isdigit(*flbeg)) ++flbeg;
  1756.           if(*flbeg)
  1757.           {
  1758.             if(*flbeg == '1')
  1759.             {/* enter file */
  1760.                 goto enter_file;
  1761.             }
  1762.             else if(*flbeg == '2')
  1763.             {/* leave file */
  1764.               pg->line_file = ParserPop(pg);
  1765.               return;
  1766.             }
  1767.           }
  1768.           /* '3' or 0 in the first flag field */
  1769.           if(pg->line_file > 0)
  1770.             return ;
  1771. enter_file:
  1772.           *fnbeg = '{';        /* Ensure uniqueness of the symbol */
  1773.           *fnend++ = '}';
  1774.           *fnend = 0;
  1775.           pg->curfile = NewParserSymbol(pg, fnbeg);
  1776.           if(pg->curfile > pg->maxfile)
  1777.           {
  1778.             pg->maxfile = pg->curfile;
  1779.             pg->files[++pg->numfiles] = (short)pg->curfile;
  1780.             newfile = pg->numfiles;
  1781.           }
  1782.           else
  1783.           {
  1784.           int i;
  1785.             for(i = 1; i <= pg->numfiles; ++i) {
  1786.               if(pg->curfile == pg->files[i]) {
  1787.                 newfile = i;
  1788.                 break;
  1789.               }
  1790.             } 
  1791.           }
  1792.           if(pg->line_file)
  1793.               ParserPush(pg, pg->line_file);
  1794.           pg->line_file = newfile;
  1795.         } /* END: fnbeg == '"' */
  1796.       }  /* END: fnend == '"' */
  1797.     } /* END: lnbeg */
  1798. }
  1799.  
  1800. /*
  1801.     Standard lexical action to convert symbols to terminals of the grammar.
  1802.     It is usually called when <identifier> or some such is detected.
  1803.     The symbol has already been entered in the symbol table (which was
  1804.     filled with the terminals of the grammar at init time). If the
  1805.     symbol number is less than the number of grammar terminals, then
  1806.     this symbol is a reserved word, the token for which is not <identifier>
  1807.     but the symbol number itself. Other <identifier> symbols may
  1808.     have been classified (such as {typedef-name} or {class-name}).
  1809. */
  1810. static void
  1811. dyntoken(PG *pg, long *args )
  1812. {
  1813. int symnum = pg->L_stack[pg->LSP];
  1814.  
  1815.     if(symnum < pg->ptab->n_terms)
  1816.     {/* This symbol really a reserved word */
  1817.         pg->ltab->lextoken = symnum;
  1818.     }
  1819.     else if(pg->lastclass)
  1820.     {/* This symbol has been classified */
  1821.         pg->ltab->lextoken = pg->lastclass;
  1822.     }    
  1823. }
  1824.