第四章语法分析自上而下分析精选文档.ppt

《第四章语法分析自上而下分析精选文档.ppt》由会员分享，可在线阅读，更多相关《第四章语法分析自上而下分析精选文档.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章语法分析自上而下分析本讲稿第一页，共二十八页引言引言在词法分析完成之后，进入语法分析阶段。在词法分析完成之后，进入语法分析阶段。语法分析是编译过程的语法分析是编译过程的核心核心。其任务是：。其任务是：在词法分析识别出的在词法分析识别出的单词符号串单词符号串的基础上，的基础上，分析并判定程序的分析并判定程序的语法结构语法结构是否符合是否符合语法语法规则规则。语法分析的基础语法分析的基础上下文无关文法上下文无关文法语法分析的语法分析的输入：单词符号串输入：单词符号串输出：程序的内部中间表示形式。输出：程序的内部中间表示形式。本讲稿第二页，共二十八页语法分析器语法分析器完成语法分析的程序，其工

2、作完成语法分析的程序，其工作的实质是的实质是按文法产生式，识别输入符号串是按文法产生式，识别输入符号串是否为一个句子。否为一个句子。具体来说，就是看能否从文法的开始符号出发，具体来说，就是看能否从文法的开始符号出发，推导出输入串（单词符号组成的有限序列），推导出输入串（单词符号组成的有限序列），即能否建立一个与输入串相匹配的语法分析树。即能否建立一个与输入串相匹配的语法分析树。以建立与输入串相匹配的语法分析树的不同，以建立与输入串相匹配的语法分析树的不同，语法分析树分为：语法分析树分为：自上而下的语法树自上而下的语法树自下而上的语法树自下而上的语法树4.1 语法分析器的功能语法分析器的功能本讲

3、稿第三页，共二十八页4.2 自上而下分析面临的问题自上而下分析面临的问题自上而下分析的实质：自上而下分析的实质：从推导的角度看，从文从推导的角度看，从文法的开始符号出发，自上而下，推出句子。（一般法的开始符号出发，自上而下，推出句子。（一般是最左推导）是最左推导）自上而下分析的主旨：自上而下分析的主旨：对任何输入串，试图对任何输入串，试图尝试一切可能的办法，文法的开始符号（根节点）尝试一切可能的办法，文法的开始符号（根节点）出发，试图自上而下建立一个语法树，其末端节出发，试图自上而下建立一个语法树，其末端节点正好与输入符号串相同。点正好与输入符号串相同。本讲稿第四页，共二十八页例例4.1（1）

4、S x A y（2）A *|*SSxAy=x*y=x*y=x*ySxAySxAy*=x*y回溯*=x*y=x*y=x*y本讲稿第五页，共二十八页上述过程面临的一些问题上述过程面临的一些问题左递归问题回溯成功的暂时性不成功时找不到出错的位置效率底、代价高（穷尽一切方法）解决方法：解决方法：消除文法的左递归找出克服回溯的充分必要条件本讲稿第六页，共二十八页1.1 消除直接左递归消除直接左递归P PP P|P P P PP P P P|例4.2 P69P PP P 1 1|P|P 2 2|P|P m m|1 1|2 2|n nP P 1 1P P|2 2P P|n nP PP P 1 1P P|2

5、2P P|m m P P|本讲稿第七页，共二十八页1.2 消除间接左递归消除间接左递归间接左递归的含义间接左递归的含义P70 消除间接左递归的算法消除间接左递归的算法用代入的方用代入的方法变间接左递归为直接左递归，然后用公法变间接左递归为直接左递归，然后用公式消除左递归式消除左递归本讲稿第八页，共二十八页例子例子4.3文法文法G4.2E:=E+T|TT:=T*F|FF:=(E)|i消左递归得到消左递归得到E:=TEE:=+TE|T:=FTT:=*FT|F:=(E)|i本讲稿第九页，共二十八页2.1 消除回溯消除回溯为什么要消除回溯？为什么要消除回溯？无回溯就意味着不用做无谓的尝试。无回溯就意味

