本章介绍编译程序的第二个阶段语法分析的第二种设计方法和实现原理即自下而上分析的原理，包括一些基本概念、LR分析法。 （二）本章重点
自下而上分析的思想，LR分析器逻辑结构和功能，LR(0)文法及其分析、SLR(1)文法及其分析、LR(1)、LALR(1) 文法及其分析。 （三）本章难点
句柄的定义，LR项目及活前缀识别自动机，四种LR文法的差别。 （四）本章考点
基本概念的定义（短语、直接短语、句柄、规范归约等）。 LR（0）、SLR（1）分析。 （五）学习指导
理解有效项目的基本概念；掌握LR(0)、SLR（1）文法的判断及LR(0)、SLR（1）分析表的构造与分析方法。自下而上分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的开始符号，从输入串的语法树上直观地看就是沿着语法树的底部向上分析归约，最终能到达根结点的就认为当前的输入串能被接受。大部分现代的编译器都采用LR分析作为语法分析的方式。因此本章的学习重点是学习如何构造LR分析表。OPG分析可以作为自下而上分析算法的切入点要求重点掌握。 附训练试题： 1、对于文法G[S]
S→ ( L) | aS |a L→ L, S | S
（1）画出句型( S ,(a))的语法树
（2）写出上述句型的所有短语， 直接短语， 句柄. 2、 设有文法G[S]: S→L=R S →R L →*R L →i R →L
为构造拓广文法，增加新的非终结符S’，得到规则S’ →S，则： closure ( { [S’ →.S, # ]} )=________ 3、设文法G(S’)
S’→A A →aA | b
构造识别文法G(S’)的所有活前缀的DFA. 4、求文法 （1） S’→A （2） A →aA （3）A → b LR(0)分析表：
5、设文法G，试构造G的LR(0)分析表 G: 1) S→CC 2) C →cC 3) C →d
6、对于文法A→aA|a构造SLR(1)分析表 7、设有文法G(S’)为
1） S’→S 2) S →L=R 3) S →R 4) L →*R 5) L →i 6) R →L
构造文法G(S’)的LR(1)分析表： 8、设有文法G(A） 1) A’→ A 2) A →BB 3) B →aB 4) B → b
构造LALR(1)分析表
第八章语法制导翻译和中间代码的生成课外训练
（一）自学内容
本章内容围绕语义分析展开，主要介绍属性文法，语法制导翻译与翻译模式的计算，抽象语法树、带注释的语法树。语义分析及中间代码生成的设计原理和实现方法，包括语法制导翻译的具体实现、中间代码的形式，可执行语句和说明语句的语法制导翻译方法。 （二）本章重点
属性文法、后缀式和四元式中间代码表示，简单算术表达式和赋值语句的翻译，布尔表达式及控制语句的翻译，数组元素的处理，过程语句的翻译。 （三）本章难点
抽象语法树，属性的作用及计算，语法制导翻译。布尔表达式的翻译，数组元素的处理。 （四）本章考点
语法制导翻译定义。中间语言表示（后缀式和三地址代码）。赋值语句的翻译。布尔表达式及控制语句的翻译。 （五）学习指导
要求理解属性的引入、两种属性的计算原则，掌握S属性的计算方法，掌握L属性翻译模式的计算（递归下降分析），继承属性计算的四种方法。本章介绍属性文法的基本概念和基于属性文法的处理方法，讨论如何在自上而下分析和自下而上分析中实现属性的计算。本章的学习重点以掌握属性文法及语法制导翻译的概念为主，分析中属性的计算作为了解。
理解语法制导翻译、语义动作的基本概念；掌握算术表达式和赋值语句到中间代码的翻译、布尔表达式和几种控制语句的目标代码结构分析和到四元式的语法制导翻译；说明语句的语法制导翻译。本章是将上一章介绍的属性文法和语法制导翻译的方法和技术应用于语义分析和中间代码的产生。本章的学习重点为：掌握各种中间代码的形式，包括后缀式、三元式、四元式等；了解常用语法结构单元的语义表达形式，包括说明语句，赋值语句，布尔表达式，控制语句，过程调用。 附训练试题：
1、在一个移入——归约的分析中采用以下的语法制导的翻译模式，在某产生式归约时，立即执行括号中的动作。
A→aB {print “0” } A→c {print “1” } B→Ab { print “2” } 当分析器输入为aacbb时，打印的字符串是
什么?
2、下列文法由开始符S产生一个二进制数，令综合属性val给出该数的值： S→L .L| L L→LB | B B→0 | 1
试设计求S.val 的属性文法，其中，已知B的综合属性，给出由B产生的二进位的结果值。如输入101。101时，输出S.val=5.625。
3、设有文法G[S]： S→(L) | a L→L , S | S
给此文法配上语义动作子程序（或者说为此文法写出一个语法制导定义），使其输出配对括号的个数，如对于句子(a, (a, a)),输出是2。 4、给出文法G[S]： S→SaA | A A→AbB | B B→cSd | e
1) 请证实 AacAbcBaAdbed 是文法的一个句型。 2）写出该句型的短语、直接短语、以及句柄。
3）为文法G[S]每个产生式写出相应的翻译语义动作，使句型AacAbcBaAdbed经该翻译方案后，输出131042521430。 5、写出下列各式的逆波兰表示
（1） -a-(b*c/(c-d) + (-b)*a) (2) -A+B*C↑ (D/E)/F 6、写出表达式
A+B*(C-D)-E/F↑G
逆波兰表示， 三元组表示， 四元组表示。 7、写出当型语句
WHILE x+y > 3 DO { a:= a+3*b;
b:= a + e – f*e } 该语句的四元式形式为： 8、写出条件语句
IF a>0 THEN x:=x+1 ELSE x:=4*( x- 1) 四元式序列
9、把语句： if A∨B 第十章 目标程序运行时存储空间组织课外训练 （一）内容 本章介绍目标程序运行时的存储组织方式，包括静态存储分配和动态存储分配。 （二）本章重点 静态存储分配，栈式存储分配，嵌套过程的存储实现。 （三）本章难点 嵌套过程的存储实现。 （四）本章考点 目标程序运行时存储空间的划分。 活动记录的内容。 嵌套过程的存储实现（DISPLAY表的使用）。 （五）学习指导 要求掌握各种存储组织形式的基本方法。在编译过程生成目标代码之前，需要把程序静态的正文和实现这个程序的动行的活动联系起来，弄清楚将来在代码运行时刻，源代码中的各种变量、常量等用户定义的量是如何存放的，如何去访问它们。本章就目标程序运行时的活动和运行环境进行讨论，主要讨论存储组织与管理，包括活动记录的建立与管理、存储器的组织与存储分配策略、非局部名称的访问。 附训练试题： 1 在编译过程中，嵌套调用的过程之间寻址问题如何解决？下面是一个示意性源程序，请给出编译期间栈式符号表的变化情况。 PROGRAM main a=10; b,c: integer; d,e: real; PROCEDURE p ( x:real ); f:real; PROCEDURE q (y:real); g=5; n:boolean; ?BEGIN ?IF e<0 THEN p (f); ?.. END; {q} BEGIN ?. Q (e); ?? END; {p} PROCEDURE t ; j: real; BEGIN ? p (e); ?? END; {t} BEGIN ? WHILE c>0 DO ?; p (d); ?? END. {main} 2 对于下面程序： Procedure p (x,y,z) ; begin y:=y+1; z:=z+x; end; {p} begin a:=2; b:=3; p (a+b , a , a) print a end. 若参数传递的方法分别为 （1）传名（2）传地址 （3） 传值。 执行时所输出的a分别是什么？ 第十一章 代码优化课外训练 （一）内容 本章介绍优化概述，局部优化，基本块的划分，基本块的DAG表示及其应用，循环优化。 （二）本章重点 基本块的划分，基本块的DAG表示及其应用。 （三）本章难点 循环优化。 （四）本章考点 优化的分类。 基本块的DAG表示及其应用。 （五）学习指导 要求了解局部优化的常用技术，基本块的DAG表示及其应用。编译程序为了最终生成更有效的目标代码，常常在中间代码生成之后对中间代码序列进行优化。本章就目标代码生成之前进行中间代码优化的技术进行讨论，主要讨论基于基本块的局部优化。 附训练试题： 1试对以下基本块B1应用DAG进行优化。 ? B1: A:=B*C ? D:=B/C ? E:=A+D ? F:=E*2 ? G:=B*C ? H:=G*G ? F:=H*G ? L:=F ? M:=L ? 并就以下两种情况分别写出优化后的四元式序列： （1）假设G、L、M在基本块后面背引用； ? （2）假设只有L在基本块后被引用。 ? 2 设有基本块 T1：＝2 T2：＝10/T T3：＝S－R T4：＝S＋R A：＝T2 * T4 B：=A T5：＝S＋R T6：＝T3 * T5 B：＝T6 (1) 画出DAG图； (2) 假设基本块出口时只有A，B还被引用，请写出优化后的四元序列