编译原理总复习

1、总复习总复习编译原理编译原理（一）（一） 基本概念题：基本概念题：一、一、编译程序的概念编译程序的概念 编译程序是现代计算机系统的基本组成部分之一。编译程序是现代计算机系统的基本组成部分之一。简而言之简而言之, 编译程序编译程序就是一种语言翻译程序。就是一种语言翻译程序。所谓翻所谓翻译程序，是指这样一个程序，它能将高级程序设计语译程序，是指这样一个程序，它能将高级程序设计语言程序翻译成逻辑等价的低级语言言程序翻译成逻辑等价的低级语言( (汇编语言汇编语言, ,机器语机器语言言) ) 程序。程序。编译程序一般由词法分析程序、语法分析编译程序一般由词法分析程序、语法分析程序、语义分析程序、中间代码

2、生成程序、目标代码程序、语义分析程序、中间代码生成程序、目标代码生成程序、代码优化程序、表格管理程序和出错处理生成程序、代码优化程序、表格管理程序和出错处理程序等成分构成。程序等成分构成。 一个编译软件，实际涉及三种语言：源语言、一个编译软件，实际涉及三种语言：源语言、目标语言、实现语言。目标语言、实现语言。 源语言：源语言：Source Language 目标语言：目标语言：Target or Object Language 实现语言：实现语言：Implementation L 常常使用常常使用T型图来表示的一个编译器涉及的三个型图来表示的一个编译器涉及的三个语言之间的关系。语言之间的关系。

3、二、请解释编译程序的前端和后端的概念，试问前端二、请解释编译程序的前端和后端的概念，试问前端通常包括那些阶段，后端包括那些阶段？通常包括那些阶段，后端包括那些阶段？ 编译程序的前端只依赖于源语言，由几乎独立于编译程序的前端只依赖于源语言，由几乎独立于目标机器的阶段或阶段的一部分组成。编译程序的前目标机器的阶段或阶段的一部分组成。编译程序的前端通常包括词法分析程序、语法分析程序、语义分析端通常包括词法分析程序、语法分析程序、语义分析程序、中间代码生成程序及相关的表格管理程序和出程序、中间代码生成程序及相关的表格管理程序和出错处理程序。编译程序的后端是指编译器中依赖于目错处理程序。编译程序的后端是

4、指编译器中依赖于目标机器的部分标机器的部分,它们一般独立于源语言，而与中间代它们一般独立于源语言，而与中间代码有关。通常包括目标代码生成程序、代码优化程序码有关。通常包括目标代码生成程序、代码优化程序以及相关的表格管理程序和出错处理程序。以及相关的表格管理程序和出错处理程序。三、三、语言的语法描述语言的语法描述 语言的语法描述方法有其三，用自然语言描述语言的语法描述方法有其三，用自然语言描述语言的语法，用语法图描述语言的语法和用巴科斯语言的语法，用语法图描述语言的语法和用巴科斯-瑙尔范式及扩充的巴科斯瑙尔范式及扩充的巴科斯-瑙尔范式瑙尔范式 (EBNF)两种两种形式给出语言的语法描述。形式给出

5、语言的语法描述。 用语法图描述语言的语法与用语法图描述语言的语法与EBNF描述相比较：描述相比较： 语法图描述：语法图描述： 直观，易读，易写。直观，易读，易写。 EBNF表示：形式化强，易机器识别。表示：形式化强，易机器识别。四、四、阐明语法的一个工具是文法，这是形式语言理阐明语法的一个工具是文法，这是形式语言理论的基本概念之一。当我们表述一种语言时，无非论的基本概念之一。当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲

6、，存在着如何给出它的有穷有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。事实上，使用文法作为工具，不仅为表示的问题。事实上，使用文法作为工具，不仅为了严格地定义句子的结构，也是为了用适当条数的了严格地定义句子的结构，也是为了用适当条数的规则把语言的全部句子描述出来，是以有穷的集合规则把语言的全部句子描述出来，是以有穷的集合刻划无穷的集合的工具。刻划无穷的集合的工具。 在形式上语言是符号串的集合。在形式上语言是符号串的集合。符号串是由字符号串是由字母表中的符号所组成的任何有穷序列。母表中的符号所组成的任何有穷序列。符号串的运符号串的运算和符号串集合的运算。和、算和符号串集合的运算。和、乘

