编译原理 8章.ppt

while E do S 1 E 2jumpf S 1 jump 2 for k:= k1 step k3 until k2 do S k:=k1; 1 kk2-sign(k3)*2 jumpf S kk3+:= 1 jump 2 while(循环判定式) 循环体语句; LOC L1 E; FJP L2 ； S1; UJF L1; LOC L2； S→T S1 ，T S1 UJF L1; LOC L2； T→W(E) , W E FJP L2 ； W→while , LOC L1 do 循环体语句 while(循环判定式); LOC L1 S1; ┐E; FJF L1; S→D1 W ，D1 W FJF L1; D1→D S1 , D S1 ┐； D→do , LOC L1 W→(E) , E 8.3.3 函数调用 考虑函数调用的情况，假定有关的基础源文法是 F→N(L) L→L；E L→E A→Aa A→a N→A 注意：这里实参表列由分号隔开的若干个E组成。 如果允许CALL和过程名都出现在实在参数代码之后，就需要一个非简单的翻译器。 下面的简单后缀的SDTS可用来产生过程的后缀调用形式： F→N(L),N L;CALL L→L;E，L E N→A,A LOAD L→E,E A→Aa,Aa A→a，a 那么，函数调用：aa(a;a+aaa) 将翻译成 aa；LOAD a；LOAD a；LOAD aaa；ADD；CALL 而且CALL将操作在第一个标识符aa上。 8.4 抽象语法树的构造(1) 抽象语法树AST(Abstract-Syntax Tree)是某个语言结构的一种简洁的树形表示形式，它只需包含该结构尚须转换或归约的信息。一般说来，任何语法结构(例如表达式、控制结构和说明)都可以用AST表示。 AST也可作为一个多遍编译程序的中间语言结构。采用AST表示法有助于代码的产生和优化。 8.4 抽象语法树的构造(2) 考虑文法G0： E→E+T E→T T→T*F T→F F→（E） F→a 利用该文法构造的每个简单表达式的语法树都比较大。 例如，简单表达式a*(a+a)的语法树如图8.4所示。这棵树有7个末结点和11个中间结点，但所给表达式本身却只有两个运算符和三个操作数．为什么差别如此之大呢? 8.4 抽象语法树的构造(3) 可按如下方式将这棵语法树简化成一个AST。 首先，去掉与单非产生式,上提终结符结点。 第二，上提运算符并让它取代其父结点。 第三，去掉括号，并上提运算符。 最后得到的语法树便是一个AST。 这棵树也是下述表达式的抽象语法树： a*((a)+a) a*(a+(a)) (a*(a+a)) 注意：AST并不是一种规范形式，它并没有指明运算符的交换律和结合律．例如，a*b+c、c+b*a、c+a*b等表达式在数学上是等价的，但可生成不同的AST． 只要稍微改变一下SDTS的实现方式，就可不必生成一个完整的语法树而直接构造一个AST． 8.4.1 自下而上构造AST 对于一个自下而上分析器. 考虑产生式E→E+T，当E+T作为句柄出现在栈顶时，已存在两棵子树E和T，但并无以“+”为根的子树。这条规则是说：构造以“+”为根的一棵子树，并将E和T子树作为它的两个孩子(左孩子和右孩子)。于是，得到以“+”为根的一棵新子树，将它连到E以替代栈顶的E和T。 对于规则E→T，当T是句柄时，它本身已连在某棵子树上，将这棵子树连到E以替代栈顶上的T。 最后，规则F→(E)告诉我们将E子树连到F以取代栈顶的(E)，而F→a则指明将由终结符a构成的单一结点的树连到F并用F取代a。 当到达接收状态时，已构造好一棵AST，且它已连到位于栈顶的开始符号上。 表8.2 根据文法G0 及其分析器直接产生一个AST 文法中的产生式 AST的成分 E→E+T E→T T T→T*F T→F F F→(E) E F→a a 8.4.2 AST的拓广 AST的一般形式是：其中间结点是运算符，而它的叶子为简单变量或常数。事实上，运算符号可以是任何单目运算符、二日运算符或n目运算符。 例如，一个类似于X(el,e2,…,en) 的数组元素可表示成图8.8所示形式的AST，其中，X是多维数组的名字，el，e2，…，en为其下标。 AST也可表示控制结构和说明(略)。 8.5 属性文法(1) 属性文法(Attribute Grammar)是Knuth于1968年提出的，也