编译原理(龙书)

龙书编译原理(一)编译原理简介什么是编译编译是指将人类编写的高级程序代码转换成机器能够理解的底层语言的过程。

编译器是负责完成这种转换的程序。

编译器的工作过程编译器大致可以分为以下几个步骤：1.分词2.语法分析3.语义分析4.中间代码生成5.代码优化6.目标代码生成分词分词阶段将源代码拆分成一个个单词。

单词是指代码中的标识符、关键字、运算符等不可拆分的最小单元。

例如，针对以下代码：int main(){printf("Hello, World!\n");return0;}分词后会得到这样的结果：intmain(){printf("Hello, World!");return;}语法分析语法分析阶段将单词组成的序列转化成语法分析树，也叫做抽象语法树。

语法分析树采用树状结构表示程序的语法结构。

例如，对于以下代码：int main(){printf("Hello, World!\n");return0;}语法分析树大致如下：Program│└─── Main Function│├─── Declare int│├─── Function Body│ ││ ├─── Call printf│ │ ││ │ ├─── String "Hello, World!"│ │ ││ │ └─── End of Arg uments│ ││ └─── Return 0│└─── End of Main Function语义分析语义分析阶段检查程序的语义错误和类型错误。

例如，一个整数类型的变量不能被赋值给一个字符串类型的变量。

中间代码生成中间代码生成阶段将语法分析树转化成一种中间代码，以便在后面的优化和目标代码生成阶段使用。

中间代码通常是一种抽象的栈式或寄存器式指令集。

例如，以下代码：int main(){int a =1+2;printf("%d\n", a);return0;}中间代码大致如下：1: t1 = 12: t2 = 23: t3 = t1 + t24: a = t35: printf("%d\n", a)6: return 0代码优化代码优化阶段根据中间代码尽量优化程序性能，以及压缩代码。

编译原理龙书第四章答案编译原理是计算机科学中的一门基础课程，是用于教授计算机程序的设计、构建和优化的学科，常常被用于编写编译器和解释器。

在编译原理课程中，龙书（Compilers: Principles, Techniques, and Tools）是一本经典的教材，其中第四章主要讲述了词法分析器的设计和实现。

以下是第四章的答案，按照列表划分：1. 什么是词法分析器？词法分析器（Lexical Analyzer）是编译器的组成部分之一，它用于将程序中的字符序列转换为一系列单词或词法单元（Lexeme），以便后续的语法分析和语义分析使用。

2. 词法分析器的工作流程是什么？词法分析器的工作流程如下：（1）读入字符序列。

（2）将字符序列划分为一个个词法单元，或者检查字符序列是否合法。

（3）生成一个词法单元序列，并将其传递给语法分析器。

3. 词法单元的定义是什么？词法单元是编程语言中的一个基本单元，它是对代码中的一个单一概念进行编码的基本方式。

例如，在C语言中，词法单元包括关键字（如int，if，while等）、标识符（Identifier，即自定义变量名）、运算符和特殊符号等。

4. 有哪些方法可以实现词法分析器？可以使用正则表达式、自动机等方法实现词法分析器。

其中，正则表达式可以表示字符串的集合，因此可以将其用于识别单词类别；自动机是根据输入字符序列转换状态的一种计算模型，因此可以用于实现有限自动机（Deterministic Finite Automaton）和非确定有限自动机（Nondeterministic Finite Automaton）等。

5. DFA和NFA分别是什么？DFA和NFA都是有限自动机的一种，但在转换动作上有所不同。

DFA 是确定的有限自动机，即在状态转换时只有唯一的一个选择；而NFA 是非确定的有限自动机，即在状态转换时可以有多个选择。

6. DFA和NFA之间有什么关系？DFA和NFA虽然在转换动作上不同，但它们可以互相转化。

