2023年编译原理复习题考试.pdf

《2023年编译原理复习题考试.pdf》由会员分享，可在线阅读，更多相关《2023年编译原理复习题考试.pdf（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译原理复习题一、是非题1.计算机高级语言翻译成低档语言只有解释一种方式。（X）3 .每个文法都能改写为L L（1）文法。（X）4 .算符优先关系表不一定存在相应的优先函数。（J）5 .L R分析方法是自顶向下语法分析方法。（X）6 .“用高级语言书写的源程序都必须通过编译，产生目的代码后才干投入运营”这种说法。（x）7 .一个句型的句柄一定是文法某产生式的右部。N）8 .仅考虑一个基本块，不能拟定一个赋值是否真是无用的。N）9 .在中间代码优化中循环上的优化重要有不变表达式外提和削减运算强度。（x）1 0 .对于数据空间的存贮分派，F O R T R AN采用动态贮存分派策略。（x）1 1

2、.甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。（x）1 2 .递归下降分析法是自顶向下分析方法。N）1 3 .产生式是用于定义词法成分的一种书写规则。（x）1 4 .在S L R（l）分析法的名称中，S的含义是简朴的。（V）1 5 .综合属性是用于“自上而下”传递信息。（x）1 6 .符号表中的信息栏中登记了每个名字的属性和特性等有关信息，如类型、种属、所占单元大小、地址等等。（x）1 7 .程序语言的语言解决程序是一种应用软件。（x）1 8 .解释程序合用于C O B O L和F O R T R A N语言。（x）1 9.一 个L L文法一定是无二义的。

3、（J）2 0 .正规文法产生的语言都可以用上下文无关文法来描述。（J）2 1 .一张转换图只包具有限个状态，其中有一个被认为是初态，最多只有一个终态。（X）2 2 .目的代码生成时，应考虑如何充足运用计算机的寄存器的问题。（J）2 2 .逆波兰法表达的表达式亦称后缀式。（4）2 3.假如一个文法存在某个句子相应两棵不同的语法树，则称这个文法是二义的。（7）2 4 .数组元素的地址计算与数组的存储方式有关。（J）2 5 .算符优先关系表不一定存在相应的优先函数。（x）2 6 .编译程序是对高级语言程序的解释执行。（x）2 7 .一个有限状态自动机中，有且仅有一个唯一的终态.（x）2 8 .一个算

4、符优先文法也许不存在算符优先函数与之相应。（4）2 9 .语法分析时必须先消除文法中的左递归。（x）3 0 .L R分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出犯错地点。W）3 1 .逆波兰表达法表达表达式时无须使用括号。N）3 2 .静态数组的存储空间可以在编译时拟定。（J）3 3 .进行代码优化时应着重考虑循环的代码优化，这对提高目的代码的效率将起更大作用。（J）3 4.两个正规集相等的必要条件是他们相应的正规式等价。（J）3 5 .一个语义子程序描述了一个文法所相应的翻译工作.（x）3 6 .设 r 和 s 分别是正规式，则有L（r|s）=L（r）L（s）。（x）3 7 .

5、拟定的自动机以及不拟定的自动机都能对的地辨认正规集。（“）3 8 .词法分析作为单独的一遍来解决较好。（x）3 9 .构造LR分析器的任务就是产生LR分析表。（）40 .规范归约和规范推导是互逆的两个过程。（J）41 .同心集的合并有也许产生新的“移进”/“归约”冲突。（x）42 .L R分析技术无法合用二义文法。（x）43 .树形表达和四元式不便于优化，而三元式和间接三元式则便于优化。（x）44.程序中的表达式语句在语义翻译时不需要回填技术。（4）45 .对中间代码的优化依赖于具体的计算机。（x）46 .若一个句型中出现了某产生式的右部，则此右部一定是该句型的句柄。（x）47 .在程序中标记

