【教学课件】第四章自顶向下的语法分析.ppt

《【教学课件】第四章自顶向下的语法分析.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第四章自顶向下的语法分析.ppt（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章第四章 自顶向下的自顶向下的语法分析语法分析School of Computer Science&Technology Harbin Institute of Technology重点：重点：自顶向下分析的基本思想，预测分析器总体结构，预测分自顶向下分析的基本思想，预测分析器总体结构，预测分析表的构造，递归下降分析法基本思想，简单算术表达式的递归析表的构造，递归下降分析法基本思想，简单算术表达式的递归下降分析器。下降分析器。难点：难点：FIRST FIRST 和和 FOLLOW FOLLOW 集的求法，对它们的理解以及在构造集的求法，对它们的理解以及在构造LL(1)LL(1)分析表时的使

2、用。递归子程序法中如何体现分析的结果。分析表时的使用。递归子程序法中如何体现分析的结果。2023/1/102第第4章章 自自顶顶向下的向下的语语法分析法分析4.1 语法分析概述语法分析概述 4.2 自顶向下的语法分析面临的问题自顶向下的语法分析面临的问题 与文法的改造与文法的改造 4.3 预测分析法预测分析法 4.4 递归下降分析法递归下降分析法 4.5 本章小结本章小结2023/1/103语语法分析的功能和位置法分析的功能和位置n语法分析语法分析(syntax analysis)(syntax analysis)是编译程序的核心部是编译程序的核心部分，其任务是检查词法分析器输出的单词序列是否

