home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 8 / FreshFishVol8-CD2.bin / bbs / dev / oberon-a-1.4ß.lha / Oberon-A / texts / OP2.Paper.Text < prev    next >
Text File  |  1994-03-10  |  26KB  |  569 lines
  1. OP2: A PORTABLE OBERON-2 COMPILER
  2.  
  3. Presented at the 2nd International Modula-2 Conference, Loughborough,
  4. Sept 91
  5.  
  6. Regis CRELIER
  7. Institut für Computersysteme, ETH Zürich
  8.  
  9. ABSTRACT
  10.  
  11. A portable compiler for the language Oberon-2 is presented. Most related
  12. works pay for portability with low compilation speed or poor code
  13. quality. Portability and efficiency have been given the same importance
  14. in our approach. Hence, an automated retargetable code generation has
  15. not been considered. The compiler consists of a front-end and a
  16. back-end. The front-end does the lexical and syntactic analysis,
  17. including type checking. It builds a machine-independent structure
  18. representing the program. This structure is made up of a symbol table
  19. and an abstract syntax tree, rather than a stream of pseudo-instructions
  20. coded in an "intermediate language". If no errors are found, control is
  21. passed to the back-end which generates code from this intermediate
  22. structure. This structure clearly separates the front-end which is
  23. machine-independent from the back-end which is machine-dependent. While
  24. the front-end can remain unchanged, the back-end has to be reprogrammed,
  25. when the compiler is retargeted to a new machine.
  26.  
  27. This compiler has been successfully used to port the Oberon System onto
  28. different computers. Code generators have been implemented both for CISC
  29. and RISC processors. Differences in processor architectures are
  30. reflected in the complexity of the back-end, the generated code density
  31. and performance. The compiler is written in Oberon. New compilers have
  32. therefore to be first compiled on an already working Oberon System. If
  33. such a system is not available, a version of the compiler whose back-end
  34. produces C code may be used for the bootstrap.
  35.  
  36. The compilation techniques presented here are not restricted to Oberon
  37. compilers, but could be used for other programming languages too.
  38. Nevertheless, Oberon and OP2 tend to the same ideal: simplicity,
  39. flexibility, efficiency and elegance.
  40.  
  41. INTRODUCTION
  42.  
  43. Portability is an important criterion for program quality. A compiler is
  44. a program as well, and it may be ported. If it should produce the same
  45. code as before on the new machine (cross compiler), then it is not more
  46. difficult to port it than any other program also written in a higher
  47. programming language. But if the produced code must run on the new
  48. machine, the compiler has to be rewritten and it is not the same program
  49. any more. In that sense, the compiler is not, and cannot be, portable.
  50. By the term portable compiler , we refer here to a compiler that needs
  51. reasonably small effort to be adapted to a new machine and/or to be
  52. modified to produce new code. Most related work attempt to reduce this
  53. adaptation cost to a minimum, compromising the compilation speed and the
  54. code quality. A classification of such automated retargetable code
  55. generation techniques and a survey of the works on those techniques are
  56. presented in [1]. The basic idea is to produce code for a virtual
  57. machine. This code is then expanded into real machine instructions. The
  58. expansion can be done by hand-written translators [2] or by a
  59. machine-independent code generation algorithm, in which case each
  60. intermediate language instruction [3] or each recognized pattern of
  61. these [4] is expanded into a fixed pattern of target machine
  62. instructions recorded in tables. Trees may replace linear code to feed
  63. the pattern matching algorithm [5, 6, 7]. These techniques usually yield
  64. poor code quality, making a peephole optimization phase necessary, which
  65. further increases the compilation time.
  66.  
  67. In our approach, we tried to find the right balance between code
  68. quality, compilation speed and portability. We think it is worth-while
  69. investing, say three man-months, for a port, if the resulting compiler
  70. is very fast and produces efficient code. Thus, a pattern matching or
  71. table-driven code generation has not been considered. Instead, we looked
  72. at more conventional and faster techniques, such as single-pass
  73. compilation [8, 9]. In a single-pass compiler, the compilation phases
  74. are executed simultaneously. No intermediate representation of the
  75. source text is needed between the different phases, making the compiler
  76. compact and efficient, but not very portable. Indeed, since
  77. machine-dependent and machine-independent phases are mixed up, it is
  78. very difficult to modify the compiler for a new machine.
  79.  
  80. One solution to the problem is to clearly separate the compilation
  81. phases into two groups: the front-end consisting of the
  82. machine-independent phases (lexical and syntactic analysis, type
  83. checking) and the back-end consisting of the machine-dependent phases
  84. (storage allocation, code generation). Only the back-end must be
  85. modified when the compiler is ported. The front-end enters declarations
  86. in a symbol table and builds an intermediate representation of the
  87. program statements, an abstract syntax tree. If no errors were found,
  88. control is passed to the back-end, which generates code from the syntax
  89. tree. Since this structure is guaranteed to be free of errors, type
  90. checking or error recovery are not part of the back-end, which is a
  91. noteworthy advantage. Only implementation restrictions must be checked.
  92. Another advantage of the intermediate structure is that optional passes
  93. may be inserted to optimize the code. Such an optimization phase cannot
  94. be easily embedded in a conventional single-pass compiler. The front-end
  95. and the back-end are implemented separately as a set of modules.
  96.  
  97. MODULE STRUCTURE
  98.  
  99. Originally, OP2 has been designed to compile Oberon programs [10] and
  100. has been slightly modified later to compile Oberon-2 programs [11, 12].
  101. It consists of nine modules (see figure 1) all written in Oberon.
  102.  
  103. The lowest module of the hierarchy is OPM , where M stands for machine.
  104. We must distinguish between the host machine on which the compiler is
  105. running, and the target machine for which the compiler is generating
  106. code. Most of the time, the two machines are the same, except during a
  107. bootstrap or in case of a cross-compiler. The module OPM defines and
  108. exports several constants used to parametrize the front-end. Some of
  109. these constants reflect target machine characteristics or implementation
  110. restrictions. For example, these values are used in the front-end to
  111. check the evaluation of constant expressions on overflow. But OPM has a
  112. second function. It works as interface between the compiler and the host
  113. machine. This interface includes procedures to read the text to be
  114. compiled, to read and write data in symbol files [13], and to display
  115. text (error messages e.g.) onto the screen. All these input and output
  116. operations are strongly dependent on the operating system. If the
  117. compiler resides in the Oberon System environment [14, 15], the
  118. host-dependent part of OPM remains unchanged.
  119.  
  120. The topmost module (OP2) is very short. It is the interface to the user,
  121. and therefore host machine-dependent. It first calls the front-end with
  122. the source text to be compiled as parameter. If no error is detected, it
  123. then calls the back-end with the root of the tree that was returned by
  124. the front-end as parameter.
  125.  
  126. Figure 1.    Module import graph (an arrow from A to B means B imports A)
  127.  
  128. Between the highest and the lowest module, one finds the front-end and
  129. the back-end, which consist of four, respectively three modules. There
  130. is no interaction during compilation between these two sets of modules.
  131. The symbol table and the syntax tree are defined in module OPT and are
  132. used by both the front-end and the back-end. This explains the presence
  133. of import arrows from OPT to back-end modules visible in the import
  134. graph (figure 1). But there is no transfer of control, such as procedure
  135. calls.
  136.  
  137. The front-end is controlled by the module OPP, a recursive-descent
  138. parser. Its main task is to check syntax and to call procedures to
  139. construct the symbol table and the syntax tree. The parser requests
  140. lexical symbols from the scanner (OPS) and calls procedures of OPT,
  141. the symbol table handler, and of OPB, the syntax tree builder. OPB
  142. also checks type compatibility.
  143.  
  144. The back-end is controlled by OPV, the tree traverser. It first
  145. traverses the symbol table to enter machine-dependent data (usi