tailieunhanh - An introduction to compilers

A compiler is a program that translates a source language text into an equivalent target language text. . for a C compiler, the source language is C while the target language may be Sparc assembly language. Of course, one expects a compiler to do a faithful translation, . the meaning of the translated text should be the same as the meaning of the source text. | An introduction to compilers Revision D. Vermeir Dept. of Computer Science Free University of Brussels VUB dvermeir@ January 26 2001 Contents 1 Introduction 5 Compilers and languages. 5 Applications of compilers. 6 Overview of the compilation process. 8 Micro. 8 JVM code. 9 Lexical analysis. 11 Syntax analysis. 12 Semantic analysis. 13 Intermediate code generation. 14 Optimization. 15 Code generation . 16 2 Lexical analysis 17 Introduction. 17 Regular expressions. 23 Finite state automata. 24 Deterministic finite automata. 24 Nondeterministic finite automata. 26 Regular expressions vs finite state automata. 30 A scanner generator. 31 1 VUB-DINF 2001 1 2 3 Parsing 34 Context-free grammars. 34 Top-down parsing. 37 Introduction. 37 Eliminating left recursion in a grammar. 40 Avoiding backtracking LL 1 grammars . 42 Predictive parsers. 43 Construction of first and follow . 47 Bottom-up parsing . 49 Shift-reduce parsers . 49 LR 1 parsing. 54 LALR parsers and yacc bison. 61 4 Checking static semantics 64 Attribute grammars and syntax-directed translation. 64 Symbol tables. 67 String pool. 68 Symbol tables and scope rules. 68 Type checking. 70 5 Intermediate code generation 73 Postfix notation. 74 Abstract syntax trees. 75 Three-address code. 77 Translating assignment statements. 78 Translating boolean expressions. 80 Translating control flow statements. 84 Translating procedure calls. 86 Translating array references. .