home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_300 / 357_01 / cstar1.exe / CHANGES.DOC < prev    next >
Text File  |  1991-06-20  |  6KB  |  110 lines
  1. CHANGES.DOC:  How the CSTAR compiler could be improved
  2.  
  3. June 25, 1991
  4.  
  5. If I were to do CSTAR all over again I would make several significant 
  6. changes.  Although I doubt that anyone would want to revise CSTAR a 
  7. whole lot, the following comments would also apply to speeding up a C 
  8. compiler, so they may be of more general interest.
  9.  
  10. What follows are terse hints about how to improve CSTAR's performance 
  11. and coding style.  I would be glad to discuss any of these ideas at greater 
  12. length with you.  Just give me a call.
  13.  
  14. 1.  I would make CSTAR token based, rather than character based.  CSTAR 
  15. spends a lot of time scanning identifiers and copying characters from one 
  16. buffer to another.  (I've measured.) Tokens would be created for identifiers, 
  17. strings, constants and other entities very early on.
  18.  
  19. 2.  I would make CSTAR a multiple pass compiler.  This would 
  20. significantly *increase* its speed because only the first two passes would 
  21. deal with characters.  All other passes would deal with tokens.  The pass 
  22. structure would closely follow the translation phases described in the ANSI 
  23. C Standard.
  24.  
  25. Pass one would be a state machine which read the entire file into memory 
  26. and then gather statistics about the file.  These statistics would be used to 
  27. allocate memory for all strings, identifiers and tokens.  This is an important 
  28. point:  although this initial pass would seem to be pure overhead, it would 
  29. *greatly* simplify later storage allocation.  (No more testing to see if we 
  30. have to allocate more memory.) Storage for all tokens, symbol tables and 
  31. strings (including the spellings of identifiers) would then be allocated *all at 
  32. once.*
  33.  
  34. Pass two would also be a state machine, similar to the first pass.  Pass two 
  35. would simply "fill in" the already allocated storage with all the tokens and 
  36. strings.  Symbol tables would be created in a later pass.  Later passes would 
  37. handle parsing and output.
  38.  
  39. By the way, I am not sure that the initial statistics gathering pass would 
  40. really be a good idea, and it is worth looking into.  If if doesn't turn out it 
  41. could be abandoned without giving up tokens.
  42.  
  43. 3.  I would distinguish between an id's spelling table and its symbol table.  
  44. The spelling table would be created when the id is first tokenized.  It would 
  45. contain information about whether the id could be a reserved word, is 
  46. currently defined as a macro, etc. The symbol table would be used during 
  47. parsing, and would contain a pointer to the spelling table.
  48.  
  49. The name table would have the following format:
  50.  
  51.     attribute byte:  reserved-word and macro-expansion bits and             
  52.     possibly other bits.
  53.  
  54.     length byte:  the length of the identifier.
  55.  
  56.     the spelling of the identifier itself, \0 terminated.
  57.  
  58. 4.  I would have CSTAR look up an id only once, when it is first tokenized.  
  59. All further references to an identifier would be via a pointer to the id's 
  60. spelling table entry which would be part of the id's token.  This will save 
  61. *lots* of time.
  62.  
  63. 5.  I would rewrite the semantic routines.  (Notice all the bug fixes in 
  64. sem.c)  I tried to do all the semantic actions on the fly which turned out to 
  65. be a big mistake.  It would be much better, and probably *faster*, to use 
  66. three passes for doing semantic analysis.  The first pass would build a full 
  67. parse tree for declarations, the second pass would do flow analysis, and a 
  68. third pass would output the program including the Sherlock macros.  
  69. Having a tokenized parse tree helps a lot, since each pass can move back 
  70. and forth in the tree as required.
  71.  
  72. 6.  I would scrap the file copier logic in sysnext.  Although this logic 
  73. works, it is *very* slow since it is used on every input character.  CSTAR 
  74. should produce its output in a final pass after all tokenizing and parsing is 
  75. complete.  That way very little scanning will need to be done.
  76.  
  77. To summarize these first 6 points, I would use tokens and multiple passes 
  78. instead of a single-pass character-oriented approach.  The remaining points 
  79. deal with programming style.
  80.  
  81. 7.  I would use stream routines in the macro expansion logic instead of a 
  82. profusion of buffers.  (See the code in def.c) The stream routines would 
  83. hide the details of testing for full buffers and allocating new buffers.  
  84. Although the details of macro expansion and token pasting are inherently 
  85. complex, using streams would have significantly simplified matters. 
  86. (Dealing with tokens instead of characters would also remove some 
  87. complications from the macro expansion code.)
  88.  
  89. 8.  I would use many more header files.  This is made possible and 
  90. desirable by  several new features in the new ANSI C Standard.  First,  the 
  91. Standard defines many new headers, which I would naturally incorporate 
  92. into the program.  Second, having function prototypes is a godsend, so I 
  93. would define a header file for just about every .c file.  The Macintosh 
  94. version of CSTAR uses this new style and it has been quite an 
  95. improvement.
  96.  
  97. I have found two headers to be particularly useful:  env.h and ver.h.  env.h 
  98. contains #defines that describe the current environment.  So any machine-
  99. dependent code is enclosed in
  100.  
  101.     #ifdef ENV_XXX
  102.         code
  103.     #endif
  104.  
  105. The ver.h header contains strings describing the current version of the code.
  106.  
  107. Although my opinions are based on statistics and a great deal of reflection I 
  108. am not attached to them.  If you have any questions or comments or other 
  109. suggestions I would be happy to hear from you.
  110.