K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 57
Текст из файла (страница 57)
Write an attribute grammar that assigns the correct data type toeach declared variable.b. Write an ad hoc syntax-directed translation scheme that assigns thecorrect data type to each declared variable.c. Can either scheme operate in a single pass over the syntax tree?8. Sometimes, the compiler writer can move an issue across theboundary between context-free and context-sensitive analysis.Consider, for example, the classic ambiguity that arises betweenfunction invocation and array references in fortran 77 (and otherlanguages). These constructs might be added to the classic expressiongrammar using the productions:Factor→ name ( ExprList )ExprList → ExprList , Expr| ExprHere, the only difference between a function invocation and an arrayreference lies in how the name is declared.In previous chapters, we have discussed using cooperation betweenthe scanner and the parser to disambiguate these constructs.
Can theproblem be solved during context-sensitive analysis? Which solutionis preferable?9. Sometimes, a language specification uses context-sensitivemechanisms to check properties that can be tested in a context-freeway. Consider the grammar fragment in Figure 4.16 on page 208. Itallows an arbitrary number of StorageClass specifiers when, in fact,the standard restricts a declaration to a single StorageClass specifier.a. Rewrite the grammar to enforce the restriction grammatically.b. Similarly, the language allows only a limited set of combinations ofTypeSpecifier. long is allowed with either int or float; short isallowed only with int.
Either signed or unsigned can appearExercises 219with any form of int. signed may also appear on char. Can theserestrictions be written into the grammar?c. Propose an explanation for why the authors structured the grammaras they did.d. Do your revisions to the grammar change the overall speed of theparser? In building a parser for c, would you use the grammar likethe one in Figure 4.16, or would you prefer your revised grammar?Justify your answer.10.
Object-oriented languages allow operator and function overloading. Inthese languages, the function name is not always a unique identifier,since you can have multiple related definitions, as invoid Show(int);void Show(char *);void Show(float);For lookup purposes, the compiler must construct a distinct identifierfor each function. Sometimes, such overloaded functions will havedifferent return types, as well. How would you create distinctidentifiers for such functions?11. Inheritance can create problems for the implementation ofobject-oriented languages. When object type A is a parent of objecttype B, a program can assign a “pointer to B” to a “pointer to A,” withsyntax such as a ← b.
This should not cause problems sinceeverything that A can do, B can also do. However, one cannot assign a“pointer to A” to a “pointer to B,” since object class B can implementmethods that object class A does not.Design a mechanism that can use ad hoc syntax-directed translation todetermine whether or not a pointer assignment of this kind is allowed.Hint: The scanner returned a single token type forany of the StorageClass values and another tokentype for any of the TypeSpecifiers.Section 4.5This page intentionally left blankChapter5Intermediate RepresentationsnCHAPTER OVERVIEWThe central data structure in a compiler is the intermediate form of theprogram being compiled. Most passes in the compiler read and manipulatethe ir form of the code. Thus, decisions about what to represent and howto represent it play a crucial role in both the cost of compilation and itseffectiveness.
This chapter presents a survey of ir forms that compilers use,including graphical ir, linear irs, and symbol tables.Keywords: Intermediate Representation, Graphical ir, Linear ir, ssa Form,Symbol Table5.1 INTRODUCTIONCompilers are typically organized as a series of passes. As the compilerderives knowledge about the code it compiles, it must convey that information from one pass to another. Thus, the compiler needs a representationfor all of the facts that it derives about the program.
We call this representation an intermediate representation, or ir. A compiler may have a single ir,or it may have a series of irs that it uses as it transforms the code from sourcelanguage into its target language. During translation, the ir form of the inputprogram is the definitive form of the program. The compiler does not referback to the source text; instead, it looks to the ir form of the code. The properties of a compiler’s ir or irs have a direct effect on what the compiler cando to the code.Almost every phase of the compiler manipulates the program in its ir form.Thus, the properties of the ir, such as the mechanisms for reading and writing specific fields, for finding specific facts or annotations, and for navigatingaround a program in ir form, have a direct impact on the ease of writing theindividual passes and on the cost of executing those passes.Engineering a Compiler.
DOI: 10.1016/B978-0-12-088478-0.00005-0c 2012, Elsevier Inc. All rights reserved.Copyright 221222 CHAPTER 5 Intermediate RepresentationsConceptual RoadmapThis chapter focuses on the issues that surround the design and use of anir in compilation. Section 5.1.1 provides a taxonomic overview of irs andtheir properties. Many compiler writers consider trees and graphs as the natural representation for programs; for example, parse trees easily capture thederivations built by a parser. Section 5.2 describes several irs based on treesand graphs. Of course, most processors that compilers target have linearassembly languages as their native language. Accordingly, some compilersuse linear irs with the rationale that those irs expose properties of the targetmachine’s code that the compiler should explicitly see.
Section 5.3 examineslinear irs.Appendix B.4 provides more material on symboltable implementation.The final sections of this chapter deal with issues that relate to irs but are not,strictly speaking, ir design issues. Section 5.4 explores issues that relate tonaming: the choice of specific names for specific values.
Naming can have astrong impact on the kind of code generated by a compiler. That discussionincludes a detailed look at a specific, widely used ir called static singleassignment form, or ssa. Section 5.5 provides a high-level overview of howthe compiler builds, uses, and maintains symbol tables. Most compilers buildone or more symbol tables to hold information about names and values andto provide efficient access to that information.OverviewTo convey information between its passes, a compiler needs a representationfor all of the knowledge that it derives about the program being compiled.Thus, almost all compilers use some form of intermediate representation tomodel the code being analyzed, translated, and optimized. Most passes inthe compiler consume ir; the scanner is an exception.
Most passes in thecompiler produce ir; passes in the code generator can be exceptions. Manymodern compilers use multiple irs during the course of a single compilation.In a pass-structured compiler, the ir serves as the primary and definitiverepresentation of the code.A compiler’s ir must be expressive enough to record all of the useful factsthat the compiler might need to transmit between passes. Source code isinsufficient for this purpose; the compiler derives many facts that have norepresentation in source code, such as the addresses of variables and constants or the register in which a given parameter is passed.
To record all ofthe detail that the compiler must encode, most compiler writers augment their with tables and sets that record additional information. We consider thesetables part of the ir.5.1 Introduction 223Selecting an appropriate ir for a compiler project requires an understandingof the source language, the target machine, and the properties of the applications that the compiler will translate. For example, a source-to-sourcetranslator might use an ir that closely resembles the source code, while acompiler that produces assembly code for a microcontroller might obtainbetter results with an assembly-code-like ir. Similarly, a compiler for cmight need annotations about pointer values that are irrelevant in a compiler for Perl, and a Java compiler keeps records about the class hierarchythat have no counterpart in a c compiler.Implementing an ir forces the compiler writer to focus on practical issues.The compiler needs inexpensive ways to perform the operations that it doesfrequently.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
