自顶向下语法分析方法完ppt课件

1、第第5章章 自顶向下语法分析方法自顶向下语法分析方法G1S有如下特点：有如下特点： 1 每个产生式的右部由终结符开头每个产生式的右部由终结符开头; 2 同一非终结符的不同产生式的右部由同一非终结符的不同产生式的右部由不同的终结符开头。不同的终结符开头。对于这种文法，在推导过程可以根据当前的对于这种文法，在推导过程可以根据当前的输入符号独一确定选哪个产生式往下推导，输入符号独一确定选哪个产生式往下推导，即分析过程是确定的。即分析过程是确定的。该例阐明，当该例阐明，当1 产生式右部以终结符或非终结符开头无产生式右部以终结符或非终结符开头无空产生式；空产生式；2 同一非终结符的不同产生式的右部由不同

2、同一非终结符的不同产生式的右部由不同的符号开头。的符号开头。对于这种文法，在推导过程选用哪个产生式不直对于这种文法，在推导过程选用哪个产生式不直观，关键是判别产生式右部推出的开场符号观，关键是判别产生式右部推出的开场符号集集First集，分析过程能够是确定的。集，分析过程能够是确定的。文法的特点是：包含空产生式文法的特点是：包含空产生式对于空产生式左部的非终结符，关键是判别对于空产生式左部的非终结符，关键是判别该非终结符的后跟符号集该非终结符的后跟符号集Follow集，集，分析过程能够是确定的。分析过程能够是确定的。例例 文法文法G3S: SaA|d AbAS|由由 S=* S 得得 # FO

3、LLOWS 由由S=aA=abAS=abbASS=abbASaA =abbASd FOLLOWS=#,a,d由由S=* aA 得得 # FOLLOWA 由由S=* abAS=* abAaA 得得 a FOLLOWA =* abAd 得得 d FOLLOWA FOLLOWA=#,a,d文法的特点是文法的特点是:包含空产生式包含空产生式对于空产生式左部的非终结符，关键是判别对于空产生式左部的非终结符，关键是判别该非终结符的后跟符号集，分析过程能该非终结符的后跟符号集，分析过程能够是确定的。够是确定的。假设假设*,那么那么SELECTA=FIRST假设假设=*, 那么那么SELECTA=FIRST-

4、FOLLOWAq例例 G3S:q SaA q Sd q AbAS q ASELECTSaA=SELECTSd=SELECTAbAS=SELECTA=假设假设*,那么那么SELECTA=FIRST假设假设=*, 那么那么SELECTA=FIRST-FOLLOWAFIRSTaA=FIRSTd=FIRSTbAS=FOLLOWA=#,a,bbda可确定可确定不可确定不可确定5.2 LL1文法的判别q要判别一个上下文无关文法能否是要判别一个上下文无关文法能否是LL1文法文法q分为五步：分为五步：q 1. 求出能推出求出能推出的非终结符集的非终结符集q 2. 计算每个产生式右部计算每个产生式右部的的FIR

5、ST集集q 3. 计算每个非终结符计算每个非终结符A的的FOLLOWA集集q 4. 计算每个产生式计算每个产生式A的的SELECTA集集q 5. 按按LL1文法的定义判别文法的定义判别步骤：步骤：1第第1次扫描次扫描扫描文法中的产生式扫描文法中的产生式对能直接推出对能直接推出的产生式左部的终结符标的产生式左部的终结符标“是。是。删除一切右部含有终结符的产生式。假设删除一切右部含有终结符的产生式。假设以某一非终结符为左部的一切产生式以某一非终结符为左部的一切产生式都被删除，那么该非终结符不能推出都被删除，那么该非终结符不能推出，将其标为将其标为“否。否。2. 计算每个产生式右部计算每个产生式右部

6、的的FIRST集集2. 计算每个产生式右部计算每个产生式右部的的FIRST集集Xn 3计算每个非终结符计算每个非终结符A的的FOLLOWA集集1.对一切对一切AVN令令FollowA= ;对开场符对开场符S，令令FollowS=# 由于由于S=*S，显然，显然#FOLLOWS2. 对每条产生式对每条产生式AxBy，调查产生式右部的每一非，调查产生式右部的每一非终结符终结符B， x,y V*，假设，假设y不能推出不能推出 FollowB=FollowBFirsty,否那么否那么,假设假设y *， FollowB=FollowBFirsty- FollowA3. 反复反复2，直至对一切，直至对一切

