编译原理 龙书答案

第四章部分习题解答

Aho：《编译原理技术与工具》书中习题 （Aho）4.1 考虑文法 S → ( L ) | a L → L, S | S

a) 列出终结符、非终结符和开始符号 解：

终结符：(、)、a、， 非终结符：S、L 开始符号：S

b) 给出下列句子的语法树

i) (a, a) ii) (a, (a, a)) iii) (a, ((a, a), (a, a)))

c) 构造b)中句子的最左推导

i) ii) iii)

S?(L)?(L, S) ?(S, S) ?(a, S) ?(a, a)

S?(L)?(L, S) ?(S, S) ?(a, S) ?(a, (L)) ?(a, (L, S)) ?(a, (S, S)) ?(a, (a, S) ?(a, (a, a))

S?(L)?(L, S) ?(S, S) ?(a, S) ?(a, (L)) ?(a, (L, S)) ?(a, (S, S)) ?(a, ((L), S)) ?(a, ((L, S), S)) ?(a, ((S, S), S)) ?(a, ((a, S), S)) ?(a, ((a, a), S)) ?(a, ((a, a), (L))) ?(a, ((a, a), (L, S))) ?(a, ((a, a), (S, S))) ?(a, ((a, a), (a, S))) ?(a, ((a, a), (a, a)))

d) 构造b)中句子的最右推导

i) ii) iii)

S?(L)?(L, S) ?(L, a) ?(S, a) ?(a, a)

S?(L)?(L, S) ? (L, (L)) ?(L, (L, S)) ?(L, (L, a)) ?(L, (S, a)) ?(L, (a, a)) ?(S, (a, a)) ?(a, (a, a))

S?(L)?(L, S) ?(L, (L)) ?(L, (L, S)) ?(L, (L, (L))) ?(L, (L, (L, S))) ?(L, (L, (L, a))) ?(L, (L, (S, a))) ?(L, (L, (a, a))) ?(L, (S, (a, a))) ?(L, ((L), (a, a))) ?(L, ((L, S), (a, a))) ?(L, ((L, a), (a, a))) ?(L, ((S, a), (a, a))) ?(L, ((a, a), (S, S))) ?(S, ((a, a), (a, a))) ?(a, ((a, a), (a, a)))

e) 该文法产生的语言是什么

解：设该文法产生语言（符号串集合）L，则

L = { (A1, A2, …, An) | n是任意正整数，Ai=a，或Ai∈L，i是1～n之间的整数}

（Aho）4.2考虑文法 S→aSbS | bSaS | ?

a) 为句子构造两个不同的最左推导，以证明它是二义性的 S?aSbS?abS?abaSbS?ababS?abab

S?aSbS?abSaSbS?abaSbS?ababS?abab

b) 构造abab对应的最右推导

S?aSbS?aSbaSbS?aSbaSb?aSbab?abab S?aSbS?aSb?abSaSb?abSab?abab

c) 构造abab对应语法树

d) 该文法产生什么样的语言？

解：生成的语言：a、b个数相等的a、b串的集合

（Aho）4.3 考虑文法

bexpr → bexpr or bterm | bterm bterm → bterm and bfactor | bfactor

bfactor → not bfactor | ( bexpr ) | true | false a) 试为句子not ( true or false) 构造分析树 解：

b) 试证明该文法产生所有布尔表达式 证明：

一、首先证明文法产生的所有符号串都是布尔表达式

变换命题形式——以bexpr、bterm、bfactor开始的推导得到的所有符号串都是布尔表达式 最短的推导过程得到true、false，显然成立 假定对步数小于n的推导命题都成立

考虑步数等于n 的推导，其开始推导步骤必为以下情况之一 bexpr ? bexpr or bterm bexpr ? bterm

bterm ? bterm and bfactor bexpr ? bfactor

bfactor ? not bfactor bfactor ? ( bexpr )

而后继推导的步数显然

二、证明所有布尔表达式均可由文法生成

