第一章引论1. 解释下列术语：编译程序、编译程序的前端和后端答：（1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。
（2）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。
通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。
（3）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。
2.一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。
答案：一个典型的编译程序通常包含 8 个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。
其各部分的主要功能简述如下：（1）词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。
（2）语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。
（3）语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。
（4）中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。
（5）中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。
（6）目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。
（7）表格管理程序：负责建立、填写和查找等一系列表格工作。
表格的作用是记录源程序的各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。
可以说整个编译过程就是造表、查表的工作过程。
需要指出的是，这里的“表格管理程序”并不意味着它就是一个独立的表格管理模块，而是指编译程序具有的表格管理功能。
（8）错误处理程序：处理和校正源程序中存在的词法、语法和语义错误。
当编译程序发现源程序中的错误时，错误处理程序负责报告出错的位置和错误性质等信息，同时对发现的错误进行适当的校正（修复），目的是使编译程序能够继续向下进行分析和处理。
4.对下列错误信息，请指出可能是编译的哪个阶段（词法分析、语法分析、语义分析、代码生成）报告的。
（1）else 没有匹配的if（2）数组下标越界（3）使用的函数没有定义（4）在数中出现非数字字符答案：（1）语法分析（2）运行时或者语义分析（3）语法分析（4）词法分析第三章文法和语言1.文法G＝({A,B,S},{a,b,c},P,S)其中P 为：S→Ac|aBA→abB→bc写出L(G[S])的全部元素。
答案：L(G[S])={abc}2.文法G[N]为：N→D|NDD→0|1|2|3|4|5|6|7|8|9G[N]的语言是什么？答案：长度至少为 1 的任意的数字串。
3.为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。
答案：G[S]:S->S+D|S-D|DD->0|1|2|3|4|5|6|7|8|94.已知文法G[Z]：(1)Z：：= aZb(2)Z：：= ab写出L(G[Z])的全部元素。
答案：L(G[Z]) = { a n b n | n≥1 }5.写一文法，使其语言是偶正整数的集合。
要求：(1) 允许0 打头；(2)不允许0 打头。
答案：(1)允许0 开头的偶正整数集合的文法E→NT|DT→NT|DN→D|1|3|5|7|9D→0|2|4|6|8(2)不允许0 开头的偶正整数集合的文法E→NT|DT→FT|GN→D|1|3|5|7|9D→2|4|6|8F→N|0G→D|08.文法G[S]为：S→Ac|aBA→abB→bc该文法是否为二义的？为什么？答案：由于对于文法 G[S] 的一个句子abc ，存在以下两个不同的最右推导：最右推导 1：最右推导 2：所以该文法为二义文法。
11.令文法G[E]为：E→T|E+T|E-TT→F|T*F|T/FF→(E)|i证明E+T*F 是它的一个句型，指出这个句型的所有短语、直接短语和句柄。
答案：按照句型的定义，由于存在推导，所以是该文法的一个句型。
通过构造该句型的语法树，可以直观地看出句型的所有的短语、直接短语和句柄。
该句型的语法树如下：所有的短语：所有的直接短语：句柄：13.一个上下文无关文法生成句子abbaa 的推导树如下：(1)给出串abbaa 最左推导、最右推导。
(2)该文法的产生式集合P 可能有哪些元素？(3)找出该句子的所有短语、直接短语、句柄。
(1)最左推导：最右推导：(2) 该文发的产生式集合 P 可能的元素：、、、、、。
(3) 所有短语：abbaa、a、bb、aa、ε、b；所有直接短语：a、ε、b；句柄：a。
第四章词法分析2.已知NFA＝（｛x,y,z｝,{0,1},M,{x},{z}），其中：M(x,0)={z}，M(y,0)={x,y}，,M(z,0)={x,z}，M(x,1)={x}，M(y,1)=φ，M(z,1)={y}，构造相应的DFA。
答案：先构造其矩阵用子集法将NFA 确定化：将x、z、xz、y、xy、xyz 重新命名，分别用A、B、C、D、E、F 表示。
因为B、C、F中含有z，所以它为终态。
DFA 的状态图：3.将下图确定化：答案：用子集法将NFA 确定化：0 1S VQ QUVQ VZ QUQU V QUZVZ Z ZV Z -QUZ VZ QUZZ Z Z重新命名状态子集，令VQ 为A、QU 为B、VZ 为C、V 为D、QUZ 为E、Z 为F。
0 1-S A BA C BB D E+C F FD F -+E C E+F F FDFA 的状态图：7.给文法G[S]：S→aA|bQA→aA|bB|bB→bD|aQQ→aQ|bD|bD→bB|aAE→aB|bFF→bD|aE|b构造相应的最小的DFA。
答案：相应的 NFA 为：a b-S A QA A B,ZB Q DQ Q D,ZD A BE B FF E D,Z+Z - -确定化：a b-S A QA A BZQ Q DZ+BZ Q D+DZ A BD A BB Q DM = {S,A,Q,D,B} ∪ {BZ,DZ}{S,A,Q,D,B}按照 b 可划分为 {S,D,B}∪{A,Q} M = {S,D,B} ∪ {A,Q} ∪ {BZ,DZ}{S,D,B}按照 b 可划分为 {S}∪{D,B}M = {S} ∪ {D,B} ∪ {A,Q} ∪ {BZ,DZ}已不能再划分，所以，状态 D与 B、A 与 Q、BZ 与 DZ 分别为等价状态。
删除D、Q 和 DZ：a b-S A Q→AA A BZQ Q DZ+BZ Q→A D→B+DZ A BD A BB Q→A D→B8.给出下述文法所对应的正规式：S→0A|1BA→1S|1B→0S|0答案：11.一种证明两个正则表达式等价的方法，那就是构造它们的最小 DFA，表明这两个 DFA 是一样的（当然状态名可以不同）。
使用此方法，证明下面的正则表达式是等价的。
(1) (a|b)*(2) (a*|b*)*(3) ((|a)b*)*解：（1）（2）a b±SAB SAB SAB（3）a b±SA SA SA第五章自顶向下语法分析方法例题1 已知文法 G[S]：S → aHH → aMd | dM → Ab | εA → aM | e①判断 G[S] 是否为 LL(1) 文法，若是，构造相应的预则分析表。
②若 G[S] 为 LL(1) 文法，给出输入串 aaabd# 的分析过程，并说明该串是否为 G[S] 的句子。
解：①【第 1 步】求出能推导出ε的非终结字符。
非终结字符S H M A能否推导出ε不可不可可不可【第 2.1 步】计算每一个终结或非终结字符 X 的 FIRST 集合：First(S) = {a}First(H) = {a,d}First(M) = first(A)∪{ε} = {a,e,ε}First(A) = {a,e}【第 2.2 步】计算每一个产生式右部的 FIRST 集合：First(aH) = {a}First(aMd) = {a}First(d) = {d}First(Ab) = first(A) = {a,e}First(ε) = {ε}First(aM) = {a}First(e) = {e}【第 3 步】计算每一个非终结字符 X 的 FOLLOW 集合：Follow(S) = {#}Follow(H) = follow(S) = {#}Follow(M) = {d}∪follow(A) = {b,d}Follow(A) = {b}【第 4 步】计算每一个产生式的 SELECT 集合：Select(S→aH) = {a}Select(H→aMd) = {a}Select(H→d) = {d}Select(M→Ab) = first(Ab) = {a,e}Select(M→ε) = follow(M) = {b,d}Select(A→aM) = {a}Select(A→e) = {e}【第 5 步】判别是否为 LL(1) 文法：由于：Select(H→aMd) ∩ Select(H→d) = ΦSelect(M→Ab) ∩ Select(M→ε) = ΦSelect(A→aM) ∩ Select(A→e) = Φ所以，该文法为 LL(1) 文法。
a b d e #S S→aHH H→aMd H→dM M→Ab M→εM→εM→AbA A→aM A→e ②步骤分析栈剩余输入串（第 1 个字符为当前输入字符）推导所用的产生式或匹配1 #S aaabd# S→aH2 #Ha aaabd# 匹配 a3 #H aabd# H→aMd4 #dMa aabd# 匹配 a5 #dM abd# M→Ab6 #dbA abd# A→aM7 #dbMa abd# 匹配 a8 #dbM bd# M→ε9 #db bd# 匹配 b10 #d d# 匹配 d11 # # 接受（分析成功）例题2.文法 G[S]：①试对 G[S] 进行改写，并判断改写后的文法是否为 LL(1) 文法？②通过这个例子，能够说明什么？解：①文法存在间接左递归，应该先将间接左递归转换为直接左递归。
有以下两种转换方法：转换方法 1：将代入中的 A，将间接左递归转换为直接左递归后，文法转换为：消除关于 S 的直接左递归后，文法转换为：由于所以，改写以后的文法为 LL(1) 文法。