2022年编译原理复习题 .pdf

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

1、编译原理复习题一、填空题1. 编译程序的工作过程一般可以划分为词法分析 ，语法分析 ，语义分析 ，中间代码优化 ，代码优化 等几个基本阶段。2. 若源程序是用高级语言编写的，目标程序是 汇编程序或机器语言程序，则其翻译程序称为编译程序 . 3. 编译方式与解释方式的根本区别在于是否生成目标代码. 5. 对编译程序而言，输入数据是源程序 ，输出结果是 目标程序 . 7. 若源程序是用高级语言编写的，目标程序是机器语言程序或汇编程序，则其翻译程序称为编译程序 。8. 一个典型的编译程序中，不仅包括词法分析、语法分析、中间代码生成、代码优化、目标代码生成等五个部分，还应包括表格管理 和出错处理 。其

2、中，词法分析器用于识别单词 。10. 一个上下文无关文法所含四个组成部分是一组终结符号、一组非终结符号、一个开始符号 、一组产生式 。12. 产生式是用于定义语法成分 的一种书写规则。13. 设 GS 是给定文法，则由文法G 所定义的语言L(G)可描述为： L(G)=x|Sx ， xVT* 。14. 设 G 是一个给定的文法，S 是文法的开始符号，如果S*x（其中 xV*），则称 x 是文法的一个 句型 。15. 设 G 是一个给定的文法，S 是文法的开始符号，如果S*x(其中 xVT*)，则称 x 是文法的一个 句子 。16. 扫描器的任务是从源程序中识别出一个个单词符号 。17. 语法分析

3、最常用的两类方法是自顶向下 和自底向上 分析法。18. 语法分析的任务是识别给定的终结符串是否为给定文法的句子 。19. 递归下降法不允许任一非终结符是直接左递归的。20. 自顶向下的语法分析方法的关键是如何选择候选式的问题。21. 递归下降分析法是自顶向下 分析方法。22. 自顶向下的语法分析方法的基本思想是：从文法的开始符号 开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的句子，使之与给定的输入串匹配。23. 自底向上的语法分析方法的基本思想是：从给定的终结符串开始，根据文法的规则一步一步的向上进行直接归约 ，试图 归约 到文法的 开始符号 。24. 自

4、底向上的语法分析方法的基本思想是：从输入串入手，利用文法的产生式一步一步地向上进行 直接归约 ，力求 归约 到文法的 开始符号 。26. 在 LR（0）分析法的名称中，L 的含义是 自左向右的扫描输入串，R 的含义是 最左归约 ，0 的含义是 向右查看输入串符号的个数为0。31. 终结符只有，它们由词法分析器提供。32. 在使用高级语言编程时，首先可通过编译程序发现源程序的全部语法 错误和 语义 部分错误. 34一个句型中的最左简单短语称为该句型的句柄 。36从功能上说，程序语言的语句大体可分为执行性 语句和 说明性 语句两大类。名师资料总结 - - -精品资料欢迎下载 - - - - - -

5、 - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 17 页 - - - - - - - - - 37语法分析是依据语言的语法 规则进行的，中间代码产生是依据语言的语义规进行的。38语法分析器的输入是单词符号串 ，其输出是 语法单位 。40逆波兰式ab+c+ d*e- 所表达的表达式为（a+b+c）*d-e 。41计算机执行用高级语言编写的程序主要有两种途径：解释和编译 。42自上而下分析法采用移进 、归约、错误处理、接收 等四种操作。43一个 LR 分析器包括两部分：一个总控程序和一张分析表 。44后缀式 abc-/所代表的表达式是a/

6、(b-c)。46语法分析基于 上下文无关 文法进行， 即识别的是该类文法的句子。语法分析的有效工具是语法树 。48 语义分析阶段所生成的与源程序等价的中间表示形式可以有逆波兰 、 四元式 与三元式 等。51. 自顶向下语法分析会遇到的主要问题有回溯 和左递归 。52. 已知文法GE：ET|E+T; TF|T*F; F(E)|i该文法的开始符号是E，终结符号集合 VT是+,*,(,), ，非终结符号结合VN是E,T,F 。二、单选题1一个编译程序中，不仅包含词法分析，(A)，中间代码生成，代码优化，目标代码生成等五个部分。A语法分析B文法分析C语言分析D解释分析2语法分析器则可以发现源程序中的(

7、D)。A语义错误B语法和语义错误C错误并校正D语法错误3解释程序处理语言时, 大多数采用的是(B)方法。A源程序命令被逐个直接解释执行B先将源程序转化为中间代码, 再解释执行C先将源程序解释转化为目标程序, 再执行D以上方法都可以4编译程序是一种(B)。A汇编程序B翻译程序C解释程序D目标程序5通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括(C)。A模拟执行器 B解释器 C表格处理和出错处理D符号执行器6一个句型中的最左(B)称为该句型的句柄。A短语B简单短语C素短语D终结符号7文法GE ：ET ET TF TF Fa (E) 该文法句

