语法分析-自上而下分析.ppt

资源描述

《语法分析-自上而下分析.ppt》由会员分享，可在线阅读，更多相关《语法分析-自上而下分析.ppt（48页珍藏版）》请在金锄头文库上搜索。

1、第四章语法分析-自上而下分析第四章第四章语法分析语法分析- -自上而下分析自上而下分析n4.1 语法分析器的功能n4.2 自上而下分析面临的问题n4.3 LL(1)分析法n 一、直接左递归的消除n 二、提取左因子、消除回溯n 三、LL(1)分析法n4.4 递归下降分析程序构造n4.5 LL(1)分析中的错误处理主要内容：主要内容：7/26/20242中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析4.1 4.1 语法分析器的功能语法分析器的功能语法分析是编译过程的核心部分。语法分析是编译过程的核心部分。语法分析的任务：在词法分析识别出单词符号：在词法分析

2、识别出单词符号串的基础上，分析并判定程序的语法结构是否串的基础上，分析并判定程序的语法结构是否符合语法规则。符合语法规则。语言的语法结构用上下文无关文法描述。语言的语法结构用上下文无关文法描述。7/26/20243中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析词法分析器符号表编译程序后续部分语法分析器源程序单词符号取下一单词符号语法分析树图4-1 语法分析器在编译程序中的地位7/26/20244中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析语法分析器的功能：按照文法的产生式，识别：按照文法的产生式，识别输入符号串是否为

3、一个句子。这里所说的输入输入符号串是否为一个句子。这里所说的输入串是指由单词符号（文法的终结符）组成的有串是指由单词符号（文法的终结符）组成的有限序列。限序列。关键：对一个文法，当给你一串（终结）符号：对一个文法，当给你一串（终结）符号时，怎样知道它是不是该文法的一个句子呢？时，怎样知道它是不是该文法的一个句子呢？这就要判断，看是否能从文法的开始符号出发这就要判断，看是否能从文法的开始符号出发推导出这个字符串。或者，从概念上讲，就是推导出这个字符串。或者，从概念上讲，就是要建立一棵与输入串相匹配的语法分析树。要建立一棵与输入串相匹配的语法分析树。7/26/20245中南大学软件学院陈志刚第四

4、章第四章语法分析语法分析- -自上而下分析自上而下分析语法分析的方法：自上而下分析法基本思想：从输入串开始，逐步进行从输入串开始，逐步进行“归约归约”，直，直至归约到文法的开始符号；或者说，从语法树的末至归约到文法的开始符号；或者说，从语法树的末端开始，步步向上端开始，步步向上“归约归约”，直到根结。所谓归约，直到根结。所谓归约，是指根据文法的产生式规则，把产生式的右部替换是指根据文法的产生式规则，把产生式的右部替换成左部符号。成左部符号。自下而上分析法基本思想：从文法的开始符号出发，根据文法的产从文法的开始符号出发，根据文法的产生式规则正向推导出给定句子的一种方法；或者说，生式规则正向推导

5、出给定句子的一种方法；或者说，从树根开始，往下构造语法树，直到建立每个叶的从树根开始，往下构造语法树，直到建立每个叶的分析方法。分析方法。7/26/20246中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析4.2 4.2 自上而下分析面临的问题自上而下分析面临的问题顾名思义，自上而下就是从文法的开始符号出顾名思义，自上而下就是从文法的开始符号出发，向下推导，推出句子。发，向下推导，推出句子。带回溯的分析方法带回溯的分析方法不带回溯的递归子程序（递归下降）分析方不带回溯的递归子程序（递归下降）分析方法法自上而下分析的主旨：对任意输入串，试图用一切可能的办法，从

6、文对任意输入串，试图用一切可能的办法，从文法开始符号（根结）出发，自上而下地为输入法开始符号（根结）出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一串建立一棵语法树。或者说，为输入串寻找一个最左推导。个最左推导。7/26/20247中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析这种分析过程本质上是一种试探过程，是反复这种分析过程本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。使用不同产生式谋求匹配输入串的过程。例例4-1 假定有文法：假定有文法：(1) SxAy (2) A*|*分析输入串分析输入串x*y(记为记为)。 7/2

