编译原理语法分析.ppt

《编译原理语法分析.ppt》由会员分享，可在线阅读，更多相关《编译原理语法分析.ppt（114页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第3章章 语法分析语法分析语法分析是编译过程的核心部分。语法分析的基本任务是在词法分析识别出单词符号串的基础上，分析判断程序的语法结构是否符合语法规则。语言的语法结构用上下文无关文法来描述，因此，语法分析器的任务本质上是按上下文无关文法的产生式，确定整个单词串是否构成语法上正确的程序。语法分析的方法通常分为两类：自上而下分析法和自下而上分析法3.1文法和语言3.2推导与语法树3.3自上而下分析方法3.4自下而上分析方法3.5LR分析法3.1 文法和语言文法和语言文法文法是程序语言的生成系统。自动机自动机是程序语言的识别系统。用文法可精确定义一个语言,并依据文法构造出识别该语言的自动机。因此,

2、文法对程序语言和编译程序的构造具有重要意义,如程序语言的词法可用正规文正规文法法描述,语法可用上下文无关文法上下文无关文法描述,而语义可借助于上下文有关文法上下文有关文法描述。3.1.1文法和语言的概念1语言语言通常用表示字母表。由字母表中字符组成的有穷序列称为上的字符串字符串或字字。字母表上的所有字符串(包括空串)组成的集合用*表示。对于字母表,*上的任一子集子集称为上的一个语言语言,记为L,L*。语言L的每个字符串称为语言L的一个语句语句或句子句子。2.文法文法终终结结符符是语言不可再分的基本符号,通常为一个语言的字母表。终结符代表了语法的最小元素,是一种个体记号。非非终终结结符符也称语法

3、变量,它代表语法实体或语法范畴。一个非终结符是一个类、一个集合。例如,变量、常量、+、*等为终终结结符符，而“算术表达式”为非非终终结结符符,它代表一定算术式组成的类类,如i*(i+i)、i+i+i等,即非非终终结结符符代表由终结符组成且满足一定规则的符号串的集合集合。文法文法可表示为四元组G=(VT,VN,S,),其中(1)VT为非空终结符集终结符集;(2)VN为非空非终结符集非终结符集,且VTVN=;(3)S为文法开始符文法开始符,SVN;(4)是产生式的非空有限集产生式的非空有限集,其中每个产生式(规则)记作或:=左部(VTVN)+至少含一非终结符,右部(VTVN)*。产生式(也称产生式

4、规则或规则)是定义语法实体的一种书写规则。一个语法实体的相关规则可能不止一个,如:P1,P2,Pn相同左部的产生式可合并为一个:P1|2|n其中,i(i=1,2,n)称为P的候选候选式式。例例3.1试构造产生试构造产生标识符标识符的文法的文法。分析:用L表示字母,D表示数字,T表示字母或数字,则LabzD019TLD用S表示字母数字串字母数字串,则ST是字母数字串,即ST|ST标识符I或为单个字母,或为一字母后跟字母数字串,即IL LS解:产生标识符的文法产生标识符的文法GI为：G=(a,b,z,0,9,I,S,T,L,D,I,)其中,:ILLSSTSTTLDLabzD019例例3.2写一文法

5、,使其语言是奇数集,但不允许出现以0打头的奇数。解:将奇数划分为三个部分：最高位最高位允许出现19,用非终结符B表示;中间部分中间部分可出现任意多位数字09,每一位用非终结符D表示;最低位最低位只出现1,3,5,7,9,用A表示。由于中间部分可任意位,故需另引入一非终结符M,它包括最高位和中间部分。MB最高位中间位DDDA最低位解:奇数集文法GN为:G=(0,1,9,N,A,M,B,D,N,):NA|MAMB|MDA1|3|5|7|9B1|2|3|4|5|6|7|8|9D0|B3.文法产生的语言文法产生的语言设G=(VT,VN,S,)且,(VTVN)*,若存在产生式A,(VTVN)*，则称A可

6、直接推出可直接推出,记为A注意与的不同:是产生式中的定义记号,表示直接推导,是对文法符号串A中A用产生式A的右部替换。关于推导的两点说明关于推导的两点说明：(1)若1可直接推出2,2可直接推出3,即存在一个自1至n的推导序列:123n(n0)则称1可推导出可推导出n,记为1n,表示从1出发经1步或若干步可推导出n(2)若记11,则1n表示从1出发,经过0步或若干步可推导出n,即1n意味着或1=n,或1n。+0*+例如,考虑算术表达式文法GE：EE+EE*E(E)i非终结符E代表一类算术表达式,从E出发可进行一系列推导,表达式i+i*i的推导如下：EE+EE+E*EE+E*iE+i*ii+i*I

