ppt编译原理7章7.ppt

《ppt编译原理7章7.ppt》由会员分享，可在线阅读，更多相关《ppt编译原理7章7.ppt（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七章第七章 语法制导的翻译语法制导的翻译7.1基本概念基本概念 1.编译系统的两类翻译：编译系统的两类翻译：非语法制导的翻译非语法制导的翻译语法制导的翻译：以语法分析为主导的语义处理在源程序语法制导的翻译：以语法分析为主导的语义处理在源程序的语法分析中嵌入语义处理。即，利用源程序的文法框架生成的语法分析中嵌入语义处理。即，利用源程序的文法框架生成中间代码或目标代码。中间代码或目标代码。Tips：语义学：语义学：semantics lexeme lexicon semantic 例例（1）递归子程序法的代码生成）递归子程序法的代码生成（2）利用优先矩阵的语法分析直接生成目标代码）利用优先矩阵的

2、语法分析直接生成目标代码（3）利用逆波兰算法进行语法、语义分析）利用逆波兰算法进行语法、语义分析（1）语法分析语义分析语法分析语义分析：直接生成目标代码直接生成目标代码 优点：编译相对简单，时间效率高优点：编译相对简单，时间效率高 缺点：空间代价较高缺点：空间代价较高（2）语法分析中间代码优化目标代码）语法分析中间代码优化目标代码7.7.2 2 两种编译流程两种编译流程例如有如下表达式：例如有如下表达式：a+ba+b*c(a+b)*c逆波兰表示逆波兰表示ab+abc*+ab+c*可以看出后缀表示具备以下优点：可以看出后缀表示具备以下优点：(1)无括号，形式简单清楚；无括号，形式简单清楚；(2)

3、运算符的顺序与表达式的运算次序相同；运算符的顺序与表达式的运算次序相同；在具体处理过程中，可以从左到右检查表达式的各符在具体处理过程中，可以从左到右检查表达式的各符号，遇到运算分量则保存，若遇到运算符，则取其前面的号，遇到运算分量则保存，若遇到运算符，则取其前面的两个分量两个分量(双目运算双目运算)或一个分量或一个分量(单目运算单目运算)进行处理。进行处理。后缀表示法与前缀表示法及中缀表示法相比较，其共同后缀表示法与前缀表示法及中缀表示法相比较，其共同的特点是：的特点是：(1)运算符的个数不变运算符的个数不变;(2)运算量的次序和个数不变。运算量的次序和个数不变。在在计计算算机机处处理理过过程

4、程中中可可以以用用一一个个栈栈(硬硬件件或或软软件件栈栈)来来计计算算它它的的值值。一一般般的的计计算算过过程程是是：自自左左向向右右扫扫描描后后缀缀式式，每每逢逢遇遇到到运运算算量量就就令令其其入入栈栈；遇遇到到K目目运运算算符符，则则将它作用于栈顶的将它作用于栈顶的K个项，并用运算结果代替这个项，并用运算结果代替这K个项。个项。实际计算时，每遇到一个实际计算时，每遇到一个K目运算符，与它有关的目运算符，与它有关的K个运算量已在栈顶，运行结果在原来的个运算量已在栈顶，运行结果在原来的K个项从栈中移个项从栈中移出后置于栈顶。出后置于栈顶。例如例如：ab+c*的计值过程如下：的计值过程如下：1.

5、a入栈；入栈；a2.b入栈；入栈；b3.将栈顶两项相加将栈顶两项相加,移走栈顶的两个项移走栈顶的两个项,把和数把和数E1置于栈顶置于栈顶 E1E1=a+b4.c入栈入栈.c5.将栈顶两项相乘将栈顶两项相乘,移走栈顶的两个项移走栈顶的两个项,把积把积E2置于栈顶置于栈顶;E2E2=E1*c二、二、其它语法成分的逆波兰表示其它语法成分的逆波兰表示：1.赋值语句赋值语句:=把把:=看成一个运算符号看成一个运算符号赋值运算，它为一特殊的赋值运算，它为一特殊的双目运算，则对应的逆波兰表示为：双目运算，则对应的逆波兰表示为：:=例：例：x:=100逆波兰表示为：逆波兰表示为：x100:=x:=a*b+c/

6、d逆波兰表示为：逆波兰表示为：xab*cd/+:=在进行具体处理时，可以采用与表达式相似的方法，不在进行具体处理时，可以采用与表达式相似的方法，不同之处是进行运算时，栈中保存的是同之处是进行运算时，栈中保存的是变量的地址，而变量的地址，而不是它的直，最后的处理不是得到一个结果，而是进行赋值不是它的直，最后的处理不是得到一个结果，而是进行赋值(将表达式的值送到指定的内存单元将表达式的值送到指定的内存单元)，所以，赋值工作完成，所以，赋值工作完成后，应将栈顶两项后，应将栈顶两项(变量地址和表达式的值变量地址和表达式的值)退栈。退栈。2.转向语句转向语句:goto 它对应的逆波兰表示为：它对应的逆波

