编译原理学习.pptx-淘文阁

资源描述

《编译原理学习.pptx》由会员分享，可在线阅读，更多相关《编译原理学习.pptx（109页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、上下文无关文法的定义：一个上下文无关文法G G是一个四元式 G=(VG=(VT T，V VN N，S S，P)P)，其中V VT T：终结符集合(非空)V VN N：非终结符集合(非空)，且V VT T V VN N=S S：文法的开始符号，S S V VN NP P：产生式集合(有限)，每个产生式形式为P P，P P V VN N，(V VT T V VN N)*开始符S S至少必须在某个产生式的左部出现一次。第1页/共109页例，定义只含+，*的算术表达式的文法 G=，其中，P由下列产生式组成：E iE E+EE E*EE (E)第2页/共109页定义：称 A 直接推出，即 A 仅当A 是

2、一个产生式，且，(VT VN)*。如果 1 2 n，则我们称这个序列是从 1到 n的一个推导。若存在一个从 1到 n的推导，则称 1可以推导出 n。例：对文法(1)E (E)(E+E)(i+E)(i+i)第3页/共109页通常，用通常，用表示：从表示：从 1 1出发，经过一步或若出发，经过一步或若干步，可以推出干步，可以推出 n n。用表示：从 1 1出发，经过0 0步或若干步，可以推出 n n。所以：即或q定义：假定G G是一个文法，S S 是它的开始符号。如果，则称是一个句型。仅含终结符号的句型是一个句子。文法G G所产生的句子的全体是一个语言，将它记为 L(G)L(G)。第4

3、页/共109页4.1 语法分析器的功能语法分析的任务是分析一个文法的句子结构。语法分析器的功能：按照文法的产生式(语言的语法规则)，识别输入符号串是否为一个句子(合式程序)。第5页/共109页源程序单词符号取下一单词.语法分析树词法分析器语法分析器符号表编译程序后续部分第6页/共109页语法分析的方法：自下而上分析法(Bottom-up)(Bottom-up)基本思想：从输入串开始，逐步进行“归约归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。LR

4、LR分析法：规范归约第7页/共109页G(E)：E i|E+E|E-E|E*E|E/E|(E)i*i+i E*i+i E*E+i E+i E+E Ei+*EiiEEEE第8页/共109页语法分析的方法：自下而上分析法(Bottom-up)(Bottom-up)自上而下分析法(Top-down)(Top-down)基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找匹配的推导推导。递归下降分析法：对每一语法变量(非终结符)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。预测分析程序F优点：直观、简单和宜于手工实现。第9页/共109

5、页4.2 自上而下分析面临的问题自上而下就是从文法的开始符号出发，向下推导推导，推出句子。带“回溯”的不带回溯的递归子程序(递归下降)分析方法。自上而下分析的主旨：对任何输入串，试图用一切可能的办法，从文法开始符号(根结点)出发，自上而下地为输入串建立一棵语法树语法树。或者说，为输入串寻找一个最左推导。第10页/共109页例假定有文法G(S):(1)SxAy (2)A*|*分析输入串x*y(记为)。Sx*yIPSx*yIPAxySx*yIPAxySx*yIPAxy*Sx*yIPAxy*Sx*yIPAxy*Sx*yIPAxy*第11页/共109页当某个非终结符有多个产生式候选时，可能带来如下问题

6、:1.1.分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。出错时，不得不“回溯”。2.2.文法左递归问题。一个文法是含有左递归的，如果存在非终结符P P含有左递归的文法将使自上而下的分析陷入无限循环。第12页/共109页4.3 LL(1)分析法构造不带回溯的自上而下分析算法要消除文法的左递归性克服回溯第13页/共109页左递归的消除直接消除见诸于产生式中的左递归：假定关于非终结符P的规则为PP|其中不以P开头。我们可以把P的规则等价地改写为如下的非直接左递归形式：P P P P|左递归变右递归第14页/共109页一般而言，假定P关于的全部产生式是PP 1|P 2|P

