Chapter 1
1．解答：
程序设计语言：程序设计语言是遵守一定规范的、描述“计算”（Computing）过程的形式语言。一般可以划分为低级语言和高级语言两大类。低级语言是面向机器的语言，它是为特定的计算机系统设计的语言，机器指令、汇编语言是低级语言。高级语言是与具体计算机无关的“通用”语言，它更接近于人类的自然语言和数学表示，例如FORTRAN、Pascal、C等等我们熟悉的语言是高级语言。
语言处理程序：由于目前的计算机只能理解和执行机器语言，因此必须有一个程序将用程序设计语言书写的程序等价（执行效果完全一致）地转换为计算机能直接执行的形式，完成这一工作的程序称为“语言处理程序”。它一般可分为解释程序和翻译程序两大类。
翻译程序： 翻译程序(Translator)是一种语言处理程序，它将输入的用程序设计语言书写的程序（称为源程序）转换为等价的用另一种语言书写的程序（称为目标程序）。若源语言是汇编语言，目标程序是机器语言，称这种翻译程序为汇编程序。若源语言是高级语言，目标程序是低级语言，称这种翻译程序为编译程序。
解释程序：解释程序（Interpreter）是一种语言处理程序，它对源程序逐个语句地进行分析，根据每个语句的含义执行语句指定的功能。
2．解答：
编译程序的总框图见图1.2。其中词法分析器，又称扫描器，它接受输入的源程序，对源程序进行词法分析，识别出一个个的单词符号，其输出结果是单词符号。
语法分析器，对单词符号串进行语法分析（根据语法规则进行推导或归约），识别出程序中的各类语法单位，最终判断输入串是否构成语法上正确的“程序”。
语义分析及中间代码产生器，按照语义规则对语法分析器归约出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代码。编译程序可以根据不同的需要选择不同的中间代码形式，有的编译程序甚至没有中间代码形式，而直接生成目标代码。
优化器对中间代码进行优化处理。一般最初生成的中间代码执行效率都比较低，因此要做中间代码的优化，其过程实际上是对中间代码进行等价替换，使程序在执行时能更快，并占用更小的空间。
目标代码生成器把中间代码翻译成目标程序。中间代码一般是一种机器无关的表示形式，只有把它再翻译成与机器硬件直接相关的机器能识别的语言，即目标程序，才能在机器上运行。
表格管理模块保持一系列的表格，登记源程序的各类信息和编译各阶段的进展状况。编译程序各个阶段所产生的中间结果都记录在表格中，所需要的信息也大多从表格中获取，整个编译过程都在不断地和表格打交道。
出错处理程序对出现在源程序中的错误进行处理。如果源程序有错误，编译程序应设法发现错误，把有关错误信息报告给用户。编译程序的各个阶段都有可能发现错误，出错处理程序要对发现的错误进行处理、记录，并反映给用户
Chapter 2
1． 试写出VT＝{0，1}上下述集合的正则表达式：
⑴ 所有以1开始和结束的符号串。
⑵ 恰含有3个1的所有符号所组成的集合。
⑶ 集合{01，1}。
⑷ 所有以111结束的符号串。
解答：⑴ 1(0|1)*1|1
⑵ 0*10*10*10*
⑶ 01|1
⑷ (0|1)*111
2．⑴ 试写出非负整数集的正则表达式。⑵ 试写出以非5数字为头的所有非负整数集的正则表达式。
解答：⑴ 0|(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*
万圣节派对⑵ 0|(1|2|3|4|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*
3．试将2.8中所示的有限状态自动机M最小化。
分析：只能对确定的有限状态自动机进行最小化，本题的自动机已经是确定的。
最小化采用状态分离法，具体做法如下：
① 进行0等价类的划分：Q划分为Qf与Q－Qf
② 若已进行了k等价划分，即Q已被划分成（Q1，Q2，…Qn），再进行k＋1划分，对Qi
（i＝1音乐术语…n），若q、q’∈Qi，使得对某一个a∈VT，δ（q，a）∈Qj和δ（q’，a）∈Ql，j≠l或δ（q，a）存在而δ（q’，a）不存在或反之。则将Qi划分为二个子集Qi1，Qi2，使q∈Qi1，q’ ∈Qi2。
③ 重复②直至无法进一步划分为止。对最后划分得到的状态子集中每一个子集，选择该子集中任何一个状态作为该状态子集的代表，然后修改原来的有限状态自动机的状态转换函数δ，凡在δ作用下转向某状态子集中任何一个状态的一律改成转向该状态子集的代表。若一个状态子集中某一状态是原来的开始状态，则该状态子集的代表就是新的有限状态自动机的开始状态。同理，若一个状态子集中的状态均是最终状态，则该状态子集的代表就是新的有限状态自动机的最终状态。
④ 抹去可能存在的无用状态与不可及状态。
解答：此有限状态自动机的状态转换表如表3.1所示：
表2.1 M的状态转换表
| a | b | ⊥ |
A | B | C | |
B | D | C | |
C | B | E | |
D | D | F | Accept |
E | G | E 吃泡面的幽默句子 | Accept |
F | G | E | Accept |
G | D | F | Accept |
| | | |
由此看出：此有限状态自动机是确定的。
最小化：
初始划分由2个子集组成，即：（{A,B,C},{D,E,F,G}）
集合{D,E,F,G}不需要进一步划分，考察子集{A,B,C}。由于
δ（B,a）=D∈{D,E,F,G}，而δ（A,a）＝δ（C,a）＝B∈{A,BC}，
因此Q可进一步划分为：（{A,C},{B},{D,E,F,G}）。由于
δ（A,b）＝C∈{A,C}，而δ（C，b）＝E∈{D,E,F,G}。
因此Q可进一步划分为：（{A},{C},{B},{D,E,F,G}）。
这时不能再划分了，得到的最小化的有限状态自动机如表3.2所示：
表2.2 最小化的有限状态自动机
| a | b | ⊥ |
A | B | C | |
C | B | 以为的拼音E | |
B | D | C | |
D | D | D | Accept |
切换窗口的快捷键 | | | |
4．某程序语言的无（正负）符号常数可以用下面正则表达式R来表示：
（D+E|D+.D+E|E|.D+E）((+|-)D|D)D*|D+|D*.D+
⑴ 试把它转换成确定性有限状态自动机。
⑵ 把上述有限状态自动机最小化。
⑶ 在上述有限状态自动机中添加相应动作，取出无（正负）符号常数。
分析：从正则表达式构造有限状态自动机可以分两步进行。
① 画一条从结点X到结点Y的有向弧，有向弧上标以正则表达式R。结点X为标以“－”的初始状态，结点Y为标以“＋”的最终状态。从这一有向图出发反复应用图3.2所示的替代规则，直至所有有向弧都以VT中的符号或标记ε为止。
图2.2 3条替代规则
② 消除应用①所得到的传递图中的ε弧，可以分为两步：首先消除ε环路，其次消除其他ε弧。
a) ε环路的消除方法：
i．将ε环路的诸项合并为一个顶点。
ii．修改各个相关的有向弧。
iii．若ε环路中某一状态是最终（或初始）状态，则新顶点是最终（或初始）状态。
b)其它冰抓ε弧的消除有两种方法：东坡肉的来历
1）子集法：即计算ε-Closure（T），其表示从状态集T中任何一状态沿ε弧可以到达的状态全体。
其要点是：从初始状态q0的X=ε-Closure（q0）开始，按如下方法构造状态集：
i．令Set＝{X}；
ii．若Set中还有未考察过的状态子集Xi，则对于每一输入符号a VT，求T=ε-Closure（move（Xi,a）），Set=Set∪{T}（其中move(Xi,a)={q|q δ(p,a),p Xi}）。重复执行（2），直至不存在这样的Xi。这样得到的Set即为消除ε弧后的确定的有限状态机（DFA）。
DFA的初始状态就是ε-Closure（q0），最终状态由那些至少含有一个最终状态的状态子集组成。
2）逐步消除法：
其要点是找到类似于图2.3所示，但从B再无ε弧引出的εPPPoE服务器弧。