7、注意:在每一步推导中,只能对其中一个非终结符用其对应的产生式右部的一个候选式来替换。假定GS是一个文法,S是其开始符号,若S,(VTVN)*,则称是文法GS的一个句型句型;若S,VT*，则称是文法GS的一个句子句子。由上述定义知：仅含终结符的句型是一个句子。开始符S是一个句型而不是一个句子。i+i*i是一个句子,也是一个句型,E+E*E、E+E*i和E+i*i是句型,但不是一个句子。*对于文法GS,它所产生的句子的全句子的全体体称为由文法GS产生的语言语言,记为LG。L(G)=|S且VT*3.1.2形式语言分类形式语言分类Chomsky于1956年定义了四类文法及相应的四类形形式式语语言言,它

8、对程序语言的设计、编译方法、计算复杂性等方面都产生了重大影响。+10型文法与型文法与0型语言型语言(短语文法)若文法G的每个产生式具有下列形式:其中至少含一个非终结符，则称文法G为0型文法型文法或或短语文法短语文法,记为PSG。0型文法相应的语言称为0型语言型语言,它的识别系统是图灵机。21型文法与型文法与1型语言型语言(对应自然语言)若文法G的每个产生式均满足|则称文法G为1型文法型文法或上下文有关文上下文有关文法法,记为CSG。1型文法相应的语言称为1型语言型语言。1型文法的另一种定义型文法的另一种定义:文法G的每个产生式具有下列形式：A其中,V*,AVN,V+它更明确地表达了上下文有关的

9、特性。32型文法与型文法与2型语言型语言(对应程序设计语言)若文法G的每个产生式具有下列形式：A其中,AVN,V*称文法G为2型文法型文法或上下文无关文法上下文无关文法,记为CFG。2型文法相应的语言称为2型语言型语言或上下文无关语言。它的识别系统是下推自动机。43型文法与型文法与3型语言型语言(对应有限自动机)若文法G的每个产生式具有下列形式：Aa或AaB其中，A,BVN，aVT*，则文法G称为3型文法型文法或正规文法正规文法或右线性文法，记为RG。3型文法相应语言为3型语言型语言或正规语言。它的识别系统是有限自动机。3型文法还可呈左线性形式：Aa或ABa5.四类文法的关系与区别四类文法的关

10、系与区别从0型文法到3型文法逐步增加限制。一般地,13型文法属于0型文法，2,3型文法属于1型文法,3型文法属于2型文法。四类文法的区别四类文法的区别：(1)1型文法不允许有形如A的产生式,2,3型文法允许形如A的产生式;(2)0,1型文法的产生式左部左部可以是含终结符的符号串或两个以上的非终结符,2,3型文法的产生式左部只允许是单个单个非终结符非终结符。anbncn|n1anbncm|m,n1ambnck|m,n,k1这说明对文法规则定义形式的限制虽加强了,但相应的语言反而更大了。因此,不能主观认定文法限制越大则语言越小,即下述结论不成立不成立：3型语言2型语言1型语言0型语言编译方法中通常

11、用3型文法型文法描述词法词法,用FA识别单词;利用2型文法型文法描述语法语法,用下推自动机PDA识别各种语法成分。例例3.4给出=a,b上具有奇数个具有奇数个a和奇数和奇数个个b的所有字符串集合的正规文法正规文法。解:如图,由S出发经奇数个a到达A,或经奇数个b到达B。再由A出发经奇数个b到达C;同样,由B出发经奇数个a到达C。正规文法GS如下:SaA|bBAaS|bCBbS|aCCbA|aB|bbbbaaaaSAB2 C3.1.3正规式与上下文无关文法正规式与上下文无关文法1.正规式到上下文无关文法的转换正规式到上下文无关文法的转换由正规式构造由正规式构造CFG的一种方法的一种方法：(1)构

12、造正规式的NFA；(2)若0为初始状态,则A0为开始符；(3)若存在映射关系f(i,a)=j,则定义产生式AiaAj；(4)若存在映射关系f(i,)=j，则定义产生式AiAj；(5)若i为终态终态,则定义产生式Ai。例例3.5用CFG描述正规式(a|b)*abb解:先构造识别(a|b)*abb的NFAM:0122 3ababbGA0:A0aA0bA0aA1A1bA2A2bA3A3由正规式构造由正规式构造CFG的另一种方法的另一种方法：通过分析正规式凭经验凭经验直接构造。例如,把(a|b)*abb看作(a|b)*和abb两部分,第一部分是由0个或若干个a和b组成的字符串,第二部分仅由abb字符串

