06第6章 语法制导翻译技术

null第6章 语法制导翻译技术 第6章 语法制导翻译技术 **内容提要内容提要引言 翻译文法 语法制导翻译 自顶向下语法制导翻译 属性翻译文法 属性文法的自顶向下翻译 自底向上语法制导翻译**6.1 引言6.1 引言编译程序的逻辑工作过程 词法分析和语法分析仅仅对源程序做形式变换和检查。 语义分析检查程序语义是否正确 中间代码生成将语义分析后的结果翻译成代码 上述工作过程采用串行处理方式 实际应用中语法分析、语义分析、中间代码生成采用并行处理方式 中间代码生成**null并行处理方式： 对文法中的每个产生式都附加一些动作(语义分析、操作符号 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 、代码生成等),在语法分析过程中，每当需要使用一个产生式进行推导或归约，语法分析程序除执行相应的语法分析动作外，还要执行相应的其它动作，完成语义分析和代码生成等工作。（边分析边翻译） 并行处理方式涉及几个概念 翻译文法 语法制导翻译 属性翻译文法 **6.2 翻译文法翻译文法：是上下文无关文法的推广，通过在描述语言规则的文法产生式右部的适当位置加入动作而得到的文法 。6.2 翻译文法例：设计一个能将中缀表达式翻译成后缀表达式的翻译器。 假设输入串为a+b*c 输入符号本身表示读操作，用@表示输出操作 则翻译器的输入输出动作为： a@a+b@b*c@c@*@+ @为动作符号标记，由符号@开始的符号串称为一个动作符号。 输出结果由紧跟在符号@之后的各符号组成，即abc*+。**null例：构造中缀表达式文法的翻译文法。① 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把中缀表达式文法叫做输入文法； 在输入文法上添加动作后形成的文法叫做翻译文法 使用中缀表达式文法推导得到终结符号串叫做输入序列； 使用翻译文法推导得到的符号串称为活动序列。 从活动序列中去掉所有动作符号得到输入序列，而所有动作符号组成的符号串称为动作序列。 从动作序列中去掉动作符号标记得到输出序列（翻译结果）**null例：对于符号串(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+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@c**6.3 语法制导翻译 语法制导翻译：给定一输入序列，根据翻译文法得到翻译该输入序列的活动序列，从活动序列中分离出动作符号串，然后执行该动作符号串所规定的动作，从而得到翻译结果。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@c**将二元组（输入序列，动作序列）称为一个对偶 对偶集合称为由给定翻译文法所定义的翻译null由于翻译文法是在输入文法的产生式右部的适当位置插入动作符号形成的，因此，翻译文法产生的动作序列受输入语言的文法控制（语法制导）。 语法制导翻译：根据输入语言的文法，分析各条产生式的语义(要求计算机所完成的操作)，分别编出完成这些操作的子程序或程序段(称为语义子程序或语义动作)，并把这些子程序或程序段的名字作为动作符号插入到输入文法各产生式右部的适当位置上，从而实现翻译文法。 ① 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→T*F ⑦ F→b ④ T→F ⑧ F→c**null*语法制导翻译的基本思想 通俗地讲，以语法分析为基础，伴随语法分析的各个步骤，执行相应的语义动作。 具体方法： 1．将文法符号所代表的语言结构的意思，用隶属于该文法符号的属性表示； 2．用语义规则(语义规则的执行就是语义动作)规定产生式所代表的语言结构之间的关系（即属性之间的关系），即用语义规则实现属性计算。 3.语义动作(语义规则的执行)： 在语法分析的适当时刻（如推导或归约）执行附着在对应产生式上的语义规则，以实现对语言结构语义的处理，如计算、查填符号表、生成中间代码、发布出错信息等。*6.4 自顶向下语法制导翻译 自顶向下的语法制导翻译有递归下降翻译和LL(1)翻译。 递归下降翻译(在适当位置插入实现动作符号的子程序）:例:算术表达式翻译文法如下：(@为输出其后的符号串) ① E→E+T@+ ② E→T ③ T→T*F@* ④ T→F ⑤ F→(E) ⑥ F→a@a ⑦ F→b@b ⑧ F→c@c消除左递归得到： E→TE’ E’ →+T@+E’|ε T→FT’ T’ →*F @* T’|ε F→(E)|a@a| b@b| c@c6.4 自顶向下语法制导翻译 *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}求FIRST集和FOLLOW集不考虑动作符号null*－对改写后文法的每个非终结符号编写一个函数。 对于产生式 E→TE’ FIRST(TE’)={(,a,b,c} －用E1表示E’ E() { if(ch∈FIRST(TE’)) { T(); E1(); } else error(); }*E→TE’ E’ →+T@+E’|ε T→FT’ T’ →*F @* T’|ε F→(E)|a@a| b@b| c@cnull*对于产生式 E’ →+T@+E’|ε -用E1表示E’ FIRST(+T@+E’)={+} FOLLOW(E’)={#,)} E1() { if(ch==‘+’) { ch = getnextsymbol(); T(); OUT(“+”); E1()； } else if(ch∈FOLLOW(E’))return; else error(); }*E→TE’ E’ →+T@+E’|ε T→FT’ T’ →*F @* T’|ε F→(E)|a@a| b@b| c@cnull对于产生式 T→FT’ -用T1表示T’ T() { if(ch∈FIRST(FT’)) { F(); T1(); } else error(); }*E→TE’ E’ →+T@+E’|ε T→FT’ T’ →*F @* T’|ε F→(E)|a@a| b@b| c@cnull对于产生式T’ →*F @* T’|ε FIRST(*F @* T’)={*} FOLLOW(T’)={#,+,)} -用T1表示T’ T1 () {if(ch==‘*’) { ch = getnextsymbol(); F ();OUT(“*”); T1 ()； } else if(ch∈FOLLOW(E’))return; else error(); } **E→TE’ E’ →+T@+E’|ε T→FT’ T’ →*F @* T’|ε F→(E)|a@a| b@b| c@cnull对于产生式F→(E)|a@a| b@b| c@c F ( ) {if(ch==‘a’){ch = getnextsymbol();OUT(“a”); } else if(ch==‘b’) {ch=getnextsymbol();OUT(“b”); } else if(ch==‘c’) {ch=getnextsymbol();OUT(“c”); } else if(ch==‘(’） { ch = getnextsymbol(); E ( ); if(ch ==‘)’)ch = getnextsymbol(); } else error（）; }**LL(1)翻译器 LL(1)翻译器 例：输入文法： ① A→aBcD ② A→b ③ B→c ④ B→aA ⑤ D→cD ⑥ D→b 输入文法的LL(1)分析表 翻译文法： ①A→@va@wB@xc@yD@z ②A→b ③B→c@r ④B→a@mA ⑤D→cD@n ⑥D→@sb翻译文法的LL(1)分析表 翻译文法的动作符号同样入栈，当其处于栈顶时，无条件出栈并执行其规定的操作，不移动读符号指针。 构造翻译文法分析表不考虑动作符号**nulla……@v出栈并执行，a出栈，@w出栈并执行 **6.5 属性翻译文法 属性：指与文法符号的类型和值等有关的一些语义信息，在编译中用属性描述被处理对象的语义特征。 属性代表与文法符号相关的语义信息。 属性的设置和语法结构的语义以及翻译程序的需要有关。例如: 文法符号X的类型属性:X.type 文法符号X的值属性:X.val 文法符号X的代码序列:X.code 文法符号X的内存：X.place 文法符号X的符号表入口指针: X.entry等。6.5 属性翻译文法 注：教材中用箭头↑和 ↓代替.**属性、语义规则*属性、语义规则属性和变量一样，可以在语法分析过程中进行计算和传递。 语义规则：属性的计算规则，属性的加工和计算过程。由语义处理过程、语义动作、语义子程序来实现。 属性分为两类：综合属性和继承属性。 终结符只有综合属性, 由词法分析器提供 例：i.lexval表示单词符号“数”的词法值 id.entry表示单词符号“标识符”的符号表入口 非终结符既可以有综合属性也可以有继承属性注：教材中属性前用↑表示综合属性， ↓表示继承属性*两种属性：综合属性*两种属性：综合属性综合属性用于“自下而上”传递信息。 综合属性：在语法树中，一个结点的综合属性值由其子结点的属性值确定。 通常结合自下而上的语法分析在每一个结点处使用语义规则计算综合属性的值 --- 由下层子结点的属性值计算上层父结点的综合属性值，随着自下而上语法分析的进行，最终可计算出开始符号的综合属性值。A X1X2…Xn 综合属性A.b = f(c1,c2,…,ck) 带属性的语法树*null例：设计一个语法分析程序接受算术表达式，并通过添加动作符号输出表达式的值。 已知符号串翻译文法如下： ① S→E@ANSWER ② E→E+T ③ E→T ④ T→T*F ⑤ T→F ⑥ F→(E) ⑦ F→NUM@ANSWER的动作是输出表达式的计算结果。 表达式3+2*3的词法分析结果如下： NUM↑3+ NUM↑2* NUM↑3 其中NUM代表无符号整数,↑数字串表示该符号的属性 **null改写每一个产生式，添加符号属性变量名，并定义符号属性之间的关系即属性求值规则(语义规则)，得到： 属性文法 求值规则 ① S → E↑q@ANSWER↓r r = q ② E↑p→ E↑q+ T↑r p = q + r ③ E↑p→ T↑q p = q ④ T↑p→ T↑q* F↑r p = q * r ⑤ T↑p→ F↑q p = q ⑥ F↑p→ (E↑q) p = q ⑦ F↑p→ NUM↑q p = q 通过自底向上进行求值的属性，称为综合属性，用↑来表示。 终结符号的综合属性具有初始值，由词法分析给出。 **null 属性文法 求值规则 ① S → E↑q@ANSWER↓r r = q ② E↑p→ E↑q+ T↑r p = q + r ③ E↑p→ T↑q p = q ④ T↑p→ T↑q* F↑r p = q * r ⑤ T↑p→ F↑q p = q ⑥ F↑p→ (E↑q) p = q ⑦ F↑p→ NUM↑q p = q 在归约过程中完成属性值的计算⑦⑤③⑦⑤⑦④②**两种属性：继承属性*两种属性：继承属性继承属性用于“自上而下”传递信息。 继承属性：在语法树中，一个结点的继承属性由此结点的父结点和(或)兄弟结点的某些属性确定。 可以用继承属性来表示程序语言结构中的上下文依赖关系。 继承属性的计算可以结合自上而下的语法分析进行A X1X2…X…Xn 继承属性 X.b = f(c1,c2,…,ck) *null例：声明语句文法 ① <声明语句>→TYPE ID<变量表>; ② <变量表>→，ID<变量表> ③ <变量表>→ε 其中TYPE可为int，real，bool 假设词法分析程序输出单词符号时，对变量名输出单词记号ID和变量名；对TYPE输出单词记号TYPE和类型名。 构造语法分析程序，能输出变量名及其类型 **null1、添加语义动作@SET_TYPE输出变量名及类型，因此@SET_TYPE带有两个属性，即变量名和类型： @SET_TYPE↓n1，t1 语法分析程序读到一个变量后，调用SET_TYPE。因此文法改写为： (1) <声明语句>→TYPE ID@SET_TYPE <变量表>; (2) <变量表>→，ID@SET_TYPE <变量表> (3) <变量表>→ε2、确定需要的属性 TYPE需要一个属性(类型名)，即TYPE↑t ID需要一个属性(变量名)，即ID↑n <变量表>需要一个属性，即<变量表↓t2> **null3、确定语义规则（属性求值规则） 产生式(1)的TYPE↑t 和ID↑n由词法分析输出得到。 产生式(2)从词法分析只能得到ID↑n ，令产生式(2)左边<变量表↓t2 > = 产生式(1)右边<变量表↓t2 >,得到翻译文法： <声明语句>→TYPE↑tID↑n@SET_TYPE↓n1,t1 <变量表↓t2> t2= t，t1= t ，n1= n（属性求值规则） 2) <变量表↓t>→，ID↑n@SET_TYPE↓n1,t1<变量表↓t2 > t2= t，t1= t ，n1= n（属性求值规则） 3 ) <变量表>→ε (1) <声明语句>→TYPE ID @SET_TYPE <变量表>; (2) <变量表>→，ID@SET_TYPE <变量表> (3) <变量表>→ε**null假设输入符号串为int a,b；，词法分析输出为TYPE↑int ID↑a, D↑b； ，则带有属性的语法树如图所示 按自顶向下或自左向右方式求得的属性称为继承属性, 其前面冠以↓表示。 声明语句 ；@SET_TYPE↓a, int ID↑a TYPE↑int 变量表↓int @SET_TYPE↓b, int ID↑b 变量表↓int ，ε TYPE↑int ID↑a, D↑b；的语法树 <声明语句>→TYPE↑tID↑n@SET_TYPE↓n1,t1 <变量表↓t2> (1)t2= t，(2)t1= t ，(3)n1= n（属性求值规则） 2) <变量表↓t>→，ID↑n@SET_TYPE↓n1,t1<变量表↓t2 > (4)t2= t，(5)t1= t ，(6)n1= n（属性求值规则） 3 ) <变量表 >→ε **null*属性文法：编译技术中采用的一种语义描述工具，是一种适用于定义语言语义的特殊文法，即在语言的文法中增加了属性的文法。实际上，属性文法是对上下文无关文法的推广。 属性翻译文法：是以一个上下文无关文法为基础, 为每个文法符号引进一组属性(语义值)，对文法的每个产生式都配备一组与之相关联的属性的计算规则(语义规则)而得到的文法。 或者说：符号具有属性并带有属性求值规则的翻译文法称为属性翻译文法 其具体定义如下：*null1)文法的每个终结符、非终结符和动作符号都可以有一个有穷的属性集。 2)每个非终结符和动作符号属性可分为综合属性和继承属性。 3)继承属性的求值规则： ①开始符号的继承属性具有初始值。 ②对产生式左部的非终结符，其继承属性则继承前面产生式中该符号已有的继承属性值。 ③右部的符号，其继承属性由产生式中其它符号属性值进行计算。（语法树上的父亲和兄弟）**null4)综合属性的求值规则： ① 终结符号的综合属性具有指定的初始值。在具体实现中，初始值由由词法分析程序提供。 ② 产生式右部的非终结符号的综合属性值，则取后面以该非终结符号为产生式左部时求得的综合属性值。 ③ 产生式的左部的非终结符号的综合属性值，由产生式中左部或右部的某些符号的属性值进行计算。 ④给定一动作符号，其综合属性值用该动作符号的其它属性值进行计算。 **例：算术表达式的翻译翻译要求：翻译输出是四元式代码 输出符号串中的每个双目运算都用一个四元式表示。 四元式的顺序与执行时的运算顺序相同。 四元式有三个 参数 转速和进给参数表a氧化沟运行参数高温蒸汽处理医疗废物pid参数自整定算法口腔医院集中消毒供应 ，从左到右为∶左操作数，右操作数，运算结果。 例：翻译器将表达式a+b翻译成如下四元式∶ ADD a , b , t1 其中t1是临时变量，保存表达式的结果。 对于表达式：a+a*b，词法分析得到ID↑a+ID↑a * ID↑b，属性翻译文法翻译得到： MULT a b , t1 ADD a t1 , t2 例：算术表达式的翻译文法： E→E+T E→T T→T*F T→F F→(E) F→ID **null1、设计翻译文法： E→E+T@ADD E→T T→T*F@MULT T→F F→(E) F→ID **null2、确定属性和求值规则，构造属性翻译文法 1)令每个非终结符有一个综合属性：临时变量，保存由它产生的表达式结果。 2)输入符号ID有一个综合属性：符号的变量名。 3)动作符号有三个继承属性：左操作数、右操作数、运算结果。 属性翻译文法如下： E↑x→E↑q+T↑r@ADD↓y,z,t， y = q, z = r,t = NEWT，x = t E↑x→T↑p x = p T↑x→T↑q*F↑r@MULT↓y,z,t，y = q,z = r, t = NEWT，x = t T↑x→F↑p ， x = p F↑x→(E↑p)，x = p F↑x→ID↑p ，x = p 函数NEWT返回一个新的临时变量名，按产生顺序分别为t1、t2、…。 动作符号@ADD↓y,z,t 输出ADD y,z,t 动作符号@MULT↓y,z,t 输出MULT y,z,t **null表达式a+a*b的属性语法树 E↑t2 T↑t1 E↑a F↑b T↑a T↑a F↑a F↑a @MULT↓a,z,t @ADD↓a,z,t 产生新变量t2 产生新变量t1 E↑x→E↑q +T↑r@ADD↓y,z,t， y = q, z = r,t = NEWT，x = t E↑x→T↑p x = p T↑x→T↑q *F↑r@MULT↓y,z,t，y = q,z = r, t = NEWT，x = t T↑x→F↑p ， x = p F↑x→(E↑p)，x = p F↑x→ID↑p ，x = p**@MULT↓a,b,t @MULT↓a,b,t1 @ADD↓a,t1,t @ADD↓a,t1,t2 6.6 属性文法的自顶向下翻译属性翻译文法的语法树需要保证完整性，即保证所有属性能通过计算赋值。 不同分析方法对文法有不同要求。 L-属性翻译文法 ：自顶向下分析时保证语法树的完整性6.6 属性文法的自顶向下翻译**null** 属性翻译文法是L-属性翻译文法，当且仅当对其中的每个产生式A→X1X2…Xn，下面三个条件成立： 1．右部符号Xi(1≦i≦n)的继承属性之值，仅依赖于X1,X2,…,Xi-1的任意属性或A的继承属性（P133继承属性规则③的限制）； （L的含义：符号的继承属性只依赖于该符号左边的属性值） 2．左部符号A的综合属性之值仅依赖于A的继承属性或(和)右部符号Xi(1≦i≦n)的任意属性（P133综合属性规则③的限制） ； 3．对一动作符号而言，其综合属性之值是以该动作符号的继承属性或产生式右部的任意属性为变元的函数（P133继承属性规则④的限制） 。条件2、3避免求值的循环依赖；给定文法后可通过构造依赖图进行拓扑排序证明）例：文法中有产生式为： A↓I1↑S2,S3→B↓I4C↑S5D↑S6↓I7,I8E↓I9 根据L-属性的限制条件，I4=F(I1)、S2=G(I7,S6)合法，而I4=H(S2)不合法 。 条件1条件2L-属性文法翻译的实现——递归下降翻译 L-属性文法翻译的实现——递归下降翻译 处理思路和处理不带属性的翻译文法相同，由于属性的存在需要改造对非终结符的处理方法： 1)若非终结符具有属性，则该非终结符的分析函数具有形参，形参数目等于其属性个数。 2)对于继承属性，采用值传递方式，将继承属性值传入被调函数，即在函数调用中所对应的实参是继承属性的值。 3)对于综合属性，采用引用（地址）传递方式，以便将值回传给主调函数,即实参是一个变量引用（地址），在函数返回之前，把综合属性的值赋给该变量。 **null为了进行属性翻译的程序设计，作下述约定： 1) 将属性名用作变量名和参数名。 2)所有出现在左部的同名非终结符，应具有相同的属性名表。 例:产生式 L↑a↓b→E↓i R↓j， i,j = b,a = i + 2 L↑x↓y → H↑z↓w， w = y, z = 2, x = z + y 改成： L↑a↓b→ E↓iR↓j， i,j = b,a = j + 2 L↑a↓b→ H↑z↓w， w = b,z = 2,a = z + b **null3) 若两个属性值相同，则给它们相同的名字，但左部符号的属性值相等时，不能改变成相同的名字。 规则S→A↑aB↓bC↓c，当b=a，c=a时， 可写成S→A ↑aB↓aC↓a 规则L↑a→A↓b@f↓c ，当a=b, c=b时， 可写成L↑a→A↓a@f↓a 规则L↓a↑b→aB↓cC↓d ,当c=a, d=a时， 可写成L↓a↑b→aB↓aC↓a 但当b=a时，不能写成L↓a↑a→aB↓a C↓a 理由：左部非终结符号的属性将作为该非终结符号分析函数的形参，而一个函数的形参不能重名。 如函数L(int a,int b)不可写成L(int a,int a)。**null采用C语言编写属性翻译程序时采用的方法： 1)形式参数：产生式左部非终结符的属性名表设计成相应函数的形参表；将继承属性的形参名说明为值形参(即简单变量)，综合属性形参名说明为指针变量。 2)局部变量：产生式中与在左部出现的属性名不同的属性名变成相应函数的局部变量。 3)非终结符的代码：对于右部出现的每个非终结符的函数调用，该非终结符的属性作为实参。**null4)输入符号的代码：对文法中出现的每个输入符号(即终结符号)，将赋值语句插入到函数中它所对应的NEXTSYM之前，把保存在读符号程序NEXTSYM中的终结符号属性(某个全局变量中)赋给输入符号属性中的每个属性变量（读下一个符号前赋值）。 5)动作符号的代码：对出现在文法中的每个动作符号，插入代码对动作符号的综合属性进行计算，并且把结果赋给对应于该综合属性的变量，然后执行相应动作。 **null6)属性规则的代码：与每个产生式有关的属性求值规则，插入其代码以便对属性求值规则的右部求值，并把结果赋给该规则左部的每个变量。可以把这些代码放在属性计算规则的所有自变量已知之后，且函数值被使用之前的任何地方。 7)主程序：MAIN函数中，对文法开始符号的每一个综合属性的名字变成主程序的局部变量，然后调用开始符号对应的函数。**null例：为算术表达式的L-属性翻译文法编写递归下降翻译器。 E↑t→T↑pE'↓p↑t E'↓p↑t→+T↑r @ADD↓p,r,t0 E'↓t0↑t t0 = NEWT E'↓p↑t→ε t = p T↑t→F↑pT'↓p↑t T'↓p↑t→*F↑r @MULT↓p,r,t0 T'↓t0↑t t0 = NEWT T'↓p↑t→ε t = p F↑p →(E↑p) | ID↑p **如何得到该文法？ 1、消除左递归 2、命名改造null**E↑x→E↑q +T↑r@ADD↓y,z,t， y = q, z = r,t = NEWT，x = t E↑x→T↑p x = p T↑x→T↑q *F↑r@MULT↓y,z,t，y = q,z = r, t = NEWT，x = t T↑x→F↑p ， x = p F↑x→(E↑p)，x = p F↑x→ID↑p ，x = pE↑x→T↑pE'↓q↑y x=y q=p E'↓q↑y→+T↑r @ADD↓p,s,t0 E'↓t1↑t t0 = NEWT p=q s=r t1=t0 y=t E'↓q↑y→ε y=q T↑x→F↑pT'↓q↑y x=y q=p T'↓q↑y→*F↑r @MULT↓p,s,t0 T'↓t0↑t t0 =NEWT p = q s=r t1=t0 y=t T'↓q↑y→ε y=q F↑q →(E↑p) | ID↑p q=p消除左递归null**命名处理E↑t→T↑pE'↓p↑t E'↓p↑t→+T↑r @ADD↓p,r,t0 E'↓t0↑t t0 = NEWT E'↓p↑t→ε t = p T↑t→F↑pT'↓p↑t T'↓p↑t→*F↑r @MULT↓p,r,t0 T'↓t0↑t t0 = NEWT T'↓p↑t→ε t = p F↑p →(E↑p) | ID↑p E↑x→T↑pE'↓q↑y x=y q=p E'↓q↑y→+T↑r @ADD↓p,s,t0 E'↓t1↑t t0 = NEWT p=q s=r t1=t0 y=t E'↓q↑y→ε y=q T↑x→F↑pT'↓q↑y x=y q=p T'↓q↑y→*F↑r @MULT↓p,s,t0 T'↓t0↑t t0 =NEWT p = q s=r t1=t0 y=t T'↓q↑y→ε y=q F↑q →(E↑p) | ID↑p q=pnull对产生式E↑t→T↑pE'↓p↑t ，t为综合属性,形参用指针变量 int E(int *t) { int es=0; int p; es=T(&p); es=E1(p,t); return(es); }E↑t→T↑pE'↓p↑t E'↓p↑t→+T↑r @ADD↓p,r,t0 E'↓t0↑t t0 = NEWT E'↓p↑t→ε t = p T↑t→F↑pT'↓p↑t T'↓p↑t→*F↑r @MULT↓p,r,t0 T'↓t0↑t t0 = NEWT T'↓p↑t→ε t = p F↑p →(E↑p) | ID↑p 方法1方法2方法3**null对产生式 E’↓p↑t→+T↑r @ADD↓p,r,t0 E’↓t0↑t 和 E'↓p↑t→ε p为继承属性,形参用整型变量,t为综合属性,形参用指针变量int E1(int p,int *t) { int r, es, t0; if (ch == '+') { ch = getword(); es = T(&r); t0 = NEWT(); printf(“ ADD %c,%c,%c\n",p,r,t0); es = E1(t0,t); return(es); } else if(ch =='(' ||ch =='#' ) { *t = p; return(0);} else error(); } ...... E'↓p↑t→+T↑r @ADD↓p,r,t0 E'↓t0↑t t0 = NEWT E'↓p↑t→ε t = p ......方法4， 但+无属性方法5， 动作符号无综合属性方法6**int NEWT() { static int i = 64; i = i+1; return(i); }null对产生式T↑t→F↑pT'↓p↑t t为综合属性,形参用指针变量 int T(int *t) { int es=0,p; es=F(&p); es=T1(p,t); return(es); }E↑t→T↑pE'↓p↑t E'↓p↑t→+T↑r @ADD↓p,r,t0 E'↓t0↑t t0 = NEWT E'↓p↑t→ε t = p T↑t→F↑pT'↓p↑t T'↓p↑t→*F↑r @MULT↓p,r,t0 T'↓t0↑t t0 = NEWT T'↓p↑t→ε t = p F↑p →(E↑p) | ID↑p **nullint T1(int p,int *t) { int r,es,t0; if (ch == '*') { ch = getword(); es = F(&r); t0 = NEWT(); printf(“ MULT %c,%c,%c\n",p,r,t0); es=T1(t0,t); return(es); } else if(ch =='+' ||ch =='#' ||ch ==')' ) { *t=p; return(0);} else error(); }...... T'↓p↑t→*F↑r @MULT↓p,r,t0 T'↓t0↑t t0 = NEWT T'↓p↑t→ε t = p ...... **对产生式T’↓p↑t→*F↑r @MULT↓p,r,t0 T’↓t0↑t和T’ ↓p↑t→ε，p为继承属性,形参用整型变量；t为综合属性,形参用指针变量nullint F(int *p) { int es=0; if (ch=='(' ) { ch=getword(); es=E(p); if (ch!=')') return(3); else {ch=getword();return(es);} } else { if (isalpha(ch)) { *p=ch; ch=getword(); return(es); } else return(4); } }对产生式F↑p→(E↑p)|ID↑p p为综合属性,形参用指针变量方法4**null主程序： 1、MAIN函数中对开始符号的每一个综合属性作为其局部变量； 2、调用开始符号对应的函数，如果实参对应开始符号的继承属性，则以值参方式传入该属性的初始值；如果对应开始符号的综合属性，则传入该属性局部变量的地址。 E↑t→T↑pE'↓p↑t main() { int es = 0, t; printf("请输入算术表达式(操作数只能是单个字母)："); ch = getword(); printf("输出四元式为：\n"); es = E(&t); if (es == 0) printf("\n翻译成功!\n"); else printf("\n表达式有语法错误!\n"); }方法7（1）方法7（2）**null运行程序 输入：a*(b+c)+b*d 输出四元式序列为： 其中A、B、C、D都是临时变量。 ADD b,c,A MULT a,A,B MULT b,d,C ADD B,C,D**null*输入：NUM↑2 *NUM ↑4 +NUM ↑6 #E'↓t0↑tNUM↑2*E↑tT↑pF↑pT'↓p↑t+F↑rE'↓p↑tT↑rNUM↑6F↑p*T'↓p↑tNUM↑4F↑2T'↓2↑tF↑4MULT ↓p,r,t0MULT ↓2,r,t0MULT ↓2,4,t0MULT ↓2,4,8T'↓t0↑tT'↓8↑tADD ↓p,r,t0F↑6T'↓6↑tT'↓8↑8T'↓2↑8T↑8E'↓8↑tT↑6T'↓6↑6E'↓8↑14ADD ↓8,6,t0ADD ↓8,6,14E'↓14↑tE'↓14↑14E↑14调用进入返回递归下降翻译程序的运行 （将文法中ID改为NUM t0 = p+r t0 = p*r）L-属性文法翻译的实现—LL(1)法 L-属性文法翻译的实现—LL(1)法 扩充翻译文法的LL(1)翻译器： 对所有符号，符号本身和属性同时进栈。 将栈符号设计为两部分(符号名、属性域) 例：对符号串ABC，假定A有属性A1和A2，B有属性B1，C无属性。入栈后如图所示。 **null例：文法 S→E↑p@ANSWER↓r r = p E↑p→+E↑qE↑r@ADD↓A1,A2↑R A1 = q, A2 = r, R = A1 + A2, p = R E↑p→*E↑qE↑r@MULT↓A1,A2↑R A1 = q, A2 = r, R = A1 * A2, p = R E↑p→NUM↑q p = q  构造其翻译器 步骤： 1、栈符号设计 2、构造LL(1)分析表 3、设计语义动作**null1、栈符号设计 根据属性类型确定属性域的存放内容，可存放属性值和指向属性值的指针。 对于综合属性，其属性域存放一个指针，指向存贮该属性值的单元。 对于继承属性，其属性域直接保存其属性值。继承属性的属性域刚入栈时为空，但在该栈符号变成栈顶符号之前的某一时刻，必须通过计算赋值，即在成为栈顶时，继承属性的属性域必须有值。**null S的栈符号 E的栈符号 NUM的栈符号 @ANSWER的栈符号 @ADD的栈符号 @MULT的栈符号 S→E↑p@ANSWER↓r r = p E↑p→+E↑qE↑r@ADD↓A1,A2↑R A1 = q, A2 = r, R = A1 + A2, p = R E↑p→*E↑qE↑r@MULT↓A1,A2↑R A1 = q, A2 = r, R = A1 * A2, p = R E↑p→NUM↑q p = q **null2、构造属性翻译文法LL(1)分析表。 LL(1)析表 (1)S→E↑p@ANSWER↓r r=p (2)E↑p→+E↑qE↑r@ADD↓A1,A2↑R A1=q, A2=r, R= 1 + A2, p=R (3)E↑p→*E↑qE↑r@MULT↓A1,A2↑R A1=q, A2 =r, R= A1 * A2, p=R (4)E↑p→NUM↑q p=q **null3、语义动作设计 假定要求翻译器计算输出由文法定义的表达式值,三个动作符号的翻译动作为： 1) @ADD：把头两个域的内容相加并将结果存贮在第三个域所指的单元中，然后出栈。 2) @MULT：把头两个域的内容相乘并将结果存贮在第三个域所指的单元中，然后出栈。 3) @ANSWER：输出属性域的内容结果，然后出栈。 **null1)#入栈，文法开始符号S入栈，输入指针指向符号++NUM↑2NUM↑3# 符号栈： 输入串+NUM↑2NUM↑3# 符号栈： 2)查分析表S行+列，入栈，因为r = p，所以E↑p为指向@ANSWER↓r的指针。 输入符号串+NUM↑2NUM↑3#的分析过程：**(1)S→E↑p@ANSWER↓r r = p (2)E↑p→+E↑qE↑r@ADD↓A1,A2↑R A1 = q, A2 = r, R = A1 + A2, p = R (3)E↑p→*E↑qE↑r@MULT↓A1,A2↑R A1 = q, A2 = r, R = A1 * A2, p = R (4)E↑p→NUM↑q p = q nullNUM↑2NUM↑3# 符号栈： 3)查分析表E行+列,E出栈前,E↑p指向@ANSWER↓r,因为E↑p=@ADD↑R,所以@ADD↑R指向@ANSWER↓r;新入栈的E↑q E↑r,分别指向@ADD↑A1↑A2;因栈顶为+,+出栈,读下一个符号。 **(1)S→E↑p@ANSWER↓r r = p (2)E↑p→+E↑qE↑r@ADD↓A1,A2↑R A1 = q, A2 = r, R = A1 + A2, p = R ......+NUM↑2NUM↑3# NUM↑3# 符号栈： 4)查分析表E行NUM列，E出栈前,E↑q指向@ADD↑A1,而E↑q =NUM↑q,所以NUM↑q入栈,把NUM ↑2放入E出栈前E↑q指向的单元@ADD↑A1。然后，NUM出栈,读下一个符号。 **...... (4)E↑p→NUM↑q p = q 符号栈： NUM↑2NUM↑3# null5) 查分析表E行NUM列，E出栈前,E↑r指向@ADD↑A2,而E↑r=NUM↑q,所以NUM↑q入栈,把NUM↑3放入E↑r指向的单元@ADD↑A2。然后NUM出栈，读下一个符号。 # 符号栈： **....... (4)E↑p→NUM↑q p = q NUM↑3# 符号栈： null6)栈顶为动作符号@ADD：把头两个域内容2和3相加，并把计算结果5存贮在第三个域@ADD↑R所指的@ANSWER↓r中，出栈。# 符号栈： **...... (2)E↑p→+E↑qE↑r@ADD↓A1,A2↑R A1 = q, A2 = r, R = A1 + A2, p = R# 符号栈： null7)栈顶为动作符号@ANSWER,输出属性域的内容5，出栈。栈内为#，输入指针指向#，成功结束。 #符号栈： **(1)S→E↑p@ANSWER↓r r = p .......# 符号栈： 6.7 自底向上的语法制导翻译 波兰翻译文法：对于一个文法,当且仅当文法中每个产生式右部的所有动作符号都只出现在所有输入符号和非终结符号的右边,则称此类翻译文法为波兰翻译文法。 例：0)S→ E 1)E→E +T@ADD 2)E→T 3)T→T *F@MULT 4)T→F 5)F→(E) 6)F→i 0)S→ E 1)E→ E +T 2)E→T 3)T→T *F 4)T→F 5)F→(E) 6)F→ i 6.7 自底向上的语法制导翻译 **null算术表达式的LR分析表 使用带动作符号的产生式归约要执行动作符号规定的动作。波兰翻译0)S→E 1)E→E +T@ADD 2)E→T 3)T→T *F@MULT 4)T→F 5)F→(E) 6)F→i **null输入符号串i+i#的翻译过程 归约之后执行@ADD,输出ADD0)S→E 1)E→E +T@ADD 2)E→T 3)T→T *F@MULT 4)T→F 5)F→(E) 6)F→i **S-属性文法L属性保证自顶向下分析时完整计算属性； S-属性保证自底向上分析时完整计算属性。 S-属性文法：一个属性文法,当且仅当满足以下三个条件： 所有非终结符只具有综合属性; 在一个产生式中，每一个符号的各个综合属性的定义互不依赖； 在一个产生式中，若某个文法符号X具有继承属性，则此继承属性之值仅依赖于该产生式右部且位于X左边的符号之属性。 如果一个波兰翻译文法符合S-属性文法的三个条件,则该文法是S-属性波兰翻译文法。S-属性文法**null例：算术表达式属性翻译文法： 0) S → E↑x 1) E↑x → E↑q +T↑r @ADD↓q,r,x x=NEWV 2) E↑x → T↑x 3) T↑x → T↑q *F↑r @MULT↓q,r,x x=NEWV 4) T↑x → F↑x 5) F↑x → (E↑x) 6) F↑x → i↑x **null 0) S → E↑x 1) E↑x → E↑q +T↑r @ADD↓q,r,x x=NEWV 2) E↑x → T↑x 3) T↑x → T↑q *F↑r @MULT↓q,r,x x=NEWV 4) T↑x → F↑x 5) F↑x → (E↑x) 6) F↑x → i↑x **符合S-属性文法的三个条件, 是S-属性文法,而且是S-属性波兰翻译文法。S-属性波兰翻译文法的翻译实现步骤： 1、将S-属性翻译文法中的属性和动作符号去掉,形成输入文法。为输入文法构造LR分析表； 2、确定文法中每个符号的栈符号 每个栈符号由名字和属性域组成，栈中任何符号的域都是一些存贮单元,当该符号在栈内时,这些域用于保存该符号的属性信息，栈组织方式同LL(1)方法的栈组织。 3、扩充分析表的移进和归约动作 S-属性波兰翻译文法的翻译实现** 扩充方法如下∶ 1）移进动作：把当前输入符号的属性放在移进操作压入的栈符号的相应属性域中。 2）归约动作：当选用产生式P进行归约时,此时栈顶符号串表示输入文法产生式P的右部,且这些域含有文法符号的属性。归约时使用这些属性来计算与该产生式有关的所有动作符号以及左部非终结符号的所有属性。 ①使用这些动作符号属性来产生所需要的输出或完成有关的动作。 ②使用左部非终结符属性来填写表示左部非终结符的属性域,同时归约操作把左部非终结符压入栈中。 **nulli↑3+i↑5分析过程0)S → E↑x 1)E↑x → E↑q +T↑r @ADD↓q,r,x x=NEWV 2)E↑x → T↑x 3)T↑x → T↑q *F↑r @MULT↓q,r,x x=NEWV 4)T↑x → F↑x 5)F↑x → (E↑x) 6)F↑x → i↑x *执行动作ADD，输出ADD 3, 5，x课堂作业课堂作业1、语法制导的基本思想是什么？ 2、