变换命题——所有析取式均可由bexpr推导出来，所有合取式均可由bterm（bexpr）推导出来，所有对子布尔表达式施加not运算或加括号或简单true、false都可由bfactor（bexpr、bterm）推导出来

最简单的布尔表达式true和false显然成立

假定对长度小于n的布尔表达式，均可由文法推导出来

考虑长度等于n的布尔表达式B，显然，B只能是以下形式之一 B = B1 or B2 B = B1 and B2 B = not B1 B = ( B1 )

以上几种情况，B1、B2的长度均小于n

对于情况1：B为析取式，B1可为析取式也可为合取式，B2为合取式，根据假设可由bexpr合bterm推导出来，显然可构造推导过程，由bexpr推导出B 其他情况类似，命题二得证

综合一、二，可知文法产生的语言就是布尔表达式 c)

（Aho）4.4考虑文法

R→R ‘|’ R | RR | R* | (R) | a | b c) 构造等价的非二义性文法 R→R ‘|’ A | A A→A B | B B→B* | C C→( R ) | a | b

（Aho）4.5下面if-then-else文法试图消除空悬else的二义性，证明它仍是二义性的 stmt→if expr then stmt | matched_stmt

matched_stmt→if expr then matched_stmt else stmt | other 解：

用S、M、E表示stmt、matched_stmt和expr，用i、t、e、o表示if、then、else和other 则句子i E t i E t o e i E t o e o对应两个最左推导：

S?i E t S?i E t M?i E t i E t M e S?i E t i E t o e S?i E t i E t o e M ?i E t i E t o e i E t M e S?i E t i E t o e i E t o e S ?i E t i E t o e i E t o e M ?i E t i E t o e i E t o e o

S?M?i E t M e S?i E t i E t M e S e S? i E t i E t o e S e S? i E t i E t o e i E t S e S ? i E t i E t o e i E t M e S? i E t i E t o e i E t o e S? i E t i E t o e i E t o e M ? i E t i E t o e i E t o e o 因此文法是二义性文法

直接构造比较困难，可从SLR分析表的构造角度考虑，LR(0)项目集规范族中，项目 I8={M→i E t M ? e S, S→?M}，有移进/归约冲突，这就是是二义性所在。

显然，存在句型...i E t M e S...和...i E t S e S...，当M位于栈顶时，产生移进/归约冲突。 按此思路，构造形如... i E t S e S...的句型即可

（Aho）4.6 为下列语言设计上下文无关文法。哪些语言是正规式？ a) 满足这样条件的二进制串：每个0之后都紧跟着至少一个1 S→0 A | 1 S | ? A→1 S

正规式：(1 | 01)*

b) 0和1个数相等的二进制串 S→0 S 1 S | 1 S 0 S | ??

d) 不含011子串的二进制串 S→0 A | 1 S | ? A→0 A | 1 B | ? B→0 A | ??

正规式：1*(0 | 01)*

e) 具有形式xy的二进制串，x≠y S→ A | B | A B | B A A→ D A D | 0 B→ D B D | 1 D→ 0 | 1

A、B分别表示中心符号为0、1的长度为奇数的二进制串

将AB串接，长度为偶数，将它从中间分为长度相等的两部分，x、y

虽然A、B长度可能不一样，但容易得到，A的中心0在x中的位置，与B的中心1在y中的位置是相同的，因此x≠y BA的情况类似

f) 形如xx的0、1串

解：此语言无法用上下文无关文法描述

（Aho）4.11 对习题4.1中文法 a) 消除左递归 S→( L ) | a L→S L’ L’→, S L’ | ?

b) 构造预测分析表，对4.1(b)中句子，给出预测分析器的运行过程 FIRST(S) = { (, a ) FIRST(L) = { (, a } FIRST(L’) = { ‘,’, ? } FOLLOW(S) = {‘,’, ), $} FOLLOW(L) = { ) } FOLLOW(L’) = { ) } 预测分析表：

S L L’ (a, a)的分析过程 栈 $S $) L ( $) L $) L’ S $) L’ a $) L’ $) L’ S ,