7、AVN，FollowA收收敛为止。敛为止。假 设假 设 a F O L L O W A , 那 么 阐 明那 么 阐 明S=*Aa， 由于由于AxBy，且，且y=*,那么有那么有 S=*Aa=xBya=xBa，即即S=*xBa, 所以所以aFOLLOWB5. 按按LL1文法的定义判别文法的定义判别产生式的产生式的select集如下集如下:SELECTSAB= b,a,#SELECTSbC=bSELECTA= a,c,#SELECTAb= bSELECTB= #SELECTBaD=aSELECTCAD= b,a,cSELECTCb =bSELECTDaS= aSELECTDc= c 由于由于 S

8、ELECTSABSELECTSbC=b SELECTCADSELECTCb=b所以文法所以文法GS不是不是LL1文法文法一个上下文无关文法是一个上下文无关文法是LL1文法的充沛文法的充沛必要条件是，对每个非终结符必要条件是，对每个非终结符A的两个不同的两个不同产生式产生式A与与 A，满足，满足SELECTASELECTA=q非非LL1文法文法q含有左公共因子的文法含有左公共因子的文法q假设文法中含有形如：假设文法中含有形如：A|r 的的产生式，称文法含有左公共因子。产生式，称文法含有左公共因子。q显然显然,qSELECTASELECTA r,文法不是文法不是LL1文法文法 5.3 某些非某些非

9、LL1文法到文法到 LL1文法的等价变文法的等价变换换含有左递归的文法含有左递归的文法文法中只需含有以下方式的产生式含有文法中只需含有以下方式的产生式含有或含有或二者皆有，那么称文法含有左递或含有或二者皆有，那么称文法含有左递归归:AAAB BA在中含有左递归的产生式，称为直接左递在中含有左递归的产生式，称为直接左递归；归；在中虽然没有含左递归的产生式，在中虽然没有含左递归的产生式，但但A=B=A 即即A=+ A,称为间接称为间接左递归左递归. 5.3 某些非某些非LL1文法到文法到 LL1文法的等价变文法的等价变换换以直接左递归为例，假设有如下产生式以直接左递归为例，假设有如下产生式AA A

10、A | |AA其中其中和和为恣意语法符号串。为恣意语法符号串。不难证明有下面关系式：不难证明有下面关系式：SelectSelect AA AA First First A A FirstFirst SelectSelect A A First First 故故AAAA和和AA的的SelectSelect集相交，不是集相交，不是LLLL1 1文法文法 5.3 某些非某些非LL1文法到文法到 LL1文法的等价变文法的等价变换换A A A A 不知何时终了不知何时终了不确定不确定假设假设*,那么那么SELECTA=FIRST假设假设=*, 那么那么SELECTA=FIRST-FOLLOWAq对非对非

11、LL1文法进展等价变换文法进展等价变换q提取左公共因子提取左公共因子q消除左递归消除左递归q留意：变换后的文法不一定是留意：变换后的文法不一定是LL1文法，文法不含左递归和左公共因子只文法，文法不含左递归和左公共因子只是是LL1文法的必要条件。文法的必要条件。 5.3 某些非某些非LL1文法到文法到 LL1文法的等价变文法的等价变换换将产生式将产生式A|r 等价变换为等价变换为: A|r，将括号内用一新引入的非终结符将括号内用一新引入的非终结符A表示表示,得得 AA，A|r普通方式：假设普通方式：假设A1|2|n,提取左公共因子后变为提取左公共因子后变为 A1|2|n ， 引进新的非终结符引进