7、6/20248中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析实现这种自上而下的带回溯试探法的一实现这种自上而下的带回溯试探法的一个简单途径是个简单途径是让每个非终结符对应一个递归子程序。每个这种子程序可作为一个布尔过程。每个这种子程序可作为一个布尔过程。一旦发现它的某个候选与输入串相匹配，就用一旦发现它的某个候选与输入串相匹配，就用这个候选去扩展语法树，并返回这个候选去扩展语法树，并返回“真真”值；否值；否则，保持原来的语法树和则，保持原来的语法树和IP值不变，并返回值不变，并返回“假假”值。值。7/26/20249中南大学软件学院陈志刚第四章第四章

8、语法分析语法分析- -自上而下分析自上而下分析面临的问题：n首先，是文法的左递归性问题。一个文法是含首先，是文法的左递归性问题。一个文法是含有左递归的，如果存在非终结符有左递归的，如果存在非终结符P 含有左递归的文法将使上述的自上而下的分析含有左递归的文法将使上述的自上而下的分析过程陷入无限循环。即当试图用过程陷入无限循环。即当试图用P去匹配输入去匹配输入串时，我们会发现，在没有识别任何输入符号串时，我们会发现，在没有识别任何输入符号的情况下，又得重新要求的情况下，又得重新要求P去进行新的匹配。去进行新的匹配。7/26/202410中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自

9、上而下分析自上而下分析n其次，由于回溯就碰到一大堆麻烦事情。如果其次，由于回溯就碰到一大堆麻烦事情。如果我们走了一大段错路，最后必须回头，那么，我们走了一大段错路，最后必须回头，那么，就应把已经做的一大堆语义工作推倒重来。就应把已经做的一大堆语义工作推倒重来。n第三，在上述的自上而下分析过程中，当一个第三，在上述的自上而下分析过程中，当一个非终结符用某一个候选匹配成功时，这种成功非终结符用某一个候选匹配成功时，这种成功可能仅是暂时的。可能仅是暂时的。n第四，当最终报告分析不成功时，我们难于知第四，当最终报告分析不成功时，我们难于知道输入串中出错的确切位置。道输入串中出错的确切位置。n最后，由于

10、带回溯的自上而下分析实际上采用最后，由于带回溯的自上而下分析实际上采用了一种穷尽一切可能的试探法，因此效率很低，了一种穷尽一切可能的试探法，因此效率很低，代价极高。代价极高。7/26/202411中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析一、左递归的消除使用自顶向下的任何一种算法必须消除左递归和提取公共左因子。n1、直接左递归的消除若文法中有形如PP的产生式，则称直接左递归，如AAb|a。设，有PP|，若，不以P开头（否则不可能消除左递归）。则改写为：可消除左递归。 4.3 LL(1)4.3 LL(1)分析法分析法7/26/202412中南

11、大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析n一般地，若 i，j不以P开头，则可改写为：从而消除直接左递归。例：SSabc|Sab|ab消除直接左递归得：7/26/202413中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析n2、完全消除左递归分析虽不含直接左递归，但所以含有左递归。如果文法G不含回路（），也不含产生式，则下列算法可消除左递归（完全）把G的非终结符按任意顺序排列成P1,Pnfor i:=1 to n do begin for j:=1 to i-1 do 把形如的规则改写成，其中；消除关

12、于的直接左递归 end;化简由得到的文法（取消无用非终结符产生式）7/26/202414中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析n例：上述文法n排序：S,Q,Rn循环： i=1时，处理SQc|c，消除直接左递归，不变 i=2时，处理QRb|b，j=1，把有关Q的产生式中以S开头的候选式替换（无），所以不变 i=3时，处理RSa|a， j=1，把以S开头的候选式替换，得RQca|ca|a7/26/202415中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析 j=2，把以Q开头的候选式替换，得：RRbca|bca|

14、那么在自上而下分析时便可消除回溯。设，而FIRST(1),FIRST(n)两两不相交，那么当分析时要A去匹配某输入串时，便可根据此输入串的输入符号a,准确地选用候选式i（设aFIRST(i),若FIRST(i)以后讨论）。7/26/202418中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析n例：文法例：文法SaSb|c，输入串为输入串为aacbb时：时：n3公共左因子的提取：公共左因子的提取：把文法改造为每个非终结符的所有候选式两把文法改造为每个非终结符的所有候选式两两不相交的方法是提取公共左因子。两不相交的方法是提取公共左因子。可改造为：可改