6、符的出现仅为使用性的。（x）48 .削减运算强度破坏了临时变量在一基本块内仅被定义一次的特性。（x）49 .编译程序与具体的机器有关，与具体的语言无关。（x）二、选择题（请在前括号内选择最确切的一项作为答案划一个勾，多划按错论）1 .一个编译程序中，不仅包含词法分析，（A）,中间代码生成，代码优化，目的代码生成等五个部分。A.语法分析 B.文法分析 C.语 言 分 析 D.解释分析2 .语法分析器则可以发现源程序中的（D ）。A.语义错误B.语法和语义错误 C.错误并校正D.语法错误3.解释程序解决语言时，大多数采用的是（B ）方法。A.源程序命令被逐个直接解释执行B.先将源程序转化为中间代码

7、，再解释执行C.先将源程序解释转化为目的程序，再执行D.以上方法都可以4 .编译程序是一种（B）。A.汇编程序 B.翻译程序 C.解释程序 D.目的程序5 .文法分为四种类型，即。型、1 型、2型、3型。其中3型文法是（B ）。A.短语文法 B.正则文法 C.上下文有关文法 D.上下文无关文法6 .通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目的代码生成等五个部分,还应涉及（C）。A.模拟执行器 B.解释器 C.表格解决和犯错解决 D.符号执行器7 .一个句型中的最左（B）称为该句型的句柄。A.短语 B.简朴短语 C.素短语 D.终结符号8 .文法 G E|：E-T

8、 I E +TT F I T *FF a I（E ）该文法句型E +F *（E +T）的简朴短语是下列符号串中的（B）。（E +T ）E +T F F *（E +T）A.和 B.和 C.和 D.9 .词法分析器用于辨认（C）。A.句子 B.句型 C.单词 D.产生式1 0 .在自底向上的语法分析方法中，分析的关键是（A ）。A.寻找句柄 B.寻找句型 C.消除递归 D.选择候选式1 1 .文 法 G 产生的（D）的全体是该文法描述的语言。A.句型 B.终结符集 C.非终结符集 D.句子1 2 .若 文 法 G 定义的语言是无限集，则文法必然是（A ）。A.递归的 B.前后文无关的 C.二义性的

9、 D.无二义性的1 3.四种形式语言文法中，1 型文法又称为(C)文法。A.短语结构文法 B.前后文无关文法 C.前后文有关文法D.正规文法14.一个文法所描述的语言是(A)。A.唯一的B.不唯一的C.也许唯一，好也许不唯一D.都不对15.(B)和代码优化部分不是每个编译程序都必需的。A.语法分析B.中间代码生成C.词法分析D.目的代码生成16.(B)是两类程序语言解决程序。A.高级语言程序和低档语言程序B.解释程序和编译程序C.编译程序和操作系统D.系统程序和应用程序17.数组的内情向量中肯定不具有数组的(D)的信息。A.维数B.类型C.维上下界D.各维的界差18.一个上下文无关文法G 涉及

10、四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组(D)。A.句子B.句型C.单词D.产生式1 9.文法分为四种类型，即 0 型、1 型、2 型、3 型。其中2 型文法是(D)。A.短语文法 B.正则文法C.上下文有关文法D.上下文无关文法20.文 法 G 所描述的语言是(C)的集合。A.文 法 G 的字母表V 中所有符号组成的符号串B.文 法 G 的字母表V 的 闭 包 V*中的所有符号串C.由文法的开始符号推出的所有终极符串D.由文法的开始符号推出的所有符号串21.词法分析器用于辨认(C)。A.字符串B.语句 C.单词D.标记符2 2.文法分为四种类型，即 0 型、

11、1 型、2 型、3 型。其中0 型文法是(A)。A.短语文法B.正则文法C.上下文有关文法D.上下文无关文法24.(A)是一种典型的解释型语言。A.BASIC B.C C.FORTRAND.PASCAL25.与编译系统相比,解释系统(D)。A.比 较 简 朴，可移植性好，执行速度快B.比较复杂，可移植性好，执行速度快C.比较简朴，可移植性差，执行速度慢D.比较简朴，可移植性好，执行速度慢26.用高级语言编写的程序经编译后产生的程序叫(B)。A.源程序 B.目的程序 C.连接程序 D.解释程序27.词法分析器用于辨认（A）。A.字符串 B.语句 C.单词 D.标记符28.编写一个计算机高级语言的