3、是分，其任务是检查词法分析器输出的单词序列是否是源语言中的句子，亦即是否符合源语言的语法规则。源语言中的句子，亦即是否符合源语言的语法规则。图图4.14.1语法分析器在编译器中的位置语法分析器在编译器中的位置2023/1/1044.1 语法分析概述语法分析概述 递归子程序法递归子程序法自顶向下自顶向下 预测分析法预测分析法(LL(1)(LL(1)算符优先分析法算符优先分析法自底向上自底向上 LR(0)LR(0)、SLR(1)SLR(1)、LR(1)LR(1)、LALR(1)LALR(1)Top DownTop DownBottom UpBottom Up从文法产生语言的角度从文法产生语言的角度

4、从自动机识别语言的角度从自动机识别语言的角度从根开始，逐从根开始，逐步为某语句构步为某语句构造一棵语法树造一棵语法树相反，将一句相反，将一句子归约为开始子归约为开始符号符号问题：解决确定性问题！问题：解决确定性问题！假定文法是压缩的：即删除了单位产生式和无用产生式。假定文法是压缩的：即删除了单位产生式和无用产生式。2023/1/1054.2 自顶向下的语法分析面临的问题自顶向下的语法分析面临的问题与文法的改造与文法的改造n自顶向下语法分析的基本思想自顶向下语法分析的基本思想n从文法的开始符号出发，寻求所给的输入符号串从文法的开始符号出发，寻求所给的输入符号串的一个最左推导。的一个最左推导。n从

5、树根从树根S开始，构造所给输入符号串的语法树开始，构造所给输入符号串的语法树n例例:设有设有G：SxAy A*|*，输入串：，输入串：x*yS S S SxAy x*yS Sx xA Ay y*2023/1/1064.2.1 自顶向下分析面临的问题自顶向下分析面临的问题1.二义性问题二义性问题n对于文法对于文法G，如果，如果L(G)中存在一个具有两棵或两棵以上中存在一个具有两棵或两棵以上分析树的句子，则称分析树的句子，则称G是二义性的。也可以等价地说：是二义性的。也可以等价地说：如果如果L(G)中存在一个具有两个或两个以上最左中存在一个具有两个或两个以上最左(或最右或最右)推导的句子，则推导的

6、句子，则G是二义性文法。是二义性文法。n如果一个文法如果一个文法G是二义性的，假设是二义性的，假设w L(G)且且w存在两存在两个最左推导个最左推导，则在对，则在对w进行自顶向下的语法分析时，语进行自顶向下的语法分析时，语法分析程序将无法确定采用法分析程序将无法确定采用w的哪个最左推导。的哪个最左推导。nGexp：EE+T|E-T|TTT*F|T/F|FFFP|P Pc|id|(E)解决办法：改造文法，引入新的文法变量解决办法：改造文法，引入新的文法变量2023/1/1074.2.1 自顶向下分析面临的问题自顶向下分析面临的问题2.回溯问题回溯问题n文法中每个语法变量文法中每个语法变量A的产生

7、式右部称为的产生式右部称为A的的候选式，如果候选式，如果A有多个候选式存在公共前缀，有多个候选式存在公共前缀，则自顶向下的语法分析程序将无法根据当前输则自顶向下的语法分析程序将无法根据当前输入符号准确地选择用于推导的产生式，只能试入符号准确地选择用于推导的产生式，只能试探。当试探不成功时就需要退回到上一步推导，探。当试探不成功时就需要退回到上一步推导，看看A是否还有其它的候选式，这就是是否还有其它的候选式，这就是回溯回溯(backtracking)。nGe：ET EE+T EE-T TF TT*F TT/F F(E)Fid n例如：考虑为输入串例如：考虑为输入串id+id*id建立最左推导建立

8、最左推导 2023/1/1084.2.1 自顶向下分析面临的问题自顶向下分析面临的问题2.回溯问题回溯问题nET (4.1)nETF (4.2)nETF(E)(4.3)nETFid (4.4)nETT*F (4.5)n.4.2.2节我们将采用提取左因子的方法来改造文法，节我们将采用提取左因子的方法来改造文法，以便减少推导过程中回溯现象的发生，当然，单以便减少推导过程中回溯现象的发生，当然，单纯通过提取左因子无法彻底避免回溯现象的发生。纯通过提取左因子无法彻底避免回溯现象的发生。2023/1/1094.2.1 自顶向下分析面临的问题自顶向下分析面临的问题3.左递归引起的无穷推导问题左递归引起的无

9、穷推导问题n假设假设A是文法是文法G的某个语法变量，如果存在推导的某个语法变量，如果存在推导A A，则称文法，则称文法G是递归的是递归的，当，当=时称之为左递归；时称之为左递归；如果如果A A至少需要两步推导，则称文法至少需要两步推导，则称文法G是间接递归的是间接递归的，当当=时称之为间接左递归；时称之为间接左递归；如果文法如果文法G中存在形如中存在形如AA的产生式，则称文法的产生式，则称文法G是直接递归的是直接递归的，当，当=时时称之为直接左递归称之为直接左递归。nGer：ET EE+T EE-T TF TT*F TT/F F(E)Fid n考虑考虑为输入串为输入串id+id*id建立一个最

10、左推导建立一个最左推导 nEE+TE+T+TE+T+T+T 2023/1/10104.2.2 对上下文无关文法的改造对上下文无关文法的改造 1.消除二义性消除二义性n改造的方法就是通过引入新的语法变量等，使文法改造的方法就是通过引入新的语法变量等，使文法含有更多的信息。其实，许多二义性文法是由于概含有更多的信息。其实，许多二义性文法是由于概念不清，即语法变量的定义不明确导致的，此时通念不清，即语法变量的定义不明确导致的，此时通过引入新的语法变量即可消除文法的二义性。过引入新的语法变量即可消除文法的二义性。n if then n|if then else n|other (4.7)n根据根据if

11、语句中语句中else与与then配对情况将其分为配对的语配对情况将其分为配对的语句和不配对的语句两类。上述句和不配对的语句两类。上述if语句的文法没有对语句的文法没有对这两个不同的概念加以区分，只是简单地将它们都这两个不同的概念加以区分，只是简单地将它们都定义为定义为，从而导致该文法是二义性的。，从而导致该文法是二义性的。2023/1/10114.2.2 对上下文无关文法的改造对上下文无关文法的改造 引入语法变量引入语法变量来表示不配来表示不配对语句，对语句，表示配对语句表示配对语句 n|n if then else|othern if then|if then else 2023/1/101

12、24.2.2 对上下文无关文法的改造对上下文无关文法的改造 2.消除左递归消除左递归n直接左递归的消除直接左递归的消除(转换为右递归转换为右递归)n引入新的变量引入新的变量A，将左递归产生式，将左递归产生式AA|替换为替换为AA A A|nEE+T|T TT*F|F F(E)|id替换为：替换为：nETE E+TE|TFT T*FT|F(E)|id n一般地，假设文法一般地，假设文法G中的语法变量中的语法变量A的所有产生式如下：的所有产生式如下：AA1|A2|An|1|2|m其中，其中，i(i=1,2,m)不以不以A打头。则用如下的产生式代替打头。则用如下的产生式代替A的所有产生式即可消除其直

13、接左递归：的所有产生式即可消除其直接左递归：A1A|2A|mA A1A|2A|nA|2023/1/10134.2.2 对上下文无关文法的改造对上下文无关文法的改造 算法算法4.1 消除左递归。消除左递归。输入：不含循环推导和输入：不含循环推导和-产生式的文法产生式的文法G;输出：与输出：与G等价的无左递归文法等价的无左递归文法;步骤：步骤：1将将G的所有语法变量排序的所有语法变量排序(编号编号)，假设排序后的语法变量记，假设排序后的语法变量记为为A1，A2，An；2for i1 to n 3for j1 to i-1 4用产生式用产生式Ai1|2|k代替每个形如代替每个形如AiAj的产生式，的

14、产生式，其中，其中，Aj1|2|k是所有的当前是所有的当前Aj产生式；产生式；5 6 消除消除Ai产生式中的所有直接左递归产生式中的所有直接左递归7 2023/1/10144.2.2 对上下文无关文法的改造对上下文无关文法的改造n3.3.提取左因子提取左因子n对每个语法变量对每个语法变量A，找出它的两个或更多候选式的最，找出它的两个或更多候选式的最长公共前缀长公共前缀。如果。如果，则用下面的产生式替换所，则用下面的产生式替换所有的有的A产生式产生式A1|2|n|1|2|n，其中，其中1，2，n表示所有不以表示所有不以开头的候选式：开头的候选式：AA|1|2|nA1|2|nn其中，其中，A是新引

15、入的语法变量。反复应用上述变换，是新引入的语法变量。反复应用上述变换，直到任意语法变量都没有两个候选式具有公共前缀为直到任意语法变量都没有两个候选式具有公共前缀为止。请读者自行给出这个变换的算法。止。请读者自行给出这个变换的算法。2023/1/10154.2.3 LL(1)文法文法问题：什么样的文法对其句子才能进行确定的问题：什么样的文法对其句子才能进行确定的自顶向下分析？自顶向下分析？n确定的自顶向下分析首先从文法的开始符号出发，每一步确定的自顶向下分析首先从文法的开始符号出发，每一步推导都根据当前句型的最左语法变量推导都根据当前句型的最左语法变量A和当前输入符号和当前输入符号a，选择选择A

16、的某个候选式的某个候选式来替换来替换A，并使得从，并使得从推导出的第一推导出的第一个终结符恰好是个终结符恰好是a。n当当A有多个候选式时，当前选中的候选式必须是惟一的。有多个候选式时，当前选中的候选式必须是惟一的。n第一个终结符是指符号串的第一个符号，并且是终结符号，第一个终结符是指符号串的第一个符号，并且是终结符号，可以称为首终结符号。在自顶向下的分析中，它对选取候可以称为首终结符号。在自顶向下的分析中，它对选取候选式具有重要的作用。为此引入首符号集的概念。选式具有重要的作用。为此引入首符号集的概念。2023/1/10164.2.3 LL(1)文法文法1.假设假设是文法是文法G=(V，T，P

17、，S)的符号串，即的符号串，即(VT)*，从，从推导出的串的首符号集记作推导出的串的首符号集记作FIRST()：FIRST()=a|a，a T，(VT)*。2.如果如果 ，则，则 FIRST()。3.如果文法如果文法G中的所有中的所有A产生式为产生式为A1|2|m，且且 FIRST(1)FIRST(2)FIRST(n)且对且对 i，j，1 i，j m；ij，均有，均有FIRST(i)FIRST(j)=成立，则可以对成立，则可以对G的句子的句子进行确定的自顶向下分析进行确定的自顶向下分析2023/1/10174.2.3 LL(1)文法文法如果如果存在存在A这样的产生式，则需定义这样的产生式，则需

18、定义FOLLOW(A)A定义定义A的的后续符号集为后续符号集为：1.FOLLOW(A)=a|S Aa,a T,(VT)*2.如果如果A是某个句型的最右符号，则将结束符是某个句型的最右符号，则将结束符#添加到添加到FOLLOW(A)中中3.如果如果j ，则如果对，则如果对 i(1 i m；ij)，FIRST(i)FOLLOW(A)=均成立，则可以对均成立，则可以对G的句子进行确定的自顶向下分析的句子进行确定的自顶向下分析2023/1/10184.2.3 LL(1)文法文法如果如果G的任意两个具有相同左部的产生式的任意两个具有相同左部的产生式A|满足下列条满足下列条件：件：1.如果如果、均不能推导

19、出均不能推导出，则，则FIRST()FIRST()=；2.和和至多有一个能推导出至多有一个能推导出；3.如果如果 ，则，则FIRST()FOLLOW(A)=则称则称G为为LL(1)文法。文法。第一个第一个L代表从左向右扫描输入符号串，第二个代表从左向右扫描输入符号串，第二个L代表产代表产生最左推导，生最左推导，1代表在分析过程中执行每步推导都要向代表在分析过程中执行每步推导都要向前查看一个输入符号前查看一个输入符号 2023/1/1019LL(1)文法的判定文法的判定算法算法4.2 计算计算FIRST(X)。输入：文法输入：文法G=(V，T，P，S)，X(VT);输出：输出：FIRST(X);

20、步骤：步骤：1FIRST(X)=;2if(XT)then FIRST(X):=X;3if XV then begin4if(X P)then FIRST(X):=FIRST(X)a|XaP;5if(XP)then FIRST(X):=FIRST(X)a|XaPend6对对 X，重复如下的过程，重复如下的过程7-10，直到所有，直到所有FIRST集不变为止。集不变为止。7if(XYP and YV)then FIRST(X):=FIRST(X)(FIRST(Y)-)；8if(XY1YnP and Y1.Yi-1 )then 9for k=2 to i do FIRST(X):=FIRST(X)(

21、FIRST(Yk)-);10if Y1.Yn then FIRST(X):=FIRST(X);2023/1/1020LL(1)文法的判定文法的判定算法算法4.3 计算计算FIRST()。输入：文法输入：文法G=(V，T，P，S)，(VT)*，=X1Xn;输出：输出：FIRST();步骤：步骤：1计算计算FIRST(X1);2FIRST():=FIRST(X1)-;3k:=1;4while(FIRST(Xk)and kn)do begin5 FIRST():=FIRST()(FIRST(Xk+1)-);6 k:=k+1 end7if(k=n and FIRST(Xk)then FIRST():=

22、FIRST();2023/1/1021例例 表达式文法的语法符号的表达式文法的语法符号的FIRST 集集FIRST(F)=（,idFIRST(T)=FIRST(F)=（,id FIRST(E)=FIRST(T)=（,id FIRST(E)=+，FIRST(T)=*,FIRST(+)=+,FIRST(*)=*FIRST(（)=（FIRST(）)=）FIRST(id)=idETE ETE E+TE|E+TE|TFT TFT T*FT|T*FT|F(E)|idF(E)|id2023/1/1022LL(1)文法的判定文法的判定算法算法4.4 计算计算FOLLOW集。集。输入：文法输入：文法G=(V，T

23、，P，S)，A V;输出：输出：FOLLOW(A);步骤：步骤：1对对 XV，FOLLOW(X):=;2FOLLOW(S):=#，#为句子的结束符为句子的结束符;3对对 XV，重复下面的第，重复下面的第4步到第步到第5步，直到所有步，直到所有FOLLOW集不变为止。集不变为止。4若若ABP，则，则FOLLOW(B):=FOLLOW(B)FIRST();5若若AB或或ABP，且，且 ，AB，则，则FOLLOW(B):=FOLLOW(B)FOLLOW(A);2023/1/1023例例 表达式文法的语法变量的表达式文法的语法变量的 FOLLOW 集集FOLLOW(E)=#,)FOLLOW(E)=FO

24、LLOW(E)=#,)FOLLOW(T)=FIRST(E)-FOLLOW(E)FOLLOW(E)=+,),#FOLLOW(T)=FOLLOW(T)=+,),#FOLLOW(F)=FIRST(T)FOLLOW(T)FOLLOW(T)=*,+,),#ETEETE E E+TE+TE|TFTTFT T T*FTFT|F(E)|idF(E)|idFIRST(F)=FIRST(F)=（,id,idFIRST(T)=FIRST(F)=FIRST(T)=FIRST(F)=（,id ,id FIRST(E)=FIRST(T)=FIRST(E)=FIRST(T)=（,id ,id FIRST(EFIRST(E)

25、=+)=+，FIRST(TFIRST(T)=*,)=*,2023/1/1024表达式文法是表达式文法是 LL(1)文法文法nE T E E T E nE+T EE+T E nT F T T F T nT*F TT*F T nF (E)F (E)idid考察考察nE:+E:+不在不在 FOLLOW(E)=),#FOLLOW(E)=),#nT:*T:*不在不在 FOLLOW(T)=+,),#FOLLOW(T)=+,),#nF:(F:(和和 id id 不同不同2023/1/1025非非 LL(1)文法文法的不确定性的不确定性例例 对文法对文法nScAdnAab|a 输入输入 cad 的分析的分析S

26、 S S Sd d d dc c c cA A A Ab b b ba a a aS S S Sd d d dc c c cA A A Aa a a a2023/1/1026不确定性的解决方法不确定性的解决方法1)1)采用回溯算法采用回溯算法n过于复杂，效率低下过于复杂，效率低下2 2）改写文法）改写文法n将非将非LL(1)LL(1)文法改写为等价的文法改写为等价的LL(1)LL(1)文法文法n无法改写时：无法改写时：n增加其它的判别因素增加其它的判别因素n文法过于复杂，无法用自顶向下方法处理文法过于复杂，无法用自顶向下方法处理2023/1/10274.3 预测分析法预测分析法n系统维持一个分

