第四章语法分析自上而下分析

第四章语法分析自上而下分析第一页，共二十八页，2022年，8月28日引言在词法分析完成之后，进入语法分析阶段。语法分析是编译过程的核心。其任务是：在词法分析识别出的单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语法分析的基础——上下文无关文法语法分析的输入：单词符号串输出：程序的内部中间表示形式。第二页，共二十八页，2022年，8月28日语法分析器——完成语法分析的程序，其工作的实质是按文法产生式，识别输入符号串是否为一个句子。具体来说，就是看能否从文法的开始符号出发，推导出输入串（单词符号组成的有限序列），即能否建立一个与输入串相匹配的语法分析树。以建立与输入串相匹配的语法分析树的不同，语法分析树分为：自上而下的语法树自下而上的语法树4.1语法分析器的功能第三页，共二十八页，2022年，8月28日4.2自上而下分析面临的问题自上而下分析的实质：从推导的角度看，从文法的开始符号出发，自上而下，推出句子。（一般是最左推导）自上而下分析的主旨：对任何输入串，试图尝试一切可能的办法，文法的开始符号（根节点）出发，试图自上而下建立一个语法树，其末端节点正好与输入符号串相同。第四页，共二十八页，2022年，8月28日例4.1（1）SxAy（2）A**|*SSxAy=x*y=x*y=x*ySxAySxAy**=x*y回溯*=x*y=x*y=x*y第五页，共二十八页，2022年，8月28日上述过程面临的一些问题左递归问题回溯成功的暂时性不成功时找不到出错的位置效率底、代价高（穷尽一切方法）解决方法：消除文法的左递归找出克服回溯的充分必要条件第六页，共二十八页，2022年，8月28日1.1消除直接左递归PP|

PP’P’

P’|例4.2P69PP1|P2…|Pm

|1|2|…|nP1P’|2P’|…|nP’P’

1P’|2P’|…|m

P’|第七页，共二十八页，2022年，8月28日1.2消除间接左递归间接左递归的含义P70消除间接左递归的算法——用代入的方法变间接左递归为直接左递归，然后用公式消除左递归第八页，共二十八页，2022年，8月28日例子4.3文法G4.2E::=E+T|T T::=T*F|F F::=(E)|i消左递归得到

E::=TE’ E’::=+TE’| T::=FT’ T’::=*FT’| F::=(E)|i第九页，共二十八页，2022年，8月28日2.1消除回溯为什么要消除回溯？

——无回溯就意味着不用做无谓的尝试。如何消除回溯？对于任一非终结符号A的产生式的右部的后选式：

1|

2|…|

n，如果其对应的第一个终结符号两两各不相同，那么A在匹配过程中就不用试探了，而是根据所面临的输入符号a唯一确定用哪个后选式匹配，即该后选式的成败全权代表了A。第十页，共二十八页，2022年，8月28日

G是一个不带左递归的文法，对于G的所有非终结符的每个后选定义其终结首符集：FIRST（）={a|a…，aVT

}FIRST(u)包含了u对应的字的所有可能的首终结符号。First（X）的求法如下(书P78)：

1）若X是终结符或ε，则First（X）={X}。

2）若X是非终结符，则对于每个产生式X→X1X2…Xn,

a）First（X）包含First(X1)-{ε}。

b）若对于某个i<n，所有First(X1)...First(Xi)

都包括了ε，则First(X)包括First(Xi+1)-{ε}。

c）若所有集合First(X1)...First(Xn)包括ε，则First（X）包括ε。若→ε，则规定εFirst（）如果非终结符A的所有后选首符集两两不相交，则当要求A匹配输入串时，A就能根据它所面临的第一个输入符号a准确指派某个后选去匹配。*第十一页，共二十八页，2022年，8月28日FIRST（）求法示例文法G4.2E::=TE’ E’::=+TE’| T::=FT’ T’::=*FT’| F::=(E)|iFIRST（E）=First（T）=First（F）

=First（（）并First（i）={（，i}FIRST（E’）=First（+TE’

）并First（）

={+，

}FIRST（T’）=First（*FT’

）并First（）

={*，

}第十二页，共二十八页，2022年，8月28日提取公因子——将文法改造成任何非终结符的所有首符集两两不相交的方法P1|2|…|n|1|2|

…

|m（每个不以开头）PA|1|2|

…

|mA1|2|…|n第十三页，共二十八页，2022年，8月28日自动匹配——文法不含左递归，也满足任何非终结符的所有首符集两两不相交的要求，要进行有效的自上而下的语法分析，还要考虑空字的自动匹配问题。例子：对文法4.2输入串i+i自上而下的分析：=i+ii+ii+iT’FiT+E’ETE’iFT’由于E只有一个后选式TE’，iFirst（TE’），所以用ETE’进行推导由于iFirst（i），所以用Fi推导由于iFirst（FT’），所以用TFT’进行推导从T’出发继续匹配，而输入字符+不输入First（T’），但有T’

