① E→E+T ② E→T ③ T→T*F ④ T→F
⑤ F→(E) ⑥ F→a ⑦ F→b ⑧ F→c
① E→E+T@+ ② E→T ③ T→T*F@* ④ T→F
⑤ F→(E) ⑥ F→a@a ⑦ F→b@b ⑧ F→c@c
2020/11/13
8
语法制导翻译的基本思想 通俗地讲，以语法分析为基础，伴随语法分析的各个步骤，执 行相应的语义动作。 具体方法： 1．将文法符号所代表的语言成分的意思，用隶属于该文法符 号的属性表示； 2．用语义规则(语义规则的执行就是语义动作)规定产生式所 代表的语言成分之间的关系（即属性之间的关系），即用语义 规则实现属性计算。 3.语义动作(语义规则的执行)： 在语法分析的适当时刻（如推导或归约）执行附在对应产生 式上的语义规则，以实现对语言结构语义的处理，如计算、查 填符号表、生成中间代码、发布出错信息等。
10
－对改写后文法的每个非终结符号编写一个函数。
代标 码代 优码 化生
目 标 代 码
成
成
➢ 词法分析和语法分析仅仅对源程序做形式变换和检查。
➢ 语义分析检查程序语义是否正确。
➢ 中间代码生成将语义分析后的结果翻译成代码。
☻上述工作过程采用串行处理方式 ☻实际应用中语法分析、语义分析、中间代码生成采用并
行处理方式
2020/11/13
3
并行处理方式：
消除左递归得到： E→TE’ E’ →+T@+E’|ε T→FT’ T’ →*F @* T’|ε F→(E)|a@a| b@b| c@c
求FIRST集和 FOLLOW集不 考虑动作符号
FIRST(TE’)={(,a,b,c} FIRST(+T@+E’)={+} FOLLOW(E’)={#,)} FIRST(FT’ )={(,a,b,c} FIRST(*F @* T’)={*} FOLLOW(T’)={#,+,)} FIRST((E))={(} FIRST(a@a)={a} FIRST(b@b)={b} FIRST(c@c)={c}
2020/11/13
① E→E+T ② E→T ③ T→T*F ④ T→F
⑤ F→(E) ⑥ F→a ⑦ F→b ⑧ F→c
① E→E+T@+ ② E→T ③ T→T*F@* ④ T→F
⑤ F→(E) ⑥ F→a@a ⑦ F→b@b ⑧ F→c@c
7
语法制导翻译
➢由于翻译文法是在输入文法的产生式右部的适当位置插入动 作符号形成的，因此，翻译文法产生的动作序列受输入语言的 文法控制（语法制导）。 ➢语法制导翻译：根据输入文法，分析各条产生式的语义(要求 计算机所完成的操作)，分别编出完成这些操作的子程序或程序 段(称为语义子程序或语义动作)，并把这些子程序或程序段的 名字作为动作符号插入到输入文法各产生式右部的适当位置上， 从而实现翻译文法。
⑤ F→(E) ⑥ F→a@a ⑦ F→b@b ⑧ F→c@c
@为动作符号标记，由符号@开始的符号串称为一个动作符号。
2020/11/13
5
① E→E+T ⑤ F→(E)
① E→E+T@+
② E→T
⑥ F→a
② E→T
③ T→T*F ⑦ F→b
③ T→T*F@*
④ T→F
⑧ F→c
④ T→F
➢把中缀表达式文法叫做输入文法；
第6章 语法制导翻译技术
2020/11/13
1
内容提要
➢ 引言 ➢ 翻译文法 ➢ 语法制导翻译
自顶向下语法制导翻译 自底向上语法制导翻译 ➢ 属性翻译文法 属性文法的自顶向下翻译 属性文法的自底向上翻译
2020/11/13
2
引言
编译程序的逻辑工作过程
中
目
源 程 序
词 法 分 析
语语 间 法义 代 分分 码 析析 生
2020/11/13
6
例：对于符号串(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@*
对文法中的每个产生式都附加一些动作(语义分 析、操作符号表、代码生成等),在语法分析过程 中，每当需要使用一个产生式进行推导或归约， 语法分析程序除执行相应的语法分析动作外，还 要执行相应的其它动作，完成语义分析和代码生 成等工作。（边分析边翻译）
并行处理方式涉及几个概念
➢ 翻译文法 ➢ 语法制导翻译 ➢ 属性翻译文法
2020/11/13
9
自顶向下语法制导翻译
自顶向下的语法制导翻译：递归下降翻译、LL(1)翻译。 递归下降翻译(在适当位置插入实现动作符号的子程序）:
例:算术表达式翻译 文法如下：(@为输 出其后的符号串) ① E→E+T@+ ② E→T ③ T→T*F@* ④ T→F ⑤ F→(E) ⑥ F→a@a ⑦ F→b@b ⑧ F→c@c
2020/11/13
4
翻译文法
翻译文法：在描述语言规则的文法产生式右部的适当位置加入动 作而得到的文法 。
例：构造中缀表达式文法的翻译文法，得到其后缀表达式。
① E→E+T ② E→T ③ T→T*F ④ T→F
⑤ F→(E) ⑥ F→a ⑦ F→b ⑧ F→c
① E→E+T@+ ② E→T ③ T→T*F@* ④ T→F
⑤ F→(E) ⑥ F→a@a ⑦ F→b@b ⑧ F→c@c
➢在输入文法上添加动作后形成的文法叫做翻译文法
➢使用中缀表达式文法推导得到终结符号串叫做输入序列；
➢使用翻译文法推导得到的符号串称为活动序列。
➢从活动序列中去掉所有动作符号得到输入序列，而所有动 作符号组成的符号串称为动作序列。
➢从动作序列中去掉动作符号标记得到输出序列（翻译结果）
=>(F+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*