home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / World_Of_Computer_Software-02-387-Vol-3of3.iso / p / pascal-.zip / pascal- / doc / paper.fw < prev    next >
Encoding:
Text File  |  1993-01-05  |  6.0 KB  |  162 lines
  1. @=~
  2.  
  3. ~t vskip 20 mm
  4. ~t title titlefont centre "A Complete Specification of a Simple Compiler"
  5. ~t vskip 5 mm
  6. ~t title normalfont centre "W. M. Waite"
  7. ~t title normalfont centre "Department of Electrical and Computer Engineering"
  8. ~t title normalfont centre "University of Colorado"
  9. ~t title normalfont centre "Boulder, CO  80309-0425"
  10. ~t vskip 20 mm
  11. ~t title normalfont centre "ABSTRACT"
  12. ~t vskip 5 mm
  13.  
  14. This report is a complete description of a simple compiler that implements the
  15. Pascal- language described in the book ``Brinch-Hansen on Pascal Compilers''.
  16. It was produced by the Eli
  17. compiler construction system from a body of text.
  18. The compiler was also generated by Eli from that same body of text.
  19. Its purpose is to illustrate a complete Eli specification in the context of
  20. an introductory compiler construction text.
  21. It follows the structure of Brinch-Hansen's book, commenting on the
  22. relationship between the hand-written compiler it describes and the
  23. specifications from which an equivalent compiler can be generated by Eli.
  24. Using this report, a reader can compare and contrast one approach to
  25. building a compiler by hand to an equivalent approach using tools.
  26.  
  27. ~t new_page
  28. ~t table_of_contents
  29.  
  30. ~A~<What the Pascal- Compiler Does~>
  31.  
  32. The Pascal- compiler accepts a program written in a subset of Pascal
  33. and produces an equivalent program in the language of an abstract
  34. stack-oriented machine ideally suited to the execution of Pascal programs.
  35. If the source program is not valid according to the rules of Pascal-,
  36. the compiler issues an error report keyed to the coordinates (line and column)
  37. at which the problem was detected.
  38.  
  39. ~B~<Translation~>
  40.  
  41. Here is a fragment of a program written in Pascal-
  42. (declarations of the integer variable ~{m~}, ~{n~}, ~{q~} and ~{r~} have
  43. been omitted):
  44.  
  45. ~$~<Pascal- code for Euclid's integer division algorithm~>~Z==~{
  46. { m>=0 and n>0 }
  47. q:=0; r:=m;
  48. while r>=n do
  49.   begin r:=r-n; q:=q+1 end;
  50. { q = quotient of m/n and r = remainder of m/n }
  51. ~}
  52.  
  53. The Pascal- compiler will accept a program containing this fragment
  54. and produce a program containing an equivalent fragment
  55. in the language of the abstract stack machine.
  56. In order to make it readable by humans,
  57. the abstract machine code is output as a text file.
  58. Each line of the file contains a single symbolic operation
  59. with arguments enclosed in parentheses
  60. (the comments on the right were added to
  61. explain the compiler's implementation):
  62.  
  63. ~$~<Abstract machine code for Euclid's integer division algorithm~>~Z==~{
  64. Variable(0,5)    Push the address of q onto the stack
  65. Constant(0)    Push the constant 0 onto the stack
  66. Assign(1)    Store the value at the address, removing both
  67. Variable(0,6)    Push the address of r onto the stack
  68. Variable(0,3)    Push the address of m onto the stack
  69. Value(1)    Replace the address at the top of the stack with its content
  70. Assign(1)
  71. DefAddr(L1)    Represent the current address symbolically by ``L1''
  72. Variable(0,6)    Push the address of r onto the stack
  73. Value(1)    Replace the address at the top of the stack with its content
  74. Variable(0,4)    Push the address of n onto the stack
  75. Value(1)    Replace the address at the top of the stack with its content
  76. NotLess        Compare the two values, removing both and setting the test flag
  77. Do(L2)        If the test flag is false, go to address represented by ``L2''
  78. Variable(0,6)
  79. Variable(0,6)
  80. Value(1)
  81. Variable(0,4)
  82. Value(1)
  83. Subtract    Replace the top two values by (second-top)
  84. Assign(1)
  85. Variable(0,5)
  86. Variable(0,5)
  87. Value(1)
  88. Constant(1)
  89. Add        Replace the top two values by (second+top)
  90. Assign(1)
  91. Goto(L1)    Go to address represented by ``L1''
  92. DefAddr(L2)    Represent the current address symbolically by ``L2''
  93. ~}
  94.  
  95. This form of the abstract machine code is not only easy for humans to read,
  96. thereby allowing them to understand the compiler's translation,
  97. but is also easy to implement via C pre-processor macros.
  98. Thus the programs produced by the compiler can be run on any machine that
  99. provides C.
  100.  
  101. ~B~<Error reporting~>
  102.  
  103. If an incorrect program is submitted to the Pascal- compiler,
  104. it must deduce that the program ~/is~/ incorrect
  105. and give the user an indication of the problem.
  106. Error reports are keyed to a particular position in the program,
  107. specified by a file name, line number, and character position within the line.
  108. The report itself consists of a ~/severity~/
  109. and a short text describing the problem.
  110. All of the errors detected by the Pascal- compiler are ~{FATAL~} -- compilation
  111. can proceed, but the generated program cannot be run.
  112. A ~{NOTE~} does not describe an error, but provides additional information.
  113.  
  114. Here is an erroneous program that illustrates a variety of reports:
  115.  
  116. ~$~<Error reporting example~>~Z==~{
  117. {Miscellaneous errors}
  118. program MiscError;
  119.   const
  120.     b = c;
  121.   type
  122.     T = array [5..1] of integer;
  123.     U = record x: true end;
  124.     V = array [false..true] of integer;
  125.   var
  126.     x, y, x: integer;
  127.     z: V;
  128.   begin
  129.   y := 1 and 2;
  130.   y := 2 * (3+4;
  131.   z[1] := &2;
  132.   end.
  133.  
  134. "miscerr", line 14:16 FATAL: Syntax error
  135. "miscerr", line 14:16 NOTE: Parsing resumed here
  136. "miscerr", line 15:11 FATAL: char '&' (ascii:38) is not a token
  137. "miscerr", line 4:9 FATAL: identifier not defined
  138. "miscerr", line 6:16 FATAL: Lower bound may not exceed upper bound
  139. "miscerr", line 7:19 FATAL: Must be a type identifier
  140. "miscerr", line 10:5 FATAL: identifier is multiply defined
  141. "miscerr", line 10:11 FATAL: identifier is multiply defined
  142. "miscerr", line 13:10 FATAL: Invalid operand for this operator
  143. "miscerr", line 15:3 FATAL: Invalid index type
  144. ~}
  145.  
  146. All of the reports are for file ~{miscerr~}.
  147. At the fourteenth line, the compiler detected a syntax error upon reaching
  148. character position 16.
  149. Character position 16 contains the semicolon of the assignment statement
  150. ~{y := 2 * (3+4;~}.
  151. At this point the compiler recognizes that there is no right parenthesis
  152. to match the left parenthesis before the ~{3~}.
  153. It recovers from the error by assuming that a right parenthesis is present,
  154. and continues analysis of the program by accepting the semicolon.
  155. (That is the meaning of the ~{NOTE~} following the syntax error report.)
  156.  
  157. ~i Structure.fwi
  158. ~i Scope.fwi
  159. ~i Type.fwi
  160. ~i Computer.fwi
  161. ~i Code.fwi
  162.