编译器构造

《编译器构造（Java语言版）》以Java为实现语言，清晰地向读者展示编译器设计和实现，提供了若干精心准备的实验项目及其测试用例。这些实验项目不仅使读者掌握理论知识，还能够应用理论。本书涵盖了自动机与形式语言课程的多数内容，包括有穷自动机、栈分析器、正规表达式、正规文法、上下文无关文法、上下文有关文法、非受限文法、Chomsky层次、泵引理、下推自动机、图灵机、可计算性、复杂性，还包括了下推自动机模拟器和图灵机模拟器。本书适用于作为编译原理、自动机、形式语言等课程的教材。

第1章 字符串、语言和编译器 1.1 概述 1.2 语言的基本概念 1.3 编译器的基本概念 1.4 集合论中的基本概念 1.5 空串 1.6 连接 1.7 指数记法 1.8 星运算符（也称为0次或多次运算符） 1.9 串集合的连接 1.10 加运算符（也称为1次或多次运算符） 1.11 问号运算符（也称为0次或1次运算符） 1.12 包含单独一个串的集合的简便记法 1.13 运算符优先级 1.14 正规表达式 1.15 正则表达式的局限性 问题 第2章 上下文无关文法（一） 2.1 概述 2.2 什么是上下文无关文法 2.3 基于上下文无关文法的推导 2.4 由上下文无关文法定义的语言 2.5 上下文无关文法的不同表示方法 2.6 一些简单文法 2.7 基于上下文无关文法的语言生成技术 2.8 正规文法和右线性文法 2.9 基于正规文法的计数 2.10 表的文法 2.11 一个不是上下文无关的重要语言 问题 第3章 上下文无关文法（二） 3.1 概述 3.2 语法分析树 3.3 最左和最右推导 3.4 替换 3.5 二义文法 3.6 确定可致空的非终结符 3.7 消除 （ 产生式 3.8 消除unit产生式 3.9 消除无用非终结符 3.10 递归转换 3.11 增加空串到语言 问题 第4章 上下文无关文法（三） 4.1 概述 4.2 算术表达式文法 4.3 文法中结合性和优先级的描述 4.4 Backus-Naur范式 4.5 语法图 4.6 抽象语法树和三地址码 4.7 非收缩文法 4.8 基本非收缩文法 4.9 上下文无关文法到基本非收缩文法的转换 4.10 上下文无关语言的pumping特性 问题 第5章 Chomsky层次（选讲） 5.1 概述 5.2 上下文有关产生式 5.3 上下文有关文法 5.4 非受限文法 问题 第6章 自上而下语法分析 6.1 概述 6.2 自上而下构造语法分析树 6.3 失败的语法分析 6.4 不适合自上而下语法分析的文法 6.5 确定的语法分析器 6.6 借助栈的语法分析器 6.7 用表来表示栈式语法分析器 6.8 处理不以终结符领头的产生式 6.9 用Java写一个栈式语法分析器 问题 第7章 LL（1）文法 7.1 概述 7.2 产生式右端的FIRST集合 7.3 确定操作序列 7.4 确定 （ 产生式的选择集合 7.5 后跟-左端-后跟-最右规则 7.6 右端可致空的产生式的选择集合 7.7 包含输入结束符的选择集合 7.8 针对含lambda产生式文法的栈式语法分析器 7.9 将非LL（1）文法转换为LL（1）文法 7.10 用二义文法进行分析 7.11 计算FIRST和FOLLOW集合 问题 第8章 表驱动的栈式语法分析器（选讲） 8.1 概述 8.2 统一栈式语法分析器的操作 8.3 实现表驱动的栈式语法分析器 8.4 表驱动栈式语法分析器的改进 8.5 不确定的语法分析器--偏向理论的内容（选讲） 问题 第9章 递归-下降语法分析 9.1 概述 9.2 一个简单的递归-下降语法分析器 9.3 处理lambda产生式 9.4 一个公共错误 9.5 产生式的Java代码 9.6 递归-下降语法分析器中提取左公因子 9.7 消除尾递归 9.8 翻译星号、加号和问号算符 9.9 反向动作 问题 第10章 递归-下降翻译 10.1 概述 10.2 一个简单的翻译文法 10.3 转换翻译文法到Java代码 10.4 翻译文法的描述 10.5 在语法分析过程中传递信息 10.6 L-属性文法 10.7 一个新的单词符号管理器 10.8 解决单词符号向前一个字符看问题 10.9 新单词符号管理器的代码 10.10 前缀表达式编译器的翻译文法 10.11 趣用递归（选讲） 问题 第11章 汇编语言 11.1 概述 11.2 J1计算机的结构 11.3 机器语言指令 11.4 汇编语言指令 11.5 压入字符 11.6 aout指令 11.7 使用标号 11.8 使用汇编器 11.9 stav指令 11.10 编译赋值语句 11.11 编译print和println 11.12 输出字符串 11.13 输入十进制数 11.14 入口指导语句 11.15 更多的汇编语言内容 问题 第12章 一个简单的编译器S1 12.1 概述 12.2 源语言 12.3 源语言的文法 12.4 目标语言 12.5 符号表 12.6 代码生成器 12.7 token类 12.8 写出翻译文法 12.9 实现S1编译器 12.10 使用 12.11 关于扩展S1编译器的忠告 12.11.1 更新单词符号管理器 12.11.2 先调试单词符号管理器 12.11.3 选择集合 12.11.4 使用必要的break语句 12.11.5 使用必要的Consume方法调用 12.11.6 正确地解释翻译文法 12.12 对于S2的描述 问题 第13章 JavaCC（选讲） 13.1 概述 13.2 JavaCC中扩展的正规表达式 13.3 JavaCC输入文件 13.4 正规表达式动作描述 13.5 S1j的JavaCC输入文件 13.6 JavaCC产生的文件 13.7 使用星号和加号操作 13.8 选择点和向前看 13.9 JavaCC的选择算法 13.10 语法和语义的向前看描述（选讲） 13.11 用JavaCC仅生成单词符号管理器 13.12 使用单词符号链 13.13 抑制警告信息 问题 第14章 在S2基础上构造 14.1 概述 14.2 扩展println和print 14.3 级联赋值语句 14.4 一元加和减 14.5 readint语句 14.6 从命令行控制单词符号踪迹的生成 14.7 S3的规范 问题 第15章 编译控制结构 15.1 概述 15.2 while语句 15.3 if语句 15.4 do-while语句 15.5 数字常量的范围检查 15.6 处理字符串中的反斜线-引号 15.7 用JavaCC处理反斜线（选讲） 15.8 JavaCC中的全局块（选讲） 15.9 处理跨行字符串 15.10 用JavaCC处理跨行字符串（选讲） 15.11 JavaCC中的SPECIAL_TOKEN块（选讲） 15.12 错误恢复 15.13 JavaCC中的错误恢复（选讲） 15.14 S4的规范 问题 第16章 编译函数形式的程序 16.1 概述 16.2 分别汇编和连接 16.3 调用函数和从函数返回 16.4 S5的源语言 16.5 S5的符号表 16.6 S5的代码生成器 16.7 S5的翻译文法 16.8 与库连接 16.9 S5规范 16.10 扩展S5（选讲） 问题 第17章 有限自动机 17.1 概述 17.2 确定有限自动机 17.3 转换DFA到正规表达式 17.4 DFA的Java代码 17.5 非确定有限自动机 17.6 使用NFA作为一个算法 17.7 利用子集算法转换NFA到DFA 17.8 转换DFA到正规文法 17.9 转换正规文法到 17.10 转换正规表达式到NFA 17.11 求出最小的NFA 17.12 正规语言的泵理论 问题 第18章 课程设计项目：用编译技术实现grep 18.1 概述 18.2 grep程序的正规表达式 18.3 针对正规表达式的单词符号管理器 18.4 正规表达式的文法 18.5 正规表达式编译器的目标语言 18.6 用NFA进行模式匹配 问题 第19章 编译到面向寄存器的结构 19.1 概述 19.2 使用寄存器指令集 19.3 修改R1符号表 19.4 R1的语法分析器和代码生成器 问题 第20章 优化 20.1 概述 20.2 使用ldc指令 20.3 重用临时变量 20.4 常量合并 20.5 寄存器分配 20.6 窥孔优化 问题 第21章 解释器 21.1 概述 21.2 转换S1到I1 21.3 解释转移控制的语句 21.4 实现编译：解释器CI1 21.5 解释器的优点 问题 第22章 自下而上语法分析 22.1 概述 22.2 自下而上语法分析原理 22.3 语法分析：右递归文法对比左递归文法 22.4 用二义文法进行自下而上语法分析 22.5 不归约规则 22.6 SLR（1）语法分析 22.7 移进/归约冲突 22.8 归约/归约冲突 22.9 LR（1）语法分析 问题 第23章 yacc 23.1 概述 23.2 yacc输入和输出文件 23.3 一个yacc-生成的简单语法分析器 23.4 用取值栈传递值 23.5 对二义文法使yacc 23.6 在语法分析树中传递值 23.7 实现Sly 23.8 jflex 问题 附录A 栈指令集 附录B 寄存器指令集 参考文献