当前位置:首页 >> 理学 >>

编译原理复习资料 例题习题讲解(ch1-ch2)


第一部分 重点知识回顾
第一章 引论 1.程序语言的定义 (1)程序语言:一个程序语言是一个记号系统。如同自然语言一样,程序语言也是由语 法和语义两方面定义的。任何语言程序都可看成是一定字符集(称为字母表)上的一个字符 串,合乎语法的字符串才算是一个合式的程序。所谓一个语言的语法是指这样一组规则,用 它可以形成和产生一个合式的程序, 这些规则一部分称为词法规则, 另一部分称为语法规 (或 产生规则) 。 (2)词法规则:指单词符号的形成规则。 (3)语法规则:语言的语法规则规定了如何从单词符号形成更大的结构(即语法单位) 。 换言之,语法规则是语法单位的形成规则,一般程序语言的语法单位有表达式、语句、分程 序、函数、过程和程序等。 语言的词法规则和语法规则定义了程序的形式结构, 是判断输入的字符串是否构成一个 形式上正确(即合式)的程序的依据。 (4)语义规则:对于一个语言,不仅要给出它的词法、语法规则,而且要定义它的单词 符号和语法单位的意义,这就是语义问题。离开了语义,语言只不过是一堆符号的集合。所 谓一个语言的语义是指这样一组规则,使用它可以定义一个程序的意义。 2.编译程序 编译程序的工作是指从输入源程序开始到输出目标程序为止的整个过程, 是非常复杂的。 一般来说,整个过程可以划分成 5 个阶段:词法分析、语法分析、中间代码生成、优化和目 标代码生成。 第一阶段,词法分析。词法分析的任务是输入源程序,对构成源程序的字符串进行扫描 和分解,识别出一个个单词符号,如基本字、标识符、常数、算符和界符等。在词法分析阶 段的工作中遵循的是语言的构词规则。 第二阶段, 语法分析。 语法分析的任务是在词法分析的基础上, 根据语言的语法规则 (文 法规则)把单词符号串分解成各类语法单位(语法范畴) ,如“短语” 、 “子句” 、 “句子(语 句) ” 、 “程序段”和“程序” 。通过语法分解确定整个输入串是否构成一个语法上正确的“程 序” 。语法分析所遵循的是语言的语法规则。 第三阶段, 中间代码生成。 这一阶段的任务是对各类不同语法范畴按语言的语义进行初 步翻译的工作。把语法范畴翻译成中间代码所遵循的是语言的语义规则。一般而言,中间代 码是一种独立于具体硬件的记号系统, 它与现代计算机的指令形式有某种程度的接近, 或者 说能够比较容易地把它变换成现代计算机的机器指令。常用的中间代码有四元式、三元式、 间接三元式和逆波兰记号等。 第四阶段,优化。优化的任务是对前阶段产生的中间代码进行加工变换,以便在最后阶 段能产生出更为高效(节省时间和空间)的目标代码。优化的主要方面有:公共子表达式的 提取、循环优化、算符归约等。优化所遵循的原则是程序的等价变换规则。 第五阶段,目标代码生成。这一阶段的任务是把中间代码(或经优化处理之后)变换成 特定机器上的绝对指令代码或可重新定位的指令代码或汇编指令代码。 这个阶段实现了最后 的翻译,它的工作依赖于硬件系统结构和机器指令含义。 如果最终得到的目标代码是绝对指令代码, 则这种目标代码可以立即运行; 如果目标代 码是汇编指令代码, 则这种目标代码需经汇编之后方可运行。 目前多数实用编译程序所产生 的目标代码都是一种可重定位的指令代码, 这种目标代码必须通过一个连接装配程序把各个

目标模块连接、装配在一起,使之成为一个可以独立运行的绝对指令代码程序。 上述编译过程的 5 个阶段是编译程序工作时的动态特征,编译程序的结构可以按照这 5 个阶段的任务分模块进行设计。

3.编译程序与解释程序的异同

