语法分析自上而下分析课件.ppt-得力文库

资源描述

《语法分析自上而下分析课件.ppt》由会员分享，可在线阅读，更多相关《语法分析自上而下分析课件.ppt（96页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第四章第四章语法分析语法分析-自上而下分析自上而下分析程程序序设设计计语语言言 2023/2/151Ch4.语法分析-自上而下分析本章在编译程序中的地位本章在编译程序中的地位表格管理词法分析器语法分析器语义分析与中间代码产生优化器目标代码生成器源程序单词符号语法单位中间代码中间代码目标代码出错处理2回顾：语法分析回顾：语法分析n任任务务：在在词词法法分分析析的的基基础础上上，根根据据语语言言的的语语法法规规则则，把把单单词词符符号号串串分分解解成成各各类类语语法法单单位位，如如“短短语语”、“句句子子”、“子子句句”、“程程序序段段”等等，为为语语法法正正确确的的输输入入构构造造语

2、语法法树树(或或分分析析树树)。n语语法法分分析析依依据据的的是是语语言言的的语语法法规规则则，即即描描述述程程序序结结构构的的规规则则，通通过过语语法法分分析析确确定定整整个个输输入入串串是否构成一个语法上正确的程序。是否构成一个语法上正确的程序。n语法规则通常用语法规则通常用上下文无关文法上下文无关文法描述。描述。n语法分析方法有语法分析方法有自上而下自上而下和和自下而上自下而上两类。两类。n本本章章和和下下一一章章将将介介绍绍编编译译程程序序构构造造中中的的一一些些典典型的语法分析方法型的语法分析方法。3典型的语法分析方法典型的语法分析方法n自上而下自上而下语法分析方法语法分析方法第四

3、章介绍第四章介绍 n递归子程序法递归子程序法n预测分析法，即预测分析法，即LL(1)LL(1)法法 n自下而上自下而上语法分析方法语法分析方法第五章介绍第五章介绍 n算符优先分析法算符优先分析法n规范归约法规范归约法nLRLR方方法法：LR(0)LR(0)、SLR(1)SLR(1)、LR(1)LR(1)、LALR(1)LALR(1)2023/2/154Ch4.语法分析-自上而下分析CH.4 CH.4 语法分析语法分析-自上而下分析自上而下分析n掌掌握握：消消除除文文法法左左递递归归，消消除除回回溯溯，计计算算FIRSTFIRST集集、FOLLOWFOLLOW集集，LL(1)LL(1)分分析

4、析条条件件，LL(1)LL(1)文文法法的的概概念念，预测分析表的构造。预测分析表的构造。n了了解解理理解解：自自上上而而下下分分析析方方法法的的基基本本思思想想,自自上上而而下分析的过程。下分析的过程。n教学内容：教学内容：4.1 4.1 语法分析器的功能语法分析器的功能 4.2 4.2 自上而下分析面临的问题自上而下分析面临的问题 4.34.3 LL(1)LL(1)分析法分析法 4.44.4 递归下降分析程序的构造递归下降分析程序的构造 4.54.5 预测分析程序预测分析程序 *4.6 4.6 LL(1)LL(1)分析中的错误处理分析中的错误处理重点难点重点难点54.1 语法分析器的功能语

5、法分析器的功能n语法分析是语法分析是编译程序的核心部分编译程序的核心部分。n它的任务是在词法分析识别出单词符号串的它的任务是在词法分析识别出单词符号串的基础上，基础上，分析并判定分析并判定一串单词符号的语法结一串单词符号的语法结构是否符合语法规则构是否符合语法规则,是否文法的一个句子。是否文法的一个句子。n分析判定的方法分析判定的方法：n建立输入串建立输入串n n的从文法开始符号的从文法开始符号S S出发的出发的推导推导 S S1 1n nn即建立以即建立以S S为根的与输入串为根的与输入串n n相匹配的相匹配的语语法树法树n图图4.1表明语法分析器在编译程序中的地位表明语法分析器在编译程序中

