K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 71
Текст из файла (страница 71)
Thus, if Main has level 0, as shown, namesdeclared directly in Main, such as x, y, z, Fee, and Fie all have level 1.To represent names in a lexically scoped language, the compiler can use thestatic coordinate for each name. The static coordinate is a pair hl,oi, whereStatic coordinateFor a name x declared in scope s, its staticcoordinate is a pair hl,oi where l is the lexicalnesting level of s and o is the offset where x isstored in the scope’s data area.278 CHAPTER 6 The Procedure AbstractionDYNAMIC SCOPINGThe alternative to lexical scoping is dynamic scoping.
The distinctionbetween lexical and dynamic scoping only matters when a procedurerefers to a variable that is declared outside the procedure’s own scope,often called a free variable.With lexical scoping, the rule is simple and consistent: a free variable isbound to the declaration for its name that is lexically closest to the use. Ifthe compiler starts in the scope containing the use, and checks successivesurrounding scopes, the variable is bound to the first declaration thatit finds. The declaration always comes from a scope that encloses thereference.With dynamic scoping, the rule is equally simple: a free variable is boundto the variable by that name that was most recently created at runtime.Thus, when execution encounters a free variable, it binds that free variableto the most recent instance of that name. Early implementations created aruntime stack of names, on which every name was pushed as its declarationwas encountered.
To bind a free variable, the running code searched thename stack from its top downward until a variable with the right name wasfound. Later implementations are more efficient.While many early Lisp systems used dynamic scoping, lexical scoping hasbecome the dominant choice. Dynamic scoping is easy to implement in aninterpreter and somewhat harder to implement efficiently in a compiler.It can create bugs that are difficult to detect and hard to understand.Dynamic scoping still appears in some languages; for example, CommonLisp still allows the program to specify dynamic scoping.l is the name’s lexical nesting level and o is the its offset in the data areafor level l. To obtain l, the front end uses a lexically scoped symbol table,as described in Section 5.5.3. The offset, o, should be stored with the nameand its level in the symbol table.
(Offsets can be assigned when declarationsare processed during context-sensitive analysis.) The table on the right sideof Figure 6.3 shows the static coordinate for each variable name in eachprocedure.The second part of name translation occurs during code generation. Thecompiler must use the static coordinate to locate the value at runtime. Givena coordinate hl,oi, the code generator must emit code that translates l intothe runtime address of the appropriate data area. Then, it can use the offset oto compute the address for the variable corresponding to hl,oi.
Section 6.4.3describes two different ways to accomplish this task.6.3 Name Spaces 279Scope Rules across Various LanguagesProgramming language scope rules vary idiosyncratically from language tolanguage. The compiler writer must understand the specific rules of a sourcelanguage and must adapt the general translation schemes to work with thesespecific rules. Most alls have similar scope rules. Consider the rules for thelanguages fortran, c, and Scheme:nnnfortran has a simple name space.
A fortran program creates a singleglobal scope, along with a local scope for each procedure or function.Global variables are grouped together in a “common block”; eachcommon block consists of a name and a list of variables. The globalscope holds the names of procedures and common blocks. Globalnames have lifetimes that match the lifetime of the program.
Aprocedure’s scope holds parameter names, local variables, and labels.Local names obscure global names if they conflict. Names in the localscope have, by default, lifetimes that match an invocation of theprocedure, The programmer can give a local variable the lifetime of aglobal variable by listing it in a save statement.c has more complex rules. A c program has a global scope forprocedure names and global variables. Each procedure has a local scopefor variables, parameters, and labels. The language definition does notallow nested procedures, although some compilers have implementedthis feature as an extension. Procedures can contain blocks (set off withleft and right braces) that create separate local scopes; blocks can benested.
Programmers often use a block-level scope to create temporarystorage for code generated by a preprocessor macro or to create a localvariable whose scope is the body of a loop.c introduces another scope: the file-level scope. This scope includesnames declared as static that not enclosed in a procedure. Thus,static procedures and functions are in the file-level scope, as are anystatic variables declared at the outermost level in the file.
Withoutthe static attribute, these names would be global variables. Names inthe file-level scope are visible to any procedure in the file, but are notvisible outside the file. Both variables and procedures can be declaredstatic.Scheme has a simple set of scope rules. Almost all objects in Schemereside in a single global space. Objects can be data or executableexpressions. System-provided functions, such as cons, live alongsideuser-written code and data items. Code, which consists of an executableexpression, can create private objects by using a let expression.Nesting let expressions inside one another can create nested lexicalscopes of arbitrary depth.Separate compilation makes it hard for FORTRANcompilers to detect different declarations for acommon block in distinct files.
Thus, the compilermust translate common-block references intohblock, offseti pairs to produce correct behavior.Static nameA variable declared as static retains its valueacross invocations of its defining procedure.Variables that are not static are called automatic.280 CHAPTER 6 The Procedure Abstraction6.3.2 Runtime Structures to Support Algol-likeLanguagesActivation recorda region of storage set aside to hold controlinformation and data storage associated with asingle instance of a single procedureTo implement the twin abstractions of procedure calls and scoped namespaces, the translation must establish a set of runtime structures. The keydata structure involved in both control and naming is the activation record(ar), a private block of memory associated with a specific invocation of aspecific procedure. In principle, every procedure call gives rise to a new ar.nnnnThe compiler must arrange for each call to store the return addresswhere the callee can find it.
The return address goes into the ar.The compiler must map the actual parameters at the call site into theformal parameter names by which they are known in the callee. To doso, it stores ordered parameter information in the ar.The compiler must create storage space for variables declared in thecallee’s local scope. Since these values have lifetimes that match thelifetime of the return address, it is convenient to store them in the ar.The callee needs other information to connect it to the surroundingprogram, and to allow it to interact safely with other procedures.
Thecompiler arranges to store that information in the callee’s ar.Since each call creates a new ar, when multiple instances of a procedureare active, each has its own ar. Thus, recursion gives rise to multiple ars,each of which holds the local state for a different invocation of the recursiveprocedure.Activation record pointerTo locate the current AR the compiler arranges tokeep a pointer to the AR, the activation recordpointer, in a designated register.Figure 6.4 shows how the contents of an ar might be laid out. The entire aris addressed through an activation record pointer (arp), with various fieldsin the ar found at positive and negative offsets from the arp. The ars inFigure 6.4 have a number of fields.nnnnnnnThe parameter area holds actual parameters from the call site, in anorder that corresponds to their order of appearance at the call.The register save area contains enough space to hold registers that theprocedure must preserve due to procedure calls.The return-value slot provides space to communicate data from thecallee back to the caller, if needed.The return-address slot holds the runtime address where executionshould resume when the callee terminates.The “addressability” slot holds information used to allow the callee toaccess variables in surrounding lexical scopes (not necessarily thecaller).The slot at the callee’s arp stores the caller’s arp.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