12、新的非终结符A，得：，得： AA，A 1|2|n假设在假设在i中仍含有左公共因子中仍含有左公共因子,可再次提取可再次提取.1、提取左公因子、提取左公因子q例文法例文法G1：qSaSb|aS|q 提左因子得提左因子得:SaSb|q 引进新的非终结符引进新的非终结符S得得:qSaSS|qS b|1、提取左公因子、提取左公因子1消除直接左递归消除直接左递归文法文法G:SSa|b可改写成可改写成 SbSS aS|普通情形普通情形:含直接左递归的文法含直接左递归的文法G：AA1|A2|Am|1|2|n消除左递归后改写成：消除左递归后改写成： A1A|2A|nA A1 A|2 A|m A| 2、消除左递归

13、、消除左递归2消除间接左递归消除间接左递归将间接左递归变成直接左递归，再加以消除。将间接左递归变成直接左递归，再加以消除。算法步骤：算法步骤：把文法的一切非终结符按任一顺序陈列，把文法的一切非终结符按任一顺序陈列，如：如：A1，A2，An从从A1开场，按以下顺序处置开场，按以下顺序处置Ai。首先，消除左部为首先，消除左部为Ai的产生式的直接左递归；的产生式的直接左递归；然后，假设左部为然后，假设左部为Ai的产生式的右部为非终结符的产生式的右部为非终结符Ajj* ，且，且FollowA FirstbAS =b ，从而引起，从而引起回溯回溯q例例3 3q文法文法G G：SSaSSa SbSbq输入

14、串输入串w=baaw=baa，推导树为，推导树为: :SSabSbSSa回溯回溯回溯回溯SSaSaSSaSab由于文法含有左递归而引起回溯由于文法含有左递归而引起回溯5.5 确定的自顶向下分析方法确定的自顶向下分析方法q确定的自顶向下分析方法有：确定的自顶向下分析方法有：q递归子程序法递归子程序法recursive-descent parserq预测分析法预测分析法predictive parserq两种方法都要求文法是两种方法都要求文法是LL1文法。文法。q实现思想：实现思想：q 对应文法中每个非终结符编写对应文法中每个非终结符编写一个递归过程，识别由该非终结符推一个递归过程，识别由该非终结

15、符推出的串。当非终结符有多条产生式时，出的串。当非终结符有多条产生式时，按当前输入符属于哪条产生式的按当前输入符属于哪条产生式的SELECT集可独一确定选择哪个产生集可独一确定选择哪个产生式进展匹配。式进展匹配。q当识别到终结符时，与当前输入符号当识别到终结符时，与当前输入符号匹配，并读取下一输入符；匹配，并读取下一输入符；q当识别到非终结符时，那么调用该非当识别到非终结符时，那么调用该非终结符相应的过程。终结符相应的过程。5.5.1 递归子程序法递归子程序法5.5.1 递归子程序法递归子程序法由于递归子程序法对每个过程能够存在直由于递归子程序法对每个过程能够存在直接或间接递归调用，所以对某个

16、过程在退接或间接递归调用，所以对某个过程在退出之前能够又被调用，因此有些信息需求出之前能够又被调用，因此有些信息需求保管，通常在入口时需保管某些信息，出保管，通常在入口时需保管某些信息，出口时需恢复口时需恢复先进后出栈。先进后出栈。优点：优点：简单直观、易于构造简单直观、易于构造缺陷：缺陷：对文法要求高，必需是对文法要求高，必需是LL1文法文法递归调用多，速度慢，占用空间多递归调用多，速度慢，占用空间多5.5.2 预测分析方法预测分析方法一个预测分析器由三个部分组成：一个预测分析器由三个部分组成：预测分析程序：控制分析过程的进展。预测分析程序：控制分析过程的进展。分析栈：存放从文法开场符号动身

17、的自顶向下推分析栈：存放从文法开场符号动身的自顶向下推导过程中等待匹配的文法符号。开场时放入导过程中等待匹配的文法符号。开场时放入#和文法开场符，终了时栈应是空的。和文法开场符，终了时栈应是空的。预测分析表：是一张二维表，元素预测分析表：是一张二维表，元素MA,a的内容的内容是当非终结符是当非终结符A面临输入符号面临输入符号a终结符或句子终结符或句子括号时应选取的产生式，当无产生式时，括号时应选取的产生式，当无产生式时，元素内容为转向出错处置。元素内容为转向出错处置。构造预测分析表构造预测分析表步骤：步骤：1 把文法转变为把文法转变为LL1文法文法2 求出每条产生式的求出每条产生式的SELEC

