home *** CD-ROM | disk | FTP | other *** search
/ Frozen Fish 2: PC / frozenfish_august_1995.bin / bbs / d09xx / d0975.lha / PCal / exprpars.c < prev    next >
C/C++ Source or Header  |  1992-02-19  |  9KB  |  374 lines
  1. /*
  2.  * exprpars.c - Pcal routines concerned with parsing if{n}def expressions
  3.  *
  4.  * Contents:
  5.  *
  6.  *        do_xxx
  7.  *        lookup_token
  8.  *        next_token
  9.  *        parse_expr
  10.  *
  11.  * Revision history:
  12.  *
  13.  *    4.0    AWR    02/06/91    Author
  14.  *
  15.  */
  16.  
  17. /*
  18.  * Standard headers:
  19.  */
  20.  
  21. #include <ctype.h>
  22. #include <string.h>
  23. #include <stdio.h>
  24.  
  25. /*
  26.  * Pcal-specific definitions:
  27.  */
  28.  
  29. #include "pcaldefs.h"
  30. #include "pcalglob.h"
  31.  
  32. /*
  33.  * Macros:
  34.  */
  35.  
  36. /*
  37.  * token type code definitions:
  38.  */
  39.  
  40. #define TK_UNKNOWN     0        /* codes returned by next_token() */
  41. #define TK_IDENT     1
  42. #define TK_LPAREN     2
  43. #define TK_RPAREN     3
  44. #define TK_UNARYOP     4
  45. #define TK_BINARYOP     5
  46. #define TK_ENDINPUT     6
  47. #define TK_STARTINPUT     7        /* special code for start symbol */
  48.  
  49. /* bit position for token type codes (cf. where_ok[] below) */
  50. #define ID_OK        (1 << TK_IDENT)
  51. #define LP_OK        (1 << TK_LPAREN)
  52. #define RP_OK        (1 << TK_RPAREN)
  53. #define UO_OK        (1 << TK_UNARYOP)
  54. #define BO_OK        (1 << TK_BINARYOP)
  55. #define ST_OK        (1 << TK_STARTINPUT)
  56. #define NEVER_OK    0
  57.  
  58. /* is token "curr" legal after "prev"? (cf. where_ok[] below) */
  59. #define IS_LEGAL(curr, prev)    (where_ok[curr] & (1 << (prev)))
  60.  
  61. /*
  62.  * operator-related definitions:
  63.  */
  64.  
  65. #define OP_AND        0    /* operator subcodes */
  66. #define OP_OR        1
  67. #define OP_XOR        2
  68. #define OP_NEGATE    3
  69.  
  70. #define ENDINPUT_PREC    -1    /* arbitrary number < lowest op. prec  */
  71. #define OR_PREC         1    /* operator precedence levels */
  72. #define XOR_PREC     2
  73. #define AND_PREC     3
  74. #define NEGATE_PREC     4
  75. #define PAREN_PREC     8    /* arbitrary number > highest op. prec */
  76.  
  77. /* lower bits of operator stack entry are code; higher are precedence */
  78. #define OPR_BITS    4
  79. #define OPR_MASK    ((1 << OPR_BITS) - 1)
  80. #define PREC(op)    ((op) >> OPR_BITS)
  81. #define OPCODE(op)    ((op) & OPR_MASK)
  82. #define MAKE_OPR(p, o)    (((p) << OPR_BITS) | (o))
  83.  
  84. #define MAX_OP        20    /* size of operand and operator stacks */
  85.  
  86. /*
  87.  * Globals:
  88.  */
  89.  
  90. typedef short OPERAND;        /* types for operand and operator stacks */
  91. typedef short OPERATOR;
  92.  
  93.  
  94. typedef struct {
  95.     char    *name;        /* token spelling */
  96.     short    type;        /* token type code */
  97.     short    value;        /* associated value */
  98.     } TOKEN;
  99.  
  100. /* token table - note that substrings must follow longer strings */
  101.  
  102. TOKEN token_tbl[] = {
  103.     "&&",    TK_BINARYOP,    OP_AND,        /* synonym for "&" */
  104.     "&",    TK_BINARYOP,    OP_AND,
  105.     "||",    TK_BINARYOP,    OP_OR,        /* synonym for "|" */
  106.     "|",    TK_BINARYOP,    OP_OR,
  107.     "!",    TK_UNARYOP,    OP_NEGATE,
  108.     "^",    TK_BINARYOP,    OP_XOR,
  109.     "(",    TK_LPAREN,    0,
  110.     ")",    TK_RPAREN,    0,
  111.     NULL,    TK_UNKNOWN,    0        /* must be last entry */
  112.     };
  113.  
  114.  
  115. typedef struct {
  116.     short prec;        /* precedence */
  117.     short type;        /* token type (TK_UNARYOP or TK_BINARYOP) */
  118. #ifdef PROTOS
  119.     OPERAND (*pfcn)(OPERAND *);    /* dispatch function */
  120. #else
  121.     OPERAND (*pfcn)();        /* dispatch function */
  122. #endif
  123.     } OPR;
  124.  
  125. /* operator table - entries must be in same order as OP_XXX */
  126.  
  127. #ifdef PROTOS
  128. static OPERAND do_and(OPERAND *);
  129. static OPERAND do_or(OPERAND *);
  130. static OPERAND do_xor(OPERAND *);
  131. static OPERAND do_negate(OPERAND *);
  132. #else
  133. static OPERAND do_and(), do_or(), do_xor(), do_negate();   /* dispatch fcns */
  134. #endif
  135.  
  136. OPR opr_tbl[] = {
  137.     AND_PREC,    TK_BINARYOP,    do_and,        /* OP_AND    */
  138.     OR_PREC,    TK_BINARYOP,    do_or,        /* OP_OR    */
  139.     XOR_PREC,    TK_BINARYOP,    do_xor,        /* OP_XOR    */
  140.     NEGATE_PREC,    TK_UNARYOP,    do_negate    /* OP_NEGATE    */
  141.     };
  142.  
  143.  
  144. /* set of tokens which each token may legally follow (in TK_XXX order) */
  145.  
  146. int where_ok[] = {
  147.     NEVER_OK                                      ,     /* TK_UNKNOWN    */
  148.     ST_OK         | LP_OK         | UO_OK | BO_OK ,     /* TK_IDENT    */
  149.     ST_OK         | LP_OK         | UO_OK | BO_OK ,     /* TK_LPAREN    */
  150.             ID_OK | LP_OK | RP_OK                 ,     /* TK_RPAREN    */
  151.     ST_OK         | LP_OK                 | BO_OK ,     /* TK_UNARYOP    */
  152.             ID_OK         | RP_OK                 ,     /* TK_BINARYOP    */
  153.     ST_OK | ID_OK         | RP_OK                    /* TK_ENDINPUT    */
  154.     };
  155.  
  156.  
  157. /*
  158.  * do_xxx - dispatch functions for operators
  159.  */
  160.  
  161. #ifdef PROTOS
  162. static OPERAND do_and(OPERAND *ptop)
  163. #else
  164. static OPERAND do_and(ptop)
  165.     OPERAND *ptop;
  166. #endif
  167. {
  168.     return ptop[0] & ptop[-1];
  169. }
  170.  
  171.  
  172. #ifdef PROTOS
  173. static OPERAND do_or(OPERAND *ptop)
  174. #else
  175. static OPERAND do_or(ptop)
  176.     OPERAND *ptop;
  177. #endif
  178. {
  179.     return ptop[0] | ptop[-1];
  180. }
  181.  
  182.  
  183. #ifdef PROTOS
  184. static OPERAND do_xor(OPERAND *ptop)
  185. #else
  186. static OPERAND do_xor(ptop)
  187.     OPERAND *ptop;
  188. #endif
  189. {
  190.     return ptop[0] ^ ptop[-1];
  191. }
  192.  
  193.  
  194. #ifdef PROTOS
  195. static OPERAND do_negate(OPERAND *ptop)
  196. #else
  197. static OPERAND do_negate(ptop)
  198.     OPERAND *ptop;
  199. #endif
  200. {
  201.     return ! ptop[0];
  202. }
  203.  
  204.  
  205. /*
  206.  * lookup_token - look up token in table; return pointer to table entry
  207.  */
  208. #ifdef PROTOS
  209. static TOKEN *lookup_token(char *p)
  210. #else
  211. static TOKEN *lookup_token(p)
  212.     char *p;
  213. #endif
  214. {
  215.     TOKEN *ptok;
  216.  
  217.     for (ptok = token_tbl;
  218.          ptok->name && strncmp(p, ptok->name, strlen(ptok->name));
  219.          ptok++)
  220.         ;
  221.  
  222.     return ptok;
  223. }
  224.  
  225.  
  226. /*
  227.  * next_token - fetch next token from input string; fill in its type and value
  228.  * and return pointer to following character
  229.  */
  230. #ifdef PROTOS
  231. static char *next_token(char *p,
  232.             int *ptype,
  233.             int *pvalue)
  234. #else
  235. static char *next_token(p, ptype, pvalue)
  236.     char *p;
  237.     int *ptype;
  238.     int *pvalue;
  239. #endif
  240. {
  241.     TOKEN *ptok;
  242.     char tokbuf[STRSIZ], *pb;
  243.  
  244. #define NT_RETURN(p, t, v) \
  245.     if (1) { *ptype = t; *pvalue = v; return p; } else
  246.  
  247.     while (*p && isspace(*p))    /* skip whitespace */
  248.         p++;
  249.  
  250.     if (*p == '\0')            /* end of input? */
  251.         NT_RETURN(p, TK_ENDINPUT, 0);
  252.  
  253.     if (isalpha(*p) || *p == '-') {        /* identifier or flag? */
  254.  
  255.         pb = tokbuf;        /* make local copy and look up */
  256.         while (*p && (isalpha(*p) || isdigit(*p) || *p == '_' ||
  257.                (pb == tokbuf && *p == '-')))
  258.             *pb++ = *p++;
  259.         *pb = '\0';
  260.  
  261.         NT_RETURN(p, TK_IDENT, find_sym(tokbuf));
  262.     }
  263.  
  264.     ptok = lookup_token(p);        /* other token */
  265.     NT_RETURN(p + (ptok->name ? strlen(ptok->name) : 1), ptok->type,
  266.         ptok->value);
  267. }
  268.  
  269.  
  270. /*
  271.  * parse_expr - parses expression consisting of identifiers and logical
  272.  * operators; return TRUE if expression is true (identifier defined => true);
  273.  * FALSE if false; EXPR_ERR if syntax error in expression
  274.  */
  275. #ifdef PROTOS
  276. int parse_expr(char *pbuf)
  277. #else
  278. int parse_expr(pbuf)
  279.     char *pbuf;
  280. #endif
  281. {
  282.     OPERAND opd_stack[MAX_OP];    /* operand stack - TRUE/FALSE values */
  283.     OPERATOR opr_stack[MAX_OP];    /* operator stack - precedence | op */
  284.     int value, token, plevel, prec, result, npop, opr, opd, prev_token, op;
  285.  
  286.     plevel = 0;            /* paren nesting level */
  287.     opd = opr = -1;            /* indices of stack tops */
  288.     prev_token = TK_STARTINPUT;    /* to detect null expressions */
  289.  
  290.     if (DEBUG(DEBUG_PP))
  291.         FPR(stderr, "evaluating expression '%s'\n", pbuf);
  292.     do {
  293.         pbuf = next_token(pbuf, &token, &value);
  294.  
  295.         /* check that the current token may follow the previous one */
  296.         if (! IS_LEGAL(token, prev_token))
  297.             return EXPR_ERR;
  298.  
  299.         switch(token) {
  300.  
  301.         case TK_IDENT:        /* identifier => 1 if def, 0 if not */
  302.             opd_stack[++opd] = value != PP_SYM_UNDEF;
  303.             break;
  304.  
  305.         case TK_LPAREN:        /* left paren - bump nesting level */
  306.             ++plevel;
  307.             break;
  308.  
  309.         case TK_RPAREN:        /* right paren - decrement nesting */
  310.             if (--plevel < 0)
  311.                 return EXPR_ERR;
  312.             break;
  313.  
  314.         case TK_ENDINPUT:    /* end-of-input - treat as operator */
  315.             if (prev_token == TK_STARTINPUT)
  316.                 return FALSE;    /* null expr => FALSE */
  317.             /* fall through */
  318.  
  319.         case TK_UNARYOP:
  320.         case TK_BINARYOP:
  321.  
  322.             /* get precedence of operator, adjusting for paren
  323.              * nesting (TK_ENDINPUT has the lowest precedence
  324.              * of all, to unwind operand/operator stacks at end)
  325.              */
  326.  
  327.             prec = token == TK_ENDINPUT ? ENDINPUT_PREC :
  328.                 (plevel * PAREN_PREC) + opr_tbl[value].prec;
  329.  
  330.             /* pop (and perform) any equal- or higher-precedence
  331.              * operators on operator stack: extract operator,
  332.              * check for operand stack underflow, execute
  333.              * operator, adjust operand stack height and place
  334.              * result of operator on top
  335.              */
  336.  
  337.             for ( ;
  338.                  opr >= 0 && PREC(opr_stack[opr]) >= prec;
  339.                  opr--) {
  340.                 op = OPCODE(opr_stack[opr]);
  341.                 npop = opr_tbl[op].type == TK_UNARYOP ? 0 : 1;
  342.                 if (opd < npop)
  343.                     return EXPR_ERR;
  344.                 result = (*opr_tbl[op].pfcn)(opd_stack + opd);
  345.                 opd_stack[opd -= npop] = result;
  346.             }
  347.  
  348.             /* push operator (if any) onto stack */
  349.  
  350.             if (token != TK_ENDINPUT)
  351.                 opr_stack[++opr] = MAKE_OPR(prec, value);
  352.  
  353.             break;
  354.  
  355.         default:        /* should never get here */
  356.             return EXPR_ERR;
  357.             break;
  358.  
  359.         }
  360.  
  361.         prev_token = token;
  362.  
  363.     } while (token != TK_ENDINPUT);
  364.  
  365.     /* done - check for dangling parens, and leftover operand/operators */
  366.  
  367.     if (DEBUG(DEBUG_PP))
  368.         FPR(stderr, "evaluated to %s\n", opd_stack[0] ? "TRUE" : "FALSE");
  369.     return plevel != 0 || opd != 0 || opr != -1 ?
  370.         EXPR_ERR :        /* leftover junk - return error */
  371.         opd_stack[0];        /* all OK - return final value */
  372. }
  373.  
  374.