12、源程序后，到正式上机运营之前，一般要通过（B）这几步：（1）编辑 编 译（3）连 接（4）运营A.（1）（4）B.C.D.29.把汇编语言程序翻译成机器可执行的目的程序的工作是由（B）完毕的。A.编译器 B.汇编器 C.解释器 D.预解决器31.词法分析器的输出结果是（C）。A.单词的种别编码 B.单词在符号表中的位置 C.单词的种别编码和自身值 D.单词自身值32.正 规 式 M 1 和 M 2 等价是指（C）oA.M l和 M 2的状态数相等 B.M l和 M 2的有向边条数相等C.M l和 M 2所辨认的语占集相等 D.M l和 M 2状态数和有向边条数相等33.文法G：SxSx|y所辨

13、认的语言是（C）。A.xyx B.（xyx）*C.xyx（n 0）D.x*yx*34.假如文法G 是无二义的，则它的任何句子a（A）。A.最左推导和最右推导相应的语法树必然相同 B.最左推导和最右推导相应的语法树也许不同C.最左推导和最右推导必然相同 D.也许存在两个不同的最左推导，但它们相应的语法树相同35.构造编译程序应掌握（D）。A.源程序 B.目的语言 C.编译方法 D.以上三项都是36.四元式之间的联系是通过（B）实现的。A.指示器 B.临时变量 C.符号表 D.程序变量37.表达式（1 AVB）A（CVD）的逆波兰表达为（B）。A.ABVACDV B.A-BVCDVA C.ABVq

14、CDVA D.A-）BVACDV38.优化可生成（D）的目的代码。A.运营时间较短 B,占用存储空间较小C.运营时间短但占用内存空间大 D.运营时间短且占用存储空间小39.下列（C）优化方法不是针对循环优化进行的。A.强度削弱B.删除归纳变量 C.删除多余运算D.代码外提40.编译程序使用（B）区别标记符的作用域。A.说明标记符的过程或函数名 B.说明标记符的过程或函数的静态层次C.说明标记符的过程或函数的动态层次 D.标记符的行号41.编译程序绝大多数时间花在（D）上。A.犯错解决 B.词法分析 C.目的代码生成 D.表格管理42.编译程序是对（D）。A.汇编程序的翻译 B.高级语言程序的解

15、释执行 C.机器语言的执行 D.高级语言的翻译43.采用自上而下分析，必须（C）。A.消除左递归 B.消除右递归 C.消除回溯 D.提取公共左因子44.在规范归约中，用（B）来刻画可归约串。A.直接短语 B.句柄 C.最左素短语 D.素短语45.若 a 为终结符，则 A-a a0为（B）项目。A.归约 B.移进 C.接受 D.待约46.间 接 三元式表达法的优点为（A）。A.采用间接码表，便于优化解决 B.节省存储空间，不便于表的修改C.便于优化解决，节省存储空间 D.节省存储空间，不便于优化解决47.基本块内的优化为（B）。A.代码外提，删除归纳变量 B.删除多余运算，删除无用赋值C.强度削

16、弱，代码外提 D.循环展开，循环合并48.在目的代码生成阶段，符号表用（D）。A.目的代码生成 B.语义检查 C.语法检查 D.地址分派49.若项目集k 具有A-a，则在状态k 时，仅当面临的输入符号aGFOLLOW（A）时，才采用“A-a”动作的一定是（D）A.LALR文法 B.LR（0）文法 C.LR文法 D.SLR文法50.堆式动态分派申请和释放存储空间遵守（D）原则。A.先请先放 B.先请后放 C.后请先放 D.任:苣三、填空题1.编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,中间代码生成，代码优化等儿个基本阶段,同时还会伴有表格解决 和 犯错解决_O2.编译方式与解释