27、析表和一个分析栈，根据当前扫描系统维持一个分析表和一个分析栈，根据当前扫描到的符号，选择当前语法变量（处于栈顶）的候选到的符号，选择当前语法变量（处于栈顶）的候选式进行推导式进行推导希望找到相应输入符号串的最左推希望找到相应输入符号串的最左推导。导。n一个通用的控制算法一个通用的控制算法n一个分析栈，一个分析栈，#为栈底符号为栈底符号n一个输入缓冲区，一个输入缓冲区，#为输入串结束符为输入串结束符n一个统一形式的分析表一个统一形式的分析表Mn不同语言使用内容不同的分析表不同语言使用内容不同的分析表2023/1/10284.3.1 预测分析器的构成预测分析器的构成 输入缓冲区输入缓冲区(符号序列

28、符号序列)栈栈预测分析程序预测分析程序预测分析表预测分析表M输出的输出的输出的输出的产生式序列产生式序列产生式序列产生式序列2023/1/1029系统的执行与特点系统的执行与特点n在系统启动时，输入指针指向输入串的第一个字在系统启动时，输入指针指向输入串的第一个字符，分析栈中存放着栈底符号符，分析栈中存放着栈底符号#和文法的开始符号。和文法的开始符号。n根据栈顶符号根据栈顶符号A A和读入的符号和读入的符号a a，查看分析表，查看分析表M,M,以以决定相应的动作。决定相应的动作。n优点：优点：1 1）效率高）效率高2 2）便于维护、自动生成）便于维护、自动生成n关键关键分析表分析表M M的构造

