home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / pccts.zip / pccts / dlg / dlg_p.g < prev    next >
Text File  |  1994-03-31  |  11KB  |  419 lines
  1. /*  This is the parser for the dlg
  2.  *  This is a part of the Purdue Compiler Construction Tool Set
  3.  *
  4.  * SOFTWARE RIGHTS
  5.  *
  6.  * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
  7.  * Set (PCCTS) -- PCCTS is in the public domain.  An individual or
  8.  * company may do whatever they wish with source code distributed with
  9.  * PCCTS or the code generated by PCCTS, including the incorporation of
  10.  * PCCTS, or its output, into commerical software.
  11.  * 
  12.  * We encourage users to develop software with PCCTS.  However, we do ask
  13.  * that credit is given to us for developing PCCTS.  By "credit",
  14.  * we mean that if you incorporate our source code into one of your
  15.  * programs (commercial product, research project, or otherwise) that you
  16.  * acknowledge this fact somewhere in the documentation, research report,
  17.  * etc...  If you like PCCTS and have developed a nice tool with the
  18.  * output, please mention that you developed it using PCCTS.  In
  19.  * addition, we ask that this header remain intact in our source code.
  20.  * As long as these guidelines are kept, we expect to continue enhancing
  21.  * this system and expect to make other tools available as they are
  22.  * completed.
  23.  *
  24.  * DLG 1.20
  25.  * Will Cohen
  26.  * With mods by Terence Parr; AHPCRC, University of Minnesota
  27.  * 1989-1994
  28.  */
  29.  
  30. #header    <<
  31. #include <ctype.h>
  32. #include "dlg.h"
  33. #ifdef MEMCHK
  34. #include "trax.h"
  35. #endif
  36. >>
  37.  
  38. <<
  39. int    action_no = 0;       /* keep track of actions outputed */
  40. int    nfa_allocated = 0; /* keeps track of number of nfa nodes */
  41. nfa_node **nfa_array = NULL;/* root of binary tree that stores nfa array */
  42. nfa_node nfa_model_node;   /* model to initialize new nodes */
  43. set    used_chars;       /* used to label trans. arcs */
  44. set    used_classes;       /* classes or chars used to label trans. arcs */
  45. set    normal_chars;       /* mask to get rid elements that aren't used
  46.                   in set */
  47. int    flag_paren = FALSE;
  48. int    flag_brace = FALSE;
  49. int    mode_counter = 0;  /* keep track of number of %%names */
  50.  
  51. >>
  52.  
  53. #lexaction <<
  54. int    func_action;        /* should actions be turned into functions?*/
  55. int    lex_mode_counter = 0;    /* keeps track of the number of %%names */
  56. >>
  57.  
  58. #token "[\r\t\ ]+"    << zzskip(); >>            /* Ignore white */
  59. #token "[\n]"        << zzline++; zzskip(); >>    /* Track Line # */
  60. #token L_EOF        "\@"
  61. #token PER_PER        "\%\%"
  62. #token NAME_PER_PER    "\%\%[a-zA-Z_][a-zA-Z0-9_]*"
  63.         << p_mode_def(&zzlextext[2],lex_mode_counter++); >>
  64. #token ACTION        "\<\<"
  65.         << if (func_action)
  66.             fprintf(OUT,"\n%s %sact%d()\n{ ",
  67.                     gen_cpp?"TokenType":"static void",
  68.                     gen_cpp?ClassName("::"):"", ++action_no);
  69.            zzmode(ACT); zzskip();
  70.         >>
  71. #token GREAT_GREAT    "\>\>"
  72. #token L_BRACE        "\{"
  73. #token R_BRACE        "\}"
  74. #token L_PAR        "\("
  75. #token R_PAR        "\)"
  76. #token L_BRACK        "\["
  77. #token R_BRACK        "\]"
  78. #token ZERO_MORE    "\*"
  79. #token ONE_MORE        "\+"
  80. #token OR        "\|"
  81. #token RANGE        "\-"
  82. #token NOT        "\~"
  83. #token OCTAL_VALUE "\\0[0-7]*"        
  84.     << {int t; sscanf(&zzlextext[1],"%o",&t); zzlextext[0] = t;}>>
  85. #token HEX_VALUE   "\\0[Xx][0-9a-fA-F]+"
  86.     << {int t; sscanf(&zzlextext[3],"%x",&t); zzlextext[0] = t;}>>
  87. #token DEC_VALUE   "\\[1-9][0-9]*"
  88.     << {int t; sscanf(&zzlextext[1],"%d",&t); zzlextext[0] = t;}>>
  89. #token TAB        "\\t"        << zzlextext[0] = '\t';>>
  90. #token NL        "\\n"        << zzlextext[0] = '\n';>>
  91. #token CR        "\\r"        << zzlextext[0] = '\r';>>
  92. #token BS        "\\b"        << zzlextext[0] = '\b';>>
  93. /* NOTE: this takes ANYTHING after the \ */
  94. #token LIT        "\\~[tnrb]"    << zzlextext[0] = zzlextext[1];>>
  95. /* NOTE: this takes ANYTHING that doesn't match the other tokens */
  96. #token REGCHAR        "~[\\]"
  97.  
  98.  
  99. grammar        :   << p_head(); p_class_hdr(); func_action = FALSE;>> (ACTION)*
  100.             <<if ( gen_cpp ) p_includes();>>
  101.             start_states
  102.             << func_action = FALSE; p_tables(); p_tail(); >>
  103.             (ACTION)* "@"
  104.         ;
  105.  
  106. start_states    : ( PER_PER do_conversion
  107.           | NAME_PER_PER do_conversion (NAME_PER_PER do_conversion)*)
  108.             PER_PER 
  109.         ;
  110.  
  111. do_conversion    : <<new_automaton_mode(); func_action = TRUE;>>
  112.             rule_list
  113.             <<
  114.                 dfa_class_nop[mode_counter] =
  115.                     relabel($1.l,comp_level);
  116.                 if (comp_level)
  117.                     p_shift_table(mode_counter);
  118.                 dfa_basep[mode_counter] = dfa_allocated+1;
  119.                 make_dfa_model_node(dfa_class_nop[mode_counter]);
  120.                 nfa_to_dfa($1.l);
  121.                 ++mode_counter;
  122.                     func_action = FALSE;
  123. #ifdef HASH_STAT
  124.                 fprint_hash_stats(stderr);
  125. #endif
  126.             >>
  127.         ;
  128.  
  129. rule_list    : rule <<$$.l=$1.l; $$.r=$1.r;>>
  130.             (rule
  131.                 <<{nfa_node *t1;
  132.                    t1 = new_nfa_node();
  133.                    (t1)->trans[0]=$$.l;
  134.                    (t1)->trans[1]=$1.l;
  135.                    /* all accept nodes "dead ends" */
  136.                    $$.l=t1; $$.r=NULL;
  137.                    }
  138.                 >>
  139.             )*
  140.         | /* empty */
  141.             <<$$.l = new_nfa_node(); $$.r = NULL;
  142.                warning("no regular expressions", zzline);
  143.             >>
  144.         ;
  145.  
  146. rule        : reg_expr ACTION
  147.             <<$$.l=$1.l; $$.r=$1.r; ($1.r)->accept=action_no;>>
  148.         | ACTION
  149.             <<$$.l = NULL; $$.r = NULL;
  150.               error("no expression for action  ", zzline);
  151.             >>
  152.         ;
  153.  
  154. reg_expr    : and_expr <<$$.l=$1.l; $$.r=$1.r;>>
  155.             (OR and_expr 
  156.                 <<{nfa_node *t1, *t2;
  157.                    t1 = new_nfa_node(); t2 = new_nfa_node();
  158.                    (t1)->trans[0]=$$.l;
  159.                    (t1)->trans[1]=$2.l;
  160.                    ($$.r)->trans[1]=t2;
  161.                    ($2.r)->trans[1]=t2;
  162.                    $$.l=t1; $$.r=t2;
  163.                   }
  164.                 >>
  165.             )*
  166.         ;
  167.  
  168. and_expr    : repeat_expr <<$$.l=$1.l; $$.r=$1.r;>>
  169.             (repeat_expr <<($$.r)->trans[1]=$1.l; $$.r=$1.r;>>)*
  170.         ;
  171.  
  172. repeat_expr    : expr <<$$.l=$1.l; $$.r=$1.r;>>
  173.             { ZERO_MORE
  174.             <<{    nfa_node *t1,*t2;
  175.                 ($$.r)->trans[0] = $$.l;
  176.                 t1 = new_nfa_node(); t2 = new_nfa_node();
  177.                 t1->trans[0]=$$.l;
  178.                 t1->trans[1]=t2;
  179.                 ($$.r)->trans[1]=t2;
  180.                 $$.l=t1;$$.r=t2;
  181.               }
  182.             >>
  183.             | ONE_MORE
  184.             <<($$.r)->trans[0] = $$.l;>>
  185.             }
  186.         | ZERO_MORE
  187.             << error("no expression for *", zzline);>>
  188.         | ONE_MORE
  189.             << error("no expression for +", zzline);>>
  190.         ;
  191.  
  192. expr        : << $$.l = new_nfa_node(); $$.r = new_nfa_node(); >>
  193.           L_BRACK atom_list R_BRACK
  194.             <<
  195.                 ($$.l)->trans[0] = $$.r;
  196.                 ($$.l)->label = set_dup($2.label);
  197.                 set_orin(&used_chars,($$.l)->label);
  198.             >>
  199.         | NOT L_BRACK atom_list R_BRACK
  200.             <<
  201.                 ($$.l)->trans[0] = $$.r;
  202.                 ($$.l)->label = set_dif(normal_chars,$3.label);
  203.                 set_orin(&used_chars,($$.l)->label);
  204.             >>
  205.         | L_PAR reg_expr R_PAR
  206.             <<
  207.                 ($$.l)->trans[0] = $2.l;
  208.                 ($2.r)->trans[1] = $$.r;
  209.             >>
  210.         | L_BRACE reg_expr R_BRACE
  211.             <<
  212.                 ($$.l)->trans[0] = $2.l;
  213.                 ($$.l)->trans[1] = $$.r;
  214.                 ($2.r)->trans[1] = $$.r;
  215.             >>
  216.         | atom
  217.             <<
  218.                 ($$.l)->trans[0] = $$.r;
  219.                 ($$.l)->label = set_dup($1.label);
  220.                 set_orin(&used_chars,($$.l)->label);
  221.             >>
  222.         ;
  223.  
  224. atom_list    : << set_free($$.label); >>
  225.             (near_atom <<set_orin(&($$.label),$1.label);>>)*
  226.         ;
  227.  
  228. near_atom    : << register int i;
  229.              register int i_prime;
  230.           >>
  231.           anychar
  232.             <<$$.letter=$1.letter; $$.label=set_of($1.letter);
  233.             i_prime = $1.letter + MIN_CHAR;
  234.             if (case_insensitive && islower(i_prime))
  235.                 set_orel(toupper(i_prime)-MIN_CHAR,
  236.                     &($$.label));
  237.             if (case_insensitive && isupper(i_prime))
  238.                  set_orel(tolower(i_prime)-MIN_CHAR,
  239.                     &($$.label));
  240.             >>
  241.             { RANGE anychar 
  242.                 << if (case_insensitive){
  243.                     i_prime = $$.letter+MIN_CHAR;
  244.                     $$.letter = (islower(i_prime) ?
  245.                         toupper(i_prime) : i_prime)-MIN_CHAR;
  246.                     i_prime = $2.letter+MIN_CHAR;
  247.                     $2.letter = (islower(i_prime) ?
  248.                         toupper(i_prime) : i_prime)-MIN_CHAR;
  249.                    }
  250.                    /* check to see if range okay */
  251.                    if ($$.letter > $2.letter){
  252.                       error("invalid range  ", zzline);
  253.                    }
  254.                    for (i=$$.letter; i<= $2.letter; ++i){
  255.                     set_orel(i,&($$.label));
  256.                     i_prime = i+MIN_CHAR;
  257.                     if (case_insensitive && islower(i_prime))
  258.                         set_orel(toupper(i_prime)-MIN_CHAR,
  259.                             &($$.label));
  260.                     if (case_insensitive && isupper(i_prime))
  261.                          set_orel(tolower(i_prime)-MIN_CHAR,
  262.                             &($$.label));
  263.                     }
  264.                 >>
  265.             }
  266.         ;
  267.  
  268. atom        : << register int i_prime;>>
  269.           anychar
  270.           <<$$.label = set_of($1.letter);
  271.             i_prime = $1.letter + MIN_CHAR;
  272.             if (case_insensitive && islower(i_prime))
  273.             set_orel(toupper(i_prime)-MIN_CHAR,
  274.                 &($$.label));
  275.             if (case_insensitive && isupper(i_prime))
  276.              set_orel(tolower(i_prime)-MIN_CHAR,
  277.                 &($$.label));
  278.           >>
  279.         ;
  280.  
  281. anychar        : REGCHAR    <<$$.letter = $1.letter - MIN_CHAR;>>
  282.         | OCTAL_VALUE    <<$$.letter = $1.letter - MIN_CHAR;>>
  283.         | HEX_VALUE    <<$$.letter = $1.letter - MIN_CHAR;>>
  284.         | DEC_VALUE    <<$$.letter = $1.letter - MIN_CHAR;>>
  285.         | TAB        <<$$.letter = $1.letter - MIN_CHAR;>>
  286.         | NL        <<$$.letter = $1.letter - MIN_CHAR;>>
  287.         | CR        <<$$.letter = $1.letter - MIN_CHAR;>>
  288.         | BS        <<$$.letter = $1.letter - MIN_CHAR;>>
  289.         | LIT        <<$$.letter = $1.letter - MIN_CHAR;>>
  290.         /* NOTE: LEX_EOF is ALWAYS shifted to 0 = MIN_CHAR - MIN_CHAR*/
  291.         | L_EOF        <<$$.letter = 0;>>
  292.         ;
  293.  
  294. <</* empty action */>>
  295.  
  296. #lexclass ACT
  297. #token "@"    << error("unterminated action", zzline); zzmode(START); >>
  298. #token ACTION "\>\>"
  299.         << if (func_action) fprintf(OUT,"}\n\n");
  300.            zzmode(START);
  301.         >>
  302. #token "\>"        << putc(zzlextext[0], OUT); zzskip(); >>
  303. #token "\\\>"        << putc('>', OUT); zzskip(); >>
  304. #token "\\"        << putc('\\', OUT); zzskip(); >>
  305. #token "\n"        << putc(zzlextext[0], OUT); ++zzline; zzskip(); >>
  306. #token "~[\>\\@\n]+"    << fprintf(OUT, "%s", &(zzlextext[0])); zzskip(); >>
  307.  
  308. <<
  309. /* adds a new nfa to the binary tree and returns a pointer to it */
  310. nfa_node *new_nfa_node()
  311. {
  312.     register nfa_node *t;
  313.     static int nfa_size=0;    /* elements nfa_array[] can hold */
  314.  
  315.     ++nfa_allocated;
  316.     if (nfa_size<=nfa_allocated){
  317.         /* need to redo array */
  318.         if (!nfa_array){
  319.             /* need some to do inital allocation */
  320.             nfa_size=nfa_allocated+NFA_MIN;
  321.             nfa_array=(nfa_node **) malloc(sizeof(nfa_node*)*
  322.                 nfa_size);
  323.         }else{
  324.             /* need more space */
  325.             nfa_size=2*(nfa_allocated+1);
  326.             nfa_array=(nfa_node **) realloc(nfa_array, 
  327.                 sizeof(nfa_node*)*nfa_size);
  328.         }
  329.     }
  330.     /* fill out entry in array */
  331.     t = (nfa_node*) malloc(sizeof(nfa_node));
  332.     nfa_array[nfa_allocated] = t;
  333.     *t = nfa_model_node;
  334.     t->node_no = nfa_allocated;
  335.     return t;
  336. }
  337.  
  338.  
  339. /* initialize the model node used to fill in newly made nfa_nodes */
  340. void
  341. make_nfa_model_node()
  342. {
  343.     nfa_model_node.node_no = -1; /* impossible value for real nfa node */
  344.     nfa_model_node.nfa_set = 0;
  345.     nfa_model_node.accept = 0;   /* error state default*/
  346.     nfa_model_node.trans[0] = NULL;
  347.     nfa_model_node.trans[1] = NULL;
  348.     nfa_model_node.label = empty;
  349. }
  350. >>
  351.  
  352. <<
  353. #ifdef DEBUG
  354.  
  355. /* print out the pointer value and the node_number */
  356. fprint_dfa_pair(f, p)
  357. FILE *f;
  358. nfa_node *p;
  359. {
  360.     if (p){
  361.         fprintf(f, "%x (%d)", p, p->node_no);
  362.     }else{
  363.         fprintf(f, "(nil)");
  364.     }
  365. }
  366.  
  367. /* print out interest information on a set */
  368. fprint_set(f,s)
  369. FILE *f;
  370. set s;
  371. {
  372.     unsigned int *x;
  373.  
  374.     fprintf(f, "n = %d,", s.n);
  375.     if (s.setword){
  376.         fprintf(f, "setword = %x,   ", s.setword);
  377.         /* print out all the elements in the set */
  378.         x = set_pdq(s);
  379.         while (*x!=nil){
  380.             fprintf(f, "%d ", *x);
  381.             ++x;
  382.         }
  383.     }else{
  384.         fprintf(f, "setword = (nil)");
  385.     }
  386. }
  387.  
  388. /* code to be able to dump out the nfas
  389.     return 0 if okay dump
  390.     return 1 if screwed up
  391.  */
  392. int dump_nfas(first_node, last_node)
  393. int first_node;
  394. int last_node;
  395. {
  396.     register int i;
  397.     nfa_node *t;
  398.  
  399.     for (i=first_node; i<=last_node; ++i){
  400.         t = NFA(i);
  401.         if (!t) break;
  402.         fprintf(stderr, "nfa_node %d {\n", t->node_no);
  403.         fprintf(stderr, "\n\tnfa_set = %d\n", t->nfa_set);
  404.         fprintf(stderr, "\taccept\t=\t%d\n", t->accept);
  405.         fprintf(stderr, "\ttrans\t=\t(");
  406.         fprint_dfa_pair(stderr, t->trans[0]);
  407.         fprintf(stderr, ",");
  408.         fprint_dfa_pair(stderr, t->trans[1]);
  409.         fprintf(stderr, ")\n");
  410.         fprintf(stderr, "\tlabel\t=\t{ ");
  411.         fprint_set(stderr, t->label);
  412.         fprintf(stderr, "\t}\n");
  413.         fprintf(stderr, "}\n\n");
  414.     }
  415.     return 0;
  416. }
  417. #endif
  418. >>
  419.