6、的地位64.2 4.2 自上而下分析面临的问题自上而下分析面临的问题n本节主要是通过例子本节主要是通过例子n1.1.说明自上而下分析方法的说明自上而下分析方法的思想和步骤思想和步骤n2.2.认识自上而下分析时所遇到的主要认识自上而下分析时所遇到的主要困难困难n自上而下分析的主要困难是自上而下分析的主要困难是:n文法的左递归性文法的左递归性，使分析陷入无限循环，使分析陷入无限循环n回回溯溯的的不不确确定定性性，要要求求将将已已经经完完成成工工作作推推倒重来倒重来n为为解解决决这这些些问问题题，考考虑虑要要消消除除文文法法左左递递归归和和避免回溯避免回溯。2023/2/157Ch4.语法分析-自上

7、而下分析自上而下分析方法的思想自上而下分析方法的思想n从从文文法法的的开开始始符符号号出出发发，向向下下推推导导，试试图图推推出出句句子子，匹匹配配输输入入符符号号串串，寻寻找找输输入入串串的的最最左左推推导导，并并按按与与最最左左推推导导相相对对应应的的顺顺序序，自自上上而而下下从左到右地建立输入串的语法分析树。从左到右地建立输入串的语法分析树。n推推导导过过程程中中，试试图图根根据据当当前前的的输输入入符符号号判判断断使使用非终结符的哪个候选式去替换用非终结符的哪个候选式去替换。n分分析析过过程程是是一一种种穷穷尽尽一一切切可可能能的的试试探探过过程程；是是反复使用不同产生式谋求匹配输入串

8、的过程。反复使用不同产生式谋求匹配输入串的过程。n用例子说明，用例子说明，P67.P67.例例4.14.18自上而下分析自上而下分析(1)(1)n例例4.1 4.1 文法：文法：SxAy SxAy A*A*A*A*输入串输入串 =x*y=x*y，分析分析是否文法的句子？是否文法的句子？序号序号 ipip指向指向语法树语法树最左推导最左推导说明说明 x*yS根结根结S,当前符当前符xx*yx得匹配得匹配,移动移动ip Sx A ySx A y用用SxAy展开展开S欲用欲用xAy匹配输匹配输入串入串SxAyx*y9自上而下分析自上而下分析(2)(2)序号序号 ipip指向指向语法树语法树

9、最左推导最左推导说明说明 Sx*yx A y试用试用A*展开展开ASxAyx*y*x*y*得匹配得匹配,移动移动ip但但y得不到匹配得不到匹配Sx A y*用用A*展开失败展开失败回溯回溯:回到第回到第步步Sx A ySxAyx*y10自上而下分析自上而下分析(3)(3)序号序号 ipip指向指向语法树语法树最左推导最左推导说明说明 x*ySx A y试用试用A*展开展开ASxAyx*y*x*y*得匹配得匹配,移动移动ipSx A y*A完成匹配完成匹配,y得匹得匹配配,移动移动ip,输入输入串匹配成功串匹配成功,结束结束Sx A ySxAyx*yx*y*11自上而下分析：说明自上而下

10、分析：说明n注注:自上而下分析过程是带回溯的试探过程自上而下分析过程是带回溯的试探过程n 遇遇非非终终结结符符标标记记的的结结,就就试试图图用用某某个个候候选选式式展展开开,期期望望此此候候选选能能匹匹配配输输入入串串,若若不不能能匹匹配配,则则要回溯。要回溯。n 遇遇终终结结符符号号的的结结，就就进进行行匹匹配配，然然后后移移动动输输入入串指针串指针ipip指向下一个符号。指向下一个符号。n 回回溯溯是是一一项项复复杂杂而而费费时时的的工工作作，须须废废弃弃已已做做的的许多工作，恢复到前面的某一情况，效率很低。许多工作，恢复到前面的某一情况，效率很低。n下面讨论自上而下分析法存在的困难和缺点