7、m|1|2|n其中，每个都不等于，每个都不以P开头那么，消除P的直接左递归性就是把这些规则改写成：P 1P|2P|nP P 1P|2P|mP|左递归变右递归第15页/共109页例文法G(E):EET|TTT*F|FF(E)|i经消去直接左递归后变成：ETE E+TE|TFT T*FT|F(E)|i(4.2)PPP P 1 1|P|P 2 2|P|P mm|1 1|2 2|n nPP 1 1P P|2 2P P|n nP P P P 1 1P P|2 2P P|mmP P|第16页/共109页例如文法G(S):SQc|cQRb|bRSa|a (4.3)虽没有直接左递归，但S、Q、R都是左

11、号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。A 1|2|nSa.IPA.第24页/共109页令G是一个不含左递归的文法，对G的所有非终结符的每个候选定义它的终结首符集FIRST()为：特别是，若，则规定FIRST()。如果非终结符A的所有候选首符集两两不相交，即A的任何两个不同候选 i和 jFIRST(i)FIRST(j)当要求A匹配输入串时，A就能根据它所面临的第一个输入符号a，准确地指派某一个候选前去执行任务。这个候选就是那个终结首符集含a的。第25页/共109页提取公共左因子:假定关于A的规则是 A 1|2|n|1|2|m(其中，每个不以开头)那么，可

12、以把这些规则改写成A A|1|2|mA 1|2|n经过反复提取左因子，就能够把每个非终结符(包括新引进者)的所有候选首符集变成为两两不相交。第26页/共109页 ETE E+TE|TFT T*FT|F(E)|i i +i分析条件第27页/共109页i +i IPEnG(E):ETE E+TE|TFT T*FT|F(E)|i第28页/共109页i +i IPETEnG(E):ETE E+TE|TFT T*FT|F(E)|i第29页/共109页i +i IPETEFTnG(E):ETE E+TE|TFT T*FT|F(E)|i第30页/共109页i +i IPETEFTinG(E):ETE E+T

15、41页/共109页n构造不带回溯的自上而下分析的文法条件1.文法不含左递归，2.对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若A 1|2|n 则 FIRST(i)FIRST(j)(i j)3.对文法中的每个非终结符A，若它存在某个候选首符集包含，则FIRST(i)FOLLOW(A)=i=1,2,.,n如果一个文法G满足以上条件，则称该文法G为LL(1)LL(1)文法文法。第42页/共109页对于一个满足上述条件的文法，可以对其输入串进行有效的无回溯的自上而下分析。假设要用非终结符A进行匹配，面临的输入符号为a，A的所有产生式为A 1|2|n1.若a FIRST(i)，则指

16、派 i执行匹配任务；2.若a不属于任何一个候选首符集，则：(1)若属于某个FIRST(i)且 a FOLLOW(A)，则让A与自动匹配。(2)否则，a的出现是一种语法错误。第43页/共109页回顾：LL(1)分析法构造不带回溯的自上而下分析算法要消除文法的左递归性克服回溯第44页/共109页一般而言，假定P关于的全部产生式是PP 1|P 2|P m|1|2|n其中，每个都不等于，每个都不以P开头那么，消除P的直接左递归性就是把这些规则改写成：P 1P|2P|nP P 1P|2P|mP|第45页/共109页消除左递归的算法:1.把文法G的所有非终结符按任一种顺序排列成P1，P2，Pn；

17、按此顺序执行；2.FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如PiPj 的规则改写成 Pi 1|2|k ;(其中Pj 1|2|k是关于Pj的所有规则)消除关于Pi规则的直接左递归性 END3.化简由2所得的文法。去除那些从开始符号出发永远无法到达的非终结符的产生规则。第46页/共109页回顾：LL(1)分析法构造不带回溯的自上而下分析算法要消除文法的左递归性克服回溯第47页/共109页消除回溯、提左因子为了消除回溯就必须保证：对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果

