2022年编译原理复习题 3.pdf

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

1、1 编译原理复习题一、是非题1计算机高级语言翻译成低级语言只有解释一种方式。( ) 3每个文法都能改写为 LL(1) 文法。 ( ) 4算符优先关系表不一定存在对应的优先函数。 ( ) 5LR分析方法是自顶向下语法分析方法。 ( ) 6“ 用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行” 这种说法。 ( ) 7一个句型的句柄一定是文法某产生式的右部。( )8仅考虑一个基本块，不能确定一个赋值是否真是无用的。( )9在中间代码优化中循环上的优化主要有不变表达式外提和削减运算强度。( ) 10对于数据空间的存贮分配，FORTRAN 采用动态贮存分配策略。( ) 11甲机上的某编译

2、程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。( ) 12递归下降分析法是自顶向下分析方法。( )13产生式是用于定义词法成分的一种书写规则。( ) 14在SLR(1) 分析法的名称中，S 的含义是简单的。( )15综合属性是用于“ 自上而下” 传递信息。 ( ) 16符号表中的信息栏中登记了每个名字的属性和特征等有关信息，如类型、种属、所占单元大小、地址等等。( ) 17程序语言的语言处理程序是一种应用软件。( ) 18解释程序适用于COBOL 和 FORTRAN 语言。( ) 19一个LL(l) 文法一定是无二义的。( ) 20正规文法产生的语言都可以用上下文无关文法

3、来描述。( ) 21一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。( ) 22目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。( ) 22逆波兰法表示的表达式亦称后缀式。 ( )23如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。( )24数组元素的地址计算与数组的存储方式有关。( ) 25算符优先关系表不一定存在对应的优先函数。( ) 26编译程序是对高级语言程序的解释执行。( ) 27一个有限状态自动机中，有且仅有一个唯一的终态。( ) 28一个算符优先文法可能不存在算符优先函数与之对应。( )29语法分析时必须先消除文法中的左递归。 (

4、 ) 30LR 分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。( )31逆波兰表示法表示表达式时无须使用括号。( )32静态数组的存储空间可以在编译时确定。() 33进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。( ) 34两个正规集相等的必要条件是他们对应的正规式等价。( ) 35一个语义子程序描述了一个文法所对应的翻译工作。( ) 36设 r 和 s 分别是正规式，则有L(r|s)=L(r)L(s) 。( ) 37确定的自动机以及不确定的自动机都能正确地识别正规集。( )38词法分析作为单独的一遍来处理较好。( ) 39构造 LR 分析器