7、积、乘积、方幂与闭包。方幂与闭包。五、请写出五、请写出Chomcky关于文法的定义。关于文法的定义。 Chomcky文法的定义：文法文法的定义：文法G定义为四元组定义为四元组,记记为为: G=(VN,VT,P,S)其中：其中：VN 非空有限的非终结符号集非空有限的非终结符号集 VT 非空有限的终结符号集非空有限的终结符号集 P 产生式集产生式集 S 开始符号开始符号/识别符号识别符号 S VN 六、例：已知文法：六、例：已知文法： EX|E+X XY|X*Y Y（E）|i 请判定该文法是那类文法？请判定该文法是那类文法？ 答：根据答：根据 Chomcky文法的定义，该文法是文法的定义，该文法是

8、2类文类文法，即上下文无关文法。法，即上下文无关文法。七、七、*请说明有关句型、句子、句柄概念？请说明有关句型、句子、句柄概念？ 答：设答：设GS是一文法，如果符号串是一文法，如果符号串x是从文法的是从文法的识别符号推导出来的，则称符号串识别符号推导出来的，则称符号串x是文法是文法GS的句的句型。若符号串型。若符号串x还满足仅由终结符号组成的条件，则还满足仅由终结符号组成的条件，则称称x为为GS的句子。一个句型的最左直接短语称为该的句子。一个句型的最左直接短语称为该句型的句柄。句型的句柄。八、请说明有关规范句型的概念？八、请说明有关规范句型的概念？ 答：最右推导，即推导的每一步都是替换当前答：

9、最右推导，即推导的每一步都是替换当前句型最右边的非终结符，被称为规范推导，由规范句型最右边的非终结符，被称为规范推导，由规范推导得到的句型称为规范句型。推导得到的句型称为规范句型。九、简单说明词法分析程序的主要任务。九、简单说明词法分析程序的主要任务。 答：词法分析程序是编译程序的一个构成成分，答：词法分析程序是编译程序的一个构成成分，它的主要任务是扫描源程序，按构词规则识别单词，它的主要任务是扫描源程序，按构词规则识别单词，并报告发现的词法错误。并报告发现的词法错误。十、程序设计语言的单词符号一般可分成下列十、程序设计语言的单词符号一般可分成下列5种：种： 保留字，也称关键字。保留字，也称关

10、键字。 标识符，用来表示各种名字，如常量名、变标识符，用来表示各种名字，如常量名、变量名和过程名等。量名和过程名等。 常数，各种类型的常数，如常数，各种类型的常数，如25，3.1415，TRUE和和“ABC”等。等。 运算符，如运算符，如+，*，=等。等。 界符，如逗点，分号，括号等。界符，如逗点，分号，括号等。十一、程序设计语言的单词可用正规文法描述。正十一、程序设计语言的单词可用正规文法描述。正规文法是右线性文法规文法是右线性文法,文法文法G=(VN,VT,P,S), P中的每中的每一条规则形为一条规则形为AaB或或Aa,其中其中A,BVN ,aVT 。正规文法所描述的是正规文法所描述的是

11、VT上的正规集（正规文法描述上的正规集（正规文法描述的语言的句子的集合）。正规式也称正则表达式，的语言的句子的集合）。正规式也称正则表达式，也是表示正规集的数学工具。正规式说明单词的模也是表示正规集的数学工具。正规式说明单词的模式，也就是说明单词组成的形式规则，正规集则是式，也就是说明单词组成的形式规则，正规集则是满足这些规则的单词的集合。满足这些规则的单词的集合。十二、十二、*确定的有穷自动机也称有限自动机，它是作确定的有穷自动机也称有限自动机，它是作为一种识别装置，它能准确地识别正规集，即识别为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合。具正规文法所

12、定义的语言和正规式所表示的集合。具体而言，一个确定的有穷自动机可以用一个五元组体而言，一个确定的有穷自动机可以用一个五元组表示，即表示，即M=(K,f, S,Z)。K是一个有穷状态集，是一个有穷状态集，是一个有穷字母表，是一个有穷字母表，f是转换函数，是转换函数，S是初态，是初态，Z是一是一个终态集。个终态集。 十三、确定的有穷自动机十三、确定的有穷自动机DFA和不确定的有穷自动机和不确定的有穷自动机NFA 的概念，对每个的概念，对每个NFA N一定存在一个一定存在一个DFA M，使得使得L(M)=L(N)。对每个。对每个NFA N存在着与之等价的存在着与之等价的DFA M。与某一。与某一NF