13、组成,由此得到CFGGA0如下：GA0:AHTHaH|bH|Tabb2.正规式与正规式与CFG描述的对象描述的对象CFG既可描述语法,又可描述词法。基于下述原因,通常用正规式描述词法:(1)词法规则简单,用正规式已足以描述;(2)正规式的表示比CFG更简洁、直观和易于理解；(3)FA的构造比PDA(下推自动机)的构造简单且效率高。注意注意:(1)语言的描描述述和语言的识识别别是表示一种语言的两个不同侧面,二者缺一不可。(2)正正规规式式通常适合于描述线线性性结结构构,如标识符、关键字和注释等;上上下下文文无无关关文文法法通常适合于描述具有嵌套(层次)性质的非线性结构非线性结构,如if-else

14、语句、while语句。3.2 推导与语法树推导与语法树3.2.1推导与短语1.规范推导规范推导最最右右推推导导:在推导过程中,若每一步推导都是对句型中的最最右右非非终终结结符符用相应产生式的右部进行替换,则称这种推导为最右推导。最最左左推推导导:在推导过程中,若每一步推导都是对句型中的最最左左非非终终结结符符用相应产生式的右部进行替换,则称这种推导为最左推导。例如例如,考虑句子i+i*i按文法GE的推导最左推导最左推导:EE+Ei+Ei+E*Ei+i*Ei+i*i最右推导最右推导:EE+EE+E*EE+E*iE+i*ii+i*i注意注意:推导过程不唯一,通常只考虑最左推导或最右推导。最右推导最

15、右推导又称为规范推导规范推导。规范推导的逆过程称为规范归约规范归约。2.短语短语如果SA且A,则称 是句型句型关于非终结符A的一个短语短语,简称是的一个短语短语。如果SA且A,则称为句型的一个直接短语直接短语或简单短语。注意注意:短语的两个条件缺一不可。考虑i+i*i,Ei+i,但i+i不是短语*+*+3.句柄句柄句型的最左直接短语最左直接短语称为句柄句柄。注意,一个句型的直接短语不唯一,但最左直接短语唯一。例如,对SA ,若为终结符串,则句型中的句柄为。将句型中的句柄用产生式的左部符号代替便得到新句型A,这是一次规范归约,恰与规范推导相反。*4.素短语素短语含有终结符的短语,如果它不存在具有

16、同样性质的真子串,则该短语为素短素短语语。例如,在EE+E*i中,i、E*i、E+E*i是句型E+E*i的短语,其中,i为素短语素短语,E*i虽含终结符,但其真子串i含终结符,故E*i不是素短语不是素短语,同样E+E*i也不是素短语。+3.2.2语法树与二义性语法树与二义性1.语法树语法树对于程序语言,有两个问题需要解决:(1)判别程序在语法上是否正确;(2)句子的识别或分析。为便于分析句子而引入语法树语法树。语法树语法树以图示化形式把句子分解成各个组成部分,以分析句子的语法结构。语法树表示法与文法规则完全一致,但更为直观和完整。满足下列条件的树称为文法满足下列条件的树称为文法G的的语法树语法

17、树:(1)每个结点用G的一个终结符或非终结符标记;(2)根结点用文法开始符S标记;(3)内部结点一定是非终结符,若某内部结点A有n个分支,且其所有子结点从左至右依次标记为x1,x2,xn,则Ax1x2xn一定是G的一条产生式;(4)若某结点标记为,则它必为叶结点且是其父结点的唯一子结点。一个句句型型对应的语语法法树树以文法开始符S作为根结点,并随着推导逐步展开。当某非终结符被产生式右部的某候选式替换时,该非终结符对应的结点产生出下一代结点,即候选式中从左至右的每个符号依次顺序对应一个新结点,且每个新结点与其父结点之间都有一连线。在在一一棵棵语语法法树树生生长长过过程程中中的的任任何何时时刻刻,

18、所所有有没没有有后后代代的的叶结点叶结点的自左至右排列是一个的自左至右排列是一个句型句型。例如,句子i+i*i的语法树如下:EEEE*Eiii第一代第二代第三代第四代构造语法树时,一个句型的最左推导及最右推导只决定先先生长左子树还是先先生长右子树,推导结束时相应的语法树已看不出先生长的是哪个子树。因此,一棵语法树表示一个句型种种可能的不同推导过程,包括最左(最右)推导。若坚坚持持使使用用最最左左(最最右右)推推导导,则则一一棵棵语语法法树树等等价价于于一一个个最最左左(最最右右)推推导导,这种等价性包括语法树的每一步生长和推导过程的每一步展开的完全一致性。2.子树和短语子树和短语语法树的某个结

