《第四章语法分析自上而下分析精选PPT.ppt》由会员分享，可在线阅读，更多相关《第四章语法分析自上而下分析精选PPT.ppt（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章语法分析自上而下分析第1页，此课件共28页哦引言引言在词法分析完成之后，进入语法分析阶段。在词法分析完成之后，进入语法分析阶段。语法分析是编译过程的语法分析是编译过程的核心核心。其任务是：。其任务是：在词法分析识别出的在词法分析识别出的单词符号串单词符号串的基础上，的基础上，分析并判定程序的分析并判定程序的语法结构语法结构是否符合是否符合语法语法规则规则。语法分析的基础语法分析的基础上下文无关文法上下文无关文法语法分析的语法分析的输入：单词符号串输入：单词符号串输出：程序的内部中间表示形式。输出：程序的内部中间表示形式。第2页，此课件共28页哦语法分析器语法分析器完成语法分析的程序，其工
2、作完成语法分析的程序，其工作的实质是的实质是按文法产生式，识别输入符号串是否按文法产生式，识别输入符号串是否为一个句子。为一个句子。具体来说，就是看能否从文法的开始符号出具体来说，就是看能否从文法的开始符号出发，推导出输入串（单词符号组成的有限序发，推导出输入串（单词符号组成的有限序列），即能否建立一个与输入串相匹配的语列），即能否建立一个与输入串相匹配的语法分析树。法分析树。以建立与输入串相匹配的语法分析树的不同，以建立与输入串相匹配的语法分析树的不同，语法分析树分为：语法分析树分为：自上而下的语法树自上而下的语法树自下而上的语法树自下而上的语法树4.1 语法分析器的功能语法分析器的功能第3
3、页，此课件共28页哦4.2 自上而下分析面临的问题自上而下分析面临的问题自上而下分析的实质：自上而下分析的实质：从推导的角度看，从文从推导的角度看，从文法的开始符号出发，自上而下，推出句子。（一般法的开始符号出发，自上而下，推出句子。（一般是最左推导）是最左推导）自上而下分析的主旨：自上而下分析的主旨：对任何输入串，试图对任何输入串，试图尝试一切可能的办法，文法的开始符号（根节点）尝试一切可能的办法，文法的开始符号（根节点）出发，试图自上而下建立一个语法树，其末端节出发，试图自上而下建立一个语法树，其末端节点正好与输入符号串相同。点正好与输入符号串相同。第4页，此课件共28页哦例例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第5页，此课件共28页哦上述过程面临的一些问题上述过程面临的一些问题左递归问题回溯成功的暂时性不成功时找不到出错的位置效率底、代价高（穷尽一切方法）解决方法：解决方法：消除文法的左递归找出克服回溯的充分必要条件第6页，此课件共28页哦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|第7页，此课件共28页哦1.2 消除间接左递归消除间接左递归间接左递归的含义间接左递归的含义P70 消除间接左递归的算法消除间接左递归的算法用代入的用代入的方法变间接左递归为直接左递归，然后用方法变间接左递归为直接左递归，然后用公式消除左递归公式消除左递归第8页，此课件共28页哦例子例子4.3文法文法G4.2E:=E+T|TT:=T*F|FF:=(E)|i消左递归得到消左递归得到E:=TEE:=+TE|T:=FTT:=*FT|F:=(E)|i第9页，此课件共28页哦2.1 消除回溯消除回溯为什么要消除回溯？为什么要消除回溯？无回溯就意味着不用做无谓的尝试。无回溯就意味
6、着不用做无谓的尝试。如何消除回溯？如何消除回溯？对于任一非终结符号对于任一非终结符号A的产生式的右部的后选式：的产生式的右部的后选式：1|2|n，如果其对应的第一个终结符号，如果其对应的第一个终结符号两两各不相同，那么两两各不相同，那么A在匹配过程中就不用试探在匹配过程中就不用试探了，而是根据所面临的输入符号了，而是根据所面临的输入符号a唯一确定用哪唯一确定用哪个后选式匹配，即该后选式的成败全权代表了个后选式匹配，即该后选式的成败全权代表了A。第10页，此课件共28页哦 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、派准确指派某个后选去匹配。某个后选去匹配。*第11页，此课件共28页哦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（）=*，第12页，此课件共28页哦提取公因子提取公因子将文法改造成任何非终结符的所有将文法改
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第13页，此课件共28页哦自动匹配自动匹配文法不含左递归，也满足任何非终结文法不含左递归，也满足任何非终结符的所有首符集两两不相交的要求，要进行有效的符的所有首符集两两不相交的要求，要进行有效的自上而下的语法分析，还要考虑空字的自动匹配问自上而下的语法分析，还要考虑空字的自动匹配问题。题。例子：对文法4.2 输入串i+i自上而下的分析：=i+ii+ii+iTFi T+EET
11、Ei 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 ，所以自动匹，所以自动匹配配第14页，此课件共28页哦自动匹配的条件：自动匹配的条件：当当a是允许在文法的某个句型中跟是允许在文法的某个句型中跟在在A后
12、的终结符时，后的终结符时，A才能自动匹配。才能自动匹配。FOLLOW(A)=a|S A a,a VT其中，如果S A那么#FOLLOW(A)直观地讲：FOLLOW(A)表示了句型中可能紧跟再A后面的终结符号*第15页，此课件共28页哦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集合增长为止。集合增长为止。第16页，此课件共28页哦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)=+,#,),*第17页，此课件共28页哦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第18页，此课件共28页哦无回溯的自顶向下分析技术先决条件：无递归既没有规则左递归，也没有文法左递归。无回溯性对于任一非终结符号U的规则右部x1|x2|xn，其对应的字的头终结符号两两不相交。第19页，此课件共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只
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）第20页，此课件共28页哦递归下降分析技术（实现思想）实现思想：识别程序由一组过程组成。每个过程对应
17、于一个非终结符号。每一个过程的功能是：选择正确的右部，扫描完相应的字。在右部中有非终结符号时，调用该终结符号对应的过程来完成。第21页，此课件共28页哦递归下降技术（实例）文法G4.3E E+T|TT T*F F(E)|i消左递归得到E TEE +TE|T FTT *FT|F(E)|i第22页，此课件共28页哦递归分析程序的优点实现思想简单明了。程序结构和语法规则有直接的对应关系。因为每个过程表示一个非终结符号的处理，添加语义加工工作比较方便。需要书写程序的语言支持递归调用。如果递归调用机制是高效的，那么分析程序也是高效的。第23页，此课件共28页哦预测分析表利用预测分析表进行预测分析预测分析
18、表的构造当我们需要将U选择某个规则展开时，如果当前的输入为a，表示我们要将U展开为以a为首符号的字。如果有规则U:=u，且a FIRST(u)，那么表示这个规则是个好的选择。第24页，此课件共28页哦分析表构造算法对于每个规则U u，执行一下步骤对于每个终结符号a FIRST(u)，AU,a=U u.如果 FIRST(y)，对于每个FOLLOW(U)中的每个终结符号b和#，让AU,b=U 。将其它为定义的分析表元素为ERROR。第25页，此课件共28页哦分析表的例子文法G4.3E:E TEE +TE|T FTT *FT|F(E)|ii+*)#(ETETEE+TETFTFTT*FTFi(E)第26页，此课件共28页哦分析表的冲突文法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 第27页，此课件共28页哦作业：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）文法第28页，此课件共28页哦