5、的任务就是产生LR 分析表。( )40规范归约和规范推导是互逆的两个过程。() 41同心集的合并有可能产生新的“ 移进 ”/ “归约 ” 冲突。( ) 42LR 分析技术无法适用二义文法。( ) 43树形表示和四元式不便于优化，而三元式和间接三元式则便于优化。( ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 18 页 - - - - - - - - - 2 44程序中的表达式语句在语义翻译时不需要回填技术。( )45对中间代码的优化依赖于具体的计算机。( ) 46若

6、一个句型中出现了某产生式的右部，则此右部一定是该句型的句柄。( ) 47在程序中标识符的出现仅为使用性的。( ) 48削减运算强度破坏了临时变量在一基本块内仅被定义一次的特性。( ) 49编译程序与具体的机器有关，与具体的语言无关。( ) 二、选择题 ( 请在前括号内选择最确切的一项作为答案划一个勾，多划按错论) 1 一个编译程序中，不仅包含词法分析，( A )，中间代码生成，代码优化，目标代码生成等五个部分。A语法分析B文法分析C语言分析D解释分析2 语法分析器则可以发现源程序中的( D )。A语义错误 B语法和语义错误C错误并校正D语法错误3 解释程序处理语言时 , 大多数采用的是( B

7、)方法。A源程序命令被逐个直接解释执行B先将源程序转化为中间代码 , 再解释执行C先将源程序解释转化为目标程序 , 再执行D以上方法都可以4 编译程序是一种( B )。A汇编程序B翻译程序C解释程序 D目标程序5 文法分为四种类型，即0 型、 1 型、2 型、 3型。其中 3 型文法是 ( B )。A.短语文法 B 正则文法C上下文有关文法 D上下文无关文法6 通常一个编译程序中，不仅包含词法分析，语法分析， 中间代码生成， 代码优化， 目标代码生成等五个部分，还应包括 ( C )。A模拟执行器 B解释器 C表格处理和出错处理D符号执行器7 一个句型中的最左( B )称为该句型的句柄。A短语B

8、简单短语C素短语D终结符号8 文法 GE ：ET E T TF T F Fa （ E ）该文法句型E F (E T) 的简单短语是下列符号串中的( B )。 （ E T ） E T F F (E T) A和 B 和 C和 D9 词法分析器用于识别( C )。A句子B句型C单词D产生式10 在自底向上的语法分析方法中，分析的关键是( A ) 。A寻找句柄B寻找句型C消除递归D选择候选式11 文法G 产生的 ( D )的全体是该文法描述的语言。A句型B终结符集C非终结符集D句子12 若文法G 定义的语言是无限集，则文法必然是( A ) 。A递归的B前后文无关的C二义性的D无二义性的13 四种形式语

9、言文法中，1 型文法又称为 ( C )文法。A短语结构文法B前后文无关文法C前后文有关文法D正规文法14 一个文法所描述的语言是( A ) 。A唯一的B不唯一的C可能唯一，好可能不唯一D都不对15 ( B )和代码优化部分不是每个编译程序都必需的。A语法分析B中间代码生成C词法分析D目标代码生成16( B ) 是两类程序语言处理程序。A高级语言程序和低级语言程序B解释程序和编译程序名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 18 页 - - - - - - - - -

10、 3 C编译程序和操作系统D系统程序和应用程序17 数组的内情向量中肯定不含有数组的( D ) 的信息。A维数B类型C维上下界D各维的界差18. 一个上下文无关文法G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 ( D )。A句子B句型C单词D产生式19 文法分为四种类型，即0 型、 1 型、 2 型、3 型。其中 2 型文法是 ( D ) 。A短语文法B正则文法C上下文有关文法D上下文无关文法20文法G 所描述的语言是( C )的集合。A文法G 的字母表V 中所有符号组成的符号串B文法G 的字母表V 的闭包V* 中的所有符号串C由文法的开始符号推出的所有终

11、极符串D由文法的开始符号推出的所有符号串21词法分析器用于识别( C )。A字符串B语句C单词D标识符22文法分为四种类型，即0 型、 1 型、2 型、 3型。其中 0 型文法是 ( A ) 。A短语文法B正则文法C上下文有关文法D上下文无关文法24( A ) 是一种典型的解释型语言。ABASICBC CFORTRAN DPASCAL 25与编译系统相比，解释系统( D )。A比较简单, 可移植性好, 执行速度快B比较复杂, 可移植性好, 执行速度快C比较简单, 可移植性差, 执行速度慢D比较简单, 可移植性好, 执行速度慢26用高级语言编写的程序经编译后产生的程序叫( B )。A源程序B目标

12、程序 C连接程序D解释程序27词法分析器用于识别( A ) 。A字符串B语句 C单词 D标识符28编写一个计算机高级语言的源程序后, 到正式上机运行之前，一般要经过( B ) 这几步 : (1) 编辑(2) 编译(3) 连接(4) 运行A(1)(2)(3)(4) B(1)(2)(3) C(1)(3) D (1)(4) 29把汇编语言程序翻译成机器可执行的目标程序的工作是由( B )完成的。A编译器 B汇编器 C解释器 D预处理器31词法分析器的输出结果是( C )。A单词的种别编码B单词在符号表中的位置C单词的种别编码和自身值D单词自身值32 正规式M 1 和 M 2 等价是指 ( C )。A

13、M1 和 M2 的状态数相等BM1 和 M2 的有向边条数相等CM1 和 M2 所识别的语言集相等DM1 和 M2 状态数和有向边条数相等33 文法 G：SxSx|y 所识别的语言是( C )。Axyx B(xyx)* C)0(nyxxnnDx*yx* 34如果文法G 是无二义的，则它的任何句子 ( A ) 。A最左推导和最右推导对应的语法树必定相同B最左推导和最右推导对应的语法树可能不同C最左推导和最右推导必定相同D可能存在两个不同的最左推导，但它们对应的语法树相同35构造编译程序应掌握( D )。A源程序B目标语言C编译方法D以上三项都是36四元式之间的联系是通过( B )实现的。A指示器

14、B临时变量C符号表D程序变量37表达式 ( AB)(CD)的逆波兰表示为( B )。AAB CDBAB CD CAB CDDAB CD38. 优化可生成 ( D )的目标代码。A运行时间较短B占用存储空间较小名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 18 页 - - - - - - - - - 4 C运行时间短但占用内存空间大D运行时间短且占用存储空间小39下列 ( C )优化方法不是针对循环优化进行的。A强度削弱B删除归纳变量C删除多余运算D代码外提40编译程序使

15、用( B )区别标识符的作用域。A说明标识符的过程或函数名B说明标识符的过程或函数的静态层次C说明标识符的过程或函数的动态层次D标识符的行号41编译程序绝大多数时间花在( D )上。A出错处理B词法分析C目标代码生成D表格管理42 编译程序是对( D )。A汇编程序的翻译B高级语言程序的解释执行C机器语言的执行D高级语言的翻译43 采用自上而下分析，必须( C )。A消除左递归B消除右递归C消除回溯D提取公共左因子44在规范归约中，用( B )来刻画可归约串。A直接短语B句柄C最左素短语D素短语45 若 a为终结符，则A- a 为( B ) 项目。A归约B移进C接受D待约46间接三元式表示法的

16、优点为( A ) 。A采用间接码表，便于优化处理B节省存储空间，不便于表的修改C便于优化处理，节省存储空间D节省存储空间，不便于优化处理47基本块内的优化为( B )。A代码外提，删除归纳变量B删除多余运算，删除无用赋值C强度削弱，代码外提D循环展开，循环合并48. 在目标代码生成阶段，符号表用( D )。A目标代码生成B语义检查C语法检查D地址分配49若项目集Ik含有 A- ，则在状态k 时，仅当面临的输入符号aFOLLOW(A) 时，才采取 “A- ” 动作的一定是 ( D )。ALALR 文法BLR(0) 文法CLR(1) 文法DSLR(1) 文法50堆式动态分配申请和释放存储空间遵守(

17、 D )原则。A先请先放B先请后放C后请先放D任意三、填空题1 编译程序的工作过程一般可以划分为词法分析, 语法分析 , 语义分析 , 中间代码生成, 代码优化等几个基本阶段,同时还会伴有_表格处理 _和 _ _出错处理 _。2编译方式与解释方式的根本区别在于_是否生成目标代码_。3产生式是用于定义_语法成分 _的一种书写规则。4设 G 是一个给定的文法，S是文法的开始符号，如果S-x( 其中 xVT*), 则称x 是文法的一个 _句子 _。5自顶向下的语法分析方法的基本思想是：从文法的_开始符号 _开始，根据给定的输入串并按照文法的产生式一步一步的向下进行_直接推导 _，试图推导出文法的_句

18、子 _，使之与给定的输入串_匹配 _。6常用的参数传递方式有_传地址 _，传值和传名。7一个句型中的最左简单短语称为该句型的_句柄 _。8对于文法的每个产生式都配备了一组属性的计算规则，称为_语义规则 _ 。9一个典型的编译程序中，不仅包括_词法分析 _、_语法分析 _、_中间代码生成_、代码优化、目标代码生成等五个部分，还应包括表格处理和出错处理。10 从功能上说，程序语言的语句大体可分为_执行性 _语句和 _说明性 _语句两大类。11 扫描器的任务是从_源程序 _中识别出一个个_单词符号 _。12 产生式是用于定义_语法范畴 _的一种书写规则。13语法分析是依据语言的_语法 _规则进行的，

19、中间代码产生是依据语言的_语义 _规进行的。14语法分析器的输入是_单词符号串 _，其输出是 _语法单位 _。15一个名字的属性包括_类型 _和_作用域 _。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 18 页 - - - - - - - - - 5 16逆波兰式ab+c+ d*e- 所表达的表达式为_(a+b+c)*d-e _ 。17语法分析最常用的两类方法是_自上而下 _和_自下而上 _分析法。18计算机执行用高级语言编写的程序主要有两种途径：_解释 _和_编译

20、_。19扫描器是 _词法分析器 _，它接受输入的_源程序 _，对源程序进行_词法分析 _并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。20自上而下分析法采用_移进 _、归约、错误处理、_接受 _等四种操作。21一个 LR 分析器包括两部分：一个总控程序和_一张分析表 _。22后缀式abc-/所代表的表达式是_a/(b-c)_。23局部优化是在_基本块 _范围内进行的一种优化。24词法分析基于_正则 _文法进行，即识别的单词是该类文法的句子。25 语法分析基于_上下文无关 _文法进行， 即识别的是该类文法的句子。语法分析的有效工具是_语法树 _。26分析句型时，应用算符优先分析

21、技术时，每步被直接归约的是_最左素短语 _，而应用LR 分析技术时，每步被直接归约的是_句柄_。27语义分析阶段所生成的与源程序等价的中间表示形式可以有_逆波兰 _、_四无式表示 _与_三元式表示_等。28按 Chomsky 分类法，文法按照_规则定义的形式_进行分类。29一个文法能用有穷多个规则描述无穷的符号串集合（语言）是因为文法中存在有_递归 _定义的规则。四、简答题1. 写一文法，使其语言是偶正整数的集合, 要求：(1) 允许 0 打头；(2) 不允许 0打头。解： (1)GS=(S,P,D,N,0,1,2,9,P,S) P: S-PD|D P-NP|N D-0|2|4|6|8 N-0

22、|1|2|3|4|5|6|7|8|9 (2)GS=(S,P,R,D,N,Q ,0,1,2,9,P,S) P: S-PD|P0|D P-NR|N R-QR|Q D-2|4|6|8 N-1|2|3|4|5|6|7|8|9 Q-0|1|2|3|4|5|6|7|8|9 2. 构造正规式相应的NFA : 1(0|1)*101 解 1(0|1)*101 对应的 NFA 为3. 写出表达式 (ab*c)/(a b)d 的逆波兰表示和三元式序列。逆波兰表示：abc*ab/d三元式序列： (* ，b，c) (， a， ) (， a，b) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - -

23、- - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 18 页 - - - - - - - - - 6 (/， ) (， d) 4. 已知文法GS 为：S dAB AaA|aBBb| GS 产生的语言是什么？答： GS 产生的语言是L(GS)=0, 1|mnbdamn 。5. 构造正规式相应的DFA : 1(1010 * | 1(010) * 1) * 0。解：1(1010 * | 1(010) * 1) * 0对应的NFA为：6. 已知文法 G(S) Sa| |(T) TT ，S|S 写出句子 (a，a)，a)的规范归约过程及每一步的句柄。解：句型