第二章 高级语言及其文法 1 上下文无关文法的定义 文法是描述语言的语法结构的形式规则。 一个上下文无关文法 G 包括四个组成部分:一组终结符、一组非终结符、一个开始符号 和一组产生式。从形式上说,一个上下文无关文法 G 是一个四元式(V,T, S,P),其中: (1) T 是一个非空有限集,它的每个元素称为终结符号; (2) V 是一个非空有限集,它的每个元素称为非终结符号, T∩V=φ ; (3)S 是一个非终结符号,称为开始符号; (4)P 是一个产生式集合(有限) ,每个产生式的形式是 P→α ;其中,P∈V,α ∈(T * ∪V) 。开始符号至少必须在某个产生式的左部出现一次。 用上下文无关文法定义语言的中心思想是: 从文法的开始符号出发, 反复连续地使用产 生式,对非终结符实施替换和展开。 2 推导与语法树 我们称α Α β 直接推出α γ β ,即: α Α β =>α γ β 仅当 A→γ 是一个产生式,且α ,β ∈ (T ∪V) 。如果α 1=>α 2=>?=>α n,则称这个 序列是从丛α 1 至α n 的一个推导。若存在一个从α 1 至α n 的推导,则称“α 1 可推导出α n。 注意:用α 1=>α n,表示从α 1 出发,经过 0 步或若干步可推导出α n;而用α 1=>α n 表示从α 出发,经过一步或若干步可推导出α n。这里α =>β 意味着或者α =β ,或者α =>β . 假定 G 是一个文法,S 是它的开始符号。如果 S=> α ,则称 a 是一个句型;仅含终结符
* 1

*

号的句型是一个句子。文法 G 所产生的句子的全体是一个语言,将它记为 L(G) 。 * L(G)={α |S=>α &α ∈T } 我们可以用一张图表示一个推导, 这种表示称为语法树。 语法树有助于理解一个句子语 法结构的层次。语法树通常表示成一棵倒立的树,树根在上,枝叶在下。 语法树的根结点由开始符号所标记, 每一步推导则对应语法树的生长。 在一棵语法树 生长程中的任何时刻,所有那些没有后代的树叶自左至右全部排列起来就是一句型。 例如,对文法 E→E+E|E*E|(E)|i,关于(i*E+E )推导的语法树生长过程如图所示

如果一个文法中存在某个句子,它有两个不同的最左(最右)推导。也就是说,该句于 对应两棵不同的语法树,则这个文法是二义的。因此,判断文法是否具有二义性,就是设法 找到该文法下的一个句子.该句子对应两棵不同的语法树。 注意: 假定 G 是一个文法, 则由该文法开始符号出发所进行的每一步推导所对应的语法树的 树叶自左至右排列的全体就是一个句型,仅含终结符号的句型就是一个句子。 此外,对无二义性的文法来说,无论是最左推导还是最右推导,同一个句子最终形成的 语法树都是一样的。 3.乔姆斯基(Chomsky)文法 乔姆斯基 (Chomsky) 把文法分成 4 种类型, 即 0 型、1 型、2 型和 3 型。0 型强于 1 型, 1 型强于 2 型,2 型强于 3 型。 我们说 G=(T, V , S,P)是一个 0 型文法,如果它的每个产生式α →β 是这样一种 + * 结构:α ∈(T∪V) 且至少含有一个非终结符,而β ∈(T∪V) 。 如果把 0 型文法分别加上以下的第(1)条限制,则我们就得到 1 型文法: ( 1) G 的任何产生式 α → β 均满足 | α | ≤ | β | ( | α | 指符号串 α 的长度 ,| ε |=0); * (2)G 的任何产生式为 A→β ,A∈V, β ∈(T∪V) :2 型文法 (3)G 的任何产生式为 A→aB 或 A→a,其中 a∈T,A, B∈V:3 型文法。 0 型文法也称短语文法,0 型文法的能力相当于图灵(Turing)机。或者说,任何 0 型语 言都是递归可枚举的;反之,递归可枚举集必定是一个 0 型语言。 1 型文法也称上下文有关文法 (简记为 CSG) 。 这种文法意味着对非终结符进行替换时务 必考虑上下文;并且,一般不允许替换成空串ε 。 2 型文法也称上下文无关文法 (简记为 CFG) 。 这种文法对非终结符进行替换时无需考虑 上下文。上下文无关文法对应非确定的下推自动机。 3 型文法由于形式上类似线性方程,故称右线性文法。由于这类文法等价于正规式,所 以也称正规文法。由正规文法产生的语言叫做正规语言(正规集) 。对任何一个 3 型文法 G. 可以设计一个 NFA,它能够而且只能够识别 G 的语言。当然,也可以对任何 NFA 构造一个 相应的正规文法, 3 型文法的另一种形式是左线性文法,其文法 G 的产生式为: A--Ba 或 A→a a∈T,A,B ∈V 注意:左线性文法与右线性文法是相互等价的。