18、应是确信无疑的。A 1|2|nSa.IPA.第48页/共109页令G是一个不含左递归的文法，对G的所有非终结符的每个候选定义它的终结首符集FIRST()为：特别是，若，则规定FIRST()。如果非终结符A的所有候选首符集两两不相交，即A的任何两个不同候选 i和 jFIRST(i)FIRST(j)当要求A匹配输入串时，A就能根据它所面临的第一个输入符号a，准确地指派某一个候选前去执行任务。这个候选就是那个终结首符集含a的。第49页/共109页提取公共左因子:假定关于A的规则是 A 1|2|n|1|2|m(其中，每个不以开头)那么，可以把这些规则改写成A A|1|2|mA 1|2|n经过反

19、复提取左因子，就能够把每个非终结符(包括新引进者)的所有候选首符集变成为两两不相交。第50页/共109页i +i IPETEFTi+TEn ETE E+TE|TFT T*FT|F(E)|i第51页/共109页假定S是文法G的开始符号，对于G的任何非终结符A，我们定义特别是，若，则规定 FOLLOW(A)FOLLOW定义第52页/共109页n构造不带回溯的自上而下分析的文法条件1.文法不含左递归，2.对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若A 1|2|n 则 FIRST(i)FIRST(j)(i j)3.对文法中的每个非终结符A，若它存在某个候选首符集包含，则FIR

20、ST(i)FOLLOW(A)=i=1,2,.,n如果一个文法G满足以上条件，则称该文法G为LL(1)LL(1)文法文法。第53页/共109页对于一个满足上述条件的文法，可以对其输入串进行有效的无回溯的自上而下分析。假设要用非终结符A进行匹配，面临的输入符号为a，A的所有产生式为A 1|2|n1.若a FIRST(i)，则指派 i执行匹配任务；2.若a不属于任何一个候选首符集，则：(1)若属于某个FIRST(i)且 a FOLLOW(A)，则让A与自动匹配。(2)否则，a的出现是一种语法错误。第54页/共109页构造FIRST()第55页/共109页对每一文法符号X VTVN构造FIRST(

21、X)连续使用下面的规则，直至每个集合FIRST不再增大为止：1.若X VT，则FIRST(X)X。2.若X VN，且有产生式Xa，则把a加入到FIRST(X)中；若X 也是一条产生式，则把也加到FIRST(X)中。第56页/共109页3.l若XY是一个产生式且Y VN，则把FIRST(Y)中的所有非-元素都加到FIRST(X)中；l若XY1Y2Yk是一个产生式，Y1，Yi-1都是非终结符，而且，对于任何j，1 j i-1，FIRST(Yj)都含有(即Y1Yi-1)，则把FIRST(Yi)中的所有非-元素都加到FIRST(X)中；特别是，若所有的FIRST(Yj)均含有，j1，2，k，则把加

22、到FIRST(X)中。第57页/共109页对文法G的任何符号串=X1X2Xn构造集合FIRST()。1.置FIRST()FIRST(X1)；2.若对任何1 j i-1，FIRST(Xj)，则把FIRST(Xi)加至FIRST()中；特别是，若所有的FIRST(Xj)均含有，1 j n，则把也加至FIRST()中。显然，若则FIRST()。第58页/共109页构造FOLLOW(A)第59页/共109页对于文法G的每个非终结符A构造FOLLOW(A)的办法是，连续使用下面的规则，直至每个FOLLOW不再增大为止：1.对于文法的开始符号S，置于FOLLOW(S)中；2.若A B 是一个产生式，则