24、归约规则句柄(a，a)， a) Saa (S，a)，a) TSS (T ，a)，a) Saa (T ，S)，a) TT ，ST，S (S)，a) TSS (T) ，a) S S(T)(T) (S，a) TSS (T，a) Saa (T，S) TT ，ST，S (T) S (T)(T) S7. 写一个文法，使其语言是奇数集，且每个奇数不以0 开头。解：文法G(N) ：NAB|BAAC|DB1|3|5|7|9DB|2|4|6|8C0|D8. 设文法 G(S)：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - -

25、- - - - 第 6 页，共 18 页 - - - - - - - - - 7 S(L)|a S|a LL ，S|S (1) 消除左递归和回溯； (2) 计算每个非终结符的FIRST 和 FOLLOW 。解： (1) S(L)|aS S S|LSL L SL| (2) FIRST)S) (，aFOLLOW(S) # ， ， ，) FIRST(S) ，a, FOLLOW(S) #， ， ，) FIRST(L) ( ，aFOLLOW(L) ) FIRST(L) ， ，FOLLOW(L ) 9. 已知文法 G(E) ET|E T T F|T *F F(E)|i (1)给出句型 (T *F i)的最

26、右推导；(2)给出句型 (T *F i)的短语、素短语。解： (1) 最右推导：E=T-F=(E)-(E T)=(E F)-(E i)=(T i)=(T*F i) (2) 短语： (T*F i)，T*F i，T*F ，i 素短语： T*F,i 10. Whilea0 b0do Begin X： X1；if a0 then a： a1 else b： b1 End；翻译成四元式序列。解：(1) (j ， a，0，5) (2) (j ， 3) (3) (j ， b，0，5) (4) (j ， 15) (5) (， X，1，T1) (6) (：， T1， X) (7) (j，a，0，9) (8) (

27、j ， 12) (9) (， a，1， T2) (10) (：， T2， a) (11) (j， 1) (12) (， b，1， T3) (13) (：， T3， b) (14) (j ， 1) (15) 11. 写出下列表达式的三地址形式的中间表示。 (1) 5+6 *(a + b); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 18 页 - - - - - - - - - 8 (2)for j:=1 to 10 do aj + j:=0。答：(1)100: t1:

28、=a+b 101: t2:=6*t1 102: t3:=5+t2 (2)100: j:=1 101: if j10 goto NEXT 102: i:=j+j 103: ai:=0 12. 设基本块p 由如下语句构成： T 0 : =3.14; T 1 :=2*T 0 ; T 2 :=R+r; A:=T l *T 2 ； B:=A; T 3 :=2*T 0 ; T 4 :=R+r; T 5 :=T 3 *T 4 ; T 6 :=R-r ； B:=T 5 *T 6 ；试给出基本块p 的 DAG 。解：基本块p 的 DAG 图: 13. 写出表达式 (a+b)/(a-b-(a+b*c) 的三元序列

29、及四元序列。解： （1）三元式：（， a，b）（， a，b）（ /，）（ * ，b，c）（， a，）（，）（2）四元式：（， a，b，T1）（， a，b，T2）（ /，T1，T2，T3）（ * ，b，c， T4）（， a，T4，T5）1 2 3 4 + - * * T03.14 T1,T36.28 R r T2,T4T6A,T5B 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 18 页 - - - - - - - - - 9 （， T3，T5，T6）14. 写一个文法使

30、其语言为偶数集，且每个偶数不以0 开头。解：文法G（S） ：SAB|B|A0 AAD|C B2|4|6|8 C1|3|5|7|9|B D0|C15. 设文法G （ S ）：S S aF|aF| aF F*aF|*a （1）消除左递归和回溯；（2）构造相应的FIRST 和 Follow 集合。解： （1）S-aFS|aFS S-aFS| F-*aF F-F| （2）FIRST（S） a，+FOLLOW （S）FIRST（S） +， FOLLOW （S）FIRST（F） * FOLLoW （F）（ +，FIRST（F） *， FOLLOW （+，16. 简要说明语义分析的基本功能。答：语义分析的基

31、本功能包括: 确定类型、类型检查、语义处理和某些静态语义检查。17. 考虑文法GS: S (T) | a+S | a T T,S | S 消除文法的左递归及提取公共左因子。解：消除文法GS 的左递归：S(T) | a+S | a TST T ,ST | 提取公共左因子：S(T) | aSS +S | TST T ,ST | 18. 试为表达式w+(a+b)*(c+d/(e-10)+8) 写出相应的逆波兰表示。解：w a b + c d e 10 - / + 8 + * + 19. 按照三种基本控制结构文法将下面的语句翻译成四元式序列：while (AC BD) if (A 1) C=C+1;e

32、lse while (A D)A=A+2; 。解：该语句的四元式序列如下(其中 E1、E2 和 E3 分别对应 ACBD、A1 和 AD ，并且关系运算符优先级名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 18 页 - - - - - - - - - 10 高)：100 (j,A,C,102) 101 (j,_,_,113) 102 (jAc|aB A-ab B-bc 写出L(GS) 的全部元素。解： S=Ac=abc 或 S=aB=abc 所以 L(GS)=abc 2

33、2. 构造正规式1(0|1)*101 相应的 DFA 。解：先构造NFA：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 18 页 - - - - - - - - - 11 确定化：重新命名，令AB 为 B、AC 为 C、ABY 为 D 得：所以，可得DFA 为：23. 文法S-a|(T) T-T,S|S 对 (a,(a,a) 和 (a,a),(a),a) 的最左推导。解：对(a,(a,a)的最左推导为：S=(T) =(T,S) =(S,S) =(a,S) =(a,(T

34、) =(a,(T,S) =(a,(S,S) =(a,(a,S) =(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),S),S) =(a,a),(T),S) =(a,a),(S),S) =(a,a),(a),S) =(a,a),(a),a) 24. 文法：S-MH|a H-LSo| K-dML| L-eHf

35、 M-K|bLM 判断G 是否为LL(1) 文法，如果是，构造LL(1) 分析表。解：各符号的FIRST 集和 FOLLOW 集为：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 18 页 - - - - - - - - - 12 预测分析表为：由于预测分析表中无多重入口，所以可判定文法是LL(1) 的。25叙述由下列正规式描述的语言(a)0(0|1)*0 (b)(|0)1*)* (c)(0|1)*0(0|1)(0|1) (d)0*10*10*10* (e)(00|11

36、)*(01|10)(00|11)*(01|10)(00|11)*)* 解： (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)|a LL,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,