第四章部分习题解答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(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)) (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, a)))e)该文法产生的语言是什么解：设该文法产生语言（符号串集合）L，则L = { (A1, A2, …, A n) | n是任意正整数，A i=a，或A i∈L，i是1～n之间的整数}（Aho）4.2考虑文法S→aSbS | bSaS |a)为句子构造两个不同的最左推导，以证明它是二义性的S aSbS abS abaSbS ababS ababS aSbS abSaSbS abaSbS ababS ababb)构造abab对应的最右推导S aSbS aSbaSbS aSbaSb aSbab ababS aSbS aSb abSaSb abSab ababc)构造abab对应语法树d)该文法产生什么样的语言？解：生成的语言：a、b个数相等的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的推导命题都成立考虑步数等于n 的推导，其开始推导步骤必为以下情况之一bexpr bexpr or btermbexpr btermbterm bterm and bfactorbexpr bfactorbfactor not bfactorbfactor ( bexpr )而后继推导的步数显然<n，因此由归纳假设，第二步句型中的NT推导出的串均为布尔表达式，这些布尔表达式经过or、and、not运算或加括号，得到的仍是布尔表达式因此命题一得证。

编译原理(龙书)课后习题解答(详细)编译原理(龙书)课后题解答第一章1.1.1 ：翻译和编译的区别？答：翻译通常指自然语言的翻译，将一种自然语言的表述翻译成另一种自然语言的表述，而编译指的是将一种高级语言翻译为机器语言（或汇编语言）的过程。

1.1.2 ：简述编译器的工作过程？答：编译器的工作过程包括以下三个阶段：(1) 词法分析：将输入的字符流分解成一个个的单词符号，构成一个单词符号序列；(2) 语法分析：根据语法规则分析单词符号序列中各个单词之间的关系，确定它们的语法结构，并生成抽象语法树；(3) 代码生成：根据抽象语法树生成目标程序（机器语言或汇编语言），并输出执行文件。

1.2.1 ：解释器和编译器的区别？答：解释器和编译器的主要区别在于执行方式。

编译器将源程序编译成机器语言或汇编语言等，在运行时无需重新编译，程序会一次性运行完毕；而解释器则是边翻译边执行，每次执行都需要进行一次翻译，一次只执行一部分。

1.2.2 ：Java语言采用的是解释执行还是编译执行？答：Java一般是编译成字节码的形式，然后由Java虚拟机（JVM）进行解释执行。

但是，Java也有JIT（即时编译器）的存在，当某一段代码被多次执行时，JIT会将其编译成机器语言，提升代码的执行效率。

第二章2.1.1 ：使用BNF范式定义简单的加法表达式和乘法表达式答：<加法表达式> ::= <加法表达式> "+" <乘法表达式> | <乘法表达式><乘法表达式> ::= <乘法表达式> "*" <单项式> | <单项式><单项式> ::= <数字> | "(" <加法表达式> ")"2.2.3 ：什么是自下而上分析？答：自下而上分析是指从输入字符串出发，自底向上构造推导过程，直到推导出起始符号。

编译原理书籍推荐
编译原理书籍推荐：
1.《编译原理》（龙书），作者：Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman
这本经典教材系统地介绍了编译原理的基本概念、原理和技术。

它包含了编译器设计与实现所需的知识，涉及词法分析、语法分析、语义分析、中间代码生成等内容。

2.《现代编译原理-C语言描述》，作者：Andrew W. Appel
这本书以C语言描述编译原理的各个方面，包括词法分析、
语法分析、语义分析、中间代码生成、代码优化和代码生成等。

适合初学者入门，易于理解和实践。

3.《编译器设计》（虎书），作者：阿巴基维尔编著
这本书以编译器设计和实现为主题，内容包括词法分析、语
法分析、语义分析、中间代码生成、代码优化和代码生成等。

它以编译器设计的实例为线索，使读者更易于理解和应用所学知识。

4.《编程语言实现模式》，作者：Terence Parr
这本书介绍了使用ANTLR工具进行编译器开发的实践方法
和技巧。

它通过实例来展示如何实现词法分析器、语法分析器和语义分析器等编译器模块。

5.《深入理解计算机系统》，作者：Randal E. Bryant, David R. O'Hallaron
这本书以计算机系统的层次结构为基础，介绍了编译器在系统中的地位和作用。

它涵盖了编译器的基本概念和技术，并介绍了与编译器相关的主题，如汇编语言、操作系统和计算机体系结构等。