15、造为：7/26/202419中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析三、三、LL(1)LL(1)分析法分析法n预测分析（LL(1)）法是实现自上而下分析的另一种有效方法。它使用一个分析栈和一张分析表。n分析表矩阵元素MA, a指出非终结符A，面临输入符号a时，应选用的候选式（或产生式）。若A不该面临a，则放一出错标志。7/26/202420中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析n1、LL(1)分析法的工作过程开始往栈stack中放“”，然后把文件开始符号压栈。预测分析程序总是按stack栈顶符号X和当前

16、输入符号a行事。若X=a=”#”，则分析成功，停止分析若X=a”#”，则把X从栈顶弹出，a指向下一个输入符号若XVn，则查分析表。若MX, a为某候选式，则弹出X，把该候选式反序压栈；若MX, a=,则弹出X，什么也不压；若MX, a=error，则报错。 7/26/202421中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析n为了便于描述分析过程，我们定义：，代表栈X面临输入符号a采取第i条动作后，栈变为Y。n例1分析i*i# 7/26/202422中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析2、FIRS

17、T集和FOLLOW集的定义设G=(VT,VN,P，S)是上下文无关文法FIRST（）=a| a,aVT, , V* 若则规定FRIST（）FOLLOW（A）=aS =* A 且a FRIST（）， V*， V+ 若S u A ,且，则#FOLLOW(A)7/26/202423中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析计算FIRST集1.若XV,则FIRST(X)=X2.若XVN,且有产生式Xa，则把a加入到FIRST(X)中;若X也是一条产生式,则把也加到FIRST(X)中.3.若XY是一个产生式且YVN,则把FIRST(Y)中的所有非元素都加到

18、FIRST(X)中;若X Y1Y2YK 是一个产生式,Y1,Y2,Y(i-1)都是非终结符,而且,对于任何j,1j i-1, FIRST(Yj)都含有 (即Y1.Y(i-1) ),则把FIRST(Yj)中的所有非元素都加到FIRST(X)中;特别是,若所有的FIRST(Yj , j=1,2,K)均含有,则把加到FRIST(X)中. 7/26/202424中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析计算FOLLOW集1.对于文法的开始符号S,置#于FOLLOW(S) 中;2.若 B 是一个产生式,则把 FIRST()加至FOLLOW(B)中;3.若 B是一

19、个产生式,或 B是一个产生式而 (即FIRST()），则把FOLLOW（A）加至FOLLOW（B）中7/26/202425中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析一个文法G是LL（1）的，当且仅当对于G的每一个非终结符的任何两个不同产生式，下面的条件成立：FIRST（）FIRST()=,也就是和推导不出以同一个终结符a为首的符号串；它们不应该都能推出空字.假若，那么， FIRST（)FOLLOW（A）. 也就是，若 .则所能推出的串的首符号不应在FOLLOW(A）中7/26/202426中南大学软件学院陈志刚第四章第四章语法分析语法分

20、析- -自上而下分析自上而下分析例：例：G E: (1) E TE (2) E +TE (3) E (4) T FT (5) T *FT (6) T (7) F (E) (8) F a各非终结符的各非终结符的FIRSTFIRST集集合如下：合如下：FIRST(E)=FIRST(E)=(,i(,iFIRST(E)=FIRST(E)=+,+,FIRST(T)=FIRST(T)=(,i(,iFIRST(T)=FIRST(T)=*,*,FIRST(F)=FIRST(F)=(,i(,i各非终结符的各非终结符的FOLLOWFOLLOW集合集合为：为：FOLLOW(E)=FOLLOW(E)=),),FOLL

21、OW(E)=FOLLOW(E)=) )，FOLLOW(T)=FOLLOW(T)=，) )，FOLLOW(T)=FOLLOW(T)=,),)，# # FOLLOW(F)=FOLLOW(F)=*,*,，),#),# 7/26/202427中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析例：例：G E: (1) E TE (2) E +TE (3) E (4) T FT (5) T *FT (6) T (7) F (E) (8) F a试判断文法试判断文法G是不是是不是LL(1)文法。文法。分析： E +TE | FIRST(+TE)=+ FOLLOW(E)=)，

