home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / intercal.zip / doc / THEORY < prev   
Text File  |  1996-06-20  |  4KB  |  93 lines
  1.         INTERCAL IMPLEMENTOR'S NOTES
  2.             by ESR
  3.  
  4. The C-INTERCAL compiler has a very conventional implementation using
  5. YACC and LEX (latterly, bison and flex).  It generates C, which
  6. is then passed to your C compiler.
  7.  
  8.             Lexical issues
  9.  
  10. Note that the spectacular ugliness of INTERCAL syntax requires that
  11. the lexical analyzer have two levels.  One, embedded in the input()
  12. function, handles the backquote and bang constructs, and stashes the
  13. input line away in a buffer for the splat construct's benefit.  The
  14. upper level is generated by lex(1) and does normal tokenizing for YACC.
  15.  
  16. In order to splatter erroneous statements correctly, the generated code has
  17. to track both logical and physical lines.  That's the reason for the
  18. `lineno' variable in the generated C, it's actually tracking physical lines.
  19.  
  20. Numeral tokens for input are defined in a symbol table (numerals.c)
  21. that is directly included in the run-time library module (cesspool.c).
  22. This avoids having to put the the size of the numerals array in an
  23. extern.  To add new numeral tokens, simply put them in the numerals
  24. initializer.
  25.  
  26.             Compilation
  27.  
  28. The parser builds an array of tuples, one for each INTERCAL statement.  Most
  29. tuples have node trees attached.  Once all tuples have been generated,
  30. the compile-time checker and optimizer phases can do consistency checks
  31. and expression-tree rewrites.  Finally, the tuples are ground out as C code
  32. by the emit() function.
  33.  
  34. Calculations are fully type-checked at compile time; they have to be because
  35. (as I read the manual) the 16- and 32-bit versions of the unary ops do
  36. different things.  The only potential problem here is that the typechecker
  37. has to assume that :m ~ :n has the type of :n (32-bit) even though the
  38. result might fit in 16 bits.  At run-time everything is calculated in 32
  39. bits.  When INTERCAL-72 was designed 32 bits was expensive; now it's cheap.
  40. Really, the only reason for retaining a 16-bit type at all is for the
  41. irritation value of it (yes, C-INTERCAL *does* enforce the 16-bit limit
  42. on constants).
  43.  
  44. Labels are mapped to tuple indices (logical line numbers) in the code
  45. checker, just before optimization.
  46.  
  47. The optimizer does full recursive folding of all constant expressions
  48. at compile time (evaluating away all the irritating little kluges you
  49. have to use to generate 32-bit constants).  It also checks for known
  50. INTERCAL idioms for `test for equality', `test for nonzeroness', and
  51. the C logical operators &, |, ^, and ~.
  52.  
  53.             Code Generation
  54.  
  55. Each line of INTERCAL is translated into a C if()-then; the guard part
  56. is used to implement abstentions and RESUMES, and the arm part
  57. translates the `body' of the corresponding INTERCAL statement.
  58.  
  59. The generated C code is plugged into the template file ick-wrap.c
  60. inside main().  It needs to be linked with cesspool.o, fiddle.o and
  61. lose.o (these are in libick.a, with the support for runtime switches,
  62. arrgghh.o).  Cesspool.o is the code that implements the storage
  63. manager; fiddle.o implements the INTERCAL operators; and lose.o is the
  64. code that generates INTERCAL's error messages.  The routine arrgghh.o
  65. parses the runtime command line arguments.
  66.  
  67. The abstain[] array in the generated C is used to track line and label
  68. abstentions; if member i is on, the statement on line i is being
  69. abstained from.  If gerund abstentions/reinstatements are present in
  70. the code, a second array recording the type of each statement in
  71. generated into the runtime, and used to ensure that these operations
  72. are translated into abstention-guard changes on all appropriate line numbers.
  73.  
  74. RESUMES are implemented with a branch to a generated switch statement
  75. that executes a goto to the appropriate label.  If there are no RESUMES,
  76. no such switch is generated.
  77.  
  78. The compiler places a simple label at the location of each COME FROM
  79. in the program, while all of the machinery for checking for abstention
  80. and conditional execution and actually performing the jump is placed
  81. immediately after the code for the target statement.
  82.  
  83.             Credits
  84.  
  85. I wrote the first version of this compiler over a weekend using a
  86. pre-ANSI C compiler.  It worked, but it wasn't pretty.  Louis Howell
  87. added the array support later; he also torture-tested the COME FROM
  88. implementation by actually using it for the life2.i program included
  89. in this distribution, and fixed some bugs.  Brian Raiter did a
  90. much-needed delinting while porting it for ANSI C, flex and Linux. He
  91. also improved the lexical analyzer's line tracking.
  92.  
  93.