a S→a L→S L’ ( S→( L ) L→S L’ 输入 ) L’→? , L’→, S L’ $ 输出 (a, a)$ (a, a)$ a, a)$ a, a)$ a, a)$ , a)$ , a)$ S→( L ) L→S L’ S→a L’→, S L’

$) L’ S $) L’ a $) L’ $) $ a)$ a)$ )$ )$ $ S→a L’→? 其他两个句子的分析过程类似

（Aho）4.13 下面文法产生除?外所有长度为偶数的a的串 S → a S a | a a

a）试为该文法构造一个带回溯的递归下降语法分析器，对S的两个候选式首先考虑aSa。证明：S所对应的过程可以成功分析2、4、8个a的串，但6个a的串不行。

解：aa的分析过程，其中√表示匹配成功，×表示匹配失败，匹配失败则尝试下个候选式

aaaa分析过程：

aaaaaa分析过程：

aaaaaaaa分析过程：

b）此语法分析器能识别什么样的语言？

解：由a）的解可以看出，2N个a的串分析过程中，步骤如下

1） 产生2N+1个S的语法树，对第2N+1个S进行扩展时输入缓冲已空，失败 2） 对第2N个S尝试候选式aa，第二个a匹配失败

3） 对第2N-1个S尝试候选式aa，左边N-1个a匹配，右边最后一个a匹配，倒数第二个

a失败

4） 对第2N-2个S尝试候选式aa，左边N-2个a匹配，右边最后一个a和倒数第二个a匹

配，倒数第三个a失败

5） 对第2N-4个S尝试候选式aa，左边N-4个a匹配，右边最后一个a～倒数第四个a匹

配，倒数第五个a失败

6） 对第2N-8个S尝试候选式aa，…

最后正确识别的情况必然是：对第N个S尝试aa，左边N个a和右边N个a恰与输入匹配 显然，可以正确识别的符号串的N满足 2N – 1 – 1 – 2 – 4 - … = N?N=2i

（Aho）4.25 试给出图4－60中的优先关系表对应的优先级函数 解：有向图如下

优先级函数为 f g a 2 3 ( 0 3 ) 2 0 , 2 1 $ 0 0

（Aho）4.26 对习题4.1中文法，利用讲义中给出的算法计算终结符之间的优先关系 解： S → ( L ) | a L → L, S | S 由于S → ( L )，因此 ( ? )

S → ( L )，而L?L , S，L?S?( L )，L?S?a 因此 ( ? , ，( ? (，( ? a；, ? )，) ? )，a ? )

由于L → L, S，而L?L , S，L?S?( L )，L?S?a，因此 , ? ,，) ? ,，a ? ,