这里推荐的书籍都是经典教材或实践指南，适合初学者入门和深入学习编译原理的读者。

1) What is the difference between a compiler and an interpreter?• A compiler is a program that can read a program in one language - the source language - and translate it into an equivalent program in another language – the target language and report any errors in the source program that it detects during the translation process.• Interpreter directly executes the operations specified in the source program on inputs supplied by the user.2) What are the advantages of:(a) a compiler over an interpretera. The machine-language target program produced by a compiler is usually much faster than an interpreter at mapping inputs to outputs.(b) an interpreter over a compiler?b. An interpreter can usually give better error diagnostics than a compiler, because it executes the source program statement by statement.3) What advantages are there to a language-processing system in which the compiler produces assembly language rather than machine language?The compiler may produce an assembly-language program as its output, becauseassembly language is easier to produce as output and is easier to debug.4.2.3 Design grammars for the following languages:a) The set of all strings of 0s and 1s such that every 0 is immediately followed by at least 1.S -> SS | 1 | 01 | ε4.3.1 The following is a grammar for the regular expressions over symbols a and b only, using + in place of | for unions, to avoid conflict with the use of vertical bar as meta-symbol in grammars:rexpr -> rexpr + rterm | rtermrterm -> rterm rfactor | rfactorrfactor -> rfactor * | rprimaryrprimary -> a | ba) Left factor this grammar.rexpr -> rexpr + rterm | rtermrterm -> rterm rfactor | rfactorrfactor -> rfactor * | rprimaryrprimary -> a | bb) Does left factoring make the grammar suitable for top-down parsing?No, left recursion is still in the grammar.c) In addition to left factoring, eliminate left recursion from the original grammar.rexpr -> rterm rexpr’rexpr’ -> + rterm rexpr | εrterm -> rfactor rterm’rterm’ -> rfactor rterm | εrfactor -> rprimary rfactor’rfactor’ -> * rfactor’ | εrprimary -> a | bd) Is the resulting grammar suitable for top-down parsing?Yes.Exercise 4.4.1 For each of the following grammars, derive predictive parsers and show the parsing tables. You may left-factor and/or eliminate left-recursion from your grammars first.A predictive parser may be derived by recursive decent or by the table driven approach. Either way you must also show the predictive parse table.a) The grammar of exercise 4.2.2(a).4.2.2 a) S -> 0S1 | 01This grammar has no left recursion. It could possibly benefit from left factoring. Here is the recursive decent PP code.s() {match(‘0’);if (lookahead == ‘0’)s();match(‘1’);}OrLeft factoring the grammar first:S -> 0S’S’ -> S1 | 1s() {match(‘0’); s’();}s’() {if (lookahead == ‘0’)s(); match(‘1’);elsematch(‘1’);}Now we will build the PP tableS -> 0S’S’ -> S1 | 1First(S) = {0}First(S’) = {0, 1}Follow(S) = {1, $}The predictive parsing algorithm on page 227 (fig4.19 and 4.20) can use this table for non-recursive predictive parsing.b) The grammar of exercise 4.2.2(b).4.2.2 b) S -> +SS | *SS | a with string +*aaa.Left factoring does not apply and there is no left recursion to remove.s() {if(lookahead == ‘+’)match(‘+’); s(); s();else if(lookahead == ‘*’)match(‘*’); s(); s();else if(lookahead == ‘a’)match(‘a’);elsereport(“syntax error”);}First(S) = {+, *, a}Follow(S) = {$, +, *, a}The predictive parsing algorithm on page 227 (fig4.19 and 4.20) can use this table for non-recursive predictive parsing.5.1.1 a, b, c: Investigating GraphViz as a solution to presenting trees5.1.2: Extend the SDD of Fig. 5.4 to handle expressions as in Fig. 5.1:1.L -> E N1.L.val = E.syn2. E -> F E'1. E.syn = E'.syn2.E'.inh = F.val3.E' -> + T Esubone'1.Esubone'.inh = E'.inh + T.syn2.E'.syn = Esubone'.syn4.T -> F T'1.T'.inh = F.val2.T.syn = T'.syn5.T' -> * F Tsubone'1.Tsubone'.inh = T'.inh * F.val2.T'.syn = Tsubone'.syn6.T' -> epsilon1.T'.syn = T'.inh7.E' -> epsilon1.E'.syn = E'.inh8. F -> digit1. F.val = digit.lexval9. F -> ( E )1. F.val = E.syn10.E -> T1. E.syn = T.syn5.1.3 a, b, c: Investigating GraphViz as a solution to presenting trees5.2.1: What are all the topological sorts for the dependency graph of Fig. 5.7?1.1, 2, 3, 4, 5, 6, 7, 8, 92.1, 2, 3, 5, 4, 6, 7, 8, 93.1, 2, 4, 3, 5, 6, 7, 8, 94.1, 3, 2, 4, 5, 6, 7, 8, 95.1, 3, 2, 5, 4, 6, 7, 8, 96.1, 3, 5, 2, 4, 6, 7, 8, 97.2, 1, 3, 4, 5, 6, 7, 8, 98.2, 1, 3, 5, 4, 6, 7, 8, 99.2, 1, 4, 3, 5, 6, 7, 8, 910.2, 4, 1, 3, 5, 6, 7, 8, 95.2.2 a, b: Investigating GraphViz as a solution to presenting trees5.2.3: Suppose that we have a production A -> BCD. Each of the four nonterminals A, B, C, and D have two attributes: s is a synthesized attribute, and i is an inherited attribute. For each of the sets of rules below, tell whether (1) the rules are consistent with an S-attributed definition (2) the rules are consistent with an L-attributed definition, and (3) whether the rules are consistent with any evaluation order at all?a) A.s = B.i + C.s1.No--contains inherited attribute2.Yes--"From above or from the left"3.Yes--L-attributed so no cyclesb) A.s = B.i + C.s and D.i = A.i + B.s1.No--contains inherited attributes2.Yes--"From above or from the left"3.Yes--L-attributed so no cyclesc) A.s = B.s + D.s1.Yes--all attributes synthesized2.Yes--all attributes synthesized3.Yes--S- and L-attributed, so no cyclesd)• A.s = D.i• B.i = A.s + C.s• C.i = B.s• D.i = B.i + C.i1.No--contains inherited attributes2.No--B.i uses A.s, which depends on D.i, which depends on B.i (cycle)3.No--Cycle implies no topological sorts (evaluation orders) using the rules5.3.1: Below is a grammar for expressions involving operator + and integer or floating-point operands. Floating-point numbers are distinguished by having a decimal point.1. E -> E + T | T2.T -> num . num | numa) Give an SDD to determine the type of each term T and expression E.1. E -> Esubone + T1. E.type = if (E.type == float || T.type == float) { E.type = float } else{ E.type = integer }2. E -> T1. E.type = T.type3.T -> numsubone . numsubtwo1.T.type = float4.T -> num1.T.type = integerb) Extend your SDD of (a) to translate expressions into postfix notation. Use the binary operator intToFloat to turn an integer into an equivalent float.Note: I use character ',' to separate floating point numbers in the resulting postfix notation. Also, the symbol "||" implies concatenation.1. E -> Esubone + T1. E.val = Esubone.val || ',' || T.val || '+'2. E -> T1. E.val = T.val3.T -> numsubone . numsubtwo1.T.val = numsubone.val || '.' || numsubtwo.val4.T -> num1.T.val = intToFloat(num.val)5.3.2 Give an SDD to translate infix expressions with + and * into equivalent expressions without redundant parenthesis. For example, since both operators associate from the left, and * takes precedence over +, ((a*(b+c))*(d)) translates into a*(b+c)*d. Note: symbol "||" implies concatenation.1.S -> E1. E.iop = nil2.S.equation = E.equation2. E -> Esubone + T1.Esubone.iop = E.iop2.T.iop = E.iop3. E.equation = Esubone.equation || '+' || T.equation4. E.sop = '+'3. E -> T1.T.iop = E.iop2. E.equation = T.equation3. E.sop = T.sop4.T -> Tsubone * F1.Tsubone.iop = '*'2. F.iop = '*'3.T.equation = Tsubone.equation || '*' || F.equation4.T.sop = '*'5.T -> F1. F.iop = T.iop2.T.equation = F.equation3.T.sop = F.sop6. F -> char1. F.equation = char.lexval2. F.sop = nil7. F -> ( E )1.if (F.iop == '*' && E.sop == '+') { F.equation = '(' || E.equation || ')' }else { F.equation = E.equation }2. F.sop = nil5.3.3: Give an SDD to differentiate expressions such as x * (3*x + x * x) involving the operators + and *, the variable x, and constants. Assume that no simplification occurs, so that, for example, 3*x will be translated into 3*1 + 0*x. Note: symbol "||" implies concatenation. Also, differentiation(x*y) = (x * differentiation(y) + differentiation(x) * y) and differentiation(x+y) = differentiation(x) + differentiation(y).1.S -> E1.S.d = E.d2. E -> T1. E.d = T.d2. E.val = T.val3.T -> F1.T.d = F.d2.T.val = F.val4.T -> Tsubone * F1.T.d = '(' || Tsubone.val || ") * (" || F.d || ") + (" || Tsubone.d || ") * (" ||F.val || ')'2.T.val = Tsubone.val || '*' || F.val5. E -> Esubone + T1. E.d = '(' || Esubone.d || ") + (" || T.d || ')'2. E.val = Esubone.val || '+' || T.val6. F -> ( E )1. F.d = E.d2. F.val = '(' || E.val || ')'7. F -> char1. F.d = 12. F.val = char.lexval8. F -> constant1. F.d = 02. F.val = constant.lexval。

