|
|
|
|
General Information
Tutorials
Reference Manuals
Libraries
Translation Tasks
Tools
Administration
|
|
Tutorial for Name Analysis Using ScopeGraphs
Multiple Scope GraphsThe scope graph is the basic data structure for name analysis (see Fundamentals of Name Analysis of Name Analysis Reference Manual). Its structure embodies the relationships among ranges dictated by scope rules, and its content reflects the set of defining occurrences subject to those rules. There are two reasons that a processor specification may require more than one scope graph:
Reusing identifiers in the same scopeIt's hard to think up names! Suppose that, as language designers, we allow a programmer to use the same identifier to represent a package, a class, a variable, and a method in a single range. If we, as developers, can decide which of these is meant on the basis of context then we can use distinct scope graphs to obtain the proper defining occurrence for each applied occurrence. Here is an example: mgcd.nl[106]==
import gcd.*;
class gcd { int z; }
int gcd;
int gcd(int x, int y) {
while (x != y) {
if (x > y) x = x - y;
else y = y - x;
}
return x;
}
{ gcd c;
gcd = gcd(c.z, w); }
package gcd;
int w;
This macro is attached to a non-product file.
The program in `mgcd.nl' contains four
applied occurrences of An Eli-generated processor needs four scope graphs to support that intuition, each modeling the bindings for one kind of entity. Because the scope rules are the same for all of the identifiers naming those entities, the scope graphs will have the same structure but different contents; the graphs themselves are isomorphic (see Isomorphic Scope Graphs of Name Analysis Reference Manual).
A single instantiation of the ScopeGraphs.h content[107]== #define MaxIsoGraphs 4 This macro is defined in definitions 72, 107, and 109. This macro is invoked in definition 73.
The actual number of isomorphic scope graphs associated with a single
instantiation of the module is specified by the Abstract syntax tree[108]== SYMBOL Collection COMPUTE SYNT.NumberOfIsoGraphs=4; 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. Each graph is indexed by a integer whose value is between 0 and 3. Values larger that 3 can be used to give information about the syntactic context, but indicate that the specific graph to be used either is unknown or must be computed. (We call these weak contexts to distinguish them from the strong contexts where the specific graph can be determined.) It's a good idea to use a symbolic name instead of a numeric value when specifying a graph index. Appropriate names can be defined as a C enumeration in `ScopeGraphs.h': ScopeGraphs.h content[109]==
enum {
packageGraph, classGraph, variableGraph, methodGraph,
packageOrClassContext, ambiguousContext
};
This macro is defined in definitions 72, 107, and 109. This macro is invoked in definition 73.
The first four identifiers, whose representations end in
Each defining or applied occurrence has a
When the module instantiation supports several isomorphic scope graphs, the
developer must override the default values of the Abstract syntax tree[110]== ATTR GraphIndex: int; SYMBOL PackageDefName COMPUTE INH.GraphIndex = packageGraph; END; SYMBOL ClassDefName COMPUTE INH.GraphIndex = classGraph; END; SYMBOL VarDefName COMPUTE INH.GraphIndex = variableGraph; END; SYMBOL ParamDefName COMPUTE INH.GraphIndex = variableGraph; END; SYMBOL MethodDefName COMPUTE INH.GraphIndex = methodGraph; 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. Applied occurrences are always components of the complete names that we have defined throughout this document (see Qualified names). As language designers, we must state NameLan rules for the context of each complete name, and then as developers derive LIDO computations to implement them. Here we write just the LIDO computation for each such context, however, leaving it to you to deduce an appropriate NameLan rule: Abstract syntax tree[111]== RULE: ClassName ::= Name COMPUTE Name.GraphIndex = classGraph; END; RULE: ExprName ::= Name COMPUTE Name.GraphIndex = variableGraph; END; RULE: MethName ::= Name COMPUTE Name.GraphIndex = methodGraph; END; RULE: WithName ::= Name COMPUTE Name.GraphIndex = variableGraph; END; RULE: SuperClass ::= WLName COMPUTE WLName.GraphIndex = classGraph; END; RULE: ImportName ::= WLName COMPUTE WLName.GraphIndex = classGraph; END; RULE: PCName ::= WLName COMPUTE WLName.GraphIndex = packageOrClassContext; 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.
Note that all but one of these complete names is in a strong context.
The only weak context is the Once we know the context of a complete name, we need to analyze the applied occurrences making up that name. The context for a complete name applies only to the rightmost applied occurrence of that complete name. If the complete name is a simple name, the computations are: Abstract syntax tree[112]== RULE: Name ::= SimpleName COMPUTE SimpleName.GraphIndex = Name.GraphIndex; END; RULE: WLName ::= SimpleWLName COMPUTE SimpleWLName.GraphIndex = WLName.GraphIndex; 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 NameLan rules that we, as language designers, have formulated to define the meanings of other applied occurrences come in two parts: definition of the weak contexts of any qualifiers, and then resolution of those weak contexts by selecting possible bindings. The rules for qualifier contexts are:
Here is a LIDO implementation of these rules: Abstract syntax tree[113]==
RULE: Name ::= Name '.' QualifiedId COMPUTE
QualifiedId.GraphIndex = Name[1].GraphIndex;
Name[2].GraphIndex =
IF(EQ(Name[1].GraphIndex,classGraph),
packageOrClassContext,
IF(EQ(Name[1].GraphIndex,packageOrClassContext),
packageOrClassContext,
ambiguousContext));
END;
RULE: WLName ::= WLName '.' QualifiedWLId COMPUTE
QualifiedWLId.GraphIndex = WLName[1].GraphIndex;
WLName[2].GraphIndex = packageOrClassContext;
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
If the value of the
Eli's default version of ambig.nl[114]==
import v.*;
class A {
class C { int x; }
}
A v;
{ v.C x;
v.C.x = 0; }
package v;
class C { int x; }
This macro is attached to a non-product file.
Consider the two uses of The solution is to explain the choice as a reclassification of the context, based on the results of the searches. This reclassification turns a weak context into a strong context, which requires the desired selection. Here are our rules for NameLan:
Note that these rules do not require any actual modification of any
Implementation of the NameLan reclassification[115]==
if (GraphIndex == packageOrClassContext) {
if (G[classGraph] != NoKey) return G[classGraph];
return G[packageGraph];
}
if (GraphIndex == ambiguousContext) {
if (G[variableGraph] != NoKey) return G[variableGraph];
if (G[classGraph] != NoKey) return G[classGraph];
return G[packageGraph];
}
This macro is invoked in definition 116.
The simplest way to complete the implementation is to download Eli's version
of
-> $elipkg/Name/DisambiguateGraphs.c > DisambiguateGraphs.c[116]==
#include "deftbl.h"
#include "pdl_gen.h"
#include "ScopeGraphs.h"
DefTableKey
DisambiguateGraphs (DefTableKey G[], int N, DefTableKey app)
/* On entry-
* G[] is an array with N elements giving the result for each search
* app is the UseKey of the applied occurrence sought
* On exit-
* DisambiguateGraphs is the selected key
***/
{ int GraphIndex = GetGraphIndex(app, 0);
Implementation of the NameLan reclassification[115]
return NoKey;
}
This macro is attached to a product file.
`DisambiguateGraphs.c' must be included in the list of specifications: Specification files[117]== DisambiguateGraphs.c 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%Kinds > . None of these files will have write permission in your current directory.
Constructs obeying different scope rulesConsider the task of reading integer values from a file until the current number would cause the running sum to exceed the first value on the file. The program must print the number of values making up the final sum. The problem here is that there are two conditions under which to exit the loop: either the data runs out or the preset value is exceeded. As language designers, we can extend NameLan to simplify the solution to this problem: Phrase structure[118]==
Statement: Loop / 'break' Ident ';'.
Loop: Ident ':' 'while' '(' Expr ')' Statement.
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. Here is a program that uses the extension: maxsum.nl[119]==
import stdio.*;
{ int sum = 0, count = 0, below;
below = getint();
loop: while (feof(stdin) == 0) {
int next = sum + getint();
if (next > below) break loop;
sum = next; count = count + 1;
}
putint(count);
}
package stdio;
class file { }
file stdin;
int feof(file f) { }
int getint() { }
void putint(int v) { }
This macro is attached to a non-product file.
As developers, we need new abstract syntax symbols to distinguish
the two new contexts for an identifier
(see Representation of identifiers of Name Analysis Reference Manual).
The obvious choices are Abstract syntax of identifiers[120]==
RULE: Loop ::= LabelDef ':' 'while' '(' Expr ')' Statement END;
RULE: LabelDef ::= Ident END;
RULE: Statement ::= 'break' LabelUse ';' END;
RULE: LabelUse ::= Ident END;
This macro is defined in definitions 8, 9, 26, 31, 33, 42, 51, and 120. This macro is invoked in definition 10.
The
The key point for name analysis of labels is that this scope rule
requires a scope graph whose structure is completely different from
that of the scope graphs we have been using.
It therefore cannot be implemented by isomorphism, but requires an
additional instantiation of the Specification files[121]== $/Name/ScopeGraphs.gnrc +instance=LBL_ :inst $/Name/SGProof.gnrc +instance=LBL_+referto=Ident :inst 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.
The Abstract syntax tree[122]== SYMBOL Loop INHERITS LBL_RangeScope END; SYMBOL LabelDef INHERITS LBL_IdDefScope END; SYMBOL LabelUse INHERITS LBL_GCSimpleName, LBL_ChkIdUse 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%Labels > . 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.
|
