编译原理期末考试习题及答案.doc

优秀文件第一，空白问题|(每个问题4分，共20分)1.乔莫斯基定义的类型3语法(线性语法)生成格式ABa|a或AaB|a，a，bVN，a，bvt。2.解析器的输入是单词符号，其输出是语法单位。类型3为B .aB的LR(0)项称为移动项，类型B a.B的LR(0)项称为挂起项。4.属性语法汉语符号的两个属性分别是继承属性和综合属性。5、运行时存储管理方案包括静态存储分配、动态存储分配和堆存储分配和方案。二.已知语法G(S)(1) E T | E T(2) T F | F*F(3) F (E)| I(1)写句子模式(T*F I)的最右推，画语法树。(4点)(2)填写上述句子、直接短语和句柄。(4点)A: (1)最右侧的推力(两点)e=t=f=(e)=(e t)=(e f)=(e I)=(e I)=(t I)=(t * f I)(2)语法树(2分)(3)(4点)球体：(T*F I)，T*F I，T*F，I直线球：T*F，I句柄：T*F三.证明语法g(s):s SAS |是异议。(6分)答：对应句子AAA的两个语法树是：因此语法是彝族的语法四。给定的正则语法G(S):(1) S Sa | Ab |b(2) A Sa构建相应的DFA。(6分)答：相应的NFA是：(6点)状态转换表：abFSSS，AS，AS，ASV.配置标识常规语言b*a(bb*a)*b*最小DFA(需要创建解决过程)。(15分)A: (1)相应的NFA(5点)(2)结果(1) NFA决定：(5分钟)ab01，301，32，32，31，32，3(5分)六。已知语法G(S) :(1) s | a | (t)(2) t，s | s试一试：(1)去掉语法的左递归。(4点)(2)配置相应的first和follow集合。(6分)A: (1)删除语法的左边递归语法G(S)如下：(1) s | a | (t)(2) T ST | S(3) T ，ST | (4点)(2)(6点)第一次Followsa(#，)ta()，以获取详细信息t )，以获取详细信息Vii .已知语法G(S) :(1) S SiA | A(2)A B | B(3) B A* |(请尝试配置firstVT和lastVT集合，而不是终结器。(10分)A: (10分钟)FirstVTLastVTsI、*、(I、*、(a，*，(，*，(b*，(*，(Follows#ba、b、#Viii .已知语法G(S) :(1) s b(2) B a B(3) B b表格的follow集合：尝试这样做：(1)给出了此语法的LR(0)项目集规范族划分。(2)填写相应SLR(1)的分析表格。(15分)A: (1)LR(0)项目集规范族分隔(8点)I0s 。ss .BBb .aBb .b-i1-I2- I3- I4sbabI1S sI2S B.Bb .aBb .b-i5- I3- I4babI3B a.Bb .aBb .b-i6- I3- I4babI4B.b .I5S BB .I6B aB。(2) SLR(1)分析表(7点)状态Action加藤ab#sb0S3S4121Acc2S3S453S3S464R3R3R35R16R2R2R29.用于设置语言的not-then-else语句的语法格式如下：S not E then S1其含义如下：对于自上而下解析器：(1)创建段；(3点)(2)写出每个生成的相应语义动作。(7点)A: (1)创建线束段(三点)和语义动作(七点)(1) R not E then Backpatch($2 .FC、nxq)；$。chain=$2。Tc(2) S R S1 Backpatch($2.chain，nxq )第一，空白问题|(每个问题4分，共20分)1.乔莫斯基定义的类型2语法(上下文无关语法)生成格式a ，a/VN，/v2.词法输入是字符串，其输出是单词符号。3算子有限分析方法每次规定最左边的子句。B aB。类型的LR(0)项称为设置项。4，x 3360=b *(d-e)/(c-d)e的反向波兰_ _ xde-* CD-/e 3360=_ _ _ _。5、两种常用的动态存储分配方法是_ _堆栈存储分配和堆栈存储_ _分配。二.已知语法G(S) :(1) s | a | (t)(2) t，s | s试一试：(1)写句子模式(a，(a，a)的最左边，画语法树。(4点)(2)写上述句子的词组、直句、手柄。(4点)A: (1)最左推(两点)S=(t，s)=(s，s)=(a，s)=(a，(t)=(a，(t，s)(2)语法树(2分)(3)(4点)球体：(a，(a，a) a，(a，a)，(a，a)，a，a直接球体：a控制柄：a三.语法g (s)证明：s ASB | sb | b是二进制的。(6分)答：对应句子aabbbb的两个语法树是：因此语法是彝族的语法四。给定的正则语法G(S):(1) S aA(2) A aB | bA(3)B aA | b构建相应的DFA。(6分)答：相应的DFA是：(6点)V.配置标识常规语言(ab*|a)*最小DFA(需要创建解决过程)。(15分)A: (1)相应的NFA (5点)(2)结果(1) NFA决定：(5分钟)ab11，21，21，21，2(5分)六。已知语法G(S) :(1) s | a | (t)(2) T ST | S(3) T ，ST |尝试：寻找first和follow集合，并建构变更语法的LL(1)分析表格。(10分)答：语法对应的first和follow集合(5分)第一次Followsa(#，)ta()，以获取详细信息t )，以获取详细信息LL(1)分析表格如下：Vii .已知语法G(S) :(1) S SiA | A(2)A B | B(3) B A* |(非终结器的firstVT和lastVT集合为：FirstVTLastVTsI、*、(I、*、(a，*，(，*，(b*，(*，(配置运算符的优先级关系表。(10分)回答：I哟)，以获取详细信息* *I哟)，以获取详细信息* *8个已知语法G(S) :(1) S a | aAb | b | bBa(2) 1a 0 | (3) B 1B0 | 查找：语法的LR(0)项目集规范族。(15分)回答：9.用于设置语言的DO-while语句的语法格式如下：S do S1 while E其含义如下：对于自上而下解析器：(1)创建段；(3点)(2)写出每个生成的相应语义动作。(7点)A: (1)创建线束段(三点)G(S) : (1) R do(2) u S