29、的构造2023/1/1030预测分析程序的总控程序预测分析程序的总控程序 算法算法4.5 预测分析程序的总控程序。预测分析程序的总控程序。输入：输入串输入：输入串w和文法和文法G=(V,T,P,S)的分析表的分析表M;输出：如果输出：如果w属于属于L(G)，则输出，则输出w的最左推导，否则报告错误的最左推导，否则报告错误;步骤：步骤：1将栈底符号将栈底符号#和文法开始符号和文法开始符号S压入栈中压入栈中;2repeat3X:=当前栈顶符号当前栈顶符号;4a:=当前输入符号当前输入符号;5if XT#then6if X=a then7 if X#then begin8将将X弹出栈弹出栈;9前移输

30、入指针前移输入指针10end 2023/1/1031预测分析程序的总控程序预测分析程序的总控程序 11else error12else 13if MX,a=Y1Y2Yk then begin14 将将X弹出栈弹出栈;15依次将依次将Yk，Y2，Y1压入栈压入栈;16输出产生式输出产生式XY1Y2Yk17end18else error19until X=#2023/1/1032FOLLOW(E)=),#FOLLOW(T)=+,),#FIRST(TE)=(,id FIRST(+TE)=+FIRST(FT)=(,id FIRST(*FT)=*FIRST(E)=(FIRST(id)=idETE E+T

