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