语法制导翻译技术

《语法制导翻译技术》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章语法制导翻译技术2021/9/201内容提要引言翻译文法语法制导翻译自顶向下语法制导翻译属性翻译文法属性文法的自顶向下翻译自底向上语法制导翻译2021/9/2026.1引言编译程序的逻辑工作过程词法分析和语法分析仅仅对源程序做形式变换和检查。语义分析检查程序语义是否正确中间代码生成将语义分析后的结果翻译成代码上述工作过程采用串行处理方式实际应用中语法分析、语义分析、中间代码生成采用并行处理方式词法分析语法分析语义分析代码优化目标代码生成目标代码源程序中间代码生成2021/9/203并行处理方式：对文法中的每个产生式都附加一些动作(语

2、义分析、操作符号表、代码生成等),在语法分析过程中，每当需要使用一个产生式进行推导或归约，语法分析程序除执行相应的语法分析动作外，还要执行相应的其它动作，完成语义分析和代码生成等工作。（边分析边翻译）并行处理方式涉及几个概念翻译文法语法制导翻译属性翻译文法2021/9/204翻译文法：是上下文无关文法的推广，通过在描述语言规则的文法产生式右部的适当位置加入动作而得到的文法。6.2翻译文法例：设计一个能将中缀表达式翻译成后缀表达式的翻译器。假设输入串为a+b*c输入符号本身表示读操作，用@表示输出操作则翻译器的输入输出动作为：a@a+b@b

3、*c@c@*@+*+abc@为动作符号标记，由符号@开始的符号串称为一个动作符号。输出结果由紧跟在符号@之后的各符号组成，即abc*+。2021/9/205例：构造中缀表达式文法的翻译文法。①E→E+T⑤F→(E)②E→T⑥F→a③T→T*F⑦F→b④T→F⑧F→c①E→E+T@+⑤F→(E)②E→T⑥F→a@a③T→T*F@*⑦F→b@b④T→F⑧F→c@c把中缀表达式文法叫做输入文法；在输入文法上添加动作后形成的文法叫做翻译文法使用中缀表达式文法推导得到终结符号串叫做输入序列；使用翻译文法推导得到的符号串称为活动序列。从活动序列中去掉

4、所有动作符号得到输入序列，而所有动作符号组成的符号串称为动作序列。从动作序列中去掉动作符号标记得到输出序列（翻译结果）2021/9/206例：对于符号串(a+b)*c用输入文法推导输入序列(a+b)*c:E=>T=>T*F=>F*F=>(E)*F=>(E+T)*F=>(T+T)*F=>(F+T)*F=>(a+T)*F=>(a+F)*F=>(a+b)*F=>(a+b)*c用翻译文法推导活动序列(a@a+b@b@+)*c@c@*:E=>T=>T*F@*=>F*F@*=>(E)*F@*=>(E+T@+)*F@*=>(T+T@+)*F@*=>(F

5、+T@+)*F@*=>(a@a+T@+)*F@*=>(a@a+F@+)*F@*=>(a@a+b@b@+)*F@*=>(a@a+b@b@+)*c@c@*将活动序列(a@a+b@b@+)*c@c@*中的动作符号去掉得到输入序列：(a+b)*c所有动作符号组成的符号串即动作序列为：@a@b@+@c@*去掉动作符号标记得到：ab+c*①E→E+T⑤F→(E)②E→T⑥F→a③T→T*F⑦F→b④T→F⑧F→c①E→E+T@+⑤F→(E)②E→T⑥F→a@a③T→T*F@*⑦F→b@b④T→F⑧F→c@c2021/9/207语法制导翻译：给定一输入

6、序列，根据翻译文法得到翻译该输入序列的活动序列，从活动序列中分离出动作符号串，然后执行该动作符号串所规定的动作，从而得到翻译结果。6.3语法制导翻译例:根据算术表达式翻译文法，对于输入序列a+b*c推导出活动序列：a@a+b@b*c@c@*@+其中：a+b*c为输入序列@a@b@c@*@+为动作序列执行动作序列中的动作产生输出序列abc*+；即输入序列a+b*c的翻译结果。①E→E+T@+⑤F→(E)②E→T⑥F→a@a③T→T*F@*⑦F→b@b④T→F⑧F→c@c2021/9/208将二元组（输入序列，动作序列）称为一个对偶对偶集合称

7、为由给定翻译文法所定义的翻译由于翻译文法是在输入文法的产生式右部的适当位置插入动作符号形成的，因此，翻译文法产生的动作序列受输入语言的文法控制（语法制导）。语法制导翻译：根据输入语言的文法，分析各条产生式的语义(要求计算机所完成的操作)，分别编出完成这些操作的子程序或程序段(称为语义子程序或语义动作)，并把这些子程序或程序段的名字作为动作符号插入到输入文法各产生式右部的适当位置上，从而实现翻译文法。①E→E+T@+⑤F→(E)②E→T⑥F→a@a③T→T*F@*⑦F→b@b④T→F⑧F→c@c①E→E+T⑤F→(E)②E→T⑥F→a③T→

8、T*F⑦F→b④T→F⑧F→c2021/9/20910语法制导翻译的基本思想通俗地讲，以语法分析为基础，伴随语法分析的各个步骤，执行相应的语义动作。具体方法：1．将文法符号所代表的语言结构的意