internal.doc 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342
  1. .pl 12.5i
  2. .sp 1.5i
  3. .NH
  4. The compiler
  5. .nh
  6. .LP
  7. The compiler can be divided roughly into four modules:
  8. \(bu lexical analysis
  9. .br
  10. \(bu syntax analysis
  11. .br
  12. \(bu semantic analysis
  13. .br
  14. \(bu code generation
  15. .br
  16. The four modules are grouped into one pass. The activity of these modules
  17. is interleaved during the pass.
  18. .br
  19. The lexical analyzer, some expression handling routines and various
  20. datastructures from the Modula-2 compiler contributed to the project.
  21. .sp 2
  22. .NH 2
  23. Lexical Analysis
  24. .LP
  25. The first module of the compiler is the lexical analyzer. In this module, the
  26. stream of input characters making up the source program is grouped into
  27. \fItokens\fR, as defined in \fBISO 6.1\fR. The analyzer is hand-written,
  28. because the lexical analyzer generator, which was at our disposal,
  29. \fILex\fR [LEX], produces much slower analyzers. A character table, in the file
  30. \fIchar.c\fR, is created using the program \fItab\fR which takes as input
  31. the file \fIchar.tab\fR. In this table each character is placed into a
  32. particular class. The classes, as defined in the file \fIclass.h\fR,
  33. represent a set of tokens. The strategy of the analyzer is as follows: the
  34. first character of a new token is used in a multiway branch to eliminate as
  35. many candidate tokens as possible. Then the remaining characters of the token
  36. are read. The constant INP_NPUSHBACK, defined in the file \fIinput.h\fR,
  37. specifies the maximum number of characters the analyzer looks ahead. The
  38. value has to be at least 3, to handle input sequences such as:
  39. .br
  40. 1e+4 (which is a real number)
  41. .br
  42. 1e+a (which is the integer 1, followed by the identifier "e", a plus, and the identifier "a")
  43. Another aspect of this module is the insertion and deletion of tokens
  44. required by the parser for the recovery of syntactic errors (see also section
  45. 2.2). A generic input module [ACK] is used to avoid the burden of I/O.
  46. .sp 2
  47. .NH 2
  48. Syntax Analysis
  49. .LP
  50. The second module of the compiler is the parser, which is the central part of
  51. the compiler. It invokes the routines of the other modules. The tokens obtained
  52. from the lexical analyzer are grouped into grammatical phrases. These phrases
  53. are stored as parse trees and handed over to the next part. The parser is
  54. generated using \fILLgen\fR[LL], a tool for generating an efficient recursive
  55. descent parser with no backtrack from an Extended Context Free Syntax.
  56. .br
  57. An error recovery mechanism is generated almost completely automatically. A
  58. routine called \fILLmessage\fR had to be written, which gives the necessary
  59. error messages and deals with the insertion and deletion of tokens.
  60. The routine \fILLmessage\fR must accept one parameter, whose value is
  61. a token number, zero or -1. A zero parameter indicates that the current token
  62. (the one in the external variable \fILLsymb\fR) is deleted.
  63. A -1 parameter indicates that the parser expected end of file, but did
  64. not get it. The parser will then skip tokens until end of file is detected.
  65. A parameter that is a token number (a positive parameter) indicates that
  66. this token is to be inserted in front of the token currently in \fILLsymb\fR.
  67. Also, care must be taken, that the token currently in \fILLsymb\fR is again
  68. returned by the \fBnext\fR call to the lexical analyzer, with the proper
  69. attributes. So, the lexical analyzer must have a facility to push back one
  70. token.
  71. .br
  72. Calls to the two standard procedures \fIwrite\fR and \fIwriteln\fR can be
  73. different from calls to other procedures. The syntax of a write-parameter
  74. is different from the syntax of an actual-parameter. We decided to include
  75. them, together with \fIread\fR and \fIreadln\fR, in the grammar. An alternate
  76. solution would be to make the syntax of an actual-parameter identical to the
  77. syntax of a write-parameter. Afterwards the parameter has to be checked to
  78. see whether it is used properly or not.
  79. .bp
  80. As the parser is LL(1), it must always be able to determine what to do,
  81. based on the last token read (\fILLsymb\fR). Unfortunately, this was not the
  82. case with the grammar as specified in [ISO]. Two kinds of problems
  83. appeared, viz. the \fBalternation\fR and \fBrepetition\fR conflict.
  84. The examples given in the following paragraphs are taken from the grammar.
  85. .NH 3
  86. Alternation conflict
  87. .LP
  88. An alternation conflict arises when the parser can not decide which
  89. production to choose.
  90. .br
  91. \fBExample:\fR
  92. .in +2m
  93. .ft 5
  94. .nf
  95. procedure-declaration : procedure-heading \fB';'\f5 directive |
  96. .br
  97. \h'\w'procedure-declaration : 'u'procedure-identification \fB';'\f5 procedure-block |
  98. .br
  99. \h'\w'procedure-declaration : 'u'procedure-heading \fB';'\f5 procedure-block ;
  100. .br
  101. procedure-heading : \fBprocedure\f5 identifier [ formal-parameter-list ]? ;
  102. .br
  103. procedure-identification : \fBprocedure\f5 procedure-identifier ;
  104. .fi
  105. .ft R
  106. .in -2m
  107. A sentence that starts with the terminal \fBprocedure\fR is derived from the
  108. three alternative productions. This conflict can be resolved in two ways:
  109. adjusting the grammar, usually some rules are replaced by one rule and more
  110. work has to be done in the semantic analysis; using the LLgen conflict
  111. resolver, "\fB%if\fR (C-expression)", if the C-expression evaluates to
  112. non-zero, the production in question is chosen, otherwise one of the
  113. remaining rules is chosen. The grammar rules were rewritten to solve this
  114. conflict. The new rules are given below. For more details see the file
  115. \fIdeclar.g\fR.
  116. .in +2m
  117. .ft 5
  118. .nf
  119. procedure-declaration : procedure-heading \fB';'\f5 ( directive | procedure-block ) ;
  120. .br
  121. procedure-heading : \fBprocedure\f5 identifier [ formal-parameter-list ]? ;
  122. .fi
  123. .ft R
  124. .in -2m
  125. A special case of an alternation conflict, which is common to many block
  126. structured languages, is the \fI"dangling-else"\fR ambiguity.
  127. .in +2m
  128. .ft 5
  129. .nf
  130. if-statement : \fBif\f5 boolean-expression \fBthen\f5 statement [ else-part ]? ;
  131. .br
  132. else-part : \fBelse\f5 statement ;
  133. .fi
  134. .ft R
  135. .in -2m
  136. The following statement that can be derived from the rules above is ambiguous:
  137. .ti +2m
  138. \fBif\f5 boolean-expr-1 \fBthen\f5 \fBif\f5 boolean-expr-2 \fBthen\f5 statement-1 \fBelse\f5 statement-2
  139. .ft R
  140. .ps 8
  141. .vs 7
  142. .PS
  143. move right 1.1i
  144. S: line down 0.5i
  145. "if-statement" at S.start above
  146. .ft B
  147. "then" at S.end below
  148. .ft R
  149. move to S.start then down 0.25i
  150. L: line left 0.5i then down 0.25i
  151. box ht 0.33i wid 0.6i "boolean" "expression-1"
  152. move to L.start then left 0.5i
  153. L: line left 0.5i then down 0.25i
  154. .ft B
  155. "if" at L.end below
  156. .ft R
  157. move to L.start then right 0.5i
  158. L: line right 0.5i then down 0.25i
  159. "statement" at L.end below
  160. move to L.end then down 0.10i
  161. L: line down 0.25i dashed
  162. "if-statement" at L.end below
  163. move to L.end then down 0.10i
  164. L: line down 0.5i
  165. .ft B
  166. "then" at L.end below
  167. .ft R
  168. move to L.start then down 0.25i
  169. L: line left 0.5i then down 0.25i
  170. box ht 0.33i wid 0.6i "boolean" "expression-2"
  171. move to L.start then left 0.5i
  172. L: line left 0.5i then down 0.25i
  173. .ft B
  174. "if" at L.end below
  175. .ft R
  176. move to L.start then right 0.5i
  177. L: line right 0.5i then down 0.25i
  178. box ht 0.33i wid 0.6i "statement-1"
  179. move to L.start then right 0.5i
  180. L: line right 0.5i then down 0.25i
  181. .ft B
  182. "else" at L.end below
  183. .ft R
  184. move to L.start then right 0.5i
  185. L: line right 0.5i then down 0.25i
  186. box ht 0.33i wid 0.6i "statement-2"
  187. move to S.start
  188. move right 3.5i
  189. L: line down 0.5i
  190. "if-statement" at L.start above
  191. .ft B
  192. "then" at L.end below
  193. .ft R
  194. move to L.start then down 0.25i
  195. L: line left 0.5i then down 0.25i
  196. box ht 0.33i wid 0.6i "boolean" "expression-1"
  197. move to L.start then left 0.5i
  198. L: line left 0.5i then down 0.25i
  199. .ft B
  200. "if" at L.end below
  201. .ft R
  202. move to L.start then right 0.5i
  203. S: line right 0.5i then down 0.25i
  204. "statement" at S.end below
  205. move to S.start then right 0.5i
  206. L: line right 0.5i then down 0.25i
  207. .ft B
  208. "else" at L.end below
  209. .ft R
  210. move to L.start then right 0.5i
  211. L: line right 0.5i then down 0.25i
  212. box ht 0.33i wid 0.6i "statement-2"
  213. move to S.end then down 0.10i
  214. L: line down 0.25i dashed
  215. "if-statement" at L.end below
  216. move to L.end then down 0.10i
  217. L: line down 0.5i
  218. .ft B
  219. "then" at L.end below
  220. .ft R
  221. move to L.start then down 0.25i
  222. L: line left 0.5i then down 0.25i
  223. box ht 0.33i wid 0.6i "boolean" "expression-2"
  224. move to L.start then left 0.5i
  225. L: line left 0.5i then down 0.25i
  226. .ft B
  227. "if" at L.end below
  228. .ft R
  229. move to L.start then right 0.5i
  230. L: line right 0.5i then down 0.25i
  231. box ht 0.33i wid 0.6i "statement-1"
  232. .PE
  233. .ps
  234. .vs
  235. \h'615u'(a)\h'1339u'(b)
  236. .sp
  237. .ce
  238. Two parse trees showing the \fIdangling-else\fR ambiguity
  239. .sp 2
  240. According to the standard, \fBelse\fR is matched with the nearest preceding
  241. unmatched \fBthen\fR, i.e. parse tree (a) is valid (\fBISO 6.8.3.4\fR).
  242. This conflict is statically resolved in LLgen by using "\fB%prefer\fR",
  243. which is equivalent in behaviour to "\fB%if\fR(1)".
  244. .bp
  245. .NH 3
  246. Repetition conflict
  247. .LP
  248. A repetition conflict arises when the parser can not decide whether to choose
  249. a production once more, or not.
  250. .br
  251. \fBExample:\fR
  252. .in +2m
  253. .ft 5
  254. .nf
  255. field-list : [ ( fixed-part [ \fB';'\f5 variant-part ]? | variantpart ) [;]? ]? ;
  256. .br
  257. fixed-part : record-section [ \fB';'\f5 record-section ]* ;
  258. .fi
  259. .in -2m
  260. .ft R
  261. When the parser sees the semicolon, it can not decide whether another
  262. record-section or a variant-part follows. This conflict can be resolved in
  263. two ways: adjusting the grammar or using the conflict resolver,
  264. "\fB%while\fR (C-expression)". The grammar rules that deal with this conflict
  265. were completely rewritten. For more details, the reader is referred to the
  266. file \fIdeclar.g\fR.
  267. .sp 2
  268. .NH 2
  269. Semantic Analysis
  270. .LP
  271. The third module of the compiler is the checking of semantic conventions of
  272. ISO-Pascal. To check the program being parsed, actions have been used in
  273. LLgen. An action consists of several C-statements, enclosed in brackets
  274. "{" and "}". In order to facilitate communication between the actions and
  275. \fILLparse\fR, the parsing routines can be given C-like parameters and
  276. local variables. An important part of the semantic analyzer is the symbol
  277. table. This table stores all information concerning identifiers and their
  278. definitions. Symbol-table lookup and hashing is done by a generic namelist
  279. module [ACK]. The parser turns each program construction into a parse tree,
  280. which is the major datastructure in the compiler. This parse tree is used
  281. to exchange information between various routines.
  282. .sp 2
  283. .NH 2
  284. Code Generation
  285. .LP
  286. The final module in the compiler is that of code generation. The information
  287. stored in the parse trees is used to generate the EM code [EM]. EM code is
  288. generated with the help of a procedural EM-code interface [ACK]. The use of
  289. static exchanges is not desired, since the fast back end can not cope with
  290. static code exchanges, hence the EM pseudoinstruction \fBexc\fR is never
  291. generated.
  292. .br
  293. Chapter 3 discusses the code generation in more detail.
  294. .sp 2
  295. .NH 2
  296. Error Handling
  297. .LP
  298. The first three modules have in common that they can detect errors in the
  299. Pascal program being compiled. If this is the case, a proper message is given
  300. and some action is performed. If code generation has to be aborted, an error
  301. message is given, otherwise a warning is given. The constant MAXERR_LINE,
  302. defined in the file \fIerrout.h\fR, specifies the maximum number of messages
  303. given per line. This can be used to avoid long lists of error messages caused
  304. by, for example, the omission of a ';'. Three kinds of errors can be
  305. distinguished: the lexical error, the syntactic error, and the semantic error.
  306. Examples of these errors are respectively, nested comments, an expression with
  307. unbalanced parentheses, and the addition of two characters.
  308. .sp 2
  309. .NH 2
  310. Memory Allocation and Garbage Collection
  311. .LP
  312. The routines \fIst_alloc\fR and \fIst_free\fR provide a mechanism for
  313. maintaining free lists of structures, whose first field is a pointer called
  314. \fBnext\fR. This field is used to chain free structures together. Each
  315. structure, suppose the tag of the structure is ST, has a free list pointed
  316. by h_ST. Associated with this list are the operations: \fInew_ST()\fR, an
  317. allocating mechanism which supplies the space for a new ST struct; and
  318. \fIfree_ST()\fR, a garbage collecting mechanism which links the specified
  319. structure into the free list.
  320. .bp