17、方式的主线区别在于一是否生成H的代码。3.产生式是用于定义一语法成分一的一种书写规则。4.设G是一个给定的文法，S是文法的开始符号，假 如S-x(其 中xG V T*),则 称x是文法的一个一句子。5.自顶向下的语法分析方法的基本思想是：从文法的一开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导一，试图推导出文法的一句子，使之与给定的输入串一 匹配o6.常用的参数传递方式有 传 地 址 传值和传名。7.一个句型中的最左简朴短语称为该句型的一 句柄8.对于文法的每个产生式都配备了一组属性的计算规则，称 为 _ 语 义规则。9.一个典型的编译程序中，不仅涉及一词法分析、一

18、语法分析、_中间代码生成一、代码优化、目的代码生成等五个部分，还应涉及表格解决和犯错解决。10.从功能上说，程序语言的语句大体可分为_执行性 语句和_ 说明性 语句两大类.11.扫描器的任务是从_源程序 中辨认出一个个一单词符号12.产生式是用于定义语法范畴 的一种书写规则。13.语法分析是依据语言的语法 规则进行的，中间代码产生是依据语言的语义 规进行的。14.语法分析器的输入是 单词符号串其输出是语法单位15.一个名字的属性涉及_类型 和 _ 作用域。16.逆波兰式ab+c+d*e-所表达的表达式为(a+b+c)*d-e。17.语法分析最常用的两类方法是_ 自 上而下 和 自下而上一 分

19、析 法。18.计算机执行用高级语言编写的程序重要有两种途径：解释和编译。19.扫描器是一词法分析器，它接受输入的_源程序,对源程序进行一 词法分析 _ 并辨认出一个个单词符号，其输出结果是单词符号，供语法分析器使用。20.自上而下分析法采用 移进_、归约、错误解决、接受一等四种操作。21.一个LR分析器涉及两部分：一个总控程序和 一张分析表22.后缀式abc-/所代表的表达式是 a/(b-c)_。23.局部优化是在基本块 范围内进行的一种优化。24.词法分析基于_ 正则 文法进行，即辨认的单词是该类文法的句子。25.语法分析基于上下文无关 文法进行，即辨认的是该类文法的句子。语法分析的有效工具

20、是语法树。26.分析句型时，应用算符优先分析技术时，每步被直接归约的是_最左素短语一，而应用L R分析技术时，每步被直接归约的是一 句 柄27.语义分析阶段所生成的与源程序等价的中间表达形式可以有_逆波兰_、一 四 无式表达与 三元式及达等。28.按 Chomsky分类法，文法按照 规则定义的形式进行分类。29.一个文法能用有穷多个规则描述无穷的符号串集合(语言)是由于文法中存在有 递归定义的规则。四、简答题1.写一文法，使其语言是偶正整数的集合，规定：(1)允许0 打头；(2)不允许0 打头。解：(l)GSHS,P,D,N,0,l,2,.,9,P,S)P:S-PD|DP-NP|ND-0|2|

21、4|6|8N-0|l|2|3|4|5|6|7|8|9(2)GS=(S,P,R,D,N,Q,0 2.,9,P,S)P:S-PD|P0|DP-NR|NR-QR|QD-2|4|6|8N-I|2|3|4|5|6|7|8|9Q-0|l|2|3|4|5|6|7|8|92.构造正规式相应的NFA:I(0|l)*1010解 1(011)*101相应的NFA为 13.写出表达式(a+b*c)/(a+b)d 的逆波兰表达和三元式序列。逆波兰表达：abc*+ab+/d三元式序列：(*,b,c)(+,a,)(+,a,b)(/,，)(一，d)4.已知 文 法 G S为：S-dABA-aA|aBB*G S产生的语言是什么

