编译原理作业集

第一章测试题一.解答题1:试述标识符与名字的区别。答案标识符是由字母和数字(有些语言中还允许含一些其他符号)组成的以字母(及其他符号)打头的字符串。若给某个标识符赋予确切的含义，这个标识符就称为名字。标识符只是抽象的字符序列，无确切的意义，而名字则是由标识符表示，且具有语义属性(如类型、种属等)的实体。2:将高级语言程序翻译为计算机可执行的目标程序有哪些途径？答案主要途径有两种:解释与编译。解释程序的特点是不先将高级语言程序全部翻译成机器代码，而是每读人一条高级语言程序语句，就用解释程序将其翻译成一段机器指令并执行之，然后再读人下一条语句继续进行解释、执行，如此反复，即边解释边执行，翻译所得的指令序列并不保存。编译程序的特点是先将高级语言程序翻译成机器语言程序，将其保存到指定的存储空间中，在用户箱要时再执行之,即先翻译后执行。3:何谓源程序、目标程序、翻译程序、编译程序和解释程序？它们之间可能有何种关系？答案源程序是指以某种程序设计语言编写并供加工处理的程序。目标程序是指编译程序(或解释程序)将源程序处理加工而得的另一种语言(目标语言)的程序。翻译程序是将用某种语言编写的程序翻译成另一种语言形式的程序的系统软件。编译程序与解释程序均为翻译程序，但二者工作方法不同。解释程序的特点是并不先将高级语言程序全部翻译成机器代码，而是每读入一条高级语言程序语句，就用解释程序将其翻译成一段机器指令并执行之，然后再读人下一条语句继续进行解释、执行，如此反复。即边解释边执行，翻译所得的指令序列并不保存。编译程序的特点是先将高级语言程序翻译成机器语言程序，将其保存到指定的存储空间中，在用户需要时再执行之。即先翻译后执行。第二章测试题一.解答题1:已给文法G[表达式]:试给出句子的规范推导，指出每步推导所得句型的句柄，并画出相应的语法树，指出树中的所有短语。答案规范推导(有下划线的子串为该句型的句柄)：相应的语法树如图解2.1所示。该语法树中有三个直接短语i,还有及也是短语，其中，最左侧的i为句子的句柄。2:试证明文法。答案显然,上述推导都是规范的，所以，该文法是二义性文法。3:化简文法：答案(1)首先，应消除那些推导不出终结符号串的非终结符。4:试分别构造产生下列语言的文法:答案5:试描述由下列文法所产生的语言的特点(文法的开始符号均为S)：答案6:设已给文法试指出此文法所产生的语言。答案7:设已给文法G[程序]:(1)给出句子的最左推导和最右推导。(2)画出上述句子的语法树。答案8:设答案9:对于下列的文法和相应的句子,试指出这些句子的全部短语；分别给出句子的最右推导，并指出各步直接推导所得句型的句柄。答案10:化简下列各个文法。答案第三章测试题一.解答题1:已知文法，试构造相应的状态换图。答案由于G是左线性文法，所以除了非终结符S，U各对应一个状态外，还应引人一个新状态R作为初态；S为唯一的终止状态。相应的状态转换图如图解3.1所示。2:将如图3.1所示的NFA确定化。答案相应DFA的状态转换图如图解3.2所示。3:将图3.2所示的带有一动作的NFA解定化。答案4:已知正规式，试构造相应的DFA,并将其最小化。答案5:画出用来识别如下三个关键字的状态转换图：答案6:假定有一个猎人带着一只狼、一头山羊和一棵白菜来到一条河的左岸，拟摆渡过河，而岸边只有一条小船，其大小仅能装载人和其余三件东西中的一件，也就是说，每一次猎人只能将随行者中的一件带到彼岸。若猎人将狼和山羊留在同一岸上而无人照管，那么，狼就会将羊吃掉；如果猎人把山羊和白菜留在同一岸，山羊也会把白菜吃掉。现在，请你用状态转换图作为工具,描述猎人可能采取的种种摆渡方案，并从中找出可将上述三件东西安全带到右岸的方案。答案图中，M，W,S，C分别代表人、狼、羊和白菜。每个状态中间的横线代表河，横线上、下侧的字母分别表示在左、右两岸现有的人或物。弧线上的字母表示正在过河的人和物。7:对于如图3.3所示的状态转换图：(1)写出相应的右线性文法；(2)指出它接受的最短输人串；(3)任意列出它接受的另外四个输入串；(4)任意列出它拒绝接受的四个输入串。答案8:对于下列的状态转换矩阵：(1)分别画出相应的状态转换图；(2)写出相应的3型文法；(3)用自然语言分别描述它们所识别的输人串的特征。答案(3)用正规式描述各FA所接受的正规集如下，读者不妨自行用自然语言解释所识别输入串的结构特征。9:对于下面所给的文法：(1)试分别对G1和G2构造相应的状态转换图(提示:对于右线性文法，可将形如的产生式视为；而对左线性文法，则可将它视为)。(2)对于，构造一等价的左线性文法；对于G2构造一等价的右线性文法。(3)对于和，分别给出如下符号串的推导序列：对于和分别给出如下符号串的推导序列：(4)试给出若干个不能由和产生的符号串，并验证它们同样不能由和产生。答案10:将如图3.4所示的NFA确定化和最小化。答案11:设r，s为任意的正规式，试证明下列关系式成立：答案可见上述四个正规式表征的正规集相同,所以,它们是等价的,原关系式成立。(2)略。(3)略。第四章测试题一.解答题1:消除文法G[S]:答案显然,其中S,A都是左递归的非终结符号。将此文法表示为矩阵形式：2:给定文法G[S]:答案首先计算出各候选式的FIRST集如表解所示。相应的LL(1)分析表如表解所示表解中，因为只需填写产生式右部符号串即可表示产生式,省略了产生式的左部符号。对进行预测分析的过程如表解所示。3:设已给文法G[S]:答案构造识别G[S]全部活前缀的DFA如图解所示。构造相应的LR(O)分析表如表解所示。4:给定文法G[B]:答案首先构造识别G[B]全部活前缀的DFA如图解所示。再构造SLR(l)分析表如表解.所示。5:给定文法G[S]:答案6:对于如下的文法，用某种高级语言写出递归下降分析程序。答案(1)文法没有左递归，以下是相应的递归下降分析程序：(2)消去文法左递归,并将消去左递归后的文法各产生式简记为以下是相应的递归下降分析程序：7:对于如下的文法，求出各个FIRST集和FOLLOW集。答案所给文法的各FIRST集和FOLLOW集如表解所示。8:试证明:任何具有左递归性的前后文无关文法均非LL(1)文法。答案9:试证明:任何LL(1)文法均为无二义性文法。答案10:对于如下的文法G[S]:答案此文法已满足LL(1)文法的三个条件。所以是LL(1)文法(2)文法的各非终结符的FIRST集和FOLLOW集如表解所示。的LL(1)分析表如表解4.5(b)所示。11:设已给文法答案(1)FlRST集和FOLLOW集如表解所示。12:试证明，任何算符文法不会有两个非终结符号相邻的句型。答案13:试证明，若G不是算符文法,则G至少有一个句型包含相邻的非终结符号。答案14:对于下列的文法，试分别构造它们的LR(O)项目集规范族及识别全部活前缀的DFA。答案(1)识别全部活前缀的DFA如表解所示(以表格的形式表示，很容易转化为图的形式，本章中其余的题目也是采用这种形式表示)。(2)识别全部活前缀的DFA如表解所示,所求的LR(O)项目规范族(3)识别全部活前缀的DFA如表解所示。(4)识别全部活前缀的DFA如表解所示。15:对于习题14中的各文法，判别哪些是LR(O)文法，并对它们构造相应的LR(O)分析表。答案(1)是LR(O)文法,其SLR(l)分析表如表解所示。(2)是LR(O)文法，其SLR(l)分析表如表解所示。(3)是LR(O)文法,其SLR(l)分析表如表解所示。(4)因为12中含有冲突项目，所以不是LR(O)文法,其SLR(l)分析表如表解所示。(所以可以用SLR(l)规则解决冲突)，16:判断下面的文法是哪一类LR文法，并构造LR分析表。答案识别全部活前缀的DFA如表解所示。LR(O)分析表如表解所示。由此可见是LR(O)文法。17:下列文法是否为SLR(l)文法？若是,构造相应的SLR(l)分析表，若不是，则阐明其理由。答案(1)识别全部活前缀的DFA如表解所示。其中，项目同时具有移进和归约项目，对于，，所以SLR(l)规则不能解决冲突,从而该文法不是SLR(l)文法。(2)识别全部活前缀的DFA如表解所示。其中不存在冲突项目，故该文法是LR(0)文法，也是SLR(l)文法。SLR(l)分析表如表解所示。(3)先求识别全部活前缀的DFA如表解所示。其中不存在冲突项，故该文法是LR(O)文法，也是SLR(l)文法。SLR(l)分析表如表解所示。(4)先求识别全部活前缀的DFA如表解所示。因为，所以冲突项目可以用SLR⑴规则得以解决，从而该文法为SLR(l)文法。其SLR(l)分析表如表解所示。(5)原文法可等价地化为先求识别全部活前缀的DFA如表解所示。其中不存在冲突项,故该文法是LR(0)文法，也是SLR(l)文法。SLR(l)分析表如表解所示。(6)原文法可等价形式：先求识别全部活前缀的DFA如表解所示。因为，故冲突项目可以通过SLR(l)规则来解决，从而该文法为SLR(l)文法。SLR(l)分析表如表解所示。18:对如下的文法分别构造LR(O)及SLR(l)分析表，并比较两者的异同。答案识别活前缀的DFA及LR(O)分析分别如表解所示。两表的异同：两表都用ACTION表和GOTO表反映了移进、归约(包括接受)的状态和动作。不同之处在于SLR(l)增加了在归约的时候考虑向前符号，以解释可能出现的“移进-归约”冲突；SLR(l)的分析稀疏'些，原因是填写归约项时,并不是在一个状态对应行上全部填写归约动作，而是考虑了相应非终结符的FOLLOW集因素。另外，SLR(l)分析的效率更高一些，因为在检测错误方面,SLR(l)比LR(0)分析发现得更早些。19:对于文法：(1)构造LR(1)分析表；(2)给出用LR(1)分析表对输人符号串abab的分析过程。答案(1)求LR(1)项目集和状态转换表，得到表解。相应的LR(1)分析表如表解所示。(2)用LR(1)分析表对输人符号串abab的分析过程如表解所示。20:对于如下的文法，构造LR(1)项目集族，并判断它们是否为LR(1)文法。答案(1)求LR(1)项目集和状态转换图，得到表解。相应的LR(1)分解表如表解所示。表中没有多重定义的元素，所以文法是LR(1)文法。(2)用LR(1)分析法得到表解。用LALR(l)分析(合并同心集)，得到表解。LR(1)分析表如表解所示。可以看出，表中无冲突项目，所以是LR(1)文法。LALR(l)分析如表解所示。21:下列文法是否为LR(1)文法？若不是,能否将它们改写为等价的LR(1)文法。答案(1)求LRU)项目集和状态转换图，得到表解。依据表解4.14(a)求出该文法的LR(1)分析表，由于项目15,16存在多重定义的元素，所以不是LR(1)文法。事实上,从文法本身可以看出它是二义性的，因此不可能是LR(1)文法。等价的LR(1)文法为另外，对原文法的冲突项来说,若考虑算术运算符的运算优先级别，以及结合方式，上述冲突是可解决的。例如，假设表达式运算满足左结合律(即而不是右结合律，及*运算的优先级高于+运算,则上述文法相应的LR(1)分析表可改为如表解所示的表。(2)LR(1)项目集和状态转换如表解所示。由表中可看出，有移进一归约冲突，不是LR(1)文法。依据表解求出该文法的LR(1)分析表知道由于项目导致了有多重定义的元素，所以不是LR(1)文法。⑷略。22:设已给文法G[S]:试证明G是LL(1)文法,但不是SLR⑴文法。答案在文法G[S]中，只有非终结符S有两个候选式：AaAb及BbBa,而两个候选的FIRST集分别为，它们不相交，所以，文法G[S]满足LL(1)文法的条件,是LL(1)文法。在SLR(l)方法识别活前缀的DFA中，项目中出现归约一归约冲突,而，用SLR(1)方法不能解决冲突。第五章测试题一.解答题1:将PASCAL程序的条件语句翻译为逆波兰表示。答案2:写出对表达式进行自顶向下分析的属性翻译文法。答案首先