37、(a,a) 句子 (a,(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构造下述文法GS 的自动机：S-A0 A-A0|S1|0 该自动机是确定的吗？若不确定，则对它确定化。解：由于该文法的产生式S-A0，A-A0|S1 中没有字符集VT 的输入，所以不是确定的自动机。要将其他确定化，必须先用代入法得到它对应的正规式。把S?A0 代入产生式A?S1 有： A=A0|A01|0=A(0|01)|0=0(0|01)*。 代入S-A0有 该 文 法 的 正 规 式

38、： 0(0|01)*0 ， 所 以 ， 改 写 该 文 法 为 确 定 的 自 动 机 为 ：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 18 页 - - - - - - - - - 13 由于状态A 有 3 次输入 0 的重复输入，所以上图只是NFA ，下面将它确定化：下表由子集法将NFA转换为DFA:由上表可知DFA 为：2对下面的文法G ：E-TE E-+E| T-FT T -T| F- PF F- *F| P-(E)|a|b| (1)计算这个文法的每个非终结

39、符的FIRST 集和FOLLOW 集。(2) 证明这个方法是LL(1) 的。(3) 构造它的预测分析表。解： （1）计算这个文法的每个非终结符的FIRST 集和 FOLLOW 集。FIRST 集合有：FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,; FIRST(E)=+, FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,; FIRST(T)=FIRST(T) =(,a,b,; FIRST(F)=FIRST(P)=(,a,b,; FIRST(F)=FIRST(P)=*,; FIRST(P)=(,a,b,; FOLLOW 集合有：FOLLOW

40、(E)=),#; FOLLOW(E)=FOLLOW(E)=),#; FOLLOW(T)=FIRST(E)FOLLOW(E)=+,),#;/不包含 FOLLOW(T)=FOLLOW(T)=FIRST(E)FOLLOW(E)=+,),#; FOLLOW(F)=FIRST(T)FOLLOW(T)=(,a,b,+,),#;/不包含 FOLLOW(F)=FOLLOW(F)=FIRST(T)FOLLOW(T)=(,a,b,+,),#; FOLLOW(P)=FIRST(F)FOLLOW(F)=*,(,a,b,+,),#;/不包含 (2)证明这个方法是LL(1) 的。名师资料总结 - - -精品资料欢迎下载

41、- - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 18 页 - - - - - - - - - 14 各产生式的SELECT 集合有：SELECT(E-TE)=FIRST(T)=(,a,b,; SELECT(E-+E)=+; SELECT(E- )=FOLLOW(E/)=),# SELECT(T-FT)=FIRST(F)=(,a,b,; SELECT(T-T)=FIRST(T)=(,a,b,; SELECT(T- )=FOLLOW(T/)=+,),#; SELECT(F-PF)=FIRST(P)=(,a,b,;

42、SELECT(F-*F)=*; SELECT(F- )=FOLLOW(F)=(,a,b,+,),#; SELECT(P-(E)=( SELECT(P-a)=a SELECT(P-b)=b SELECT(P-)= 可见，相同左部产生式的SELECT 集的交集均为空，所以文法GE 是 LL(1) 文法。(3)构造它的预测分析表。文法 GE的预测分析表如下：3已知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 图:下表由子集

43、法将NFA转换为DFA：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 18 页 - - - - - - - - - 15 下面将该DFA 最小化：(1) 首先将它的状态集分成两个子集：P1=A,D,E,P2=B,C,F (2) 区分 P2:由于 F(F,1)=F(C,1)=E,F(F,0)=F 并且 F(C,0)=C, 所以 F， C 等价。由于 F(B,0)=F(C,0)=C, F(B,1)=D,F(C,1)=E,而 D，E 不等价（见下步） ，从而 B 与 C，F

44、 可以区分。有P21=C,F,P22=B。(3) 区分 P1:由于 A，E 输入 0 到终态，而 D 输入 0 不到终态， 所以 D 与 A，E 可以区分， 有 P11=A,E,P12=D。(4) 由于 F(A,0)=B,F(E,0)=F, 而 B，F 不等价，所以A，E 可以区分。(5) 综上所述， DFA 可以区分为P=A，B ，D ，E ，C ，F 。所以最小化的DFA 如下：4 已知文法为： S-a|(T) T-T,S|S 构造它的LR(0) 分析表。解：加入非终结符S，方法的增广文法为：S-S S-a S- S-(T) T-T,S T-S 下面构造它的LR(0) 项目集规范族为：名师

45、资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 18 页 - - - - - - - - - 16 从上表可看出,不存在移进 -归约冲突以及归约归约冲突，该文法是LR(0) 文法。从而有下面的LR(0) 分析表：5已知文法A- aAd|aAb| 判断该文法是否是SLR(1) 文法，若是构造相应分析表，并对输入串ab# 给出分析过程。解：增加一个非终结符S/后，产生原文法的增广文法有：S-A A- aAd|aAb| 名师资料总结 - - -精品资料欢迎下载 - - - - -

46、 - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 18 页 - - - - - - - - - 17 下面构造它的LR(0)项目集规范族为：从 上 表 可 看 出 , 状 态I0和I2存 在 移 进 - 归 约 冲 突 ， 该 文 法 不 是LR(0) 文 法 。 对 于I0来 说 有 ：FOLLOW(A) a=b,d,#a= ，所以在 I0 状态下面临输入符号为a 时移进，为b,d,#时归约，为其他时报错。对于 I2 来说有也有与I0 完全相同的结论。 这就是说， 以上的移进 -归约冲突是可以解决的，因此该文法是SLR(1)文法

47、。其 SLR(1)分析表为：对输入串ab#给出分析过程为：6已知文法GS 为：S-a|(T) T- T,S|S (1) 计算GS 的 FIRSTVT 和 LASTVT 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 18 页 - - - - - - - - - 18 (2) 构造GS 的算符优先关系表并说明GS 是否未算符优先文法。(3) 计算GS 的优先函数。(4) 给出输入串(a,a)# 的算符优先分析过程。解：（ 1）各符号的FIRSTVT 和 LASTVT ：（2）算符优先关系表：（3）对应的算符优先函数为：（4）句子 (a,a)#分析过程如下：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 18 页 - - - - - - - - -