8、型EF(ET)的简单短语是下列符号串中的(B)。（ ET）ET F F(ET) A和B和C和D8词法分析器用于识别(C)。A句子B句型C单词D产生式9在自底向上的语法分析方法中，分析的关键是(A) 。A寻找句柄B寻找句型C消除递归D选择候选式名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 17 页 - - - - - - - - - 10文法G 产生的 (D) 的全体是该文法描述的语言。A句型B终结符集C非终结符集D句子11若文法G 定义的语言是无限集，则文法必然是(A)

9、 。A递归的B前后文无关的C二义性的D无二义性的12四种形式语言文法中，1 型文法又称为 (C)文法。A短语结构文法B前后文无关文法C前后文有关文法D正规文法13一个文法所描述的语言是(A) 。A唯一的B不唯一的C可能唯一，好可能不唯一D都不对14 (B)和代码优化部分不是每个编译程序都必需的。A语法分析B中间代码生成C词法分析D目标代码生成15 (B)是两类程序语言处理程序。A高级语言程序和低级语言程序B解释程序和编译程序C编译程序和操作系统D系统程序和应用程序16. 一个上下文无关文法G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组(D)。A句子B句型C单

10、词D产生式17文法分为四种类型，即0 型、 1 型、 2 型、 3 型。其中2 型文法是 (D) 。A短语文法B正则文法C上下文有关文法D上下文无关文法18文法G 所描述的语言是(C)的集合。A文法 G 的字母表V 中所有符号组成的符号串B文法G 的字母表V 的闭包V* 中的所有符号串C由文法的开始符号推出的所有终结符串D由文法的开始符号推出的所有符号串19文法分为四种类型，即0 型、 1 型、 2 型、 3 型。其中0 型文法是 (A) 。A短语文法B正则文法C上下文有关文法D上下文无关文法20 (A) 是一种典型的解释型语言。ABASIC B C CFORTRAN D PASCAL 21与

11、编译系统相比，解释系统(D) 。A比较简单, 可移植性好, 执行速度快B比较复杂, 可移植性好, 执行速度快C比较简单, 可移植性差, 执行速度慢D比较简单, 可移植性好, 执行速度慢22用高级语言编写的程序经编译后产生的程序叫(B)。A源程序 B目标程序 C连接程序D解释程序23编写一个计算机高级语言的源程序后，到正式上机运行之前，一般要经过(B) 这几步 : (1) 编辑(2) 编译(3) 连接(4) 运行A(1)(2)(3)(4) B(1)(2)(3) C(1)(3) D (1)(4) 24把汇编语言程序翻译成机器可执行的目标程序的工作是由(B) 完成的。A编译器 B汇编器 C解释器 D

12、预处理器25词法分析器的输出结果是(C)。A单词的种别编码B单词在符号表中的位置C单词的种别编码和自身值D单词自身值26正规式M 1 和 M 2 等价是指 (C)。AM1 和 M2 的状态数相等BM1 和 M2 的有向边条数相等CM1 和 M2 所识别的语言集相等DM1 和 M2 状态数和有向边条数相等27文法 G：S xSx|y 所识别的语言是(C)。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 17 页 - - - - - - - - - Axyx B(xyx)*

