home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / os2 / pgen_2 / pg_parse.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-06-04  |  7.2 KB  |  252 lines
  1. /*    PG_PARSE.C
  2.     Copyright (C) 1992    Keith L. Robertson    All Rights Reserved
  3.  
  4.     Implementation of parser.
  5.     Need to add table produced by the PGEN Parser Generator.
  6.  
  7.     Any user of 'parse()' must ensure that the following are defined:
  8.  
  9. 1)    The type  'LEX_INFO', that defines info relevant to token
  10.     lexemes and parser nonterminal symbols.
  11.  
  12. 2)    Global variable  'lexeme' of type LEX_INFO in which the
  13.     lexer returns information related to the token it last saw.
  14.  
  15. 3)    Global variable  'USHORT last_token', which is the token number
  16.     returned by the last call to 'get_token()'.
  17.  
  18. 4)    Function  'USHORT  get_token()', which reads the input stream and
  19.     returns the token it saw, with related information in 'lexeme'.
  20.  
  21. 5)    Procedure  'VOID  log_error (USHORT etype,  CSTRING desc)', which
  22.     prints an error message based on the given error type and
  23.     description.  See EXPR_LEX.H for a description.
  24.  
  25. 6)    Two operations on type  'LEX_INFO', probably through macros:
  26.  
  27.         VOID    set_jumped(LEX_INFO& lex_info, INT value), or
  28.         #define    set_jumped(lex_info,value)
  29.         // Mark 'lex_info' as jumped if 'value' is true,
  30.         //  and as not jumped if 'value' is false.
  31.         // Used by the parser to mark/unmark stack objects.
  32.         INT        was_jumped(LEX_INFO& lex_info), or
  33.         #define    was_jumped(lex_info)
  34.         // Return true if 'lex_info' is marked as jumped.
  35.  
  36.     The lexical analyzer must ensure that 'lexeme' is marked as not jumped.
  37.     The  'LEX_INFO&' sytax above is actually valid C++, not C.
  38.     It means that in the call, you specify the structure to pass without
  39.     the '&' address-of operator, and the pointer is actually passed.
  40.     Therefore, call using  "was_jumped (attr [num])", for example,
  41.     NOT  "was_jumped (& attr [num])".
  42. */
  43. /* Lexer header must go first to define LEX_INFO. */
  44. #include "expr_lex.h"        /* Get token definitions */
  45.       /**** Replace with your lexical analyzer header file. ****/
  46. #include "pg_parse.h"        /* Get type definitions for parse tables */
  47.  
  48. /* If STACK_SIZE is set (nonzero), the stack will be checked    */
  49. /* for overflow each time something is pushed onto it.        */
  50. #define        STACK_SIZE        0
  51.  
  52.  
  53. extern USHORT        state_stack [];
  54. extern LEX_INFO        state_value [];
  55.  
  56. LEX_INFO*    attr;    /* Pass attribute info to semantic actions */
  57.  
  58.  
  59. /* ------------------------------------- */
  60.  
  61. /* Return true if bit 'bitidx' is set in 'bitmap' */
  62. BOOL    bitlookup (USHORT* bitmap,  USHORT bitidx)
  63. {   USHORT    idx = bitidx >> 4;
  64.     USHORT    bmp = 1 << (bitidx & 0xF);
  65.     return  bitmap [idx] & bmp;
  66. }
  67.  
  68. VOID    bitset (USHORT* bitmap,  USHORT bitidx,  BOOL value)
  69. {   USHORT    idx = bitidx >> 4;
  70.     USHORT    bmp = 1 << (bitidx & 0xF);
  71.     if  (! value)    { bitmap [idx] &= ~bmp; }
  72.     else        { bitmap [idx] |=  bmp; }
  73. }
  74.  
  75.  
  76. /* ------------------------------------- */
  77.  
  78. extern ACTION_ITEM    action_list   [];
  79. extern USHORT        action_index  [];
  80.  
  81. static ACTION _near    action (USHORT state,  USHORT next)
  82. {   USHORT    idx = action_index [state];
  83.     ACTION    ANY_action = no_change (0);
  84.     ACTION    act;
  85.     while  (1)  {
  86.     USHORT    tok = action_list [idx].token;
  87.     if  (tok == ANY_TK)  {
  88.         if  (ANY_action != no_change (0))  { act = ANY_action; }
  89.         else    { act = action_list [idx].action; }
  90.         break;
  91.     }
  92.     else if  (tok == next)  {
  93.         act = action_list [idx].action;
  94.         break;
  95.     }
  96.     else if  (tok & BR)  {
  97.         if  (ANY_action == no_change (0))  {
  98.         ANY_action = action_list [idx].action;
  99.         }
  100.         idx = (tok ^ BR);
  101.     }
  102.     else    { ++idx; }
  103.     }
  104.     return  act;
  105. }
  106.  
  107.  
  108. /* ------------------------------------- */
  109.  
  110. extern GOTO_LIST_ITEM    goto_list [];
  111. extern USHORT        goto_index [];
  112.  
  113. static USHORT _near    go_to (USHORT state,  USHORT nonterm)
  114. {   USHORT    idx = goto_index [nonterm];
  115.     while  (1)  {
  116.     USHORT    chkst = goto_list [idx].cur_state;
  117.     if  (chkst == ANY_ST  ||  chkst == state)  { break; }
  118.     ++idx;
  119.     }
  120.     return  goto_list [idx].nxt_state;
  121. }
  122.  
  123.  
  124. /* ------------------------------------- */
  125.  
  126. extern PRODUCTION_INFO    production [];
  127.  
  128. SHORT    top = 0;    /* Index of top state on stack.  Can go negative. */
  129.  
  130. VOID    parse ()
  131. {
  132.     PRODUCTION_INFO*    pr;
  133.     USHORT    next_tok = get_token ();
  134.  
  135.     state_stack [top] = 0;    /* Start in state 0 */
  136.  
  137.     while  (1)  {
  138.     ACTION    act = action (state_stack [top], next_tok);
  139.     USHORT    sec = second_part (act);
  140.  
  141.     switch  (action_part (act))  {
  142.     /* ------------------------------------- */
  143.     case  JUMP_ACTION:
  144.         if  (act == error(0))  {
  145.         /* Token seen was not expected. */
  146.         do  {
  147.             act = action (state_stack [top], ERR_TK);
  148.             if  (action_part (act) == SHIFT_ACTION)    { break; }
  149.             --top;
  150.         }   while  (top >= 0);
  151.         if  (top < 0)  {
  152.             log_error (FATAL, "no error processing available for syntax error.");
  153.         }
  154.         else if  (next_tok == 0)  {
  155.             log_error (FATAL, "premature end of input.");
  156.         }
  157.  
  158.         /* Push to an error state, but don't consume token. */
  159.         state_stack [++top] = second_part (act);
  160.         }
  161.         else  {
  162.         /* An optional nonterminal is being jumped. */
  163.         ++ top;
  164.  
  165.         #if  STACK_SIZE
  166.             if  (STACK_SIZE <= top)  { goto STACK_OVERFLOW; }
  167.         #endif
  168.  
  169.         /* 'sec' is the state being jumped. */
  170.         state_stack [top] = sec;
  171.         /* Mark it as a jumped lexeme. */
  172.         set_jumped (state_value [top], 1);
  173.         }
  174.         break;
  175.  
  176.     /* ------------------------------------- */
  177.     case  REDUCE_ACTION:
  178.         pr = & production [sec];
  179.  
  180.         /* Reset 'top' to point to state beginning the production. */
  181.         /* (An empty production will push a new state on the stack.) */
  182.         top = top - pr->size_m1;
  183.  
  184.         #if  STACK_SIZE
  185.         if  (STACK_SIZE <= top)  { goto  STACK_OVERFLOW; }
  186.         #endif
  187.  
  188.         if  (pr->sem_action)  {
  189.         /* Set up global for semantic action. */
  190.         attr = & (state_value [top]);
  191.         (* pr->sem_action) ();    /* Do semantic action. */
  192.         }
  193.  
  194.         /* Assign the go_to state after reduction */
  195.         state_stack [top] = go_to (state_stack [top-1], pr->nonterm);
  196.  
  197.         if  (was_jumped (state_value [top]))  {
  198.         /* This nonterm is not jumped, but it may have begun with */
  199.         /* a jumped symbol.  Ensure it is marked as not jumped.   */
  200.         set_jumped (state_value [top],  0);
  201.         }
  202.  
  203.         /* Reassign in case sem action called get_token(). */
  204.         next_tok = last_token;
  205.         break;
  206.  
  207.     /* ------------------------------------- */
  208.     case  SHIFT_ACTION:
  209.         ++ top;
  210.  
  211.         #if  STACK_SIZE
  212.         if  (STACK_SIZE <= top)  {
  213.         STACK_OVERFLOW:
  214.             log_error (FATAL, "input too complex.  Parse stack overflow.");
  215.         }
  216.         #endif
  217.  
  218.         state_stack [top] = sec;        /* Push state shifted to */
  219.         state_value [top] = lexeme;        /* Assign token value */
  220.         /* The lexical analyzer must ensure that */
  221.         /* its tokens are marked as not jumped.  */
  222.  
  223.         next_tok = get_token ();        /* Advance input stream */
  224.         break;
  225.  
  226.     /* ------------------------------------- */
  227.     case  ACCEPT_ACTION:
  228.         goto  DONE;        /* Break out of loop. */
  229.  
  230.     /* ------------------------------------- */
  231.     }
  232.     }
  233.     DONE:    ;
  234. }
  235.  
  236.  
  237. /* ------------------------------------- */
  238.  
  239. VOID    skip_to_token (USHORT tok)
  240. {   while  (last_token != tok  &&  last_token != EOS)  {
  241.     get_token ();
  242.     }
  243. }
  244.  
  245. VOID    skip_to_bittok (USHORT* tokmap)
  246. {    /* Set EOS bit so we don't have to check it explicitly. */
  247.     tokmap [0] |= 1;
  248.     while  ( ! bitlookup (tokmap, last_token) )  {
  249.     get_token ();
  250.     }
  251. }
  252.