各类语言与各类自动机的对应关系见表 3.1。

注意:如果产生式“→”左侧有终结符,刚该文法一定属于 0 型或者 1 型文法范畴。0 型和 1 型的区别仅在产生式“→”左、右两侧的符号串长度上;如果文法中所有产生式“→”左 部的符号串长度均小工或等于“→”右部的符号串长度,则为 1 型文法,否则为 0 型文法。 2 型或 3 型文法的产生式“→”的左侧仅为非终结符,如果产生式“→”的右侧形式 上为 aB 或(a∈T,B∈V) ,则为 3 型文法,否则为 2 型文法(上下文无关文法) 。

第二部分

例题与习题

重点与难点
重点:文法、推导与归约、短语与句柄。 难点:文法、推导、归约、短语、句柄、文法的二义性、用文法表示语言。

基本要求
掌握语言的描述、形式定义、文法、文法分类的概念以及形式文法的应用,了解二义性 文法,熟练掌握推导与规约、短语与句柄及用文法描述语言、正则语言、上下文无关文法、 语法分析树。

例题解析
例 1 设有文法 G[S]: S→a|(T)|? T→T,S|S (1) 试给出句子(a,a,a)的最左推导。 (2) 试给出句子(a,a,a)的分析树 (3) 试给出句子(a,a,a)的最右推导和最右推导的逆过程(即最左规约)的每一步的句柄。 【解】(1) (a,a,a)的最左推导 S=>(T) =>(T,S) =>( T,S,S) =>( S,S,S) =>(a,S,S) =>(a,a,S) =>(a,a,a) (2)(a,a,a)的分析树

S ( T T S a , T , S a ) S a

(3)

(a,a,a)最右推导 S=>(T) =>(T,S) =>(T,a) =>(T,S,a) =>(T,a,a) =>(S,a,a) =>(a,a,a)

最左规约每一步的句柄 句柄为:(T) 句柄为:T,S 句柄为:a 句柄为:T,S 句柄为:第一个 a 句柄为:S 句柄为:第一个 a

例 2 已知文法 G[Z]: Z→0U|1V U→1Z|1 V→0Z|0 (1) 请写出此文法描述的只含有4个符号的全部句子。 (2) G[Z]产生的语言是什么? (3) 该文法在 Chomsky 文法分类中属于几型文法? 【解】 (1)0101,0110,1010, 1001 (2)分析 G[Z]所推导出的句子的特点:由 Z 开始的推导不外乎图 1 所示的四种情形。
Z 0 1 U Z 0 Z U 1 1 0 Z V Z 1 Z V 0

图 1 文法 G[Z]可能的几种推导

由 Z 推导出 10 或 01 后就终止或进入递归,而 Z 的每次递归将推导出相同的符号串:10 或 + 01。所以 G[Z]产生的语言 L(G[Z])={x|x∈(10|01) } (3)该文法属于 3 型文法。 例 3 已知文法 G=({A,B,C},{a,b,c},P,A), P 由以下产生式组成: A→abc A→aBbc Bb→bB Bc→Cbcc bC→Cb