11、下面讨论自上而下分析法存在的困难和缺点n左左递递归归、回回溯溯、虚虚假假匹匹配配、当当报报告告分分析析不不成成功功时时难于知道输入串中出错的确切位置，等难于知道输入串中出错的确切位置，等12文法的左递归问题文法的左递归问题n文法的左递归性文法的左递归性n直接左递归直接左递归：文法存在产生式：文法存在产生式 P PP Pn间接左递归间接左递归：存在推导：存在推导 P P+PPn文文法法具具有有左左递递归归性性，采采用用自自上上而而下下方方法法分分析析，可能会陷入可能会陷入无限循环无限循环，分析不下去。，分析不下去。n例如：文法有左递归产生式例如：文法有左递归产生式 AAxAAx 分分析析中中会会

12、遇遇到到试试图图展展开开A A，却却又又立立即即遇遇到到A A，并并将将永永远远循循环环下下去去。在在没没有有识识别别任任何何输输入入符符号号的的情情况况下下又又得得重重新新要要求求A A去进行新的匹配去进行新的匹配-消左递归消左递归！SA x A x A x 13候选式的确定与回溯问题候选式的确定与回溯问题n自自上上而而下下分分析析是是一一种种反反复复用用可可能能的的候候选选式式去去进进行行试试探探的的过过程程，不不能能预预知知本本次次试试探探是是否否会会成成功功，若不成功则需要若不成功则需要回溯回溯。n例如文法：例如文法：SxAy A*|*SxAy A*|*判判定定句句子子x*yx*y是是

13、否否该该文文法法定定义义的语言的句子。的语言的句子。n希希望望：当当要要进进行行关关于于某某个个非非终终结结符符的的推推导导时时，能能够够根根据据当当前前输输入入符符号号确确定定候候选选式式，避避免免回回溯溯。Sx A y*不成功，回溯不成功，回溯Sx A y*成功成功 x*y是句子是句子14虚假匹配问题虚假匹配问题n虚虚假假匹匹配配：当当一一个个非非终终结结符符用用某某一一候候选选式式匹匹配配成成功功时时，这这种种成成功功可可能能仅仅是是暂暂时时的的、虚假的。虚假的。n例如：文法例如：文法 S xAy A *|*识别输入串识别输入串=x*y 是否为该文法的句子是否为该文法的句子n自自上上而而

14、下下的的语语法法分分析析中中，若若在在 SxAy 后后选选择用择用*替换替换 A，则则 S xAy x*y。n的的第第二二个个符符号号可可以以与与叶叶结结点点*得得以以匹匹配配，但第三个符号却不能与下一叶结点但第三个符号却不能与下一叶结点y匹配。匹配。n于于是是分分析析失失败败，意意味味着着不不能能为为串串x*y 构构造造语法树，即语法树，即 x*y 不是句子。错误的结论。不是句子。错误的结论。n失失败败的的原原因因在在于于错错误误的的选选择择了了A的的产产生生式式 -用用最长匹配方法最长匹配方法解决。解决。x*ySx A y*x*ySx A y*154.3 LL(1)分析法分析法下面将集中

15、讨论下面将集中讨论不带回溯不带回溯的自上而下分析法的自上而下分析法n4.34.3 LL(1)LL(1)分析法分析法n消除文法左递归消除文法左递归n提左因子、避免回溯提左因子、避免回溯nLL(1)LL(1)分析条件、分析条件、LL(1)LL(1)文法文法n4.44.4 递归下降分析程序构造递归下降分析程序构造n实现实现 LL(1)分析的简单方法分析的简单方法n4.54.5 预测分析程序预测分析程序n实现实现 LL(1)分析的有效方法分析的有效方法164.3.1 左递归的消除左递归的消除n无无法法对对左左递递归归文文法法进进行行有有效效的的自自上上而而下下分分析析，因此必须消除文法的左递归。因此必

