1、编译原理习题2003.41目录 chap 1 基本知识 chap 3 词法分析 chap 4 语法分析 chap 5 语法制导翻译 chap 6 运行时刻环境 chap 7 中间代码生成 chap 8 代码生成2第一章 练习1.1 文法 S ( L ) | aL L , S | S(a) 指出文法的终结符号 , 非终结符号 , 开始符号 .文法的四个组成部分 :终结符号 VT : 语言不可再分的基本符号非终结符号 VN : 语法范畴 (语法概念 )开始符号 S : 最终感兴趣的语法范畴产生式 P : 定义语法范畴的一种书写形式终结符号 : ( , ) a 非终结符号 : S L开始符号 : S
2、元语言符号 : 表示 “定义为 ”| 表示 “或 ”3(b) 给出句子的分析树分析树 : (推导树 ) 表示一个句型的推导 (a, (a,a)S( L )L , SS ( L )a Sa4(c) 给出句子的最左推导给出每次推导后得到的句型的短语 , 直接短语最左推导 : 推导中任何一步 都是对 中的最左非终结lm 符号进行替换的推导 .短语 是文法的句型 (S * ) S * A且 A + 则 是关于 A的句型 的短语 . 直接短语 是文法的句型 (S * ) S * A且 A 则 是关于 A的句型 的直接短语 . 句柄 : 一个句型的最左直接短语称为句柄 . 5S ( L ) ( L, S
3、) ( S, S ) ( a, S ) ( a, ( L )短语 ( L ) L, S S a a( L, S ) S,S a, S a, ( L )( S, S ) (a, S) ( a, ( L )( L )直接 ( L ) L, S S a a 短语 ( L ) ( a, ( L, S ) ( a, ( S, S) ( a, (a, S) ( a, (a, a)短语 a a a a a, ( L, S ) a, ( S, S) a, (a, S) a, (a, a)( a, ( L, S ) ( a, ( S, S) ( a, (a, S) ( a, (a, a)L, S S a a (
4、L, S) S, S a, S a, a( S, S) ( a, S) ( a, a)直接 a a a a短语 L, S S a aa 6(d) 构造各个句子的最右推导 .最右推导 (规范推导 )(e) 这个文法产生的语言是什么 ?a(a)(a,a)(a,a),a).a和数据元素为 a的广义表全体71.2 考虑文法S aSbS | bSaS |(a) 试说明此文法是二义性的 .(定义 1.5)如果一文法的句子存在两棵分析树 , 则该 句子是二义性的 .如果一文法包含二义性的句子 ,则这个 文法是二义性的 .可以从句子 abab有两个不同的最左推导来说明 .S aSbS abS abaSbS a
5、babS abablm lm lm lm lmS aSbS abSaSbS abaSbS ababS abablm lm lm lm lm句子 abab有两个不同的最左推导 , 该句子是二义性的 .所以此文法是二义性的 .8(b) 对于句子 abab构造两个相应的最右推导 .S aSbS aSb abSaSb abSab ababrm rm rm rm rmS aSbS aSbaSbS aSbaSb aSbab ababrm rm rm rm rm(c)对于句子 abab构造两个相应的分析树 .S Sa S b S a S b Sb S a S a S b S (d) 此文法产生的语言是什么 ?由相同个数的 a和 b组成的字符串 . 91.3 考虑文法bexpr bexpr or bterm | btermbterm bterm and bfactor | bfactorbfactor not bfactor | ( bfactor ) | true | false(a) 请指出此文法的终结符号 , 非终结符号和开始符号 .终结符号 : or, and, not, (, ), true, false 非终结符号 : bexpr, bterm, bfactor开始符号 : bexpr10