31、E|TFT T*FT|F(E)|id例例4.10 考虑简单算术表达式文法的实现考虑简单算术表达式文法的实现2023/1/1033简单算术表达式文法的预测分析表简单算术表达式文法的预测分析表2023/1/1034对输入对输入串串id+id*id进行进行分析的过程分析的过程（在黑板上同时画出语法树）（在黑板上同时画出语法树）栈栈 输入缓冲区输入缓冲区 输出输出#E#E id+idid+id*id#*id#ET#ET id+idid+id*id#ETE*id#ETE#ETF#ETF id+idid+id*id#TFT*id#TFT#ETidETid id+idid+id*id#*id#FidFid#

32、ET +id*id#ET +id*id#E +id*id#E +id*id#TT#ET+id*id#E+TE#ET+id*id#E+TE#ET id*#ET id*idid#2023/1/1035#ETF id*#ETF id*idid#TFT#TFT#ETidETid id*id*idid#FidFid#ET *id#ET *id#ETF*id#T*FT#ETF*id#T*FT#ETF id#ETF id#ETidETid id#id#FidFid#ET#ET#E#E#TT#EE输出的产生式序列形成了最左推导对应的分析树输出的产生式序列形成了最左推导对应的分析树输出的产生式序列形成了最左推导

33、对应的分析树输出的产生式序列形成了最左推导对应的分析树#ET id*id#ET id*id#ET id*id#ET id*id#2023/1/10364.3.2 预测分析表的构造算法预测分析表的构造算法算法算法4.6 预测分析表预测分析表(LL(1)分析表分析表)的构造算法。的构造算法。输入：文法输入：文法G;输出：分析表输出：分析表M;步骤：步骤：1对对G中的任意一个产生式中的任意一个产生式A,执行第执行第2步和第步和第3步步;2 for a FIRST(),将将A填入填入MA,a;3 if FIRST()then a FOLLOW(A),将将A填入填入MA,a;if FIRST()&#FO