22、 T *FT | FIRST(*FT)=* FOLLOW(T)=+,)， F (E) | a FIRST(E)=( FIRST(a)=a所以GE是LL（1）的7/26/202428中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析3、LL(1)分析表的构造1.对文法G的每个产生式执行第2步和第3步；2.对每个终结符aFIRST()，把加至A,a中，3.若 FIRST()，则对任何bFOLLOW(A) 把加至A,b中，4.把所有无定义的A,a标上“出错标志”。可以证明，一个文法G的预测分析表不含多重入口，当且仅当该文法是LL(1)的。7/26/2024

23、29中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析n例1：文法，试用LL(1)分析法分析输入串abbcde。解：消除左递归得文法：求必要的FIRST和FOLLOW。 FIRST(aAcBe)=a FIRST(bA)=b FIRST()= FIRST(d)=d FOLLOW(A)=FOLLOW(A)=c 7/26/202430中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析构造LL(1)分析表分析abcde#SaAcBeAbAAbABd7/26/202431中南大学软件学院陈志刚第四章第四章语法分析语法分析

24、- -自上而下分析自上而下分析4、LL(1)文法n分析表有多重入口。n若一个文法G的分析表不含多重入口，则称它为LL(1)文法。n一个文法是LL(1)的，当且仅当G的每个非终结符A的任何两个侯选式和有 FIRST()FIRST()= 若FIRST()，则有FIRST()FOLLOW(A)=7/26/202432中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析LL(1)文法的性质： LL(1)文法是无二义的 LL(1)文法不含左递归非LL(1)文法的改造消除左递归提左公因子将产生式 | 变换为： B B |7/26/202433中南大学软件学院陈志刚第四章

25、第四章语法分析语法分析- -自上而下分析自上而下分析例例1 1：文法：文法G G（E E）：）：EE+TEE+TT TTT*FTT*FF FFiFi(E)(E)FIRST(E)=FIRST(E)=(,i(,iFIRST(T)=FIRST(T)=(,i(,iFIRST(F)=FIRST(F)=(,i(,i消左递归消左递归 E TE E +TE E 例2：S if C t S | if C t S e S C b提左因子 S if C t S A A e S | First集 Follow集S if #,eA e, #, eC b tMA,e=A e S A 7/26/202434中南大学软件学

26、院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析4.4 递归下降分析程序构造一、递归子程序法的原理：一、递归子程序法的原理：n对文法中每个非终结符U（它们代表一定的语法成分）都编出一个子程序，以完成该非终结符号所对应的语法成分的分析和识别任务。n每个非终结符号的子程序功能是：用该非终结符的产生式规则右部符号串去匹配输入串。注：可匹配任何终结符，但搜索指针不前进。n使用自上而下的方法时前提是：消除左递归；提取公共左因子。 7/26/202435中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析当一个文法满足当一个文法满足LL(1)条件时，

27、我们就可以为条件时，我们就可以为它构造一个不带回溯的自上而下分析程序，这它构造一个不带回溯的自上而下分析程序，这个分析程序是由一组递归过程组成的，每个过个分析程序是由一组递归过程组成的，每个过程对应文法的一个非终结符。这样的一个分析程对应文法的一个非终结符。这样的一个分析程序称为程序称为递归下降分析器。如果用某种高级语言写出所有递归过程，那就如果用某种高级语言写出所有递归过程，那就可以用这个语言的编译系统来产生整个的分析可以用这个语言的编译系统来产生整个的分析程序。程序。7/26/202436中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析例如，考虑文法：例

28、如，考虑文法：ETE E +TE | TFT T *FT | F(E) | i它的每个非终结符都有对应的递归过程，在分它的每个非终结符都有对应的递归过程，在分析过程中，当需要从某个非终结符出发进行展析过程中，当需要从某个非终结符出发进行展开时，就调用这个非终结符对应的子程序。开时，就调用这个非终结符对应的子程序。7/26/202437中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析几个全局过程和变量nADVANCE：是指把输入串指示器是指把输入串指示器IP调至指向调至指向下一个输入符号下一个输入符号nSYM：是指是指IP当前所指的那个输入符号当前所指的那个输

29、入符号nERROR：为出错诊察处理程序为出错诊察处理程序7/26/202438中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析对应的递归过程如下：PROCEDURE E；BEGIN T；E END；PROCEDURE E ；IF SYM=+ THEN BEGIN ADVANCE； T；E END7/26/202439中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析PROCEDURE T；BEGIN F；T ENDPROCEDURE T ；IF SYM=* THENBEGIN ADVANCE； F；T END；7/26/20

30、2440中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析 PROCEDURE F； IF SYM=i THEN ADVANCE ELSE IF SYM=( THEN BEGIN ADVANCE; E； IF SYM=) THEN ADVANCE ELSE ERROR END ELSE ERROR;7/26/202441中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析二、文法的另一种表示法在元符号在元符号“”和和“|”的基础上，扩充几个的基础上，扩充几个元语言符号：元语言符号：1. 用花括号用花括号表示闭包运算表示闭包运算

31、 *。2. 用用 n0表示表示可任意重复可任意重复0次至次至n次。次。3. 用方括号用方括号表示表示 10 ，即表示，即表示的的出现可有可无出现可有可无(等价于等价于 | )。引入上述元符号的文法亦称引入上述元符号的文法亦称扩充的巴科斯范式。7/26/202442中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析n例如，通常的例如，通常的“实数实数”可定义为：可定义为： decimalsigninteger.digitexponent exponentEsigninteger integerdigitdigit sign + | -n用扩充的巴科斯范式来

32、描述语法的好处是，直用扩充的巴科斯范式来描述语法的好处是，直观易懂，便于表示左递归消去和因子提取。对观易懂，便于表示左递归消去和因子提取。对于构造自上而下分析器来说，采用这种定义系于构造自上而下分析器来说，采用这种定义系统描述文法显然是非常可取的。统描述文法显然是非常可取的。7/26/202443中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析n例例4.5 文法文法ET | E+TTF | T*FFi | (E)可表示成可表示成ET+TTF*FFi | (E) (4.6)7/26/202444中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而

33、下分析自上而下分析语法图n可以用语法图来表示语言的文法，它显得更直可以用语法图来表示语言的文法，它显得更直观形象。如文法观形象。如文法(4.6)可等价地用如下所示的可等价地用如下所示的语法图来表示：语法图来表示：T+ETF*TFi)FE(7/26/202445中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析从文法(4.6)出发可构造一组代替前面的递归下降分析程序PROCEDURE E；BEGIN T； WHILE SYM=+ DO BEGIN ADVANCE； T ENDEND；PROCEDURE T；BEGIN F； WHILE SYM=* DO BEGI

34、N ADVANCE； F ENDEND；7/26/202446中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析 PROCEDURE F； IF SYM=i THEN ADVANCE ELSE IF SYM=( THEN BEGIN ADVANCE; E； IF SYM=) THEN ADVANCE ELSE ERROR END ELSE ERROR;7/26/202447中南大学软件学院陈志刚第四章第四章语法分析语法分析- -自上而下分析自上而下分析4.5 4.5 LL(1)LL(1)分析中的一种错误处理办法分析中的一种错误处理办法发现错误1栈顶的栈顶的

35、终结符与当前输入符不匹配终结符与当前输入符不匹配2非终结符非终结符A于栈顶，面临的输入符为于栈顶，面临的输入符为a，但分析表但分析表M的的MA,a为为空空“应急”恢复策略跳过输入串中的一些符号直至遇到跳过输入串中的一些符号直至遇到“同步符号同步符号”为止。为止。同步符号的选择1把把FOLLOW(A)中的所有符号作为中的所有符号作为A的同步符号。跳过输入串中的的同步符号。跳过输入串中的一些符号直至遇到这些一些符号直至遇到这些“同步符号同步符号”，把，把A从栈中弹出，可使从栈中弹出，可使分析继续分析继续2把把FIRST(A)中的符号加到中的符号加到A的同步符号集，当的同步符号集，当FIRST(A)中的中的符号在输入中出现时，可根据符号在输入中出现时，可根据A恢复分析恢复分析7/26/202448中南大学软件学院陈志刚

展开阅读全文

语法分析-自上而下分析.ppt

最新文档