吉林大学：《编译原理》课程教学资源（PPT课件讲稿）第七章 动作文法和属性文法

第七章动作文法和属性文法 义处理的抽象描述。 C作用:自动实现语法和语义检查 C分类: 动作文法 属性文法

第七章 动作文法和属性文法  语义处理的抽象描述。  作用：自动实现语法和语义检查  分类： 动作文法 属性文法

动作文法 动作文法 动作符( Action Symbo) 动作文法( Action Grammer) 尾动作文法 抽象动作文法 动作文法的实现: 动作文法的L实现 动作文法的LR实现

动作文法  动作文法 动作符(Action Symbol) 动作文法(Action Grammer) 尾动作文法 抽象动作文法  动作文法的实现： 动作文法的LL实现 动作文法的LR实现

动作符和动作文法 动作符:(区别于语法符号) 作用:无语法作用,代表语义动作。 形式:#Name (Name是语义子程序名,无参。) 位置:产生式右部的任意位置 动作文法:产生式带动作符的文法 作用:描述语义分析、中间代码生成 等工作过程

动作符和动作文法  动作符： （区别于语法符号） 作用：无语法作用，代表语义动作。 形式：#Name （Name是语义子程序名，无参。） 位置：产生式右部的任意位置  动作文法：产生式带动作符的文法。 作用：描述语义分析、中间代码生成 等工作过程

动作文法的例子 例:文法 L→DL L→>DL L→)入 L→入 D→)a D→)a D b D→b<Add S:=0 亲Add:S:=S+1 来Out: Print(S)

动作文法的例子 例：文法： L → D L L →  D → a D → b L →D L L →  D → a D → b S:=0  Add: S:=S+1  Out: Print(S)

SyntexStack InputStream Action bab L→)DL LD bab D→)b#Add Lb bab match b): S: =S+ ab L→DL LD ab D→a La b match(a) → LD D→b#Add Lb match(b); S: =S+ L→)#0ut <0 Prints)

SyntexStack InputStream Action L bab L → D L LD bab D → b #Add Lb bab match(b);S:=S+1 L ab L → D L LD ab D → a La ab match(a) L b L → D L LD b D → b #Add Lb b match(b);S:=S+1 L L → #Out Print(S)

例2:串中出现连续b的个数。 L→BB B→aB B→bB M nit B→c m:=0 米0 lut nit L→BB lfm≠0 B→aB Print(m): m: =0 B→bB M Add B→c m:=m+1

例2：串中出现连续b的个数。 ⚫ L → B B ⚫ B → a B ⚫ B → b B ⚫ B → c  L → B B ⚫ B → a B ⚫ B → b B ⚫ B → c  Init: m:= 0  Out_Init: If m0 Print(m);m:=0  Add: m:= m + 1

尾动作文法 定义:动作符只出现于产生式的末尾。 特点:实现容易,LL方法和LR方法都可以。 例:E→n #PUSH E→(E1+E2) HEADD E→(E1*E2) iMUL PUSH: top: =top+1; Sem[top]: =n ADD: Sem[top-1]: =Sem[top-1]+Sem[top]; top: =top-1 MUL: Sem [top-1]: =Sem[top-1]*Semtop]; top: =top-1

尾动作文法  定义：动作符只出现于产生式的末尾。  特点：实现容易，LL方法和LR方法都可以。  例：E → n #PUSH E → (E1+ E2) #ADD E → (E1* E2) #MUL PUSH:top:=top+1; Sem[top]:=n ADD: Sem[top-1]:=Sem[top-1]+Sem[top];top:=top-1 MUL：Sem[top-1]:=Sem[top-1]*Sem[top];top:=top-1

抽象尾动作文法 定义:动作子程序中,直接引用对应文法符 号的值,不考虑其形式、位置和结构如何。 ÷举例: E0→n1 iPUSH E0→>(E2+E4)#ADD E0→(E2*E4)#MUL PUSH [E0.va|:=n1.va| ADD IEO. val: = E2. val + E4. val F I EO. val E2 val E4 val F

抽象尾动作文法  定义：动作子程序中，直接引用对应文法符 号的值，不考虑其形式、位置和结构如何。  举例： E 0 → n 1 #PUSH E 0 → ( E2 + E4 ) #ADD E 0 → ( E2 * E4 ) #MUL PUSH: { E0.val := n 1.val } ADD: { E0.val := E 2.val + E4.val } MUL: { E0.val := E 2.val * E4.val }

动作文法的山实现 LL动作文法: 动作文法满足L(1)文法的条件。 实现组成: LL(1)分析表,驱动器,语义子程序。 驱动程序的分类: 不带语义栈控制:由用户实现语义栈的 管理,即将语义栈的处理写在语义 子程序中。 带语义栈控制:由驱动器来控制语义栈

动作文法的LL实现  LL动作文法： 动作文法满足LL(1)文法的条件。  实现组成： LL(1)分析表，驱动器，语义子程序。  驱动程序的分类： 不带语义栈控制：由用户实现语义栈的 管理，即将语义栈的处理写在语义 子程序中。 带语义栈控制：由驱动器来控制语义栈

带语义栈控制的L驱动器 LRGT指针: Leftindex:指向当前产生式左部符号的语义栈地址 Right Index:指向当前产生式右部的语义栈基地址 CurrentIndex:指向当前符号的语义栈地址 ÷ Top Index:指向当前第一自由地址 LeftIndex right index Current Index Top Index Semantic Stack

带语义栈控制的LL驱动器 LRCT指针：  LeftIndex：指向当前产生式左部符号的语义栈地址  RightIndex：指向当前产生式右部的语义栈基地址  CurrentIndex：指向当前符号的语义栈地址  TopIndex：指向当前第一自由地址 LeftIndex RightIndex CurrentIndex TopIndex Semantic Stack