19、点连同它的所有后代组成了一棵子树子树。只含有单层分枝的子树称为简单子树简单子树。子树与短语的关系子树与短语的关系:(1)短语短语:子树的所有叶结点所有叶结点组成的符号串是相对于子树根子树根的短语短语；(2)直接短语直接短语:简单子树的所有叶结点简单子树的所有叶结点组成的符号串是直接短语直接短语;(3)句柄句柄:最左简单子树最左简单子树的所有叶结点组成的符号串为句柄句柄;(4)素短语素短语:子树的所有叶结点组成的含终结符含终结符的符号串,且在该子树中没有没有有包含终结符的更小子树更小子树。显然,从语法树出发寻找短语、直接短语、句柄和素短语直观得多。但要注意,子子树树叶叶结结点点组组成成的的符符号

20、号串串是指由该子子树树根根开始向下生长的所所有有叶叶结结点点,该子树的部分叶结点并不是该子树的短语。考虑句型E+E*i的语法树:短语:i、E*i和E+E*i;直接短语:i;句柄:i;素短语:iEEEE*Ei3.文法的二义性文法的二义性若文法G的一个句子能找到两种不同的最左推导(最右推导),即存在两棵不同的语法树,则称这个句子句子是二义性是二义性的。若一个文法包含二义性句子,则这个文法是二义文法二义文法,否则是无二义文法。例如,对文法(3.1),句子i+i*i存在两种最左(右)推导:EEEE*EiEEEE*Eiii(a)ii(b)再如,条件语句文法GS:GS:SifBSSifBSelseSSA/

21、A指其它语句其中,VN=B,S,A,VT=if,else文法GS的一个句型ifBifBSelseS对应两棵不同的语法树,如下图所示,因此,文法GS是二义性文法。SifS(a)(b)BSifS elseBSBSifS elseifSB4.文法二义性的消除文法二义性的消除一个文法是二义性的,并不说明文法所描述的语言是二义性的。即对于一个二义文法GS,若能找到一个非二义文法GS,使得L(G)=L(G),则该二义文法的二义性可以消除。若找不到这样的GS,则二义文法描述的语言为先天二义性的。文法二义性的消除方法:(1)不改变文法中原有的语法规则,仅加进一些语法的非形式规定。如对文法(3.1),不改变已有

22、产生式,仅加进运算符的优先顺序优先顺序和结合规则结合规则,即*优先于+,且*,+都服从左结合。(2)构造一个等价的无二义文法。即把排除二义性的规则合并到原文法中,改写原改写原文法文法。GE:EE+TTTT*FFF(E)i此时,句子i+i*i只有唯一一棵语法树。例如,将文法(3.1)改写为无二义文法GE:EETFTFiiTFi*例例3.6将下述文法GS的二义性消除:GS:SifbSifbSelseSA解:消除GS的二义性可采用两种方法:(1)不改变已有规则不改变已有规则,仅加进一项非形式的语法规定:else与离它最近的if匹配,这样,句子ifbifbAelseA对应唯一的一棵语法树。SbSifS

23、 elseAAbifS(2)改写文法GS为GS:SS1|S2S1ifbS1elseS1|AS2ifbS|ifbS1elseS2由于引起二义性的原因是if-else语句的if后后可以是任意if语句,故改写文法改写文法时规定时规定if和和else之间只能是之间只能是if-else语句或其它语句语句或其它语句。S1bS1ifS1elseAAbifSS2S编译过程中希望一个文法是无二义性的,这样句子的分析可按唯一确定的方式进行。但文法的二义性是不可判定的,即不存在一种算法能在有限步内判定一个文法是否为二义性的。不过,二义文法有时也可带来一定好处,如语法分析中二义文法的应用。3.3 自上而下分析方法自上

24、而下分析方法自自上上而而下下分分析析从文法开始符出发,向下推导,推出句子。即寻找一个推导序列,使推导出的句子恰为输入串;亦即,从根结点出发向下生长出一棵语法树,其叶结点组成的句子恰为输入串。显然,语法树的每一步生长(推导)都以能否与输入串匹配为准。1.自上而下分析存在的不确定性文法GS:SxAyAaba若输入串为xay,则其分析过程如下:(1)首先建立根结点S。(2)文法关于S的产生式只有一个。yAxS下一待分析字符a与A匹配。(3)非终结符A有两个候选式,先选用第一个候选式:yAxSab(4)下一待分析字符y与b匹配,失败。(5)将A生成的子树注销,指针回退到输入串的第二个字符a。(6)A选

25、用第二个候选式:yAxSa这时输入串中a与叶结点a匹配。(7)下一个待分析字符为y,而语法树下一个叶结点也为y,匹配成功。在上述分析过程中,若有多个候选式可供选择,则逐一试试探探每个候选式。一次试探失败时,必须回回溯溯到该试探的初始现场,包括注销已生长子树、指针回退到失败前状态。这种带回溯的自上而下分析方法是一种穷举法,效效率率极极低低,在实用编译程序中很少使用。2.确定的自上而下分析确定的自上而下分析实现确定的自上而下分析需满足条件:(1)文法不含左递归文法不含左递归。左递归:AA或AA左递归的存在可可能能使自上而下分析过程陷入无限循环,故使用自上而下分析法必须消除文法的左递归必须消除文法的

