cha4自上而下语法分析wh.ppt

第四章第四章 语法分析语法分析 自上而下分析自上而下分析 n n 内容回顾内容回顾 n n 4.1 4.1 语法分析器的功能语法分析器的功能 n n 4.2 4.2 自上而下分析面临的问题自上而下分析面临的问题 uu回溯回溯公共左因子公共左因子 uu无限循环无限循环左递归左递归 n n 4.3 LL(1)4.3 LL(1)分析法分析法 uu不带回溯的自上而下分析条件不带回溯的自上而下分析条件 uuLL(1)LL(1)文法文法 n n 4.4 4.4 递归下降分析程序构造递归下降分析程序构造 n n 4.5 4.5 预测分析程序预测分析程序 n n 4.6 LL(1)4.6 LL(1)分析中的错误处理分析中的错误处理 n n 本章练习本章练习 n n 作业作业 课程目录课程目录 Date1 内容回顾内容回顾 n句型、句子和语言的定义 n句型 u有文法GS，若S =*，且*, 则 称是是文法G的一个句型 n句子 u有文法GS，若S =*，且T* ,则 称是是文法G的一个句子 n语言 u由文法 G 产生的所有句子的集合 L(G)=|S=+,且VT* Date2 内容回顾内容回顾( (续续) ) n最左(最右)推导 u在推导的任何一步=*(其中和是句型)， 都对中的最左(最右)非终结符进行替换 n句型分析(句子分析) u识别一个符号串是否为某文法的句型(句子)的过 程 u也就是某文法的某个推导的构造过程 n n 设文法设文法G G为为: : E E+T|T E E+T|T T T*F|F T T*F|F F (E)|i F (E)|i n n 请问符号串请问符号串i+i*ii+i*i是是 否为该文法的句子否为该文法的句子? ? E E E + TE + T T * FT * F F F F F T T i i i i i i 自自 上上 而而 下下 自自 下下 而而 上上 章节目录章节目录 Date3 4.14.1语法分析的功能语法分析的功能 p67 p67 n任务 u分析并判定输入的单词符 号串是否符合该语言的语 法规则(上下文无关文法) n实质 u就是按照文法的产生式， 识别输入符号串是否为一 个句子(合法程序，语句 ， 表达式等) 词法扫描器词法扫描器 语法分析器语法分析器 语义处理语义处理 单词符号单词符号 语法树语法树 Date4 语法分析器的设计思想和输出语法分析器的设计思想和输出 n设计思想 u判断是否能从文法的开始符号出发推导 出这个输入串 u或者,判断能否建立一棵与输入串匹配的 语法分析树 n输入 单词符号串 n输出 语法分析树 u格式化的程序 u合法的表达式、语句、函数 n出错处理要求 u尽快发现错误，准确定位 u可能时进行恢复处理，继续语法分析 Date5 常用语法分析方法常用语法分析方法 p66 p66 n语法分析算法可分为两大类: n自上而下分析法 u从文法的开始符号出发，反复使用各种产生式 向 下推导，寻找与输入符号串匹配的推导 n自下而上分析法 u从输入串开始，逐步进行归约，直至归约到文 法 的开始符号 n两种方法反映了两种不同的语法树的构造过 程 u自上而下从树根推导到树叶 u自下而上从树叶归约到树根 Date6 上下文无关文法（型文法）上下文无关文法（型文法） n编程语言的语法大都可用2型文法来描 述没有一种方法能够有效地分析所有上 下文 无关文法 u存在无法处理的2型文法 n每种方法能够处理一部分上下文无关文 法 u每种方法都有适用范围 章节目录章节目录 Date7 4.2 自上而下分析面临的问题 p67 n基本方法 u对任何输入串,试图从文法的开始符号出发 ， 自上而下地为输入串建立一棵语法树， 或者说为输入串寻找一个最左推导。 n过程本质 u是一种试探过程，是反复使用不同产生式谋 求匹配输入串的过程如何选择哪个产生式进 行推导? Date8 自上而下分析举例自上而下分析举例 p67 p67 n例 文法GS SxAy Aab|a n 判断输入串 w = x a y是否为该文法的句子 ？ S S x x A Ay y 试探试探 a a b b 失败失败回溯回溯 a a 试探成功试探成功分析结束分析结束 S S x xA Ay y=x xa ay y= 问题问题 产生回溯的产生回溯的原因原因是什么是什么? ? Date9 自上而下分析面临的问题自上而下分析面临的问题 p68 p68 n公共左因子产生回溯 u例 文法G: S xAy A ab|a u无法确定非终结符A面临输入 符 号a时选用哪个关于A的候 选式 n左递归无限循环 u例 文法G: S Sa|aba w = abaaaw = abaaa S S S S a a S S a a uu无法确定何时用无法确定何时用SabaSaba产生式产生式 进行推导进行推导 n n某些文法导致自上而下分析具有不确定性某些文法导致自上而下分析具有不确定性 章节目录章节目录 Date10 4.3 LL(1)4.3 LL(1)分析法分析法 p68 p68 为了构造不带回溯的自上而下分析算 法 n消除文法的左递归 n消除回溯、提取左因 子 nLL(1)分析条件 uLL(1)文法 章节目录章节目录 Date11 4.3.1 4.3.1 左递归的消除左递归的消除 p69 p69 关于非终结符P的规则 n直接左递归定义：若P P 、 * n例如 E E + TT（含有E的左递归 ） T T * FF（含有T的左递归 ） F ( E )i Date12 间接左递归的定义间接左递归的定义 p68 p68 n间接左递归定义： 若P =+ P * n例如 间接左递归 S Aa A Sb|b S =Aa=Sba 即S=+Sb n用S的产生式右部替换A右部的S得： A Aab|b 变成A的产生式含有直接左递归 Date13 消除直接左递归的方法消除直接左递归的方法 p69 p69 改写为等价的右递归 n形如：P P 非，不以P开始 n改写为：PP（P为新增加的非终结符 ） PP n改写前产生式可产生短语 P=P= 改写后产生式可产生短语 P= P = P = 等价等价 Date14 举例：表达式文法直接左递归的举例：表达式文法直接左递归的 消除消除 nE E + T T nT T * F F nF ( E ) i nE T E E + T E nT F T T * F T nF ( E )i Date15 消除多个直接左递归消除多个直接左递归 p69 p69 n n若有多个左递归的产生式如：若有多个左递归的产生式如： PPPP 1 1 | | PP 2 2 | | | PP m m | | 1 1 | | 2 2 | n n n n消除左递归后变为：消除左递归后变为： P P 1 1 P |P | 2 2 P| P| n n PP P P 1 1 P | P | 2 2 P| P| m m P| P| n n消除左递归要求文法：消除左递归要求文法： 1. 1.无回路（无回路（A =A = * * A A） 2. 2.无空产生式（无空产生式（A A ） Date16 消除直接左递归课堂练习 n例如有文法： KKa | Kb| Kc | d | e BEGIN n n消除左递归后变为：消除左递归后变为： K K d dK |K |e eK K K K a aK | K | b bK| K| c cK|K| Date17 间接左递归消除举例 p70 S Qcc Q Rbb R Saa S=Qc=Rbc=Sabc 是间接左递归 消除方法1： n 将非终结符排序： R Q S n 将R的右部代入Q，S ： Q Sababb S Qcc （不变 ） n 将Q的右部代入S： S Sabcabcbcc n 消除S的直接左递归： S abcSbcS|cS SabcS| Q Sabab|b R Saa n 整理化简：删除Q，R（无用） n 消除左递归后得： S abcSbcS|cS SabcS| Date18 间接左递归消除举例（续） p70 S Qcc Q Rbb R Saa 消除方法2： n 将非终结符排序： S Q R n 将S的右部代入Q，R ： Q Rbb（不变 ） R Qcaca|a n n 将将Q Q的右部代入的右部代入R R： R R RbRbcacab bca|ca|aca|ca|a n n 消除消除R R的直接左递归：的直接左递归： R bcaR R bcaRcaR|aRcaR|aR RbcaR| RbcaR| n n 整理化简：整理化简：S S，Q Q（有用）（有用） n n 消除左递归后得：消除左递归后得： S Qc S Qcc c Q Rb Q Rbb b R bcaR R bcaRcaR|aRcaR|aR RbcaR| RbcaR| Date19 消除左递归算法 p70 1.以某种顺序将文法的非终结符排列 P1，P2，,Pn 2.FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如PiPj的规则改写成 Pi1|2|k,其中 Pj1|2|k是关于Pj的所有规则; 消除Pi的直接左递归 END 3.化简由2所得的文法，即去除那些从开始符号 出发永远无法到达的非终结符的产生式 n 当非终结符的排列顺序不 同时，变换后的文法形式 可能不同，但是它们都和 原文法是等价的 节目录节目录 Date20 4.3.2 4.3.2 消除回溯、提左因子消除回溯、提左因子 p71 p71 n消除回溯目的 u对文法的任何非终结符，当它去匹配输入串 时，能够根据输入符号，准确地选择合适的候 选式去匹配 u若需要非终结符A去匹配输入串，A的候选式 为A1| 2 | n ， A所面临的第一个 输入符号为a时，A能准确地选择i去执行匹 配任务，则无需回溯 Date21 提取公共左因子方法提取公共左因子方法 p71 p71 n对于所有形如 uA12.n的规则 其中，为左因子，不以开头 n改写为 uAA 其中A为新增加的非终结符 A12.n n例如 S xAy A ab|a n n提左因子后变换为提左因子后变换为 S xAy S xAy A A a aAA A A b| b| 节目录节目录 Date22 4.3.3 LL(1)分析条件 p71 nFIRST集合的定义与计算 nFOLLOW集合的定义与计算 nLL(1)文法的定义 nLL(1)分析 节目录节目录 Date23 FIRST()集合的定义 p71 n 设G=(T，N，S，P） * n FIRST()=a|=* a ，aT u若=*，则FIRST() uFIRST()是的所有可能推导的首遇终 结符号或，是选择产生式的依据 a E T E E + T E T F T T * F T F ( E )i nFIRST(E) = ( （E）=0（E） nFIRST（TE） =（，i TE=FTE=（E） TE TE=FTE=iTE Date24 FIRST()FIRST()的计算法的计算法 nFIRST()= a =* a ，aT u若 =*，则 FIRST() n计算文法符号X的FIRST（X） n计算文法符号串=X1X2Xn的FIRST() Date25 FIRST( X )FIRST( X )的计算法的计算法 p78 p78 重复以下计算，直到FIRST（X）不再增大为止 : 1) 若 XT，则 FIRST( X ) = X 。 例 FIRST（+）=+ FIRST（i）=i 2) 若 XN， 若有Xa，则将 a 加入FIRST(X)； 例 E+TE +FIRST（E） F（E）|i （，iFIRST（F） 若有X ，则将加入FIRST( X )。 例 E FIRST（E） Date26 uu若有若有X X Y Y 1 1 Y Yi-1i-1 Y Yi i YY k k ，并对于某个 并对于某个i i， 有有1ji-11ji-1，FIRSTFIRST（Y Y j j ），）， 即即Y Y1 1 ，Y Yi-1i-1= * * ， 则将所有则将所有FIRST( YFIRST( Y j j )-FIRST( Y )-FIRST( Y i i )- )- 加入加入FIRST( X )FIRST( X )中；中； - - n n3)3)若有若有 X X Y Y，且，且 Y Y N N ， 则则 FIRST(Y)- FIRST(Y)-加入加入FIRST(X);FIRST(X); 例例 F F( (E)|E)|i i FIRST(F)= FIRST(F)=（，i i TTF FT FIRST(T)T FIRST(T)=FIRST(=FIRST(F F)-)- =（，i i uu若所有若所有Y Y 1 1 ,Y,Y k k = * * ，则将，则将加入到加入到 FIRST( X ) FIRST( X )。 Date27 计算计算XYXY 1 1 YYi-1i-1 Y Yi i YY k k FIRST(X) FIRST(X)集举例集举例 若有文法G为： X Y1 Y2 Y3 Y4 Y5 Y1 a Y2 b Y3 c Y4 d Y5 ef FIRSTFIRST集集 Y Y1 1 Y Y2 2 Y Y3 3 Y Y4 4 Y Y5 5 X X a a， b b， c c， d d， e e，f f a,a,b,b,c,c,d,d, e,fe,f 因为因为Y Y 5 5 = * * ， 所以所以FIRSTFIRST（X X） = * * = * * 因为因为Y Y 5 5 = * * ， 所以所以FIRSTFIRST（X X） Date28 计算表达式文法计算表达式文法FIRST(X)FIRST(X)集举例集举例 文法G为： E T E E+ T E T F T T* F T F ( E )i n n先找以先找以终结符开头终结符开头的产生式的产生式 FIRST( F ) = ( ,i FIRST( F ) = ( ,i FIRST( E ) = + FIRST( E ) = + ， FIRST( T ) = * , FIRST( T ) = * , n n再找右部以再找右部以非终结符开头非终结符开头的产生式的产生式 FIRST( T ) = FIRST( F )FIRST( T ) = FIRST( F ) FIRST( E ) = FIRST( T )FIRST( E ) = FIRST( T ) = ( ,i = ( ,i Date29 计算计算FIRST(X)FIRST(X)集合课堂练习集合课堂练习 =a=a，c c，d d，q q 文法文法GG为：为： S ApS ApBqBq A aA acA cA B dBB dB BEGINBEGIN n n 先找以先找以终结符开头终结符开头的产生式的产生式 FIRST(A)= a ,c FIRST(A)= a ,c FIRST(B)= d ,FIRST(B)= d , n n 再找右部以再找右部以非终结符开头非终结符开头的产生式的产生式 FIRST(S)= FIRST(A)-FIRST(S)= FIRST(A)- FIRST(B)-FIRST(B)- 因为因为B=B= FIRST(S),FIRST(S),因为因为S=S= * * FIRST(q)FIRST(q) Date30 FIRST() FIRST() 的计算法的计算法 设设=X=X 1 1 X X 2 2 X Xi-1 i-1 X X i i X X n n ，按以下方法构造集合，按以下方法构造集合 则则FIRST(FIRST() = FIRST) = FIRST（ X X 1 1 ) )； n n若任何若任何1ji-11ji-1, ,2in2in, ,FIRST ( FIRST ( X X j j ) ) 则则X X i i 前所有前所有FIRST( FIRST( X X j j )-)- 和和FIRST( FIRST( X X i i ) ) 加入到加入到 FIRST() FIRST() 中；中； n n若所有的若所有的1jn1jn，FIRST( FIRST( X X j j ) ) 则把则把也加入也加入FIRST()FIRST()中；中； n n若若=，则，则 FIRST()= FIRST()= n n若若 FIRST( X FIRST( X 1 1 ) ) 即即X1=X1= Date31 计算表达式文法候选式计算表达式文法候选式FIRST()FIRST()集举例集举例 候选式的FIRST集 FIRST(TE)=FIRST(T)=(, i FIRST(+TE)=+ FIRST(FT)=FIRST(F)=(, i FIRST(*FT)=* FIRST(E)=( FIRST(i)=i FIRST()= 文法文法GG为：为： EETETE E E+TE+TE| | T TFTFT T T*FT*FT| | FF(E)(E)| |i i 非终结符的非终结符的FIRSTFIRST集集 FIRST(E)=(,iFIRST(E)=(,i FIRST(E)=+,FIRST(E)=+, FIRST(T)=(,iFIRST(T)=(,i FIRST(T)=*, FIRST(T)=*, FIRST(F)=(,iFIRST(F)=(,i Date32 计算计算FIRST()FIRST()集合课堂练习集合课堂练习 文法文法G G为：为： S S ApApBqBqA A a acAcAB B dBdB 非终结符的非终结符的FIRSTFIRST集集 FIRST(S)=a,c,d,q FIRST(S)=a,c,d,q FIRST(A)=a,cFIRST(A)=a,c FIRST(B)=d, FIRST(B)=d, BEGINBEGIN 候选式的FIRST集 FIRST(Ap)=FIRST(A)=a,c FIRST(Bq)=FIRST(B)- FIRST(q) =d,q FIRST(a)=a FIRST(cA)=c FIRST(dB)=d FIRST()= 小节目录小节目录 Date33 FOLLOW(A)集合的定义 p73 AN n FOLLOW(A)= aS=*Aa，aT u若S=*A，则#FOLLOW（A） #输入串的结束符 也可看作是句子的括号 #S# uFOLLOW(A)表示了句型中可能紧跟在A后面的终结符 号 S Aa E T E E + T E T F T T * F T F ( E )i n ） FOLLOW（E） S = TE = FTE =（E） TE n + FOLLOW（T） S = TE = T+TE n # FOLLOW（E） S =0 E Date34 FOLLOW(A)FOLLOW(A)的计算法的计算法 p79 p79 nFOLLOW(A)= aS=*Aa，aT u若S=*A，则#FOLLOW（A） 重复以下计算，直到每个FOLLOW(A)不再增大为止： n1)将 # 加入到 FOLLOW( S )中 例 # FOLLOW( E ) n2)若AB, 则将FIRST()-加入FOLLOW(B) 例例 ETE FIRST(E)- ETE FIRST(E)-加入加入 FOLLOW(T)FOLLOW(T) TFT FIRST(T)- TFT FIRST(T)-加入加入 FOLLOW(F)FOLLOW(F) Date35 FOLLOW( A ) FOLLOW( A ) 的计算法（续）的计算法（续） n3) 若 A B ，或 A B， 且 =*，即 FIRST()，AB 则将FOLLOW(A)所有元素加入FOLLOW(B) 例例 E E T T EEFOLLOW(E)FOLLOW(E)加入加入 FOLLOW(E)FOLLOW(E) E E T T EE EEFOLLOW(E)FOLLOW(E)加入加入FOLLOW(T)FOLLOW(T) T T F F TT FOLLOW(T)FOLLOW(T)加入加入 FOLLOW(T)FOLLOW(T) T T F F TTFOLLOW(T)FOLLOW(T)加入加入FOLLOW(F)FOLLOW(F)TT Date36 计算表达式文法的计算表达式文法的FOLLOWFOLLOW集举例集举例 n n #FOLLOW#FOLLOW（开始符号）（开始符号） n n 对每个非终结符查看其在产生式右边的出现对每个非终结符查看其在产生式右边的出现 GG：ETE E+TE| TFT T*FT| ETE E+TE| TFT T*FT| F(E)|iF(E)|i #FOLLOW(E)#FOLLOW(E) 相同不需处理相同不需处理 =FIRST(E)-=FIRST(E)-FOLLOW(T)FOLLOW(T) FOLLOW(E)FOLLOW(E) =+,),#=+,),# FOLLOW(F)FOLLOW(F) =FIRST(T)-=FIRST(T)- FOLLOW(T)FOLLOW(T) =*,+,),#=*,+,),# FOLLOW(E)FOLLOW(E) =),#=),# FOLLOW(E)FOLLOW(E)=FOLLOW(E)=FOLLOW(E)=),#=),# FOLLOW(T)FOLLOW(T)=FOLLOW(T)=FOLLOW(T)=+,),#=+,),# Date37 计算计算FOLLOW(A)FOLLOW(A)集合课堂练习集合课堂练习 文法文法GG为：为： S ApS ApBqBqA aA acAcAB dBB dB 非终结符的非终结符的FIRSTFIRST集集 FIRST(S)=a,c,d,q FIRST(S)=a,c,d,q FIRST(A)=a,cFIRST(A)=a,c FIRST(B)=d,FIRST(B)=d, BEGINBEGIN 非终结符非终结符FOLLOWFOLLOW集集 FOLLOW(S)=#FOLLOW(S)=# FOLLOW(A)=FIRST(p)-FOLLOW(A)=FIRST(p)- =p =p FOLLOW(B)=FIRST(q)-FOLLOW(B)=FIRST(q)- =q =q 小节目录小节目录 Date38 i + i # i + i # 的推导过程的推导过程 p72 p72 设有文法设有文法G G ETE ETE E+TE|E+TE| TFT TFT T*FT|T*FT| F(E)|F(E)|i i P79 P79 iFIRST(iFIRST(i i) ) +FIRST(+TE+FIRST(+TE ) +FOLLOW(T+FOLLOW(T ) ) #FOLLOW(E#FOLLOW(E ) ) #FOLLOW(T#FOLLOW(T ) ) i i i i 生成语法分析树生成语法分析树 Date39 推导过程的分析推导过程的分析 n输入输出 u输入：符号串(有序的) u输出：结构化的符号串(树结构) n产生式的选择 u根据当前符号（单词） n语法分析树的表示 u按照使用序列排列的产生式序列 Date40 消除回溯的条件消除回溯的条件 p71 p71 n非终结符A的所有候选首符集两两不相交， 即A的任何两个不同候选和，满足： FIRST() FIRST() = 当要求 A 匹配输入串时，A就能根据它所 面 临的第一个输入符号 a，准确地指派 某一个 候选去执行任务，这个候选就是 那个终结首 符集含 a 的 Date41 非终结符非终结符A A的自动匹配的自动匹配 p73 p73 n当非终结符 A 面临输入符号a，但a不属 于A的任何候选首符集，如果A有候选式 A(A的某个候选首符集包含)，可以 让A自动得到匹配，即A匹配于空字，但 输入符号不读进 n要想让A自动匹配成功，需要考察 FOLLOW(A) Date42 无回溯的自上而下分析的文法的条件无回溯的自上而下分析的文法的条件p73p73 n文法不含左递归 n对于文法的每个非终结符 A 的任何 两 个不同的产生式 A| 1) FIRST()FIRST() = 2) =*和=*不能同时成立 3) 如果=*，则 FISRT()FOLLOW(A)= n满足以上条件的文法称为LL(1)文法 Date43 表达式文法是表达式文法是 LL(1) LL(1) 文法文法 满足条件（3）： E FIRST(+TE)=+ FOLLOW(E)=),# T FIRST(*FT)=* FOLLOW(T)=+,),# 文法G是LL（1）文法 n n 满足条件（满足条件（1 1）：已消除左递归）：已消除左递归 n n 满足条件（满足条件（2 2）：）： FIRST(+TE)=+ FIRST(FIRST(+TE)=+ FIRST()=)= FIRST(*FT)=* FIRST(FIRST(*FT)=* FIRST()=)= FIRST(E)=( FIRST(i)=i FIRST(E)=( FIRST(i)=i n n 文法文法G G： E TE E TE E+TE|E+TE| T FT T FT T*FT|T*FT| F (E)F (E)i i 小节目录小节目录 Date44 LL(1)LL(1)分析分析 p73 p73 n含义 u第一个 L 表示从左向右扫描输入符号串 u第二个 L 表示生成最左推导 u1 表示读入一个符号可确定下一步推导 nLL(1)文法能够对输入串进行有效的 n 无回溯的自上而下分析 Date45 LL(1)LL(1)分析分析 p73 p73 n对于文法G，当面临的输入符号为a，要用 非终结符A进行匹配时，假设A的所有产生 式为 A1| 2 | n 1)若aFIRST(i )，则指派i去执行任 务 2)若a不属于任何候选首符集，则： 若属于某个FIRST(i )且 aFOLLOW(A)，则让A与自动匹配 否则，a的出现是一种语法错误 小节目录小节目录 Date46 4.4 4.4 递归下降分析程序构造递归下降分析程序构造 p74 p74 不带回溯的自上而下分析程 序 分析程序分析程序一组递归过程一组递归过程 每个非终结符每个非终结符 一个子过程一个子过程 LLLL（1 1）文法）文法 构造构造 分析程序从分析程序从开始符号所对应的过程开始符号所对应的过程开始运行开始运行 子过程的功能：子过程的功能： 对相应非终结符对相应非终结符产生式右部进行语法分析产生式右部进行语法分析 Date47 例例 表达式文法的递归下降分析器表达式文法的递归下降分析器 n n消除左递归后的表达消除左递归后的表达 式文法式文法G G为：为： E TE E TE E+TE| E+TE| T FT T FT T*FT| T*FT| F (E)|iF (E)|i n n可以证明可以证明 G G是一个是一个LLLL（1 1）文法）文法 E( )E( ) E( E( ) ) T( )T( ) T( T( ) ) F( )F( ) 5 5个非终结符个非终结符 构造构造 5 5个子过程个子过程 Date48 递归下降分析器构造说明递归下降分析器构造说明 p74 p74 C语言 E（ ） T; E ; EE T T E E （1 1）E E（）：完成对（）：完成对 E E T ET E的右部分的右部分 析析 PASCALPASCAL语言语言 procedure E;procedure E; beginbegin T;T; EE; ; end;end; 右部有非右部有非 终结符时终结符时 ，调用该，调用该 非终结符非终结符 对应的子对应的子 过程来完过程来完 成成 Date49 递归下降分析器构造说明递归下降分析器构造说明 E() if (c=+) p+; T; E; EE T T E E （2 2）EE（）：完成对（）：完成对 E E +T E|+T E|的右部的右部 分析分析 procedure E;procedure E; if sym=if sym=+ + then then begin begin advance; advance; T T; ; EE; ; end end； + + 其它其它 非非+ +字符字符 自动匹配自动匹配 advanceadvance：把输入指针：把输入指针ipip下移一位下移一位 symsym：当前所面临的输入符号：当前所面临的输入符号 Date50 表达式文法的递归下降分析器表达式文法的递归下降分析器 举例举例 C语言练习 T( ) F; T; (3)T(): T (3)T(): T F TF T procedure T;procedure T; beginbegin F F; ; TT; ; end;end; TT F F T T Date51 表达式文法的递归下降分析器表达式文法的递归下降分析器 举例举例 (4)T(): T(4)T(): T* F * F T|T| C C语言练习语言练习 T()T() if (c=if (c=* *) p+; p+; F F; ; TT; ; procedure T;procedure T; if sym=if sym=* * then then begin begin advance; advance; F F; ; TT; ; end end； TT F F * * 其它其它 非非* *字符字符 自动匹配自动匹配 T T Date52 表达式文法的递归下降分析器表达式文法的递归下降分析器 举例举例 (5)F(): F (5)F(): F (E)|i(E)|i E E F F ( ( ) ) i i 其它其它 非非(,i(,i字符出现语法错误字符出现语法错误 procedure F; begin if sym=( then begin advance; E; if sym= ) then advance else error括号不匹配 end else if sym= i then advance else error F面临非（，i输入符号，语法错 误 end Date53 的子程序的子程序 C C语言练习语言练习 F()F() if (c= if (c=( () p+; p+; E E; ; if (c= if (c=) ) p+;) p+; else error; else error; /*/*括号不匹配括号不匹配*/*/ else else if (c= if (c=i i) p+;) p+; else else errorerror; ;/*F/*F面临非面临非(,i(,i输入符号，输入符号， 语法错误语法错误*/*/ E E F F ( ( ) ) i i 其它其它 非非(,i(,i字符出现语法错误字符出现语法错误 Date54 i+i的递归下降分析过程 i i 生成语法分析树 i + i # 匹配成功返回，指针下移 自动匹配，返回 自动匹配，返回 自动匹配，返回 匹配成功继续，指针下移 匹配成功返回，指针下移 分析成 功结束 Date55 递归下降分析程序优缺点分析递归下降分析程序优缺点分析 n优点： u1）直观、简单、可读性好 u2）便于扩充 n缺点： u1) 递归算法的实现效率低 u2) 处理能力相对有限 u3) 通用性差，难以自动生成 Date56 递归下降分析程序课堂练习递归下降分析程序课堂练习 n n 文法文法G G为：为： S (T)|S (T)|a a+S|+S|a a T T T T,S|S ,S|S n n 消除左递归：消除左递归： S (T)|S (T)|a a+S|+S|a a T ST STT T T ， S STT| | n n 提取左因子：提取左因子： S (T)|S (T)|aSaS S +S|S +S| T STT ST T T ， ST|ST| n n 4 4个子程序：个子程序： S S（）（） S S（）（） T T（）（） T T（）（） BEGIN BEGIN Date57 递归下降分析程序课堂练习答案递归下降分析程序课堂练习答案 （1 1）S S (T)|aS(T)|aS S()S() if(c= if(c=( () ) /*/*匹配第一候选式匹配第一候选式*/*/ p+; p+; T T; ; if(c=if(c=) ) p+;) p+; else else errorerror; ; /*/*括号不匹配括号不匹配*/*/ else else if(c= if(c=a a) p+;) p+;SS;/*/*匹配第二候选匹配第二候选 式式*/*/ else else errorerror; ; /*/*语法错误语法错误*/*/ Date58 递归下降分析程序课堂练习答案递归下降分析程序课堂练习答案 (2)S(2)S+S|+S| S() S() if(c=if(c=+ + ) ) p+; p+; S S; ; (3)T (3)T STST T()T() S S; ; TT; ; (4)T,ST(4)T,ST | T()T() if(c=if(c=, ,) p+; p+; S S; ; TT; 章节目录章节目录 Date59 4.5 4.5 预测分析程序预测分析程序p76p76 n简介 n预测分析程序的工作过程 n预测分析表的构造 n综合练习 章节目录章节目录 Date60 预测分析程序简介预测分析程序简介 p76 p76 n实现LL(1)分析的另一种有效方法 n使用一张二维分析表（预测分析表 ）和一个分析栈（文法符号栈）联 合进行控制来实现自上而下分析技 术 节目录节目录 Date61 4.5.14.5.1预测分析程序工作过程预测分析程序工作过程 n n预测分析表实际上是一个矩阵预测分析表实际上是一个矩阵MA,aMA,a MAMA，a =a = A A i i 当当A A面临面临a a时所应选用时所应选用 的候选式的候选式 空空(error)(error) A A不可能与不可能与a a匹配匹配 出现语法错误出现语法错误 待匹配待匹配 栈顶非栈顶非 终结符终结符 所面临所面临 输入符输入符 号号 预测分析表说明预测分析表说明 p76 p76 Date62 表达式文法的预测分析表表达式文法的预测分析表p76p76 MEME，+ = + = E+TEE+TE EE面临面临+ +时选用时选用 E+TEE+TE MTMT，) = ) = T T TT面临）时选用面临）时选用 TT MFMF，* = error* = errorF F面临面临* *时出现语法错误时出现语法错误 请试给出输入串请试给出输入串w=i*i+iw=i*i+i的预测分析过程的预测分析过程? ? Date63 分析栈的说明分析栈的说明 p76 p76 n分析栈用于存放分析过程中的文法符号 toptop stackstack 栈顶指栈顶指 针针 分析栈初始化时：分析栈初始化时： n n栈底压入一个栈底压入一个 # 底底 顶顶 # # S S toptop toptop n n次栈底压入文法开次栈底压入文法开 始符始符S S 入栈操作入栈操作pushpush 出栈操作出栈操作poppop toptop Date64 预测分析器模型预测分析器模型p77p77 输入缓冲区输入缓冲区: a#: a# X X # # 栈栈 总控制程序总控制程序 预测分析表预测分析表 输出输出 所选用所选用 产生式产生式 序列序列 查找查找 Date65 总控程序执行时可能动作总控程序执行时可能动作p77p77 对于任何（X，a） X是栈顶符号 a是面临输入符号 n XT 且 Xa#， 分析成功结束，输入串是一个合法句子 (2) XT 且 Xa#， X出栈，输入指针指向下一输入符号 (3) XN ，查分析表 M X，a 若 M X，a= Xi， X出栈，i逆序入栈，输入指针不动 若 M X，a= 空， 则调用error程序，进行错误处理 Date66 执行例子：执行例子： i*i+i i*i+i分析过程分析过程 栈 输入缓冲区 所用产生式 0 #E i*i+i# E TE ET入栈 1 #ET i*i+i# T FT 2 #ETF i*i+i# F i 3 #ETi i*i+i# i出栈，a下移 4 #ET *i+i# T*FT 5 #ETF* *i+i# *出栈，a下移 6 #ETF i+i# F i 7 #ETi i+i# i出栈，a下移 Date67 i*i+i i*i+i 分析分析 过程过程 续续 栈 输入缓冲区 所用产生式 8 #ET +i# T 9 #E +i# E +TE 10 #ET+ +i# 11 #ET i# T FT 12 #ETF i# F i 13 #ETi i# 14 #ET # T 15 #