第四章部分习题解答

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)