编译原理PPT学习教案

1、会计学1编译编译(biny)原理原理第一页，共109页。VN)VN)* *n开始符开始符S S至少必须在某个至少必须在某个(mu )(mu )产生式的左部出现一次。产生式的左部出现一次。第1页/共109页第二页，共109页。第2页/共109页第三页，共109页。1n 。n例：对文法例：对文法(1)nE (E) (E+E) (i+E)(i+i)第3页/共109页第四页，共109页。通常，用通常，用 表示：从表示：从 1 1出发，经过一步或出发，经过一步或若干步，可以推出若干步，可以推出 n n。n1n*1 用用 表示：从表示：从 1 1出发，经过出发，经过0 0步或步或若干步，可以推出若干步，可

2、以推出 n n。* 所以所以 ： 即即 或或,|)(*TV SGLq定义：假定定义：假定G G是一个文法，是一个文法，S S 是它的开始符号。是它的开始符号。如果如果 ，则，则 称是一个称是一个句型句型。仅含终结符。仅含终结符号的句型是一个号的句型是一个句子句子。文法。文法G G所产生的句子的全所产生的句子的全体是一个体是一个语言语言，将它记为，将它记为 L(G)L(G)。*S 第4页/共109页第五页，共109页。4.1 语法分析器的功能(gngnng)第5页/共109页第六页，共109页。源程序源程序单词符号单词符号取下一单词取下一单词.语法分语法分析树析树词法分词法分析器析器语法分语法分

3、析器析器符号表符号表编译程序编译程序后续部分后续部分第6页/共109页第七页，共109页。nLRLR分析法：规范归约分析法：规范归约第7页/共109页第八页，共109页。i+ +* *EiiEEEE第8页/共109页第九页，共109页。用实现对输入串的识别。用实现对输入串的识别。n预测分析程序预测分析程序n优点：直观、简单和宜于手工优点：直观、简单和宜于手工实现。实现。第9页/共109页第十页，共109页。4.2 自上而下分析(fnx)面临的问题立一棵语法树。或者说，为输立一棵语法树。或者说，为输入串寻找一个最左推导。入串寻找一个最左推导。第10页/共109页第十一页，共109页。Sx*yIP

4、Sx*yIPAxySx*yIPAxySx*yIPAxy*Sx*yIPAxy*Sx*yIPAxy*Sx*yIPAxy*第11页/共109页第十二页，共109页。 含有含有(hn yu)(hn yu)左递归的文法将使自上左递归的文法将使自上而下的分析陷入无限循环。而下的分析陷入无限循环。第12页/共109页第十三页，共109页。4.3 LL(1)分析法第13页/共109页第十四页，共109页。左递归的消除(xioch)nPPnPP|左递归变右递归第14页/共109页第十五页，共109页。nP1P | 2P | | mP | 左递归变右递归第15页/共109页第十六页，共109页。n TFTn T*

5、FT | n 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页第十七页，共109页。一个文法一个文法(wnf)消除左递归的条件：消除左递归的条件：不含以不含以为右部的产生式为右部的产生式不含回路。不含回路。第17页/共109页第十八页，共109页。Pi1|2|k ; n (其中其中Pj1|2|k是关于是关于Pj的的所有规则所有规则)n消除

6、关于消除关于Pi规则的直接左递规则的直接左递归性归性n ENDn3. 化简由化简由2所得的文法。去除那所得的文法。去除那些从开始符号出发永远无法到些从开始符号出发永远无法到达的非终结符的产生规则。达的非终结符的产生规则。第18页/共109页第十九页，共109页。nQSab | ab | b第19页/共109页第二十页，共109页。选后，选后，S变成变成nSSabc | abc | bc | c第20页/共109页第二十一页，共109页。nQSab |ab | bnRSa|a第21页/共109页第二十二页，共109页。nRSa|an关于关于Q和和R的规则已是多余的，的规则已是多余的，化简为：化简

7、为：nSabcS | bcS | cSnSabcS | (4.4)第22页/共109页第二十三页，共109页。nRbcaR | caR|a R (4.5)nR bca R | n文法文法(4.4)和和(4.5)的等价性是显的等价性是显然的。然的。第23页/共109页第二十四页，共109页。消除回溯(hu s)、提左因子Sa.IPA.第24页/共109页第二十五页，共109页。 特别是，若特别是，若 ，则规定，则规定FIRST( )。* 如果非终结符如果非终结符A的所有候选首符集两两不相交的所有候选首符集两两不相交(xingjio)，即，即A的任何两个不同候选的任何两个不同候选 i和和 j FI

8、RST(i)FIRST( j) 当要求当要求A匹配输入串时，匹配输入串时，A就能根据它所面临的就能根据它所面临的第一个输入符号第一个输入符号a，准确地指派某一个候选前去，准确地指派某一个候选前去执行任务。这个候选就是那个终结首符集含执行任务。这个候选就是那个终结首符集含a的的。第25页/共109页第二十六页，共109页。nA 1 | 2 | | nn经过反复提取左因子，就能够经过反复提取左因子，就能够把每个非终结符把每个非终结符(包括新引进者包括新引进者)的所有候选首符集变成为两两的所有候选首符集变成为两两不相交。不相交。第26页/共109页第二十七页，共109页。分析(fnx)条件第27页/

9、共109页第二十八页，共109页。i + i IPEnG(E): ETE E +TE | TFT T *FT | F(E) | i第28页/共109页第二十九页，共109页。i + i IPETEnG(E): ETE E +TE | TFT T *FT | F(E) | i第29页/共109页第三十页，共109页。i + i IPETEFTnG(E): ETE E +TE | TFT T *FT | F(E) | i第30页/共109页第三十一页，共109页。i + i IPETEFTinG(E): ETE E +TE | TFT T *FT | F(E) | i第31页/共109页第三十二页

10、，共109页。i + i IPETEFTinG(E): ETE E +TE | TFT T *FT | F(E) | i第32页/共109页第三十三页，共109页。i + i IPETEFTi nG(E): ETE E +TE | TFT T *FT | F(E) | i第33页/共109页第三十四页，共109页。i + i IPETEFTi +TEnG(E): ETE E +TE | TFT T *FT | F(E) | i第34页/共109页第三十五页，共109页。i + i IPETEFTi +TEnG(E): ETE E +TE | TFT T *FT | F(E) | i第35页/共

11、109页第三十六页，共109页。i + i IPETEFTi +TEFTnG(E): ETE E +TE | TFT T *FT | F(E) | i第36页/共109页第三十七页，共109页。i + i IPETEFTi +TEFTinG(E): ETE E +TE | TFT T *FT | F(E) | i第37页/共109页第三十八页，共109页。i + i IPETEFTi +TEFTinG(E): ETE E +TE | TFT T *FT | F(E) | i第38页/共109页第三十九页，共109页。i + i IPETEFTi +TEFTi nG(E): ETE E +TE

12、| TFT T *FT | F(E) | i第39页/共109页第四十页，共109页。i + i IPETEFTi +TEFTi nG(E): ETE E +TE | TFT T *FT | F(E) | iS T+第40页/共109页第四十一页，共109页。AS*特别是，若特别是，若 ，则规定，则规定 FOLLOW(A)分析(fnx)条件第41页/共109页第四十二页，共109页。n构造不带回溯的自上而下分析的文法条件构造不带回溯的自上而下分析的文法条件n1. 文法不含左递归，文法不含左递归，n2. 对于文法中每一个非终结符对于文法中每一个非终结符A的各个的各个(gg)产产生式的候选首符集两

13、两不相交。即，若生式的候选首符集两两不相交。即，若nA 1| 2| nn 则则 FIRST( i)FIRST( j) (ij)n3. 对文法中的每个非终结符对文法中的每个非终结符A，若它存在某个候，若它存在某个候选首符集包含选首符集包含，则，则nFIRST( i)FOLLOW(A)=ni=1,2,.,nn如果一个文法如果一个文法G满足以上条件，则称该文法满足以上条件，则称该文法G为为LL(1)文法。文法。第42页/共109页第四十三页，共109页。n (1) 若若属于某个属于某个FIRST(i )且且aFOLLOW(A)， 则让则让A与与自自动匹配动匹配(ppi)。n (2) 否则，否则，a的

14、出现是一种语法的出现是一种语法错误。错误。第43页/共109页第四十四页，共109页。回顾(hug)：LL(1)分析法第44页/共109页第四十五页，共109页。nP1P | 2P | | mP | 第45页/共109页第四十六页，共109页。Pi1|2|k ; n (其中其中Pj1|2|k是是关于关于Pj的所有规则的所有规则)n消除关于消除关于Pi规则的直接左递规则的直接左递归性归性n ENDn3. 化简由化简由2所得的文法。去除所得的文法。去除(q ch)那些从开始符号出发永远无那些从开始符号出发永远无法到达的非终结符的产生规则。法到达的非终结符的产生规则。第46页/共109页第四十七页，

15、共109页。回顾(hug)：LL(1)分析法第47页/共109页第四十八页，共109页。消除(xioch)回溯、提左因子Sa.IPA.第48页/共109页第四十九页，共109页。.,|=)(*TVaaaFIRST 特别是，若特别是，若 ，则规定，则规定FIRST( )。* 如果非终结符如果非终结符A的所有候选首符集两两不相交，即的所有候选首符集两两不相交，即A的任何两个不同候选的任何两个不同候选 i和和 j FIRST(i)FIRST( j) 当要求当要求A匹配输入串时，匹配输入串时，A就能根据它所面临的第就能根据它所面临的第一个输入符号一个输入符号a，准确地指派，准确地指派(zhpi)某一个

16、候选前某一个候选前去执行任务。这个候选就是那个终结首符集含去执行任务。这个候选就是那个终结首符集含a的的。第49页/共109页第五十页，共109页。nA 1 | 2 | | nn经过反复提取左因子，就能够经过反复提取左因子，就能够(nnggu)把每个非终结符把每个非终结符(包包括新引进者括新引进者)的所有候选首符集的所有候选首符集变成为两两不相交。变成为两两不相交。第50页/共109页第五十一页，共109页。i + i IPETEFTi +TEn ETE E +TE | TFT T *FT | F(E) | i第51页/共109页第五十二页，共109页。.,.|)(*TVaAaSaAFOLLO

17、WAS*特别是，若特别是，若 ，则规定，则规定 FOLLOW(A)FOLLOW定义(dngy)第52页/共109页第五十三页，共109页。n构造构造(guzo)不带回溯的自上而下分析的文不带回溯的自上而下分析的文法条件法条件n1. 文法不含左递归，文法不含左递归，n2. 对于文法中每一个非终结符对于文法中每一个非终结符A的各个产生的各个产生式的候选首符集两两不相交。即，若式的候选首符集两两不相交。即，若nA 1| 2| nn 则则 FIRST( i)FIRST( j) (ij)n3. 对文法中的每个非终结符对文法中的每个非终结符A，若它存在某，若它存在某个候选首符集包含个候选首符集包含，则，则

18、nFIRST( i)FOLLOW(A)=ni=1,2,.,nn如果一个文法如果一个文法G满足以上条件，则称该文法满足以上条件，则称该文法G为为LL(1)文法。文法。第53页/共109页第五十四页，共109页。n (1) 若若属于某个属于某个FIRST(i )且且aFOLLOW(A)， 则让则让A与与自自动匹配。动匹配。n (2) 否则，否则，a的出现是一种语法的出现是一种语法错误。错误。第54页/共109页第五十五页，共109页。第55页/共109页第五十六页，共109页。a中；若中；若X也是一条产生式，也是一条产生式，则把则把也加到也加到FIRST(X)中。中。第56页/共109页第五十七页

19、，共109页。第57页/共109页第五十八页，共109页。FIRST()中。显然，若中。显然，若则则FIRST()。第58页/共109页第五十九页，共109页。第59页/共109页第六十页，共109页。3. 3. 若若AAB B是一个是一个(y )(y )产生式，或产生式，或A AB B是一个是一个(y )(y )产生产生式而式而 ( (即即FIRST(FIRST() )， 则把则把FOLLOW(A)FOLLOW(A)加至加至FOLLOW(B)FOLLOW(B)中。中。第60页/共109页第六十一页，共109页。 FIRST(E) =(,iFIRST(E) =(,iFIRST(EFIRST(E

20、 )=+, )=+, 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) =* *,+,),#,+,),#第61页/共109页第六十二页，共109页。4.4 递归下降(xijing)分析程序构造第62页/共109页第

21、六十三页，共109页。n，nERRORERROR，出错处理子程序，出错处理子程序第63页/共109页第六十四页，共109页。应的子程序。应的子程序。第64页/共109页第六十五页，共109页。PROCEDURE E；BEGIN T；E END；PROCEDURE E ； IF SYM=+ THEN BEGINADVANCE； T；E END第65页/共109页第六十六页，共109页。PROCEDURE T；BEGIN F；T ENDPROCEDURE T ；IF SYM=* THENBEGIN ADVANCE； F；T END；例例: :文法文法(wnf)G(E):(wnf)G(E):ETEE

22、TEE E+TE+TE | | TFTTFT T T* *FTFT | | F(E) | iF(E) | i对应的递归下降子程序为对应的递归下降子程序为: : 第66页/共109页第六十七页，共109页。例例: :文法文法G(E):G(E):ETEETEE E+TE+TE | | TFTTFT T T* *FTFT | | F(E) | iF(E) | i对应对应(duyng)(duyng)的递归下降子程序为的递归下降子程序为: : 第67页/共109页第六十八页，共109页。主程序主程序:PROGRAM PARSER;BEGIN ADVANCE; E; IF SYM # THEN ERROR

23、END;第68页/共109页第六十九页，共109页。ETE | BCPROCEDURE E；BEGINIF SYM FIRST(TE) THEN T；E ELSE IF SYM FIRST(BC)THENB; CELSE ERROREND；第69页/共109页第七十页，共109页。PROCEDURE E；BEGIN T；E END；PROCEDURE T；BEGIN F；T END第70页/共109页第七十一页，共109页。PROCEDURE E ； IF SYM=+ THEN BEGINADVANCE； T；E END ELSE IF SYM# AND SYM) THEN ERROR第71页

24、/共109页第七十二页，共109页。PROCEDURE T ； IF SYM=* THEN BEGIN ADVANCE； F；T END ELSE IF SYM# AND SYM) AND SYM+ THEN ERROR第72页/共109页第七十三页，共109页。PROCEDURE F； IF SYM=i THEN ADVANCE ELSE IF SYM=( THEN BEGIN ADVANCE; E； IF SYM=) THEN ADVANCE ELSE ERROR END ELSE ERROR;第73页/共109页第七十四页，共109页。主程序主程序:PROGRAM PARSER;BEGI

25、N ADVANCE; EEND;第74页/共109页第七十五页，共109页。扩充的巴科斯范式。扩充的巴科斯范式。文法的另一种(y zhn)表示法和转换图第75页/共109页第七十六页，共109页。归消去和因子归消去和因子(ynz)提取。提取。第76页/共109页第七十七页，共109页。第77页/共109页第七十八页，共109页。T+ETF*TFi)FE(第78页/共109页第七十九页，共109页。PROCEDURE E；BEGIN T； WHILE SYM=+ DO BEGIN ADVANCE； T ENDEND；第79页/共109页第八十页，共109页。PROCEDURE T；BEGIN F

26、； WHILE SYM=* DO BEGIN ADVANCE； F ENDEND；第80页/共109页第八十一页，共109页。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页第八十二页，共109页。 1. 文法不含左递归，文法不含左递归，2. 对于文法中每一个非终结符对于文法中每一个非终结符A的各个产生式的候的各个产生式的候选首符集两两不相交选首符集两两不相交(xingjio)。即，若

27、。即，若A 1| 2| n 则则 FIRST( i)FIRST( j) (ij)3. 对文法中的每个非终结符对文法中的每个非终结符A，若它存在某个候选，若它存在某个候选首符集包含首符集包含，则，则FIRST( i)FOLLOW(A)=i=1,2,.,n如果一个文法如果一个文法G满足以上条件，则称该文法满足以上条件，则称该文法G为为LL(1)文法。文法。回顾：LL(1)文法(wnf)条件第82页/共109页第八十三页，共109页。非终结符出发进行展开非终结符出发进行展开( (推导推导) )时，就调用这个非终结符对应时，就调用这个非终结符对应的子程序。的子程序。回顾(hug)：构造不带回溯的自上而

28、下分析器第83页/共109页第八十四页，共109页。4.5 预测(yc)分析程序文法符号文法符号第84页/共109页第八十五页，共109页。总控程序总控程序分析表分析表X#输入串输入串分析栈分析栈STACKa1a2.ai#预测分析程序的工作图预测分析程序的工作图# Sa1a2.ai#分析开始时：分析开始时：第85页/共109页第八十六页，共109页。q总控程序根据现行总控程序根据现行(xinxng)栈顶符号栈顶符号X和当和当前输入符号前输入符号a，执行下列三种动作之一，执行下列三种动作之一:q1. 若若Xa，则宣布分析成功，停，则宣布分析成功，停止分析。止分析。q2. 若若Xa ，则把，则把X

29、从从STACK栈顶栈顶逐出，让逐出，让a指向下一个输入符号。指向下一个输入符号。匹配(ppi)成功第86页/共109页第八十七页，共109页。3. 若若X是一个非终结符，则查看分析表是一个非终结符，则查看分析表M。 若若MX，a中存放着关于中存放着关于X的一个产生的一个产生(chnshng)式，把式，把X逐出逐出STACK栈顶，把产生栈顶，把产生(chnshng)式的右部符号串按反序一一推进式的右部符号串按反序一一推进STACK栈栈(若右部符号为若右部符号为，则意味不推什么东，则意味不推什么东西进栈西进栈)。在把产生。在把产生(chnshng)式的右部符号推式的右部符号推进栈的同时应做这个产生

30、进栈的同时应做这个产生(chnshng)式相应的语式相应的语义动作。义动作。若若MX，a中存放着中存放着“出错标志出错标志”，则调用出错诊，则调用出错诊察程序察程序ERROR。推导(tudo)第87页/共109页第八十八页，共109页。匹配(ppi)成功第88页/共109页第八十九页，共109页。STOP /*分析分析(fnx)成功，过程完成功，过程完毕毕*/END分析(fnx)成功推导(tudo)第89页/共109页第九十页，共109页。第90页/共109页第九十一页，共109页。i+*()#EETE ETE E E +TE E E TTFT TFT T T T *FT T T FFiF (

31、E)第91页/共109页第九十二页，共109页。i+*()#EETE ETE E E +TE E E TTFT TFT T T T *FT T T FFiF (E)第92页/共109页第九十三页，共109页。i+*()#EETE ETE E E +TE E E TTFT TFT T T T *FT T T FFiF (E)第93页/共109页第九十四页，共109页。i+*()#EETE ETE E E +TE E E TTFT TFT T T T *FT T T FFiF (E)第94页/共109页第九十五页，共109页。非递归预测(yc)分析器的模型 id + id * id $预测(yc)分析控制程序$输入(shr)栈EETETETFFT