16、须消除文法的左递归。n直接左递归直接左递归n有产生式有产生式 AAn间接左递归间接左递归n没有产生式没有产生式 AA,但有推导但有推导 A+An消消除除直直接接左左递递归归的的方方法法：引引入入新新的的非非终终结结符符号号P，将关于将关于P P的如下产生式的如下产生式 PP|PP|(非非且且不以不以P P打头打头)替换为替换为 PPPP P P PP17例例4.2 4.2 表达式文法直接左递归的消除表达式文法直接左递归的消除E E+TE E+TT TT T*FT T*FF FF (E)F (E)i iE T EE T EE E +T T E E|T F TT F TT T*F F T TF(E

18、言，假定关于一般而言，假定关于P的全部产生式是：的全部产生式是：PP 1|P 2|P m|1|2|n 其中其中,每个每个都不等于都不等于,而每个而每个都不以都不以P开头开头 n消除消除P的直接左递归就是把这些规则改写成：的直接左递归就是把这些规则改写成：P 1 P|2 P|n P P 1P|2P|mP|n直直接接左左递递归归和和间间接接左左递递归归的的消消除除方方法法均均在在必必须须掌掌握握之之列列。P70.有有一一个个消消除除任任何何左左递递归归的的算算法，下面先举例说明消除间接左递归的方法。法，下面先举例说明消除间接左递归的方法。20消除间接左递归消除间接左递归n间间接接左左递递归归的

19、的消消除除:先先将将间间接接左左递递归归变变为为直直接接左递归，再按消直接左递归的方法消除。左递归，再按消直接左递归的方法消除。n例例1 1：文法：文法 (1)(1)A Bb A Bb 有间接左递归有间接左递归 (2)B Ac (2)B Ac (3)B d (3)B d 先先将将(1)(1)代入代入(2)(2)得：得：BBbcBBbc，于是于是 B Bbc|dB Bbc|d 再消除直接左递归，得到的文法不含左递归再消除直接左递归，得到的文法不含左递归:A BbA Bb B dBB dB B bc B|B bc B|21消除间接左递归：例消除间接左递归：例1 1n例例1 1：有间接左递归文法：有

20、间接左递归文法：(1)(1)A Bb (2)B Ac (3)B dA Bb (2)B Ac (3)B d 也可以先也可以先将将(2)(3)(2)(3)代入代入(1)(1)得得:A Acb|db再消直接左递归再消直接左递归,得到不含左递归的文法得到不含左递归的文法:A dbA A cb A|B现在是无用符号现在是无用符号,把把B及其产生式删除。及其产生式删除。n说说明明：代代入入方方法法不不同同，得得到到的的不不含含左左递递归归的的文文法法可可能能是是不不一一样样的的，但但它它们们等等价价。消消左左以以后，可能会出现无用符号，应把它们去掉。后，可能会出现无用符号，应把它们去掉。22间接左递归的消

22、回路无回路(无形如无形如 P+P 的推导的推导)；2.无无产生式产生式n算法算法(1)以某种顺序将文法非终结符排列以某种顺序将文法非终结符排列 P1,P2,Pn(2)For i:=1 to n dobegin for j:=1 to i-1 do 把形如把形如 Pi Pj 的规则改写为的规则改写为 Pi 1|2|k 其中其中,Pj 1|2|k 是关于是关于Pj的全部产生式的全部产生式;消除消除Pi规则的直接左递归规则的直接左递归;end;(3)化简由化简由(2)得到的文法得到的文法,去掉无用的非终结符号去掉无用的非终结符号。24消左递归算法：例消左递归算法：例4.3n 解：将非终结符排序为解：

25、因子n强强调调:实实现现有有效效的的自自上上而而下下分分析析，要要求求文文法法不不得得含含左左递递归归，并并且且不不得得回回溯溯。现现在在左左递递归归已已经解决。经解决。n接下来讨论接下来讨论:n1.在在不不得得回回溯溯的的情情况况下下进进行行自自上上而而下下分分析析，对于文法有什么要求。对于文法有什么要求。n2.如何如何改写文法改写文法使满足消除回溯的要求。使满足消除回溯的要求。n需要引入需要引入:n符号串符号串的终结首符集的终结首符集 FIRST()n非终结符非终结符A的后随终结符集的后随终结符集 FOLLOW(A)27为避免回溯对文法的要求为避免回溯对文法的要求n回回溯溯的的产产生生是是

26、由由于于文文法法中中存存在在非非终终结结符符A有有n个候选式：个候选式：A 1|2|nn在在自自上上而而下下分分析析中中展展开开A时时，穷穷尽尽A的的一一切可能的候选式去谋求与输入串相匹配。切可能的候选式去谋求与输入串相匹配。n如如果果能能够够:根根据据当当前前的的输输入入符符号号a，能能准准确确地地指指出出其其匹匹配配的的某某个个候候选选式式 i，而而不不需需要要从从 1开开始始逐逐个个试试探探。并并且且若若 i 匹匹配配输输入入串串成成功功，那那么么这这种种匹匹配配决决不不会会是是虚虚假假的的；若若 i 无无法法完完成成匹匹配配任任务务，那那么么其其他他候候选选式式也也肯肯定定不不能能完完

27、成成。i 是是A的的全全权权代代表表，i 的工作成效完全代表了的工作成效完全代表了A。A 输入串输入串a aSi 28为避免回溯引入为避免回溯引入FIRST()集集n回回溯溯的的产产生生是是由由于于文文法法中中存存在在非非终终结结符符A有有n个候选式：个候选式：A 1|2|nn在在面面临临当当前前输输入入符符号号a时时要要能能准准确确指指出出唯唯一一可可使使用用的的候候选选式式 i去去代代表表A谋谋求求与与输输入入串串相相匹匹配配，显然要求各显然要求各 i的终结首符号互不相同。的终结首符号互不相同。n引引入入符符号号串串的的终终结结首首符符集集FIRST()，上上述述要求即：要求即：FIRST

28、(i)FIRST(j)=ij，i,j=1,2,nn显显然然，当当输输入入符符号号a FIRST(i)时时,可可以以确定用候选式确定用候选式 i去谋求匹配。去谋求匹配。29FIRST()集合及作用集合及作用n令令G是一个不含左递归的文法是一个不含左递归的文法,符号串符号串 VTVN*n定义定义的终结首符集为：的终结首符集为：FIRST()=a|*a 且且 a VT n特别是，若特别是，若 *，则规定，则规定 FIRST()。nFIRST集集合合的的作作用用:如如果果非非终终结结符符A 的的任任何何两两个个不不同同的候选的候选 i和和 j有：有：FIRST(i)FIRST(j)=那那么么，当当要

29、要求求A匹匹配配输输入入串串时时，A 就就能能根根据据它它所所面面临临的的当当前前输输入入符符号号a，准准确确地地指指派派某某个个候候选选前前去去执执行行任务任务,这个候选就是那个这个候选就是那个终结首符集合含终结首符集合含a 的的 i。30n例例1：文法：文法:SaA A Sd AbAS FIRST(S)=a,d FIRST(bAS)=b FIRST(A)=,b FIRST()=n例例2：文法：文法:SAa A Sd AbaS FIRST(S)=b,a,d FIRST(Aa)=a,bFIRST(A)=,b计算计算FIRSTFIRST集合集合:例例2023/2/1531Ch4.语法分析-自上而

30、下分析n练习：文法练习：文法 EE+T|T TT*F|F F(E)|i 计算计算:FIRST(E)=?FIRST(i)=?FIRST(T*F)=?FIRST(F)=?FIRST(E)=?计算计算FIRSTFIRST集合集合:练习练习n解解:FIRST(E)=(FIRST(i)=i FIRST(T*F)=(,i FIRST(F)=(,i FIRST(E)=(,i 2023/2/1532Ch4.语法分析-自上而下分析n如如何何把把一一个个文文法法改改造造成成所所有有候候选选式式的的终终结结首首符集两两不相交呢？符集两两不相交呢？n其办法是其办法是提取公共左因子提取公共左因子。n例如，假定关于例如，

31、假定关于A 的规则是的规则是:A 1|2|n|1|2|m (其中每个其中每个不以不以开头开头)那那末末，可可以以引引进进新新的的非非终终结结符符,把把这这些些规规则则改改写成：写成：A A|1|2|m A 1|2|n改写文法避免回溯改写文法避免回溯:提左因子提左因子1|2|n=(1|2|n)33n例例1:有产生式有产生式 B bBcA|b 由于由于FIRST(bBcA)FIRST(b)=b 则需要对则需要对B bBcA|b提取公共左因子提取公共左因子b 将产生式改写成：将产生式改写成：B bB B BcA|提左因子：例提左因子：例n例例2:有文法有文法 S cAd|b A ab|a 由于由

34、合两两不交n考察识别输入串考察识别输入串 i+i#(#是句末符是句末符,#不属于不属于VT)37LL(1)LL(1)分析条件的提出分析条件的提出(1)(1)E只有一个候选只有一个候选TE,E替换为替换为 TE T只有一个候选只有一个候选 FT,T替换为替换为 FTF有两个候选有两个候选,i FIRST(i)F替换为替换为 i,i 得到匹配得到匹配,移动移动 ip指指+T有两个候选有两个候选,+不属于任一候选不属于任一候选的的 FIRST集集;但有但有 T,认为认为T 自动匹配自动匹配注意注意：+号号并不读进！并不读进！ET Ei+i#F T ET Eii+i#F T E TE E +TE|T

35、FT T *FT|F (E)|i38LL(1)LL(1)分析条件的提出分析条件的提出(2)(2)E有两个候选有两个候选,+FIRST(+TE),故故E替换为替换为+TE。+得到匹得到匹配配,移动移动 ip 指下一个指下一个 i。T只有一个候选只有一个候选,T展开为展开为 FT。F展开展开为为 i。i 得到匹配，得到匹配，移动移动 ip 指指#。#不属于不属于T任一候选的任一候选的 FIRST集，集，但有但有 T,认为认为T 自动匹配自动匹配。#不属于不属于E任一候选的任一候选的 FIRST集，集，但有但有 E,认为认为E 自动匹配自动匹配。+T E i F T ET EiF T i+i#i+i

36、#i+i#E TE E +TE|T FT T *FT|F (E)|i39LL(1)LL(1)分析条件的提出分析条件的提出(3)(3)i+i#最后得到与最后得到与 i+i i+i 相匹配的相匹配的语法树语法树+T E i F T ET EiF T 问题问题:是不是一旦非终结符是不是一旦非终结符A面临输入符号面临输入符号a,且且a不属于所有不属于所有FIRST(i),但但属于某个属于某个FIRST(j),就就一定可以使一定可以使A自动匹配自动匹配呢呢?答案是答案是不一定不一定。在一定的条件。在一定的条件下才可以。否则错误。下才可以。否则错误。条件是条件是a 允许跟在允许跟在A的紧后面的紧后面例如上

37、例中，例如上例中，+可跟在可跟在T后，后，#可跟在可跟在T、E后面。后面。下面定义下面定义可跟在非终结符后的可跟在非终结符后的终结符号的集合终结符号的集合FOLLOW。40非终结符的后随终结符集非终结符的后随终结符集FOLLOWFOLLOWn假定假定S是文法是文法G的开始符号，对于任何非终结的开始符号，对于任何非终结符符A，定义：定义：FOLLOW(A)=a|S*Aa且且 a VT n特别是特别是,若若S*A,则规定则规定#FOLLOW(A)(#是句末符号是句末符号)n也就是说，也就是说，FOLLOW(A)是所有句型中，出是所有句型中，出现在紧接现在紧接A之后的终结符或之后的终结符或#。n例：

38、例：SaA A Sd AbAS FOLLOW(S)=#,a,d FOLLOW(A)=a,d,#SaAabASabbASS41计算计算FOLLOWFOLLOW集合：例集合：例n例：例：P69.(4.2)表达式文法表达式文法 ETE E+TE|TFT T*FT|F(E)|iFOLLOW(T)=#,+,)ETE T FT 有有#号号 E TE T+TE FT+TE 有有+号号 E TE T FT(E)T(TE)T(T)T(FT)T 有有)号号2023/2/1542Ch4.语法分析-自上而下分析LL(1)LL(1)分析条件：分析条件：3 3个个n(1)(1)文法文法不含左递归不含左递归。n(2)(2)

39、对对于于文文法法中中每每个个非非终终结结符符A A的的各各个个候候选选式的终结首符集两两不相交式的终结首符集两两不相交。即，若。即，若 A A 1 1|2 2|n n 则：则：FIRST(FIRST(i i)FIRST(FIRST(j j)=(i (i j)j)n(3)(3)对对文文法法中中每每一一个个非非终终结结符符A A，若若它它存存在在某个候选式的终结首符集包含某个候选式的终结首符集包含，则，则 FIRST(A)FIRST(A)FLLOW(A)=FLLOW(A)=n 特特别别注注意意第第3 3个个条条件件：当当空空字字属属于于非非终终结结符符的某个候选式的终结首符集时的条件的某个候选式的

40、终结首符集时的条件!2023/2/1543Ch4.语法分析-自上而下分析LL(1)文法文法n一一个个文文法法G若若满满足足上上述述LL(1)分分析析的的三三个个条条件件，则则称称该文法该文法G为为LL(1)文法文法。nLL(1)文法文法:n第一个第一个 L 表示从左到右扫描输入串表示从左到右扫描输入串n第二个第二个L 表示语法分析欲构造输入串的最左推导表示语法分析欲构造输入串的最左推导n括括号号里里的的 1 表表示示分分析析时时,每每步步只只需需向向前前查查看看一一个个符号符号nLL(1)文文法法是是无无二二义义文文法法,上上述述三三个个条条件件是是LL(1)文文法无二义的充分条件。法无二义的

41、充分条件。n 对对LL(1)文文法法，可可以以对对其其输输入入串串进进行行有有效效的的无无回回溯溯的自上而下分析。的自上而下分析。44LL(1)LL(1)文法：自上而下分析过程文法：自上而下分析过程n对对LL(1)文文法法，假假设设要要用用非非终终结结符符A进进行行匹匹配配，面面临临的的输输入入符符号号为为 a，A的的所所有有产产生生式式为为：A 1|2|nn(1)若若aFIRST(i),则指派则指派 i 执行匹配任务。执行匹配任务。n(2)若若a不属于任何一个候选式的终结首符集不属于任何一个候选式的终结首符集,则则:n 若若属属于于某某个个FIRST(j)且且aFO

42、LLOW(A),则让则让A与与自动匹配自动匹配;n 否则否则,a的出现是一种错误。的出现是一种错误。n根根据据LL(1)文文法法的的条条件件,每每一一步步这这样样的的工工作作都都是是确信无疑的。确信无疑的。2023/2/1545Ch4.语法分析-自上而下分析LL(1)LL(1)文法：例文法：例n例例4.24.2文法文法(P69.)P69.)不是不是LL(1)LL(1)文法文法,有左递归有左递归n例例4.24.2消左以后的文法消左以后的文法P69.(4.2)P69.(4.2)是是LL(1)LL(1)文法文法n满足满足LL(1)LL(1)分析的三个条件分析的三个条件n例例1 1 文法文法G:S i

43、AG:S iA A :i=e|=e A :i=e|=e 是是LL(1)LL(1)文法文法n满足满足LL(1)LL(1)分析的三个条件分析的三个条件:1.1.不含左递归不含左递归 2.FIRST(:i=e)=:,FIRST(=e)=,2.FIRST(:i=e)=:,FIRST(=e)=,不交不交 3.3.候选式的候选式的FIRSTFIRST集都不含集都不含46LL(1)LL(1)文法文法:例例2 2n例例2 2 文法文法G:S LUG:S LU L i:|L i:|U i=e U i=en因为因为:1.1.不含左递归不含左递归 2.L 2.L的各个候选的的各个候选的FIRSTFIRST集合互不交

44、集合互不交 3.3.L L有个候选式的有个候选式的FIRSTFIRST集合含集合含,再求得再求得 FIRST(L)=FIRST(L)=i,i,FOLLOW(L)=FOLLOW(L)=i i,是是相相交的交的n所以所以G G不是不是LL(1)LL(1)文法文法。2023/2/1547Ch4.语法分析-自上而下分析4.4 递归下降分析程序构造递归下降分析程序构造n当当一一个个文文法法满满足足LL(1)LL(1)条条件件时时，就就可可以以为为该该文文法法构构造造一一个个不不带带回回溯溯的的自自上上而而下下分分析程序析程序：n这个分析程序由一组这个分析程序由一组递归过程递归过程组成；组成；n每每个个递

45、递归归过过程程对对应应文文法法的的一一个个非非终终结结符符号号，完完成成该该非非终终结结符符号号所所对对应应的的语语法成分的分析和识别任务。法成分的分析和识别任务。n这这样样一一个个自自上上而而下下语语法法分分析析程程序序称称为为递递归下降分析器归下降分析器。2023/2/1548Ch4.语法分析-自上而下分析递归下降分析程序构造：递归下降分析程序构造：过程和变量过程和变量n先先设设定定一一些些过过程程和和变变量量，作作为为递递归归下下降降分分析析程序的基本成分。程序的基本成分。n过过程程ADVANCEADVANCE：调调整整ipip指指向向下下一一个个输输入入符符号号,读入读入ipip指向的

46、输入符号到指向的输入符号到SYMSYM中。中。n变量变量SYMSYM：表示表示ipip当前所指的那个输入符号。当前所指的那个输入符号。n过程过程ERRORERROR：出错诊察处理。出错诊察处理。2023/2/1549Ch4.语法分析-自上而下分析递归下降分析程序构造：递归下降分析程序构造：非终结符对应的递归过程的结构非终结符对应的递归过程的结构n A1|2|nn =X1X2Xm Xi(VTVN)n XiVTn XiVNn IF ELSE IF ELSE 结构结构n顺序结构顺序结构n IF SYM=Xi THEN ADVANCE ELSE ERRORn 调调用用Xi对对应应的的递递归归过过程程5

47、0例例:算术表达式的递归下降分析器算术表达式的递归下降分析器(1)(1)n 的的子子程程序序 ETEETE procedure E;procedure E;beginbegin T;T;的过程调用的过程调用 E E EE的的过过程程调用调用end;end;n的子程序的子程序 E+TE|E+TE|procedure E;procedure E;IF SYM=+THEN IF SYM=+THEN begin begin ADVANCE;ADVANCE;T;T;T T的过程调用的过程调用 E E EE的过程的过程调用调用 end;end;2023/2/1551Ch4.语法分析-自上而下分析例例

48、:算术表达式的递归下降分析器算术表达式的递归下降分析器(2)(2)nT T的的子子程程序序 TFTTFT procedure T;procedure T;beginbegin F;F;F F的过程调用的过程调用 T T T T的的过过程程调用调用end;end;nTT的子程序的子程序 T*FT|T*FT|procedure E;procedure E;IF SYM=*THEN IF SYM=*THEN begin begin ADVANCE;ADVANCE;F;F;F F的过程调用的过程调用 T T T T的过程的过程调用调用 end;end;2023/2/1552Ch4.语法分析-自上而下分

49、析例例:算术表达式的递归下降分析器算术表达式的递归下降分析器(3)(3)nF F的子程序的子程序 Fi|(E)Fi|(E)procedure F;procedure F;IF IF SYM=i then SYM=i then ADVANCE ADVANCE ELSE ELSE IF IF SYM=(then SYM=(then BEGIN BEGIN ADVANCE;ADVANCE;E;E;E E的过程调用的过程调用 IF SYM=)IF SYM=)THENTHEN ADVANCE ADVANCE ELSE ELSE ERROR ERROR END END ELSE ERROR;ELSE ER

50、ROR;2023/2/1553Ch4.语法分析-自上而下分析扩充巴科斯范式定义系统扩充巴科斯范式定义系统n对前面的产生式对前面的产生式(巴科斯范式巴科斯范式)进行扩充进行扩充：n(1)用花括号用花括号表示闭包运算表示闭包运算*。n(2)用用 0n表示表示可以任意重复可以任意重复0次至次至n次次,00=0=。n(3)用用方方括括号号表表示示 01，即即表表示示的的出出现现可可有可无有可无,等价于等价于|。n这这样样,使使得得产产生生式式右右部部的的形形式式像像正正规规式式一一样样,这这种定义形式称种定义形式称扩充扩充巴科斯范式定义系统巴科斯范式定义系统。n例如例如,P75.P75.“实

展开阅读全文