13、C)0(nyxxnnDx*yx* 28如果文法G 是无二义的，则它的任何句子 (A) 。A最左推导和最右推导对应的语法树必定相同B最左推导和最右推导对应的语法树可能不同C最左推导和最右推导必定相同D可能存在两个不同的最左推导，但它们对应的语法树相同29构造编译程序应掌握(D) 。A源程序B目标语言C编译方法D以上三项都是30四元式之间的联系是通过(B)实现的。A指示器B临时变量C符号表D程序变量31表达式 ( AB)(CD)的逆波兰表示为(B) 。AAB CDBAB CD CABCD DAB CD33编译程序是对(D)。A汇编程序的翻译B高级语言程序的解释执行C机器语言的执行D高级语言的翻译3

14、4采用自上而下分析，必须(C)。A消除左递归B消除右递归C消除回溯D提取公共左因子35在规范归约中，用(B)来刻画可归约串。A直接短语B句柄C最左素短语D素短语36间接三元式表示法的优点为(A) 。A采用间接码表，便于优化处理B节省存储空间，不便于表的修改C便于优化处理，节省存储空间D节省存储空间，不便于优化处理37在目标代码生成阶段，符号表用(D)。A目标代码生成B语义检查C语法检查D地址分配38下面关于解释程序的描述正确的是B. (1) 解释程序的特点是处理程序时不产生目标代码(2) 解释程序适用于COBOL 和 FORTRAN 语言(3) 解释程序是为打开编译程序技术的僵局而开发的A.

15、(1)(2) B. (1) C. (1)(2)(3) D.(2)(3) 40. 用不同语言编写的程序产生后，可用连接在一起生成机器可执行的程序.在机器中真正执行的是 . 上面三空格对应的选项是：A a. 源程序b. 目标程序c. 函数d. 过程e. 机器指令代码f. 模块g. 连接程序h.程序库A. b、g、e B. b、c、 e C. e、g、 f D. e、c、f 41. 由于受到具体机器主存容量的限制，编译程序几个不同阶段的工作往往被组合成，诸阶段的工作往往是进行的. 上面两空格对应的选项是：A a. 过程b. 程序c. 批量d.遍e. 顺序f. 并行g. 成批h.穿插A. d 和 h

16、B. d 和 e C. a 和 h D. a 和 e 42. 编译过程中，语法分析器的任务就是B. (1)分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的(3)分析语句和说明是如何构成程序的(4) 分析程序的结构A. (2)(3) B. (2)(3)(4) C. (1)(2)(3) D.(1)(2)(3)(4) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 17 页 - - - - - - - - - 43. 编译程序必须完成的工作有A. (1) 词法分析

17、(2) 语法分析(3) 语义分析(4) 代码生成(5) 中间代码生成(6) 代码优化A. (1)(2)(3)(4) B. (1)(2)(3)(4)(5) C. (1)(2)(3)(4)(5)(6) D. (1)(2)(3)(4)(6) 44按逻辑上划分，编译程序第二步工作是C。A. 语义分析B. 词法分析C. 语法分析D. 代码优化45已知语言L= xnyyn | n=1 ，则下述文法中，D 可以产生语言L。A 1.Z xZy|xAy|y B 1.A xAy2. A xAy|x 2.A xC 1.Z AyB D 1.Z xAy2.A xA|x 2.A xAy|y3.B yB|y 46乔姆斯基（

18、 Chomsky）把文法分为四种类型，即0 型、 1 型、2 型、 3 型。其中3 型文法是 B。A.短语文法B.正则文法C.上下文有关文法D.上下文无关文法48设 G 是一个给定的文法，S 是文法的开始符号，如果Sx(其中 xV*)，则称 x 是文法 G 的一个 B。A. 候选式B.句型C. 单词D. 产生式49若一个文法是递归的，则它所产生的语言的句子A。A.是无穷多个B.是有穷多个C.是可枚举的D.个数是常量50文法的二义性和语言的二义性是两个A 的概念。A 不同B 相同C 无法判断D 不存在51. 在语法分析处理中，FIRST 集合、 FOLLOW 集合、 SELECT 集合均是 B。

19、A. 非终结符集B.终结符集C. 字母表D. 状态集52. 编译程序中语法分析器接收以A 为单位的输入。A. 单词B. 表达式C. 产生式D. 句子53. 在 LR 分析法中，分析栈中存放的状态是识别规范句型C 的 DFA 状态。A.句柄B. 前缀C. 活前缀D. LR(0) 项目三、判断题1计算机高级语言翻译成低级语言只有解释一种方式。（）2在编译中进行语法检查的目的是为了发现程序中所有错误。（）3甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。 （）4“ 用高级语言书写的源程序都必须通过编译，产生目标代码后才能投入运行” 说法。（）5正则文法其产生式为Aa

20、，ABb， A，BVN，a、bVT。 （）6产生式是用于定义词法成分的一种书写规则。() 7解释程序适用于COBOL 和 FORTRAN 语言。() 8正规文法产生的语言都可以用上下文无关文法来描述。() 9如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。() 10编译程序是对高级语言程序的解释执行。() 11一个有限状态自动机中，有且仅有一个唯一的终态。() 12语法分析时必须先消除文法中的左递归。() 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共

21、 17 页 - - - - - - - - - 13两个正规集相等的必要条件是他们对应的正规式等价。() 14设 r 和 s 分别是正规式，则有L(r|s)=L(r)L(s) 。() 15确定的自动机以及不确定的自动机都能正确地识别正规集。() 16词法分析作为单独的一遍来处理较好。() 17构造 LR 分析器的任务就是产生LR 分析表。() 18编译程序与具体的机器有关，与具体的语言无关。() 19每个文法都能改写为LL(1) 文法。（）20递归下降法允许任一非终结符是直接左递归的。（）21递归下降分析法是自顶向下分析方法。() 22一个LL(l) 文法一定是无二义的。() 23算符优先关系

22、表不一定存在对应的优先函数。（）24自底而上语法分析方法的主要问题是候选式的选择。（）25LR 分析方法是自顶向下语法分析方法。（）26简单优先文法允许任意两个产生式具有相同右部。（）27若一个句型中出现了某产生式的右部，则此右部一定是该句型的句柄。（）28一个句型的句柄一定是文法某产生式的右部。（）29在SLR(1) 分析法的名称中，S 的含义是简单的。() 30综合属性是用于“ 自上而下” 传递信息。() 31一个算符优先文法可能不存在算符优先函数与之对应。() 32LR 分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。() 33规范归约和规范推导是互逆的两个过程。()

23、 34LR 分析技术无法适用二义文法。() 35逆波兰表示法表示表达式时无须使用括号。() 36逆波兰法表示的表达式亦称后缀式。() 38在程序中标识符的出现仅为使用性的。（）39. 设为 a ，b ，则 a，ba， ， 都是上的正规式。 （）40. 对于上下文无关文法GS，若 S AB 则 A 一定是一条产生式规则，其中 , , （ VTVN）*。（）41. 对于逆波兰后缀式，无论从哪头开始分析均可得到唯一正确的分解。（）42. LR（0）分析法是一种规范归约法。（）43. 算符优先分析法只能用来分析算符优先文法。（）44. 解释程序和编译程序一样，生成目标代码。（）45. 编译程序生成的目

24、标代码只能是机器语言。（）46. 等价文法是指两个文法完全相同。（）47. 对于字母表 上的任一 NFA M，必存在 上与 NFA M 等价的 DFA M 。 （）48. 不存在正规文法能产生语言：L=anbn|n=1 （）四、简答题1、什么是句子？什么是语言? 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 17 页 - - - - - - - - - 句子：设G 是一个给定的文法，S 是文法的开始符号，如果Sx（其中 xVT* ） ，则称 x 是文法的一个句子。语言：

25、句子的集合。设GS是给定文法，则由文法G 所定义的语言L（G）可描述为：2、已知文法GE 为：E T|E+T|E -T T F|T*F|T/FF（E） |i 该文法的开始符号（识别符号）是什么？E请给出该文法的终结符号集合VT和非终结符号集合VN。答： VN=E,T,FVT=i,+,-,*,(,), 找出句型T+T*F+i 的所有短语、简单短语和句柄。答：短语 T，T*F ，i，T+T*F+i 简单短语： T，T*F 句柄： T 3、已知文法GS为：S dABA aA|aB Bb| GS产生的语言是什么？答： L(GS)=danbn|n 1,m 0 GS能否改写为等价的正规文法？答：能，GS，

26、 S，dAB AaA|aB|a BbB|b 5、证明下面文法GN 是二义性文法。GN ： N SE E S SD D E 0 210 D 0 12 证明：左推导1：N=SE=DE=D0=10 左推导 2：N=E=10 7、简述 DFA 与 NFA 有何区别? 答： DFA 与 NFA 的区别：NFA 可以有若干个开始状态，而DFA 仅只有一个开始状态；DFA 的映象 M 是从 K 到 K，而 NFA 的映象 M 是从 K 到 K 的子集，即映象M 将产生一个状态集合（可能为空集），而不是单个状态。8、试给出非确定自动机的定义。答：一个 NFA （ M）是一个五元组：M=(K ， ，f，S，Z)

27、。(K 是一个有穷集，它的每个元素称为一个状态；( 是一个有穷字母表，它的每个元素成为一个输入符号，所以也称 为输入符号表；(f 是状态转换函数，是在 K * K 的子集的映射， 即 f：K *ZK；表明在某状态下对于某输入符号可能有多个后继状态；SCK 是一个非空初态集；ZCK 是一个终态集（可空） 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 17 页 - - - - - - - - - 9、为正规式（ a|b）*a(a|b) 构造一个等价的确定的有限自动机。10

28、、构造正规式相应的NFA : 1(0|1)*101 13、编译过程一般分为几个阶段？各阶段的输入输出分别为什么？15、在 LL(1) 分析法中， LL 分别代表什么含义? 答：第一个L 表明自顶向下分析是从左向右扫描输入串，第二个L 表明分析过程中将用最左推导。16、文法 G为： S aAB A a B | | 则判断 G为 LL（1）文法的条件是：答： Sclect(S aAB)=a Sclect(A a)=a Sclect(B | /y)= ， ，y=?17、文法 G=(A, B, S, a, b, c, P , S) 其中 P为：SAc|aB A ab B bc 该文法是二义的吗？说明理

29、由。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 17 页 - - - - - - - - - 答：是有二义性的，因为句子abc 有两棵语法树 (或称有两个最左推导或有两个最右推导 ) 最左推导 1：S ? Ac ? abc 最左推导 2：S ? aB ? abc 18、文法 G=(E, +, *, i, (, ), P , E)其中 P为：Ei E E+E E E*E E (E) 该文法是二义的吗？说明理由。答：是有二义性的，因为句子i*i+i 有两个最左推导最左推导

30、1：E? E+E ? E*E+E? i*E+E ? i*i+E ? i*i+i 最左推导2：E? E*E ? i*E ? i*E+E ? i*i+E ? i*i+i19、自顶向下分析思想是什么？答：从开始符出发导出句型并一个符号一个符号地与给定终结符串进行匹配。如果全部匹配成功，则表示开始符号可推导出给定的终结符串。因此判定给定终结符号串是正确句子。25、简单优先方法基本思想是什么？答：简单优先方法基本思想是首先规定文法符号之间的优先关系和结合性质，然后再利用这种关系，通过比较两个相邻的符号之间的优先顺序来确定句型的“句柄”并进行归约。28、语法制导翻译方法的基本思想是什么? 答：在语法分析过

31、程中，每当使用一条产生式进行推导或归约时，就执行该产生式所对应的语义动作进行属性计算，完成对输入符号串的翻译。33、给定下列中缀式，分别写出等价的后缀式和四元式(运算符优先级按常规理解)。(1)(ab*c)/(a b)d 答：后缀式： abc*+ab+/d- 四元式：（* ，b， c，t1）（+，a，t1，t2）（+，a，b，t3）（ /，t2,t3,t4 ） (-,t4,d,t5) 一、最左、最右推导及语法树1、令文法为 ET|E+T|E-T TF|T*F|T/F 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理

32、- - - - - - - 第 9 页，共 17 页 - - - - - - - - - F（E）|i 1）给出 i+i*i的最左推导和最右推导；2）给出 i+i*i的最左推导语法树。3、下面的文法生成的是以x 和 y 为操作数、二元运算符 +、*和- 为运算符的前缀表达式： E+EE|*EE|-EE|x|y1）给出串 +*-xyxy的最左推导和最右推导；2）给出 +*-xyxy的语法树。4、一个上下文无关文法生成句子abbaa 的推导树如下：SABSaSBBbbAaa1） 给出该句子相应的最左推导，最右推导。2） 该文法的产生式集合P可能有哪些元素？二、自动机的确定化和最小化1、将下图中的自

33、动机确定化并最小化。X5Y62431abababab3、试构造正规式 (0|1)*1(0|1) 相应的自动机，并将其确定化名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 17 页 - - - - - - - - - 4、试构造正规式 (a|b)*ab(a|b)* 相应的自动机，并将其确定化和最小化。三、FIRST 和 FOLLOW 集合1、考虑下面文法G1 ：Sa|(T) TT，S|S 1） 消去 G1的左递归；2） 经改写后的文法是否是LL(1) 的？给出它的预测分析

34、表(要求写出详细过程，应先求出每个非终结符的FIRST和 FOLLOW 集合 ) 。2、判断下面文法是否为LL(1) 文法，若是，请构造相应的预测分析表。SaD D STe| T bH|HH d| 3、对文法 G(S) ：S S a T | a T | a T T a T | a 1）消除该文法的左递归和提取左公因子；2）构造各非终结符的FIRST 和 FOLLOW 集合；3）构造该文法的 LL(1) 分析表，并判断该文法是否是LL(1) 的。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - -

35、- 第 11 页，共 17 页 - - - - - - - - - 四、短语、直接短语、句柄和素短语1、对于文法 G （S） ：S(L)|aS|a LL,S|S 1）画出句型 (S,(a)的语法树。2）写出上述句型的所有短语、直接短语、句柄和素短语。2、文法 GS为：S V V T | ViTT F| T+FF )V* |(1）画出句型ViFi( 的语法树。2）写出上述句型的所有短语、直接短语、句柄和素短语。3、对于文法G(E): ET|E+T TF|T*F F(E)|i 1）画出句型T*F+i1*i2的语法树。2）写出上述句型的短语，直接短语、句柄、素短语和最左素短语。答：短语： T*F +

36、i1*i2, T*F, i1*i2 , i1, i2名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 17 页 - - - - - - - - - 直接短语： T*F, i1, i2句柄： T*F 素短语： T*F, i1, i2最左素短语： T*F五、FIRSTVT 集合和 LASTVT 集合，构造优先关系表1、设文法G （ S ） ：S(A)|a AA+S|S 1）构造各非终结符的FIRSTVT集合和 LASTVT集合。2）构造优先关系表。2、设文法G3为：SAaBc

37、 AAa|a Bb 1）构造各非终结符的FIRSTVT集合和 LASTVT集合。2）构造优先关系表。3）求句型 AaBc 的最左素短语。答： 1） 非终结符的FIRSTVT 集合和 LASTVT 集合为：FIRSTVT(S)=a, LASTVT(S)=c, FIRSTVT(A)=a, LASTVT(A)=a, FIRSTVT(B)=b, LASTVT(B)=b 。2）则优先关系表为：3）句型 AaBc 的最左素短语为：对于 #AaBc#，#，则最左素短语为AaBc。3、设文法G(S)：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - -

38、- 名师精心整理 - - - - - - - 第 13 页，共 17 页 - - - - - - - - - ( |*)BB|BAAA|SiASA1） 构造各非终结符的FIRSTVT 和 LASTVT集合；2） 构造优先关系表。答： 1）FIRSTVT(S)= i ，+， )，( FIRSTVT(A)= + ，)，( FIRSTVT(B)= ) ，( LASTVT(S)= i ，+，* ，( LASTVT(A)= + ，* ，( LASTVT(B)= * ，( 2）优先关系表六、LR分析1、已知文法AaAd|aAb| 判断该文法是否是 SLR(1) 文法，若是构造相应分析表。答：拓展文法为G

39、，增加产生式S A 产生式排序为：S A A aAd A aAb A 由产生式知：First (S ) = ,a First (A ) = ,a Follow(S ) = # Follow(A ) = d,b,# 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 17 页 - - - - - - - - - G 的 LR(0) 项目集族及识别活前缀的DFA 如下图所示：在 I0 中：A.aAd 和 A .aAb 为移进项目，A . 为归约项目，存在移进- 归约冲突，因此所

40、给文法不是LR(0) 文法。在 I0 、 I2 中：Follow(A) a= d ， b ， # a=所以在I0 、 I2 中的移进- 归约冲突可以由Follow 集解决，所以G 是 SLR(1) 文法。构造的SLR(1) 分析表如下：2、若有定义二进制数的文法如下：SLL|L LLB|B B0|1 试为该文法构造LR 分析表，并说明属哪类LR 分析表。3、已知文法 GS：SMH|a HLSo| KdML| LeHf 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 17

41、 页 - - - - - - - - - M K|bLM 判断 G 是否是 LL(1)文法，如果是，构造LL(1)分析表。4、考虑文法：S A S | b A S A | a 1)构造文法的LR(0) 项目集规范族及相应的DFA 。2)构造文法的SLR 分析表。答： 1) 令拓广文法G 为(0) S S (1)S A S (2)S b (3)A S A (4)A a 其 LR(0) 项目集规范族及识别该文法活前缀的DFA 如下图所示：FOLLOW(S)=#,a,b FOLLOW(A)=a,b LR(0) 项目：2) 文法的SLR 分析表如下：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 17 页 - - - - - - - - - 因为 I5 中： FOLLOW （ A ） a ， bI7 中： FOLLOW （ S ） a ， b所以，该文法不是SLR （ 1 ）文法。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 17 页 - - - - - - - - -