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

Nate McFadden guided this edition from its inception throughits publication with patience and good humor. Penny Anderson provided administrative andorganizational support that was critical to finishing the second edition. To all these people goour heartfelt thanks.This page intentionally left blankChapter1Overview of CompilationnCHAPTER OVERVIEWCompilers are computer programs that translate a program written in onelanguage into a program written in another language. At the same time, acompiler is a large software system, with many internal components andalgorithms and complex interactions between them. Thus, the study of compiler construction is an introduction to techniques for the translation andimprovement of programs, and a practical exercise in software engineering.This chapter provides a conceptual overview of all the major components ofa modern compiler.Keywords: Compiler, Interpreter, Automatic Translation1.1 INTRODUCTIONThe role of the computer in daily life grows each year.

With the rise of theInternet, computers and the software that runs on them provide communications, news, entertainment, and security. Embedded computers have changedthe ways that we build automobiles, airplanes, telephones, televisions, andradios. Computation has created entirely new categories of activity, fromvideo games to social networks. Supercomputers predict daily weather andthe course of violent storms. Embedded computers synchronize traffic lightsand deliver e-mail to your pocket.All of these computer applications rely on software computer programsthat build virtual tools on top of the low-level abstractions provided by theunderlying hardware.

Almost all of that software is translated by a toolcalled a compiler. A compiler is simply a computer program that translates other computer programs to prepare them for execution. This bookpresents the fundamental techniques of automatic translation that are usedEngineering a Compiler. DOI: 10.1016/B978-0-12-088478-0.00001-3c 2012, Elsevier Inc. All rights reserved.Copyright Compilera computer program that translates othercomputer programs12 CHAPTER 1 Overview of Compilationto build compilers. It describes many of the challenges that arise in compilerconstruction and the algorithms that compiler writers use to address them.Conceptual RoadmapA compiler is a tool that translates software written in one language intoanother language. To translate text from one language to another, the toolmust understand both the form, or syntax, and content, or meaning, of theinput language. It needs to understand the rules that govern syntax and meaning in the output language.

Finally, it needs a scheme for mapping contentfrom the source language to the target language.The structure of a typical compiler derives from these simple observations.The compiler has a front end to deal with the source language. It has a backend to deal with the target language. Connecting the front end and the backend, it has a formal structure for representing the program in an intermediate form whose meaning is largely independent of either language.

Toimprove the translation, a compiler often includes an optimizer that analyzesand rewrites that intermediate form.OverviewComputer programs are simply sequences of abstract operations written ina programming language—a formal language designed for expressing computation. Programming languages have rigid properties and meanings—asopposed to natural languages, such as Chinese or Portuguese.

Programminglanguages are designed for expressiveness, conciseness, and clarity. Naturallanguages allow ambiguity. Programming languages are designed to avoidambiguity; an ambiguous program has no meaning. Programming languagesare designed to specify computations—to record the sequence of actions thatperform some task or produce some results.Programming languages are, in general, designed to allow humans to expresscomputations as sequences of operations.

Computer processors, hereafterreferred to as processors, microprocessors, or machines, are designed to execute sequences of operations. The operations that a processor implementsare, for the most part, at a much lower level of abstraction than those specified in a programming language. For example, a programming language typically includes a concise way to print some number to a file. That singleprogramming language statement must be translated into literally hundredsof machine operations before it can execute.The tool that performs such translations is called a compiler. The compilertakes as input a program written in some language and produces as its output an equivalent program.

In the classic notion of a compiler, the output1.1 Introduction 3program is expressed in the operations available on some specific processor,often called the target machine. Viewed as a black box, a compiler mightlook like this:SourceProgramCompilerTargetProgramTypical “source” languages might be c, c++, fortran, Java, or ml. The“target” language is usually the instruction set of some processor.Some compilers produce a target program written in a human-oriented programming language rather than the assembly language of some computer.The programs that these compilers produce require further translation beforethey can execute directly on a computer. Many research compilers produceC programs as their output.

Because compilers for C are available on mostcomputers, this makes the target program executable on all those systems,at the cost of an extra compilation for the final target. Compilers that target programming languages rather than the instruction set of a computer areoften called source-to-source translators.Instruction setThe set of operations supported by a processor;the overall design of an instruction set is oftencalled an instruction set architecture or ISA.Many other systems qualify as compilers.

For example, a typesetting program that produces PostScript can be considered a compiler. It takes asinput a specification for how the document should look on the printed pageand it produces as output a PostScript file. PostScript is simply a languagefor describing images. Because the typesetting program takes an executablespecification and produces another executable specification, it is a compiler.The code that turns PostScript into pixels is typically an interpreter, nota compiler. An interpreter takes as input an executable specification andproduces as output the result of executing the specification.SourceProgramInterpreterResultsSome languages, such as Perl, Scheme, and apl, are more often implementedwith interpreters than with compilers.Some languages adopt translation schemes that include both compilationand interpretation. Java is compiled from source code into a form calledbytecode, a compact representation intended to decrease download times forJava applications.

Java applications execute by running the bytecode on thecorresponding Java Virtual Machine (jvm), an interpreter for bytecode. Tocomplicate the picture further, many implementations of the jvm include aVirtual machineA virtual machine is a simulator for someprocessor. It is an interpreter for that machine’sinstruction set.4 CHAPTER 1 Overview of Compilationcompiler that executes at runtime, sometimes called a just-in-time compiler,or jit, that translates heavily used bytecode sequences into native code forthe underlying computer.Interpreters and compilers have much in common. They perform many of thesame tasks. Both analyze the input program and determine whether or not itis a valid program.

Both build an internal model of the structure and meaning of the program. Both determine where to store values during execution.However, interpreting the code to produce a result is quite different fromemitting a translated program that can be executed to produce the result. Thisbook focuses on the problems that arise in building compilers.

However, animplementor of interpreters may find much of the material relevant.Why Study Compiler Construction?A compiler is a large, complex program. Compilers often include hundredsof thousands, if not millions, of lines of code, organized into multiple subsystems and components. The various parts of a compiler interact in complexways. Design decisions made for one part of the compiler have important ramifications for other parts. Thus, the design and implementation ofa compiler is a substantial exercise in software engineering.A good compiler contains a microcosm of computer science.

It makes practical use of greedy algorithms (register allocation), heuristic search techniques(list scheduling), graph algorithms (dead-code elimination), dynamic programming (instruction selection), finite automata and push-down automata(scanning and parsing), and fixed-point algorithms (data-flow analysis). Itdeals with problems such as dynamic allocation, synchronization, naming, locality, memory hierarchy management, and pipeline scheduling.