13、A等价的等价的DFA不唯一。不唯一。 -闭包和闭包和子集法算法将子集法算法将NFA转换成接受同样的语言的转换成接受同样的语言的DFA。十四、语法分析是编译程序的核心部分。语法分析的十四、语法分析是编译程序的核心部分。语法分析的作用是识别由词法分析给出的单词符号序列是否是给作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子定文法的正确句子(程序程序)，目前语法分析常用的方法，目前语法分析常用的方法有自顶向下（自上而下）分析和自底向上（自下而上）有自顶向下（自上而下）分析和自底向上（自下而上）分析两大类。分析两大类。 十五、自顶向下分析法也称面向目标的分析方法，十五、自顶向下分析法也称

14、面向目标的分析方法，也就是从文法的开始符号出发企图推导出与输入的也就是从文法的开始符号出发企图推导出与输入的单词串完全相匹配的句子，若输入串是给定文法的单词串完全相匹配的句子，若输入串是给定文法的句子，则必能推出，反之必然出错。自顶向下分析句子，则必能推出，反之必然出错。自顶向下分析法又可分为确定的和不确定的两种，确定的分析方法又可分为确定的和不确定的两种，确定的分析方法需对文法有一定的限制，但由于实现方法简单、法需对文法有一定的限制，但由于实现方法简单、直观，便于手工构造或自动生成语法分析器，因而直观，便于手工构造或自动生成语法分析器，因而仍是目前常用的方法之一。不确定的方法即带回溯仍是目前

15、常用的方法之一。不确定的方法即带回溯的分析方法，这种方法实际上是一种穷举的试探方的分析方法，这种方法实际上是一种穷举的试探方法，因此效率低，代价高，因而极少使用。法，因此效率低，代价高，因而极少使用。在确定在确定的自顶向下语法分析中用的是最左推导。的自顶向下语法分析中用的是最左推导。 十六、请说明有关预测符号集的概念？十六、请说明有关预测符号集的概念？ 答：产生式答：产生式A预测符号集表示：在确定的自预测符号集表示：在确定的自上而下的语法分析过程中，当需要替换的非终结符是上而下的语法分析过程中，当需要替换的非终结符是A时，而当前需要匹配的终结符属于产生式时，而当前需要匹配的终结符属于产生式A预

16、测预测符号集中的符号，则能够采用该产生式进行推导。当符号集中的符号，则能够采用该产生式进行推导。当不能推出不能推出时，产生式时，产生式A预测符号集是预测符号集是的首符号的首符号集；当集；当能推出能推出时，产生式时，产生式A预测符号集是预测符号集是的首的首符号集与符号集与A的后跟符号集的并集，但是不包括的后跟符号集的并集，但是不包括。十七、十七、LL(1)文法：文法： LL(1)文法的含义是：第一个文法的含义是：第一个L表明自顶向下分析是从左向右扫描输入串，第二表明自顶向下分析是从左向右扫描输入串，第二个个L表明分析过程中将用最左推导，表明分析过程中将用最左推导，1表明只需向表明只需向右看一个符

17、号便可决定选择哪个产生式或规则进右看一个符号便可决定选择哪个产生式或规则进行推导。行推导。LL（1）方法是）方法是LL（K）方法的特例。）方法的特例。一个上下文无关文法是一个上下文无关文法是LL(1)文法的充分必要条件文法的充分必要条件是：对每个非终结符是：对每个非终结符A的两个不同产生式，的两个不同产生式，A, A,满足满足SELECT(A)SELECT(A)= 其中其中，不同时能不同时能 十八、预测分析方法是自顶向下分析的方法，一个预十八、预测分析方法是自顶向下分析的方法，一个预测分析器是由三个部分组成。测分析器是由三个部分组成。 预测分析程序预测分析程序(总控程序总控程序) 先进后出栈先

