K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 69
Текст из файла (страница 69)
In fortran, two variables can be forced to begin at the same storagelocation with an equivalence statement. For example, the followingstatement forces a and b to share storage:equivalence (a,b)Can the compiler keep a local variable in a register throughout theprocedure if that variable appears in an equivalence statement? Justifyyour answer.10.
Some part of the compiler must be responsible for entering eachidentifier into the symbol table.a. Should the scanner or the parser enter identifiers into the symboltable? Each has an opportunity to do so.b. Is there an interaction between this issue, declare-before-use rules,and disambiguation of subscripts from function calls in a languagewith the FORTRAN 77 ambiguity?11. The compiler must store information in the ir version of the programthat allows it to get back to the symbol table entry for each name.Among the options open to the compiler writer are pointers to theSection 5.5268 CHAPTER 5 Intermediate Representations1234567891011121314151617procedure maininteger a, b, c;procedure f1(w,x);integer a,x,y;call f2(w,x);end;procedure f2(y,z)integer a,y,z;procedure f3(m,n)integer b, m, n;c = a * b * m * n;end;call f3(c,z);end;...call f1(a,b);end;n FIGURE 5.16 Program for Exercise 12.original character strings and subscripts into the symbol table.
Ofcourse, the clever implementor may discover other options.What are the advantages and disadvantages of each of theserepresentations for a name? How would you represent the name?12. You are writing a compiler for a simple lexically-scoped language.Consider the example program shown in Figure 5.16.a. Draw the symbol table and its contents at line 11.b. What actions are required for symbol table management when theparser enters a new procedure and when it exits a procedure?13.
The most common implementation technique for a symbol table usesa hash table, where insertion and deletion are expected to have O(1)cost.a. What is the worst-case cost for insertion and for deletion in a hashtable?b. Suggest an alternative implementation scheme that guaranteesO(1) insertion and deletion.Chapter6The Procedure AbstractionnCHAPTER OVERVIEWProcedures play a critical role in the development of software systems.They provide abstractions for control flow and naming.
They provide basicinformation hiding. They are the building block on which systems provideinterfaces. They are one of the principal forms of abstraction in Algol-likelanguages; object-oriented languages rely on procedures to implement theirmethods or code members.This chapter provides an in-depth look at the implementation of proceduresand procedure calls, from the perspective of a compiler writer. Along theway, it highlights the implementation similarities and differences betweenAlgol-like languages and object-oriented languages.Keywords: Procedure Calls, Parameter Binding, Linkage Conventions6.1 INTRODUCTIONThe procedure is one of the central abstractions in most modern programming languages.
Procedures create a controlled execution environment;each procedure has its own private named storage. Procedures help defineinterfaces between system components; cross-component interactions aretypically structured through procedure calls. Finally, procedures are the basicunit of work for most compilers. A typical compiler processes a collection ofprocedures and produces code for them that will link and execute correctlywith other collections of compiled procedures.This latter feature, often called separate compilation, allows us to build largesoftware systems. If the compiler needed the entire text of a program for eachcompilation, large software systems would be untenable. Imagine recompiling a multimillion line application for each editing change made duringEngineering a Compiler.
DOI: 10.1016/B978-0-12-088478-0.00006-2c 2012, Elsevier Inc. All rights reserved.Copyright 269270 CHAPTER 6 The Procedure Abstractiondevelopment! Thus, procedures play as critical a role in system design andengineering as they do in language design and compiler implementation.This chapter focuses on how compilers implement the procedure abstraction.Conceptual RoadmapTo translate a source-language program into executable code, the compilermust map all of the source-language constructs that the program uses intooperations and data structures on the target processor.
The compiler needs astrategy for each of the abstractions supported by the source language. Thesestrategies include both algorithms and data structures that are embedded intothe executable code. These runtime algorithms and data structures combineto implement the behavior dictated by the abstraction. These runtime strategies also require support at compile time in the form of algorithms and datastructures that run inside the compiler.This chapter explains the techniques used to implement procedures andprocedure calls. Specifically, it examines the implementation of control,of naming, and of the call interface. These abstractions encapsulate manyof the features that make programming languages usable and that enableconstruction of large-scale systems.OverviewCalleeIn a procedure call, we refer to the procedure thatis invoked as the callee.CallerIn a procedure call, we refer to the callingprocedure as the caller.The procedure is one of the central abstractions that underlie most modernprogramming languages.
Procedures create a controlled execution environment. Each procedure has its own private named storage. Statementsexecuted inside the procedure can access the private, or local, variables inthat private storage. A procedure executes when it is invoked, or called, byanother procedure (or the operating system). The callee may return a valueto its caller, in which case the procedure is termed a function.
This interfacebetween procedures lets programmers develop and test parts of a programin isolation; the separation between procedures provides some insulationagainst problems in other procedures.Procedures play an important role in the way that programmers develop software and that compilers translate programs. Three critical abstractions thatprocedures provide allow the construction of nontrivial programs.1. Procedure Call Abstraction Procedural languages support anabstraction for procedure calls. Each language has a standardmechanism to invoke a procedure and map a set of arguments, orparameters, from the caller’s name space to the callee’s name space.This abstraction typically includes a mechanism to return control to the6.1 Introduction 271caller and continue execution at the pointimmediately after the call.Most languages allow a procedure to return one or more values to thecaller.
The use of standard linkage conventions, sometimes referred toas calling sequences, lets the programmer invoke code written andcompiled by other people and at other times; it lets the applicationinvoke library routines and system services.2. Name Space In most languages, each procedure creates a new andprotected name space. The programmer can declare new names, such asvariables and labels, without concern for the surrounding context.
Insidethe procedure, those local declarations take precedence over any earlierdeclarations for the same names. The programmer can create parametersfor the procedure that allow the caller to map values and variables in thecaller’s name space into formal parameters in the callee’s name space.Because the procedure has a known and separate name space, it canfunction correctly and consistently when called from different contexts.Executing a call instantiates the callee’s name space.
The call mustcreate storage for the objects declared by the callee. This allocationmust be both automatic and efficient—a consequence of calling theprocedure.3. External Interface Procedures define the critical interfaces among theparts of large software systems. The linkage convention defines rulesthat map names to values and locations, that preserve the caller’sruntime environment and create the callee’s environment, and thattransfer control from caller to callee and back. It creates a context inwhich the programmer can safely invoke code written by other people.The existence of uniform calling sequences allows the development anduse of libraries and system calls. Without a linkage convention, both theprogrammer and the compiler would need detailed knowledge about theimplementation of the callee at each procedure call.Thus, the procedure is, in many ways, the fundamental abstraction thatunderlies Algol-like languages.
It is an elaborate facade created collaboratively by the compiler and the underlying hardware, with assistancefrom the operating system. Procedures create named variables and mapthem to virtual addresses; the operating system maps virtual addresses tophysical addresses. Procedures establish rules for visibility of names andaddressability; the hardware typically provides several variants of load andstore operations. Procedures let us decompose large software systems intocomponents; linkers and loaders knit these together into an executable program that the hardware can execute by advancing its program counter andfollowing branches.Linkage conventionan agreement between the compiler andoperating system that defines the actions takento call a procedure or functionActual parameterA value or variable passed as a parameter at a callsite is an actual parameter of the call.Formal parameterA name declared as a parameter of someprocedure p is a formal parameter of p.272 CHAPTER 6 The Procedure AbstractionA WORD ABOUT TIMEThis chapter deals with both compile-time and runtime mechanisms.
Thedistinction between events that occur at compile time and those thatoccur at runtime can be confusing. The compiler generates all the codethat executes at runtime. As part of the compilation process, the compileranalyzes the source code and builds data structures that encode the resultsof the analysis. (Recall the discussion of lexically scoped symbol tables inSection 5.5.3.) The compiler determines much of the storage layout thatthe program will use at runtime. It then generates the code needed tocreate that layout, to maintain it during execution, and to access both dataobjects and code in memory.
When the compiled code runs, it accessesdata objects and calls procedures or methods. All of the code is generatedat compile time; all of the accesses occur at runtime.A large part of the compiler’s task is putting in place the code needed torealize the various pieces of the procedure abstraction. The compiler mustdictate the layout of memory and encode that layout in the generated program. Since it may compile the different components of the program atdifferent times, without knowing their relationships to one another, thismemory layout and all the conventions that it induces must be standardizedand uniformly applied. The compiler must also use the various interfacesprovided by the operating system, to handle input and output, managememory, and communicate with other processes.This chapter focuses on the procedure as an abstraction and the mechanismsthat the compiler uses to establish its control abstraction, name space, andinterface to the outside world.6.2 PROCEDURE CALLSIn Algol-like languages (alls), procedures have a simple and clearcall/return discipline.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