34、LLOW(A)then将将A填入填入MA,#;4将所有无定义的将所有无定义的MA,b标上出错标志。标上出错标志。2023/1/1037预测分析法的实现步骤预测分析法的实现步骤1.构造文法构造文法2.改造文法：消除二义性、消除左递归、提取左因子改造文法：消除二义性、消除左递归、提取左因子3.求每个候选式的求每个候选式的FIRST集和集和变量的变量的FOLLOW集集4.检查是不是检查是不是 LL(1)文法文法 若不是若不是 LL(1),说明文法的复杂性超过自顶向下方法的分析说明文法的复杂性超过自顶向下方法的分析能力，需要附加新的能力，需要附加新的“信息信息”5.构造预测分析表构造预测分析表6.实现

35、预测分析器实现预测分析器2023/1/10384.3.3 预测分析中错误的处理预测分析中错误的处理 n对语法变量对语法变量A，如果，如果MA,a无定义，并且无定义，并且a属于属于FOLLOW(A)，则增加，则增加MA,a为为“同步点同步点”(synch),同同步记号选择方法如下：步记号选择方法如下：n把把FOLLOW(A)的所有符号放入语法变量的所有符号放入语法变量A的同步记的同步记号集合中。号集合中。n把高层结构的开始符号加到低层结构的同步记号集合把高层结构的开始符号加到低层结构的同步记号集合中。中。n把把FIRST(A)的符号加入的符号加入A的同步记号集合。的同步记号集合。n如果语法变量可

36、以产生空串，若出错时栈顶是这样的如果语法变量可以产生空串，若出错时栈顶是这样的语法变量，则可以使用产生空串的产生式。语法变量，则可以使用产生空串的产生式。n如果符号在栈顶而不能匹配，则弹出此符号。如果符号在栈顶而不能匹配，则弹出此符号。2023/1/10394.4 递归下降分析法递归下降分析法一个设想一个设想1.对应每个变量设置一个处理子程序：对应每个变量设置一个处理子程序：AX1 X2 Xk Xn 当遇到当遇到Xk是终极符号时直接进行匹配是终极符号时直接进行匹配;当遇到当遇到Xk是语法变量时就调用是语法变量时就调用X对应的对应的处理子程序处理子程序.2.要求处理子程序是可以要求处理子程序是可

