home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume21 / rh2 / part02 / rhparse.c < prev   
Encoding:
C/C++ Source or Header  |  1990-03-21  |  14.2 KB  |  785 lines
  1.  
  2. /* ----------------------------------------------------------------------
  3.  * FILE: rhparse.c
  4.  * VERSION: 2
  5.  * Written by: Ken Stauffer
  6.  * This contains the parser for the C expressions,
  7.  * gettoken(), getit() and ungetit() routines.
  8.  * sectime(), datespec(), expression(), expr(), exp0(), ... , factor()
  9.  * locatename(), push(), find_macro()
  10.  *
  11.  *
  12.  * ---------------------------------------------------------------------- */
  13.  
  14. #include "rh.h"
  15. #include <ctype.h>
  16. #include <pwd.h>
  17.  
  18. static int cpos;        /* current character position */
  19. static int lineno;        /* current line number */
  20.  
  21. /* ----------------------------------------------------------------------
  22.  * getit:
  23.  *    Return the next character, input is obtained from a file or
  24.  *    a string.
  25.  *    If expstr == NULL then input is from the file called 'expfname'
  26.  *    with file pointer 'expfile'.
  27.  *
  28.  *    If expstr != NULL then input is from the string 'expstr'
  29.  *
  30.  */
  31.  
  32. getit()
  33. {
  34.     int c;
  35.  
  36.     if( expstr ) c = (*expstr) ? *expstr++ : EOF;
  37.     else c = getc(expfile);
  38.  
  39.     if( c == '\n' ) { lineno++; cpos = 0; }
  40.     cpos++;
  41.  
  42.     return(c);
  43. }
  44.  
  45. /* ----------------------------------------------------------------------
  46.  * ungetit:
  47.  *    Unget a char.
  48.  *    A character is ungotten using the same scheme as stated for
  49.  *    getit() for determining where input is comming from.
  50.  *
  51.  */
  52.  
  53. ungetit(c)
  54. int c;
  55. {
  56.     if( c == '\n' ) { lineno--; cpos = 1; }
  57.     else cpos--;
  58.     if( expstr ) expstr = (c > 0) ? expstr-1 : expstr;
  59.     else ungetc(c,expfile);
  60. }
  61.  
  62. /* ----------------------------------------------------------------------
  63.  * error:
  64.  *    Print an error message and quit.
  65.  */
  66.  
  67. error(s)
  68. char *s;
  69. {
  70.     if( expstr )
  71.         fprintf(stderr,"Command line: ");
  72.     else
  73.         fprintf(stderr,"%s: ",expfname);
  74.  
  75.     fprintf(stderr,"line: %d, char: %d, %s.\n",lineno,cpos,s);
  76.     exit(1);
  77. }
  78.  
  79. /* ----------------------------------------------------------------------
  80.  * insertname:
  81.  *    Inserts the symbol named 's' with type 't' and value 'val'
  82.  *    into the symbol table. Return the a pointer to the symbol
  83.  *    table entry. The symbol is inserted into the head of the
  84.  *    linked list. This behavior is relied upon elswhere.
  85.  *
  86.  */
  87.  
  88. struct symbol *insertname(s,t,val)
  89. char *s;
  90. int t;
  91. long val;
  92. {
  93.     char *p,*malloc();
  94.     struct symbol *sym;
  95.  
  96.     sym = (struct symbol *) malloc( sizeof(struct symbol) );
  97.     if( sym == NULL ) error("no more memory");
  98.  
  99.     p = sym->name = malloc( strlen(s)+1 );
  100.     if( sym->name == NULL ) error("no more memory");
  101.     while( *p++ = *s++ );
  102.     sym->type = t;
  103.     sym->value = val;
  104.  
  105.     sym->next = symbols;
  106.     symbols = sym;
  107.     
  108.     return( sym );
  109. }
  110.  
  111. /* ----------------------------------------------------------------------
  112.  * locatename:
  113.  *    Do a linear search for 's' in the linked list symbols.
  114.  *
  115.  */
  116.  
  117. struct symbol *locatename(s)
  118. char *s;
  119. {
  120.     struct symbol *p;
  121.  
  122.     for(p=symbols; p; p = p->next )
  123.         if( !strcmp(s,p->name) ) return(p);
  124.  
  125.     return(NULL);
  126. }
  127.  
  128. /* ----------------------------------------------------------------------
  129.  * push:
  130.  *    "assemble" the instruction into the StackProgram[] array.
  131.  *
  132.  */
  133.  
  134. push(func,val)
  135. int (*func)();
  136. long val;
  137. {
  138.     if( PC >= LENGTH ) error("program to big");
  139.     StackProgram[PC].func=func;
  140.     StackProgram[PC++].value=val;
  141. }
  142.  
  143. /* ----------------------------------------------------------------------
  144.  * program:
  145.  *    Parse a program of the form:
  146.  *        <program> ==> <function-list> <expression> EOF
  147.  *            | <function-list> EOF
  148.  *            | <function-list> <expression> ;
  149.  *
  150.  *        <function-list> ==> <function> <function-list>
  151.  *                | empty
  152.  */
  153.  
  154. program()
  155. {
  156.     cpos = 0; lineno = 1;
  157.  
  158.     token = gettoken();
  159.     for(;;) {
  160.         if( token != IDENTIFIER ) break;
  161.         function();
  162.     }
  163.  
  164.     if( token != EOF ) {
  165.         startPC = PC;
  166.         expression();
  167.         push(NULL,0);
  168.     }
  169.     if( token != EOF && token != ';') error("EOF expected");
  170. }
  171.  
  172. /* ----------------------------------------------------------------------
  173.  * function:
  174.  *    parse a function definition. Grammer for a function is:
  175.  *    <function> ==> IDENTIFIER <id-list> { RETURN <expression> ; }
  176.  *
  177.  *    <id-list> ==> ( <ids> )
  178.  *            | ( )
  179.  *            | empty
  180.  *
  181.  *    <ids> ==> IDENTIFIER <idtail>
  182.  *
  183.  *    <idtail> ==> , <ids>
  184.  *        | empty
  185.  *
  186.  */
  187.  
  188. function()
  189. {
  190.     struct symbol *s;
  191.  
  192.     s = tokensym;
  193.     tokensym->value = PC;
  194.     tokensym->type = FUNCTION;
  195.     tokensym->func = c_func;
  196.  
  197.     token = gettoken();
  198.  
  199.     push(NULL, idlist() );        /* save number of args for function */
  200.  
  201.     if( token != '{' ) error("expected '{'");
  202.     token = gettoken();
  203.  
  204.     if( token != RETURN ) error("expected keyword: return");
  205.     token = gettoken();
  206.  
  207.     expression();
  208.  
  209.     if( token != ';' ) error("expected ';'");
  210.     token = gettoken();
  211.  
  212.     push(c_return,StackProgram[s->value].value);
  213.  
  214.     /* free up the parameter symbols */
  215.     while( symbols->type == PARAM ) {
  216.         s = symbols;
  217.         symbols = symbols->next;
  218.         free(s->name);
  219.         free(s);
  220.     }
  221.  
  222.     if( token != '}' ) error("expected '}'");
  223.     token = gettoken();
  224. }
  225.  
  226. /* ----------------------------------------------------------------------
  227.  * idlist:
  228.  *    Return the maximum offset obtained in parsing the parameter list.
  229.  *    <id-list> ==> ( <ids> )
  230.  *        | ()
  231.  *        | empty
  232.  *
  233.  *    <ids> ==> IDENTIFIER <idtail>
  234.  *    <idtail> ==> <ids> , <idtail>
  235.  *        | empty
  236.  */
  237.  
  238. idlist()
  239. {
  240.     int offset = 0;
  241.  
  242.     if( token == '(' ) token = gettoken();
  243.     else if( token == '{' ) return(0);
  244.     else error("expected '(' or '{'");
  245.  
  246.     if( token == ')' ) {
  247.         token = gettoken();
  248.         return(0);
  249.     }
  250.  
  251.     for(;;) {
  252.         if( token != IDENTIFIER ) error("identifier expected");
  253.         tokensym->type = PARAM;
  254.         tokensym->func = c_param;
  255.         tokensym->value = offset++;
  256.         token = gettoken();
  257.         if( token == ')' ) break;
  258.         if( token != ',' ) error("expected ')'");
  259.         token = gettoken();
  260.     }
  261.  
  262.     token = gettoken();
  263.     return(offset);
  264. }
  265.  
  266. /* ----------------------------------------------------------------------
  267.  * expression:
  268.  *    Parse an expression. (top-level routine)
  269.  *    OPERATOR ?:
  270.  *
  271.  */
  272.  
  273. expression()
  274. {
  275.     int qm,colon,nop;
  276.  
  277.     expr0();
  278.     if( token == '?' ) {
  279.         token = gettoken();
  280.         qm = PC;
  281.         push(c_qm,0);
  282.         expression();
  283.         if( token != ':' ) error("missing ':'");
  284.         token = gettoken();
  285.         colon = PC;
  286.         push(c_colon,0);
  287.         expression();
  288.  
  289.         StackProgram[qm].value = colon;
  290.         StackProgram[colon].value = PC-1;
  291.     }
  292. }        
  293.  
  294. /* OPERATOR || */ 
  295. expr0()
  296. {
  297.     expr1();
  298.     for(;;)
  299.         if( token == OR ) {
  300.             token = gettoken();
  301.             expr1();
  302.             push(c_or,0);
  303.            } else break;
  304. }
  305.  
  306. /* OPERATOR && */ 
  307. expr1()
  308. {
  309.     expr2();
  310.     for(;;)
  311.         if( token == AND ) {
  312.             token = gettoken();
  313.             expr2();
  314.             push(c_and,0);
  315.         } else break;
  316. }
  317.  
  318. /* OPERATOR | */
  319. expr2()
  320. {
  321.     expr3();
  322.     for(;;)
  323.         if( token == '|' ) {
  324.             token = gettoken();
  325.             expr3();
  326.             push(c_bor,0);
  327.         } else break;
  328. }
  329.  
  330. /* OPERATOR ^ */
  331. expr3()
  332. {
  333.     expr4();
  334.     for(;;)
  335.         if( token == '^' ) {
  336.             token = gettoken();
  337.             expr4();
  338.             push(c_bxor,0);
  339.         } else break;
  340. }
  341.  
  342. /* OPERATOR & */
  343. expr4()
  344. {
  345.     expr5();
  346.     for(;;)
  347.         if( token == '&' ) {
  348.             token = gettoken();
  349.             expr5();
  350.             push(c_band,0);
  351.         } else break;
  352. }
  353.  
  354. /* OPERATOR == != */
  355. expr5()
  356. {
  357.     int t;
  358.     expr6();
  359.     for(;t=token;)
  360.         if( t==EQ ) {
  361.             token = gettoken();
  362.             expr6();
  363.             push(c_eq,0);
  364.         } else if( t==NE ) {
  365.             token = gettoken();
  366.             expr6();
  367.             push(c_ne,0);
  368.         } else break;
  369. }
  370.  
  371. /* OPERATOR < <= > >= */
  372. expr6()
  373. {
  374.     int t;
  375.     expr7();
  376.     for(;t=token;)
  377.         if( t==LE ) {
  378.             token = gettoken();
  379.             expr7();
  380.             push(c_le,0);
  381.         } else if( t==GE ) {
  382.             token = gettoken();
  383.             expr7();
  384.             push(c_ge,0);
  385.         } else if( t=='>' ) {
  386.             token = gettoken();
  387.             expr7();
  388.             push(c_gt,0);
  389.         } else if( t=='<' ) {
  390.             token = gettoken();
  391.             expr7();
  392.             push(c_lt,0);
  393.         } else break;
  394. }
  395.  
  396. /* OPERATOR << >> */
  397. expr7()
  398. {
  399.     int t;
  400.     expr8();
  401.     for(;t=token;)
  402.         if( t==SHIFTL ) {
  403.             token = gettoken();
  404.             expr8();
  405.             push(c_lshift,0);
  406.         } else if( t==SHIFTR ) {
  407.             token = gettoken();
  408.             expr8();
  409.             push(c_rshift,0);
  410.         } else break;
  411. }
  412.  
  413. /* OPERATOR + - */
  414. expr8()
  415. {
  416.     int t;
  417.     expr9();
  418.     for(;t=token;)
  419.         if( t=='+' ) {
  420.             token = gettoken();
  421.             expr9();
  422.             push(c_plus,0);
  423.         } else if( t=='-' ) {
  424.             token = gettoken();
  425.             expr9();
  426.             push(c_minus,0);
  427.         } else break;
  428. }
  429.  
  430. /* OPERATOR * / % */
  431. expr9()
  432. {
  433.     int t;
  434.     expr10();
  435.     for(;t=token;)
  436.         if( t== '*' ) {
  437.             token = gettoken();
  438.             expr10();
  439.             push(c_mul,0);
  440.         } else if( t== '/' ) {
  441.             token = gettoken();
  442.             expr10();
  443.             push(c_div,0);
  444.         } else if( t== '%' ) {
  445.             token = gettoken();
  446.             expr10();
  447.             push(c_mod,0);
  448.         } else break;
  449. }
  450.  
  451. /* OPERATOR ~ ! - */ 
  452. expr10()
  453. {
  454.     int t;
  455.     t = token;    
  456.     if( t=='!' ){
  457.         token = gettoken();
  458.         expr10();
  459.         push(c_not,0);
  460.     } else if( t== '~' ) {
  461.         token = gettoken();
  462.         expr10();
  463.         push(c_bnot,0);
  464.     } else if( t== '-' ) {
  465.         token = gettoken();
  466.         expr10();
  467.         push(c_uniminus,0);
  468.     } else factor();
  469. }
  470.  
  471. /* ----------------------------------------------------------------------
  472.  * explist:
  473.  *    argc is the number of arguments expected.
  474.  *    Parse an expression list of the form:
  475.  *        <explist> ==> ( <exps> )
  476.  *            | ( )
  477.  *            | empty
  478.  *
  479.  *        <exps> ==> <exps> , <expression>
  480.  *            | <expression>
  481.  *
  482.  */
  483.  
  484. explist( argc )
  485. {
  486.     if( token != '(' && !argc ) return;
  487.  
  488.     if( token != '(' ) error("missing '('");
  489.     token = gettoken();
  490.  
  491.     if( !argc && token == ')' ) {
  492.         token = gettoken();
  493.         return;
  494.     }
  495.  
  496.     for(;;) {
  497.         expression();
  498.         argc--;
  499.         if( token == ')' ) break;
  500.         if( token != ',' ) error("missing ','");
  501.         token = gettoken();
  502.     }
  503.  
  504.     token = gettoken();
  505.     if( argc ) error("wrong number of arguments");
  506. }    
  507.  
  508. /* ----------------------------------------------------------------------
  509.  * factor:
  510.  *    Parse a factor. Could be a number, variable, date, function call or
  511.  *    regular expression string.
  512.  */
  513.  
  514. factor()
  515. {
  516.     long l,datespec();
  517.     int pc;
  518.  
  519.     switch(token) {
  520.         case '(':
  521.             token = gettoken();
  522.             expression();
  523.             if( token != ')' )
  524.                 error("missing ')'");
  525.             token = gettoken();
  526.             break;
  527.         case NUMBER:
  528.             push(c_number,tokenval);
  529.             token = gettoken();
  530.             break;
  531.         case FUNCTION:
  532.             pc = tokensym->value;
  533.             token = gettoken();
  534.             explist( StackProgram[ pc ].value );
  535.             push(c_func,pc);
  536.             break;
  537.         case PARAM:
  538.             push(c_param,tokensym->value);
  539.             token = gettoken();
  540.             break;
  541.         case FIELD:
  542.             push(tokensym->func,tokenval);
  543.             token = gettoken();
  544.             break;
  545.         case '[':
  546.             token = gettoken();
  547.             l=datespec();
  548.             if( token != ']' )
  549.                 error("missing ']'");
  550.             token = gettoken();
  551.             push(c_number,l);
  552.             break;
  553.         case STR:
  554.             push(c_str,tokenval);
  555.             token = gettoken();
  556.             break;
  557.         case IDENTIFIER:
  558.             error("undefined identifier");
  559.         default:
  560.             error("syntax error");
  561.     }
  562. }
  563.  
  564. /* ----------------------------------------------------------------------
  565.  * sectime:
  566.  *    calculate the number of seconds between January 1, 1970
  567.  *    and year/month/day. Return that value.
  568.  *
  569.  */
  570.  
  571. #define leap(d)    (((d % 4 == 0) && (d % 100 != 0)) || (d % 400 == 0))
  572. #define DAYSEC    (3600*24)
  573. #define YERSEC    (3600*24*365)
  574. #define TIME0    1970
  575.  
  576. long sectime(year,month,day)
  577. int year,month,day;
  578. {
  579.  
  580.         static int months[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
  581.     int yeardays,leapers,x;
  582.     long seconds;
  583.  
  584.     if(month>12 || month<1 || year<TIME0 || day<1 || day>months[month]+
  585.         (month==2 && leap(year)) )
  586.             return(-1);
  587.  
  588.     yeardays = leapers = 0;
  589.  
  590.     for(x=1;x<month;x++)
  591.         yeardays += months[x];
  592.     if ((month > 2) && leap(year)) yeardays++;
  593.  
  594.     for(x=TIME0; x<year; x++)
  595.         if(leap(x)) leapers++;
  596.     
  597.     seconds = yeardays*DAYSEC+(year-TIME0)*YERSEC+7*3600+
  598.             leapers*DAYSEC + day*DAYSEC;
  599.  
  600.     return(seconds);
  601.  
  602. }
  603.  
  604. /* ----------------------------------------------------------------------
  605.  * datespec:
  606.  *    parse a date. Return the number of seconds from
  607.  *    some date in 1970, until the specified date.
  608.  */
  609.  
  610. long datespec()
  611. {
  612.     int year,month,day,seconds;
  613.  
  614.     if( token != NUMBER ) error("number expected");
  615.     year = tokenval;
  616.     token = gettoken();
  617.     if( token != '/' ) error("missing '/'");
  618.     token = gettoken();
  619.     if( token != NUMBER ) error("number expected");
  620.     month = tokenval;
  621.     token = gettoken();
  622.     if( token != '/' ) error("missing '/'");
  623.     token = gettoken();
  624.     if( token != NUMBER ) error("number expected");
  625.     day = tokenval;
  626.     token = gettoken();
  627.  
  628.     if( (seconds = sectime(year,month,day)) < 0 ) 
  629.         error("invalid date");
  630.  
  631.     return(seconds);
  632. }
  633.  
  634.  
  635. /* ----------------------------------------------------------------------
  636.  * gettoken:
  637.  *    Return the next token.
  638.  *    global variable: tokenval will contain any extra
  639.  *    attribute associated with the returned token, ie
  640.  *    the VALUE of a number, the index of the string etc...
  641.  *    tokensym will be a pointer to the symbol table entry for
  642.  *    any symbol encountered.
  643.  *
  644.  */
  645.  
  646. gettoken()
  647. {
  648.     char buf[IDLENGTH+1],*bufp=buf;
  649.     int c,incomment;
  650.  
  651.     incomment = 0;
  652.     c = getit();
  653.     while( c == ' ' || c == '\t' || c == '\n' || c == '/' || incomment) {
  654.        if( c == '/' && !incomment) {
  655.         c = getit();
  656.         if( c != '*' ) {
  657.             ungetit(c);
  658.             c = '/';
  659.             break;
  660.         }
  661.         incomment = 1;
  662.        } else if( c == '*' ) {
  663.         c = getit();
  664.         if( c == '/' ) incomment = 0;
  665.        }
  666.        c = getit();
  667.     }
  668.  
  669.     if(c=='0') {
  670.         tokenval=0;
  671.         while( ( c=getit() ) >= '0' && c <= '7' ) {
  672.             tokenval <<= 3;
  673.             tokenval += c-'0';
  674.         }
  675.         if( isdigit(c) ) error("bad octal constant");
  676.         ungetit(c);
  677.         return(NUMBER);
  678.     }
  679.  
  680.     if(isdigit(c)) {
  681.         tokenval=c-'0';
  682.         while(isdigit( (c=getit()) )) {
  683.             tokenval *=10;
  684.             tokenval += c-'0';
  685.         }
  686.         ungetit(c);
  687.         return(NUMBER);
  688.     }
  689.     
  690.     if(isalpha(c)) {
  691.        int count=0;
  692.        do {
  693.         if(count++ < IDLENGTH) *bufp++ = c;
  694.         c=getit();
  695.        } while( isalnum(c) );
  696.        ungetit(c);
  697.        *bufp='\0';
  698.        if( (tokensym=locatename(buf)) == NULL ) {
  699.             tokensym = insertname(buf,IDENTIFIER,0);
  700.        }
  701.        tokenval = tokensym->value;
  702.        return( tokensym->type );
  703.     }
  704.  
  705.     if( c == '"' ) {
  706.         tokenval=strfree;
  707.         while( (c=getit()) != '"' ) {
  708.             if( strfree > STRLEN )
  709.                 error("no more string space");
  710.             Strbuf[strfree++]= c;
  711.         }
  712.         Strbuf[strfree++]='\0';
  713.         return(STR);
  714.     }
  715.  
  716.     if( c == '=' ) {
  717.         c=getit();
  718.         if(c== '=') return(EQ);
  719.         else {
  720.             ungetit(c);
  721.             return('=');
  722.         }
  723.     }
  724.  
  725.     if( c== '$' ) {
  726.        int count=0;
  727.        struct passwd *info,*getpwnam();
  728.        c=getit();
  729.        if( c=='$' ) {
  730.         tokenval = getuid();
  731.         return( NUMBER );
  732.        }
  733.        do {
  734.         if (count++ < IDLENGTH) *bufp++ = c;
  735.         c=getit();
  736.        } while( isalnum(c) );
  737.        ungetit(c);
  738.        *bufp='\0';
  739.        if( (info=getpwnam(buf)) == NULL ) 
  740.         error("no such user");
  741.        tokenval = info->pw_uid;
  742.        return( NUMBER );
  743.     }
  744.     
  745.     if( c == '!' ) {
  746.         c=getit();
  747.         if( c == '=' ) return(NE);
  748.         ungetit(c);
  749.         return('!');
  750.     }
  751.  
  752.     if( c == '>' ) {
  753.         c=getit();
  754.         if( c == '=' ) return(GE);
  755.         if( c == '>' ) return(SHIFTR);
  756.         ungetit(c);
  757.         return('>');
  758.     }
  759.  
  760.     if( c == '<' ) {
  761.         c=getit();
  762.         if( c == '=' ) return(LE);
  763.         if( c == '<' ) return(SHIFTL);
  764.         ungetit(c);
  765.         return('<');
  766.     }
  767.  
  768.     if( c == '&' ) {
  769.         c=getit();
  770.         if( c == '&' ) return(AND);
  771.         ungetit(c);
  772.         return('&');
  773.     }
  774.  
  775.     if( c == '|' ) {
  776.         c=getit();
  777.         if( c == '|' ) return(OR);
  778.         ungetit(c);
  779.         return('|');
  780.     }
  781.  
  782.     return(c);
  783. }
  784.  
  785.