整理完编译原理网上作业题

1、东北农业大学网络教育学院编译原理网上作业题第一章 编译概述一、多项选择题：1. 编译程序各阶段的工作都涉及到（）。（*）A. 语法分析 B. 表格管理 C. 出错处理 D. 语义分析 E. 词法分析2. 编译程序工作时，通常有（）阶段。 （*）A. 词法分析 B. 语法分析 C. 中间代码生成 D. 语义检查 E. 目标代码生成二、填空题：1解释程序和编译程序的区别在于（）。（*）2编译过程通常可分为 5 个阶段，分别是（）、（）、（）、（）和（ ）生成。（*）3编译程序工作过程中，第一段输入是（），最后阶段的输出为（）程序。（*）4编译程序是指将（）程序翻译成（）程序的程序。（*）三、综合题

2、：1. 画出编译程序的总体结构图，简述各部分的主要功能。（*）第二章 文法和语言的基本知识、多项选择题：1.下面哪些说法是错误的（）。（*）A. 有向图是一个状态转换图B. 状态转换图是一个有向图C. 有向图是一个 DFAD.DFA 可以用状态转换图表示2. 对无二义性文法来说，一棵语法树往往代表了（）。（*）A. 多种推导过程B.多种最左推导过程C. 一种最左推导过程D.仅一种推导过程E. 一种最左推导过程3. 如果文法 G 存在一个句子，满足下列条件（）之一时，则称该文法是二义文法。A. 该句子的最左推导与最右推导相同B. 该句子有两个不同的最左推导C. 该句子有两棵不同的最右推导 D.

3、该句子有两棵不同的语法树E. 该句子的语法树只有一个4. 有一文法G: St ABAt aAb| ecBd| e它不产生下面（）集合 （*）A.a nbmcsup >ndm|n,m0B.a nbn csup>mdm |n,m >0C.anbmcsup>mdn|n,m> 0D.anbncsup>mdm|n,m> 0E.anbncsup>ndm|n,n > 05. 自下而上的语法分析中，应从（）开始分析。 （*）A. 句型 B. 句子 C. 以单词为单位的程序 D. 文法的开始符 E. 句柄6. 对正规文法描述的语言，以下（）有能力描述它。 （

4、*）A.0 型文法 B.1 型文法 C. 上下文无关文法 D. 右线性文法 E. 左线性文法二、填空题：1文法中的终结符和非终结符的交集是（）。词法分析器交给语法分析器的文法符号一定是（），它一定只出现在产生式的（）部。（*）2最左推导是指每次都对句型中的（）非终结符进行扩展。（*）3在语法分析中，最常见的两种方法一定是（）分析法，另一是（）分析法。（*）4采用（）语法分析时，必须消除文法的左递归。（*）5（）树代表推导过程，（ ）树代表归约过程。（*）6自下而上分析法采用（）、归约、错误处理、（）等四种操作。（*）7. Chomsky把文法分为（）种类型，编译器构造中采用（）和（ ）文法，它

5、们分别产生（）和（ ）语言，并分别用（）和（ ）自动机识别所产生的语言。（*）三、判断题：1 文法 StaS|bR| eFTcS。描述的语言是（a|bc） * （*）2. 在自下而上的语法分析中，语法树与分析树一定相同。（*）3. 二义文法不是上下文无关文法。（*）4. 语法分析时必须先消除文法中的左递归。（*）5. 规范归约和规范推导是互逆的两个过程。（*）6. 一个文法所有句型的集合形成该文法所能接受的语言。（*）7. 有穷自动机接受的语言是正则语言。（*）&若r1和r2是上的正规式，则 r1|r2也是。（*）9. 令2 = a,b，则工上所有以b为首的字构成的正规集的正规式为b*

6、（a|b）* 。（*）四、简答题1 . 句柄:（*）2. 素短语：（*）3. 语法树：（*）4. 归约：（*）5. 推导：（*）五、问答题1. 给出上下文无关文法的定义。（*）2. 文法 GS ：St aSPQ|abQQi PQbPtbbbQtbccQtcc（1）它是Chomsky哪一型文法？（ 2）它生成的语言是什么？（*）3. 按指定类型，给出语言的文法。L=aibj|j >i > 1的上下文无关文法。（*）4. 有文法 G： St aAcB |BdAtAaB|cBtbScA|b( 1)试求句型 aAaBcbbdcc 和 aAcbBdcc 的句柄；( 2)写出句子 acabcb

