第6章 语法制导翻译技术.ppt

1、第六章语法指导的翻译技术，没有交叉，就没有皇冠。没有风雨如何看彩虹。6.1翻译语法6.2语法指导翻译6.3自上而下语法指导翻译6.4属性翻译语法6.5自上而下翻译属性语法6.6自下而上语法指导翻译，第6章语法指导翻译技术(P120)，语法指导翻译属性翻译语法及其应用，学习重点，第6章语法指导翻译技术，语义学：它是程序设计语言中每个语法成分根据语法规则的意义。语义分析的任务是分析程序的意义并做出相应的语义处理。一个源程序经过了词法分析和语法分析，这表明它在写作和语法上是正确的，但不能保证语义上是正确的。第六章语法指导翻译技术、语义分析功能、类型和操作合法性检查：检查操作合法性和操作组件类型之间的

2、一致性(或兼容性)，必要时进行相应的类型转换。例如，a b要求A和B都是算术(整数或实数)。当A和B不是同一类型时，需要进行类型转换。确定类型：确定与标识符相关联的数据对象的数据类型(有时通过词法分析完成)。识别意义：确定程序中各种组件组合的意义，并做出相应的语义处理。此时，为可执行语句生成中间代码或目标代码。第六章语法指导的翻译技术，语义分析的功能，一致性检查：在许多编程语言中，对象只需要解释一次。控制流检查：控制流语句必须转移到合法的地方。例如，在C语言中，break语句会导致控件从包含该语句的while、For或switch语句中跳出，如果没有包含该语句的语句，则会报告错误。其他语义检查

3、：比如对象的范围。第六章语法导向翻译技术及语义分析的实现，它以语法分析的输出(语法分析树或其他等效的内部中间表示)为输入，输出为中间代码甚至目标代码。一般来说，语义分析只产生中间代码，也就是说，语义分析和目标代码生成分为两个过程。第六章语法指导的翻译技术语义学通常与语境相关，只适用于口头描述，语义形式化是困难的。目前，流行的语义描述和处理方法是语法指导翻译技术。语法导向翻译技术是基于形式描述的属性翻译语法，它将语法和语义分开，但在语法分析的同时进行相应的语义工作。因此，语法指导翻译技术使语义形式化在实际应用中向前迈进了一大步。翻译语法是上下文无关语法的扩展，它是通过在描述语言的语法规则的右边添

4、加语义动作而获得的。为了区分语法符号和语义动作，在语法表示中，表示语义动作的符号用动作符号来标记。(P120)设计一个能将中缀表达翻译成波兰语后缀表达的翻译器。假设输入字符串是b*c，翻译器的输入和输出动作是：READ(a)PRINT(a)READ(b)PRINT(b)READ(*)READ(c)PRINT(*)PRINT()，其中READ表示输入操作，PRINT表示输出操作。在该序列中，如果输入符号本身直接表示读取操作，而输出操作由表示，则上述序列可以简化为：aa bb*cc*。请注意，带有：的符号字符串称为活动序列。6.1翻译语法，上面的活动序列只显示了如何具体处理中缀表达式。为了翻译所有

5、的中缀表达式，有必要研究中缀表达式语法，并考虑是否可以在适当的位置添加动作符号，以便生成包含可以翻译成波兰语后缀的表达式的活动序列。ee t f (e) et fa TT *活动序列：从翻译语法中派生出来的符号串。动作序列：从活动序列中移除所有输入序列，即由所有动作符号组成的符号串。6.1翻译语法， 示例(P122)用输入语法导出输入序列(a b)*c的过程如下： ett * ff * f(e)* f(e t)* f(f t)* f(a t)* f(a f)* f(a b)(e)* f *(e t)* f *(t t)* f *(f t)* f *(aa t)* f *(aa bb)* f *

