《编译原理》是编译领域无可替代的经典著作，被广大计算机专业人士誉为“龙书”。《编译原理》上一版自1986年出版以来，被世界各地的著名高等院校和研究机构（包括美国哥伦比亚大学、斯坦福大学、哈佛大学、普林斯顿大学、贝尔实验室）作为本科生和研究生的编译原理课程的教材。该书对我国高等计算机教育领域也产生了重大影响。
    第2版对每一章都进行了全面的修订，以反映自上一版出版二十多年来软件工程、程序设计语言和计算机体系结构方面的发展对编译技术的影响。
    《编译原理》全面介绍了编译器的设计。并强调编译技术在软件设计和开发中的广泛应用，每章中都包含大量的习题和丰富的参考文献。《编译原理》适合作为高等院校计算机专业本科生和研究生的编译原理与技术课程的教材，也可供广大计算机技术人员参考。

    In the time since the 1986 edition of this book, the world of compiler designhas changed significantly. Programming languages have evolved to present newcompilation problems. Computer architectures offer a variety of resources ofwhich the compiler designer must take advantage. Perhaps most interestingly,the venerable technology of code optimization has found use outside compilers.It is now used in tools that find bugs in software, and most importantly, findsecurity holes in existing code. And much of the "front-end" technology ——grammars, regular expressions, parsers, and syntax-directed translators —— arestill in wide use.
    Thus, our philosophy from previous versions of the book has not changed.We recognize that few readers will build, or even maintain, a compiler for amajor programming language. Yet the models, theory, and algorithms associ-ated with a compiler can be applied to a wide range of problems in softwaredesign and software development. We therefore emphasize problems that aremost commonly encountered in designing a language processor, regardless ofthe source language or target machine.Use of the BookIt takes at least two quarters or even two semesters to cover all or most of thematerial in this book. It is common to cover the first half in an undergraduatecourse and the second half of the book —— stressing code optimization —— ina second course at the graduate or mezzanine level. Here is an outline of thechapters:Chapter 1 contains motivational material and also presents some backgroundissues in computer architecture and programming-language principles.Chapter 2 develops a miniature compiler and introduces many of the impor-taut concepts, which are then developed in later chapters. The compiler itselfappears in the appendix.Chapter 3 covers lexical analysis, regular expressions, finite-state machines, andscanner-generator tools. This material is fundamental to text-processing of allsorts.

    AlfredV.Aho，美国哥伦比亚大学教授。美国国家工程院院士，ACM和lEEE会士，曾获得IEEE的冯·诺伊曼奖。著有多部算法、数据结构、编译器、数据库系统及计算机科学基础方面的著作。
    MonicaS.Lam，斯坦福大学计算机科学系教授。曾任T'ensilica的首席科学家，也是Moka5的首任CEO。曾经主持SLJIF项目。该项目产生了最流行的研究用编译器之一。
    Ravi Sethi，Avaya实验室总裁。曾任贝尔实验室高级副总裁和LLicentTectlIlologies通信软件的CTO。他曾在宾夕法尼亚州立大学、亚利桑那州立大学和普林斯顿大学任教，是ACM会士。
    Jeffrey D.UIIman，斯坦福大学计算机科学系教授和GradianceCEO。他的研究兴趣包括数据库理论、数据库集成、数据挖掘和利用信息基础设施教学等。他是美国国家工程院院士、IEEE会士，获得过ACM的Karlstrom杰出教育奖和Knufh奖。