编译原理龙书第二版课后答案【篇一：编译原理习题答案,1-8 章龙书第二版7.8 章】6 ：c 语言函数 f 的定义如下：int f(int x, *py, **ppz){**ppz +=1 ； *py +=2 ；x +=3; return x+*py+**ppz;}变量 a 是一个指向 b 的指针；变量 b 是一个指向 c 的指针，而 c 是一个当前值为 4 的整数变量。

如果我们调用 f(c,b,a), 返回值是什么？答： x 是传值 ,而 b 和 c 是传地址方式；由函数定义可以得到： b=c,a=b, 而**a=**a+1=c+1=5 = c=5; *b=*b+2=c+2=7 =c=7,**a=7;c=c+3=4+3=7所以调用 f(c,b,a) 返回值是 7+7+ 7=21练习7.3.2 ：假设我们使用显示表来实现下图中的函数。

请给出对fib0 （1）的第一次调用即将返回时的显示表。

同时指明那时在栈中的各种活动记录中保存的显示表条目答：结果如下第八章练习 8.2.1 ：假设所有的变量都存放在内存中，为下面的三地址语句生成代码：5）下面的两个语句序列x=b*cy=a+x答：生成的代码如下练习 8.5.1 ：为下面的基本块构造构造dagd=b*ce=a+bb=b*ca=e-d答： dag 如下练习 8.6.1 ：为下面的每个 c 语言赋值语句生成三地址代码1)x=a+b*c答：生成的三地址代码如下【篇二：编译原理龙书第二版第4章】.1：考虑上下文无关文法： s-s s +|s s *|a 以及串 aa + a* (1) 给出这个串的一个最左推导 s - s s * - s s + s * - a s + s * - a a + s * - aa+a*(3)给出这个串的一棵语法分析树习题 4.3.1 ：下面是一个只包含符号 a 和 b 的正则表达式的文法。