37、以递归调用递归调用的的ETE E+TE|TFT T*FT|F(E)|id2023/1/10404.4.1 递归下降分析法的基本思想递归下降分析法的基本思想例例4.14 对于产生式对于产生式E+TE，与，与E对应的子程对应的子程序可以按如下方式来编写：序可以按如下方式来编写：procedure E begin match(+);T;/*调用识别调用识别T的过程的过程*/E /*调用识别调用识别E的过程的过程*/end;2023/1/10414.4.1 递归下降分析法的基本思想递归下降分析法的基本思想其中，服务子程序其中，服务子程序match用来匹配当前的输入记用来匹配当前的输入记号，其代码为：号

38、，其代码为：procedure match(t:token);begin if lookhead=t then lookhead:=nexttoken;else error /*调用出错处理程序调用出错处理程序*/end;2023/1/10424.4.2 语法图和递归子程序法语法图和递归子程序法n状态转换图（语法图）是非常有用的设计工具状态转换图（语法图）是非常有用的设计工具n语法分析器和词法分析器的状态转换图不同语法分析器和词法分析器的状态转换图不同n每个非终结符对应一个状态转换图，边上的标记是记号和每个非终结符对应一个状态转换图，边上的标记是记号和非终结符非终结符n记号上的转换意味着如果该

39、记号是下一个输入符号，就应记号上的转换意味着如果该记号是下一个输入符号，就应进行转换进行转换n非终结符非终结符A上的转换是对与上的转换是对与A对应的过程的调用对应的过程的调用2023/1/10434.4.2 语法图和递归子程序法语法图和递归子程序法n从文法构造语法图，对每个非终结符从文法构造语法图，对每个非终结符A A执行如执行如下操作下操作n创建一创建一个开始状态和一个终止状态（返回状态）个开始状态和一个终止状态（返回状态）n对每个产生式对每个产生式AX1X2 Xn，创建一条从开始，创建一条从开始状态到终止状态的路径，边上的标记分别为状态到终止状态的路径，边上的标记分别为X1，X2，Xn20

40、23/1/1044例例4.15 简单表达式文法的语法图简单表达式文法的语法图ETEE+TE|TFTT*FT|F(E)|id2023/1/10454.4.3基于语法图的语法分析器工作方式基于语法图的语法分析器工作方式 n初始时，分析器进入状态图的开始状态，输入初始时，分析器进入状态图的开始状态，输入指针指向指针指向输入符号串的第一个符号。输入符号串的第一个符号。n如果经过一些动作后，它进入状态如果经过一些动作后，它进入状态s，且从状，且从状态态s到状态到状态t的边上标记了终结符的边上标记了终结符a，此时下一此时下一个输入符又正好是个输入符又正好是a，则分析器将输入指针向，则分析器将输入指针向右移

41、动一位，并右移动一位，并进入状态进入状态t。2023/1/10464.4.3基于语法图的语法分析器工作方式基于语法图的语法分析器工作方式 n另一方面，如果边上标记的是非终结符另一方面，如果边上标记的是非终结符A，则，则分析器进入分析器进入A的初始状态，但不移动输入指针。的初始状态，但不移动输入指针。一旦到达一旦到达A的终态，则立刻进入状态的终态，则立刻进入状态t，事实上，事实上，分析器从状态分析器从状态s转移到状态转移到状态t时，它已经从输入时，它已经从输入符号串符号串“读读”了了A（调用调用A对应的过程对应的过程）。）。n最后，如果从最后，如果从s到到t有一条标记为有一条标记为的边，那么的边

42、，那么分析器从状态分析器从状态s直接进入状态直接进入状态t而不移动输入指而不移动输入指针。针。2023/1/1047图图4.64.6算术表达式的简化语法图算术表达式的简化语法图4.4.4 语法图的化简与实现语法图的化简与实现 左因子提取左因子提取将形如将形如AYX|YZ的产生式替换为的产生式替换为AY(X|Z)；右因子提取右因子提取将形如将形如AYX|ZX的产生式替换为的产生式替换为A(Y|Z)X；尾递归消除尾递归消除将形如将形如XYX|Z的产生式替换为的产生式替换为XY*Z。2023/1/1048的子程序的子程序(ET(+T)*)procedure E;begin T;T的过程调用的过程调用