6、(aa bb)* cc * 只要去掉活动序列中的动作符号(aa bb) * cc * 6.1翻译语法，上述例子的翻译语法可以表示为：G(E)=Vn，Vt，P，E，其中VN=e，t，f vt=a，b，c，*，(，)，*，a，b，c p=ee t，F(E)，e t，ET。在翻译语法中，如果它的动作是输出下列符号，它可以称为符号串翻译语法。 符号串翻译语法是翻译语法的一种特殊类型。语法引导翻译(P122)，示例(P122)根据前面的算术表达式翻译语法，对于输入符号串a b*c，推导出的活动序列是aa bb*cc*，其中b*c是输入序列abc*是动作序列，如果动作序列中的动作被执行，则输出序列abc*

7、将被生成，这是输入序列a b*c的翻译结果。由于该翻译结果是通过翻译语法获得的，因此称为语法引导翻译。语法指导翻译：给定一个输入序列，根据翻译语法得到翻译符号串的活动序列，从活动序列中分离出一个动作符号串，然后执行动作符号串指定的动作，得到翻译结果。6.2语法指导翻译如果给出了翻译语法，就获得了语言，语言中的每个句子都是一个活动序列。通过将每个活动序列的输入序列与动作序列配对，可以获得对偶集，然后可以获得翻译。这个对偶集被称为由给定翻译语法定义的翻译。例如，二元性(a b*c，abc*)是由算术表达式翻译的语法定义的翻译。根据语法指导翻译法，要实现语言翻译，必须根据输入语言的语法分析每个产品的

8、语义，即分析它们需要计算机完成的操作，编译子程序或程序段(称为语义子程序或语义动作)来完成这些操作，并将这些子程序或程序段的名称作为动作符号插入到每个输入语法产品右边的适当位置，从而实现语法翻译。6.3自顶向下的语法指导翻译(P123)，包括递归下降翻译和L1(1)翻译。递归下降翻译：递归下降翻译器的实现思想与递归下降分析的实现思想基本相同，要求是一样的，即不能有左递归，头符号集不能相交，只需要在适当的位置插入实现动作符号的子程序。6.3自顶向下语法引导翻译，例如(P123)算术表达式的翻译语法如下：EE T ET TT*F* TF F(E) Fii注意：输出以下符号字符串。解决方案：删除语法

9、中的左递归，修改后的语法为：ET T TF*F* F(E)| 2，处理E的递归下降翻译程序流程图，处理T的递归下降翻译程序流程图，TF * F *，处理F的递归下降翻译程序流程图，F(E)| 2，6.3自顶向下语法指导翻译，自顶向下语法指导翻译。LL(1)翻译：LL(1)翻译器的实现思想与LL(1)分析方法基本相同，要求相同，即不能有左递归，头符号集不能相交，只需在语法中适当的位置插入子程序实现动作符号，并在LL(1)分析表中添加相应的动作符号。6.3自顶向下语法指导翻译，例如(P126)，考虑以下输入语法：AaBcD Ab Bc BaA DcD Db，LL(1)输入语法分析表，并将其翻译语法

10、设置为Avawbxcydz ABBCR BAMA DCDN DSB，6.3自顶向下语法指导翻译，LL(1)翻译语法分析表，并注意：对于翻译，但是，当动作符号位于堆栈顶部时，无论当前输入符号是什么，都应该执行由动作符号指定的操作，并且应该从堆栈顶部弹出动作符号，而不移动读取符号指针。6.3从上到下的语法指导翻译。如果翻译器的分析堆栈的顶部符号是A，而当前输入符号是A，那么将要发生的动作是将A和zDycxBwav弹出到堆栈中。此时，堆栈的顶部是动作符号V，因此V从堆栈中出来，执行由动作符号指定的操作。对于这个符号串，翻译语法是输出V，即out(v)。然后，a从堆栈中出来并读取下一个符号c。然后，动

11、作符号W是堆栈的顶部，因此W从堆栈中出来并执行由动作符号指定的操作。对于这个符号串，翻译语法是输出W，即输出(W)。ac#、v被弹出并执行、A被弹出、C被读入、W被弹出并执行、AC #、6.3语法引导的自上而下的翻译，LL(1)分析被扩展为LL(1)语言的翻译器， 翻译语法所决定的语言的翻译只能通过扩展相应分析表的动作部分并具体实现每个动作符号的子程序来实现。下面总结了L1(1)翻译语法翻译的一般控制程序：1)当翻译器的控制执行程序根据顶部符号和当前输入符号查找表时，它转向错误处理程序。 2)如果控制执行程序识别出堆栈顶部的符号是一个动作符号，不管当前的输入符号是什么，该动作符号都会从堆栈中弹

