语法制导翻译技术.ppt

第6章语法制导翻译技术 2020 3 19 1 内容提要 引言翻译文法语法制导翻译自顶向下语法制导翻译属性翻译文法属性文法的自顶向下翻译自底向上语法制导翻译 2020 3 19 2 6 1引言 编译程序的逻辑工作过程词法分析和语法分析仅仅对源程序做形式变换和检查 语义分析检查程序语义是否正确中间代码生成将语义分析后的结果翻译成代码上述工作过程采用串行处理方式实际应用中语法分析 语义分析 中间代码生成采用并行处理方式 中间代码生成 2020 3 19 3 并行处理方式 对文法中的每个产生式都附加一些动作 语义分析 操作符号表 代码生成等 在语法分析过程中 每当需要使用一个产生式进行推导或归约 语法分析程序除执行相应的语法分析动作外 还要执行相应的其它动作 完成语义分析和代码生成等工作 边分析边翻译 并行处理方式涉及几个概念翻译文法语法制导翻译属性翻译文法 2020 3 19 4 翻译文法 是上下文无关文法的推广 通过在描述语言规则的文法产生式右部的适当位置加入动作而得到的文法 6 2翻译文法 例 设计一个能将中缀表达式翻译成后缀表达式的翻译器 假设输入串为a b c输入符号本身表示读操作 用 表示输出操作则翻译器的输入输出动作为 a a b b c c 为动作符号标记 由符号 开始的符号串称为一个动作符号 输出结果由紧跟在符号 之后的各符号组成 即abc 2020 3 19 5 例 构造中缀表达式文法的翻译文法 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 把中缀表达式文法叫做输入文法 在输入文法上添加动作后形成的文法叫做翻译文法使用中缀表达式文法推导得到终结符号串叫做输入序列 使用翻译文法推导得到的符号串称为活动序列 从活动序列中去掉所有动作符号得到输入序列 而所有动作符号组成的符号串称为动作序列 从动作序列中去掉动作符号标记得到输出序列 翻译结果 2020 3 19 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 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 2020 3 19 7 语法制导翻译 给定一输入序列 根据翻译文法得到翻译该输入序列的活动序列 从活动序列中分离出动作符号串 然后执行该动作符号串所规定的动作 从而得到翻译结果 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 2020 3 19 8 将二元组 输入序列 动作序列 称为一个对偶对偶集合称为由给定翻译文法所定义的翻译 由于翻译文法是在输入文法的产生式右部的适当位置插入动作符号形成的 因此 翻译文法产生的动作序列受输入语言的文法控制 语法制导 语法制导翻译 根据输入语言的文法 分析各条产生式的语义 要求计算机所完成的操作 分别编出完成这些操作的子程序或程序段 称为语义子程序或语义动作 并把这些子程序或程序段的名字作为动作符号插入到输入文法各产生式右部的适当位置上 从而实现翻译文法 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 2020 3 19 9 10 语法制导翻译的基本思想通俗地讲 以语法分析为基础 伴随语法分析的各个步骤 执行相应的语义动作 具体方法 1 将文法符号所代表的语言结构的意思 用隶属于该文法符号的属性表示 2 用语义规则 语义规则的执行就是语义动作 规定产生式所代表的语言结构之间的关系 即属性之间的关系 即用语义规则实现属性计算 3 语义动作 语义规则的执行 在语法分析的适当时刻 如推导或归约 执行附着在对应产生式上的语义规则 以实现对语言结构语义的处理 如计算 查填符号表 生成中间代码 发布出错信息等 2020 3 19 自顶向下的语法制导翻译有递归下降翻译和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 c 6 4自顶向下语法制导翻译 11 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集不考虑动作符号 12 对改写后文法的每个非终结符号编写一个函数 对于产生式E TE FIRST TE a b c 用E1表示E E if ch FIRST TE T E1 elseerror 2020 3 19 E TE E T E T FT T F T F E a a b b c c 13 对于产生式E T E 用E1表示E FIRST T E FOLLOW E E1 if ch ch getnextsymbol T OUT E1 elseif ch FOLLOW E return elseerror 2020 3 19 E TE E T E T FT T F T F E a a b b c c 对于产生式T FT 用T1表示T T if ch FIRST FT F T1 elseerror 2020 3 19 E TE E T E T FT T F T F E a a b b c c 对于产生式T F T FIRST F T FOLLOW T 用T1表示T T1 if ch ch getnextsymbol F OUT T1 elseif ch FOLLOW E return elseerror 2020 3 19 15 E TE E T E T FT T F T F E a a b b c c 对于产生式F E a a b b c cF if ch a ch getnextsymbol OUT a elseif ch b ch getnextsymbol OUT b elseif ch c ch getnextsymbol OUT c elseif ch ch getnextsymbol E if ch ch getnextsymbol elseerror 2020 3 19 16 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 分析表 翻译文法的动作符号同样入栈 当其处于栈顶时 无条件出栈并执行其规定的操作 不移动读符号指针 构造翻译文法分析表不考虑动作符号 2020 3 19 17 a v出栈并执行 a出栈 w出栈并执行 2020 3 19 18 属性 指与文法符号的类型和值等有关的一些语义信息 在编译中用属性描述被处理对象的语义特征 属性代表与文法符号相关的语义信息 属性的设置和语法结构的语义以及翻译程序的需要有关 例如 文法符号X的类型属性 X type文法符号X的值属性 X val文法符号X的代码序列 X code文法符号X的内存 X place文法符号X的符号表入口指针 X entry等 6 5属性翻译文法 注 教材中用箭头 和 代替 2020 3 19 19 20 属性 语义规则 属性和变量一样 可以在语法分析过程中进行计算和传递 语义规则 属性的计算规则 属性的加工和计算过程 由语义处理过程 语义动作 语义子程序来实现 属性分为两类 综合属性和继承属性 终结符只有综合属性 由词法分析器提供例 i lexval表示单词符号 数 的词法值id entry表示单词符号 标识符 的符号表入口非终结符既可以有综合属性也可以有继承属性 注 教材中属性前用 表示综合属性 表示继承属性 2020 3 19 21 两种属性 综合属性 综合属性用于 自下而上 传递信息 综合属性 在语法树中 一个结点的综合属性值由其子结点的属性值确定 通常结合自下而上的语法分析在每一个结点处使用语义规则计算综合属性的值 由下层子结点的属性值计算上层父结点的综合属性值 随着自下而上语法分析的进行 最终可计算出开始符号的综合属性值 A X1X2 Xn综合属性A b f c1 c2 ck 带属性的语法树 2020 3 19 例 设计一个语法分析程序接受算术表达式 并通过添加动作符号输出表达式的值 已知符号串翻译文法如下 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代表无符号整数 数字串表示该符号的属性 2020 3 19 22 改写每一个产生式 添加符号属性变量名 并定义符号属性之间的关系即属性求值规则 语义规则 得到 属性文法求值规则 S E q ANSWER rr q E p E q T rp q r E p T qp q T p T q F rp q r T p F qp q F p E q p q F p NUM qp q 通过自底向上进行求值的属性 称为综合属性 用 来表示 终结符号的综合属性具有初始值 由词法分析给出 2020 3 19 23 属性文法求值规则 S E q ANSWER rr q E p E q T rp q r E p T qp q T p T q F rp q r T p F qp q F p E q p q F p NUM qp q 在归约过程中完成属性值的计算 2020 3 19 24 25 两种属性 继承属性 继承属性用于 自上而下 传递信息 继承属性 在语法树中 一个结点的继承属性由此结点的父结点和 或 兄弟结点的某些属性确定 可以用继承属性来表示程序语言结构中的上下文依赖关系 继承属性的计算可以结合自上而下的语法分析进行 A X1X2 X Xn继承属性X b f c1 c2 ck 2020 3 19 例 声明语句文法 TYPEID ID 其中TYPE可为int real bool假设词法分析程序输出单词符号时 对变量名输出单词记号ID和变量名 对TYPE输出单词记号TYPE和类型名 构造语法分析程序 能输出变量名及其类型 2020 3 19 26 1 添加语义动作 SET TYPE输出变量名及类型 因此 SET TYPE带有两个属性 即变量名和类型 SET TYPE n1 t1语法分析程序读到一个变量后 调用SET TYPE 因此文法改写为 1 TYPEID SET TYPE 2 ID SET TYPE 3 2 确定需要的属性TYPE需要一个属性 类型名 即TYPE tID需要一个属性 变量名 即ID n需要一个属性 即 2020 3 19 27 3 确定语义规则 属性求值规则 产生式 1 的TYPE t和ID n由词法分析输出得到 产生式 2 从词法分析只能得到ID n 令产生式 2 左边 产生式 1 右边 得到翻译文法 TYPE tID n SET TYPE n1 t1t2 t t1 t n1 n 属性求值规则 2 ID n SET TYPE n1 t1t2 t t1 t n1 n 属性求值规则 3 1 TYPEID SET TYPE 2 ID SET TYPE 3 2020 3 19 28 假设输入符号串为inta b 词法分析输出为TYPE intID a D b 则带有属性的语法树如图所示按自顶向下或自左向右方式求得的属性称为继承属性 其前面冠以 表示 声明语句 SET TYPE a int ID a TYPE int 变量表 int SET TYPE b int ID b 变量表 int TYPE intID a D b 的语法树 TYPE tID n SET TYPE n1 t1 1 t2 t 2 t1 t 3 n1 n 属性求值规则 2 ID n SET TYPE n1 t1 4 t2 t 5 t1 t 6 n1 n 属性求值规则 3 2020 3 19 29 30 属性文法 编译技术中采用的一种语义描述工具 是一种适用于定义语言语义的特殊文法 即在语言的文法中增加了属性的文法 实际上 属性文法是对上下文无关文法的推广 属性翻译文法 是以一个上下文无关文法为基础 为每个文法符号引进一组属性 语义值 对文法的每个产生式都配备一组与之相关联的属性的计算规则 语义规则 而得到的文法 或者说 符号具有属性并带有属性求值规则的翻译文法称为属性翻译文法其具体定义如下 2020 3 19 1 文法的每个终结符 非终结符和动作符号都可以有一个有穷的属性集 2 每个非终结符和动作符号属性可分为综合属性和继承属性 3 继承属性的求值规则 开始符号的继承属性具有初始值 对产生式左部的非终结符 其继承属性则继承前面产生式中该符号已有的继承属性值 右部的符号 其继承属性由产生式中其它符号属性值进行计算 语法树上的父亲和兄弟 2020 3 19 31 4 综合属性的求值规则 终结符号的综合属性具有指定的初始值 在具体实现中 初始值由由词法分析程序提供 产生式右部的非终结符号的综合属性值 则取后面以该非终结符号为产生式左部时求得的综合属性值 产生式的左部的非终结符号的综合属性值 由产生式中左部或右部的某些符号的属性值进行计算 给定一动作符号 其综合属性值用该动作符号的其它属性值进行计算 2020 3 19 32 翻译要求 翻译输出是四元式代码输出符号串中的每个双目运算都用一个四元式表示 四元式的顺序与执行时的运算顺序相同 四元式有三个参数 从左到右为 左操作数 右操作数 运算结果 例 翻译器将表达式a b翻译成如下四元式 ADDa b t1其中t1是临时变量 保存表达式的结果 对于表达式 a a b 词法分析得到ID a ID a ID b 属性翻译文法翻译得到 MULTab t1ADDat1 t2 例 算术表达式的翻译 文法 E E TE TT T FT FF E F ID 2020 3 19 33 1 设计翻译文法 E E T ADDE TT T F MULTT FF E F ID 2020 3 19 34 2 确定属性和求值规则 构造属性翻译文法1 令每个非终结符有一个综合属性 临时变量 保存由它产生的表达式结果 2 输入符号ID有一个综合属性 符号的变量名 3 动作符号有三个继承属性 左操作数 右操作数 运算结果 属性翻译文法如下 E x E q T r ADD y z t y q z r t NEWT x tE x T px pT x T q F r MULT y z t y q z r t NEWT x tT x F p x pF x E p x pF x ID p x p 函数NEWT返回一个新的临时变量名 按产生顺序分别为t1 t2 动作符号 ADD y z t输出ADDy z t动作符号 MULT y z t输出MULTy z t 2020 3 19 35 表达式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 tE x T px pT x T q F r MULT y z t y q z r t NEWT x tT x F p x pF x E p x pF x ID p x p 2020 3 19 36 MULT a b t MULT a b t1 ADD a t1 t ADD a t1 t2 属性翻译文法的语法树需要保证完整性 即保证所有属性能通过计算赋值 不同分析方法对文法有不同要求 L 属性翻译文法 自顶向下分析时保证语法树的完整性 6 6属性文法的自顶向下翻译 2020 3 19 37 2020 3 19 38 属性翻译文法是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 条件2 L 属性文法翻译的实现 递归下降翻译 处理思路和处理不带属性的翻译文法相同 由于属性的存在需要改造对非终结符的处理方法 1 若非终结符具有属性 则该非终结符的分析函数具有形参 形参数目等于其属性个数 2 对于继承属性 采用值传递方式 将继承属性值传入被调函数 即在函数调用中所对应的实参是继承属性的值 3 对于综合属性 采用引用 地址 传递方式 以便将值回传给主调函数 即实参是一个变量引用 地址 在函数返回之前 把综合属性的值赋给该变量 2020 3 19 39 为了进行属性翻译的程序设计 作下述约定 1 将属性名用作变量名和参数名 2 所有出现在左部的同名非终结符 应具有相同的属性名表 例 产生式L a b E iR j i j b a i 2L x y H z w w y z 2 x z y改成 L a b E iR j i j b a j 2L a b H z w w b z 2 a z b 2020 3 19 40 3 若两个属性值相同 则给它们相同的名字 但左部符号的属性值相等时 不能改变成相同的名字 规则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 aC a理由 左部非终结符号的属性将作为该非终结符号分析函数的形参 而一个函数的形参不能重名 如函数L inta intb 不可写成L inta inta 2020 3 19 41 采用C语言编写属性翻译程序时采用的方法 1 形式参数 产生式左部非终结符的属性名表设计成相应函数的形参表 将继承属性的形参名说明为值形参 即简单变量 综合属性形参名说明为指针变量 2 局部变量 产生式中与在左部出现的属性名不同的属性名变成相应函数的局部变量 3 非终结符的代码 对于右部出现的每个非终结符的函数调用 该非终结符的属性作为实参 2020 3 19 42 4 输入符号的代码 对文法中出现的每个输入符号 即终结符号 将赋值语句插入到函数中它所对应的NEXTSYM之前 把保存在读符号程序NEXTSYM中的终结符号属性 某个全局变量中 赋给输入符号属性中的每个属性变量 读下一个符号前赋值 5 动作符号的代码 对出现在文法中的每个动作符号 插入代码对动作符号的综合属性进行计算 并且把结果赋给对应于该综合属性的变量 然后执行相应动作 2020 3 19 43 6 属性规则的代码 与每个产生式有关的属性求值规则 插入其代码以便对属性求值规则的右部求值 并把结果赋给该规则左部的每个变量 可以把这些代码放在属性计算规则的所有自变量已知之后 且函数值被使用之前的任何地方 7 主程序 MAIN函数中 对文法开始符号的每一个综合属性的名字变成主程序的局部变量 然后调用开始符号对应的函数 2020 3 19 44 例 为算术表达式的L 属性翻译文法编写递归下降翻译器 E t T pE p tE p t T r ADD p r t0E t0 tt0 NEWTE p t t pT t F pT p tT p t F r MULT p r t0T t0 tt0 NEWTT p t t pF p E p ID p 2020 3 19 45 如何得到该文法 1 消除左递归2 命名改造 2020 3 19 46 E x E q T r ADD y z t y q z r t NEWT x tE x T px pT x T q F r MULT y z t y q z r t NEWT x tT x F p x pF x E p x pF x ID p x p E x T pE q yx yq pE q y T r ADD p s t0E t1 tt0 NEWTp qs rt1 t0y tE q y y qT x F pT q yx yq pT q y F r MULT p s t0T t0 tt0 NEWTp qs rt1 t0y tT q y y qF q E p ID pq p 消除左递归 2020 3 19 47 命名处理 E t T pE p tE p t T r ADD p r t0E t0 tt0 NEWTE p t t pT t F pT p tT p t F r MULT p r t0T t0 tt0 NEWTT p t t pF p E p ID p E x T pE q yx yq pE q y T r ADD p s t0E t1 tt0 NEWTp qs rt1 t0y tE q y y qT x F pT q yx yq pT q y F r MULT p s t0T t0 tt0 NEWTp qs rt1 t0y tT q y y qF q E p ID pq p 对产生式E t T pE p t t为综合属性 形参用指针变量intE int t intes 0 intp es T E t T pE p tE p t T r ADD p r t0E t0 tt0 NEWTE p t t pT t F pT p tT p t F r MULT p r t0T t0 tt0 NEWTT p t t pF p E p ID p 方法1 方法2 方法3 2020 3 19 48 对产生式E p t T r ADD p r t0E t0 t和E p t p为继承属性 形参用整型变量 t为综合属性 形参用指针变量 intE1 intp int t intr es t0 if ch ch getword es T E p t T r ADD p r t0E t0 tt0 NEWTE p t t p 方法4 但 无属性 方法5 动作符号无综合属性 方法6 2020 3 19 49 intNEWT staticinti 64 i i 1 return i 对产生式T t F pT p tt为综合属性 形参用指针变量intT int t intes 0 p es F E t T pE p tE p t T r ADD p r t0E t0 tt0 NEWTE p t t pT t F pT p tT p t F r MULT p r t0T t0 tt0 NEWTT p t t pF p E p ID p 2020 3 19 50 intT1 intp int t intr es t0 if ch ch getword es F T p t F r MULT p r t0T t0 tt0 NEWTT p t t p 2020 3 19 51 对产生式T p t F r MULT p r t0T t0 t和T p t p为继承属性 形参用整型变量 t为综合属性 形参用指针变量 intF int p intes 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 elsereturn 4 对产生式F p E p ID pp为综合属性 形参用指针变量 方法4 2020 3 19 52 主程序 1 MAIN函数中对开始符号的每一个综合属性作为其局部变量 2 调用开始符号对应的函数 如果实参对应开始符号的继承属性 则以值参方式传入该属性的初始值 如果对应开始符号的综合属性 则传入该属性局部变量的地址 E t T pE p t main intes 0 t printf 请输入算术表达式 操作数只能是单个字母 ch getword printf 输出四元式为 n es E 方法7 1 方法7 2 2020 3 19 53 运行程序输入 a b c b d输出四元式序列为 其中A B C D都是临时变量 ADDb c AMULTa A BMULTb d CADDB C D 2020 3 19 54 55 输入 NUM 2 NUM 4 NUM 6 E t0 t NUM 2 E t T p F p T p t F r E p t T r NUM 6 F p 2020 3 19 T p t NUM 4 F 2 T 2 t F 4 MULT p r t0 MULT 2 r t0 MULT 2 4 t0 MULT 2 4 8 T t0 t T 8 t ADD p r t0 F 6 T 6 t T 8 8 T 2 8 T 8 E 8 t T 6 T 6 6 E 8 14 ADD 8 6 t0 ADD 8 6 14 E 14 t E 14 14 E 14 调用 进入 返回 递归下降翻译程序的运行 将文法中ID改为NUMt0 p rt0 p r L 属性文法翻译的实现 LL 1 法 扩充翻译文法的LL 1 翻译器 对所有符号 符号本身和属性同时进栈 将栈符号设计为两部分 符号名 属性域 例 对符号串ABC 假定A有属性A1和A2 B有属性B1 C无属性 入栈后如图所示 2020 3 19 56 例 文法S E p ANSWER rr pE p E qE r ADD A1 A2 RA1 q A2 r R A1 A2 p RE p E qE r MULT A1 A2 RA1 q A2 r R A1 A2 p RE p NUM qp q构造其翻译器 步骤 1 栈符号设计2 构造LL 1 分析表3 设计语义动作 2020 3 19 57 1 栈符号设计根据属性类型确定属性域的存放内容 可存放属性值和指向属性值的指针 对于综合属性 其属性域存放一个指针 指向存贮该属性值的单元 对于继承属性 其属性域直接保存其属性值 继承属性的属性域刚入栈时为空 但在该栈符号变成栈顶符号之前的某一时刻 必须通过计算赋值 即在成为栈顶时 继承属性的属性域必须有值 2020 3 19 58 S的栈符号 E的栈符号 NUM的栈符号 ANSWER的栈符号 ADD的栈符号 MULT的栈符号 S E p ANSWER rr pE p E qE r ADD A1 A2 RA1 q A2 r R A1 A2 p RE p E qE r MULT A1 A2 RA1 q A2 r R A1 A2 p RE p NUM qp q 2020 3 19 59 2 构造属性翻译文法LL 1 分析表 LL 1 析表 1 S E p ANSWER rr p 2 E p E qE r ADD A1 A2 RA1 q A2 r R 1 A2 p R 3 E p E qE r MULT A1 A2 RA1 q A2 r R A1 A2 p R 4 E p NUM qp q 2020 3 19 60 3 语义动作设计假定要求翻译器计算输出由文法定义的表达式值 三个动作符号的翻译动作为 1 ADD 把头两个域的内容相加并将结果存贮在第三个域所指的单元中 然后出栈 2 MULT 把头两个域的内容相乘并将结果存贮在第三个域所指的单元中 然后出栈 3 ANSWER 输出属性域的内容结果 然后出栈 2020 3 19 61 1 入栈 文法开始符号S入栈 输入指针指向符号 NUM 2NUM 3 符号栈 输入串 NUM 2NUM 3 符号栈 2 查分析表S行 列 入栈 因为r p 所以E p为指向 ANSWER r的指针 输入符号串 NUM 2NUM 3 的分析过程 2020 3 19 62 1 S E p ANSWER rr p 2 E p E qE r ADD A1 A2 RA1 q A2 r R A1 A2 p R 3 E p E qE r MULT A1 A2 RA1 q A2 r R A1 A2 p R 4 E p NUM qp q NUM 2NUM 3 符号栈 3 查分析表E行 列 E出栈前 E p指向 ANSWER r 因为E p ADD R 所以 ADD R指向 ANSWER r 新入栈的E qE r 分别指向 ADD A1 A2 因栈顶为 出栈 读下一个符号 2020 3 19 63 1 S E p ANSWER rr p 2 E p E qE r ADD A1 A2 RA1 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出栈 读下一个符号 2020 3 19 64 4 E p NUM qp q 符号栈 NUM 2NUM 3 5 查分析表E行NUM列 E出栈前 E r指向 ADD A2 而E r NUM q 所以NUM q入栈 把NUM 3放入E r指向的单元 ADD A2 然后NUM出栈 读下一个符号 符号栈 2020 3 19 65 4 E p NUM qp q NUM 3 符号栈 6 栈顶为动作符号 ADD 把头两个域内容2和3相加 并把计算结果5存贮在第三个域 ADD R所指的 ANSWER r中 出栈 符号栈 2020 3 19 66 2 E p E qE r ADD A1 A2 RA1 q A2 r R A1 A2 p R 符号栈 7 栈顶为动作符号 ANSWER 输出属性域的内容5 出栈 栈内为 输入指针指向 成功结束 符号栈 2020 3 19 67 1 S E p ANSWER rr p 符号栈 波兰翻译文法 对于一个文法 当且仅当文法中每个产生式右部的所有动作符号都只出现在所有输入符号和非终结符号的右边 则称此类翻译文法为波兰翻译文法 例 0 S E1 E E T ADD2 E T3 T T F MULT4 T F5 F E 6 F i 0 S E1 E E T2 E T3 T T F4 T F5 F E 6 F i 6 7自底向上的语法制导翻译 2020 3 19 68 算术表达式的LR分析表 使用带动作符号的产生式归约要执行动作符号规定的动作 波兰翻译 0 S E1 E E T ADD2 E T3 T T F MULT4 T F5 F E 6 F i 2020 3 19 69 输入符号串i i 的翻译过程 归约之后执行 ADD 输出ADD 0 S E1 E E T ADD2 E T3 T T F MULT4 T F5 F E 6 F i 2020 3 19 70 L属性保证自顶向下分析时完整计算属性 S 属性保证自底向上分析时完整计算属性 S 属性文法 一个属性文法 当且仅当满足以下三个条件 所有非终结符只具有综合属性 在一个产生式中 每一个符号的各个综合属性的定义互不依赖 在一个产生式中 若某个文法符号X具有继承属性 则此继承属性之值仅依赖于该产生式右部且位于X左边的符号之属性 如果一个波兰翻译文法符合S 属性文法的三个条件 则该文法是S 属性波兰翻译文法 S 属性文法 2020 3 19 71 例 算术表达式属性翻译文法 0 S E x1 E x E q T r ADD q r xx NEWV2 E x T x3 T x T q F r MULT q r xx NEWV4 T x F x5 F x E x 6 F x i x 2020 3 19 72 0 S E x1 E x E q T r ADD q r xx NEWV2 E x T x3 T x T q F r MULT q r xx NEWV4 T x F x5 F x E x 6 F x i x 2020 3 19 73 符合S 属性文法的三个条件 是S 属性文法 而且是S 属性波兰翻译文法 步骤 1 将S 属性翻译文法中的属性和动作符号去掉 形成输入文法 为输入文法构造LR分析表 2 确定文法中每个符号的栈符号每个栈符号由名字和属性域组成 栈中任何符号的域都是一些存贮单元 当该符号在栈内时 这些域用于保存该符号的属性信息 栈组织方式同LL 1 方法的栈组织 3 扩充分析表的移进和归约动作 S 属性波兰翻译文法的翻译实现 2020 3 19 74 扩充方法如下 1 移进动作 把当前输入符号的属性放在移进操作压入的栈符号的相应属性域中 2 归约动作 当选用产生式P进行归约时 此时栈顶符号串表示输入文法产生式P的右部 且这些域含有文法符号的属性 归约时使用这些属性来计算与该产生式有关的所有动作符号以及左部非终结符号的所有属性 使用这些动作符号属性来产生所需要的输出或完成有关的动作 使用左部非终结符属性来填写表示左部非终结符的属性域 同时归约操作把左部非终结符压入栈中 2020 3 19 75 i 3 i 5分析过程 0 S E x1 E x E q T r ADD q r xx NEWV2 E x T x3 T x T q F r MULT q r xx NEWV4 T x F x5 F x E x 6 F x i x 76 执行动作ADD 输出ADD3 5 x 课堂作业 1 语法制导的基本思想是什么 2 下面文法是L 属性翻译文法吗 说明理由 S a iA j d k lB nk i l n jS b mB x g yx y 45A Q4 a pA Q1 d Q2 Q3A NQ4 Q3 Q2 Q1A R2 b T1 q T2a R1T2 T1 R2 R1B T a i d T1T1 T 53 一个S 属性文法是L 属性文法吗 为什么 2020 3 19 77