它使用 +替代表示并运算的符号 |，以避免和文法中作为元符号使用的竖线相混淆： rexpr? rexpr + rterm | rterm rterm?rterm rfactor |rfactor rfactor? rfactor * | rprimary rprimary?a | b 1)对这个文法提取公因子2)提取公因子的变换使这个文法适用于自顶向下的语法分析技术吗？3)提取公因子之后，原文法中消除左递归 4) 得到的文法适用于自顶向下的语法分析吗？解1)提取左公因子之后的文法变为rexpr? rexpr + rterm | rterm rterm?rterm rfactor |rfactor rfactor? rfactor * | rprimary rprimary?a | b2)不可以，文法中存在左递归，而自顶向下技术不适合左递归文法3)消除左递归后的文法rexpr - rterm rexpr’rexpr rterm ’-+ rterm rexpr’|? rterm- rfactor rterm’ rterm-rfactor’’ |? rfactor- rprimay rfactor’ rfactor-*rfactor’’ |? rprimary- a| b4)该文法无左递归，适合于自顶向下的语法分析习题 4.4.1 ：为下面的每一个文法设计一个预测分析器，并给出预测分析表。

编译原理书籍
编译原理是计算机科学领域的重要课题之一。

它研究的是如何将高级程序语言代码转换为可执行的机器语言代码的过程。

