Cooper_Engineering_a_Compiler(Second Edition) (Rice), страница 70

The primary differences between procedure calls in an ool and an all lie in the mechanism used to name thecallee and in the mechanisms used to locate the callee at runtime.More Complex Control FlowFollowing Scheme, many programming languages allow a program toencapsulate a procedure and its runtime context into an object called aclosure. When the closure is invoked, the procedure executes in the encapsulated runtime context. A simple stack is inadequate to implement this controlabstraction. Instead, the control information must be saved in some moregeneral structure that can represent the more complex control-flow relationship. Similar problems arise if the language allows references to localvariables that outlast a procedure’s activation.SECTION REVIEWIn Algol-like languages, procedures are invoked with a call and theyterminate in a return, unless the procedure diverges.

To translatecalls and returns, the compiler must arrange for the code to record, ateach call, the appropriate return address and to use, at each return, thereturn address that corresponds to the correct call. Using a stack to holdreturn addresses correctly models the last-in, first-out behavior of returnaddresses.One key data structure used to analyze caller–callee relationships is thecall graph. It represents the set of calls between procedures, with anedge from Foe to Fum for each call site in Foe that invokes Fum.

Thus, itcaptures the static relationship between callers and callees definedby the source code. It does not capture the dynamic, or runtime,relationship between procedures; for example, it cannot tell how manytimes the recursive factorial program in Figure 6.2 calls itself.Review Questions1. Many programming languages include a direct transfer of control,often called a goto. Compare and contrast a procedure call and agoto.2. Consider the factorial program shown in Figure 6.2. Write down theexecution history of a call to (fact 5). Explicitly match up the callsand returns.

Show the value of k and of the return value.Closurea procedure and the runtime context that definesits free variables276 CHAPTER 6 The Procedure Abstraction6.3 NAME SPACESScopeIn an Algol-like language, scope refers to a namespace. The term is often used in discussions of thevisibility of names.In most procedural languages, a complete program will contain multiplename spaces. Each name space, or scope, maps a set of names to a set ofvalues and procedures over some set of statements in the code.

This rangemight be the whole program, some collection of procedures, a single procedure, or a small set of statements. The scope may inherit some names fromother scopes. Inside a scope, the programmer can create names that are inaccessible outside the scope. Creating a name, fee, inside a scope can obscuredefinitions of fee in surrounding scopes, in effect making them inaccessibleinside the scope.

Thus, scope rules give the programmer control over accessto information.6.3.1 Name Spaces of Algol-like LanguagesMost programming languages inherit many of the conventions that weredefined for Algol 60. This is particularly true of the rules that govern thevisibility of names. This section explores the notion of naming that prevailsin alls, with particular emphasis on the hierarchical scope rules that applyin such languages.Nested Lexical ScopesLexical scopeScopes that nest in the order that they areencountered in the program are often calledlexical scopes.In lexical scoping, a name refers to the definitionthat is lexically closest to its use−−that is, thedefinition in the closest surrounding scope.Most alls allow the programmer to nest scopes inside one another.

Thelimits of a scope are marked by specific terminal symbols in the programming language. Typically, each new procedure defines a scope that coversits entire definition. Pascal demarcated scopes with a begin at the start andan end at the finish. c uses curly braces, { and }, to begin and end a block;each block defines a new scope.Pascal popularized nested procedures. Each procedure defines a new scope,and the programmer can declare new variables and procedures in each scope.It uses the most common scoping discipline, called lexical scoping.

Thegeneral principle behind lexical scoping is simple:In a given scope, each name refers to its lexically closestdeclaration.Thus, if s is used in the current scope, it refers to the s declared in the currentscope, if one exists. If not, it refers to the declaration of s that occurs in theclosest enclosing scope. The outermost scope contains global variables.To make lexical scoping concrete, consider the Pascal program shown inFigure 6.3.

It contains five distinct scopes, one corresponding to the programMain and one for each of the procedures Fee, Fie, Foe, and Fum. Each procedure declares some set of variables drawn from the set of names x, y, and z.6.3 Name Spaces 277program Main0 (input, output);var x1 ,y1 ,z1 : integer;procedure Fee1 ;var x2 : integer;ScopexyzMainh1, 0ih2, 0ih1, 0ih1, 0ih1, 0ih1, 4ih1, 4ih2, 0ih2, 0ih4, 0ih1, 8ih1, 8ih1, 8ih3, 0ih3, 0iFeebegin { Fee1 }Fiex2 := 1;FoeFumy1 := x2 * 2 + 1end;(b) Static Coordinatesprocedure Fie1 ;var y2 : real;procedure Foe2 ;Mainvar z3 : real;procedure Fum3Feevar y4 : real;Fiebegin { Fum3 }x1 := 1.25 * z3 ;Fee1 ;Foewriteln(‘x = ’,x1 )end;Fumbegin { Foe2 }z3 := 1;(c) Nesting RelationshipsFee1 ;Fum3Mainend;begin { Fie1 }Foe2 ;FieFeewriteln(‘x = ’,x1 )end;Foebegin { Main0 }x1 := 0;Fie1Fumend.(a) Pascal Program(d) Calling Relationshipsn FIGURE 6.3 Nested Lexical Scopes in Pascal.The figure shows each name with a subscript that indicates its level number.Names declared in a procedure always have a level that is one more thanthe level of the procedure name.

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.