编译原理简明教程(第3版)

目 录 第1章 概述 1 1.1 程序设计语言与翻译 1 1.1.1 程序设计语言 1 1.1.2 编译程序和解释程序 2 1.2 编译过程概述 3 1.2.1 编译程序的工作过程 3 1.2.2 编译程序的结构 7 1.3 编译程序的开发 7 1.3.1 编译程序的开发步骤 8 1.3.2 编译程序的开发技术 8 1.3.3 编译程序的自动生成 10 1.4 本章小结 10 习题1 11 第2章 形式语言理论基础 12 2.1 形式语言的基本概念 12 2.1.1 符号和符号串 12 2.1.2 符号串的运算 13 2.1.3 符号串集合的运算 15 2.2 文法和语言的形式定义 16 2.2.1 文法的形式定义 16 2.2.2 形式语言的定义 19 2.3 语法树和二义性 22 2.3.1 语法树和推导 22 2.3.2 文法的二义性 25 2.4 文法的限制 28 2.4.1 文法的实用限制 28 2.4.2 文法的等价变换 31 2.4.3 扩充的BNF表示法 33 2.5 文法和语言的Chomsky分类 34 2.5.1 0型文法与0型语言(对应图灵机) 34 2.5.2 1型文法与1型语言(对应线性界限自动机) 35 2.5.3 2型文法与2型语言(对应下推自动机) 35 2.5.4 3型文法与3型语言(对应有限自动机) 36 2.5.5 四类文法的关系和区别 37 2.6 本章小结 38 习题2 38 第3章 自动机理论基础 40 3.1 有限自动机的基本概念 40 3.1.1 有限自动机的定义及表示法 40 3.1.2 有限自动机的机器模型 43 3.1.3 确定有限自动机(DFA) 43 3.1.4 有限自动机在计算机内的表示 44 3.1.5 不确定有限自动机(NFA) 45 3.1.6 由NFA到DFA的等价转换 47 3.2 确定有限自动机DFA的化简 50 3.2.1 等价状态和无关状态 50 3.2.2 自动机的化简 51 3.3 正则表达式形式定义 53 3.4 下推自动机PDA 54 3.4.1 下推自动机的机器模型 54 3.4.2 PDA的形式定义 55 3.5 本章小结 57 习题3 57 第4章 词法分析 59 4.1