12、出，并转移到相应的子例程，以完成所需的转换。对于符号串翻译语法来说，它的语义动作是输出动作符号中的符号串。6.4属性翻译语法(P128)，属性：向语法符号引入一些属性，这些属性表示与语法符号相关的信息，如类型、值、代码序列、符号表内容等。与这些属性相关的信息，即属性值，可以在解析过程中计算和传输。属性通常由标识符表示，标识符通常写在相应的语法符号下，其含义仅限于它们所属的产品。属性处理的过程就是语义处理的过程。属性分类综合属性继承属性通常规定每个语法符号的综合属性和继承属性的交集为空。属性翻译语法，综合属性：综合属性的计算规则是以“自下而上”的方式进行的，即语法生成的左符号的一些属性是根据其右

13、符号的属性和/或其自身的其他属性来计算的。在解析树中，如果节点的属性值是由子节点的属性值计算的，则该属性称为综合属性。综合属性属于约简类型，可以用表示。对于终端符号，其综合属性有一个指定的初始值，由词法分析器提供。示例ApXq，rYs，t p=q s，r=p t其中p是综合属性，r不是综合属性，q，s，t不能确定，只能通过参考其他生产表达式的属性计算规则来确定。6.4属性翻译语法继承属性：继承属性的计算规则是以“自上而下”的方式进行的，即语法生成的右侧符号的一些属性是根据其左侧符号的属性和/或右侧其他符号的一些属性来计算的。在解析树中，如果节点的属性值是由其父节点和/或同级节点的属性值计算的，

14、则该属性称为继承属性。继承的属性是派生的，可以用表示。起始符号的继承属性有一个初始值。例子ApXq，rYs，t p=q s，r=p t显然，r是一个继承的属性。6.4属性翻译语法，示例(P129-130)算术表达式的属性翻译语法： seqanswerr r=q EP eq tr p=q r EP TQ p=q TP TQ * fr p=q * r TP FQ p=q FP(eq)p=q FP numq p=q，6.4属性翻译语法，语义在上述示例中，p=q r是语义规则。一个产品只能产生一个符号串，但它并不表示所产生的符号串是什么意思。语义规则给出这些处理动作包括搜索和填充各种表格、改变编译器的

15、一些变量值、打印各种错误消息以及生成中间形式代码。属性翻译语法，属性翻译语法(或属性语法):对于压缩的上下文无关语法，当一组属性被引入到语法符号并且语义规则被附加到语法中的表达式时，上下文无关语法被称为属性翻译语法。属性翻译语法和语义分析的翻译过程：第一步，分析输入的符号串，建立语法分析树；步骤2，从语法分析树中获取描述节点属性间依赖关系的依赖图，并从依赖图中获取语义规则的计算顺序；步骤3，计算语义规则，得到翻译结果。语义分析翻译过程分类：自上而下翻译，自下而上翻译，6.4属性翻译语法，自上而下语义分析翻译过程示例(P131)，陈述句语法：类型标识；其中类型代表类型，其值可以是整数、实数或布尔值。属性翻译语法：1)typedset _ type n1，t1；T2=t，t1=t，n1=n 2)，IDnSET_TYPEn1，t1 t2=t，t1=t，n1=n 3)，其中过程SET_TYPE输出变量名及其类型。给出输入符号字符串“int a，b基于。6.4属性翻译语法，解决方案：输入符号字符串“int a，b语义分析和翻译过程为：输出a int b int，6.4属性翻译语法，自下而上语义分析和翻译过程示例(P129)，输入算术表达式3 2*3，应输出9，并给出输入符号串3 2*3的语义分析和翻译过程。例如：翻译语法，属性翻译语法，解决方案：输入符号串的语义分析和翻