|
|
|
|
General Information
Tutorials
Reference Manuals
Libraries
Translation Tasks
Tools
Administration
|
|
Tutorial for Name Analysis Using ScopeGraphs
Libraries
It's rare that a program is developed by one person, without reference to
the work of others.
Usually a programmer relies on a number of libraries for things like
common computations (e.g. There are many strategies for linking with library files, but all must support the basic name analysis concepts. For the purposes of this tutorial, we will assume that the processor input is a concatenation of source files. That concatenation will begin with the program file, followed by any number of library files. Eli provides mechanisms for collecting source files into a single input, but these are beyond the scope of this tutorial (see Insert a File into the Input Stream of Tasks related to input processing).
Without use of additional facilities, a generated processor named
cat pgmfile libfile libfile | ./procIn the remainder of this tutorial, any examples illustrating libraries will be single files that are the result of a concatenation. We will extend NameLan by defining each library file as an entity called a package. File `pkg.nl' illustrates this extension: pkg.nl[49]==
{ float rate;
rate = verbs.fly.distance / insects.fly.legs;
}
package insects;
class ant { }
class fly { int legs; }
class bee { }
package verbs;
class run { }
class fly { int distance; }
This macro is attached to a non-product file.
Our original grammar's root symbol was Phrase structure[50]== Collection: Pgmfile Libfile*. Pgmfile: Program. Libfile: 'package' Ident ';' PackageBody. PackageBody: Declaration*. This macro is defined in definitions 2, 25, 30, 32, 41, 50, 55, 67, 76, 97, 118, and 124. This macro is invoked in definition 3.
We need a new abstract syntax symbol to distinguish the new context
for identifiers
(see Representation of identifiers of Name Analysis Reference Manual).
The obvious choice is Abstract syntax of identifiers[51]== RULE: Libfile ::= 'package' PackageDefName ';' PackageBody END; RULE: PackageDefName ::= Ident END; This macro is defined in definitions 8, 9, 26, 31, 33, 42, 51, and 120. This macro is invoked in definition 10. Here are our new and modified scope rules for NameLan with packages:
Since Abstract syntax tree[52]== SYMBOL Program INHERITS RangeScope END; This macro is defined in definitions 10, 18, 22, 38, 47, 52, 53, 65, 69, 71, 88, 89, 92, 93, 95, 96, 101, 105, 108, 110, 111, 112, 113, 122, 133, 134, 135, 136, 137, 144, and 153. This macro is invoked in definition 11. The LIDO implementation of the remaining roles is left as an exercise.
The ownership relation between a package and its members
is established by overriding the default computation for the
Abstract syntax tree[53]== RULE: Libfile ::= 'package' PackageDefName ';' PackageBody COMPUTE Libfile.Key = PackageDefName.Key; END; SYMBOL PackageBody COMPUTE INH.ScopeKey = INCLUDING Libfile.Key; END; This macro is defined in definitions 10, 18, 22, 38, 47, 52, 53, 65, 69, 71, 88, 89, 92, 93, 95, 96, 101, 105, 108, 110, 111, 112, 113, 122, 133, 134, 135, 136, 137, 144, and 153. This macro is invoked in definition 11.
ExercisesThese exercises are based on files defined in the Tutorial. To obtain copies of those files in your current directory, enter Eli and give the following command:
-> $elipkg/Name/LearnSG%Pack > .None of these files will have write permission in your current directory.
Single importA single import construct makes it possible to refer to a single entity defined in some package by a simple name rather than a qualified name. For example, consider file `single.nl': single.nl[54]==
import P.D.m;
import Q.C.a;
{ a = 42; m(); }
package Q;
import P.D;
class C extends D {
int a;
void m() {
a = b;
}
}
package P;
class D {
int b;
void m() {
b = Q.C.a;
}
}
This macro is attached to a non-product file.
Single imports are used here to allow the program to refer to
variable In order to implement single imports, we need to think about how a single import interacts with the entities defined in the program or package. The nature of these interactions is specified by the language designer, and there are several possibilities. We will describe the decision that we made for NameLan, and show how that decision leads to a phrase structure. Other decisions would lead to other structures.
As language designers, we consider imports to be a convenience for
the programmer that should not have any effect beyond the obvious
one illustrated by `single.nl'.
We therefore do not want the scope of an imported binding to be
the
If the scope of an imported binding were a phrase that encompassed
the program or package body, then that binding could be referred to by a
simple name within the program or package body unless it was hidden
by a local defining occurrence.
Although the We can avoid these undesired effects if we establish a structure for a program containing import declarations that has an additional phrase encompassing the file body, but not the import declarations. The desired structure can be defined by adding six productions to the NameLan grammar: Phrase structure[55]== Pgmfile: ImportDecls PgmFileBody. PgmFileBody: Program. Libfile: 'package' Ident ';' ImportDecls LibFileBody. LibFileBody: PackageBody. ImportDecls: ImportDecl+. ImportDecl: 'import' WLName ';'. This macro is defined in definitions 2, 25, 30, 32, 41, 50, 55, 67, 76, 97, 118, and 124. This macro is invoked in definition 3.
The first and second productions introduce a new phrase
To see how this grammar addition has the desired effect, consider
`single.nl'.
Notice that we have chosen to derive the name of the imported entity from
Make contexts of complete names explicit[56]== RULE: ImportDecl ::= 'import' ImportName ';' END; RULE: ImportName ::= WLName END; This macro is defined in definitions 37, 44, 56, 57, 68, 77, and 98. This macro is invoked in definition 38.
There is also a new context for Make contexts of complete names explicit[57]==
RULE: Libfile ::=
'package' PackageDefName ';' ImportDecls LibFileBody
COMPUTE
Libfile.Key = PackageDefName.Key;
END;
This macro is defined in definitions 37, 44, 56, 57, 68, 77, and 98. This macro is invoked in definition 38. Here are the corresponding scope rules:
Inherit the appropriate roles[58]== SYMBOL PgmFileBody INHERITS RangeScope END; SYMBOL LibFileBody INHERITS RangeScope END; This macro is defined in definitions 58 and 59. This macro is invoked in definition 65.
An Inherit the appropriate roles[59]== SYMBOL ImportName INHERITS WLInsertDef END; This macro is defined in definitions 58 and 59. This macro is invoked in definition 65.
We must write computations to set the values of four of these five
Set WLInsertDef attributes[60]==
RULE: ImportName ::= WLName COMPUTE
ImportName.Sym = WLName.Sym;
ImportName.UseKey = WLName.UseKey;
ImportName.DependsOn = WLName.FPItem;
END;
SYMBOL ImportName COMPUTE
INH.Scope =
INCLUDING (Pgmfile.ImportEnv, Libfile.ImportEnv);
END;
This macro is defined in definitions 60, 61, 62, and 63. This macro is invoked in definition 65.
The Set WLInsertDef attributes[61]== SYMBOL WLName: UseKey: DefTableKey; RULE: WLName ::= SimpleWLName COMPUTE WLName.Sym = SimpleWLName.Sym; WLName.UseKey = SimpleWLName.UseKey; END; RULE: WLName ::= WLName '.' QualifiedWLId COMPUTE WLName[1].Sym = QualifiedWLId.Sym; WLName[1].UseKey = QualifiedWLId.UseKey; END; This macro is defined in definitions 60, 61, 62, and 63. This macro is invoked in definition 65.
In order to obtain a value for Set WLInsertDef attributes[62]== ATTR ImportEnv: NodeTuplePtr; RULE: Pgmfile ::= Program COMPUTE Pgmfile.ImportEnv = NoNodeTuple; END; RULE: Libfile ::= 'package' PackageDefName ';' PackageBody COMPUTE Libfile.ImportEnv = NoNodeTuple; END; This macro is defined in definitions 60, 61, 62, and 63. This macro is invoked in definition 65.
If import declarations are present, the additional scope for
those bindings is the associated Set WLInsertDef attributes[63]==
RULE: Pgmfile ::= ImportDecls PgmFileBody COMPUTE
Pgmfile.ImportEnv = PgmFileBody.Env;
END;
RULE: Libfile ::=
'package' PackageDefName ';' ImportDecls LibFileBody
COMPUTE
Libfile.ImportEnv = LibFileBody.Env;
END;
This macro is defined in definitions 60, 61, 62, and 63. This macro is invoked in definition 65.
The intent of the statement
import Q.C.m;The result is a contradiction, allowing two distinct entities to have the same simple name m, and an error must be reported
(see Source Text Coordinates and Error Reporting of The Eli Library).
When a single import collides with another one, the value of its
ImportName.Key attribute differs from the value of the
WLName.Key attribute
(see Worklist search of Name Analysis Reference Manual).
Again, WLName.Key is the Key attribute of the rightmost
applied occurrence:
Report a collision error in a single import[64]==
RULE: ImportName ::= WLName COMPUTE
IF(NE(ImportName.Key, WLName.Key),
message(
ERROR,
CatStrInd("Ambiguous import: ", WLName.Sym),
0,
COORDREF));
END;
This macro is invoked in definition 65. Attaching the LIDO specifications to the abstract syntax tree: Abstract syntax tree[65]== Inherit the appropriate roles[58] Set WLInsertDef attributes[60] Report a collision error in a single import[64] This macro is defined in definitions 10, 18, 22, 38, 47, 52, 53, 65, 69, 71, 88, 89, 92, 93, 95, 96, 101, 105, 108, 110, 111, 112, 113, 122, 133, 134, 135, 136, 137, 144, and 153. This macro is invoked in definition 11.
ExercisesThese exercises are based on files defined in the Tutorial. To obtain copies of those files in your current directory, enter Eli and give the following command:
-> $elipkg/Name/LearnSG%Single > .None of these files will have write permission in your current directory. You will need to add write permission in order to do the exercises.
Import on demandAn import on demand is used to make it possible to refer to every entity declared in a package (or a class) by a simple name rather a qualified name. Here is an example: demand.nl[66]==
import insects.*;
{ float rate;
rate = verbs.fly.distance / fly.legs;
}
package insects;
class ant { }
class fly { int legs; }
class bee { }
package verbs;
class run { }
class fly { int distance; }
This macro is attached to a non-product file.
The import declaration in `demand.nl' makes all of the
members of the package Here is the addition to the NameLan concrete syntax that supports import on demand: Phrase structure[67]== ImportDecl: 'import' WLName '.' '*' ';'. This macro is defined in definitions 2, 25, 30, 32, 41, 50, 55, 67, 76, 97, 118, and 124. This macro is invoked in definition 3. We shall see that this declaration adds a path edge to the scope graph, and therefore its applied occurrence must be sought using the worklist algorithm.
A new abstract syntax symbol is needed to represent the occurrence of a
Make contexts of complete names explicit[68]== RULE: ImportDecl ::= 'import' PCName '.' '*' ';' END; RULE: PCName ::= WLName END; This macro is defined in definitions 37, 44, 56, 57, 68, 77, and 98. This macro is invoked in definition 38. Our scope rules governing NameLan's import on demand construct are:
The intent of the statement
Each import on demand can be modeled by a path edge whose tail is
the scope graph node created for the The semantics of a path edge modeling an import on demand differ from those of a path edge modeling inheritance. We therefore need to use a second edge label for import edges (see Scope graphs of Name Analysis Reference Manual). Eli allows us to use the default edge label 1 without comment, and we have taken advantage of this avoid specifying edge labels. The result is that Eli has silently used the label 1 to indicate an inheritance edge. We will use the label 2 to indicate an import edge.
Adding an import path edge to the scope graph is similar to
adding an inheritance path edge (see Inheritance).
The only real difference is that we must specify the Abstract syntax tree[69]== SYMBOL PCName INHERITS WLCreateEdge COMPUTE SYNT.tailEnv = INCLUDING AnyScope.Env; SYNT.label = 2; END; RULE: PCName ::= WLName COMPUTE PCName.tipFPItem = WLName.FPItem; END; This macro is defined in definitions 10, 18, 22, 38, 47, 52, 53, 65, 69, 71, 88, 89, 92, 93, 95, 96, 101, 105, 108, 110, 111, 112, 113, 122, 133, 134, 135, 136, 137, 144, and 153. This macro is invoked in definition 11. Import edges do not address the scope rule that prohibits hiding. Consider the following program: hide.nl[70]==
import hide.*;
{ float rate;
rate = verbs.fly.distance / insects.fly.legs;
}
package insects;
class ant { }
class fly { int legs; }
class bee { }
package verbs;
class run { }
class fly { int distance; }
package hide;
class insects { }
class verbs { }
This macro is attached to a non-product file.
When the applied occurrences
If there had been no import on demand, bindings for
We can solve the problem by creating an edge from each scope graph
node created for a
Neither the tips nor the tails of these bypass edges are defined by names.
Therefore the Abstract syntax tree[71]== SYMBOL Toplevel INHERITS BoundEdge COMPUTE SYNT.tailEnv = THIS.Env; SYNT.tipEnv = INCLUDING Collection.Env; SYNT.label = 3; END; SYMBOL Program INHERITS Toplevel END; SYMBOL PackageBody INHERITS Toplevel END; This macro is defined in definitions 10, 18, 22, 38, 47, 52, 53, 65, 69, 71, 88, 89, 92, 93, 95, 96, 101, 105, 108, 110, 111, 112, 113, 122, 133, 134, 135, 136, 137, 144, and 153. This macro is invoked in definition 11.
Because we now have more than one edge label, we must define
ScopeGraphs.h content[72]== #define MaxKindsPathEdge 3 This macro is defined in definitions 72, 107, and 109. This macro is invoked in definition 73. We must protect against `ScopeGraphs.h' being included more than once in some C compilation. Conventionally, Eli uses the name of the include file, in capital letters with dots replaced by underscores, as the controlling symbol: ScopeGraphs.h[73]== #ifndef SCOPEGRAPHS_H #define SCOPEGRAPHS_H ScopeGraphs.h content[72] #endif This macro is attached to a product file. We must add `ScopeGraphs.h' to the set of specification files: Specification files[74]== ScopeGraphs.h This macro is defined in definitions 12, 16, 23, 27, 74, 78, 81, 91, 117, 121, 139, 142, 146, and 152. This macro is invoked in definition 13.
ExercisesThese exercises are based on files defined in the Tutorial. To obtain copies of those files in your current directory, enter Eli and give the following command:
-> $elipkg/Name/LearnSG%Demand > . None of these files will have write permission in your current directory. You will need to add write permission in order to do the exercises.
|
