编译原理 龙书答案.docx
7页
本文格式为Word版，下载可任意编辑编译原理 龙书答案 第四章片面习题解答 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’ — 7 —。