22、？答：GS产生的语言是 L(GS)=da|2 1,根2 0 。5.构造正规式相应的 DFA:1(1010*1 1(010)*1)*0解：1(1010*|1(010)*1)*0 相 应 的 NFA 为6.已知文法G(S)Sia|A|(T)TT,S|S写出句子(a,a),a)的规范归约过程及每一步的句柄。解：句型归约规则句柄(a,a),a)S 一aa(S.a),a)TSS(T,a),a)S-aa(T,S),a)TTT,ST,S(S),a)TSS(T),a)SS(T)(T)(S a)TSS(T,a)S aa(T,S)TT,ST,S(T)S-(T)(T)7.写一个文法，使其语言是奇数集，且每个奇数不以

23、0 开头。解：文法G(N)：N-AB|BA 一 AC|DB-1|3|5|7|9D-B|2|4|6|8C-O|D8.设文法G(S)：S一(L)|a S|aLL,S|S(1)消除左递归和回溯；(2)计算每个非终结符的FIRST和 FOLLOW。解：S(L)|aS，S-S,LTSLLJSL%(2)FIRST)S)=(,aFOLLOW(S)=#,)FIRST(S)=,a,EFOLLOW(S)=#,)FIRST(L)=(,aFOLLOW(L)=)FIRST(L)=,FOLLOW(L)=)9.已知文法G(E)ETT|E+TTF|T*FF-(E)|i(1)给出句型(T*F+i)的最右推导；(2)给出句型(T

24、*F+i)的短语、素短语。解：(1)最右推导：E=T-F=(E)-(E+T)=(E+F)-(E+i)=(T+i)=(T*F+i)短语：(T*F+i),T*F+i,T*F,i素短语：T*F,i10.While a0 V b0 then a：=a 1else b：=b+lEnd；翻译成四元式序列。解：(l)(j,a,0,5)(2)(j,3)(3)(jV,b,0,5)(4)(j,，,15)(5)(+,X,1,Tl)(6)(：=,Tl,X)(7)G,a,0,9)(8)(j,12)(9)(-,a,1,T2)(10)(：=,T2,a)一，,1)(1 2)(+,b,1,T 3)(1 3)(：=,T 3,一，

25、b)(1 4)0，一，一，1)(1 5)1 1.写出下列表达式的三地址形式的中间表达。5+6*(a +b);(2)f o r j:=l t o 1 0 d o a j+j :=O o答：(1)1 0 0:t l:=a+b1 0 1:t 2:=6*t l1 0 2:t 3:=5+t 2(2)1 0 0:j:=l1 0 1:i f j 1 0 g o t o NEXT1 0 2:i:=j+j1 0 3:a l i :=01 2.设基本块p由如下语句构成：T O:=3.1 4;T 1 :=2*T 0 ;T 2:=R+r;A:=T 1 *T 2；B:=A;T 3 :=2*T 0 ;T 4:=R+r;T

