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- / specs / Scope.fw < prev    next >
Text File  |  1993-01-04  |  16KB  |  415 lines
  1. @=~
  2.  
  3. ~A~<Scope Analysis~>
  4.  
  5. A Pascal- program uses names to refer to constants, types, fields, variables,
  6. procedures and parameters.
  7. Each name must be defined, and then may be used anywhere within the ~/scope~/
  8. of that definition.
  9. The scope of a definition is a phrase of the program, and within such a phrase
  10. there can be only one definition of a particular name.
  11. The purpose of scope analysis is to make certain that every name has exactly
  12. one definition, and to associate each use of that name with its definition.
  13.  
  14. It is convenient to split scope analysis into two parts.
  15. The first, which associates definitions of names with their uses, is called
  16. ~/consistent renaming~/.
  17. Once this association has been made, it is easy to report missing definitions
  18. and multiple definitions.
  19.  
  20. ~B~<Consistent renaming~>
  21.  
  22. The constants, types, fields, variables, procedures and parameters referred to
  23. by names are basic components of the algorithm described by the program.
  24. Brinch-Hansen calls these basic components ~/objects~/.
  25. Each object has properties that are established by that object's definition
  26. and examined at each use.
  27. It is therefore reasonable to represent each object internally by a unique key
  28. that allows access to arbitrary information in a global data base.
  29. The consistent renaming process associates the appropriate key with each
  30. occurrence of a name, ``renaming'' it with the key that represents the object
  31. referred to by the name.
  32.  
  33. Definitions and uses of names are distinguished in the grammar.
  34. For example, a ~{ConstantNameDef~} phrase is the definition of a constant name
  35. and a ~{TypeNameUse~} phrase is a use of a type name.
  36. A definition's scope is the smallest ~/block~/ containing its definition,
  37. excluding the text of nested blocks defining the same name.
  38. Three phrases, ~{ProcedureBlock~}, ~{Program~} and ~{StandardBlock~},
  39. are classified as blocks.
  40. A ~{ProcedureBlock~} can be nested within another ~{ProcedureBlock~}
  41. or within the ~{Program~}.
  42. The ~{StandardBlock~} is an imaginary block in which the standard objects are
  43. defined.
  44.  
  45. Scope rules based on nested phrases, in which the scope of a definition is the
  46. phrase containing the definition exclusive of nested phrases defining the same
  47. name, are common in programming languages.
  48. Eli provides a library module to implement consistent renaming
  49. according to these scope rules.
  50. The consistent renaming problem is therefore solved by analogy.
  51. Its solution requires that the user understand the problem,
  52. know that an appropriate library module exists and how to use it,
  53. and instantiate that library module.
  54.  
  55. Directory ~{$/Tool/lib~} contains a set of ~/generic~/ library modules that
  56. solve common subproblems.
  57. Each module is a file of type ~{gnrc~}, and is instantiated by requesting a
  58. derivation to ~{:inst~}.
  59. They are gathered into subdirectories according to the kinds of problems
  60. they solve; the consistent renaming problem for nested scopes is solved by
  61. the module ~{$/Tool/lib/Name/Nest.gnrc~}.
  62. To instantiate this module, therefore, the line ~{$/Tool/lib/Name/Nest.gnrc
  63. :inst~} appears in the type-~{specs~} file describing the Pascal- compiler
  64. (Section 3.3).
  65.  
  66. ~{Nest.gnrc~} exports four symbols to embody the concepts involved:
  67. a ~{RangeNest~} is a phrase that can contain definitions,
  68. the ~{RootNest~} is the ``outermost'' such phrase,
  69. an ~{IdDefNest~} is a name definition,
  70. and an ~{IdUseNest~} is a name use.
  71. Name definitions and uses are assumed to be represented by tree nodes having a
  72. ~{Sym~} attribute of type ~{int~} that specifies the corresponding name.
  73. (Distinct names result in different values for the ~{Sym~} attribute of the
  74. corresponding nodes; identical names result in the same value for the ~{Sym~}
  75. attribute of the corresponding nodes.)
  76. The module will compute the value of a ~{Key~} attribute of type ~{DefTableKey~}
  77. at each tree node representing a name definition or use.
  78. ~{Key~} attribute values of associated definitions and uses will be identical.
  79. If a use is not associated with any definition, its ~{Key~} attribute value
  80. will be the distinguished ~{DefTableKey~} value ``~{NoKey~}''.
  81.  
  82. The library module is used by defining symbols that embody Pascal-
  83. scope rule concepts, and attaching the properties of the appropriate library
  84. symbols to them by inheritance.
  85. Pascal- scope rule concepts include those embodied by the four symbols of the
  86. library module, but also include the concept that definitions in a block must be
  87. unique and that every name used in a block must have a definition in that block
  88. or an enclosing one.
  89. These additional concepts do not affect the consistent renaming process,
  90. but they mean that Pascal- scope rule concepts are not identical to those of the
  91. library module and should therefore be represented by different symbols:
  92.  
  93. ~$~<Pascal- scope rule concepts~>==~{
  94. ATTR Key: DefTableKey;
  95.  
  96. SYMBOL Block INHERITS RangeNest END;
  97.  
  98. ATTR Sym: int;
  99. SYMBOL NameOccurrence COMPUTE
  100.   SYNT.Sym=CONSTITUENT Name.Sym;
  101. END;
  102.  
  103. SYMBOL NameDef INHERITS IdDefNest, NameOccurrence END;
  104. SYMBOL NameUse INHERITS IdUseNest, NameOccurrence END;
  105. ~}
  106.  
  107. You will recall that name definition and use phrases were all defined as
  108. occurrences of the basic symbol ~{Name~}.
  109. During lexical analysis, a unique integer is computed for each name and attached
  110. to the tree node representing that basic symbol.
  111. This integer must be established as the value of the ~{Sym~} attribute of the
  112. tree node representing the name definition or use in order to satisfy an
  113. interface condition of the consistent renaming module.
  114. ~{NameOccurrence~} embodies this requirement.
  115.  
  116. The Pascal- concept of the symbol block corresponds directly to the concept
  117. represented by the module's ~{RootNest~} symbol.
  118. It is true that definitions in the symbol block must be unique,
  119. and that every name used in the symbol block must have a definition in that
  120. block,
  121. but these properties are trivially satisfied because name definition and use in
  122. the symbol block is fixed by the language design.
  123. Therefore no additional symbol is needed to embody the Pascal- concept of a
  124. symbol block; ~{RootNest~} suffices.
  125.  
  126. ~B
  127.  
  128. The requirements that a definition be unique within its scope and
  129. that all uses of names be associated with definitions
  130. are common in programming languages,
  131. and so Eli provides modules to report violations of them.
  132. ~{$/Tool/lib/Name/Unique.gnrc~} reports multiple definitions, and
  133. ~{$/Tool/lib/Name/NoKeyMsg.gnrc~} reports uses of undefined names.
  134.  
  135. It is important to remember that these requirements are distinct from the
  136. requirements of consistent renaming, and for that reason are represented by
  137. distinct modules.
  138. Unique definition is a property of both
  139. the phrase in which the definitions occur and the definitions themselves,
  140. but it is ~/not~/ a property of the uses of a name.
  141. Similarly, the requirement that every use of a name be associated with some
  142. definition is a property ~/only~/ of name uses.
  143. Thus the symbols that embody Pascal- scope rules inherit the properties of the
  144. symbols exported by the modules as follows:
  145.  
  146. ~$~<Reporting scope rule violations~>==~{
  147. SYMBOL Block INHERITS RangeUnique END;
  148. SYMBOL NameDef INHERITS IdDefUnique END;
  149.  
  150. SYMBOL NameUse INHERITS NoKeyMsg END;
  151. ~}
  152.  
  153. ~B
  154.  
  155. Although the programmer regards the standard block as an imaginary block,
  156. the compiler must actually implement it in order to make the definitions of the
  157. standard objects accessible to the scope analysis algorithms.
  158. As far as the scope rules are concerned, the program is nested within the
  159. standard block.
  160. Therefore the program should be a component phrase of the standard block phrase,
  161. and the grammar must be augmented with a production describing this
  162. relationship:
  163.  
  164. ~$~<The standard block~>==~{
  165. StandardBlock: Program .
  166. ~}
  167.  
  168. ~C
  169.  
  170. The standard block is the outermost phrase in which definitions can appear, and
  171. this concept is embodied in the symbol ~{RootNest~} exported by the consistent
  172. renaming module.
  173. ~{RootNest~} is assumed to be represented by a tree node having an attribute
  174. ~{Env~}, of type ~{Environment~}, that defines all of the names of standard
  175. objects.
  176. By default, no standard objects exist.
  177. Because standard objects do exist in Pascal-, this default must be overridden by
  178. a computation specific to Pascal-:
  179.  
  180. ~$~<Scope rules for the standard block~>==~{
  181. SYMBOL StandardBlock: Env: Environment;
  182.  
  183. SYMBOL StandardBlock INHERITS RootNest COMPUTE
  184.   SYNT.Env = StandardEnv(NewEnv());
  185. END;
  186. ~}
  187.  
  188. ~{NewEnv~} is a library routine that creates a value of type ~{Environment~}
  189. containing no definitions.
  190. ~{StandardEnv~} (described below) populates the environment specified by its
  191. argument with definitions of the standard objects of Pascal-.
  192.  
  193. ~C
  194.  
  195. Pascal- assumes six standard objects: two constants, two types and two
  196. procedures.
  197. We shall see in later chapters that it is important to be able to refer directly
  198. to the keys that represent standard objects.
  199. The easiest way to satisfy this requirement is to have a single C module
  200. exporting variables containing the keys as well as the operation
  201. ~{StandardEnv~} that defines those keys and populates an environment with them.
  202. Implementation of the standard objects is thus a problem that we describe by
  203. solution.
  204.  
  205. The exported variable containing the key representing the Pascal- ~{boolean~}
  206. type will be named ~{BooleanKey~}, the exported variable containing the key
  207. representing the constant ~{false~} will be named ~{FalseKey~}, and so forth.
  208. These names will be needed in three different contexts within the module:
  209. as external declarations in the module interface,
  210. as variable definitions in the module body,
  211. and as targets of assignments in the module body.
  212. Thus it is convenient to describe the set of standard objects by calls to a C
  213. pre-processor macro that can be redefined to suit the context:
  214.  
  215. ~$~<Standard objects~>~M~{
  216.   StdObj(Boolean)
  217.   StdObj(False)
  218.   StdObj(Integer)
  219.   StdObj(Read)
  220.   StdObj(True)
  221.   StdObj(Write)
  222. ~}
  223.  
  224. External declarations in the module interface and variable definitions in the
  225. module body have a similar form, but must appear in different files:
  226.  
  227. ~$~<External declarations in the module interface~>==~{
  228. #define StdObj(i) extern DefTableKey i/**/Key;
  229. ~<Standard objects~>
  230. #undef StdObj
  231. ~}
  232.  
  233. ~$~<Variable definitions in the module body~>==~{
  234. #define StdObj(i) DefTableKey i/**/Key;
  235. ~<Standard objects~>
  236. #undef StdObj
  237. ~}
  238.  
  239. The variables are assigned their values by the operation that populates the
  240. initial environment:
  241.  
  242. ~$~<StandardEnv operation~>==~{
  243. #include "termcode.h"
  244.  
  245. Environment
  246. StandardEnv(e)
  247. Environment e;
  248. /* Create the standard environment
  249.  *   On entry-
  250.  *     e=empty environment
  251.  *   On exit-
  252.  *     StandardEnv=e populated with the pre-defined identifiers
  253.  ***/
  254. {
  255.   int Code = Name, Attr;
  256.  
  257. #define StdObj(i) \
  258.   mkidn("i", strlen("i"), &Code, &Attr); i/**/Key = DefineIdn(e, Attr);
  259. ~<Standard objects~>
  260. #undef StdObj
  261.  
  262.   return e;
  263. }
  264. ~}
  265.  
  266. For each standard object, ~{StandardEnv~} obtains the unique integer encoding
  267. of the object's name by invoking ~{mkidn~}.
  268. This is the routine invoked by the lexical analyzer, via the canned
  269. description ~{PASCAL_IDENTIFIER~}, to provide unique encoding for names.
  270. Use of the same routine guarantees the same encoding.
  271.  
  272. The first two arguments to ~{mkidn~} are a pointer to the string to be
  273. encoded and the length of that string.
  274. The third argument is the syntax code that should be associated with the
  275. string on the basis of this instance.
  276. If the string has already been coded, this value is replaced by the syntax
  277. code previously associated with the string.
  278. ~{Name~} is the syntax code associated with Pascal- names by Eli.
  279. Its value is given in file ~{termcode.h~}, which Eli generates.
  280. Upon return from ~{mkidn~}, the variable defined as the fourth argument has
  281. been set to the value of the intrinsic attribute for this string.
  282.  
  283. ~{DefineIdn~} is a library routine that defines a name in an environment,
  284. returning the definition table key associated with that definition.
  285. If the given name has not been defined previously in the given environment,
  286. a new definition table key is generated and associated with the given
  287. name.
  288.  
  289. ~B
  290.  
  291. To complete the specification of the Pascal- scope rules, the phrases that are
  292. blocks, name definitions and name uses must be provided with the properties
  293. associated with those concepts.
  294. Since the concepts are represented by symbols, this can be done simply by having
  295. the symbols for the phrases inherit from the symbols representing the concepts:
  296.  
  297. ~$~<Scope rules for the program~>==~{
  298. SYMBOL Program INHERITS Block END;
  299. SYMBOL ProcedureBlock INHERITS Block END;
  300.  
  301. SYMBOL ConstantNameDef INHERITS NameDef END;
  302. SYMBOL TypeNameDef INHERITS NameDef END;
  303. SYMBOL VariableNameDef INHERITS NameDef END;
  304. SYMBOL ProcedureNameDef INHERITS NameDef END;
  305. SYMBOL ParameterNameDef INHERITS NameDef END;
  306.  
  307. SYMBOL ConstantNameUse INHERITS NameUse END;
  308. SYMBOL TypeNameUse INHERITS NameUse END;
  309. SYMBOL VariableNameUse INHERITS NameUse END;
  310. SYMBOL ProcedureNameUse INHERITS NameUse END;
  311. SYMBOL ParameterNameUse INHERITS NameUse END;
  312. ~}
  313.  
  314. Note that the symbols for these phrases will inherit other concepts,
  315. and may have additional properties that are unique.
  316. These other concepts and properties are defined by other parts of the
  317. specification, independent of the properties discussed in this chapter.
  318.  
  319. ~B~<Specification files for scope analysis~>
  320.  
  321. Most of the Pascal- scope analysis problem is characterized by analogy,
  322. using library modules provided by Eli.
  323. The only component of the scope analysis problem characterized by solution
  324. is the creation of the standard environment.
  325.  
  326. Library modules do not require specification files.
  327. They are instantiated by requests contained in the list of specification.
  328. The relationship between symbols of the library module and symbols of the
  329. grammar must, however, be established by specification files.
  330.  
  331. ~C
  332.  
  333. The scope analysis demanded that a physical representation of the
  334. fictitious ``standard block'' be added to the Pascal- grammar.
  335. This information is conveyed by a type-~{con~} file containing the
  336. necessary phrase.
  337. Eli merges the contents of all type-~{con~} files to produce the final
  338. specification from which the parser is constructed.
  339.  
  340. ~O~<scope.con~>~{
  341. ~<The standard block~>
  342. ~}
  343.  
  344. ~C
  345.  
  346. A type-~{lido~} file is used to describe the relationships between the
  347. library modules and the Pascal- grammar.
  348. It also specifies additional computations to take place during attribution.
  349. The specifications in type-~{lido~} files are merged and used to create the
  350. attribute evaluator.
  351.  
  352. ~O~<scope.lido~>~{
  353. ~<Pascal- scope rule concepts~>
  354. ~<Reporting scope rule violations~>
  355. ~<Scope rules for the standard block~>
  356. ~<Scope rules for the program~>
  357. ~}
  358.  
  359. ~C
  360.  
  361. A type-~{c~} file implements the solution to a problem that is
  362. characterized by solution.
  363. Each such file is the code for a single module.
  364. Type-~{c~} files are ~/not~/ merged by Eli; each is compiled separately.
  365.  
  366. ~O~<scope.c~>==~{
  367. #include "scope.h"
  368.  
  369. ~<Variable definitions in the module body~>
  370. ~<StandardEnv operation~>
  371. ~}
  372.  
  373. ~C
  374.  
  375. A type-~{h~} file defines the interface for a single C module.
  376. It uses C pre-processor directives to ensure that it is included in a given
  377. program no more than once.
  378. Type-~{h~} files are not merged by Eli.
  379.  
  380. ~O~<scope.h~>~{
  381. #ifndef PREDEF_H
  382. #define PREDEF_H
  383.  
  384. #include "deftbl.h"
  385. #include "envmod.h"
  386.  
  387. ~<External declarations in the module interface~>
  388.  
  389. extern Environment StandardEnv(/* Environment e; */);
  390. /* Create the standard environment
  391.  *   On entry-
  392.  *     e=empty environment
  393.  *   On exit-
  394.  *     StandardEnv=e populated with the pre-defined identifiers
  395.  ***/
  396. #endif
  397. ~}
  398.  
  399. ~C
  400.  
  401. A type-~{head~} file is used to incorporate information into the tree
  402. construction and attribution modules.
  403. All type-~{head~} files are merged by Eli into a single file called
  404. ~{HEAD.h~}, and this file is included by the tree construction and
  405. attribution modules.
  406.  
  407. ~O~<scope.head~>~{
  408. #include "scope.h"
  409. ~}
  410.  
  411. The operations of the standard environment creation module are made
  412. available to the computations described in ~{source.lido~}
  413. by including the interface of the standard environment creation module in a
  414. type-~{head~} file (here ~{scope.head~}).
  415.