18、进后出栈(stack) 预测分析表：预测分析表以终结符号和预测分析表：预测分析表以终结符号和“#”号作为列标志，以非终结符号作为行标志，对每个号作为列标志，以非终结符号作为行标志，对每个终结符号或终结符号或“#”号用号用a表示，若表示，若aSELECT(A),则把则把A放入放入MA,a中中,把所有无定义的把所有无定义的MA,a标标上出错标记。这就构成了预测分析表。上出错标记。这就构成了预测分析表。 要求学员能够对一个给定的文法判断是否是要求学员能够对一个给定的文法判断是否是LL(1)文法；能构造预测分析表；能用预测分析方文法；能构造预测分析表；能用预测分析方法判断给定的输入符号串是否是该文法的

19、句子。法判断给定的输入符号串是否是该文法的句子。 （基本要求）（基本要求） 十九、某些含有左递归和左公共因子的文法在通过十九、某些含有左递归和左公共因子的文法在通过等价变换把它们消除以后可能变为等价变换把它们消除以后可能变为LL(1)文法，但需文法，但需要用要用LL(1)文法的定义判别。文法的定义判别。 （基本要求）（基本要求） 二十、自底向上分析法，也称移进二十、自底向上分析法，也称移进-归约分析法，或归约分析法，或自下而上分析。自底向上分析是自顶向下分析的逆自下而上分析。自底向上分析是自顶向下分析的逆过程过程,它是从待分析的句子出发逆向使用产生式逐步它是从待分析的句子出发逆向使用产生式逐步

20、归约的过程。从语法分析树的角度讲，就是从语法归约的过程。从语法分析树的角度讲，就是从语法树的叶结点（句子）出发自下而上逐层构造语法树，树的叶结点（句子）出发自下而上逐层构造语法树，每一层对应归约过程中的一个句型。每一层对应归约过程中的一个句型。 常用的自底向上语法分析方法有优先分析方法和常用的自底向上语法分析方法有优先分析方法和LR方法。优先分析方法又分为简单优先方法和算符方法。优先分析方法又分为简单优先方法和算符优先方法；优先方法；LR方法也有多种。方法也有多种。二十一、简单优先分析法的基本思想是：通过优先关二十一、简单优先分析法的基本思想是：通过优先关系的定义，确定了在系的定义，确定了在V

21、TVVN N中任何二个符号之间的优中任何二个符号之间的优先关系；（两个符号之间最多只有一种关系成立），先关系；（两个符号之间最多只有一种关系成立），对于当前的句型，通过从右至左的扫描，利用优先关对于当前的句型，通过从右至左的扫描，利用优先关系，先找到句柄的尾符号，然后找到句柄的头符号，系，先找到句柄的尾符号，然后找到句柄的头符号，从而找到了当前句型中应该归约的句柄。通过归约，从而找到了当前句型中应该归约的句柄。通过归约，构造一层语法树；如此反复，直到归约到文法的开始构造一层语法树；如此反复，直到归约到文法的开始符号。符号。二十二、算符优先分析的基本思想是只规定算符二十二、算符优先分析的基本思想

22、是只规定算符(广广义为终结符义为终结符)之间的优先关系，也就是只考虑终结符之间的优先关系，也就是只考虑终结符之间的优先关系，不考虑非终结符之间的优先关系。之间的优先关系，不考虑非终结符之间的优先关系。它是根据算符（终结符）之间的优先关系确定句型它是根据算符（终结符）之间的优先关系确定句型中归约子串的方法。它采用的不是规范归约，因此中归约子串的方法。它采用的不是规范归约，因此它的归约子串并不是规范归约意义上的句柄，为了它的归约子串并不是规范归约意义上的句柄，为了和规范归约区分开来称之为最左素短语，也就是说，和规范归约区分开来称之为最左素短语，也就是说，在算符优先分析法每步自底向上归约时，识别和归

23、在算符优先分析法每步自底向上归约时，识别和归约的是当前的最左素短语。约的是当前的最左素短语。二十三、二十三、LR分析法的分析过程是一种规范归约过分析法的分析过程是一种规范归约过程，规范归约是规范推导的逆过程。规范推导是最程，规范归约是规范推导的逆过程。规范推导是最右推导，规范归约是其逆过程，则是最左归约。右推导，规范归约是其逆过程，则是最左归约。 LR分析法的可归约串是当前句型的句柄，即最左分析法的可归约串是当前句型的句柄，即最左直接短语。直接短语。 对于大多数用无二义性上下文无关文法描述的对于大多数用无二义性上下文无关文法描述的语言都可以用相应的语言都可以用相应的LR分析器进行识别，而且这分