7、兰表示为：LJLabel Jump含义为转向某标号处，含义为转向某标号处，LJ可看成单目运算符，可看成单目运算符，是是LJ的运算分量的运算分量例：例：goto 100;100 LJ goto Loop;Loop LJ3.条件语句条件语句:在条件语句的逆波兰表示中，它是通过转向逆波兰式中的在条件语句的逆波兰表示中，它是通过转向逆波兰式中的第几个符号去执行来实现，要转去的符号，用它的第几个符号去执行来实现，要转去的符号，用它的“序号序号”来表示：来表示：RJ TJ FJ 无条件转向转向逆波无条件转向转向逆波兰式中的第兰式中的第个个符号去执行，符号去执行，RJ为单为单目运算符号；目运算符号；布尔表达

8、式值为真转布尔表达式值为真转序号处执行序号处执行；布尔表达式值为假转布尔表达式值为假转序号处执行序号处执行；对于条件语句：对于条件语句：if then else 可用以下的逆波兰式表示：可用以下的逆波兰式表示：的逆波兰式的逆波兰式 FJ RJ：可以不分行书写而将可以不分行书写而将它们写在一行中。它们写在一行中。是指是指“的逆波兰表示的逆波兰表示”中第一中第一个单词的序号个单词的序号是指条件语句的是指条件语句的后继语句的逆波兰表示中后继语句的逆波兰表示中第一个单词的序号第一个单词的序号例：有条件语句：例：有条件语句：if ab then x:=a+b else x:=a-b其逆波兰表示为：其逆波

9、兰表示为：(1)ab(4)FJ(6)xab+:=(11)RJ (13)xab-:=(18)1318或写成一行或写成一行:ab13FJxab+:=18RJxab-:=4.循环语句循环语句:我们以我们以for循环为例进行说明：循环为例进行说明：for i:=a to b do s 先将其展开成等价的条件语句：先将其展开成等价的条件语句：i:=a;10:if i=b then begin s;i:=i+1:goto 10 end 然后用条件语句和转向语句的逆波兰表示，将它然后用条件语句和转向语句的逆波兰表示，将它表示成逆波兰式。其它形式的循环语句，也是首先展表示成逆波兰式。其它形式的循环语句，也是首

10、先展开成等价的条件语句表示，然后表示成逆波兰式。开成等价的条件语句表示，然后表示成逆波兰式。例如：例如：for i:=1 to 100 do s:=s+i 先将其展开：先将其展开：i:=1;10:if i=100 then begin s:=s+i;i:=i+1:goto 10 end逆波兰式逆波兰式(1)i1:=(4)10:(6)i100=(9)FJ(11)ssi+:=(16)ii1+:=(21)4 RJ(23)(1)i1:=(4)i100=(7)FJ(9)ssi+:=(14)ii1+:=(19)4 RJ(21)2321写成一行：写成一行：i1:=i100=21FJssi+:=ii1+:=4

11、RJ7.2 7.2 四元式表示四元式表示一、一、四元式的格式四元式的格式：(，)、为为参加运算的两个分量参加运算的两个分量即为运算结果即为运算结果若为单目运算，若为单目运算，为空，用为空，用“/”表示表示二、二、举例说明举例说明：1.表达式的四元式：表达式的四元式：例例1.a*b+c/d(*,a,b,T1)(/,c,d,T2)(+,T1,T2,T)例例2.-(a*b-c)(*,a,b,T1)(-,T1,c,T2)(,T2,/,T)表示单目运算减表示单目运算减2.赋值语句的四元式：赋值语句的四元式：把赋值看成一种运算，把赋值看成一种运算，为空为空例例1：x:=10(:=,10,/,x)例例2：x

12、:=-(a*b-c)(*,a,b,T1)(-,T1,c,T2)(,T2,/,T)(:=:=,T,/,x)3.转向语句的四元式：转向语句的四元式：仍然用仍然用RJ,TJ,FJ三个运算符号：三个运算符号：(RJ,A,/,/)表示无条件转到序号表示无条件转到序号A处；处；(TJ,A,B,/)表示当条件表示当条件B为真时转到序号为真时转到序号A处；处；(FJ,A,B,/)表示当条件表示当条件B为假时转到序号为假时转到序号A处；处；A为某个四元式的为某个四元式的序号，序号，B为条件。为条件。4.条件语句的四元式：条件语句的四元式：例：例：if ab then x:=a+b else x:=a-b 对应的四元式为：对应的四元式为：(1)(,a,b,T1)(2)(FJ,T1,/)(3)(+,a,b,T2)(4)(:=,T2,/,x)(5)(RJ,/,/)(6)(-,a,b,T3)(7)(:=,T3,/,x)(8)68处理顺序与逆波兰式相同处理顺序与逆波兰式相同5.循环语句的四元式：首先转化成等价的条件语句表示，循环语句的四元式：首先转化成等价的条件语句表示，再表示成四元式，要求自己完成。再表示成四元式，要求自己完成。HW:P188 1.(1)(7)分别给出逆波兰表示分别给出逆波兰表示和四元式。和四元式。