，所以自动匹配第十四页，共二十八页，2022年，8月28日自动匹配的条件：当a是允许在文法的某个句型中跟在A后的终结符时，A才能自动匹配。FOLLOW(A)={a|S…Aa…,aVT}其中，如果S…A那么#FOLLOW(A)直观地讲：FOLLOW(A)表示了句型中可能紧跟再A后面的终结符号**第十五页，共二十八页，2022年，8月28日FOLLOW(B)的算法（书P79）步骤1 文法的开始符号S，置#FOLLOW(B)步骤2 如果有规则A→B

，那么FIRST()中所有的非符号都在FOLLOW(B)中。步骤3 如果有规则A→B或则A→B且FIRST()，那么FOLLOW(A)中的一切符号都在FOLLOW(B)中。注意：步骤3需要重复执行，直到没有哪个非终结符号的FOLLOW集合增长为止。第十六页，共二十八页，2022年，8月28日FOLLOW例子文法G4.3’[E]: E→TE’ E’→+TE’| T→FT’ T’→*FT’| F→

(E)|iFOLLOW(E)={#,)}FOLLOW(E’)=FOLLOW(E)={#,)}FOLLOW(T)=FIRST(E’)FOLLOW(E)-{}={+,#,)}FOLLOW(T’)=FOLLOW(T)={}={+,#,)}FOLLOW(F)=FIRST(T’)FOLLOW(T)={+,#,),*}第十七页，共二十八页，2022年，8月28日LL(1)分析条件满足构造不带回溯的自上而下分析的文法，即LL（1）文法的判定条件：(1)文法不含左递归。（2）对文法的每个非终结符号A的任何后选首符集两两不相交A→

1|2

|3

…

|n

满足如下条件：

FIRST(i

)FIRST(j

)=（i不等于j）（3）如果某个非终结符号A，如果它的某个后选式首符集包含，那么FIRST(A)FOLLOW(A)=对于LL（1）文法，可以对其输入串进行有效的不带回溯的自上而下分析：P73第十八页，共二十八页，2022年，8月28日无回溯的自顶向下分析技术先决条件：无递归既没有规则左递归，也没有文法左递归。无回溯性对于任一非终结符号U的规则右部x1|x2|…|xn，其对应的字的头终结符号两两不相交。第十九页，共二十八页，2022年，8月28日例子：判断文法4.3是否是LL（1）文法？E→

E+T|T T→

T*F F→(E)|i（1）消左递归得到

E→

TE’E’→

+TE’|T→

FT’T’→

*FT’|F→(E)|i（满足条件1）（2）对于该文法的每个非终结符，考察其后选式的FIRST（）

E和T只有一个后选式，所以不用考察其FIRST（）；对于E’：FIRST（+TE’

）FIRST（）={+}{}=对于T’：FIRST（*FT’）FIRST（）={*}{}=对于F：FIRST（(E)）FIRST（i）={（}{i}=（所以，该文法也满足条件2）（3）对于含有的产生式E’::=+TE’|和T’::=*FT’|

因为FIRST（E’

）FOLLOW（E’

）={+，

}{#,)}=FIRST（T’

）FOLLOW（T’

）={*，

}{+,#,)}=

（满足条件3）第二十页，共二十八页，2022年，8月28日递归下降分析技术（实现思想）实现思想：识别程序由一组过程组成。每个过程对应于一个非终结符号。每一个过程的功能是：选择正确的右部，扫描完相应的字。在右部中有非终结符号时，调用该终结符号对应的过程来完成。第二十一页，共二十八页，2022年，8月28日递归下降技术（实例）文法G4.3E→E+T|T T→T*F F→(E)|i消左递归得到

E→TE’ E’→+TE’| T→FT’ T’→*FT’| F→(E)|i第二十二页，共二十八页，2022年，8月28日递归分析程序的优点实现思想简单明了。程序结构和语法规则有直接的对应关系。因为每个过程表示一个非终结符号的处理，添加语义加工工作比较方便。需要书写程序的语言支持递归调用。如果递归调用机制是高效的，那么分析程序也是高效的。第二十三页，共二十八页，2022年，8月28日预测分析表利用预测分析表进行预测分析预测分析表的构造当我们需要将U选择某个规则展开时，如果当前的输入为a，表示我们要将U展开为以a为首符号的字。如果有规则U::=u，且aFIRST(u)，那么表示这个规则是个好的选择。第二十四页，共二十八页，2022年，8月28日分析表构造算法对于每个规则U→u，执行一下步骤对于每个终结符号aFIRST(u)，A[U,a]=‘U→u’.如果FIRST(y)，对于每个FOLLOW(U)中的每个终结符号b和#，让A[U,b]=‘U→’。将其它为定义的分析表元素为ERROR。第二十五页，共二十八页，2022年，8月28日分析表的例子文法G4.3’[E]:E→TE