24、析器进行识别，而且这种方法还种方法还具有分析速度快，能准确、及时地指出出具有分析速度快，能准确、及时地指出出错位置错位置。二十四、一个二十四、一个LR分析器由分析器由3个部分组成：个部分组成：(1) 总控程序，也可以称为驱动程序。对所有的总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。分析器总控程序都是相同的。(2) 分析表或分析函数分析表或分析函数,分析表又可分为动作表分析表又可分为动作表(ACTION)和状态转换和状态转换(GOTO)表两个部分，它们都表两个部分，它们都可用二维数组表示。可用二维数组表示。(3) 分析栈，包括文法符号栈和相应的状态栈，分析栈，包括文法符号

25、栈和相应的状态栈，它们均是先进后出栈。它们均是先进后出栈。 分析器的动作就是由栈顶状态和当前输入符号分析器的动作就是由栈顶状态和当前输入符号所决定所决定(LR(0)分析器不需向前查看输入符号分析器不需向前查看输入符号)。二十五、拓广文法：在原文法二十五、拓广文法：在原文法G中增加一个产生式中增加一个产生式S，S是原文法是原文法G的开始符号，所得到的新文法的开始符号，所得到的新文法称为称为原文法原文法G的拓广文法。而的拓广文法。而S为拓广后文法为拓广后文法G的的开始符号。开始符号。 活前缀：在规范句型中，不包括该句型句柄右活前缀：在规范句型中，不包括该句型句柄右边符号的前缀称之为活前缀。边符号的

26、前缀称之为活前缀。 可归前缀：活前缀与句柄有可归前缀：活前缀与句柄有3种关系，：活前缀种关系，：活前缀不含句柄的任何符号；：活前缀含有句柄的部分不含句柄的任何符号；：活前缀含有句柄的部分符号；：活前缀包含句柄的全部符号。包含句柄符号；：活前缀包含句柄的全部符号。包含句柄的全部符号的活前缀称之为可归前缀。的全部符号的活前缀称之为可归前缀。 LR(0)项目：在文法项目：在文法G中每个产生式的右部适当中每个产生式的右部适当位置添加一个圆点构成项目。项目分为位置添加一个圆点构成项目。项目分为4种：移进种：移进项目、待约项目、归约项目、接受项目。项目、待约项目、归约项目、接受项目。二十六、把拓广文法的第

27、一个项目二十六、把拓广文法的第一个项目SS作为初作为初态集的核，通过求核的闭包和转换函数，求出态集的核，通过求核的闭包和转换函数，求出LR(0)项目集规范族，再由转换函数建立状态之间的连接项目集规范族，再由转换函数建立状态之间的连接关系得到识别活前缀的关系得到识别活前缀的DFA；由识别活前缀的；由识别活前缀的DFA构造构造LR（0）分析表；设计总控程序，利用分析表）分析表；设计总控程序，利用分析表和分析栈对服从和分析栈对服从 LR（0）文法的语言进行语法分析。）文法的语言进行语法分析。 （基本要求）（基本要求） LR(0)项目集规范族的方法是通过定义和构造项目集规范族的方法是通过定义和构造拓广

28、文法的项目拓广文法的项目I的闭包（的闭包（closure（I），和转换），和转换函数（函数（Go（I，X），从而直接构造出识别文法活），从而直接构造出识别文法活前缀的前缀的DFA。要求学生能够根据文法，采用。要求学生能够根据文法，采用LR(0)项目集规范族的方法，直接构造出项目集规范族的方法，直接构造出LR(0)分析表。分析表。 LR(0)文法的限制是一个文法的文法的限制是一个文法的LR(0)项目集规项目集规范族中不存在移进范族中不存在移进-归约冲突和归约归约冲突和归约-归约冲突。归约冲突。二十七、二十七、简单说明语法制导翻译的概念？简单说明语法制导翻译的概念？答：答：一句话解释：语法分析控制

29、引导下的语义翻译。语义翻一句话解释：语法分析控制引导下的语义翻译。语义翻译即是把源程序的语义，用另一种语言正确的表示出来。译即是把源程序的语义，用另一种语言正确的表示出来。具具体步骤是：体步骤是：1、根据描述源程序的语法的文法，、根据描述源程序的语法的文法，对对源程序源程序进行进行语法分析，语法分析，构造一棵与源程序匹配的语法树；构造一棵与源程序匹配的语法树；2、按照语法分析的顺序，执行、按照语法分析的顺序，执行相应相应产生式后面的语义子程序产生式后面的语义子程序，得到翻译结果，得到翻译结果，完成源程序的完成源程序的语法制导翻译。语法制导翻译。二十八、语法分析与语义翻译有什么关系呢？二十八、语