1 introduction
1.1 language processors
1.2 the structure of a compiler
1.3 the evolution of programming languages
1.4 the science of building a compiler
1.5 applications of compiler technology
1.6 programming language basics
1.7 summary of chapter 1
1.8 references for chapter 1
2 a simple syntax-directed translator
2.1 introduction
2.2 syntax definition
2.3 syntax-directed translation
2.4 parsing
2.5 a translator for simple expressions
2.6 lexical analysis
2.7 symbol tables
2.8 intermediate code generation
2.9 summary of chapter 2
3 lexical analysis
3.1 the role of the lexical analyzer
3.2 input buffering
3.3 specification of tokens
3.4 recognition of tokens
3.5 the lexical-analyzer generator lex
3.6 finite automata
3.7 from regular expressions to automata
3.8 design of a lexical-analyzer generator
3.9 optimization of dfa-based pattern matchers
3.10 summary of chapter 3
3.11 references for chapter 3
4 syntax analysis
4.1 introduction
4.2 context-free grammars
4.3 writing a grammar
4.4 top-down parsing
4.5 bottom-up parsing
4.6 introduction to lr parsing: simple lr
4.7 more powerful lr parsers
4.8 using ambiguous grammars
4.9 parser generators
4.10 summary of chapter 4
4.11 references for chapter 4
5 syntax-directed translation
5.1 syntax-directed definitions
5.2 evaluation orders for sdd's
5.3 applications of syntax-directed translation
5.4 syntax-directed translation schemes
5.5 hnplementing l-attributed sdd's
5.6 summary of chapter 5
5.7 references for chapter 5
6 intermediate-code generation
6.1 variants of syntax trees
6.2 three-address code
6.3 types and declarations
6.4 translation of expressions
6.5 type checking
6.6 control flow
6.7 backpatching
6.8 switch-statements
6.9 intermediate code for procedures
6.10 summary of chapter 6
6.11 references for chapter 6
7 run-time environments
7.1 storage organization
7.2 stack allocation of space
7.3 access to nonlocal data on the stack
7.4 heap management
7.5 introduction to garbage collection
7.6 introduction to trace-based collection
7.7 short-pause garbage collection
7.8 advanced topics in garbage collection
7.9 summary of chapter 7
7.10 references for chapter 7
8 code generation
8.1 issues m the design of a code generator
8.2 the target language
8.3 addresses in the target code
8.4 basic blocks and flow graphs
8.5 optimization of basic blocks
8.6 a simple code generator
8.7 peephole optimization
8.8 register allocation and assignment
8.9 instruction selection by tree rewriting
8.10 optimal code generation for expressions
8.11 dynamic programming code-generation
8.12 summary of chapter 8
8.13 references for chapter 8
9 machine-independent optimizations
9.1 the principal sources of optimization
9.2 introduction to data-flow analysis
9.3 foundations of data-flow analysis
9.4 constant propagation
9.5 partial-redundancy elimination
9.6 loops in flow graphs
9.7 region-based analysis
9.8 symbolic analysis
9.9 summary of chapter 9
9.10 references for chapter 9
10 instruction-level parallelism
10.1 processor architectures
10.2 code-scheduling constraints
10.3 basic-block scheduling
10.4 global code scheduling
10.5 software pipelining
10.6 summary of chapter 10
10.7 references for chapter 10
11 optimizing for parallelism and locality
11.1 basic concepts
11.2 matrix multiply: an in-depth example
11.3 iteration spaces
11.4 aftlne array indexes
11.5 data reuse
11.6 array data-dependence analysis
11.7 finding synchronization-free parallelism
11.8 synchronization between parallel loops
11.9 pipelining
11.10 locality optimizations
11.11 other uses of affine transforms
11.12 summarv of chapter 11
11.13 references for chapter 11
12 interprocedural analysis
12.1 basic concepts
12.2 why interprocedural analysis?
12.3 a logical representation of data flow
12.4 a simple pointer-analysis algorithm
12.5 context-insensitive interprocedural analysis
12.6 context-sensitive pointer analysis
12.7 datalog implementation by bdd's
12.8 summary of chapter 12
12.9 references for chapter 12
a a complete front end
a.1 the source language
a.2 main
a.3 lexical analyzer
a.4 symbol tables and types
a.5 intermediate code for expressions
a.6 jumping code for boolean expressions
a.7 intermediate code for statements
a.8 parser
a.9 creating the front end
b finding linearly independent solutions
index

    Languagel, are used to search databases. Database queries consist of predicatescontaining relational and boolean operators. They can be interpreted or com-piled into commands to search a database for records satisfying that predicate.Compiled SimulationSimulation is a general technique used in many scientific and engineering disci-plines to understand a phenomenon or to validate a design. Inputs to a simula-tor usually include the description of the design and specific input parametersfor that particular simulation run. Simulations can be very expensive. We typi-cally need to simulate many possible design alternatives on many different inputsets, and each experiment may take days to complete on a high-performancemachine. Instead of writing a simulator that interprets the design, it is fasterto compile the design to produce machine code that simulates that particulardesign natively. Compiled simulation can run orders of magnitude faster thanan interpreter-based approach. Compiled simulation is used in many state-of-the-art tools that simulate designs written in Verilog or VHDL.1.5.5 Software Productivity ToolsPrograms are arguably the most complicated engineering artifacts ever pro-duced; they consist of many many details, every one of which must be correctbefore the program will work completely. As a result, errors are rampant inprograms; errors may crash a system, produce wrong results, render a systemvulnerable to security attacks, or even lead to catastrophic failures in criticalsystems. Testing is the primary technique for locating errors in programs.
    An interesting and promising complementary approach is to use data-flowanalysis to locate errors statically （that is, before the program is run）. Data-flow analysis can find errors along all the possible execution paths, and notjust those exercised by the input data sets, as in the case of program testing.Many of the data-flow-analysis techniques, originally developed for compileroptimizations, can be used to create tools that assist programmers in theirsoftware engineering tasks.
    The problem of finding all program'errors is undecidable. A data-flow anal-ysis may be designed to warn the programmers of all possible statements witha particular category of errors. But if most of these warnings are false alarms,users will not use the tool. Thus, practical error detectors are often neithersound nor complete. That is, they may not find all the errors in the program,and not all errors reported are guaranteed to be real errors. Nonetheless, var-ious static analyses have been developed and shown to be effective in findingerrors, such as dereferencing null or freed pointers, in real programs. The factthat error detectors may be unsound makes them significantly different fromcompiler optimizations. Optimizers must be conservative and cannot alter thesemantics of the program under any circumstances.
    ……