编译原理例题与习题解答

《编译原理例题与习题解答》由会员分享，可在线阅读，更多相关《编译原理例题与习题解答（85页珍藏版）》请在文档大全上搜索。

1、1例题与习题解答例题与习题解答第二章第二章编译原理编译原理2回顾回顾n程序语言的定义程序语言的定义一个一个程序语言程序语言是一个记号系统是一个记号系统, ,它主要由以下它主要由以下方面定义：方面定义：n语法语法n语义语义 每个句子构成的规律每个句子构成的规律 研究语言研究语言 每个句子的含义每个句子的含义语法语法语义语义编译原理编译原理3语法语法=词法规则词法规则+ +语法规则语法规则 n词法规则词法规则：单词符号的形成规则：单词符号的形成规则。单词符号是语言中具有独立意义的最基本结构单词符号是语言中具有独立意义的最基本结构。一般包括：常数、标识符、基本字、算符、界一般包括：常数、标识符、基本

2、字、算符、界符等。符等。描述工具：正规式和描述工具：正规式和有限自动机有限自动机理论理论n语法规则语法规则：语法单位的形成规则：语法单位的形成规则。语法单位通常包括：表达式、语句、子程序、语法单位通常包括：表达式、语句、子程序、过程、函数、程序等过程、函数、程序等; ;描述工具：描述工具：上下文无关文法上下文无关文法回顾回顾编译原理编译原理4标识符与名字标识符与名字n标识符标识符：以字母开头的：以字母开头的，由字母数字组成由字母数字组成的字符串的字符串。n标识符标识符与与名字名字两者有本质区别：两者有本质区别：标识符标识符是语法概念是语法概念名字名字有确切的意义和属性有确切的意义和属性回顾回顾

3、编译原理编译原理5n上下文无关文法的定义：一个上下文无关文上下文无关文法的定义：一个上下文无关文法法G是一个四元式是一个四元式G=(VT，VN，S，P)，其中，其中VT：终结符集合：终结符集合(非空非空)VN：非终结符集合：非终结符集合(非空非空)，且，且VT VN=S：文法的开始符号，：文法的开始符号，S VNP：产生式集合：产生式集合(有限有限)，每个产生式形式为，每个产生式形式为P， P VN， (VT VN)*开始符开始符S至少必须在某个产生式的左部出现一次。至少必须在某个产生式的左部出现一次。回顾回顾编译原理编译原理6n假定假定G是一个文法，是一个文法，S是它的开始符号。是它的开始符

4、号。如果如果S ，则称，则称 是一个是一个句型句型。仅含终。仅含终结符号的句型是一个结符号的句型是一个句子句子。n文法文法G所产生的句子的全体是一个所产生的句子的全体是一个语言语言，将它记为将它记为L(G) L(G) = | S & VT* *文法产生语言文法产生语言*+回顾回顾编译原理编译原理7n定义定义：如果一个文法存在某个句子对应两如果一个文法存在某个句子对应两颗不同的语法树颗不同的语法树，则说这个则说这个文法是二义的文法是二义的。n语言的二义性：一个语言的二义性：一个语言是二义性的语言是二义性的，如，如果对它不存在无二义性的文法。果对它不存在无二义性的文法。可能存在可能存在G和

5、和G，一个为二义的，一个为无二，一个为二义的，一个为无二义的。但义的。但L(G)=L(G)回顾回顾文法和语言的二义性文法和语言的二义性编译原理编译原理8例题例题2.12.1：有一个文法：有一个文法 G=(S,A,B,a,b,P,S),G=(S,A,B,a,b,P,S),其中其中P: P: S S aB|bA aB|bA A A a|aS|bAAa|aS|bAA B B b|bS|aBBb|bS|aBB 采用采用最左推导最左推导产生句子产生句子aabbabaabbab 并画出相应的语法树。并画出相应的语法树。 S S a aB BaaaaB BB B aabaabS SB B aabbaabbA

