home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / compiler / 1481 < prev    next >
Encoding:
Text File  |  1992-08-31  |  4.8 KB  |  129 lines
  1. Path: sparky!uunet!europa.asd.contel.com!darwin.sura.net!wupost!uwm.edu!rutgers!faatcrl!iecc!compilers-sender
  2. From: sells@cs.umn.edu (Chris Sells)
  3. Newsgroups: comp.compilers
  4. Subject: Compiler Construction Using OO Techniques
  5. Keywords: C++, yacc, OOP
  6. Message-ID: <92-08-181@comp.compilers>
  7. Date: 31 Aug 92 02:35:41 GMT
  8. Sender: compilers-sender@iecc.cambridge.ma.us
  9. Reply-To: sells@cs.umn.edu (Chris Sells)
  10. Organization: Spanlink Communications
  11. Lines: 115
  12. Approved: compilers@iecc.cambridge.ma.us
  13.  
  14. Compiler Construction Using OO Techniques: A Case Study
  15.  
  16. I am interested in pursuing a Master's Thesis by expanding the currently
  17. available compiler generation tools (i.e. yacc) using object-oriented
  18. techniques.
  19.  
  20. I've been doing research on the net w/ this topic in mind and have come up
  21. w/ some good references, including some requests for what I'd like to do,
  22. but have not come up w/ anyone who's done what I propose.
  23.  
  24. The first thing I want to pursue is to generate parse classes
  25. automatically from a yacc grammar. For example, the following yacc code is
  26. present in just about every compiler known to man:
  27.  
  28. prog    : stmt prog        {$$ = new prog($1,$2);}
  29.         | stmt            /* default {$$ = $1;} */
  30.         ;
  31.  
  32. stmt    : expr '\n'        {$$ = new stmt($1,$2);}
  33.         | 'q'            {$$ = new constant($1);}
  34.         ; 
  35.  
  36. expr    : expr '+' term    {$$ = new expr($1,new constant($2),$3);}
  37.         | expr '-' term    {$$ = new expr($1,new constant($2),$3);}
  38.         | term            /* default {$$ = $1;} */
  39.         ;
  40.  
  41. term    : term '*' factor    {$$ = new term($1,new constant($2),$3);} 
  42.         | term '/' factor {$$ = new term($1,new constant($2),$3);}
  43.         | factor            /* default ($$ = $1;} */
  44.         ;
  45.  
  46. factor    : primary '^' factor    {$$ = new factor($1,new constant($2),$3);}
  47.         | primary            /* default {$$ = $1;} */
  48.         ;
  49.  
  50. primary    : '(' expr ')'    {$$ = new primary($1,new constant($2),$3};}
  51.         | integer        /* default {$$ = $1;} */
  52.         ;
  53.  
  54. From this, my 'generator' would read the yacc grammar and derive
  55. sub-classes (from a parent 'symbol') for prog, stmt, expr, term, factor,
  56. and primary and build the proper relationships between them to allow for
  57. the trivial construction of a parse tree (as shown above). All that it
  58. would take to generate code would be 'prog.emit()', once each object's
  59. 'emit' method was developed (that would still have to be done by hand).
  60. Likewise, to execute, 'prog.exec()' or to pretty-print,
  61. 'prog.pretty_print()'.
  62.  
  63. The beauty of it is how well the tree-structure of OO maps to the
  64. tree-structure of the internal representation of a program, i.e. a
  65. parse-tree.
  66.  
  67. My parse-tree generater would, for each non-terminal, create a sub-class
  68. of 'symbol' w/ the correct constructors (i.e. one for each rule). The
  69. instance then contains the actual arguments passed (treated as children in
  70. the tree).  The 'emit' method would then be coded, by hand, to generate
  71. code for each possible rule for the class. For example,
  72.  
  73. term    : term '*' factor  {$$ = new term($1,new constant($2),$3);} 
  74.         | term '/' factor     {$$ = new term($1,new constant($2),$3);}
  75.         | factor
  76.  
  77. would generate (not worried about syntax, feel free to correct, it's
  78. 1:30am):
  79.  
  80. class term:public Symbol {
  81.         char *name;                /* type string or constant value */
  82.         int token;                 /* token value */
  83.         SymbolList *arglist;       /* list of arguments */
  84. public:
  85.         int token() { return token; }
  86.         const char* name() { return name; }
  87.         Symbol& arg(int index) { return arglist->element(index); }
  88.         term& emit();
  89.         term& term(term* t,constant* op,factor* f)
  90.         { arglist->add(t)->add(op)->add(f);name="term";token=TERM;return
  91. this;}
  92.         ~term() {arglist->purge();}
  93. }
  94.  
  95. /* knows that it's arguments are a term, an op and a factor */
  96. /* this code written by hand but constructor(s) and destructor auto-coded
  97. */
  98. term& term::emit()
  99. {
  100.         cout << '(';
  101.         arg(0).emit();
  102.         cout << arg(1).type;
  103.         arg(2).emit();
  104.         cout << ')';
  105.  
  106.         return this;
  107. }
  108.  
  109. This 'generator' would be able to handle any grammar that could be
  110. expressed as a yacc grammar. The actual yacc code would be almost trivial,
  111. I think. The compiler constructor would be able to write each 'emit'
  112. method and not have to deal w/ tree construction or traversal.
  113.  
  114. The other areas I wish to involve involve symbols (variables, constants,
  115. arguments, etc) and scopes, but I have less concrete ideas about the
  116. benefits of OO w/ these areas. I plan on building a real-world compiler
  117. based on a C sub-set and to use OO when/where-ever I can.
  118.  
  119. Any ideas, references, comments, criticisms, flames, encouragement, etc.
  120. are more than welcome. Lord knows I rather have my lame ideas corrected
  121. now rather than before the review board. Thanx in advance.
  122.  
  123. | Chris Sells             |
  124. | Spanlink Communications |
  125. | sells@cs.umn.edu        |
  126. -- 
  127. Send compilers articles to compilers@iecc.cambridge.ma.us or
  128. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  129.