26、左递归。(2)分析过程无回溯分析过程无回溯。回溯的存在可能使已做的大量语法和语义分析推倒重来,这会严重影响效率,故使用自上而下分析法必须消除回必须消除回溯溯。+3.左递归的消除左递归的消除直接左递归直接左递归的消除方法:引入一个新的非终结符,把含有左递归的产生式改写为右递归形式。例如:AA|,是任意串且不以A开头。A的产生式可改写为:A AA A|例如,算术表达式文法GE为:GE:EE+T|TTT*F|FF(E)|i消去直接左递归后得到文法GE:GE:ETEE+TE|TFTT*FT|F(E)|i一般地,设文法中A的产生式为:AA 1|A 2|A m|1|2|n其中,每个都不等于每个都不以A开头

27、消除A的直接左递归,文法可改写为:A 1A|2A|nAA 1A|2A|mA|例如,试消除EE+T|ET|T的左递归。解:消除左递归后变为ETEE+TE|TE|间接左递归的消除间接左递归的消除例如,文法GS:SQc|cQRb|bRSa|a如何消除文法的间接左递归？间接左递归的存在是由于非终结符之间形成了循环推导,只要把循环推导中的某个连接切断,间接左递归就消除了。切断循环推导中的某个连接的方法：Step1.对n个个产生式中的某一个进行至多至多n-1次次替换,使间接左递归变成直接左递归,再消除之。例如,消除上述文法GS中S,Q间的连接间的连接:SQc|cRbc|bc|cSabc|abc|bc|c改

28、写为:SabcS|bcS|cSSabcS|消除左递归还需消除Q,R间的连接间的连接:QRb|bSab|ab|Qab|b再消除其直接左递归Step2.对其余其余n-1个个产生式中的某一个进行至多至多n-2次次替换,再消除直接左递归。考虑上述文法的后两个产生式:QRb|bRSa|a|Qa消除左递归算法消除左递归算法:(1)文法的所有非终结符排序为A1,A2,An;(2)将间接左递归改为直接左递归,消除之;for(i=1;i=n;i+)for(j=1;j=i1;j+)把AiAj|及Aj1|k改写为Ai1|k|;消除Ai的直接左递归;(3)化简,删去那些不可达元的产生式。通过例子熟悉消除左递归算法消除

29、左递归算法执行过程:例如,GS:SQc|cQRb|bRSa|a(1)将非终结符排序为R,Q,S;(2)对于对于R(i=1,P1)内层循环不执行;消除R的直接左递归:RSa|a对于对于Q(i=2,P2)内层循环改写P2P1:QSab|ab|b消除Q的直接左递归:QSab|ab|b对于对于S(i=3,P3)内层循环改写P3P1和P3P2:SSabc|abc|bc|c消除S的直接左递归:SabcS|bcS|cSSabcS|于是得文法GS:SabcS|bcS|cSSabcS|QSab|ab|bRSa|a(3)化简,删去关于Q和R的产生式。对消除左递归算法的两点说明:(1)消除左递归算法有两个限制条件:

30、文法中不不含含回回路路(PP)和-生生成成式式。该限制不会影响消除左递归算法的使用,因为后续课程形式语言中将学到,对任一CFGG,存在一个不不含含-生生成成式式和单单一一生生成成式式的CFGG,使得L(G)=L(G)-。(2)对非终结符的不同排序会导致文法形式上的不同,但可证明它们等价。上例若排序为S,Q,R,则得文法GS:SQc|cQRb|bRbcaR|caR|aRRbcaR|GS与GS等价的证明:证明:Sabc(abc)*|bc(abc)*|c(abc)*L(G)=(abc|bc|c)(abc)i|i0Sbca(bca)*bc|ca(bca)*bc|a(bca)*bc|bc|cL(G)=(

31、abc|bc|c)(abc)i|i0有兴趣的同学课后以下述文法为例熟悉消除左递归算法的执行过程:GS:SQc|c|RcQRb|b|SbRSa|a|QaGS:SQc|c|Rc|ScQRb|b|Sb|QbRSa|a|Qa|Ra2.回溯的消除回溯的消除要消除回溯,首先要清楚回溯存在的原因,根除这些原因,自然就消除了回溯。假 设 轮 到 用 A去 执 行 匹 配 任 务,A 1|2|n,而A面临的第1个输入符为a1。首先,用1的第1终结符与输入符a1匹配,若成功,再用1的第2终结符与下一输入符a2匹配,当1的第n终结符与当前输入符an匹配不成功时,说明1与输入串不匹配,此时需把关于1的分析过程推倒,回

32、到用1匹配前的状态。同样地,用2与输入串匹配,。可见,回溯的存在是由于分析过程中需对产生式的多个候选式进行试探性匹配。若能根据面临的输入符从产生式的多个候选式中选出一个作为全全权权代代表表,使得若该候选式与输入串匹配成功,则A与输入串匹配成功,若该候选式与输入串匹配不成功,则A与输入串匹配不成功,这样就可以消除回溯。如何从多个候选式中选出一个全权代表?例如,AaA|bB|cCaA 1|2|na若A的n个候选式中只只有有一一个个推出的终结符串的首字符包含a(设为 i),则候选式 i可作为A的全权代表。这就要求匹配前先求出各个候候选选式所能推出的所有终终结结符串的首首字字符符,即候选式的终结首符终

33、结首符集集FIRST()。终结首符集终结首符集FIRST()令G是一个无左递归文法,对G的所有非终结符的每个候选式,定义FIRST()a|a,aVT若,则FIRST()*即FIRST()是由所能推出的的所有所有终结符串的首字符或。A 1|2|nFIRST(A)=FIRST(1)FIRST(2)对于A 1|2|n若A有多个候选式的终结首符集含a,则仍需进行试探,此时只是减少了回溯次数,并未消除回溯。要消除回溯,准确地指派一个候选式去执行匹配任务,则各个候选式的终结首符集应互不相交,即FIRST(i)FIRST(j)=(ij)如何使每个非终结符的候选终结首符集互不相交?方法是提取公共左因子提取公共

34、左因子。提取公共左因子提取公共左因子例如,AabA|aB|ab改写文法:AaAAbA|B|b改写第2式:AbA|BAA|一般地,假设文法中关于A的产生式为A 1|2|i|i+1|j提取公共左因子后,改写为AA|i+1|jA 1|2|i经过反反复复提提取取公公共共左左因因子子,可使每个非终结符的候选终结首符集候选终结首符集互不相交。消除左递归和提取公共左因子后,文法不再含左递归且任一非终结符的候选终结首符集互不相交。此时,若不属于任一非终结符的候选终结首符集,则可进行有效的LL(1)分析了。然而,消除左递归和提取左因子后,文法中引进了大量-生成式,这就引出自动匹配自动匹配问题。3.自动匹配问题自

35、动匹配问题对于文法GE:ETEE+TE|TFTT*FT|F(E)|i考虑输入串i+i#EETFTT+Ei FTi当 A面 临 输 入 符 a时,若a FIRST(A)且FIRST(A),则考虑自动匹配问题。对于上述算术表达式文法,若输入串为i/i,即使让T自动匹配,“/”仍不能与后面符号匹配,此时没必要让T自动匹配。结论:只有在当当前前输输入入符符能与A后后的的第第一一个个终终结结符符匹配成功时,才让A自动得到匹配。这就要求分析前先求出紧跟在A后的终结符,即FOLLOW(A)。FOLLOW(A)的定义的定义对文法GS的任一非终结符A,定义FOLLOW(A)a|SAa,aVT若SA,则规定#FO

36、LLOW(A)*即FOLLOW(A)是所有句型所有句型中紧跟在A之后的终结符终结符或#。0因SS,故#FOLLOW(S)自动匹配条件自动匹配条件当A面临输入符a时,若a FIRST(A)且FIRST(A),则只有当a FOLLOW(A)时,才使A自动得到匹配。缺少任一条件,均不自动匹配。若输入符aFIRST(A)且aFOLLOW(A),则当FIRST(A)时仍需进行试探(回溯)。因此,对于存存在在-生生成成式式的非终结符A,若要进行不带回溯的自上而下分析,则FIRST(A)与与FOLLOW(A)应应互不相交互不相交。5.递归下降分析器递归下降分析器递归下降分析法是一种自上而下分析法,文法的每个

37、非非终终结结符符对应一个递递归归过过程程。分析过程从文法开始符出发,执行一组递归过程,这样向下推导直到推出句子。若文法不不含含左左递递归归且每个非终结符的候选式无公共左因子,则可构造不带回溯的递归下降分析程序,该程序由一组过程组成,每个过程对应文法的一个非终结符。这样的分析程序称为递归下降分析器递归下降分析器。例如,考虑不含左递归的算术表达式,其对应的递归下降分析器:voidE()T();E();voidE()if(lookahead=+)match(+);T();E();voidT()F();T();voidT()if(lookahead=*)match(*);F();T();voidF()

38、if(lookahead=i)match(i);elseif(lookahead=()match();E();if(lookahead=)match();elseerror();error();说明:考虑E的产生式:E+TE|E有两个候选式,当E面临输入符+时令第一个候选工作,当面临其它符号时,E自动获得匹配。递归函数E根据这一原则设计。假定递归函数的调用以栈栈的形式来模拟,下面分析输入串#i1*(i2+i3)#的语法分析过程,“#”为分隔符。进行语法分析时,首先将“#”和文法开始符E压入栈中,当语法分析进行到栈中仅剩“#”而输入串扫描指针已指向输入串尾部的“#”时,则语法分析成功。分析过程如

39、图3-12所示。3.3.2LL(1)分析法分析法LL(1)分析法又称预预测测分分析析法法,是一种不带回溯的非递归自上而下分析法。LL(1)的的含含义义:第一个L表明自自左左至至右右扫扫描描输输入入串串;第二个L表明最最左左推推导导;1表明向右查看一个符号。类似地,可有LL(k)文法,即向前查看k个符号才能确定选用哪个产生式,不过LL(k)(k1)在实际中极少使用。1.表驱动的表驱动的LL(1)分析器分析器LL(1)分分析析法法的的基基本本思思想想:根据输入串的当前输入符确定选用某某一一个个产生式进行推导,当该输入符与推导的第一个符号相同时，再取输入串的下一个符号,继续确定下一个推导应选的产生式

40、,如此下去,直到推出被分析的输入串为止。一个LL(1)分析器由一一张张LL(1)分分析析表表(预测分析表)、一一个个先先进进后后出出分分析析栈栈和一个控制程序控制程序(表驱动程序)组成。a1a2aian#分析表M控制程序输入串：栈顶#x1xj输出分析栈图314LL(1)分析器对图314的LL(1)分析器说明如下：(1)输输入入串串是待分析的符号串,它以“#”作为结束标志。(注:#VT但不是文法符号,是由分析程序自动添加的)(2)分分析析栈栈存放分析过程中的文文法法符符号号。分析开始时栈底先放一个“#”,再压入文法开始符;当分析栈中仅剩“#”且输入串指针指向串尾的“#”时,分析成功。(3)分分析

41、析表表用一个矩阵M(二维数组)表示,它概括了文法的全部信息。矩矩阵阵的的每每一一行行与与文文法法的的一一个个非非终终结结符符相相关关联联,而而每每一一列列与与文文法法的的一一个个终终结结符符或或“#”关关联联。分析表元素MA,a中的内容为一条A的产生式,表明当A面临输入符a时应采用的候选式;当元素内容为空时,表明A不应面临输入符a,即输入串含语法错误。(4)控制程序控制程序根据分析栈栈顶符号栈顶符号x和当当前输入符前输入符a决定分析器的动作:若xa“#”,则分析成功。若xa“#”,即栈顶符号x与当前输入符a匹配,则将x从栈顶弹出,输入串指针后移,继续对下一个字符进行分析。若x为非终结符非终结符

42、A,则查分析表MA,a:i.若MA,a为一产生式,则A自栈顶弹出,MA,a中产生式的右部符号逆序压栈逆序压栈;若MA,a为A,则只将A自栈顶弹出。ii.若MA,a为空,则发现语法错误,调用出错处理程序进行处理。控制程序控制程序描述如下:将“#”和文法开始符依次入栈;把第一个输入符读入a;do把栈顶符号弹出并放入x中;if(xVT)if(xa)将下一输入符读入a;elseerror();elseif(Mx,a“xy1y2yk”)把y1y2yk按逆序入栈逆序入栈;输出“xy1y2yk”;elseerror();while(x!=“#”)例例3.7一个文法的LL(1)分析表如下所示,试给出输入串aa

43、dl的分析过程。输入串aadl的分析过程如下:符号栈当前输入符输入串说明#Aaadl#弹出栈顶符,将AaA右部反序压栈#Aaaadl#匹配,弹出栈顶符a,读出下一输入符a#Aadl#弹出栈顶符,将AABl右部反序压栈#lBAadl#弹出栈顶符,将AaA右部反序压栈#lBAaadl#匹配,弹出栈顶符a,读出下一输入符d#lBAdl#由A仅弹出栈顶符号A#lBdl#弹出栈顶符,将BdB右部反序压栈#lBddl#匹配,弹出栈顶符d,读出下一输入符l#lBl#由B仅弹出栈顶符号B#ll#匹配,弹出栈顶符l,读出下一输入符#匹配,分析成功2.LL(1)分析表的构造分析表的构造LL(1)分析器中除分析表因

44、文法的不同而不同外,分析栈、控制程序都相同。因此构造一个LL(1)分析器实际上就是构造文法的LL(1)分析表。构造分析表M,需预先定义FIRST集和FOLLOW集。假定是文法任一符号串,(VTVN)*,FIRST()a|a,aVT若,则规定FIRST()即FIRST()是的所有所有可能推出的首首终结符终结符或可能的。*(1)FIRST集的构造方法集的构造方法对任一终结符a,FIRST(a)=a。对每个非终结符每个非终结符X连续使用下述规则直到FIRST集不再增大为止。若有Xa,把a加入FIRST(X);若有X,把加入FIRST(X);若有XY,YVN,把FIRST(Y)的所有非所有非元素元素都

45、加入FIRST(X);若有XY1Y2Yk,而Y1Yi1都有,则把FIRST(Yj)(j=1,2,i)的所有非元素都加入FIRST(X);特别地,若Y1Yk均有产生式,则把也加入到FIRST(X)。例例1试构造文法GE的FIRST集。GE:ETEE+TE|TFTT*FT|F(E)i解:FIRST(E)=+,;FIRST(T)=*,;FIRST(F)(,i;由TF知,把FIRST(F)的所有非元素加入FIRST(T),故FIRST(T)=(,i;由ET知,把FIRST(T)的所有非元素加入FIRST(E),故FIRST(E)=(,i对文法GS的任何非终结符A,定义定义FOLLOW(A)a|SAa,

46、aVT若SA,则规定#FOLLOW(A)FOLLOW(A)是所有所有句型中出现在紧随A之后的终结符终结符或#。*(2)FOLLOW集构造方法集构造方法对文法每个非终结符每个非终结符A构造FOLLOW(A)。方法是连续使用下述规则,直到FOLLOW 集不再增大为止。对文法开始符S,把#加入FOLLOW(S)。(由语句括号“#S#”中的S#得到)若有AB(可为空),则将FIRST()加入FOLLOW(B)。若有AB或AB且,则把FOLLOW(A)加入到FOLLOW(B)。*例例2试构造文法GE的FOLLOW集。GE:ETEE+TE|TFTT*FT|F(E)|i解:1)FOLLOW(E)=#;2)由

47、由ETE知,FIRST(E)属于FOLLOW(T),即FOLLOW(T)+;由E+TE|,FIRST(E)属于由由TFT知,FIRST(T)属于FOLLOW(F),即FOLLOW(F)*;由T*FT|知,FIRST(T)属于由由F(E)|i知,FIRST()属于FOLLOW(E),即FOLLOW(E),#;3)由由ETE知,FOLLOW(E)属于FOLLOW(E),即FOLLOW(E),#;由由ETE且E知,FOLLOW(E)属于FOLLOW(T),即FOLLOW(T)+,),#;由E+TE知,FOLLOW(E)属于FOLLOW(E)由E+TE且E知,FOLLOW(E)属于FOLLOW(T)由

48、由TFT知,FOLLOW(T)属于FOLLOW(T)，即FOLLOW(T)+,),#;由由TFT且T知,FOLLOW(T)属于FOLLOW(F),即FOLLOW(F)*,+,),#；由T*FT知,FOLLOW(T)属于FOLLOW(T)由T*FT且T知,FOLLOW(T)属于FOLLOW(F)考虑F(E)|i(3)构造分析表构造分析表M对每个产生式A1|n执行,。对 FIRST(A)中 每 个 终 结 符 a,把A i加入到MA,a,其中为终结首符集中含a的候选式i或唯一候选式。若FIRST(A),则对任何属于FOLLOW(A)的终结符b,将A加入MA,b。把所有无定义的MA,a标记为出错。若

49、一个文法G的LL(1)分析表不含多重入口,则称它是一个LL(1)文法文法。LL(1)文法所定义的语言恰好是它的分析表所能识别的全部句子。一个CFG文法是LL(1)文法的充要条件:(1)文法不含左递归。(2)文法中每个非终结符的各个候选式的终结首符集互不相交。(3)对文法的任一非终结符A,若A的候选终结首符集包含,则FIRST(A)FOLLOW(A)。例例3.8试构造文法GE的LL(1)分析表。GE:ETEE+TE|TFTT*FT|F(E)i解:首先构造首先构造FIRST集集:FIRST(E)=+,FIRST(T)=*,FIRST(F)(,iFIRST(T)=(,iFIRST(E)=(,i其次构

50、造其次构造FOLLOW集集:FOLLOW(E),#;FOLLOW(E),#FOLLOW(T)+,),#FOLLOW(T)+,),#FOLLOW(F)*,+,),#最后构造文法最后构造文法GE的的LL(1)分析表分析表:i+*()#EETEETEEE+TEEETTFTTFTTTT*FTTTFFiF(E)例例3.9程序语言中if-else语句的文法GS为:GS:SiESeSiESaEb其中,e遵从最近匹配原则。试改写文法改写文法并构造其LL(1)分析表。解:通过提取公共左因子,得文法GS:GS:SiESSaSeS|Eb首先求每个非终结符的首先求每个非终结符的FIRST集集：FIRST(S)=i,a