6、 AB BaabbaaabbaB B aabbabaabbab S S a B a B a B B a B Bb Sb Sb b b Ab Aa a编译原理编译原理9例题例题2.2 试构造生成语言试构造生成语言L=anbnci|n 1, i 0的文法的文法 分析：要求分析：要求a和和b的个数一样多，并至少为一个，的个数一样多，并至少为一个，而而c的个数为的个数为0个以上即可，所以可以用一个终结个以上即可，所以可以用一个终结符去生成符去生成anbn串，用另一个非终结符去生成串，用另一个非终结符去生成ci 。 G(Z): ZAB A aAb|ab B cB| 编译原理编译原理10n例题例题2.3

7、请证实文法请证实文法G(E): E EiT | T T T+F | iF | F F E* | ( 是一个二义文法。是一个二义文法。编译原理编译原理11P36-6. 文法文法G6为为: N D|ND D 0|1|2|3|4|5|6|7|8|9 （1） G6的语言的语言L(G6)是什么是什么? G6的语言是：的语言是： 09的数字组成的任意非空数字串的数字组成的任意非空数字串L(G6)=x|x0,1,2,3,4,5,6,7,8,9+（2）给出句子）给出句子0127、34和和568的最左和最右推导。的最左和最右推导。编译原理编译原理n注意：注意：1)1)步骤，步骤，和和 的区别的区别；2) 2)

8、不能写不能写为为n解：解：01270127的最左推导：的最左推导：N NNDNDNDDNDDNDDDNDDDDDDDDDDD 0DDD0DDD0101DDDD012012D D01270127 0127 0127的最右推导：的最右推导：N NNDNDN7N7ND7ND7N27N27ND27ND27 N127N127D127D12701270127+编译原理编译原理13P36-7 写一文法写一文法, 使其语言是使其语言是奇数集奇数集, 但不允但不允 许出现以许出现以0打头的奇数。打头的奇数。解解: : 将奇数划分为三个部分：将奇数划分为三个部分：最高位最高位允许出现允许出现1 19,9,用非终结

9、符用非终结符B B表示表示; ;中间部分中间部分可出现任意多位数字可出现任意多位数字0 09, 9, 每一位用非终结符每一位用非终结符D D表示表示; ;最低位最低位只出现只出现1,3,5,7,9, 1,3,5,7,9, 用用A A表示。表示。 由于中间部分可任意位由于中间部分可任意位, ,故故需需另引入一另引入一 非终结符非终结符M,M,它包括最高位和中间部分。它包括最高位和中间部分。编译原理编译原理14MB最高位中间位DDDA最低位编译原理编译原理15解解: 奇数集文法奇数集文法GN为为: G=(0,1,9,N,A,M,B,D,N,) : NA | MA MB | MD A1 | 3 |

10、5 | 7 | 9 B1|2|3|4|5|6|7|8|9 D0 | B编译原理编译原理n8.8. 令文法为令文法为 E T|E+T|E-TE T|E+T|E-T T F|T T F|T* *F|T/FF|T/F F ( F (E)|iE)|i (1) 给出给出 i+i*i、i*(i+i)的最左推导的最左推导和最右推导。和最右推导。解解：此处仅以：此处仅以 i*(i+i) 为例给出答案为例给出答案最左推导最左推导E E T T T T* *F F F F* *F F i i* *F F i i* *(E) (E) i i* *(E+T)(E+T) i i* *(T+T)(T+T) i i* *(

11、F+T)(F+T) i i* *( (i+Ti+T) ) i i* *( (i+Fi+F ) ) i i* *( (i+ii+i) ) 最右推导最右推导E E T T T T* *F F T T* *(E) (E) T T* *(E+T) (E+T) T T* *(E+F)(E+F) T T* *( (E+iE+i) ) T T* *( (T+iT+i) ) T T* *( (F+iF+i) ) T T* *( (i+ii+i) ) F F* *( (i+ii+i) ) i i* *( (i+ii+i) ) 编译原理编译原理n8.8. 令文法为令文法为 E T|E+T|E-TE T|E+T|E