而S?( L )，S?a，因此 , ? ( ，, ? a 非终结符与$优先关系的计算方法： 如果存在S?a…，或S?Qa…，则$ ? a， 若存在S?…a，或S?…aQ，则a ? $ 因此，$ ? (，$ ? a，) ? $，a ? $ 算符优先关系表为：

a ( ) , $ a ? ? ? ( ? ? ? ) ? ? ? ? , ? ? ? ? $ ? ?

（Aho）4.27 试给下列文法构造算符优先关系 a） 练习4.2中文法 解：

S→aSbS | bSaS | ? 由S→aSbS可得a?b 由S→bSaS可得b?a

由S→aSbS，和S?bSaS可得a?b、b?b、a?b，和S?aSbS可得a?a、b?a、b?b 由S→bSaS，和S?bSaS可得b?b、a?b、a?a，和S?aSbS可得b?a、a?a、a?a 文法不是算符优先文法，二义性文法，很自然 b） 练习4.3中文法

bexpr → bexpr or bterm | bterm bterm → bterm and bfactor | bfactor

bfactor → not bfactor | ( bexpr ) | true | false

解：无论分析语法含义，还是利用4.26算法计算，均可得到 true false not and or （ ） $

true false not and or ( ) $ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

（Aho）4.30 一个文法称为Greibach范式（GNF）文法，如果它无?产生式，且每个产生式（S→?除外）均形如A→a?，其中，a是终结符，?是非终结符串，也可能为空。 a） 试编写一个算法，将给定文法转换为Greibach范式 解：算法步骤如下

1． 先将文法消除左递归、消除?产生式、删除无用符号，然后对每个非终结符A的每个产

生式，执行2

2． 若产生式右部以终结符开始，则略过，考虑其他产生式，否则产生式必为A→A1?的形

式，A1为≠A的NT，a为语法符号串，对它执行以下操作

i. 将A1的所有产生式的右部替换A1，产生新的关于A的产生式 ii. 对于这些产生式，若右部以T开始，略过，不予处理，考虑那些以NT开始的

产生式，反复执行i、ii

iii. 由于文法的NT个数是有限的（设为k），且已消除左递归，则最多k个步骤

后，处理完毕，此时，A的产生式右部应该均以T开始。否则，若某个产生式右部以NT开始，表明A无论经过怎样的推导过程，均不可能得到一个以终结符开始的串，当然也就不可能得到一个终结符串，这显然是一个错误的文法，矛盾。这样，A的某个产生式处理完毕，其右部均以T开始。转向2，继续考虑其他产生式，所有产生式处理完毕，则转向3

3． 此时，每个产生式均为A→a?的形成，a为NT，?为语法符号串，若?中包含T，则进

行如下处理

i. 假定?中包含k个T，则产生式形为A→a??a1??…ak?k，其中ai为T，?i为NT

串或? ii. 引入k个新的NT A1、A2、…Ak，和k个新的产生式

A1→a1?1A2 A2→a2?2A3 …

Ak-1→ak-1?k-1Ak

Ak→ak?k

而将原产生式改为A→a????

4． 经过2、3处理，所有产生式必然满足Greibach范式的格式 b） 将你的算法应用到表达式文法4-10上

解：文法4－10消除左递归、消除?产生式后得到 E→T E' | T E'→+ T E' | + T T→F T' | F T'→* F T' | * F F→( E ) | id

将每个产生式转换为以T开始的形式，得到

E→( E ) T' E' | id T' E' | ( E ) E' | id E' | ( E ) T' | id T' | ( E ) | id E'→+ T E' | + T

T→( E ) T' | id T' | ( E ) | id T'→* F T' | * F F→( E ) | id

将每个产生式右部转换为T NT*的形式，最后结果为： E→( E E''| id T' E' | ( E E''' | id E' | ( E | id T' | ( E E''''' | id E''→) T' E' E'''→) E' E''''→) T' E'''''→)

E'→+ T E' | + T

T→( E E'''' | id T' | ( E E''''' | id T'→* F T' | * F F→( E E''''' | id

（Aho）4.33 考虑文法 S→AS | b A→SA | a

a) 构造此文法的LR(0)项目集规范族 解：

I0 = { S’→?S, S→?AS, S→?b, A→?SA, A→?a }

goto(I0, S) = { S’→S?, A→S?A, A→?SA, A→?a, S→?AS, S→?b } = I1 goto(I0, A) = { S→A?S, S→?AS, S→?b, A→?SA, A→?a } = I2 goto(I0, a) = { A→a? } = I3 goto(I0, b) = { S→b? } = I4

goto(I1, S) = { A→S?A, A→?SA, A→?a, S→?AS, S→?b } = I5

goto(I1, A) = { A→SA?, S→A?S, S→?AS, S→?b, A→?SA, A→?a } = I6 goto(I1, a) = I3, goto(I1, b) = I4

goto(I2, S) = { S→AS?, A→S?A, A→?SA, A→?a, S→?AS, S→?b } = I7 goto(I2, A) = I2, goto(I2, a) = I3, goto(I2, b) = I4 goto(I5, S) = I5, goto(I5, A) = I6, goto(I5, a) = I3, goto(I5, b) = I4

本文来源：https://www.bwwdw.com/article/pfdt.html