43、 while lookhead=+do begin 当前符号等于当前符号等于+时时 match(+);处理终结符处理终结符+T T的过程调用的过程调用 end end;lookhead：当前符号：当前符号 例例4.16 简单算术表达式的语法分析器简单算术表达式的语法分析器2023/1/1049的子程序的子程序(TF(*F)(TF(*F)*)procedure T;begin F;F的过程调用的过程调用 while lookhead=*then begin 当前符号等于当前符号等于*时时 match(*);处理终结符处理终结符*F F的递归调用的递归调用 end end;2023/1/1050的

44、子程序的子程序(F(E)|id)procedure F;begin if lookhead=(then begin 当前符号等于（当前符号等于（match();处理终结符（处理终结符（E;的递归调用的递归调用 match();处理终结符）处理终结符）end else if lookhead=id then match(id)处理终结符处理终结符id else error 出错处理出错处理 end2023/1/1051主程序主程序begin lookhead:=nexttoken;调词法分析程序调词法分析程序 E 的过程调用的过程调用end procedure procedure match(t

45、:tokenmatch(t:token););begin begin if if lookheadlookhead=t then =t then lookheadlookhead:=:=nexttokennexttoken else error else error 出错处理程序出错处理程序出错处理程序出错处理程序 end;end;服务子程序2023/1/10524.4.5 递归子程序法的实现步骤递归子程序法的实现步骤 1)构造文法；构造文法；2)改造文法：消除二义性、消除左递归、提取左因子；改造文法：消除二义性、消除左递归、提取左因子；3)求每个候选式的求每个候选式的FIRST集和语法变量的

46、集和语法变量的FOLLOW集；集；4)检查检查G是不是是不是 LL(1)文法，若文法，若G不是不是 LL(1)文法，说明文法，说明文法文法G的复杂性超过了自顶向下方法的分析能力，需的复杂性超过了自顶向下方法的分析能力，需要附加新的要附加新的“信息信息”；5)按照按照LL(1)文法画语法图；文法画语法图；6)化简语法图；化简语法图；7)按照语法图为每个语法变量设置一个子程序。按照语法图为每个语法变量设置一个子程序。2023/1/1053递归子程序法的优缺点分析递归子程序法的优缺点分析n优点：优点：1）直观、简单、可读性好）直观、简单、可读性好2）便于扩充）便于扩充n缺点：缺点：1)递归算法的实现

47、效率低递归算法的实现效率低2)处理能力相对有限处理能力相对有限3)通用性差，难以自动生成通用性差，难以自动生成n从递归子程序法及从递归子程序法及FIRST与与FOLLOW集看集看如何进一步用好当前的输入符号？如何进一步用好当前的输入符号？2023/1/1054本章小结本章小结1.自顶向下分析法和自底向上分析法分别寻自顶向下分析法和自底向上分析法分别寻找输入串的最左推导和最左归约找输入串的最左推导和最左归约2.自顶向下分析会遇到二义性问题、回溯问自顶向下分析会遇到二义性问题、回溯问题、左递归引起的无穷推导问题，需对文题、左递归引起的无穷推导问题，需对文法进行改造：消除二义性、消除左递归、法进行改造：消除二义性、消除左递归、提取公共左因子提取公共左因子3.LL(1)文法是一类可以进行确定分析的文法，文法是一类可以进行确定分析的文法，利用利用FIRST集和集和FOLLOW集可以判定某集可以判定某个上下文无关文法是否为个上下文无关文法是否为LL(1)文法文法2023/1/1055本章小结本章小结4.LL(1)文法可以用文法可以用LL(1)分析法进行分析。分析法进行分析。5.递归下降分析法根据各个候选式的结构为每递归下降分析法根据各个候选式的结构为每个非终结符编写一个子程序。个非终结符编写一个子程序。6.使用语法图可以方便地进行递归子程序的设使用语法图可以方便地进行递归子程序的设计。计。