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

TopDownshould display the order for a top-down parser, while BottomUpshould show the order for a bottom-up parser.9. The ClockNoise language (CN) is represented by the followinggrammar:Goal→ ClockNoiseClockNoise → ClockNoise tick tock| tick tocka.b.c.d.What are the lr(1) items of CN?What are the first sets of CN?Construct the Canonical Collection of Sets of lr(1) Items for CN.Derive the Action and Goto tables.10. Consider the following grammar:Start →S→A→|B→C→SAaBCBCfbca. Construct the canonical collection of sets of lr(1) items for thisgrammar.b. Derive the Action and Goto tables.c. Is the grammar lr(1)?11.

Consider a robot arm that accepts two commands: 5 puts an apple inthe bag and 4 takes an apple out of the bag. Assume the robot armstarts with an empty bag.A valid command sequence for the robot arm should have no prefixthat contains more 4 commands than 5 commands. As examples,5544 and 545 are valid command sequences, but 5445 and54544 are not.a. Write an lr(1) grammar that represents all the value commandsequences for the robot arm.b.

Prove that the grammar is lr(1).Exercises 15912. The following grammar has no known ll(1) equivalent:0 Start → A1| B2 A3→ ( A )4 B5→ ( B >||abShow that the grammar is lr(1).13. Write a grammar for expressions that can include binary operators (+and x), unary minus (-), autoincrement (++), and autodecrement (- -)with their customary precedence. Assume that repeated unary minusesare not allowed, but that repeated autoincrement and autodecrementoperators are allowed.Section 3.614. Consider the task of building a parser for the programming languageScheme.

Contrast the effort required for a top-down recursive-descentparser with that needed for a table-driven lr(1) parser. (Assume thatyou already have an lr(1) table generator.)Section 3.715. The text describes a manual technique for eliminating uselessproductions in a grammar.a.

Can you modify the lr(1) table-construction algorithm so that itautomatically eliminates the overhead from useless productions?b. Even though a production is syntactically useless, it may serve apractical purpose. For example, the compiler writer might associatea syntax-directed action (see Chapter 4) with the uselessproduction. How should your modified table-constructionalgorithm handle an action associated with a useless production?This page intentionally left blankChapter4Context-Sensitive AnalysisnCHAPTER OVERVIEWAn input program that is grammatically correct may still contain seriouserrors that would prevent compilation. To detect such errors, a compiler performs a further level of checking that involves considering each statementin its actual context. These checks find errors of type and of agreement.This chapter introduces two techniques for context-sensitive checking.Attribute grammars are a functional formalism for specifying contextsensitive computation.

Ad hoc syntax-directed translation provides a simpleframework where the compiler writer can hang arbitrary code snippets toperform these checks.Keywords: Semantic Elaboration, Type Checking, Attribute Grammars,Ad Hoc Syntax Directed Translation4.1 INTRODUCTIONThe compiler’s ultimate task is to translate the input program into a form thatcan execute directly on the target machine. For this purpose, it needs knowledge about the input program that goes well beyond syntax. The compilermust build up a large base of knowledge about the detailed computationencoded in the input program. It must know what values are represented,where they reside, and how they flow from name to name.

It must understand the structure of the computation. It must analyze how the programinteracts with external files and devices. All of these facts can be derivedfrom the source code, using contextual knowledge. Thus, the compiler mustperform deeper analysis than is typical for a scanner or a parser.These kinds of analysis are either performed alongside parsing or in a postpass that traverses the ir produced by the parser. We call this analysis eitherEngineering a Compiler. DOI: 10.1016/B978-0-12-088478-0.00004-9c 2012, Elsevier Inc.

All rights reserved.Copyright 161162 CHAPTER 4 Context-Sensitive Analysis“context-sensitive analysis,” to differentiate it from parsing, or “semanticelaboration,” since its elaborates the ir. This chapter explores two techniquesfor organizing this kind of analysis in a compiler: an automated approachbased on attribute grammars and an ad hoc approach that relies on similarconcepts.Conceptual RoadmapTo accumulate the contextual knowledge needed for further translation, thecompiler must develop ways of viewing the program other than syntax. Ituses abstractions that represent some aspect of the code, such as a type system, a storage map, or a control-flow graph.

It must understand the program’sname space: the kinds of data represented in the program, the kinds of datathat can be associated with each name and each expression, and the mapping from a name’s appearance in the code back to a specific instance of thatname. It must understand the flow of control, both within procedures andacross procedures. The compiler will have an abstraction for each of thesecategories of knowledge.This chapter focuses on mechanisms that compilers use to derive contextsensitive knowledge. It introduces one of the abstractions that the compilermanipulates during semantic elaboration, the type system. (Others are introduced in later chapters.) Next, the chapter presents a principled automaticapproach to implementing these computations in the form of attributegrammars. It then presents the most widely used technique, ad hoc syntaxdirected translation, and compares the strengths and weaknesses of thesetwo tools.

The advanced topics section includes brief descriptions of situations that present harder problems in type inference, along with a finalexample of ad hoc syntax-directed translation.OverviewConsider a single name used in the program being compiled; let’s call it x.Before the compiler can emit executable target-machine code for computations involving x, it must have answers to many questions.nnWhat kind of value is stored in x? Modern programming languages usea plethora of data types, including numbers, characters, boolean values,pointers to other objects, sets (such as {red, yellow, green}), andothers. Most languages include compound objects that aggregateindividual values; these include arrays, structures, sets, and strings.How big is x? Because the compiler must manipulate x, it needs toknow the length of x’s representation on the target machine.

If x is anumber, it might be one word (an integer or floating-point number), two4.1 Introduction 163nnnwords (a double-precision floating-point number or a complex number),or four words (a quad-precision floating-point number or a doubleprecision complex number). For arrays and strings, the number ofelements might be fixed at compile time or it might be determined atruntime.If x is a procedure, what arguments does it take? What kind of value, ifany, does it return? Before the compiler can generate code to invoke aprocedure, it must know how many arguments the code for the calledprocedure expects, where it expects to find those arguments, and whatkind of value it expects in each argument. If the procedure returns avalue, where will the calling routine find that value, and what kind ofdata will it be? (The compiler must ensure that the calling procedureuses the value in a consistent and safe manner. If the calling procedureassumes that the return value is a pointer that it can dereference, and thecalled procedure returns an arbitrary character string, the results maynot be predictable, safe, or consistent.)How long must x’s value be preserved? The compiler must ensure thatx’s value remains accessible for any part of the computation that canlegally reference it.

If x is a local variable in Pascal, the compiler caneasily overestimate x’s interesting lifetime by preserving its value forthe duration of the procedure that declares x. If x is a global variablethat can be referenced anywhere, or if it is an element of a structureexplicitly allocated by the program, the compiler may have a hardertime determining its lifetime. The compiler can always preserve x’svalue for the entire computation; however, more precise informationabout x’s lifetime might let the compiler reuse its space for other valueswith nonconflicting lifetimes.Who is responsible for allocating space for x (and initializing it)? Isspace allocated for x implicitly, or does the program explicitly allocatespace for it? If the allocation is explicit, then the compiler must assumethat x’s address cannot be known until the program runs.

If, on the otherhand, the compiler allocates space for x in one of the runtime datastructures that it manages, then it knows more about x’s address. Thisknowledge may let it generate more efficient code.The compiler must derive the answers to these questions, and more, fromthe source program and the rules of the source language. In an Algol-likelanguage, such as Pascal or c, most of these questions can be answered byexamining the declarations for x.

If the language has no declarations, as inapl, the compiler must either derive this kind of information by analyzingthe program, or it must generate code that can handle any case that mightarise.164 CHAPTER 4 Context-Sensitive AnalysisMany, if not all, of these questions reach beyond the context-free syntax ofthe source language. For example, the parse trees for x ← y and x ← z differonly in the text of the name on the right-hand side of the assignment.

If x andy are integers while z is a character string, the compiler may need to emitdifferent code for x ← y than for x ← z. To distinguish between these cases,the compiler must delve into the program’s meaning. Scanning and parsingdeal solely with the program’s form; the analysis of meaning is the realm ofcontext-sensitive analysis.To see this difference between syntax and meaning more clearly, considerthe structure of a program in most Algol-like languages.

These languagesrequire that every variable be declared before it is used and that each use ofa variable be consistent with its declaration. The compiler writer can structure the syntax to ensure that all declarations occur before any executablestatement. A production such asProcedureBody → Declarations ExecutablesTo solve this particular problem, the compilertypically creates a table of names. It inserts aname on declaration; it looks up the name ateach reference. A lookup failure indicates amissing declaration.This ad hoc solution bolts onto the parser, butuses mechanisms well outside the scope ofcontext-free languages.where the nonterminals have the obvious meanings, ensures that all declarations occur before any executable statements.