26、 5 :=T 3 *T 4;T 6 :=R-r ；B:二T5 町 6 ；试给出基本块p的DAG。解：基本块p 的 DAG图：1 3.写出表达式(a+b)/(a-b-(a+b*c)的三元序列及四元序列。解：(1)三元式：(+,a,b)(一，a,b)(/,，)(*,b,c)(+,a,)(一，)(2)四元式：(十,a,b,T l)(一，a,b,T2)(/,Tl,T2,T3)(*,b,c,T4)(+,a,T4,T5)(-,T3,T5,T6)1 4.写一个文法使其语言为偶数集，且每个偶数不以0 开头。解：文法G(S)：S-AB|B|AOAAD|CBT2|4|6|8CT1|3|5|7|9|BDO|C15.

27、设 文 法 G(S)：SS+aF|aF|+aFF 一*aF|*a(1)消除左递归和回溯：(2)构造相应的FIRST和 Follow集合。解：(1)S-aFS|+aFSS+aFSleF-*aFF-F|(2)FIRST(S)=a,+FOLLOW(S)=#FIRST(S)=+,FOLLOW(S)=#FIRST(F)=*FOLLoW(F)=(+,#FIRST(F1)=*,8)FOLLOW(+,#16.简要说明语义分析的基本功能。答：语义分析的基本功能涉及：拟定类型、类型检查、语义解决和某些静态语义检查。17.考虑文法GS:S (T)|a+S|aT-T,S|S消除文法的左递归及提取公共左因子。解：消除文

28、法GS的左递归：S-(T)|a+S|aT一 STT f STI 提取公共左因子：S(T)|aSzST+S I TTSTT f ST|18.试为表达式w+(a+b)*(c+d/(e-10)+8)写出相应的逆波兰表达。解：w ab+c d e 10-/+8+*+19.按照三种基本控制结构文法将下面的语句翻译成四元式序列：while(AC A B 1)C=C+1;else while(A D)A=A+2;解：该语句的四元式序列如下(其中E l、E2和 E3分别相应A C/B D、A*和 AWD,并且关系运算符优先级高)：100(j,A,C,102)101 0113)102(j,B,D,IO4)103

29、(J 一 13)104。=,A,1,106)105G，,108)106(+,C,1,C)108(jAc|aBA-abB-bc写 出 L(GIS)的所有元素。解：S=Ac=abc或 S=aB=abc所以 L(GS尸abc22.构造正规式1(0|1)*101相应的DFA。解：先构造NFA：拟定化:0XAABACABYAACAACAABABABYAB重新命名，令 A B为 B、AC为 C、ABY为 D 得:所以，可得DFA为:01XAAABBCBCADDCBS-an(T)T-T,S|S对(a,(a,a)和(a,a),A,(a),a)的最左推导。解：对(a,(a,a)的最左推导为：S=XT)=(T,S

30、)=(S,S)=(a,S)=(a,(T)=(a,(T,S)=(a,(S,S)=(a,(a,S)=(a,(a,a)对(a,a),A,(a),a)的最左推导为:S=(T)=(T,S)=(S,S)=(T),S)=(T,S),S)=(T,S,S),S)=(S,S,S),S)=(T),S,S),S)=(T,S),S,S),S)=(S,S),S,S),S)=(a,S),S,S),S)=(a,a),S,S),S)=(a,a),A,S),S)=(a,a,(T),S)=(a,a)F,(S),S)=(a,a,(a),S)=(a,a)F,(a),a)2 4.文法：S-MH|aH-LSo|K-dML|L-eHfM-K

31、|bLM判 断G是 否 为L L(1)文法，假如是，构 造L L(1)分析表。解：各符号的F I R S T集和FOLLOW集为:FIRSTFOLLOWs a,d,b,e ,e#,。M d,e,b e,#,。H#。L e a,d,b,e,o,#)K e 篇。预测分析表为:a0defb#S-a-MH-MH-MHM-K-K-K-bLM-KH-LSo-L-eHfK-s-dML-8-由于预测分析表中无多重入口，所以可鉴定文法是L L(1)的。2 5 .叙述由下列正规式描述的语言(a)0(0|l)*0(b)(e|0)1*)*(c)(0|1)*0(0 1 1 )(0 1 1)(d)0*1 0*1 0*1

