自顶向下分析技术.txt

这是一个使用MFC编成的词法语法分析器,它实现的界面及功能良好.

编译原理讲义
(第四章:语法分析--
自顶向下分析技术)
南京大学计算机系
赵建华
引言
在词法分析完成之后,进入语法分析阶段.
语法分析阶段的任务是:检查程序的语法是否正确,并生成内部中间表示形式.
语法分析的
输入:属性字序列.
输出:程序的内部中间表示形式.
自顶向下分析技术与识别算法
从推导的角度看,从识别符号出发,试图推导出与输入符号串相同的符号串.一般来讲,构造出的推导是最左推导.
从语法树的角度看,从根节点,试图向下一个语法树,其末端节点正好与输入符号串相同.
讨论前提
输入的是符号序列,不对符号构造情况感兴趣.
语法分析的文法是上下文无关文法.
自顶向下分析技术的理论基础是定理2.7:如果Z::=X1X2…Xn且y为句子.那么如果X1X2…Xn=>y,必然存在y1,y2,…,yn使得Xi=>*yi且y=y1y2… yn.
要解决的基本问题
对于特定的终结符号,使用哪个重写规则来替换 
无回溯的自顶向下分析技术
先决条件:
无递归
既没有规则左递归,也没有文法左递归.
无回溯性
对于任一非终结符号U的规则右部x1|x2|…|xn,其对应的字的头终结符号两两不相交.
递归下降分析技术(实现思想)
实现思想:
识别程序由一组过程组成.每个过程对应于一个非终结符号.
每一个过程的功能是:选择正确的右部,扫描完相应的字.在右部中有非终结符号时,调用该终结符号对应的过程来完成.
基本架构(1)
对于每个非终结符号U::=u1|u2|…|un处理的方法如下:
U( ){
ch=当前符号
if(ch可能是u1字的开头) 处理u1的程序部分
else if(ch可能是u2字的开头) 处理u2的程序部分
…
else error() 
}
基本架构(1)
对于无回溯的文法保证选择是唯一的.
但有某个右部的开头是非终结符号时,需要用LL(K)方法判断什么时候使用这个右部.
当存在空规则的时候,可以把error()替代为{return;},这样的处理使发现错误的情况比较晚.
约定:进入这个过程时,对于U的第一个符号已经被读到当前符号.离开这个程序的时候,下一个符号已经被读到当前符号.
基本架构(2)
对于每个右部u1=x1x2…xn的处理架构如下:
处理x1的程序;
处理x2的程序;
… … … 
处理xn的程序;
如果右部为空,则不处理.
基本架构(3)
对于右部中的每个符号xi
如果xi为终结符号:
if(x== 当前的符号)
{NextCh();return;}
else
出错处理
如果xi为非终结符号,直接调用相应的过程:
xi()
递归下降技术(实例)
文法G4.3
E::=E+T|T T::=T*F|F F::=(E)|i
消左递归得到
E::=TE' E'::=+TE'| T::=FT' T'::=*FT'| F::=(E)|i
递归下降技术(实例续)
对应于文法G4.3'中的每个非终结符号,都有一个过程.
E()
{
if(当前符号可能是T的开始符号)
{ T(); E1();}
else
error();
}
和书上不同的是,我们作了出错处理.一般,当只有一个右部的时候,可以不作出错处理.
递归下降技术(实例续)
E1()
{
if(ch='+')
{
getnextchar(); T(); E1();
}
else
return;
}
因为E1对应有空规则,所以其处理中,不作错误处理,而是直接return.实际表示它没有读入任何字符.
递归分析程序的运行
栈底
E()
T()
输入:i * i + i
T1()
处理完*,当前符号为i
过程调用栈:
F()
递归分析程序的主程序
假设识别符号对应的过程为Z(),那么相应的主程序为
{
GetSymbol(); //首先需要读入一个符号,以满 // 足约定.
Z();
检查是否达到输入的结尾.
}
递归分析程序的优点
实现思想简单明了.程序结构和语法规则有直接的对应关系.
因为每个过程表示一个非终结符号的处理,添加语义加工工作比较方便.
需要书写程序的语言支持递归调用.如果递归调用机制是高效的,那么分析程序也是高效的.
预测分析法
使用下推自动机的方式实现.
使用一个二维分析表和栈联合进行控制来实现递归下降分析技术.
分析表A实际上是一个从VN (VT {#})到规则的映射.当自顶向下分析过程中需要将U展开时,如果当前符号为T时,应该选择规则A[U,T].如果A[U,T]为空,表示输入符号串不正确.
预测分析过程
PUSH(S,#);PUSH(S,Z);
a=下一个符号;X=TOP(S);
如果X为终结符号且a==X且a!=#,POP(S); a=下一个符号.
如果X为终结符号且a==X且a==#,分析结束,接受句子.
如果X为终结符号且a!=X,出错处理.
预测分析过程
如果X为非终结符号且A[X,a]为报错标识,出错处理.
如果X为非终结符号且A[X,a]='X= X1 X2…Xn1 ,
{ POP(S);
将右部Xn …X2 X1压入S中.
}
例子
文法G4.3'[E]
E::=TE' E'::=+TE'| T::=FT'
T'::=*FT'| F::=(E)|i
例子
i
+
*
)
#
(
E
TE'
TE'
E'
+TE'


T
FT'
FT'
T'

FT'


F
i
(E)
i+i*i# 
i+i*i#
+i*i#
i*i#
+i*i#
i+i*i#
+i*i#
i+i*i# 
i*i#
i*i#
*i#
#E
#E'T
#E'T'F
#E'T+
#E'T
#E'T'
#E'T'i
#E'
#E'T'i
#E'T'F
#E'T'
预测分析表的生成
从前面的论述我们看到,预测分析过程的驱动程序时固定的.对于某个文法,分析表是分析过程的核心.
表中A[U,T]='U::=X1X2…Xn'表示对应于X1X2…Xn字的首符号可以是T.就是说X1X2…Xn=>*Tw.我们可以通过这个方式来确定分析表中的值.
预测分析表的生成
一般来讲,对于一个符号串X1X2…Xn的字的第一个终结符号就是X1对应的字的第一个终结符号.但是空规则的存在使情况有一点复杂.
对于U1U2…Un,如果U1=>* ,那么符号串对应的字的首符号也可以是U2对应的字的首符号.计算一个符号串对应的字的首符号的算法也需要考虑到这些.
FIRST(u)和FOLLOW(U)
FIRST(u)={T|u=>*T…,T VT},如果u=>* ,那么,我们规定 FIRST(u).
FOLLOW(U)={T|Z=>* … UT…, T VT {#}}其中,如果Z=>*…U,那么# FOLLOW(U)
直观地讲:
FIRST(u)包含了u对应的字的所有可能的首终结符号.
FOLLOW(U)表示了句型中可能紧跟再U后面的终结符号
FIRST(u) 构造算法
对于文法X构造FIRST(X)
步骤1:如果X VT,那么FIRST(X)={X}
步骤2:如果X VN,且有规则X::=T…,那么将T添加到FIRST(X)中.如果X::= ,那么 也再FIRST(X)中.
步骤3:对于规则X::= X1X2…Xn,把FIRST(X1)中的非 符号添加到FIRST(X)中.如果 在FIRST(X1)中,把FIRST(X2)中的非 符号添加到FIRST(X)中…;如果 在FIRST(Xn)中,把 添加到FIRST(X)中.
对于FIRST(u),可是使用类似于步骤3的方法求解得到.
FIRST的例子
文法G4.3'[E]:
E::=TE' E'::=+TE'| T::=FT'
T'::=*FT'| F::=(E)|i
FIRST(F)={ (,i }
FIRST(T)=FIRST(F)= { (,i }
FIRST(E')={ +, } FIRST(T')={*, }
… … … … 
FOLLOW(U)的构造算法
步骤1 # FOLLOW(Z)
步骤2 如果有规则U::=xWy,那么FIRST(y)中所有的非 符号都在FOLLOW(W)中.
步骤3 如果有规则U::=xW或则 U::=xWy且 FIRST(y),那么FOLLOW(U)中的一切符号都在FOLLOW(W)中.
注意:步骤3需要重复执行,直到没有哪个非终结符号的FOLLOW集合增长为止.
FOLLOW例子
文法G4.3'[E]:
E::=TE' E'::=+TE'| T::=FT'
T'::=*FT'| F::=(E)|i
FOLLOW(E)={#,)}
FOLLOW(E')=FOLLOW(E)={#,)}
FOLLOW(T)=FIRST(E') FOLLOW(E)-{ }={+,#,)}
FOLLOW(T')=FOLLOW(T)= { }={+,#,)}
FOLLOW(F)=FIRST(T') FOLLOW(T)= {+,#,),*}
预测分析表的构造
基本思想:
当我们需要将U选择某个规则展开时,如果当前的输入为a,表示我们要将U展开为以a为首符号的字.如果有规则U::=u,且a FIRST(u),那么表示这个规则是个好的选择.
分析表构造算法
对于每个规则U::=u,执行一下步骤
对于每个终结符号a FIRST(u),A[U,a]='U::=u'.
如果 FIRST(u),对于每个FOLLOW(U)中的每个终结符号b或#,让A[U,b]='U::= u'.
将其它未定义的分析表元素为ERROR.
分析表的例子
文法G4.3'[E]:
E::=TE' E'::=+TE'| T::=FT'
T'::=*FT'| F::=(E)|i
i
+
*
)
#
(
E
TE'
TE'
E'
TE'


T
FT'
FT'
T'

FT'


F
i
(E)
分析表的冲突
文法G4.6[S] S::=iCtSS'|a S'::=eS| C::=b
FIRST(iCtSS')={i} FIRST(eS)={e} 
FIRST(S)={i,a} FIRST(C)={b}
FIRST(S')={e, }
FOLLOW(S)=FOLLOW(S')={#,e}
a
b
e
i
t
#
S
a
iCtSS'
S'
eS; 
C
b

LL(1)文法
定义:如果其预测分析表中没有多重定义的元素,则该文法被称为LL(1)文法.
LL(1)文法是无二义性的.
定理4.1,文法G是LL(1)的,当且仅当每个非终结符号U的任何两个不同的重写规则U::=x | y满足如下条件:
FIRST(x) FIRST(y)= 
x=>* 和y=>* 不能同时成立
如果y=>* ,那么FIRST(x) FOLLOW(U)= 
对于BNF表示法的处理
如果在规则的右部是使用BNF表示的,那么使用自顶向下技术进行处理时,需要作出相应的变化.
预测分析法:修改文法,消除BNF表示.
递归子程序法:处理规则右部的过程有所改变.
例子
E ::= T {+T} T::= F {*F}
F ::= i | (E)
LL(1)的处理方法
修改方法:
对于每个{x},引入新的非终结符号U::=xU | 空.
对于每个[x],引入新的非终结符号U::= x | 空.
修改文法得到:
E ::= T E' E' ::= +TE' | 空
T ::= F T' T' ::= * F T' |空
F ::= i | (E)
然后可以使用LL(1)技术来处理.
递归子程序法
理论上,可以和LL(k)方法处理BNF表达式同样处理.但是,递归子程序法可以使用更加直接的方法.
对于规则右部X1X2…{Xk Xk+1}…Xn的处理方式为
X1的处理; X2的处理;…
while (Xk Xk+1循环继续 )
{Xk的处理,Xk+1的处理}
…; Xn的处理
在判断是否继续循环的时候,判断的是,下一个符号究竟在first(XkXk+1)中,还是在first(Xk+2Xk+3…)中.