aC→aaB aC→aa 此文法所表示的语言是什么? 【解】 分析文法的规则: 每使用一次 Bc→Cbcc,b、c 的个数各增加一个; 每使用一次 aC→aaB 或 aC→aa, a 的个数就增加一个; 产生式 Bb→bB、 bC→Cb 起连接转换作用。 由于 A 是开始符号,由产生式 A→abc 推导得到终结符号串 abc;由产生式 A→aBbc 推导得 到 B 后,每当使用产生式 Bb→bB、Bc→Cbcc、bC→Cb、aC→aaB 就会递归调用 B 一次,所产 生的 a、 b、 c 的个数分别增加一个, 因此推导所得的终结符号串为 abc、 aabbcc、 aaabbbccc、 ? n n n 所以文法描述的语言为{ a b c |n>0}. 例 4 构造描述语言 L(G[S])={( ) |n≥0} 的文法。 【解】(1)找出语言的一些典型句子: n=0 ε n=1 ( ) n=2 (()) ? 所以, L(G[S])={ ε 、( ) (())、((()))、?} (2)分析句子的特点: 只含有(和),(和)的个数相同且对称, 句子中所含的符号数可无限, 句子的个数可无限。 (3)凑规则:由 S→ε |() 得到ε |(),由 A→ (S) 得到 (()),(()) 是在()的两边再加上 一对()得到,((()))是在(())的两边再加上一对()得到,?所以将上述产生式合并为 S→(S) |ε 。 (4)得到文法 G[S]: S→(S) |ε (5)检验:语言所有的句子均可由文法 G[S]推导出来, 文法 G[S]推导出来的所有终结符号串 均为语言的句子. 例 5 构造描述语言 L(G[S])={a b |n>m>0} 的文法。 【解】找出语言的一些典型句子:abb、abbb、?、aabbb、aabbbb、?,语言的句子的特点是 仅含有 a、b, a 在 b 的左边,b 的个数大于 a 的个数,a 的个数至少是 1。 k 单独生成 c , k>1 可用产生式 C→c |Cc 句子中要求 b 的个数大于 a 的个数,所以得到文法: G[S]: S→Ab |Sb A→aAb |ab 检验:语言所有的句子均可由文法 G[S]推导出来, 文法 G[S]推导出来的所有终结符号串均 为语言 L(G[S])的句子. 例 6 设有文法 G[S]: S→S*S|S+S|(S)|i 该文法是否为二义文法? 【解】该文法是二义文法,因为该文法存在句子 i*i+i,该句子有两棵不同的语法树如图 2 所示.。
m n n n

S S i
(1)

S S S i + S i S i S * S i
(2)

*

+

S i

图 2 句子 i*i+i 的语法树 例 7 写一个文法,使其语言是奇数集,且每个奇数不以 0 开头。 【解】解题思路 首先分析题意,本题是希望构造一个文法,由它产生的句子是奇数,并且不以 0 开头, 也就是说它的每个句子都是以 1、3、5、7、9 中的某个数结尾。如果数字只有一位,则 1、 3、5、7、9 就满足要求,如果有多位,则要求第 1 位不能是 0,而中间有多少位,每位是什 么数字(必须是数字)则没什么要求,因此,我们可以把这个文法分 3 部分来完成。分别用 3 个非终结符来产生句子的第 1 位、中间部分和最后一位。引入几个非终结符,其中,一个 用作产生句子的开头,可以是 1-9 之间的数,不包括 0,一个用来产生句子的结尾,为奇 数,另一个则用来产生以非 0 整数开头后面跟任意多个数字的数字串,进行分解之后,这个 文法就很好写了。 解答: G(S):S→CD|D C→CB|A B→A|0 A→2|4|6|8|D D→1|3|5|7|9 例 8 写一个上下文无关文法 CFG, 使其语言是能被 5 整除且不以 0 开头的无符号整数的集合。 (如{5,10,15,?.} ) 【解】解答: 能被 5 整除的数从形式上看,是以 0,5 结尾的数字串。题目要求的不以 0 开头,并要注 意 0 不是该语言的句子。所求文法为: G(S):S→MF|5 F→5|0 M→MD|N D→N|0 N→1|2|3|4|5|6|7|8|9 例 9 证明下面的文法是二义的: S→iSeS|iS|i 【解】解题思路: 根据文法的二义性的定义,如果要证明该文法是二义的,必须找到一个句子,使得该句 子具有两个不同的最右推导或两个不同的语法树。 我们首先分析这个文法, 根据我们对程序 语言的了解, 不难发现, 这个文法应该是用来表示 if?.else?.结构的 (用 “i”代表 “if” 或语句集, “e” 代表 “else” ) 。 因此我们就要到 if?.else?结构中去找二义性。 我们知道, 程序语言一般都规定 else 部分是和它前面离它最近的没有被匹配的的 if 语句进行匹配。 而