7、bdcc 的最左推导过程。(*)5. 对于文法 GS ：St（ l） |aS|aLtL, S|S（1）画出句型（S, （a）的语法树。（ 2）写出上述句型的所有短语、直接短语、句柄和素短语。（*）6. 考虑文法 GS, 其产生式如下 :S(L)|aLtL, S|S(a) 试指出此文法的终结符号、非终结符号。(b) 给出句子(a,(a，a)的分析树。(c) 构造句子(a,(a，a)的一个最左推导。(d) 构造句子(a,(a，a)的一个最右推导。(e) 这个文法生成的语言是什么？ (*)7考虑文法 GT ：TtT*F|FFtFf P|PPt( T) |i证明T*Pf( T*F)是该文法的一个句型，

8、并指出直接短语和句柄。(*)8试描述下列文法产生的语言L(GS)(*)St10S0|aA AtbA|a9.已知语言L(G)=ab nc |n > 1试对该语言构造相应文法。(*)10证明下列文法的二义性(*)1 . GZ2. GSZtaZbZ|aZ|aStABAtbB|bC|baBtSb|ba|aCtBb|b11 .有文法 GS : StiSeS|iS|i该文法是否是二义的。试证明之。（*）12. 文法 GT : Tt aR FH Tb|d 生成的语言是什么？GT是否为3型文法？ （*）13. 试写出能够描述下列电话号码格式的文法。 （*）6739174201

9、0)6739174214. 试构造生成语言的上下文无关文法。 （*）（1） a nbnci | n > 1,i > 0 （2） w | w a,b且w中a的个数恰好比 b多1 GS:S -> S AND S | S OR15. 下面的二义性文法描述命题演算公式，为它写一个等价的非二义性文法。S | NOT S | p | q | (S)(*)16. 对于下列语言分别写出它们的正规表达式。（*）（1）英文字母组成的所有符号串，要求符号串中顺序包含五个元音。（2）英文字母组成的所有符号串，要求符号串中的字母依照词典顺序排列。第三章一、多项选择题：词法分析与有穷自动机1. 在词法分

10、析中，能识别出（）。（*）A.基本字 B.四元式C.运算符D.逆波兰式 E.常数2. 令刀=a,b,则刀上所有以 b开头，后跟若干个 ab的字的全体对应的正规式为(* + * +A.b(ab) * B.b(ab) + C.(ba) *b D.(ba) +bE.b(a|b)、填空题：1确定有限自动机 DFA是(2若二个正规式所表示的()的一个特例。(*)相同，则认为二者是等价的。(*)3一个字集是正规的，当且仅当它可由()所 ()。(*)三、判断题：1一个有限状态自动机中，有且仅有一个惟一终态。()2设 r 和 s 分别是正规式，则有 L( r|s ) =L(r)|L(s)。()3. 自动机M和

11、M的状态数不同，则二者必不等价。()4确定的自动机以及不确定的自动机都能正确地识别正规集。()5. 对任意一个右线性文法G,都存在一个 NFA M满足L(G)=L(M)。()6. 对任意一个右线性文法G,都存在一个 DFA M满足L(G)=L(M)。()7. 对任何正规表达式 e,都存在一个 NFA M满足L(G)=L(e)。() &对任何正规表达式 e,都存在一个 DFA M满足L(G)=L(e)。()9. 设M是一个NFA并且L(M) =x,y,z，则M的状态数至少为 4个。()10. 对任何一个 NFA M 都存在一个 DFA M'，使得L(M')=L(M)。()

12、四、综合题：1. 设M=( x,y, a,b, f,x,y)为一非确定的有限自动机，其中 f定义如下:f (x,a ) = x,y f (a,b ) = yf (y,a )=0 f (y,b ) = x,y试构造相应的确定有限自动机M。(*)2. 对给定正规式 b* (d|ad ) ( b|ab ) +，构造其 NFAMI (*)3. 字母表a , b上的正规式 R= ( ba|a ) *，构造R的相应DFA (*)4. 请写出在刀=(a,b )上，不是a开头的，但以aa结尾的字符串集合的正规表达式，并构造与之等价状 态最少的 DFAI(*)5. 人运狼、羊、菜过河，一次运一件，不让羊吃掉菜，

13、也不让狼吃掉羊，画出渡河的状态转换图。可否将其抽象为一个有限自动机。（*）6. 对于正规表达式b） a（a|b）构造最小状态的 DFA （*）第四章语法分析一、多项选择题：1. 一个LR分析器包括（）。(*)A. 一个总控程序B. 一个项目集C. 一个活前缀D. 一张分析表 E. 一个分析栈2.LR分析器核心部分是一张分析表，该表包括（）等子表。（*）A.LL（1）分析 B.优先关系 C.GOTO D.LR E.ACTION3. 每一项ACTIONS a所规定的动作包括（）。（*）A.移进 B.比较 C.接受 D.归约 E.报错4. 对LR分析表的构造，有可能存在（）动作冲突。（*）A.移进

14、B.归约 C.移进/归约D.移进/移进E.归约/归约5. 对LR分析器来说，存在（）等分析表的构造方法。（*）A.LALR B.LR (0)C.SLR (1) D.SLR (0)E.LR (1)6. 自上而下的语法分析方法有（）。（*）A.算符优先分析法B.LL (1)分析法 C.SLR (1)分析法D丄R ( 0)分析法 E.LALR (1)分析法、填空题:1.对于一个文法，如果能够构造文法。（*）（）。使得它的）均是唯一确定的，则称该文法为LR2. 字的前缀是指该字的（）。（*）3. 活前缀是指 （）的一个前缀，这种前缀不含（）之后的任何符号。（*）4. 在LR分析过程中，只要（）的已扫描

15、部分保持可归约成一个（），则扫描过的部分正确。5. 将识别（）的NFA确定化，使其成为以 （）为状态的DFA这个DFA就是建立 （）的基础。（*）6. Aa称为（）项目；对文法开始符 S'fa为（）项目；若a为终结符，则称Aaa 3为（）项目；若B为非终结符，则称 Aaa3为（）项目。（*）7. LR（ 0）分析法的名字中“ L”表示 （），“ R'表示 （），“ 0”表示 （）。三、判断题：1对一个右线性文法 G,必存在一个左线性文法 G'，使得L（G）=L（G'），反之亦然。（*）四、综合题：1. 构造下面文法的 LL( 1)分析表。 (*)D TLTt i

16、nt | realLt id RFT, id R |&2. 下面文法 GS 是否为 LL( 1)文法？说明理由。(*)STAB|PQxATxyBTbcPTdP| &QTaQ|&3. 设有以下文法： （*）GS ：STaAbDe|dATBSD|eBTSAc|cD| &DT Se| &（1 ）求出该文法的每一个非终结符U的FOLLO噪。（ 2）该文法是 LL（ 1）文法吗？（3）构造 CS 的 LL（ 1）分析表。4. 将文法 GV 改造成为 LL（1） 的。（*）GV ：VTN|NEETV|V+ENRi5. 已知文法：（*）GA ： AaAa| &

17、（ 1）该文法是 LL（ 1）文法吗？为什么？（ 2）若采用 LL（ 1）方法进行语法分析，如何得到该文法的LL （ 1）分析表？（3）若输入符号串“ aaaa”，请给出语法分析过程。6. 设有文法 GS 为：（*）St a|b|（A）At SdA|S（ 1）完成下列算符优先关系表，见下表，并判断GS 是否为算符优先文法。表 算符优先关系表（2）给出句型（SdSdS的短语、简单短语、句柄、素短语和最左素短语。（3）给出输入串（adb） #的分析过程。7. 设有文法 GS 为：（*）Sta|b|（A）AtSdA|S（ 1）完成下列算符优先关系表，见下表，并判断GS 是否为算符优先文法。表 算符优

18、先关系表(2) 给出句型(SdSdS的短语、简单短语、句柄、素短语和最左素短语。(3) 给出输入串( adb) #的分析过程。&对于文法GS : StAS|bA SA|a(1) 列出所有 LR (0)项目；(2) 列出构成文法LR (0)项目集规范族。(*)9有文法 GSSta| A | ( T)TtT, S|S该文法是否是 LL (1)文法，若不是，请进行改写。并给出它的分析表。(*)10有文法 GS( 1 )StA( 2)StB( 3)At aAb( 4 ) Atc( 5)Bt aBb( 6)Btd试构造相应的 LR( 0)项目集规范族及相应的分析表。(*)11. 已知文法 GS

19、，其产生式如下：St （L）|aLt L , S|S从GS中消除左递归，并为之构造一个非递归预测分析器LL（1）分析表。请说明在句子（a , （a ,a）上的分析器的动作。（*）12. 证明下面文法是 SLR（1）文法，并构造其 SLR分析表。Et E+T |TTt TF|FFt F*|a|b第五章一、多项选择题：语法制导翻译技术和中间代码生成1. 中间代码主要有（）。（*）A. 四元式 B. 二元式 C. 三元式 D. 后缀式 E. 间接三元式2. 在下面的（）语法制导翻译中，采用拉链 - 回填技术。（*）A.赋值语句B.goto 语句C.条件语句D.循环语句3. 下列（ ）中间代码形式有益

20、于优化处理。（*）A.三元式 B.四元式C.间接三元式D.逆波兰表示法E.树形表示法4. 在编译程序中安排中间代码生成的目的是（）。（*）A.便于进行存储空间的组织B.利于目标代码的优化C.利于编译程序的移植D.利于目标代码的移植E.利于提高目标代码的质量5. 三地址代码语句具体实现通常有（）表示方法。（*）A.逆波兰表示B.三元式C.间接三元式D.树形表示 E.四元式填空题：1中间代码有 （）、（）、（）、（） 等形式， 生成中间代码主要是为了使 （）( ) 时才能确定，因而) 。(*)串进行 ()。(*)3当源程序中的标号出现“先引用后定义”时，中间代码的转移地址须持 要进行 ()。(*)

21、4文法符号的属性有两种，一种称为( ) ，另一种称为 (5后缀式 abc-/ 所代表的表达式是()，表达式 (a-b)*c 可用后缀式()表示。(*)6用一张 () 辅以 () 的办法来表示中间代码，这种表示法称为间接三元式。(*)三、问答题：1给出下列表达式的逆波兰表示(后缀式)：(*) a*(-b+c) (A V B) A (C DA E)2 写出算术表达式：A+B*(C-D)+E/(C- D)f N 的：(*) 四元式序列； 三元式序列； 间接三元式序列3. 写出下面算术表达式E值的语义描述：(*)12(1) EE +E(2) 0(3) 14. 给出下列表达式的逆波兰表式。(*)(1)

22、aw b+cA a> d V a+be( 2) a=cA b=d( 3)( a*b-c ) *n+b* ( a+d/e )5. 分别写出语句 a:=b*-c+b*-c 的四元式、三元式和间接三元式的表示。 (*)6. 文法及其翻译方案为：P:=bQb print:”1” Q:=cR print:”2”Q:=a print:” 3” R:=Qad print:”4”当输入串为bccaadadb时，该翻译方案的输出是什么？ （*）7. 给定文法 GE :E:=T+E | T T:=F*T | F F:=i | (E)则求 i+i+(i*i)*i 的逆波兰表示。 (*)第六章 符号表的组织和管

23、理一、多项选择题：1. 符号表的每一项均包含（ ）。（*）A. 名字栏B. 类型栏C.信息栏D.值栏 E.ad均包含2. 对编译程序所用到的符号表，涉及的操作有（A. 填写或更新信息栏内容D. 杂凑技术E.B. 填入新名C.给定名字，访问它的有关信息线性表和排序二叉树3. 源程序中的错误一般有（）。（*）A. 词法错误 B .语法错误C .语义错误D. 编译错误E .违反环境限制的错误、填空题：1符号表中名字栏内容有两种填写方式，它们是） 填写和 （）填写。（*） 的办法纠正错误。（*）2词法分析阶段的错误主要是（） ，可通过 （）和（）过程中陆续填入。（*）3符号表中名字的有关信息在4在目标

24、代码生成阶段，符号表是（ ） 的依据。（*）三、简答题：1在编译过程中为什么要建立符号表？（*）2. 一个过程的活动记录中一般包含那些数据。 （*）第七章一、多项选择题：运行时的存储组织与管理1. 下面（ ）需要在运行阶段分配存储空间。（*）A.数组 B.指针变量C.动态数组D.静态变量E.动态变量2. 栈式动态分配允许（）。（*）A.递归过程B.分程序结构C.动态变量D.动态数组 E.静态数组3. 动态存储分配可采用的分配方案有（）。（*）A.队式存储分配B.栈式存储分配C.链式存储分配D.堆式存储分配E.线性存储分配4. 栈式动态分配与管理因调用而进入过程之后，要做的工作是（）。（*）A.

25、 定义新的活动记录的 SP B. 保护返回地址C. 传递参数值D.建立DISPLAY表E.定义新的活动记录的 TOP5. 静态分配不允许程序出现（）。（*）A.递归过程B.静态数组C.可变体积的数据项目D.待定性质的名字E.静态变量6. 活动记录包括（ ）。（*）A.局部变量B.连接数据C.形式单元D.局部数组的内情变量E.临时工作单元第八章 目标代码生成一、多项选择题：1. 根据优化所涉及的范围，可将优化分为（）。（*）A.局部优化B.过程优化C.全局优化 D.循环优化 E.四元式优化2. 下列优化中，属于循环优化的有（）。（*）E.代码外提A.强度削弱B.合并已知量C.删除无用赋值D.删除

26、归纳变量3. 如果ab是程序流图中的一条边，则由这条回边构成的循环由（）结点组成。（*）A.a B.bC.有通路到达b的结点D. 有通路到达a且该通路上不经过 b的结点E.有通路到达b且该通路上不经过 a的结点4.采用无环有向图（DAG，可以实现的优化有（）。（*）A.合并已知量B.删除公共子表达式C.强度削弱D.删除无用赋值 E.删除归纳变量5.编译程序的输出结果可以是（）。（*）A.目标代码B.汇编语言代码C.中间代码D.优化后的中间代码E.可重定位代码二、填空题:1.局部优化是（范围内进行的一种优化。（*）2 在一个基本块内，可实行3种优化方法，即合并已知量、)° (*)3 优

27、化就是对程序进行各种（）变换，使之能生成更有效的*)4.在优化中，可把循环中的）提到循环外面去，这种方法称为)° (*)东北农业大学网络教育学院编译原理作业题参考答案第一章 编译概述多项选择题：1. 编译程序各阶段的工作都涉及到（BC）。（*）A.语法分析B.表格管理C.出错处理 D.语义分析E.词法分析2. 编译程序工作时，通常有（ ABCE阶段。 （*）A.词法分析B.语法分析C.中间代码生成 D.语义检查E.目标代码生成填空题:1 解释程序和编译程序的区别在于（是否生成目标程序）。（*）2 编译过程通常可分为 5个阶段，分别是（词法分析）、（语法分析）、（中间代码生成）、（代码

28、优 化）和（目标代码）生成。（*）3编译程序工作过程中，第一段输入是（源程序），最后阶段的输出为（目标代码生成）程序。（*）4编译程序是指将（高级语言编写的）程序翻译成（目标语言）程序的程序。（*）综合题:1. 画出编译程序的总体结构图，简述各部分的主要功能。（*） 解答：编译程序的总体结构如下图所示：词法分析程序：输入源程序，进行词法分析，输出单词符号。语法分析程序：在词法分析的基础上，根据语言的语法规则（方法规则）把单词符号串分解成各类语 法单位，并判断输入串是否构成语法上正确的“程序”。中间代码生成程序：按照语义规则把语法分析程序归约（或推导）出的语法单位翻译成一定形式的中 间代码，比如

29、说四元式。优化程序：对中间代码进行优化处理。目标代码生成程序：把中间代码翻译成目标语言程序。表格管理模块保存一系列的表格，登记源程序的各类信息和编译各阶段的进展情况。编译程序各阶段 所产生的中间结果都记录在表格中，所需信息多数都需从表格中获取，整个编译过程中都在不断地和表格 打交道。出错处理程序对出现在源程序中的错误进行处理。此外，编译的各个阶段都可能出现错误。出错处理 程序对发现的错误都及时进行处理。第二章文法和语言的基本知识多项选择题：1. ABC 2. ACE 3. BCD 4. AC 5. BC填空题:1文法中的终结符和非终结符的交集是（空集）。词法分析器交给语法分析器的文法符号一定是

30、（终结符），它一定只出现在产生式的（右）部。（*）2最左推导是指每次都对句型中的（最左）非终结符进行扩展。（*）3在语法分析中，最常见的两种方法一定是（自上而上）分析法，另一是（自下而上）分析法。（*）4采用（自上而下）语法分析时，必须消除文法的左递归。（*）5. （语法）树代表推导过程，（分析）树代表归约过程。（*）6自下而上分析法采用（移进）、归约、错误处理、（接受）等四种操作。（*）7. Chomsky把文法分为（4）种类型，编译器构造中采用（2型）和（3型）文法，它们分别产生（上下文无关语言）和（正规语言）语言，并分别用（下推自动机）和（有限）自动机识别所产生的语言。（*）判断题：1正

31、确 2 .错误 3 .错误 4 .错误 5 .错误6. 错误7 .正确 8 .正确 9 .错误简答题1句柄：（*） 解答：一个句型的最左直接短语称为该句型的句柄。2. 素短语：（*）解答：至少含有一个终结符的素短语， 并且除它自身之外不再含任何更小的素短语。3. 语法树：（*）解答：满足下面 4 个条件的树称之为文法 GS 的一棵语法树。 每一终结均有一标记，此标记为VNU Vt中的一个符号； 树的根结点以文法 GS的开始符S标记； 若一结点至少有一个直接后继，则此结点上的标记为Vn中的一个符号； 若一个以A为标记的结点有 K个直接后继，且按从左至右的顺序，这些结点的标记分别为X,X2,Xk,

32、贝U AX1,X2,Xk, 必然是G的一个产生式。4. 归约：（*）解答：我们称 仏丫直接归约出a AB,仅当Ay是一个产生式，且a、B （VnU Vt） *。归约过程就是从输入串开始，反复用产生式右部的符号替换成产生式左部符号，直至文法开始符。5. 推导：（*）解答：我们称 a A3直接推出aY3, 即卩a A3 TayB，仅当丫是一个产生式，且 a、B (VnUVt)。如果a 1二：a 2二二：an,则我们称这个序列是从 a 1至a 2的一个推导。若存在一个从 a 1 a n的 推导，则称a 1可推导出a n。推导是归约的逆过程。问答题1 .给出上下文无关文法的定义。(*)解答：一个上下文

33、无关文法 G是一个四元式(Vt,Vn,S, P )，其中： Vt是一个非空有限集，它的每个元素称为终结符号； Vn是一个非空有限集，它的每个元素称为非终结符号，VtQVn=； S是一个非终结符号，称为开始符号； P是一个产生式集合(有限)，每个产生式的形式是ia,其中，PV N,a (VtUVn)*。开始符号S至少必须在某个产生式的左部出现一次。2. 文法 GS:St aSPQ|abQQP PQbPr bbbCH bc cCH cc(1) 它是Chomsky哪一型文法？(2) 它生成的语言是什么？ (*)解答：(1)由于产生式左部存在终结符号，且所有产生式左部符号的长度均小于等于产生式右部的符

34、号长 度，所以文法GS是Chomsky1型文法，即上下文有关文法。(2)按产生式出现的顺序规定优先级由高到低(否则无法推出句子)，我们可以得到：S abQ abcS 二；aSPQ二 aabQPg aabPQG； aabbQ冲：aabbcQ 二 aabbccS 二：aSPQ二 aaSPQP中 aaabQPQP生 aaabPQQPA aaabPQPQQ' aaaPPQQQ aaabbPqqq= aaabbQQF aaabbbcQQ二 aaabbbccQ 二 aaabbbccc于是得到文法 GS生成的语言L=a nbncn|n > 13. 按指定类型，给出语言的文法。L=aibj|j

35、>i > 1的上下文无关文法。(*)解答:由L=ai bj |j >i > 1知，所求该语言对应的上下文无关文法首先应有StaSb型产生式，以保证 b的个数不少于a的个数；其次，还需有 St Sb或St bS型的产生式，用以保证 b的个数多于a的个数；也即 所求上下文无关文法 GS为：GS : StaSb|Sb|b4. 有文法 G: St aAcB|BdAt AaB|c Bt bScA|b(1) 试求句型 aAaBcbbdcc和aAcbBdcc的句柄；(2) 写出句子 acabcbbdcc的最左推导过程。(*) 解答：(1 )分别画出对应两句型的语法树，如下图所示句柄:

36、AaB BdS(2)句子acabcbbdcc的最左推导如下:ST 二 aAcB= aAaBcB 二 acaBcB 二 acabcB = acabcbScA 二 acabcbBdcA= acabcbbdcA 二 acabcbbdcc5. 对于文法GS:St( L) |aS|aLt L, S|S(1) 画出句型(S, (a)的语法树。(2) 写出上述句型的所有短语、直接短语、句柄和素短语。(*)解答：(1)句型(S, ( a)的语法树如下图所示。(L )a图句型(S, (a)的语法树(2)由上图可知: 短语：S、a、(a)、S,(a)、(S,(a); 直接短语：a、S; 句柄：S; 素短语：素短语

37、可由图2-8-3中相邻终结符之间的优先关系求得，即;a) A#因此素短语为a。6. 考虑文法GS,其产生式如下：St (L)|aLtL, S|S(a) 试指出此文法的终结符号、非终结符号。(b) 给出句子(a,(a , a)的分析树。(c) 构造句子(a,(a , a)的一个最左推导。(d) 构造句子(a,(a , a)的一个最右推导。(e) 这个文法生成的语言是什么？ (*)解答：(a)终结符号为：(,),a,',非终结符号为：S,L开始符号为：S(b)分析树(L)Sa(S'E)(s's)(a,(L)(a,(L,S)(a,(S,S)(a,(a,S)(d)(a,(a,a

38、)(L)(L,S)(L,(L)(L,(L,S)(L,(L,a)(L,(S,a)(L,(a,a)(S,(a,a)(a,(a,a)(e) L(GS) = ( a i, a 2, a n)或 a其中a i(1 w i w n)是L(GS)。即L(GS)产生一个以a为原子的纯表，但不包括空表。 7考虑文法 GT ：TF *F|FFtFf P|PP( T) |i证明T*Pf( T*F)是该文法的一个句型，并指出直接短语和句柄。(*)解答：首先构造T*Pf( T*F)的语法树如下图所示。TF图句型T*Pf( T*F)的语法树由上图可知，T*Pf( T*F)是文法GT的一个句型。直接短语有两个，即P和T*F

39、 ;句柄为P。&试描述下列文法产生的语言L( GS)(*)St 10S0|aAAt bA|a解答：L(G)=(10) iabna0in0 i > 09.已知语言L(G)=ab nc |n > 1试对该语言构造相应文法。(*)解答：GZ:Zt aBCBt Bb|b10.证明下列文法的二义性(*)1. GZ2. GSZt aZbZ|aZ|aSt ABat bB|bC|baBt Sb|ba|aCt Bb|b解答：(1)对于句子aaaba,画出二棵不同的语法树，因而是二义的。（2）GS对于句子baba,画出二棵不同的语法树，因而是二义的。11 .有文法 GS : StiSeS|iS

40、|i该文法是否是二义的。试证明之。（*）解答:对于句子 iiiei ，有两棵不同的语法树，故文法是二义的。12. 文法 GT :aR FH Tb|d 生成的语言是什么？GT是否为3型文法？ （*）解答：不是 3 型文法。13. 试写出能够描述下列电话号码格式的文法。(*)67391742010-67391742(010)67391742解答： 文法产生式规则如下：<电话号码 > t <局代码 > <本机码 ><电话号码 >t <区前缀 > <局代码> < 本机码 ><区前缀 >t< 地区码 &

41、gt;<区前缀 >t('< 地区码 >)'<地区码 >tDIGDIG<地区码 >tDIGDIGDIG<局代码 >tDIGDIGDIG DIG<本机码 >tDIGDIGDIGDIG16. 试构造生成语言的上下文无关文法。 (*)(1) a nbnci | n > 1,i > 0 (2) w | w a,b +,且w中a的个数恰好比 b多1 解答：(1)把anbnci分成anbn和c，两部分，分别由两个非终结符号生成，因此，生成此文法的产生式为:S t ABA t aAb|abB t cB| e（2

42、）令S为开始符号，产生的 w中a的个数恰好比b多一个，令E为一个非终结符号，产生含相同个 数的a和b的所有串，则产生式如下：S t aE|Ea|bSS|SbS|SSbE t aEbE|bEaE| £GS:S -> S AND S | S OR17. 下面的二义性文法描述命题演算公式，为它写一个等价的非二义性文法。S | NOT S |p | q | （S）（*）解答：GS:S -> S AND A | AA -> A OR B | BB -> NOT B |p | q | （S）16.对于下列语言分别写出它们的正规表达式。（*）（1）英文字母组成的所有符号串，

43、要求符号串中顺序包含五个元音。（2）英文字母组成的所有符号串，要求符号串中的字母依照词典顺序排列。解答：（1） 令Letter表示除这五个元音外的其它字母。(letter)*A(letter)*E(letter)*l(letter)*O(letter)*U(letter)*(2)A*B*.Z*第三章词法分析与有穷自动机多项选择题：1. ACE 2. ABD填空题：1.确定有限自动机 DFA是（NFA ）的一个特例。（*）2 若二个正规式所表示的（正规集）相同，则认为二者是等价的。（*）3.个字集是正规的，当且仅当它可由（DFA/NFA）所 （识别）。（*）判断题：1.错误2 .错误3 .错误4

44、 .正确5 .正确6.正确 7 .正确 8 .正确 9 .错误 10 .正确综合题：)为一非确定的有限自动机，其中 f 定义如下：1 设 M=( x,y, a,b, f,x,yf ( x,a )= x,y f( a,b )= yf (y,a )=0 f (y,b ) = x,y试构造相应的确定有限自动机M。(*)解答：对照自动机的定义 M=(S,X ,f,S o,Z),由f的定义可知f(x,a) 、f(y,b)均为多值函数，所以是一非 确定有限自动机，先画出NFAM相应的状态图，如图下所示。图 NFAM用子集法构造状态转换矩阵下表所示。将转换矩阵中的所有子集重新命名而形成下表所示的状态转换矩阵

45、。表状态转换矩阵即得到M），其状态转换图如下图所示。=(0,1,2, a,b, f,0, 1,2将上图的DFAM最小化。首先，将 M的状态分成终态组1 , 2与非终态组0;其次，考察1,2由于 1,2a=1,2b=2 即整个划分只有两组 0 后，得到如下图所示化简1,2 ， 所以不再将其划分了，也1,2 ：令状态 1 代表1,2 ，即把原来到达 2 的弧都导向 1，并删除状态 2。 最DFAM。化简后的DFAM2. 对给定正规式 b* (d|ad ) ( b|ab ) +，构造其 NFAMI (*)解答：首先用a=aA改造正规式得：b*(d|ad)(b|ab)(b|ab)*;其次，构造该正规式

46、的NFAM如下图所示。图 NFAM3. 字母表a , b上的正规式 R= ( ba|a ) *，构造R的相应DFA (*)解答：II aI bx1yiy2lyiy22iyIIaI b123223324. 请写出在刀=(a,b )上，不是a开头的，但以aa结尾的字符串集合的正规表达式，并构造与之等价状 态最少的DFA (*)解答：根据题意，不以a开头就意味着以b开头，且以aa结尾的正规式为：b(a|b)* aa根将图1所示的NFA确定化，如图2所示。NFA将图1所示的NFA确定化，如图从图2可知已为最简状态，由于开始状态0只能输入字符b而不能与状态1合并，而状态2和状态32所示的状态转换矩面对输

47、入符号的下一状态相同，但两者一为非终态、一为终态，故也不有合并，故图 阵已是最简的 DFA如图3所示据正规式画出 NFA如图1所示。图 2 状态转换矩阵图 3 最简 DFA6. 人运狼、羊、菜过河，一次运一件，不让羊吃掉菜，也不让狼吃掉羊，画出渡河的状态转换图。可否将其抽象为一个有限自动机。(*)解答：先写出渡河的方法，串中对象顺序为人来回渡河时所运的货物的顺序： 羊空菜羊狼空羊 羊空狼羊菜空羊现给出一个 NFA:M=(S ,Q,0,9, S )其中=羊，空，菜，狼Q=0,1,2,3,4,5,6,7,8,9转形函数S （0,羊）=1,S （1,空）=2,S （2,菜）=3,S （2,狼）=5S

48、 （3,羊）=4,S （5,羊）=6,S （4,狼）=7,S （6,菜）=7S （7,空）=8, S （8,羊）=96.对于正规表达式 （a|b） *a（a|b） 构造最小状态的 DFA （*）解答：NFA M: DFA M: 化简： 中的DFA M中没有等价状态，因此为最小化的DFA M第四章语法分析多项选择题：1. AD 2. CE 3. ACDE 4. CE 5. ABCE 6. ACDE填空题：1对于一个文法，如果能够构造（LR（0）文法）。使得它的（每个入口）均是唯一确定的，则称该文法为LR文法。（*）2. 字的前缀是指该字的（任意首部）。（*）3. 活前缀是指（规范句型）的一个前缀

49、，这种前缀不含（句柄） 之后的任何符号。（*）4. 在LR分析过程中，只要（输入串） 的已扫描部分保持可归约成一个（活前缀），则扫描过的部分正确。（*）5. 将识别（活前缀）的NFA确定化，使其成为以（项目集合）为状态的DFA这个DFA就是建立 （LR分析算法）的基础。（*）6. Aa称为（归约）项目；对文法开始符S'fa为（接受）项目；若a为终结符，则称Aaa 3 为（移进） 项目；若B为非终结符，则称 Aaa 3为（待约） 项目。（*）7. LR ( 0)分析法的名字中“ L”表示(自左至右分析)R'表示(采用最右推导的逆过程即最左归约) ，“ 0”表示 (向右查看 0 个

50、字符) 。(*)判断题：1. 正确简答题：综合题：1构造下面文法的 LL (1 )分析表。(*)“ TLTt int | realLt id RFT, id R |&解答： LL( 1)分析表见下表。分析 虽然这个文法很简单，我们还是从求开始符号集合和后继符号集合开始。FIRST( D) =FIRST( T) =int, realFOLLOW( D) =FOLLOW( L)=#FIRST( L) =idFOLLOW( T) =idFIRST( R) = ，,&FOLLOW( R) =#有了上面每个非终结符的FIRST集合，填分析表时要计算一个产生式右部a的FIRST(a)就不是

51、件难事了。填表时唯一要小心的时，&是产生式RT&右部的一个开始符号，而 #在 FOLLO( R)中，所以RT&填在输入符号 #的栏目中。表 LL( 1)分析表2. 下面文法 GS是否为LL ( 1)文法？说明理由。(*)St AB|PQxxybePdP| eQaQ| e解答：该文法不是 LL (1)文法，见下面分析中的说明。分析 只有三个非终结符有两个选择。( 1 ) P 的两个右部 dP 和 e 的开始符号肯定不相交。(2) Q的两个右部aQ和e的开始符号肯定不相交。(3) 对S来说，由于x FIRST(AB)，同时也有x FIRST(PQx)(因为P和Q都可能为空)。所以该文 法不是 LL( 1 )文