第七章 动作文法和属性文法
? 语义处理的抽象描述。
? 作用,自动实现语法和语义检查
? 分类：
动作文法
属性文法
动作文法
? 动作文法
动作符 (Action Symbol)
动作文法 (Action Grammer)
尾动作文法
抽象动作文法
? 动作文法的实现：
动作文法的 LL实现
动作文法的 LR实现
动作符和动作文法
? 动作符,（区别于语法符号）
作用,无语法作用，代表语义动作。
形式,#Name
（ Name是语义子程序名，无参。）
位置,产生式右部的任意位置
? 动作文法,产生式带动作符的文法。
作用,描述语义分析、中间代码生成
等工作过程。
动作文法的例子
例：文法：
L ? D L
L ? ?
D ? a
D ? b
L ?D L
L ? ? <Out>
D ? a
D ? b <Add>
S:=0
?Add,S:=S+1
?Out,Print(S)
SyntexStack InputStream Action
L bab L ? D L
LD bab D ? b #Add
L<A>b 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
L<A>b b match(b);S:=S+1
L L ? #Out
<O> Print(S)
例 2：串中出现连续 b的个数。
? L ? B B
? B ? a B
? B ? b B
? B ? c
? L ? <Init>B B
? B ? a<Out_Init> B
? B ? b<Add> B
? B ? c<Out_Init>
? Init:
m:= 0
? Out_Init:
If m?0
Print(m);m:=0
? Add:
m:= m + 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 #PUSH
E0 ? ( E2 + E4 ) #ADD
E0 ? ( E2 * E4 ) #MUL
PUSH,{ E0.val,= n1.val }
ADD,{ E0.val,= E2.val + E4.val }
MUL,{ E0.val,= E2.val * E4.val }
动作文法的 LL实现
? LL动作文法：
动作文法满足 LL(1)文法的条件。
? 实现组成：
LL(1)分析表，驱动器，语义子程序。
? 驱动程序的分类,
不带语义栈控制,由用户实现语义栈的
管理，即将语义栈的处理写在语义
子程序中。
带语义栈控制,由驱动器来控制语义栈。
带语义栈控制的 LL驱动器
LRCT指针：
? LeftIndex,指向当前产生式左部符号的语义栈地址
? RightIndex,指 向当前产生式右部的语义栈基地址
? CurrentIndex,指向当前符号的语义栈地址
? TopIndex,指向当前第一自由地址
LeftIndex RightIndex CurrentIndex TopIndex
Semantic Stack
带语义栈控制的 LL(1)驱动器
算法要点：
? 语法栈顶是终极符 a:判断 a是否与输入流匹配，若匹
配,Sem(C):= a.val; C:=C+1;PopSynStack(1)
否则报错；
? 语法栈顶是非终极符 X,对当前输入 LL分析表有
X ? Y1Y2… Yn:将 PushSynStack(Eop,Yn,… Y2Y1)
调整 LRCT指针。
? 语法栈顶是动作符,调用相应的语义动作子程序。
? 若语法栈顶是 Eop,PopSynStack(1),恢复 LRCT指针，
C:=C+1
动作文法的 LR实现
? 尾动作文法的 LR实现：
不带语义栈控制：
归约动作执行前先执行语义动作。
带语义栈控制：
语法栈和语义栈同步,
移入时,输入符压入语法栈中，输入符
的语义信息压入语义栈中；
归约时,执行语义动作，语法栈和语义栈同时
退 N个，将产生式左部压入语法栈，
语义信息压入语义栈中。
属性文法
? 用于描述语言的静态语义
? 主要思想：
引入属性符号；
定义属性求值规则
? 例,
E → n E.val:= n.val
E → (E 1) E.val:= E1.val
E → E 1 + E2 E.val:= E1.val+E2.val
? 继承属性和综合属性
? 例：
E → P P.env,= E.env;
E.val,= P.val;
E1 → P+E 2 P.env,= E1.env
E2.env,= E1.env
E1.val,=P.val+E2.val
P → n P.val,=n.val
P → id P.val,=Lookup(P.env,id.name)
P → (E) E.env,= P.env
P.val,= E.val
? 语义处理的抽象描述。
? 作用,自动实现语法和语义检查
? 分类：
动作文法
属性文法
动作文法
? 动作文法
动作符 (Action Symbol)
动作文法 (Action Grammer)
尾动作文法
抽象动作文法
? 动作文法的实现：
动作文法的 LL实现
动作文法的 LR实现
动作符和动作文法
? 动作符,（区别于语法符号）
作用,无语法作用，代表语义动作。
形式,#Name
（ Name是语义子程序名，无参。）
位置,产生式右部的任意位置
? 动作文法,产生式带动作符的文法。
作用,描述语义分析、中间代码生成
等工作过程。
动作文法的例子
例：文法：
L ? D L
L ? ?
D ? a
D ? b
L ?D L
L ? ? <Out>
D ? a
D ? b <Add>
S:=0
?Add,S:=S+1
?Out,Print(S)
SyntexStack InputStream Action
L bab L ? D L
LD bab D ? b #Add
L<A>b 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
L<A>b b match(b);S:=S+1
L L ? #Out
<O> Print(S)
例 2：串中出现连续 b的个数。
? L ? B B
? B ? a B
? B ? b B
? B ? c
? L ? <Init>B B
? B ? a<Out_Init> B
? B ? b<Add> B
? B ? c<Out_Init>
? Init:
m:= 0
? Out_Init:
If m?0
Print(m);m:=0
? Add:
m:= m + 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 #PUSH
E0 ? ( E2 + E4 ) #ADD
E0 ? ( E2 * E4 ) #MUL
PUSH,{ E0.val,= n1.val }
ADD,{ E0.val,= E2.val + E4.val }
MUL,{ E0.val,= E2.val * E4.val }
动作文法的 LL实现
? LL动作文法：
动作文法满足 LL(1)文法的条件。
? 实现组成：
LL(1)分析表，驱动器，语义子程序。
? 驱动程序的分类,
不带语义栈控制,由用户实现语义栈的
管理，即将语义栈的处理写在语义
子程序中。
带语义栈控制,由驱动器来控制语义栈。
带语义栈控制的 LL驱动器
LRCT指针：
? LeftIndex,指向当前产生式左部符号的语义栈地址
? RightIndex,指 向当前产生式右部的语义栈基地址
? CurrentIndex,指向当前符号的语义栈地址
? TopIndex,指向当前第一自由地址
LeftIndex RightIndex CurrentIndex TopIndex
Semantic Stack
带语义栈控制的 LL(1)驱动器
算法要点：
? 语法栈顶是终极符 a:判断 a是否与输入流匹配，若匹
配,Sem(C):= a.val; C:=C+1;PopSynStack(1)
否则报错；
? 语法栈顶是非终极符 X,对当前输入 LL分析表有
X ? Y1Y2… Yn:将 PushSynStack(Eop,Yn,… Y2Y1)
调整 LRCT指针。
? 语法栈顶是动作符,调用相应的语义动作子程序。
? 若语法栈顶是 Eop,PopSynStack(1),恢复 LRCT指针，
C:=C+1
动作文法的 LR实现
? 尾动作文法的 LR实现：
不带语义栈控制：
归约动作执行前先执行语义动作。
带语义栈控制：
语法栈和语义栈同步,
移入时,输入符压入语法栈中，输入符
的语义信息压入语义栈中；
归约时,执行语义动作，语法栈和语义栈同时
退 N个，将产生式左部压入语法栈，
语义信息压入语义栈中。
属性文法
? 用于描述语言的静态语义
? 主要思想：
引入属性符号；
定义属性求值规则
? 例,
E → n E.val:= n.val
E → (E 1) E.val:= E1.val
E → E 1 + E2 E.val:= E1.val+E2.val
? 继承属性和综合属性
? 例：
E → P P.env,= E.env;
E.val,= P.val;
E1 → P+E 2 P.env,= E1.env
E2.env,= E1.env
E1.val,=P.val+E2.val
P → n P.val,=n.val
P → id P.val,=Lookup(P.env,id.name)
P → (E) E.env,= P.env
P.val,= E.val