18、T集集3 按照按照SELECT集把产生式填入分集把产生式填入分析表析表对每个终结符或对每个终结符或用用a表示表示假设假设a SELECTA，那么把，那么把A放入放入MA,a中，把一切无定义的中，把一切无定义的MA,a标上出错标志。标上出错标志。例例 算术表达式文法算术表达式文法GGEE+TTEE+TTTTTT* *FFFFFFE Eii1消除消除G的左递归得到文法的左递归得到文法 GETE E+TE TFT T*FTFEi2求出每个产生式的求出每个产生式的select集集,G是是LL1文法文法 SELECTETE = ,i SELECTE+TE = + SELECTE = ,# SELECTT

19、FT = ,i SELECTT*FT = * SELECTT = +,# SELECTFE = SELECTF i = i F EF iFTT T*FTT TT FTT FTTEE E+TEEE#*+iETEETE3 3按照选择集合把产生式填入分析表按照选择集合把产生式填入分析表注：表中空白处为出错注：表中空白处为出错输入串输入串i+i*i#的分析过程的分析过程i+*#EETEETEEE+TEE E TT FTT FTTT T* FTT T FF iF E+匹配匹配 +i*i#ET+7E+TE +i*i#E6T +i*i#ET5i匹配匹配 i+i*i#ETi4Fi i+i*i#ETF3TFT

20、i+i*i#ET2ETE i+i*i#E1所用产生式所用产生式剩余输入串剩余输入串分析栈分析栈步骤步骤TFTi*i#ET8Fi i#ETF13i匹配匹配 i#ETi14T #ET15E #E16接受接受 #17*匹配匹配 *i#ETF*12T *FT *i#ET11i匹配匹配i*i#ETi10Fii*i#ETF9i+*#EETEETEEE+TEE E TT FTFTT FTFTTT T* FTFTT T FF i iF E EP96 例例1文法文法GS:SaHHaMd|dMAb|AaM|e1.判别判别GS能否为能否为LL1文法，假设是，文法，假设是，请构造相应的请构造相应的LL1预测分析表。预

21、测分析表。2.假设假设GS是是LL1文法，请给出对输入文法，请给出对输入串串aaabd#的预测分析过程，并阐明该输的预测分析过程，并阐明该输入串能否是入串能否是GS的句子。的句子。思绪：思绪：1 1、判别、判别GSGS能否为能否为LLLL1 1文法，假设是，请构造文法，假设是，请构造相应的相应的LLLL1 1预测分析表。预测分析表。判别能否为判别能否为LLLL1 1文法文法5 5个步骤个步骤求出能推出求出能推出 的非终结符；的非终结符；FIRSTFIRST集集FOLLOWFOLLOW集集SELECTSELECT集集判别判别构造预测分析表构造预测分析表2.2.假设假设GSGS是是LLLL1 1文

22、法，请给出对输入串文法，请给出对输入串aaabd#aaabd#的预测分析过程，并阐明该输入串能否是的预测分析过程，并阐明该输入串能否是GSGS的的句子。句子。预测分析过程匹配胜利即阐明是该文法的句子。预测分析过程匹配胜利即阐明是该文法的句子。判别能否为判别能否为LLLL1 1文法文法5 5个步骤个步骤求出能推出求出能推出 的非终结符；的非终结符； 由文法可得，能推出由文法可得，能推出 的非终结符为的非终结符为MM求求FIRSTFIRST集集求求FOLLOWFOLLOW集集求求SELECTSELECT集的交集集的交集 Select SelectHHaMdaMdSelectSelectHHd d=ad=ad= Select SelectMMAbAbSelectSelectMM =a,ed,b=a,ed,b= Select SelectA AaMaMSelectSelectA Ae e=ae=ae=判别：该文法是判别：该文法是LLLL1 1文法。文法。GS:SaHHaMd|dMAb|AaM|e非终结符非终结符FIRST集集FOLLOW集集SHMAaa,da,e, a,e,#d,bb构造预测分析表构造预测分析表