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

  1. 1、本文档共10页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
可编辑版 PAGE Word完美格式 一、填空题|(每题4分,共20分) 1. 乔母斯基定义的3型文法(线性文法)产生式形式 A?Ba|a,或A?aB|a,A,B∈Vn,a,b∈Vt 。 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分) 答:(1)最右推到(2分) E == T == F == (E) == (E+T) == (E+F) == (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分) 状态转换表: a b {F} Φ {S} {S} {S,A} Φ {S,A} {S,A} {S} 五. 构造识别正规语言b*a(bb*a)*b* 最小的DFA(要求写出求解过程)。(15分) 答:(1)对应的NFA(5分) (2)将(1)所得的NFA确定化:(5分) a b {0} {1,3} {0} {1,3} Φ {2,3} {2,3} {1,3} {2,3} (5分) 六. 已知文法 G(S) : (1) S ? ^ | a | (T) (2) T ? T,S | S 试:(1)消除文法的左递归;(4分) (2)构造相应的first 和 follow 集合。(6分) 答:(1)消除文法的左递归后文法 G’(S)为: (1) S ? ^ | a | (T) (2) T ? ST’ | S (3) T’ ? ,ST’ |ε (4分) (2)(6分) first follow S a ^ ( # , ) T a ^ ( ) T’ , ε ) 七. 已知文法 G(S) : (1) S ? SiA | A (2) A ? A+B | B (3) B ? A* | ( 试构造非终止符的firstVT和lastVT集合。(10分) 答:(10分) firstVT lastVT S i , + , * , ( i , + , * , ( A + , * , ( + , * , ( B * , ( * , ( FollowS# Follow S # B a,b,# (1) S ? B B (2) B ? a B (3) B ? b 的follow集合如表: 试:(1)给出该文法的LR(0)项目集规范族划分; (2)填写相应的SLR(1)的分析表。(15分) 答:(1)LR(0)项目集规范族划分(8分) I I0 S’? .S S ? .BB B ? .aB B ? .b ? I1 ? I2 --? I3 --? I4 S B a b I1 S’? S. I2 S ? B.B B ? .aB B ? .b ? I5 --? I3 --? I4 B a b I3 B ? a.B B ? .aB B ? .b ? I6 --? I3 --? I4 B a b I4 B ? b. I5 S ? BB. I6 B ? aB. (2) SLR(1)分析表(7分) 状态 Action Goto a b # S B 0 S3 S4 1 2 1 Acc 2 S3 S4 5 3 S3 S4 6 4 R3 R3 R3 5 R1 6 R2 R2 R2 九.设某语言的not-then-else 语句的语法形式为:S ? not E then S1 其语义解释为: 针对自上而下的语法分析器, (1) 分段产生式;(3分) (2) 写出每个产生式对应的语义动作。(7分) 答:(1)分段产生式(3分)及

文档评论(0)

zxiangd + 关注
实名认证
内容提供者

本人从事教育还有多年,在这和大家互相交流学习

1亿VIP精品文档

相关文档