6、着不用做无谓的尝试。如何消除回溯？如何消除回溯？对于任一非终结符号对于任一非终结符号A的产生式的右部的后选式：的产生式的右部的后选式：1|2|n，如果其对应的第一个终结符号，如果其对应的第一个终结符号两两各不相同，那么两两各不相同，那么A在匹配过程中就不用试探在匹配过程中就不用试探了，而是根据所面临的输入符号了，而是根据所面临的输入符号a唯一确定用哪唯一确定用哪个后选式匹配，即该后选式的成败全权代表了个后选式匹配，即该后选式的成败全权代表了A。本讲稿第十页，共二十八页 G是一个不带左递归的文法，对于是一个不带左递归的文法，对于G的所有非终结符的所有非终结符的每个的每个后选后选 定义其终结首符集

7、：定义其终结首符集：FIRST（）=a|a，a VT FIRST(u)包含了包含了u对应的字的所有可能的首终结符号。对应的字的所有可能的首终结符号。FirstFirst（X X）的求法如下）的求法如下(书书P78)P78)：1 1）若）若X X是终结符或是终结符或，则，则FirstFirst（X X）=X=X。2 2）若）若X X是非终结符，则对于每个产生式是非终结符，则对于每个产生式 XXXX1 1 X X2 2X Xn n,a a）FirstFirst（X X）包含）包含First(XFirst(X1 1)-)-。b b）若对于某个）若对于某个inin，所有，所有First(XFirst(

8、X1 1).First(X).First(Xi i)都包括了都包括了，则，则First(X)First(X)包括包括First(XFirst(Xi+1i+1)-)-。c c）若所有集合）若所有集合First(XFirst(X1 1).First(X).First(Xn n)包括包括，则，则FirstFirst（X X）包括）包括。若若，则规定，则规定 First First（）如果非终结符如果非终结符A A的所有后选首符集两两不相交，则当要求的所有后选首符集两两不相交，则当要求A A匹配输入匹配输入串时，串时，A A就能根据它所面临的第一个输入符号就能根据它所面临的第一个输入符号a a准确指派

9、某个后选准确指派某个后选去匹配。去匹配。*本讲稿第十一页，共二十八页FIRST（）求法示例）求法示例文法G4.2E:=TEE:=+TE|T:=FTT:=*FT|F:=(E)|iFIRST（E）=FirstFirst（T T）=First=First（F F）=First=First（）并）并FirstFirst（i i）=（，（，i i FIRST（E）=FirstFirst（+TE+TE）并并 FirstFirst（）=+，FIRST（T）=FirstFirst（*FT）并并 FirstFirst（）=*，本讲稿第十二页，共二十八页提取公因子提取公因子将文法改造成任何非终结符的所将文法改造成

10、任何非终结符的所有首符集两两不相交的方法有首符集两两不相交的方法P P 1 1|2 2|n n|1 1|2 2|m m（每个（每个 不以不以 开头）开头）P P A A|1 1|2 2|m mA A 1 1|2 2|n n本讲稿第十三页，共二十八页自动匹配自动匹配文法不含左递归，也满足任何非终结符文法不含左递归，也满足任何非终结符的所有首符集两两不相交的要求，要进行有效的自上的所有首符集两两不相交的要求，要进行有效的自上而下的语法分析，还要考虑空字的自动匹配问题。而下的语法分析，还要考虑空字的自动匹配问题。例子：对文法4.2 输入串i+i自上而下的分析：=i+ii+ii+iTFi T+EETE

11、i FT 由于由于E只有一个后选式只有一个后选式TE，i FirstFirst（TETE），所以用），所以用E TEE TE进行推导进行推导由于由于i i FirstFirst（i i），所以用），所以用F iF i推导推导由于由于i FirstFirst（FTFT），所以用），所以用T FTT FT进行进行推导推导从从T T 出发继续匹配，而输入字符出发继续匹配，而输入字符 +不输入不输入FirstFirst（T T），但有），但有T T ，所以自动匹配，所以自动匹配本讲稿第十四页，共二十八页自动匹配的条件：自动匹配的条件：当当a是允许在文法的某个句型中跟是允许在文法的某个句型中跟在在A后的

12、终结符时，后的终结符时，A才能自动匹配。才能自动匹配。FOLLOW(A)=a|S A a,a VT其中，如果S A那么#FOLLOW(A)直观地讲：FOLLOW(A)表示了句型中可能紧跟再A后面的终结符号*本讲稿第十五页，共二十八页FOLLOW(B)的算法（书（书P79P79）步骤步骤1文法的开始符号文法的开始符号S，置，置#FOLLOW(B)步骤步骤2如果有规则如果有规则A B ，那么，那么FIRST()中所中所有的非有的非 符号都在符号都在FOLLOW(B)中。中。步骤步骤3如果有规则如果有规则A B或则或则 A B 且且 FIRST()，那么，那么FOLLOW(A)中的一切符号都在中的一

13、切符号都在FOLLOW(B)中。中。注意：步骤注意：步骤3需要重复执行，直到没有哪个非终结需要重复执行，直到没有哪个非终结符号的符号的FOLLOW集合增长为止。集合增长为止。本讲稿第十六页，共二十八页FOLLOW例子文法G4.3E:ETEE+TE|TFTT*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)=+,#,),*本讲稿第十七页，共二十八页LL(1)分析条件满足构造不带回溯的自

14、上而下分析的文法，即满足构造不带回溯的自上而下分析的文法，即LL（1）文法的判定条件：）文法的判定条件：(1)文法不含左递归。文法不含左递归。（2）对文法的每个非终结符号）对文法的每个非终结符号A 的任何后选首符集两两不的任何后选首符集两两不相交相交A 1 1|2 2|3 3|n n 满足如下条件：满足如下条件：FIRST(i i)FIRST(j j)=（i不等于不等于j）（3）如果）如果某个非终结符号某个非终结符号A，如果它的某个后选，如果它的某个后选式首符集包含式首符集包含 ，那么，那么FIRST(A)FOLLOW(A)=对于对于LL（1）文法，可以对其输入串进行有效的不）文法，可以对其输

15、入串进行有效的不带回溯的自上而下分析：带回溯的自上而下分析：P73本讲稿第十八页，共二十八页无回溯的自顶向下分析技术先决条件：无递归既没有规则左递归，也没有文法左递归。无回溯性对于任一非终结符号U的规则右部x1|x2|xn，其对应的字的头终结符号两两不相交。本讲稿第十九页，共二十八页例子：判断文法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只有

16、一个后选式，所以不用考察其只有一个后选式，所以不用考察其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）本讲稿第二十页，共二十八页递归下降分析技术（实现思想）实现思想：识别程序由一组过程组成。每个过程对应于

17、一个非终结符号。每一个过程的功能是：选择正确的右部，扫描完相应的字。在右部中有非终结符号时，调用该终结符号对应的过程来完成。本讲稿第二十一页，共二十八页递归下降技术（实例）文法G4.3E E+T|TT T*F F(E)|i消左递归得到E TEE +TE|T FTT *FT|F(E)|i本讲稿第二十二页，共二十八页递归分析程序的优点实现思想简单明了。程序结构和语法规则有直接的对应关系。因为每个过程表示一个非终结符号的处理，添加语义加工工作比较方便。需要书写程序的语言支持递归调用。如果递归调用机制是高效的，那么分析程序也是高效的。本讲稿第二十三页，共二十八页预测分析表利用预测分析表进行预测分析预测

18、分析表的构造当我们需要将U选择某个规则展开时，如果当前的输入为a，表示我们要将U展开为以a为首符号的字。如果有规则U:=u，且a FIRST(u)，那么表示这个规则是个好的选择。本讲稿第二十四页，共二十八页分析表构造算法对于每个规则U u，执行一下步骤对于每个终结符号a FIRST(u)，AU,a=U u.如果 FIRST(y)，对于每个FOLLOW(U)中的每个终结符号b和#，让AU,b=U 。将其它为定义的分析表元素为ERROR。本讲稿第二十五页，共二十八页分析表的例子文法G4.3E:E TEE +TE|T FTT *FT|F(E)|ii+*)#(ETETEE+TETFTFTT*FTFi(

19、E)本讲稿第二十六页，共二十八页分析表的冲突文法G4.6S S iCtSS|aS eS|C bFIRST(iCtSS)=iFIRST(eS)=eFIRST(S)=i,aFIRST(C)=bFIRST(S)=e,FOLLOW(S)=FOLLOW(S)=#,eabeit#SaiCtSSSeS;Cb 本讲稿第二十七页，共二十八页作业：P82 3（4）答:(1)不含左递归 (2)对于对于S：FIRST（aSe）FIRST（B）=a b,c,d=对于对于B：FIRST（bBe）FIRST（C）=b c,d=对于对于C：FIRST（cCe）FIRST（d）=c d=结论:是LL（1）文法本讲稿第二十八页，共二十八页