理自顶向下语法分析.ppt

第5章自顶向下语法分析方法本章知识点(内容)语法分析器的功能语法分析器的工作本质上就是按文法的产生式，识别输入符号串是否为一个句子，并建立一棵与输入串相匹配的语法分析树。
按照语法分析树的建立方法，可以把语法分析方法分成两类：
一类是自上而下分析法
一类是自下而上分析法不确定的
自顶向下分析法递归下降分析法
确定的
预测分析法LL(1)
语法分析方法简单优先分析法
优先分析法
算符优先分析法
自底向上分析法
LR(0)分析法
LR分析法SLR(1)分析法
LR(1)分析法
LALR(1)分析法自上而下分析面临的问题要点：
.由根向下构造语法树
.构造最左推导
.推导出的终结符是否与当前输入符匹配
Saaab
AB
aA[1]选择使用哪个产生式进行推导？
[2]假定要被代换的最左非终结符号是V，且有n条规则：V→A1|A2|…|An，那么如何确定用哪个右部去替代V？为了这种回溯，我们一方面应把A的第一候选所发展的子树注销掉，另一方面应把IP恢复为进入A时的原值，也就是让它重新指向第二个输入符号。现在我们试探A的第二个候选，即考虑如下的语法树：
由于子树A只有一个子结，而且它和IP所指的符号相一致，于是，A完成了匹配任务。在A获得匹配后，指示器IP应指向下一个未被触及符号y。
在S的第二子结A完成匹配后，接着就轮到第三个子结y进行工作。
由于这个子结和最后一个输入符号相符，于是，我们完成了为α构造语法树的任务，证明了α是一个句子。【例】文法G0[S]:
(1)S→Sa
(2)S→b
分析baa是不是文法的句子
自上而下分析法存在的困难自上而下分析方法不允许文法含有任何左递归。
为构造不带回溯的自上而下分析算法，首先要消除文法的左递归性，并找出克服回溯的充分必要条件。消除回朔实际上就是提取左因子。【例】考虑条件语句的产生式stmt→ifexprthenstmt
｜ifexprthenstmtelsestmt
｜other存在左因子ifexprthenstmt，妨碍自顶向下方法的使用。
【例】文法：
Stm→id:=Exp|id(ExpL)
ExpL→Exp|Exp,ExpL（1）左递归的定义
对于某些字符串α，如果存在推导
A=+>Aα，我们就称该文法含有左递归。直接左递归如果文法中含有如下形式的产生式，我们就称该文法含有直接左递归。A→Aα，其中A∈VN，α∈（VN∪VT）*间接左递归如果文法中含有如下形式的产生式，我们就称该文法含有间接左递归。A→Bα，B→Aβ，其中A，B∈VN，α，β∈（VN∪VT）*左递归的消除【例】消除文法中左递归
E→E+T|T
T→T*F|F
F→(E)|i假定P关于的全部产生式是
P→Pα1|Pα2|...|Pαm|β1|β2|...|βn
其中，每个都不等于，而每个都不以P开头
那末，消除P的直接左递归性就是把这些规则改
写成：
P→β1P'|β2P'|...|βnP'
P'→α1P'|α2P'|...|αmP'|ε【例】试构造与下列文法G[S]等价的无左递归文法。
G[S]:SSa|Nb|c(1)
NSd|Ne|f(2)
间接左递归消除间接左递归算法【例】考虑文法：SQc|c
QRb|b
RSa|a消除左递归。例：[1]A→B1|a
[2]B→C2|b
[3]C→A3|c确定的自顶向下语法分析【分析】该文法有两个特点：（1）每个产生式右部符号串以终结符开始。（2）如果产生式有相同的左部，右部符号串以不同的终结符开始。因此该文法在推导过程中完全可以根据当前输入符号决定选择哪个产生式往下推导。因此推导过程是唯一的，为确定的自顶向下语法分析。【例5.2-2】：已知文法G[S]S->ApS->BqA->aA->cAB->bB->dB给出句子w=ccap的最左推导。【分析】该文法有两个特点：（1）每个产生式右部符号串不全以终结符开始。（2）如果产生式有相同的左部，右部符号串以不同的终结符或非终结符开始。（3）文法中无空产生式。因此该文法在推导过程中根据当前输入符号决定选择哪个产生式往下推导就没有例5.1-1那么直观。比如对于第一个输入符号c，就无法确定到底是选择第一个产生式S->Ap，还是选择第二个产生式S->Bq往下推导。遇到这种情况，首先需要计算各文法右部符号串的开始符号集。首字符集（FIRST）对每一文法符号XV,计算FIRST集的方法为:
1)若XVT,则FIRST(X)={X};
2)若XVN,且有产生式X->a…,aVT,则
aFIRST(X);
3)若XVN,X->,FIRST(X);4)若XVN,Y1,Y2…YiVN,且有产生式X->Y1,Y2…Yn.当Y1,Y2…Yi-1*时(其中1<=i<=n),则FIRST(Y1)-{},FIRST(