home *** CD-ROM | disk | FTP | other *** search
/ Simtel MSDOS 1992 September / Simtel20_Sept92.cdr / msdos / ddjmag / ddj8912.arc / STEVENS.LST < prev    next >
File List  |  1989-10-30  |  8KB  |  322 lines
  1. _C PROGRAMMING COLUMN_
  2. by Al Stevens
  3.  
  4. [LISTING ONE]
  5.  
  6. /* ----------- textsrch.h ---------- */
  7.  
  8. #define MXTOKS 25       /*  maximum number of tokens */
  9.  
  10. #define OK    0
  11. #define ERROR !OK
  12.  
  13. struct postfix  {
  14.     char pfix;      /* tokens in postfix notation */
  15.     char *pfixop;   /* operand strings            */
  16. };
  17.  
  18. extern struct postfix pftokens[];
  19. extern int xp_offset;
  20.  
  21. /* --------- expression token values ---------- */
  22. #define TERM     0
  23. #define OPERAND 'O'
  24. #define AND     '&'
  25. #define OR      '|'
  26. #define OPEN    '('
  27. #define CLOSE   ')'
  28. #define NOT     '!'
  29. #define QUOTE   '"'
  30.  
  31. /* ---------- textsrch prototypes ---------- */
  32. struct postfix *lexical_scan(char *expr);
  33.  
  34.  
  35.  
  36.  
  37. [LISTING TWO]
  38.  
  39. /* ---------- express.c ----------- */
  40.  
  41. #include <stdlib.h>
  42. #include <string.h>
  43. #include <ctype.h>
  44. #include "textsrch.h"
  45.  
  46. /*
  47.  * Parse a search expression into a valid postfix token stream.
  48.  * The input expression has this form:
  49.  *   <expr>   := <ident>
  50.  *               <ident> <op> <expr>
  51.  *               NOT <expr>
  52.  *               (<expr>)
  53.  *   <op>     := AND
  54.  *               OR
  55.  *   <ident>  := <character>
  56.  *               <character> <ident>
  57.  *               "<phrase>"
  58.  *   <phrase> := <ident>
  59.  *               <ident> <space> <phrase>
  60.  */
  61.  
  62. #define iswhite(c)      (c < 33 && c > 0)
  63. #define isparen(c)      (c == OPEN || c == CLOSE)
  64. #define isop(c)         (c == AND || c == OR)
  65. #define ischaracter(c)  (!isparen(c) && \
  66.                         !isop(c)     && \
  67.                         c != TERM    && \
  68.                         !iswhite(c)  && \
  69.                         c != QUOTE)
  70.  
  71. /* ----------- prototypes --------------- */
  72. static int getword(char *expr);
  73. static int gettoken(char *expr);
  74. static int expression(char *expr);
  75. static void postfix(void);
  76. static int isp(int tok);
  77. static int icp(int tok);
  78. static void poststack(void);
  79.  
  80. int xp_offset = 0;              /* offset into the expression */
  81. static char word[50];           /* word from the expression   */
  82.  
  83. static char tokens[MXTOKS+1];   /* tokens in infix notation   */
  84. static char *operands[MXTOKS];  /* operand strings            */
  85. static int token_ptr = 0;
  86.  
  87. static char stack[MXTOKS];      /* stack for tokens           */
  88. static char *stopr[MXTOKS];     /* operand strings            */
  89. static int top = 0;
  90.  
  91. struct postfix pftokens[MXTOKS];
  92. static int pf = 0;
  93.  
  94. /* ------ analyze the expression for valid syntax ----------*/
  95. struct postfix *lexical_scan(char *expr)
  96. {
  97.     token_ptr = xp_offset = 0;
  98.     if (expression(expr) == ERROR)
  99.         return NULL;
  100.     else if (gettoken(expr) != TERM)
  101.         return NULL;
  102.     postfix();
  103.     return pftokens;
  104. }
  105.  
  106. /* ---------- analyze an element of the expression ---------- */
  107. static int expression(char *expr)
  108. {
  109.     int tok;
  110.  
  111.     tok = gettoken(expr);
  112.     switch (tok)    {
  113.         case OPEN:
  114.             if (expression(expr) == ERROR)
  115.                 return ERROR;
  116.             if ((tok = gettoken(expr)) != CLOSE)
  117.                 return ERROR;
  118.             break;
  119.         case NOT:
  120.             if (expression(expr) == ERROR)
  121.                 return ERROR;
  122.             break;
  123.         case OPERAND:
  124.             break;
  125.         default:
  126.             return ERROR;
  127.     }
  128.     tok = gettoken(expr);
  129.     switch (tok)    {
  130.         case TERM:
  131.             return OK;
  132.         case AND:
  133.         case OR:
  134.             return expression(expr);
  135.         case CLOSE:
  136.             --token_ptr;
  137.             --xp_offset;
  138.             return OK;
  139.         default:
  140.             break;
  141.     }
  142.     return ERROR;
  143. }
  144.  
  145. /* ------- extract the next token from the expression ------- */
  146. static int gettoken(char *expr)
  147. {
  148.     char tok;
  149.  
  150.     operands[token_ptr] = 0;
  151.     if ((tok = getword(expr))== OPERAND)    {
  152.         operands[token_ptr] = malloc(strlen(word) + 1);
  153.         strcpy(operands[token_ptr], word);
  154.     }
  155.     tokens[token_ptr++] = tok;
  156.     return tok;
  157. }
  158.  
  159. /* ------- extract a word, operator, parenthesis,
  160.            or terminator from the expression ------------- */
  161. static int getword(char *expr)
  162. {
  163.     int w = 0;
  164.  
  165.     /* ------- bypass white space -------- */
  166.     while (iswhite(expr[xp_offset]))
  167.         xp_offset++;
  168.     switch (expr[xp_offset])    {
  169.         case OPEN:
  170.         case CLOSE:
  171.             return expr[xp_offset++];
  172.         case TERM:
  173.             return TERM;
  174.         case QUOTE:
  175.             while (expr[++xp_offset] != QUOTE)  {
  176.                 if (w == 50)
  177.                     return ERROR;
  178.                 word[w++] = tolower(expr[xp_offset]);
  179.             }
  180.             xp_offset++;
  181.             word[w] = '\0';
  182.             return OPERAND;
  183.         default:
  184.             while (ischaracter(expr[xp_offset]))    {
  185.                 if (w == 50)
  186.                     return ERROR;
  187.                 word[w++] = tolower(expr[xp_offset]);
  188.                 xp_offset++;
  189.             }
  190.             word[w] = '\0';
  191.             if (strcmp(word, "and") == 0)
  192.                 return AND;
  193.             else if (strcmp(word, "or") == 0)
  194.                 return OR;
  195.             else if (strcmp(word, "not") == 0)
  196.                 return NOT;
  197.             return OPERAND;
  198.     }
  199. }
  200.  
  201. /* - convert the expression from infix to postfix notation - */
  202. static void postfix(void)
  203. {
  204.     char tok = '*';
  205.  
  206.     top = token_ptr = pf = 0;
  207.     stack[top] = '*';
  208.     while (tok != TERM) {
  209.         switch (tok = tokens[token_ptr])    {
  210.             case OPERAND:
  211.                 pftokens[pf].pfix = tok;
  212.                 pftokens[pf].pfixop = operands[token_ptr];
  213.                 pf++;
  214.                 break;
  215.             case NOT:
  216.             case OPEN:
  217.             case AND:
  218.             case OR:
  219.                 while (isp(stack[top]) >= icp(tok))
  220.                     poststack();
  221.                 stack[++top] = tok;
  222.                 break;
  223.             case CLOSE:
  224.                 while (stack[top] != OPEN)
  225.                     poststack();
  226.                 --top;
  227.                 break;
  228.             case TERM:
  229.                 while (top)
  230.                     poststack();
  231.                 pftokens[pf++].pfix = tok;
  232.                 break;
  233.         }
  234.         token_ptr++;
  235.     }
  236. }
  237.  
  238. static int isp(int tok)
  239. {
  240.     return ((tok == OPEN) ?  0 :
  241.             (tok == '*')  ? -1 :
  242.             (tok == NOT)  ?  2 :
  243.                              1  );
  244. }
  245.  
  246. static int icp(int tok)
  247. {
  248.     return ((tok == OPEN) ?  4 :
  249.             (tok == NOT)  ?  2 :
  250.                              1  );
  251. }
  252.  
  253. /* --- remove a token from the stack, put it into postfix --- */
  254. static void poststack(void)
  255. {
  256.     pftokens[pf].pfix = stack[top];
  257.     pftokens[pf].pfixop = stopr[top];
  258.     --top;
  259.     pf++;
  260. }
  261.  
  262.  
  263.  
  264.  
  265. [LISTING THREE]
  266.  
  267. /* ----------- testexpr.c ------------- */
  268.  
  269. /*
  270.  * A program to test the TEXTSRCH expression analyzer
  271.  */
  272.  
  273. #include <stdio.h>
  274. #include <process.h>
  275. #include <string.h>
  276. #include "textsrch.h"
  277.  
  278. static void disp_token(struct postfix *pf);
  279.  
  280. void main(void)
  281. {
  282.     char expr[80];
  283.  
  284.     do  {
  285.         /* ----- read the expression from the console ------ */
  286.         printf("\nEnter the search expression:\n");
  287.         gets(expr);
  288.         if (*expr)  {
  289.             /* --- scan for errors and convert to postfix --- */
  290.             if (lexical_scan(expr) == NULL) {
  291.                 while(xp_offset--)
  292.                     putchar(' ');
  293.                 putchar('^');
  294.                 printf("\nSyntax Error");
  295.                 exit(1);
  296.             }
  297.  
  298.             /* ------ display the postfix tokens ------ */
  299.             printf("\nToken");
  300.             printf("\n--------------");
  301.             disp_token(pftokens);
  302.             printf("\n--------------");
  303.         }
  304.     } while (*expr);
  305. }
  306.  
  307. static void disp_token(struct postfix *pf)
  308. {
  309.     if (pf->pfix != TERM)   {
  310.         disp_token(pf+1);
  311.         printf("\n %s", pf->pfix == AND  ? "<and>" :
  312.                         pf->pfix == OR   ? "<or>"  :
  313.                         pf->pfix == NOT  ? "<not>" :
  314.                         pf->pfixop);
  315.     }
  316. }
  317.  
  318.  
  319.  
  320.  
  321.  
  322.