23、把FIRST()加至FOLLOW(B)中；3.3.若若AA B B是一个产生式，或是一个产生式，或A AB B 是一个产生式而是一个产生式而 (即即FIRST(FIRST()，则把则把FOLLOW(A)FOLLOW(A)加至加至FOLLOW(B)FOLLOW(B)中。中。第60页/共109页例4.6 对于文法G(E)ETE E+TE|TFT T*FT|F(E)|i构造每个非终结符的FIRST和FOLLOW集合：FIRST(E)=(,iFIRST(E)=(,iFIRST(EFIRST(E)=+,)=+,FIRST(T)=(,iFIRST(T)=(,iFIRST(TFIRST(T)=*,)=*,F

24、IRST(F)=(,iFIRST(F)=(,i FOLLOW(E)=),#FOLLOW(E)=),#FOLLOW(EFOLLOW(E)=),#)=),#FOLLOW(T)=+,),#FOLLOW(T)=+,),#FOLLOW(TFOLLOW(T)=+,),#)=+,),#FOLLOW(F)=*,+,),#FOLLOW(F)=*,+,),#第61页/共109页4.4 递归下降分析程序构造构造不带回溯的自上而下分析程序要消除文法的左递归性克服回溯第62页/共109页构造不带回溯的自上而下分析器分析程序由一组递归过程组成，文法中每个非终结符对应一个过程；所以这样的分析程序称为递归下降分析器。(因为文

25、法的定义通常是递归的)几个全局过程和变量：ADVANCE，把输入串指示器IP指向下一个输入符号，即读入一个单字符号SYM，IP当前所指的输入符号ERROR，出错处理子程序第63页/共109页例:文法G(E):G(E):ETE E+TE|TFT T*FT|F(E)|i每个非终结符有对应的子程序的定义，首先在分析过程中，当需要从某个非终结符出发进行展开(推导)时，就调用这个非终结符对应的子程序。第64页/共109页例:文法G(E):G(E):ETE E+TE|TFT T*FT|F(E)|i对应的递归下降子程序为:PROCEDURE E；BEGIN T；E END；PROCEDURE E；IF SY

26、M=+THEN BEGINADVANCE；T；E END第65页/共109页PROCEDURE T；BEGIN F；T ENDPROCEDURE T；IF SYM=*THENBEGIN ADVANCE；F；T END；例例:文法文法G(E):G(E):ETEETE E E+TE+TE|TFTTFT T T*FT*FT|F(E)|iF(E)|i对应的递归下降子程序为对应的递归下降子程序为:第66页/共109页例例:文法文法G(E):G(E):ETEETE E E+TE+TE|TFTTFT T T*FT*FT|F(E)|iF(E)|i对应的递归下降子程序为对应的递归下降子程序为:PROCEDURE

27、 F；IF SYM=i THEN ADVANCE ELSE IF SYM=(THEN BEGIN ADVANCE;E；IF SYM=)THEN ADVANCE ELSE ERROR END ELSE ERROR;第67页/共109页主程序:PROGRAM PARSER;BEGIN ADVANCE;E;IF SYM#THEN ERROREND;第68页/共109页对应的递归下降子程序为:ETE|BCPROCEDURE E；BEGINIF SYM FIRST(TE)THEN T；E ELSE IF SYM FIRST(BC)THENB;CELSE ERROREND；第69页/共109页ETE E+

30、基础上，扩充几个元语言符号：1.用花括号表示闭包运算*。2.用表示 0n可任意重复0次至n次，。3.用方括号表示 01，即表示的出现可有可无(等价于|)。引入上述元符号的文法亦称扩充的巴科斯范式。文法的另一种表示法和转换图第75页/共109页例如，通常的“实数”可定义为：decimalsigninteger.digitexponent exponentEsigninteger integerdigitdigit sign+|-用扩充的巴科斯范式来描述语法，直观易懂，便于表示左递归消去和因子提取。第76页/共109页例4.5 文法ET|E+TTF|T*FFi|(E)可表示成ET+TTF*F

31、Fi|(E)(4.6)第77页/共109页 ET+TTF*FFi|(E)(4.6)可以用语法图来表示语言的文法。T+ETF*TFi)FE(第78页/共109页 ET+TTF*FFi|(E)(4.6)可构造一组递归下降分析程序：PROCEDURE E；BEGIN T；WHILE SYM=+DO BEGIN ADVANCE；T ENDEND；第79页/共109页PROCEDURE T；BEGIN F；WHILE SYM=*DO BEGIN ADVANCE；F ENDEND；ET+TTF*FFi|(E)(4.6)可构造一组递归下降分析程序：第80页/共109页 ET+TTF*FFi|(E)(4.6)

32、可构造一组递归下降分析程序：PROCEDURE F；IF SYM=i THEN ADVANCE ELSE IF SYM=(THEN BEGIN ADVANCE;E；IF SYM=)THEN ADVANCE ELSE ERROR END ELSE ERROR;第81页/共109页 1.文法不含左递归，2.对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若A 1|2|n 则 FIRST(i)FIRST(j)(i j)3.对文法中的每个非终结符A，若它存在某个候选首符集包含，则FIRST(i)FOLLOW(A)=i=1,2,.,n如果一个文法G满足以上条件，则称该文法G为LL(1)

33、LL(1)文法文法。回顾：LL(1)文法条件第82页/共109页分析程序由一组递归过程组成，文法中每个非终结符对应一个过程；所以这样的分析程序称为递归下降分析器。(因为文法的定义通常是递归的)每个非终结符有对应的子程序的定义，首先在分析过程中，当需要从某个非终结符出发进行展开(推导)时，就调用这个非终结符对应的子程序。回顾：构造不带回溯的自上而下分析器第83页/共109页4.5 预测分析程序一、预测分析程序工作原理预测分析程序或LL(1)分析法：总控程序分析表 MA，a矩阵，A VN，a VT 是终结符或，分析栈 STACK 用于存放文法符号第84页/共109页总控程序分析表X#输入串分析栈S

34、TACKa1a2.ai#预测分析程序的工作图#Sa1a2.ai#分析开始时：第85页/共109页q总控程序根据现行栈顶符号X和当前输入符号a，执行下列三种动作之一:1.若Xa，则宣布分析成功，停止分析。2.若Xa ，则把X从STACK栈顶逐出，让a指向下一个输入符号。匹配成功第86页/共109页3.若X是一个非终结符，则查看分析表M。若MX，a中存放着关于X的一个产生式，把X逐出STACK栈顶，把产生式的右部符号串按反序一一推进STACK栈(若右部符号为，则意味不推什么东西进栈)。在把产生式的右部符号推进栈的同时应做这个产生式相应的语义动作。若MX，a中存放着“出错标志”，则调用出错诊察程序E

35、RROR。推导第87页/共109页预测分析程序的总控程序：BEGIN 首先把然后把文法开始符号推进STACK栈；把第一个输入符号读进a；FLAG:=TRUE;WHILE FLAG DOBEGIN 把STACK栈顶符号上托出去并放在X中；IF X VT THEN IF X=a THEN 把下一输入符号读进a ELSE ERROR 匹配成功第88页/共109页 ELSE IF X=#THEN IF X=a THEN FLAG:=FALSE ELSE ERROR ELSE IF MX,a=XX1X2XkTHEN 把Xk,Xk-1,X1一一推进STACK栈 /*若X1X2Xk=，不推什么进栈*/ELS

36、E ERROR END OF WHILE;STOP/*分析成功，过程完毕*/END分析成功推导第89页/共109页例4.6 对于文法G(E)ETE E+TE|TFT T*FT|F(E)|i输入串为i1*i2+i3，利用分析表进行预测分析：第90页/共109页步骤符号栈输入串所用产生式0#Ei1*i2+i3#1#E Ti1*i2+i3#ETE 2#E T Fi1*i2+i3#TFT 3#E T ii1*i2+i3#Fi第91页/共109页步骤符号栈输入串所用产生式3#E T ii1*i2+i3#Fi4#E T*i2+i3#5#E T F*i2+i3#T*FT 6#E T F i2+i3#7#E

37、T ii2+i3#Fi第92页/共109页步骤符号栈输入串所用产生7#E T ii2+i3#Fi 8#E T+i3#9#E+i3#T 10#E T+i3#E+TE 11#E Ti3#第93页/共109页步骤符号栈输入串所用产生11#E Ti3#12#E T F i3#TFT 13#E T ii3#Fi14#E T#15#E#T 16#E 第94页/共109页非递归预测分析器的模型 id +id *id$预测分析控制程序$输入栈EETETETFFTEididTET+idE id+TET id+FTE id+idTEF id95第95页/共109页二、分析表MA，a的构造q构造FIRST()和FO

38、LLOW(A)q构造分析表MA，a第96页/共109页构造FIRST()第97页/共109页对每一文法符号X VTVN构造FIRST(X)连续使用下面的规则，直至每个集合FIRST不再增大为止：1.若X VT，则FIRST(X)X。2.若X VN，且有产生式Xa，则把a加入到FIRST(X)中；若X 也是一条产生式，则把也加到FIRST(X)中。第98页/共109页3.若XY是一个产生式且Y VN，则把FIRST(Y)中的所有非-元素都加到FIRST(X)中；若XY1Y2Yk是一个产生式，Y1，Yi-1都是非终结符，而且，对于任何j，1 j i-1，FIRST(Yj)都含有(即Y1Yi-1)

39、，则把FIRST(Yi)中的所有非-元素都加到FIRST(X)中；特别是，若所有的FIRST(Yj)均含有，j1，2，k，则把加到FIRST(X)中。第99页/共109页对文法G的任何符号串=X1X2Xn构造集合FIRST()。1.置FIRST()FIRST(X1)；2.若对任何1 j i-1，FIRST(Xj)，则把FIRST(Xi)加至FIRST()中；特别是，若所有的FIRST(Xj)均含有，1 j n，则把也加至FIRST()中。显然，若则FIRST()。第100页/共109页构造FOLLOW(A)第101页/共109页对于文法G的每个非终结符A构造FOLLOW(A)的办法是，连

40、续使用下面的规则，直至每个FOLLOW不再增大为止：1.对于文法的开始符号S，置于FOLLOW(S)中；2.若A B 是一个产生式，则把FIRST()加至FOLLOW(B)中；3.3.若若AA B B是一个产生式，或是一个产生式，或A AB B 是一个产生式而是一个产生式而 (即即FIRST(FIRST()，则把则把FOLLOW(A)FOLLOW(A)加至加至FOLLOW(B)FOLLOW(B)中。中。第102页/共109页例4.6 对于文法G(E)ETE E+TE|TFT T*FT|F(E)|i构造每个非终结符的FIRST和FOLLOW集合：FIRST(E)=(,iFIRST(E)=(,iF

41、IRST(EFIRST(E)=+,)=+,FIRST(T)=(,iFIRST(T)=(,iFIRST(TFIRST(T)=*,)=*,FIRST(F)=(,iFIRST(F)=(,i FOLLOW(E)=),#FOLLOW(E)=),#FOLLOW(EFOLLOW(E)=),#)=),#FOLLOW(T)=+,),#FOLLOW(T)=+,),#FOLLOW(TFOLLOW(T)=+,),#)=+,),#FOLLOW(F)=*,+,),#FOLLOW(F)=*,+,),#第103页/共109页在对文法G的每个非终结符A及其任意候选都构造出FIRST()和FOLLOW(A)之后，现在可以用它们

42、来构造G的分析表MA，a。1.对文法G的每个产生式A 执行第2步和第3步；2.对每个终结符a FIRST()，把A 加至MA，a中；3.若FIRST()，则对任何b FOLLOW(A)把A 加至MA，b中。4.把所有无定义的MA，a标上“出错标志”。第104页/共109页第105页/共109页如果G是左递归或二义的，那么，M至少含有一个多重定义入口。因此，消除左递归和提取左因子将有助于获得无多重定义的分析表M。可以证明，一个文法G的预测分析表M不含多重定义入口，当且仅当该文法为LL(1)的。第106页/共109页G(S):S iCtS|iCtSeS|aC b提取左因子之后，改写成：G(S):S iCtSS|aS eS|C b最近匹配原则第107页/共109页作业P811，2P823(选作2个)第108页/共109页2023/3/28109感谢您的观看。第109页/共109页

展开阅读全文