上面的这个文法体现不出这种限制,因此我们可以找这样一个句子,在 else 前面有两个 if (如句子 iiiei) ,else 和不同的 if 进行匹配时就会产生不同的语义。 解答: 考虑句子 iiiei,存在如下两个最右推导: S => iSeS => iSei => iiSei => iiiei S => iS => iiSeS => iiSei => iiiei 例 10 某程序设计语言的表达式由运算符θ 1、θ 2、θ 3、标识符、 (、 )组成,其中θ 1 和θ 2 的优先级相同,θ 3 的优先级低于θ 1、θ 2 的优先级,优先级相同的运算符从右往左计算,可 以用括号改变运算的顺序,则下述四种文法中哪一个可以描述上述的表达式文法? 设 E 为识别符号,终结符号集={θ 1、θ 2、θ 3、 (、 ) 、I},非终结符号集={E、T、F}。 a.E→T|Eθ 1T|Eθ 2T T→F|Tθ 3F F→(E)|I b. E→T|Tθ 1E|Tθ 2E T→F|Fθ 3T F→(E)|I c. E→T|Eθ 3T T→F|Tθ 1F|Tθ 2F F→(E)|I d. E→T|Tθ 3 E T→F|Fθ 1T|Fθ 2T F→(E)|I 【解】对于一个包含运算符的语言,运算符的结合顺序、运算符的优先级在文法中反映为递 归的方向和推导(或规约)的先后,左递归表明左边的运算先处理,对应的运算符左结合; 右递归表明右边的运算先处理,对应的运算符右结合。两个运算符连续出现,后推导出(或 先被规约)的,表明其运算先被处理,因此优先级高;反之,先推导出(或后被规约)的, 表明其运算后被处理,因此优先级低。 题意要求:θ 1 和θ 2 的优先级相同,θ 3 的优先级低于θ 1、θ 2 的优先级,因此θ 3 比 θ 1、θ 2 先推导出来,即应为图 3 所示的四种情形。
U U V θ θ U U U θ U θ VV U θ U θ UU U θ U θ V

3

3 V

3

3 V

1

V
(1)

1

2

V
(3)

2

(2)

(4)

图 3 可能的文法推导顺序 因此 a 和 b 不成立。 又因为优先级相同的运算符从右往左计算,应采用右递归,即应为图 4 所示的情形。

U U θ V θ V U

U θ V θ V U

U θ V θ V

1 W
(1)

