《编译原理 龙书答案》由会员分享，可在线阅读，更多相关《编译原理 龙书答案（24页珍藏版）》请在金锄头文库上搜索。
1、第四章部分习题解答Aho：编译原理技术与工具书中习题（Aho）4.1 考虑文法S ( L ) | aL L, S | Sa) 列出终结符、非终结符和开始符号解：终结符：(、)、a、，非终结符：S、L开始符号：Sb) 给出下列句子的语法树i) (a, a)ii) (a, (a, a)iii) (a, (a, a), (a, a)c) 构造b)中句子的最左推导i) S(L)(L, S) (S, S) (a, S) (a, a)ii) S(L)(L, S) (S, S) (a, S) (a, (L) (a, (L, S) (a, (S, S) (a, (a, S) (a, (a, a)iii) S(
2、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) S(L)(L, S) (L, a) (S, a) (a, a)ii) S(L)(L, S) (L, (L) (L, (L, S) (
3、L, (L, a) (L, (S, a) (L, (a, a) (S, (a, a) (a, (a, a)iii) 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
4、, a)e) 该文法产生的语言是什么解：设该文法产生语言（符号串集合）L，则 L = (A1, A2, , An) | n是任意正整数，Ai=a，或AiL，i是1n之间的整数（Aho）4.2考虑文法SaSbS | bSaS | ea) 为句子构造两个不同的最左推导，以证明它是二义性的SaSbSabSabaSbSababSababSaSbSabSaSbSabaSbSababSababb) 构造abab对应的最右推导SaSbSaSbaSbSaSbaSbaSbabababSaSbSaSbabSaSbabSabababc) 构造abab对应语法树d) 该文法产生什么样的语言？解：生成的语言：a、b个数
5、相等的a、b串的集合（Aho）4.3 考虑文法bexpr bexpr or bterm | btermbterm bterm and bfactor | bfactorbfactor not bfactor | ( bexpr ) | true | falsea) 试为句子not ( true or false) 构造分析树解：b) 试证明该文法产生所有布尔表达式证明：一、首先证明文法产生的所有符号串都是布尔表达式变换命题形式以bexpr、bterm、bfactor开始的推导得到的所有符号串都是布尔表达式最短的推导过程得到true、false，显然成立假定对步数小于n的推导命题都成立考虑步数等
6、于n 的推导，其开始推导步骤必为以下情况之一bexpr bexpr or btermbexpr btermbterm bterm and bfactorbexpr bfactorbfactor not bfactorbfactor ( bexpr )而后继推导的步数显然n，因此由归纳假设，第二步句型中的NT推导出的串均为布尔表达式，这些布尔表达式经过or、and、not运算或加括号，得到的仍是布尔表达式因此命题一得证。二、证明所有布尔表达式均可由文法生成变换命题所有析取式均可由bexpr推导出来，所有合取式均可由bterm（bexpr）推导出来，所有对子布尔表达式施加not运算或加括号或简单t
7、rue、false都可由bfactor（bexpr、bterm）推导出来最简单的布尔表达式true和false显然成立假定对长度小于n的布尔表达式，均可由文法推导出来考虑长度等于n的布尔表达式B，显然，B只能是以下形式之一B = B1 or B2B = B1 and B2B = not B1B = ( B1 )以上几种情况，B1、B2的长度均小于n对于情况1：B为析取式，B1可为析取式也可为合取式，B2为合取式，根据假设可由bexpr合bterm推导出来，显然可构造推导过程，由bexpr推导出B其他情况类似，命题二得证综合一、二，可知文法产生的语言就是布尔表达式c) （Aho）4.4考虑文法R
8、R | R | RR | R* | (R) | a | bc) 构造等价的非二义性文法RR | A | AAA B | BBB* | CC( R ) | a | b（Aho）4.5下面if-then-else文法试图消除空悬else的二义性，证明它仍是二义性的stmtif expr then stmt | matched_stmtmatched_stmtif 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
9、i E t o e o对应两个最左推导：Si E t Si E t Mi E t i E t M e Si E t i E t o e Si E t i E t o e Mi E t i E t o e i E t M e Si 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 Mi E t i E t o e i E t o e oSMi E t M e Si 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
10、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=Mi E t M e S, SM，有移进/归约冲突，这就是是二义性所在。显然，存在句型.i E t M e S.和.i E t S e S.，当M位于栈顶时，产生移进/归约冲突。按此思路，构造形如. i E t S e S.的句型即可（Aho）4.6 为下列语言设计上下文无关文法。哪些语言是正规式？a) 满足这
11、样条件的二进制串：每个0之后都紧跟着至少一个1S0 A | 1 S | eA1 S正规式：(1 | 01)*b) 0和1个数相等的二进制串S0 S 1 S | 1 S 0 S | ed) 不含011子串的二进制串S0 A | 1 S | eA0 A | 1 B | eB0 A | e正规式：1*(0 | 01)*e) 具有形式xy的二进制串，xyS A | B | A B | B AA D A D | 0B D B D | 1D 0 | 1A、B分别表示中心符号为0、1的长度为奇数的二进制串将AB串接，长度为偶数，将它从中间分为长度相等的两部分，x、y虽然A、B长度可能不一样，但容易得到，A的
12、中心0在x中的位置，与B的中心1在y中的位置是相同的，因此xyBA的情况类似f) 形如xx的0、1串解：此语言无法用上下文无关文法描述（Aho）4.11 对习题4.1中文法a) 消除左递归S( L ) | aLS LL, S L | eb) 构造预测分析表，对4.1(b)中句子，给出预测分析器的运行过程FIRST(S) = (, a )FIRST(L) = (, a FIRST(L) = , e FOLLOW(S) = , ), $FOLLOW(L) = ) FOLLOW(L) = ) 预测分析表：a(),$SSaS( L )LLS LLS LLLeL, S L(a, a)的分析过程栈输入输出
13、$S(a, a)$) L (a, a)$S( L )$) La, a)$LS L$) L Sa, a)$Sa$) L aa, a)$) L, a)$L, S L$) L S , a)$) L Sa)$Sa$) L aa)$) L)$Le$)$其他两个句子的分析过程类似（Aho）4.13 下面文法产生除e外所有长度为偶数的a的串S a S a | a aa）试为该文法构造一个带回溯的递归下降语法分析器，对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