30、法分析与语义翻译有什么关系呢？ 它们之间的联系就在语法树。语法分析就是通过采用自它们之间的联系就在语法树。语法分析就是通过采用自上而下的方法，或者采用自底向上的方法构造一棵与输入符上而下的方法，或者采用自底向上的方法构造一棵与输入符号串匹配的语法树。从而分析判断源程序在形式上是否存在号串匹配的语法树。从而分析判断源程序在形式上是否存在语法错误，是否服从程序设计语言的语法规则。而语义与语语法错误，是否服从程序设计语言的语法规则。而语义与语法树有关。我们在讨论二义性文法时，就是用语法树说明的。法树有关。我们在讨论二义性文法时，就是用语法树说明的。二义性文法的定义如下：如果对于某文法的一个句子存在两

31、二义性文法的定义如下：如果对于某文法的一个句子存在两棵不同的语法树，则该句子是二义性的。而该文法是二义性棵不同的语法树，则该句子是二义性的。而该文法是二义性文法。文法。二十九、描述语义的工具什么？描述语义的工具是属性文法。二十九、描述语义的工具什么？描述语义的工具是属性文法。属性文法建立了每个文法符号的属性。属性又分为继承属性和属性文法建立了每个文法符号的属性。属性又分为继承属性和综合属性。它们的区分，不在属性本身，而在于属性的表示方综合属性。它们的区分，不在属性本身，而在于属性的表示方式。一个文法符号的属性可以用其它文法符号的属性表示。简式。一个文法符号的属性可以用其它文法符号的属性表示。简

32、单说：如果这种表示与继承有关则称之为继承属性；而如果表单说：如果这种表示与继承有关则称之为继承属性；而如果表示与继承无关的则称之为综合属性。一个产生式中各个文法符示与继承无关的则称之为综合属性。一个产生式中各个文法符号属性之间的关系实际上表达了该产生式的语义。号属性之间的关系实际上表达了该产生式的语义。三十、编译中的语义处理是指两个功能：第一，审查每个语法三十、编译中的语义处理是指两个功能：第一，审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义。结构的静态语义，即验证语法结构合法的程序是否真正有意义。有时把这个工作称为静态语义分析或静态审查。第二，如果静有时把这个工作称为静态

33、语义分析或静态审查。第二，如果静态语义正确，语义处理则要执行真正的翻译，即，或者将源程态语义正确，语义处理则要执行真正的翻译，即，或者将源程序翻译成程序的一种中间表示形式（中间代码），或者将源程序翻译成程序的一种中间表示形式（中间代码），或者将源程序翻译成目标代码。语义处理又称为语义动作，它是依靠执行序翻译成目标代码。语义处理又称为语义动作，它是依靠执行语义子程序完成的。语义子程序完成的。三十一、静态语义分析通常包括：三十一、静态语义分析通常包括： 类型检查。类型检查。 控制流检查。控制流检查。 一致性检查。一致性检查。 相关名字检查。相关名字检查。 名字的作用域分析名字的作用域分析 。在语法

34、分析过程中，随着分析的。在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译的办法称作语法语义规则描述的语义动作）进行翻译的办法称作语法制导翻译。制导翻译。三十二、编译程序所使用的中间代码有多种形式。常三十二、编译程序所使用的中间代码有多种形式。常见的有逆波兰记号、三元式、四元式和树形表示。见的有逆波兰记号、三元式、四元式和树形表示。三十三、符号表的作用：三十三、符号表的作用：收集保存符号属性收集保存符号属性 上下文语义的合法性检查的依据上下文语义的合法性检查的依据 作为目标代码生成阶段地址分配

35、的依据。作为目标代码生成阶段地址分配的依据。三十四、代码优化：某些编译程序在中间代码或目三十四、代码优化：某些编译程序在中间代码或目标代码生成之后要对生成的代码进行优化。所谓优标代码生成之后要对生成的代码进行优化。所谓优化，实质上是对代码进行等价变换，使得变换后的化，实质上是对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行代码运行结果与变换前代码运行结果相同，而运行速度加大或占用存储空间少，或两者都有。编译过速度加大或占用存储空间少，或两者都有。编译过程中可进行的优化可按阶段划分：优化可在编译的程中可进行的优化可按阶段划分：优化可在编译的不同阶段进行，分为中间代码一