32、0*(e)(0 0|l l)*(0 1|l 0)(0 0|l l)*(0 1|1 0)(0 0 1 1 1)*)*解：(a)以0开头、以0结尾的所有0和1的串。(b)由0和1组成的串，涉及空串。(c)倒数第3个字符为0,由0和1组成的串。(d)具有3个1的所有0和1的串。(e)由偶数个0和偶数个1构成的所有0和1的串。26.已知 文 法GS：S-(L)|aL-L,S|S为句子(a,(a,a)构造最左推导和最右推导。解：句子(a,(a,a)的最左推导为：S=(L)=(L,S)=(S,S)=(a,S)=(a,(L)=(a,(L,S)=(a,(S,S)=(a,(a,S)=(a,(a,a)句子(a,(

33、a,a)的最右推导为：S=(L)=(L,S)=(l,(L)=(L,(L,S)=(L,(L,a)=(L,(S,a)=(L,(a,a)=(S,(a,a)=(a,(a,a)五.计算题1.构造下述文法G S J的自动机：S-AOA-AO|S1|O该自动机是拟定的吗？若不拟定，则对它拟定化。解：由于该文法的产生式S-AO,A-A0|S1中没有字符集V T 的输入，所以不是拟定的自动机。要将其他拟定化，必须先用代入法得到它相应的正规式。把 S?AO代入产生式A?S1有：A=AO|AO 110=A(0|01 )|0=0(0|01 )*代由于状态A 有 3 次输入0 的反复输入，所以上图只是N F A,下面将

34、它拟定化：下 表 由 子 集 法 将 NFA 转 换 为DFA:IIo-closu re(Move To(I,0)Ib-e-closure(MoveAWBXBXCX,Y,ZCX,Y,ZCX,Y,ZBXF-*F|Q-由上表可知DFA为：2.对下面的文法G：E-TEE-+E|8T-FTfT-T|F-PFbP-(E)|a|b|A计算这个文法的每个非终结符的FIRST集 和 FOLLOW集。(2)证明这个方法是LL(1)的。(3)构造它的预测分析表。解：(1)计算这个文法的每个非终结符的FIRST集和FOLLOW集。FIRST集合有：HRST(E)=FIRST(T)=FIRST(F)=FIRST(P)

35、=(,a,b,A;FIRST但尸+,FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,A;FIRSTfT尸FIRST(T)U e=(,a,b,A,8;FIRST(F)=FIRST(P)=(,a,b,A;FIRST(FFIRST(P)=*,8;FIRST(P)=(,a,b,A)；FOLLOW集合有：FOLLOW(E)=),#;FOLLOW(E)=FOLLOW(E)=),#;FOLLOW(T)=FIRST(E)U FOLLOW。尸+)#;不包含 8FOLLOW(T)=FOLLOW(T)=FIRST(E)U FOLLOW(E)=+,),#;FOLLOW(F)=FIRST(T)U FO

36、LLOW(T)=(,a,bj,+,),#;不包含 FOLLOW(F)=FOLLOW(F)=FIRST(T,)U FOLLOW(T)=(,a,b,八,十)#;FOLLOW(P)=FIRST(F)U FOLLOW(F尸八,+,),#;不包含 证明这个方法是LL的。各产生式的SELECT集合有：SELECT(E-TE,)=HRST(T)=(.a,b,A);SELECT(E-+E)=+;SELECT(E-8)=FOLLOW(E/)=),#SELECT(T-FT,)=FIRST(F)=(,a,b,八 ;SELECT(T-T)=FIRST(T)=(,a,b,A;SELECT(T-8)=FOLLOW(T/)

37、=+,),#；SELECT(F-PF)=FIRST(P)=(,a,b,A;SELECT(F-*F)=*;SELECT(F,-)=FOLLOW(F,)=(,a,b,A,+,),#;SELECT(P-(E)=(SELECT(P-a)=aSELECT(P-b)=bSELECT(P-A)=A可见，相同左部产生式的SELECT集的交集均为空，所以文法GE是 LL(1)文法。(3)构造它的预测分析表。文法GE的预测分析表如下:+*()ab*#E-TE,UTEf TE3+E-8T-FT/TFTFT-FTr-8-T-T3 TT-F-PFyPF-PF?-PFZF-e今8-e-8-8-eP-(E)3 a-b-*3

38、.已知 NFA=(x,y,z,O,l,M,x,z),其中:M(x,O)=z,M(y,O)=x,y,M(z,O)=x,z,M(x,l)=x,M(y,l)=(p,M(z,l)=y,构造相应的 DFA 并最小化。解:根据题意有NFA图:表 由 子 集 法 将 NFA 转 换 为DFAIIo-e-closHre(Movslo(lO)Ii-e-closurefMoveTbfl,1)AxBzAxBzC x,zDyC x3 zC区 zE x,yDyEx,yEx,yFx,%zAxF 区 外 zF x,y,zEx,y下面将该DFA最小化：(1)一方面将它的状态集提成两个子集：P1=A,D,E,P2=B,C,F

39、区分 P2:由于 F(F,1 )=F(C,1 )=E,F(F,O)=F 并且 F(C,0尸C,所以 F,C 等价。由于 F(B,O)=F(C,O)=C,F(B,1 )=D,F(C,1 )=E,而D,E不等价(见下步)，从而B与C,F可以区分。有P21=C,F,P22=B。区分PI:由于A,E输入0到终态，而D输入0不到终态，所以D与A,E可以区分，有Pl 1=A,E,P12=D。(4)由于F(A,O)=B,F(E,O)=F,而B,F不等价，所以A,E可以区分。(5)综上所述，DFA可以区分为P=A,B,D,E,C,F。所以最小化的DFA如下：S-aK|(T)T-T,S|S构造它的LR(O)分析

40、表。解：加入非终结符S,方法的增广文法为:S-SS-aS-(T)T-T,ST-S下面构造它的LR(O)项目集规范族为:a()，#STIo：s/-*sS-A(T)I?：SIs：I ：S-(-T)Tj FST-SS 4-aS-S-(T)I i：sz-s*I iacc工：IsI :(!)T-T,ST-Ss 7.S-(T)1=IsIK：T f SIs：S-(T-)T-T-，SIs：S-T fT SIT：Ie：T-T,-SS-*aSf(T)I?：la：T-T,SS-aSfS-*(T)1=工3I工，T-T,S-工，从上表可看出，不存在移进-归约冲突以及归约归约冲突，该文法是LR(O)文法。从而有下面的LR

41、(O)分析表:状态A C T I O NG O T Oa*()s#ST0S;s.s11a c c2XiX irxr iXiXi3Xcr2r：r：Xcr24s：S5S655STSo6r5r5r5r5X5r57r3r5r5r31 3r38s：S5S99rrrrrr5.已知文法A-aAd|aAb|8判断该文法是否是SL R(I)文法，若是构造相应分析表，并对输入串ab#给出分析过程。解：增长一个非终结符S/后，产生原文法的增广文法有：Sf-AA-aAd|aAb|下 面 构 造 它 的LR(O)项 目 集 规 范 族 为号abd#AIo：A aA dIc：A-a*AdA-abAbA-*aAdA-*aA

42、bII：Ii：accIc：A-aAdA-a*AbA aA dI：L：aAdA3aAbL：aAdA-aA*bI：A-aAb*Is：A-aAd*IsA-aAb*I5：A3aAd从 上 表 可 看 出，状 态10和12存 在 移 进-归 约 冲 突，该 文 法 不 是LR(0)文 法。对 于10来 说 有：F O LLO W(A)n a =b,d,#n a =a P|(T)T-T,S|S(1)计算 G S 的 FIRSTVT 和 LASTVT。(2)构 造 G S 的算符优先关系表并说明G S是否未算符优先文法。(3)计 算 G S 的优先函数。(4)给出输入串(a,a)#的算符优先分析过程。解：(1 )各符号的FIRSTVT和 LASTVT：FIRSTVTLASTVTSTa、八、(,、a、八、(a、八、),、a、八、)(2)算符优先关系表:a()9A#a(=)A#*(3)相应的算符优先函数为:a()A#s212221T331131(4)句子(a,a)#分析过程如下:步骤栈优先关系当前符号剩余输入串移进或归约1#(a,a)#移进2(aa,a)#移进3赳aa，9a)#归约4抵Fa)#移进5研,aA)#移进6)#归约7F,F)#归 线)8F(三)#移进9#归约10怖#接受