编译原理的研究对于优化程序性能、提高程序可靠性以及实现新的语言特性都具有重要意义。

在编译原理的学习过程中，一本好的教材是必不可少的辅助工具。

以下是一些值得推荐的编译原理教材：
1. "编译原理与技术"，作者：王生原
2. "编译原理"，作者：周伯华
3. "现代编译原理"，作者：Andrew W. Appel
4. "编译原理与实践"，作者：龙书
5. "高级编译器设计与实现"，作者：Steven Muchnick
这些教材涵盖了编译原理的基本概念、各个阶段的具体实现、相应的算法和数据结构等内容。

通过系统地学习这些教材，读者可以掌握编译原理的核心知识，并且能够应用于实际的编译工作中。

除了教材之外，还可以参考相关的学术论文、技术博客和开源项目，以获取更深入的理解和实战经验。

编译原理是一个广阔而有挑战性的领域，需要不断学习和实践才能掌握其中的精髓。

愿你在学习编译原理的过程中能够获得丰富的知识和宝贵的经验！。

编译原理龙书
编译原理是计算机科学的一个分支，研究编程语言是如何被转化为机器语言的过程。

它涉及到词法分析、语法分析、语义分析和代码生成等内容。

词法分析是将代码中的字符串序列转化为一个个词素（token），如标识符、关键字、操作符等。

通过建立一个有
限状态自动机来识别各个词素。

语法分析则是将词法分析得到的词素序列转化为一个语法树。

语法树可以表示出代码的结构，用来检查代码的语法正确性，并为后续的处理提供便利。

语义分析用于检查代码是否符合语义规则。

它检查标识符的声明和使用是否一致，类型是否匹配等。

此外，语义分析还会进行一些优化，如常量折叠和无用代码删除。

最后阶段是代码生成，将语法树转化为目标机器的机器代码。

在代码生成中，会进行一些优化，如寄存器分配和指令调度，以提高代码的执行效率。

编译原理的研究对于理解计算机的底层原理、开发编程语言和编写优化器等方面都具有重要意义。

通过学习编译原理，可以更好地理解程序的执行过程，并能够编写出高效、可靠的代码。

第四章部分习题解答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⇒(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)) ⇒(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, a)))e)该文法产生的语言是什么解：设该文法产生语言（符号串集合）L，则L = { (A1, A2, …, A n) | n是任意正整数，A i=a，或A i∈L，i是1～n之间的整数}（Aho）4.2考虑文法S→aSbS | bSaS | εa)为句子构造两个不同的最左推导，以证明它是二义性的S⇒aSbS⇒abS⇒abaSbS⇒ababS⇒ababS⇒aSbS⇒abSaSbS⇒abaSbS⇒ababS⇒ababb)构造abab对应的最右推导S⇒aSbS⇒aSbaSbS⇒aSbaSb⇒aSbab⇒ababS⇒aSbS⇒aSb⇒abSaSb⇒abSab⇒ababc)构造abab对应语法树d)该文法产生什么样的语言？解：生成的语言：a、b个数相等的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的推导命题都成立考虑步数等于n 的推导，其开始推导步骤必为以下情况之一bexpr⇒bexpr or btermbexpr⇒btermbterm⇒bterm and bfactorbexpr⇒bfactorbfactor⇒not bfactorbfactor⇒ ( bexpr )而后继推导的步数显然<n，因此由归纳假设，第二步句型中的NT推导出的串均为布尔表达式，这些布尔表达式经过or、and、not运算或加括号，得到的仍是布尔表达式因此命题一得证。