home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / compiler / 1403 < prev    next >
Encoding:
Text File  |  1992-08-18  |  2.9 KB  |  56 lines
  1. Newsgroups: comp.compilers
  2. Path: sparky!uunet!think.com!spdcc!iecc!compilers-sender
  3. From: leichter@zodiac.rutgers.edu
  4. Subject: Re: Two-pass C compilers
  5. Reply-To: leichter@zodiac.rutgers.edu
  6. Organization: Rutgers University Computing Services
  7. Date: Tue, 18 Aug 1992 12:59:23 GMT
  8. Approved: compilers@iecc.cambridge.ma.us
  9. Message-ID: <92-08-102@comp.compilers>
  10. Keywords: design
  11. References: <92-08-081@comp.compilers> <92-08-096@comp.compilers>
  12. Sender: compilers-sender@iecc.cambridge.ma.us
  13. Lines: 41
  14.  
  15. One of the problems with the definitions of "pass" that people seem to
  16. have in mind from historical referents is that they are too
  17. technology-specific.  In the old days, a "pass" required you to start the
  18. paper tape over or take the deck of cards out of the output stacker and
  19. feed them back into the input stacker.  To this day, people think in terms
  20. of file I/O.  Suppose I used a memory-mapping call to map the entire
  21. source code into memory.  Would I then have a 0-pass compiler?
  22.  
  23. I'd like to suggest a different style of definition.  Divide the compiler
  24. into blocks, each of which has the property that once exited, the block
  25. will never be re-entered.  A "strong pass" is a block whose running time
  26. is (at least) linear in the size of the input.  A "pass" is a block whose
  27. running time is (at least) linear in the size of the "meaningful" input -
  28. that is, the input less comments, for most languages.  A "weak pass" is a
  29. block whose running time is (at least) linear in the size of the tokenized
  30. input.
  31.  
  32. A strong pass captures the old notion of actually reading the input file
  33. again.  Very few, if any, few modern compilers have more than one strong
  34. pass (the entire compiler).  Passes, however, are common - in stand-alone
  35. C pre-processors, for example.  (Actually, C pre-processors are much more
  36. complex, since their output, after macro expansion and #include
  37. processing, can be much longer than their input, even leaving out
  38. comments.  For the purposes of these definitions, the "input" used must
  39. include all source text that will ever be seen, so the #include's don't
  40. matter.  For typical uses, the macro expansions won't make much
  41. difference.)  Modern compilers that allow arbitrary definition after use
  42. would probably use an extra weak pass.  A simple-minded linker fixup
  43. (which scanned the entire executable) would, in some sense, be a weak
  44. pass.  (Actually, of course, every linker is already a "weak pass" in this
  45. sense - the issue is whether the linker has more than one of them.)
  46.  
  47. Note that a pass (of any kind) is not intended to tell you anything about
  48. running time.  A "one pass" compiler may re-examine the entire text of
  49. individual functions, say, many times.  Passes have to do with the
  50. possible need of the compiler to go back arbitrarily far in the input.
  51.  
  52.                             -- Jerry
  53. -- 
  54. Send compilers articles to compilers@iecc.cambridge.ma.us or
  55. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  56.