36、级和目标代码一级不同阶段进行，分为中间代码一级和目标代码一级的优化。可按优化涉及的程序范围划分：对同一阶的优化。可按优化涉及的程序范围划分：对同一阶段，分为局部优化段，分为局部优化,循环优化和全局优化。最常用的循环优化和全局优化。最常用的代码优化技术有删除多余运算，循环不变代码外提，代码优化技术有删除多余运算，循环不变代码外提，强度削弱，变换循环控制条件，合并已知量与复写强度削弱，变换循环控制条件，合并已知量与复写传播，以及删除无用赋值等等。传播，以及删除无用赋值等等。 三十五、代码生成器是把某种高级程序设计语言编写三十五、代码生成器是把某种高级程序设计语言编写的程序经过语法、语义分析，或再经

37、过优化后的中间的程序经过语法、语义分析，或再经过优化后的中间代码作为输入，将其转换成特定机器的机器语言或汇代码作为输入，将其转换成特定机器的机器语言或汇编语言作为输出，这样的转换程序称为代码生成器。编语言作为输出，这样的转换程序称为代码生成器。 代码生成器的设计要着重考虑目标代码的质量问代码生成器的设计要着重考虑目标代码的质量问题。衡量目标代码的质量主要从占用空间和执行效率题。衡量目标代码的质量主要从占用空间和执行效率两个方面综合考虑。提高目标代码的运行效率两个方面综合考虑。提高目标代码的运行效率,需要讨需要讨论在一个基本块内如何充分利用寄存器和根据寄存器论在一个基本块内如何充分利用寄存器和根

38、据寄存器分配的原则给出寄存器分配的一般算法。分配的原则给出寄存器分配的一般算法。 一个高级程序设计语言编译程序的代码生成部分一个高级程序设计语言编译程序的代码生成部分在编译中起着关键性的作用，而它又与计算机硬件的在编译中起着关键性的作用，而它又与计算机硬件的结构乃致细节紧密相关，这导致了代码生成的可移植结构乃致细节紧密相关，这导致了代码生成的可移植性及自动生成算法的研究，无论在理论上还是在实践性及自动生成算法的研究，无论在理论上还是在实践上都相当困难。上都相当困难。 （二）（二） 应用题应用题1、文法、文法G（S）的产生式为：）的产生式为：SaAS,ASbA,AaA,Ab,Sa,请写出该文法请

39、写出该文法的非终结符号集、终结符号集及文法的开始符号，的非终结符号集、终结符号集及文法的开始符号，根据文法画出句型根据文法画出句型aSbSbaAa的语法树，并且指出的语法树，并且指出该句型的短语、直接短语和句柄？该句型的短语、直接短语和句柄？答：该文法的非终结符号集是答：该文法的非终结符号集是S,A、终结符号集是终结符号集是a,b及及文法的开始符号是文法的开始符号是S 句型句型aSbSbaAa的语法树为：的语法树为： 该句型的短语为：该句型的短语为：aA,SbaA, SbSbaA, aSbSbaAa,a直接短语为：直接短语为：aA, a 句柄为：句柄为：aA2、正规式为：、正规式为：b(ab)

40、*|bb)ba，请根据所列正规式，请根据所列正规式，画出对应的画出对应的NFA的状态转换图，并且将的状态转换图，并且将NFA确定化，确定化，画出对应的画出对应的DFA的状态转换图。的状态转换图。答：（答：（1）正规式为：正规式为：b(ab)*|bb)ba 对应的对应的NFA的的状态转换图如下：状态转换图如下：（2）利用转换矩阵将以上）利用转换矩阵将以上NFA确定化，转换矩阵如确定化，转换矩阵如下：下： （3）将状态重新编号，）将状态重新编号，NFA确定化后，生成确定化后，生成DFA状状态转换矩阵如下：态转换矩阵如下： （4）DFA状态转换图如下：状态转换图如下： 3、请根据文法、请根据文法G写出所有产生式的预测符号集，并写出所有产生式的预测符号集，并且判定该文法是否是且判定该文法是否是LL(1)文法，如