2 W
(2

3 W
(3)

1

2

3

图 4 可能的文法递归结构 故 c 不成立,应为 d。 例 11 CFG:由相同个数 a 和 b 组成句子 【解】 我们用一个非终结符 A 代表一个 a(即有 A→a),用一个非终结符 B 代表一个 b (即 有 B→b) ;为了保证 a 和 b 的个数相同,则在出现一个 a 时应相应地出现一个 B.出现一个 b 时则相应出现一个 A。假定已推导出 bA,如果下一步要推导出连续两个 b 时,则应有 bA=>bbAA。也即为了保证 b 和 A 的个数一致,应有 A→bAA;同理有 B→aBB 。此外,为了保 证递归地推出所要求的 ab 串,应有 S→aBS 和 S→bAS。由此得到无二义文法 G[S]为: G[S]:S→aBS|bAS|ε A→bAA|a B→aBB|b 例 12 下面的二义文法描述命题演算公式,为它写一个等价的非二义文法。 S → S and S|S or S|not S|p|q|(S) 【解】文法 G[S]:S→S and S| S or S |not S | p |q | (S)所产生的二义性在于:运算符 and 和 or 的优先级未确定,并且 and, or 运算的结合顺序也未确定。由于优先级的高低在产生式中反 映为归约的先后, 运算结合顺序是左结合还是右结合在产生式中反映为递归的方向是左还是 右。根据通常的约定,单个变量 p,q 及运算符 not,括号()的优先级最高,and 的优先级次 之,最 后是运算符 or.为了体现这种关系,我们引入了新的非终结符。注意,归约是从语法树底层 向上进行的,也即越是底层的优先级越高,层次越往上的优先级越低。体现在产生式中,就 是离开始符越远的优先级越高,反之越低。由此,我们得到无二义的文法 G’[S]如下: G’[S]:S→S or A|A A→A and B|B B→not B|p|q|(S) 例 13 有文法 G : S → aAcB|Bd A → AaB|c B → bScA|b ( 1) 试求句型 aAaBcbbdcc 和 aAcbBdcc 的句柄; (2) 写出句子 acabcbbdcc 的最左推导过程。 (1) 【解】分别画出对应两句型的语法树如图(a), (b)所示。

对树(a) ,直接短语有 3 个:AaB, b 和 c,而 AaB 为最左直接短语(即为句柄)。对树 (b) ,直接短语有两个:Bd 和 c,而 Bd 为最左直接短语。 (2)句子 acabcbbdcc 的最左推导如下: S=>aACB=>aAaBCB=>acaBcB=>aCabCB=>acabcbScA=>acabcbBdCA =>acabcbbdcA=>acabcbbdcc


相关文章:
编译原理考试复习题
2、整个编译过程可以划分成五河南城建学院 2010 学年第一学期期末考试编译原理》试题(A 卷) 一、填空题:(每空 1 分,共 10 分) 1、符号表项的组织常...
编译原理(清华大学_张素琴)复习例题 (2)
编译原理(清华大学_张素琴)复习例题 (2)_计算机软件及应用_IT/计算机_专业资料编译原理复习例题(有些内容没有覆盖,比如优化、SLR(1) 、LR(1) 、LALR(1)等...
编译原理复习题--有答案版
编译原理复习题--有答案版_理学_高等教育_教育专区。这是总结的编译原理的试题...(1) S → DbB (4) B → a (2) D → d (5) B → Bba LR 分析...
各章练习题(编译原理)
编译原理练习题(注... 2页 免费 编译原理 第3章习题解答 8页 1下载...{1,2,3} 状态 X 1 2 3 第五章重点:1.LL(1)的判别 要点: (1)计算 ...
编译原理期末复习题(含答案2011-5)
编译原理复习题 一、填空题: 填空题: 1、编译方式与解释方式的根本区别在于( 是否生成目标代码 )。 2、对编译程序而言,输入数据是( 源程序 ) ,输出结果是( ...
2013编译原理复习题及答案
编译原理复习题及答案 一、选择题 1. 一个正规语言只能对应( B A 一个正规文法 2. ) B 一个最小有限状态自动机 文法 G[A]:A→ε A→aB B→Ab B→...
大学计算机编译原理期末复习试题(含有答案)
大学计算机编译原理期末复习试题(含有答案)_工学_高等教育_教育专区。编译原理 计算机科学与技术 期末考试 复习题 习题一、单项选择题 1、将编译程序分成若干个“遍...
编译原理复习题目集答案
(3)对输入串 i+i#的算符优先分析过程为: 题目 2:作业、习题 6.1、复习:...编译原理期末复习题_含答... 20页 2下载券 2010编译原理复习例题答... 8页...
编译原理期末考试习题及答案
编译原理期末考试习题及答案_教育学_高等教育_教育专区。一、填空题|(每题 4 ...R S1 { Backpatch($2.chain , nxq )} 一、填空题|(每题 4 分,共 20...
编译原理复习题-给学生(2014)
编译原理复习题 一、单项选择题 概述部分 1.构造编译程序应掌握 。D A. 源程序 B. 目标语言 C. 编译方法 D. 以上三项都是 2.编译程序绝大多数时间花...
更多相关标签: