教学课件：《编译技术》.ppt

1、第三章第三章:词法分析词法分析3.1 3.1 词法分析的功能词法分析的功能 识别单词，返回单词的类别和值识别单词，返回单词的类别和值3.2 3.2 词法分析程序的设计与实现词法分析程序的设计与实现状态图：状态图：有穷自动机的非形式表示有穷自动机的非形式表示正则文法和状态图正则文法和状态图八月十五日夜湓亭望月八月十五日夜湓亭望月 白居易白居易昔年八月十五夜曲江昔年八月十五夜曲江池畔杏园边今年八池畔杏园边今年八月十五夜湓浦沙头月十五夜湓浦沙头水馆前西北望乡何水馆前西北望乡何处是东南见月几回处是东南见月几回圆昨风一吹无人会圆昨风一吹无人会今夜清光似往年今夜清光似往年八月十五日夜湓亭望月八月十五日夜湓

2、亭望月 白居易白居易昔年八月十五夜，曲江池畔杏园边。昔年八月十五夜，曲江池畔杏园边。今年八月十五夜，湓浦沙头水馆前。今年八月十五夜，湓浦沙头水馆前。西北望乡何处是，东南见月几回圆。西北望乡何处是，东南见月几回圆。昨风一吹无人会，今夜清光似往年。昨风一吹无人会，今夜清光似往年。八月十五日夜湓亭望月八月十五日夜湓亭望月 白居易白居易昔年八月十五夜，曲江池畔杏园边。昔年八月十五夜，曲江池畔杏园边。今年八月十五夜，湓浦沙头水馆前。今年八月十五夜，湓浦沙头水馆前。西北望乡何处是，东南见月几回圆。西北望乡何处是，东南见月几回圆。昨风一吹无人会，今夜清光似往年。昨风一吹无人会，今夜清光似往年。词法分析：词法

3、分析：断词，并给出词性（分类）断词，并给出词性（分类）语法分析：语法分析：断句，并给出句的结构、分类断句，并给出句的结构、分类程序int main()n int count=read();n/if number of entries read is greater than 1 n/then sort()and compact()n if(count 1)sort();compact();n if(count=0)n count 1)sort();compact();if(count=0)count 0,其中其中B=01,10左线性文法的状态图的画法：左线性文法的状态图的画法：1.令令G的每个

4、非终结符都是一个状态；的每个非终结符都是一个状态；2.设一个开始状态设一个开始状态S；3.若若Q:=T,QVn,TVt,则：则：QST4.若若Q:=RT,Q、RVn,TVt,则：则：QRT5.按自动机方法，可加上开始状态和终止状态标志。按自动机方法，可加上开始状态和终止状态标志。例：正则文法例：正则文法Z:=U0|V1U:=Z1|1V:=Z0|0例如：正则文法 Z:=U0|V1 U:=Z1|1 V:=Z0|0 其状态图为：ZSUV111000 Start1.每个非终结符设一个状态；每个非终结符设一个状态；2.设一个开始状态设一个开始状态S；3.若若Q:=T,QVn,TVt,4.若若Q:=RT,

5、Q、RVn,TVt,5.加上开始状态和终止状态标志加上开始状态和终止状态标志识别算法识别算法利用状态图可按如下步骤分析和识别字符串利用状态图可按如下步骤分析和识别字符串x：1、置初始状态为当前状态，从、置初始状态为当前状态，从x的最左字符开始，重复步骤的最左字符开始，重复步骤2，直到，直到x右端为止。右端为止。2、扫描、扫描x的下一个字符，在当前状态所射出的弧中找出标记有该字的下一个字符，在当前状态所射出的弧中找出标记有该字符的弧，并沿此弧过渡到下一个状态；如果找不到标有该字符的弧，符的弧，并沿此弧过渡到下一个状态；如果找不到标有该字符的弧，那么那么x不是句子，过程到此结束；如果扫描的是不是句

6、子，过程到此结束；如果扫描的是x的最右端字符，并的最右端字符，并从当前状态出发沿着标有该字符的弧过渡到下一个状态为终止状态从当前状态出发沿着标有该字符的弧过渡到下一个状态为终止状态Z，则则x是句子。是句子。例：x=0110 和10111SUVZ11000问题：问题：1、上述分析过程是属于自底向上分析？还是自顶向下分析？2、怎样确定句柄？1SUVZ110001 0 0 1UZVZZ=|=V1=|=Z01=|=U001=|=10013.4词法分析程序的设计与实现词法分析程序的设计与实现词法规则词法规则 状态图状态图 词法分析程序词法分析程序3.4.1文法及其状态图文法及其状态图语言的单词符号语言的

7、单词符号 标识符标识符 保留字保留字(标识符的子集）标识符的子集）无符号整数无符号整数 单分界符单分界符 +*：，：，（）双分界符双分界符 :=:=两点说明：两点说明：1.空格的作用空格的作用2.实数的表示实数的表示文法：文法：1.:=字母字母|字母字母|数字数字2.:=数字数字|数字数字3.:=:|+|*|,|(|)4.:=5.:=:标识符S标出口出口非字母数字字母字母、数字无符号整数S数出口出口非数字数字数字单字符分界符S单界出口出口其他字符+*，（）双字符分界符S冒号：双界=出口出口其他字符非=标识符 无符号整数单字符分界符双字符分界符S标非字母数字字母字母、数字数非数字数字数字单界其他

8、字符+*，（）出口出口冒号其他字符：双界=非=出错出错其他读字符读字符查保留字表查保留字表返回返回S读字符TOKEN:=出错组合标识符R查保留字表输出标识符:组数R输出常数输出单分界符读字符输出:=:R输出:读字符读去注释:YYN输出保留字YN出口NYYNNNNYYNYY转入口R输出/N是空字符？是字母？是保留字？是数字？是单分界符？是冒号？是斜竖？是=？是*？入口见教材3.4.2状态图的实现状态图的实现构造词法分析程序构造词法分析程序1.单词及内部表示单词及内部表示2.词法分析程序需要引用的公共（全局）变量和过程词法分析程序需要引用的公共（全局）变量和过程3.词法分析程序算法词法分析程序算法

9、1.单词及内部表示单词及内部表示:保留字和分界符采用一符一类保留字和分界符采用一符一类单词名称单词名称BEGINENDFORDOIFTHENELSE标识符标识符常数常数(整整):+*,():=类别编码类别编码12345678910111213141516记忆符记忆符BeginSymEndSymForSymDoSymIfSymThenSymElseSymIdSymIntSymColonSymPlusSymStarSymComSymLparSymRparSymAssignSym单词值单词值-内部字符串内部字符串整数值整数值-2.词法分析程序需要引用的公共（全局）变量和过程词法分析程序需要引用的公共

10、（全局）变量和过程名称名称4char4token4getchar4getNBC4CAT4IsLetter和和IsDigit4UnGetCH4RESERVE4ATOI4Error类别类别字符变量字符变量字符数组字符数组读字符过程读字符过程过程过程过程过程布尔函数布尔函数过程过程布尔函数布尔函数函数函数过程过程功能功能存放当前读入的字符存放当前读入的字符存放单词字符串存放单词字符串读字符读字符到到char,移动指针移动指针反复反复调用调用getchar,直至直至char进入进入一个非空白字符一个非空白字符char与与token连接连接判断判断读字符指针后退一个字符读字符指针后退一个字符判断判断to

11、ken中中的字符串的字符串是保留字是保留字,还是标识符还是标识符字符串到数字的转换字符串到数字的转换出错处理出错处理3、词法分析程序算法、词法分析程序算法START:token:=;/*置置token为空串为空串*/getchar;GetNBC;CASEcharOFa.z:BEGINWHILEIsLetterORIsDigitDOBEGINCAT;getcharEND;UnGetCH;C:=RESERVE;/*返回返回0，为标识符，为标识符*/IFC=0THENRETURN(IDSY:TOKEN)ELSERETURN(C,-)/*C为保留字编码为保留字编码*/END;0.9:BEGINWHIL

12、EIsDigitDOBEGINCAT;getcharEND;UnGetCH;RETURN(INTSY,ATOI)END;+:RETURN(PLUSSY,-);S标非字母数字字母字母、数字数非数字数字数字单界其他字符+*，（）出口出口冒号其他字符：双界=非=出错出错其他*:RETURN(StarSym,-);,:RETURN(ComSym,-);(:RETURN(LparSym,-);):RETURN(RparSym,-);:BEGINgetchar;ifCHAR=THENRETURN(AssignSym,-);UnGetCH;RETURN(ColonSym,-);ENDENDOFCASE;ER

13、ROR;GOTOSTART;练习：用练习：用C语言实现上述算法。语言实现上述算法。S标非字母数字字母字母、数字数非数字数字数字单界其他字符+*，（）出口出口冒号其他字符：双界=非=出错出错其他int getsym()/*返回类别编码*、clearToken();while(isSpace()|isNewline()|isTab()getchar();/*读取字符，跳过空格、换行和Tab*/if(isLetter()/*判断当前字符是否是一个字母*/while(isLetter()|isDigit()/*将字符拼接成字符串*/catToken();getchar();retract();/*指针

14、后退一个字符*/int resultValue=reserver();/*resultValue是查找保留字的返回值*/if(resultValue=0)symbol=IDSY;/*resultValue=0，token中的字符串为标识符*/else symbol=resultValue;/*否则token中的字符串为保留字*/else if(isDigit()/*判断当前字符是否是一个数字*/while(isDigit()/*将字符拼接成整数*/catToken();getchar();retract();num=transNum(token)；/*将token中的字符串转换成整数*/sym

15、bol=INTSY;/*此时识别的单词是整数*/。见教材第三章作业第三章作业1 1：P56 1,2,4(P56 1,2,4(词法见词法见50-5150-51页页)语法分析的功能、基本任务语法分析的功能、基本任务 自顶向下分析法自顶向下分析法 自底向上分析法自底向上分析法编译过程是指将编译过程是指将高级语言程序高级语言程序翻译为等价的翻译为等价的目标程目标程序序的过程。的过程。复习：第一章复习：第一章概述概述词法分析词法分析语法分析语法分析语义分析、生成中间代码语义分析、生成中间代码代码优化代码优化生成目标程序生成目标程序习惯上是将编译过程划分为习惯上是将编译过程划分为5 5个基本阶段：个基本阶

16、段：4.1语法分析概述语法分析概述功能：功能：根据文法规则，从源程序根据文法规则，从源程序单词符号串单词符号串中识别出语法中识别出语法成分，并进行语法检查。成分，并进行语法检查。基本任务：基本任务：识别符号串识别符号串S是否为某语法成分。是否为某语法成分。两大类分析方法：两大类分析方法：自顶向下分析自顶向下分析自底向上分析自底向上分析s 主要问题主要问题:左递归问题左递归问题 回溯问题回溯问题若若ZS则则S L(GZ)否则否则S L(GZ)GZ 主要方法主要方法:递归子程序法递归子程序法 LL分析法分析法自顶向下分析算法的基本思想为：自顶向下分析算法的基本思想为：+自底向上分析算法的基本思想为

17、：自底向上分析算法的基本思想为：+若若ZS则则S L(GZ)否则否则S L(GZ)GZs 主要问题主要问题:句柄的识别问题句柄的识别问题 主要方法主要方法:算符优先分析法算符优先分析法 LR分析法分析法4.2自顶向下分析自顶向下分析4.2.1自顶向下分析的一般过程自顶向下分析的一般过程可以通过一例子来说明语法分析过程可以通过一例子来说明语法分析过程给定符号串给定符号串S，若预测是某一语法成分，则可根据该，若预测是某一语法成分，则可根据该语法成分的文法语法成分的文法,设法为设法为S构造一棵语法树，构造一棵语法树，若成功若成功,则则S最终被识别为某一语法成分最终被识别为某一语法成分,即即S L(G

18、Z)，其中，其中GZ为某语法成分的文法为某语法成分的文法若不成功若不成功,则则S L(GZ)例：例：S=cadGZ:Z =cAdA =ab|a求解求解S L(GZ)?分析过程是设法建立一分析过程是设法建立一棵语法树棵语法树,使语法树的末端结使语法树的末端结点与给定符号串相匹配。点与给定符号串相匹配。1.开始开始:令令Z为根结点为根结点Z2.用用Z的右部符号串去匹配输入串的右部符号串去匹配输入串ZcAd完成一步推导完成一步推导ZcAd检查检查,c-c匹配匹配A是非终结符是非终结符,将匹配任务交给将匹配任务交给A3.选用选用A的右部符号串匹配输入串的右部符号串匹配输入串A有两个右部有两个右部,选第

19、一个选第一个cAdabZ完成进一步推导完成进一步推导Aab检查检查,a-a匹配匹配,b-d不匹配不匹配(失败失败)但是还不能冒然宣布但是还不能冒然宣布S L(GZ)4.回溯回溯即砍掉即砍掉A的子树的子树改选改选A的第二右部的第二右部ZcAdaAa检查检查a-a匹配匹配d-d匹配匹配建立语法树建立语法树,末端结点为末端结点为cad,与输入与输入cad相匹配相匹配,建立了推导序列建立了推导序列ZcAdcadcad L(G(Z)S=cadGZ:Z =cAdA =ab|a自顶向下分析方法特点自顶向下分析方法特点:1.分析过程是带预测的，对输入符号串要预测属于什么分析过程是带预测的，对输入符号串要预测属

20、于什么语法成分，然后根据该语法成分的文法建立语法树。语法成分，然后根据该语法成分的文法建立语法树。2.分析过程是一种试探过程，是尽一切办法分析过程是一种试探过程，是尽一切办法(选用不同选用不同规则规则)来建立语法树的过程来建立语法树的过程,由于是试探过程由于是试探过程,难免难免有失败有失败,所以分析过程需进行回溯所以分析过程需进行回溯,因此也称这种方法因此也称这种方法是带回溯的自顶向下分析方法。是带回溯的自顶向下分析方法。3.最左推导可以编写程序来实现最左推导可以编写程序来实现,但带溯的自顶向下分但带溯的自顶向下分 析方法在实际上价值不大析方法在实际上价值不大,效率低。效率低。4.2.2自顶向

21、下分析存在的问题及解决方法自顶向下分析存在的问题及解决方法1、左递归文法：左递归文法：自顶向下分析的基本缺点是：自顶向下分析的基本缺点是：不能处理具有左递归性的文法不能处理具有左递归性的文法这个文法是左递归的。这个文法是左递归的。有如下文法：有如下文法：令令U是文法的任一非终结符，文法中有规则是文法的任一非终结符，文法中有规则U =U或者或者UU+为什么？为什么？如果在匹配输入串的过程中，假定正好轮到要用非终结如果在匹配输入串的过程中，假定正好轮到要用非终结符符U直接匹配输入串，即要用直接匹配输入串，即要用U的右部符号串的右部符号串U去匹配，去匹配，为了用为了用U去匹配，又得用去匹配，又得用U

22、去匹配，这样无限的循环下去匹配，这样无限的循环下去将无法终止。去将无法终止。如果文法具有间接左递归，则也将发生上述问题，只不如果文法具有间接左递归，则也将发生上述问题，只不过环的圈子兜得更大。过环的圈子兜得更大。要实行自顶向下分析，必须要消除文法的左递归，下面要实行自顶向下分析，必须要消除文法的左递归，下面将介绍直接左递归的消除方法，在此基础上再介绍一般左递将介绍直接左递归的消除方法，在此基础上再介绍一般左递归的消除方法。归的消除方法。消除直接左递归消除直接左递归方法一，使用扩充的方法一，使用扩充的BNF表示来改写文法表示来改写文法例：例：(1)E =E+T|TE =T+T(2)T =T*F|

23、T/F|FT =F*F|/Fa.改写以后的文法消除了左递归。改写以后的文法消除了左递归。b.可以证明，改写前后的文法是等价的，表现在可以证明，改写前后的文法是等价的，表现在L(G改前改前)=L(G改后改后)如何改写文法能消除左递归，又前后等价，如何改写文法能消除左递归，又前后等价，可以给出两条规则可以给出两条规则:规则一（提因子）规则一（提因子）若：若：U =xy|xw|.|xz则可改写为：则可改写为：U =x(y|w|.|z)若：若：y=y1y2,w=y1w2则则U =x(y1(y2|w2)|.|z)若有规则：若有规则：U =x|xy则可以改写为：则可以改写为：U =x(y|)注意：不应写成

24、注意：不应写成U =x(|y)使用提因子法，不仅有助于消除直接左递归，而且有使用提因子法，不仅有助于消除直接左递归，而且有助于压缩文件的长度，使我们能更有效地分析句子。助于压缩文件的长度，使我们能更有效地分析句子。规则二规则二UUvUvvUvvv可以改写为可以改写为U =(x|y|z)v其特点是：具有一个直接左递归的右部并位于最后，其特点是：具有一个直接左递归的右部并位于最后，这表明该语法类这表明该语法类U是由是由x或或y或或z其后随有零个其后随有零个或多个或多个v组成。组成。通过以上两条规则，就能消除文法的直接左递归，通过以上两条规则，就能消除文法的直接左递归，并保持文法的等价性。并保持文法

25、的等价性。若有文法规则：若有文法规则：U =x|y|z|Uv方法二，将左递归规则改为右递归规则方法二，将左递归规则改为右递归规则规则三规则三若：若：P =P|则可改写为：则可改写为：P =PP =P|例例1E =E+T|T右部无公因子，所以不能右部无公因子，所以不能用规则一。用规则一。为了使用规则二，为了使用规则二，令令E =T|E+T由规则二可以得到由规则二可以得到E =T+T例例2T =T*F|T/F|FT =T(*F|/F)|F规则一规则一T =F|T(*F|/F)T =F(*F|/F)规则二规则二即即T =F*F|/F右递归：右递归：T:=FTT:=*FT|/FT|规则一：（提因子）规

26、则一：（提因子）规则二：规则二：U =x|y|z|Uv,则则U =(x|y|z)v规则三：右递归规则三：右递归P =P|，则，则P =P，P =P|消除一般左递归消除一般左递归一般左递归也可以通过改写文法予以消除。一般左递归也可以通过改写文法予以消除。消除所有左递归的算法：消除所有左递归的算法：1.1.把把G G的非终结符整理成某种顺序的非终结符整理成某种顺序A A1 1，A A2 2，AAn n ，使得：，使得：A A1 1:=:=1 1|2 2|k k A A2 2:=A:=A1 1 r r A A3 3:=A:=A2 2u|u|A A1 1v.v.2.Fori:=1tondobeginf

27、orj:=1toi-1do把每个形如把每个形如Ai =Ajr的规则替换成的规则替换成Ai =(1|2|k)r,其中其中Aj =1|2|k是当前全部是当前全部Aj的规则的规则;消除消除Ai规则中的直接左递归规则中的直接左递归end3.化简由化简由2得到的文法即可。得到的文法即可。例：文法例：文法Gs为为S =Qc|cQ =Rb|bR =Sa|a非终结符顺序重新排列非终结符顺序重新排列R =Sa|aQ =Rb|bS =Qc|c该文法无直接左递归，但有间接左递归该文法无直接左递归，但有间接左递归SQcRbcSabcSSabc+1.检查规则检查规则R是否存在直接左递归是否存在直接左递归R =Sa|a2

28、.把把R代入代入Q的有关选择，改写规则的有关选择，改写规则QQ =Sab|ab|b3.检查检查Q是否存在直接左递归是否存在直接左递归4.把把Q代入代入S的右部选择的右部选择S =Sabc|abc|bc|c5.消除消除S的直接左递归的直接左递归S =(abc|bc|c)abcR =Sa|aQ =Rb|bS =Qc|c最后得到文法为最后得到文法为:S =(abc|bc|c)abcQ =Sab|ab|bR =Sa|a可以看出其中关于可以看出其中关于Q和和R的规则是多余的规则的规则是多余的规则经过压缩后经过压缩后S =(abc|bc|c)abc可以证明改写前后的文法是等价的可以证明改写前后的文法是等价

29、的应该指出应该指出,由于对非终结符的排序不同由于对非终结符的排序不同,最后得到的文法在形最后得到的文法在形式上可能是不一样的式上可能是不一样的,但是不难证明它们的等价。但是不难证明它们的等价。2、回溯问题、回溯问题什么是回溯什么是回溯?分析工作要部分地或全部地退回去重做叫分析工作要部分地或全部地退回去重做叫回溯。回溯。造成回溯的条件：造成回溯的条件：文法中，对于某个非终结符号的规则其右部文法中，对于某个非终结符号的规则其右部有多个选择，并根据所面临的输入符号不能准确有多个选择，并根据所面临的输入符号不能准确地确定所要的选择时，就可能出现回溯。地确定所要的选择时，就可能出现回溯。回溯带来的问题：

30、回溯带来的问题：严重的低效率，只有在理论上的意义而无实际意义严重的低效率，只有在理论上的意义而无实际意义U:=1|2|3U 1 2 3效率低的原因效率低的原因1)语法分析要重做语法分析要重做2)语义处理工作要推倒重来语义处理工作要推倒重来为避免回溯，对文法的要求是为避免回溯，对文法的要求是:FIRST(i)FIRST(j)=(i j)定义定义FIRST(i)=a|ia,a Vt*设文法设文法G（不具左递归性），（不具左递归性），U VnU:=1|2|3U 1 2 3FIRST(1)FIRST(2)FIRST(2)消除回溯的途径：消除回溯的途径：1.改写文法改写文法对具有多个右部的规则对具有多个

31、右部的规则反复反复提取左因子提取左因子例例1U =xV|xWU,V,WVn,xVt+改写为改写为U =x(V|W)更清楚地表示为：更清楚地表示为：U =xZZ =V|W注意：注意：问题到此并没有结束，还需要问题到此并没有结束，还需要进一步检查进一步检查V和和W的首符号是否相交的首符号是否相交若若V =ab|cdFIRST(V)=a,cW =de|fgFIRST(W)=d,f只要不相交就可以根据输入符号确定只要不相交就可以根据输入符号确定目标，若相交，则要代入，并再次提目标，若相交，则要代入，并再次提取左因子。如：取左因子。如：V:=abw:=ac则：则：Z:=a(b|c)例例2：文法：文法G

32、=|=begin；end =beginendFIRST()=beginFIRST()=begin改写文法：改写文法：=begin（；end|end）引入引入 =begin =；end|end =begin =；end|end对于：对于：FIRST(；end)=real,integer,boolean,array,function,procedureFIRST(end)=标识符，标识符，goto,begin,if,for不相交。不相交。2.超前扫描超前扫描当文法不满足避免回溯的条件时，即各选择的首符号相当文法不满足避免回溯的条件时，即各选择的首符号相交时，可以采用超前扫描的方法，即向前侦察各输入

33、符交时，可以采用超前扫描的方法，即向前侦察各输入符号串的第二个、第三个符号来确定要选择的目标号串的第二个、第三个符号来确定要选择的目标这种方法是通过向前多看几个符号来确定所选择的目这种方法是通过向前多看几个符号来确定所选择的目标，从本质上来讲也有回溯的味道，因此比第一种方标，从本质上来讲也有回溯的味道，因此比第一种方法费时，但是假读仅仅是向前侦察情况，不作任何语法费时，但是假读仅仅是向前侦察情况，不作任何语义处理工作。义处理工作。例：例：=|=begin；end =beginend这两个选择的首符号是相交的，故读到这两个选择的首符号是相交的，故读到begin时并不能确定时并不能确定该用哪个选择

34、，这时可采用向前假读进行侦察，此例题只该用哪个选择，这时可采用向前假读进行侦察，此例题只需假读一次就可以确定目标。需假读一次就可以确定目标。因为因为的首符集为的首符集为real，integer，procedure而而的首符集为的首符集为标识符，标识符，if，for，begin只要超前假读得到的是只要超前假读得到的是“说明说明”的首符，便是第一个选择；的首符，便是第一个选择；若是若是“语句语句”的首符，就是第二个选择。的首符，就是第二个选择。为了在不采取超前扫描的前提下实现不带回溯的自顶向为了在不采取超前扫描的前提下实现不带回溯的自顶向下分析，文法需要满足两个条件：下分析，文法需要满足两个条件：

35、文法的两个条件文法的两个条件2、对文法的任一非终结符，若其规则右部有多个选择时，对文法的任一非终结符，若其规则右部有多个选择时，各选择各选择所推出的终结符号串的首符号集合要两两不相交。所推出的终结符号串的首符号集合要两两不相交。1、文法是非左递归的；、文法是非左递归的；在上述条件下，就可以根据文法构造有效的、不带回溯的在上述条件下，就可以根据文法构造有效的、不带回溯的自顶向下分析器。自顶向下分析器。为避免回溯，对文法的要求是为避免回溯，对文法的要求是:FIRST(i)FIRST(j)=(i j)定义定义设文法设文法G（不具有左递归性），（不具有左递归性），U VnU:=1|2|3FIRST(i

36、)=a|ia,a Vt*还有一种情况还有一种情况 E:=Ua U:=a|（回溯？）a？2、若=,则FIRST()FOLLOW(A)=*不带回溯的充分必要条件是：对于G的每一个非终结符A的任意两条规则A:=|,下列条件成立：1、FIRST()FIRST()=定义：定义：FOLLOW(A)=a|ZAa，aVtAVn,Z识别符号识别符号该集合称为该集合称为A的后继符号集合。的后继符号集合。特殊地：若特殊地：若Z.A则则#FOLLOW(A)*4.2.3递归子程序法（递归下降分析法）递归子程序法（递归下降分析法）具体做法：对语法的每一个非终结符都编一个分析程序，具体做法：对语法的每一个非终结符都编一个分

37、析程序，当根据文法和当时的输入符号预测到要用某个非终结符当根据文法和当时的输入符号预测到要用某个非终结符去匹配输入串时，就调用该非终结符的分析程序。去匹配输入串时，就调用该非终结符的分析程序。下面通过举例说明如何根据文法构造该文法的下面通过举例说明如何根据文法构造该文法的语法分析程序语法分析程序如文法如文法GZ:Z:=UVU:=.V:=.Z的分析程序的分析程序U的分析程序的分析程序V的分析程序的分析程序UV注：消除左递归后，可有其它递归：注：消除左递归后，可有其它递归：U:=UU:=WW:=U例：文法例：文法GZZ =(U)|aUbU =dZ|Ud|e1.检查并改写文法检查并改写文法Z =(U

38、)|aUbU =(dZ|e)d改写后无左递归且首符集不相交：改写后无左递归且首符集不相交：(a=de=2.检查文法的递归性检查文法的递归性因此，因此，Z和和U的分析程序要编成递归子程序的分析程序要编成递归子程序ZUZZZUZUUU+3.算法框图算法框图非终结符号的分析子程序的功能是：非终结符号的分析子程序的功能是：用规则右部符号串去匹配输入串。用规则右部符号串去匹配输入串。以下是以框图形式给出的两个子程序以下是以框图形式给出的两个子程序:入口(sym)=(读符号(sym)=)(sym)=a出口读符号 UerrorerrorTTF读符号Y U(sym)=bFFFTZ=(U)|aUbU=(dZ|e

39、)d在进入某个非终结符的分析程序时其所要分析的在进入某个非终结符的分析程序时其所要分析的语法成分的第一个符号已语法成分的第一个符号已读入读入sym中。在分析子程中。在分析子程序的出口前，一定要读取下一个符号到序的出口前，一定要读取下一个符号到sym中中。入口(sym)=d读符号(sym)=d(sym)=e出口读符号 ZerrorTTF读符号YFFZ=(U)|aUbU=(dZ|e)d说明说明要注意子程序之间的接口要注意子程序之间的接口,在程序编制时进入某个非终结在程序编制时进入某个非终结符的分析程序时其所要分析的语法成分的第一个符号已符的分析程序时其所要分析的语法成分的第一个符号已读入读入sym

40、中。中。递归子程序法对应的是递归子程序法对应的是最左推导最左推导过程过程4.2.4用递归子程序法构造语法分析程序的例子用递归子程序法构造语法分析程序的例子文法文法:=|IFTHEN|IFTHENELSE =i|i =|+=|*=|()改写文法改写文法:=|IFTHENELSE =i =+=*=|()语法分析程序所要调用的子程序语法分析程序所要调用的子程序:nextsym:词法分析程序词法分析程序,每调用一次读进一个单词每调用一次读进一个单词,单词的类别码放在单词的类别码放在sym中。中。error:出错处理程序。出错处理程序。PROCEDUREstate;/*语句分析子程序语句分析子程序*/I

41、Fsym=IFTHENBEGINnextsym;expr;IFsymTHENTHENerrorELSEBEGINnextsym;state;IFsym=ELSETHENBEGINnextsym;state;ENDENDENDELSEBEGINvar;IFsym =THENerrorELSEBEGINnextsym;expr;ENDEND =|IFTHENELSEPROCEDURE var;/*变量*/IF sym i THEN error ELSE BEGIN nextsym;IF sym=THEN BEGIN nextsym;expr;IF sym THEN error ELSE nexts

42、ym;END END =iPROCEDURE expr;/*表达式*/BEGIN term;WHILE sym=+DO BEGIN nextsym;term;END END;=|IFTHENELSE =i =+=*=|()PROCEDURE term;/*项*/BEGIN factor;WHILE sym=*DO BEGIN nextsym;factor END END;PROCEDURE factor;/*因子*/BEGIN IF sym=(THEN BEGIN nextsym;expr;IF sym)THEN error ELSE nextsym END ELSE var;END =*=|

43、()void statement()void statement()if(sym=“IF“)if(sym=“IF“)getsym();getsym();expr();expr();if(sym!=“THEN“)if(sym!=“THEN“)error();error();else getsym();else getsym();statement();statement();if(sym=“ELSE”)if(sym=“ELSE”)getsym();getsym();statment(statment(）；）；else var();else var();if(sym!if(sym!“:=“):=“

44、)error error();();else getsym();else getsym();expr();expr();void expr()void expr()term();term();while(sym=“+”)while(sym=“+”)getsym();getsym();term();term();void var()void var()if(sym!=“i”)error();if(sym!=“i”)error();else getsym();else getsym();if(sym=“”if(sym=“”）getsym();getsym();expr();expr();if(sy

45、m!=“”)if(sym!=“”)error();error();else getsym();else getsym();=|IFTHENELSE =i =+void term()void term()factor();factor();while(sym=“while(sym=“*”)”)getsym();getsym();factor();factor();void factor()void factor()if(sym=“(“)if(sym=“(“)getsym();getsym();expr();expr();if(sym!=“)”)error();if(sym!=“)”)error(

46、);else getsym();else getsym();else var();else var();void main()void main()getsym();getsym();statement();statement();error()error()printf(“syntex rror!n”)printf(“syntex rror!n”)=*=|()举例分析 if(i+i)then i:=i*i+i else ii:=i+ii*i*(i+i)作业：p90:1-3void statement()if(sym=“if“)getsym();expr();if(sym!=“then“)er

47、ror();else getsym();statement();if(sty=“else”)getsym();statment(）；else var();if(sym!“:=“)error();else getsym();expr();void expr()term();while(sym=“+”)getsym();term();void var()if(sym!=“i”)error();else getsym();if(sym=“”）getsym();expr();if(sym!=“”)error();else getsym();printf printf（“it is a statemen

48、t n”);it is a statement n”);printf printf（“it is a variable n”);it is a variable n”);printf printf（“it is a expresson n”);it is a expresson n”);=|IFTHENELSE =i =+void term()void term()factor();factor();while(sym=“while(sym=“*”)”)getsym();getsym();factor();factor();void factor()void factor()if(sym=“(

49、“)if(sym=“(“)getsym();getsym();expr();expr();if(sym!=“)”)error();if(sym!=“)”)error();else getsym();else getsym();else var();else var();void main()void main()getsym();getsym();state();state();printf printf（“it is a term n”);it is a term n”);printf printf（“it is a factor n”);it is a factor n”);error()

50、error()printf(“syntex error!n”)printf(“syntex error!n”)=*=|()4.3自底向上分析自底向上分析基本算法思想基本算法思想:若采用自左向右的描述和分析输入串若采用自左向右的描述和分析输入串,那么自那么自底向上的基本算法是：底向上的基本算法是：从输入符号串开始，通过重复查找当前句型的句从输入符号串开始，通过重复查找当前句型的句柄柄(最左简单短语最左简单短语)，并利用有关规则进行归约，若能，并利用有关规则进行归约，若能归约归约为文法的识别符号，则表示分析成功，输入符号为文法的识别符号，则表示分析成功，输入符号串是文法的合法句子，否则有语法错误。