第五章自顶向下语法分析方法.ppt

1、第5章,自顶向下语法分析方法,语法分析,语法分析是编译程序的核心部分 作用：识别由词法分析给出的单词符号序列是否为给定文法的正确句子。 自顶向下分析 ( Top-Down Parsing) 也称为面向目标的分析方法 分为确定的和不确定的两种分析方法,语法分析句形分析,句形分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。 在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。 分析算法又称识别算法。,5.1 确定的自顶向下分析思想,自顶向下从开始符开始分析 唯一的确定选用哪个产生式替换相应的非终结符，然后继续向下推导。 亦可用构造一棵语法树的方式进行分析,自顶向下的推导

2、过程的例,例 5.1 若有文法G1S S pAqB A cAda B dBb 若输入串W=pccadd 自顶向下的推导过程为：SpApcAdpccAddpccadd,确定的自顶向下分析思想,例5.1的文法有两个特点： （1）每个产生式的右部都由终结符开始 （2）如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。 根据输入符号决定选择产生式向下推导，分析过程是唯一确定的。,自顶向下的推导过程的例,例5.1的语法树,自顶向下的推导过程的例,例 5.2 若有文法G2S S Ap S Bq A a A cA B b B dB 若输入串W=ccap 自顶向下的推导过程为：SApcApccAp

3、ccap,自顶向下的推导过程的例,例5.2的语法树,确定的自顶向下分析思想,例5.2的文法的特点： （1）产生式的右部不全是由终结符开始 （2）如果两个产生式有相同的左部，那么它们的右部由不同的终结符或非终结符开始。 （3）文法中无空产生式,自上而下分析算法,要点： 由根向下构造语法树 构造最左推导 推导出的终结符是否与当前输入符匹配,S AB A aA | B b | bB aaab. S AB S AB aAB A aA aaAB A aA aaaAB A aA aaa B A aaab B b,首符号的集合,定义5.1 设G=(VT,VN,S,P)是上下文无关文法，首符号的集合： FIR

4、ST()=a|*a，aVT，,V* 若* 则规定 FIRST() 文法G2(S)中： FIRST(Ap)=a,c FIRST(Bq)=b,d,文法中包含空产生式的情况,例5.3 若有文法GS S aA S d A bAS A 若输入串W=abd 自顶向下的推导过程为：SaAabASabSabd 推导 abASabS 利用了产生式 A ,自顶向下的推导过程的例,例5.3的语法树,跟随符号的集合,定义5.2 设G=(VT,VN,S,P)是上下文无关文法，AVN S是开始符号 FOLLOW(A)=a|S*A 且aVT ， aFIRST()，VT*，V+ 若 S*A，且 * ， 则 #FOLLOW(A

5、),跟随符号的集合,也可定义为： FOLLOW(A)=a|S* Aa，a VT 若S* A，则规定# FOLLOW(A) #号作为输入串的结束符，句子括号。如： #输入串#,跟随符号的集合,当文法中含有形如： A A 其中 AVN ,V* 的产生式，当， 不同时推导出空时，即： *；*，则当： FIRST()FIRST()FOLLOW(A)=时，对于非终结符A的替换仍可唯一地确定候选。,跟随符号的集合,即当一非终结符的产生式中含有时，它的非空产生式的右部的FIRST集两两不相交，并与在推导过程中紧跟该非终结符右边可能出现的终结符集也不相交。 由定义可以看出：所谓FIRST集和FOLLOW集是对

6、于非终结符而言的，即形成的集合是对于某一非终结符的终结符的集合，,选择集合,定义5.3 给定上下文无关文法的产生式： A 其中 AVN V* 若 *，则 SELECT(A)=FIRST() 若 *，则 SELECT(A)= (FIRST()-)FOLLOW(A) 选择集合是对某一产生式而言的。,LL(1)文法,定义5.4 一个上下文无关文法是LL(1)文法的充分必要条件是，对每个非终结符A的两个不同产生式 A A ，满足： SELECT(A ) SELECT(A) = 其中：， 不能同时推出 * 能使用自顶向下分析技术的文法正是 LL(1)文法,LL(1) grammar,A grammar

7、G is LL(1) iff whenever A u | v are two distinct productions of G, the following conditions hold: for no terminal a do both u and v derive strings beginning with a (i.e. first sets are disjoint) at most one of u and v can derive the empty string if v =* then v does not derive any string beginning wi

8、th a terminal in Follow(A),LL(1)文法,第一个L 从左到右扫描输入串 第二个L 生成的是最左推导 1 向前看一个输入符号(lookahead) 便可决定如何推导，选择那一个 产生式进行推导。 LL(k)文法：向前看k个符号。,predictive parser and LL(1)grammar,Predictive parser is a non-backtracking top-down parser. A predictive parser is characterized by its ability to choose the production to

9、apply solely on the basis of the next input symbol and the current nonterminal being processed. To enable this, the grammar must take a particular form. We call such a grammar LL(1). The first “L” means we scan the input from left to right; the second “L” means we create a leftmost derivation; and t

10、he 1 means one input symbol of lookahead.,LL(1)文法的例,例5.3 的文法GS是LL(1)文法 S aA S d A bAS A 有：SELECT(SaA)=a SELECT(Sd)=d SELECT(AbAS)=b SELECT(A)=a,d,# 所以： SELECT(SaA) SELECT(Sd) = SELECT(AbAS) SELECT(A) =,a d,b a,d,#,LL(1)文法的反例,例5.4 可以证明下面的文法GS不是LL(1)文法：S aAS S b A bA A 则 SELECT(SaAS)=a SELECT(Sb)=b SE

11、LECT(AbA)=b SELECT(A)=a,b 所以： SELECT(SaAS) SELECT(Sb) = SELECT(AbA) SELECT(A) ,a b,b a,b,选用自顶向下分析，首先必须判别所给文法是否为LL(1)文法 对任意给定的文法需计算： FIRST集、FOLLOW集、SELECT集， 进而判别是否为LL(1)文法,5.2 LL(1)文法的判别,例5.5 若文法GS为： S AB S bC A A b B B aD C AD C b D aS D c 判别步骤：,说明判断LL(1)文法的步骤的例,算法：建立一维数组，上界为非终结符个数 1) 数组元素初值为“未定”,1.

12、求出能推出的非终结符,求出能推出的非终结符算法,2) 扫描文法的产生式 (a)删除所有右部含有终结符的产生式，若结果导致某一非终结符为左部的所有产生式都被删除，将数组对应元素标记为“否”，说明该非终结符不能推出。 文法中：D aS D c 被删除，非终结符D的数组对应元素标记为“否”。,求出能推出的非终结符算法,(b) 若某一非终结符的某一产生式右部为，将数组对应元素标记为“是”，删除该非终结符的所有产生式。 文法中：A A b B B aD 非终结符A和B有产生式右部为，这4个产生式被删除，将数组对应元素标记为“是”。 文法中仅保留：S AB C AD,求出能推出的非终结符算法,3) 扫描产

13、生式右部的每一符号 (a) 若所扫描到的非终结符在数组中的对应元素标记为“是”，则删除该非终结符。若这使得产生式右部为空，则对产生式左部的非终结符的数组对应元素改为“是”，并删除以该非终结符为左部的所有产生式。 文法中：S AB 删除A和B后产生式右部为空，将S的数组对应元素改为“是”。,求出能推出的非终结符算法,(b)若所扫描到的非终结符在数组中的对应元素标记为“否”，则删除该产生式。若结果导致某一非终结符为左部的所有产生式都被删除，将数组对应元素标记为“否”。 文法中：C AD A标记为“是”，D标记为“否”，删除该产生式，C的标记改为为“否” 4)重复3)步完成一遍扫描。,2.计算FIR

14、ST集,1) 根据定义计算 由定义5.1 ： FIRST()=a*a，aVT，,V* 若* 则规定 FIRST() 对每一文法符号XV 计算FIRST(X) (a) 若XVT，则FIRST(X)=X,计算FIRST集,(b) 若XVN，且有产生式 Xa， aVT， 则 a FIRST(X) 把a加入到FIRST(X)中 (c) 若XVN X 则 FIRST(X)， 把也加到FIRST(X)中。,计算FIRST集,(d) 若X，Y1，Y2，Yn VN， X Y1Y2Yn 是一个产生式，Y1，Y2， ， Yi-1都是非终结符，而且都有*，而且，对于任何j，1ji-1，FIRST(Yj)都含有，则对

15、于 1in，有 FIRST(Yi-1) FIRST(X) FIRST(Yi) FIRST(X) 把FIRST(Yi-1)中的所有非元素以及FIRST(Yi)都加到FIRST(X)中,计算FIRST集,(e) 当(d)中所有 Yi *， 1i n 则 FIRST(X)= FIRST(Y1) FIRST(Y2) FIRST(Yn) 反复使用步骤(a)(e)产生每个符号的FIRST集合,符号串的FIRST集合,若符号串 V* =X1 X2 Xn 当 X1* 则置FIRST()=FIRST(X1) 若对任何 j 1ji-1,2i n, FIRST(Xj) i-1 则FIRST()=FIRST(X1)-

16、FIRST(Xj) j=1 当所有FIRST(Xj)都含有 时，则 n FIRST()=FIRST(X1) j=1,例5.5文法各非终结符的FIRST集,FIRST(S)=(FIRST(A)- ) (FIRST(B) - )b=b,a, FIRST(A)= b= b, FIRST(B)=a= a, FIRST(C)=(FIRST(A)- ) FIRST(D)FIRST(b)=b,a,c FIRST(D)=ac=a, c,每个产生式右部符号串的FIRST集,FIRST(AB)=b,a, FIRST(bC)= b FIRST()= FIRST(b)=b FIRST(aD)=a FIRST(AD)=

17、b,a,c FIRST(AS)=a FIRST(c)=c,S BdA First(S)=a,b,c,d S SAC A AB First(A)=a, b,c, A AaC A a First(A) =a A First(A) =a, B BA B CA First(B) = a,b, c, B b First(B) = b C c First(C) = c C First(C) = c, ,例：一个文法的FIRST集,2) 由关系图法求文法符号的FIRST集,(a)每个文法符号对应图中一个结点，非终结符用FIRST(A)标记 (b)如果文法中有产生式 AX，且*则从对应A的结点到对应X的结点连

18、一条弧 (c) 凡是从FIRST(A)结点有路径到达的终结符结点的标记都是FIRST(A)的成员 (d)由判别步骤1确定是否为FIRST(A)成员,由关系图法求文法符号的FIRST集,由关系图求例5.5的FIRST集,FIRST(S)=b,a, FIRST(A)= b, FIRST(B)=a, FIRST(C)=a,b,c FIRST(D)=a,c,3.计算FOLLOW集,1) 根据定义计算 对于文法中每一A VN 计算FOLLOW(A) (a) 对于文法的开始符号S，把句子括号#加入到FOLLOW(S) 中； (b) 若A B是一个产生式，则把 FIRST()的非空元素加至FOLLOW(B)

19、中,计算FOLLOW集,若 * 即 FIRST()，则把FOLLOW(A)加至FOLLOW(B)中。 若有产生式A B，则所有包含A的串中，A可以被B代替，所以FOLLOW(B)包括FOLLOW(A)。 注意： 永远也不是FOLLOW集合中的元素； FOLLOW仅针对非终结符定义。,例5.5文法各非终结符的FOLLOW集,FOLLOW(S)=#FOLLOW(D)= # FOLLOW(A)=FIRST(B)- FOLLOW(S)FIRST(D)=a,#,c FOLLOW(B)= FOLLOW(S)=# FOLLOW(C)= FOLLOW(S)=# FOLLOW(D)= FOLLOW(B)FOLL

20、OW(C) =#,由关系图法求文法符号的FOLLOW集,FOLLOW(S)=# FOLLOW(A)=a,#,c FOLLOW(B)=# FOLLOW(C)=# FOLLOW(D)=#,4.计算SELECT集,例5.5的FIRST集和FOLLOW集,计算SELECT集,SELECT(SAB)= FIRST(AB)FOLLOW(S)=b,a,# SELECT(SbC)=FIRST(bC)=b SELECT(SAB)SELECT(SbC)= b,a,#b 由LL(1)文法定义知该文法不是LL(1)文法,计算SELECT集,SELECT(A)= FIRST()FOLLOW(A)=a,c,# SELEC

21、T(Ab)=FIRST(b)=b SELECT(A)SELECT(Ab)= a,c,#b=,5.3 某些非LL(1)文法 到LL(1)文法的等价变换,自顶向下分析的主要问题： 1.必须是LL(1)文法 2. 包含直接或间接左递归的文法不是LL(1)文法：消除左递归 3.含有左公共因子的文法不是LL(1)文法：从多个候选产生式中提取左因子 4.二义性：消除文法的二义性。,1. 提取左公共因子,若文法中含有形如：A|的产生式，使得： SELECT(A)SELECT(A) 不满足LL(1)文法的充分必要条件。 提取左因子： A| 等价变换为 A(|) 引入A，去掉括号，变换为 AA A|,提取左公共

22、因子的例,例5.6 若文法G1的产生式为： SaSb SaS S 提取左因子： SaS(b|) S 变换为文法G1： SaSA Ab A S 可以证明为G1 仍然不是一个LL(1)文法 不含左公共因子只是一个必要条件,提取左公共因子的例,例5.7 若文法G2的产生式为： Aad ABc BaA BbB 替换为：Aad AaAc AbBc BaA BbB 提取左因子： Aa(d|Ac) AbBc BaA BbB 引入A： AaA AbBc Ad AAc BaA BbB,可以证明是一个LL(1)文法,提取左公共因子的例,例5.8 若文法G3的产生式为： SaSd SAc AaS Ab 替换为：Sa

23、Sd SaSc Sbc AaS Ab 提取左因子： SaS(d|c) 引入A： SaSA Sbc Ad|c AaS Ab 右部无A，后两个以A为左部的产生式应删除,可以证明是一个LL(1)文法,提取左公共因子的例,例5.9 若文法G4的产生式为： SAp|Bq AaAp|d BaBq|e 替换为：S aApp|aBqq Sdp|eq AaAp|d BaBq|e 提取左因子： Sa(App|Bqq) 引入S：SaS Sdp|eq SApp|Bqq AaAp|d BaBq|e,可以提取左因子,2.消除左递归,直接或间接左递归文法： a) AA AVN， V* b) AB BA A,BVN， ,V*

24、 a)为直接左递归，b) 为间接左递归 一个文法是左递归时不能采用自顶向下分析法。左递归文法导致分析过程的死循环。,例5.10 文法G5含有直接左递归： SSa Sb 产生语言 L=ban|0 输入串baaaa#是该语言 的句子 无法确定何时 用Sb替换,直接左递归的例,左递归关于非终结符P的规则,直接左递归：若 P P| 、 V*且不以P开头 间接左递归：若 P * P S Aa A Sb ,消除左递归,消除直接左递归 形如：P P| 非 ，不以P打头 改写为：P Q Q Q|,a)消除直接左递归,对文法G5： SSa Sb 可改写为： SbS SaS| 改写后的文法所产生的语言句子集仍为：

25、L=ban|0 改写后的文法为LL1文法,消除左递归,消除间接左递归 要求文法:1. 无回路(A(+A) 2.无空产生式 先将间接左递归变成直接左递归，然后再消除直接左递归。,间接左递归的例,例5.11文法G6为： AaB ABb BAc Bd 若有输入串：adbc# 分析过程的语法树：,b)消除间接左递归,对文法G6：AaB ABb BAc Bd 替换为：AaB ABb BaBc BBbc Bd 消除左递归：AaB ABb B(aBc|d)B BbcB| 改写后的文法为LL1文法,c)消除文法中一切左递归的算法,对文法中一切左递归的消除要求文法中不含回路 A+A 的推导 满足这个要求的充分条

26、件是，文法中不含形如 AA 的有害规则和 A 的空产生式,消除文法中一切左递归的算法步骤,把文法的所有非终结符按某一顺序排序，如：A1,A2,An 从A1开始消除左部为A1的产生式的直接左递归，然后把左部为A1的规则的右部逐个替换左部为A2右部以A1开始的产生式中的A1，并消除左部为A2的产生式的直接左递归， 去掉无用产生式,使用算法消除左递归的例,例：有文法的产生式为： (1) SQc|c (2) QRb|b (3)RSa|a 若排序为：S Q R 无直接左递归，替换：(1)代入(3) (4) R Qca|ca|a 替换：(2)代入(4) (5) R Rbca|bca|ca|a 消除直接左递

27、归 SQc|c QRb|b R (bca|ca|a)R R bcaR|,使用算法消除左递归的例,(1) SQc|c (2) QRb|b (3)RSa|a 若排序为：R Q S 替换：(3)代入(2) Q Sab|ab|b 再代入(1) S Sabc|abc|bc|c 消除直接左递归 S (abc|bc|c)S SabcS| R (bca|ca|a)R R bcaR|,消除左递归的例,例：考虑文法 S (L)|a LL,S|S 消除左递归后的文法为 S(L)|a LSL L,SL|,5.4 不确定的自顶向下分析思想,当文法不满足LL(1)时，可以用不确定的自顶向下分析法(带回溯的自顶向下分析法)

28、 当某个非终结符的产生式有多个候选时，对当前输入符号无法确定选用唯一的产生式，从而引起回溯。 回溯退回，重新匹配,1.由于相同左部的产生式的右部FIRST集的交集不为空而引起回溯,例如，有文法： SxAy Aab|a 若当前输入串为 xay 对于字符 a，可选用产生式Aab， 但b和y不匹配，回溯，重新选用Aa,2.由于相同左部的非终结符的右部存在能 * 的产生式，且该非终结符FOLLOW集中含有其它右部FIRST集的元素,例如，文法： S aAS S b A bA A 对当前输入串 ab#，首选 S aAS 对于字符 b，可选用产生式 A bA A为非终结符，而且后面有S，回溯，选用产生式

29、A ，然后选S b，完成匹配。,3.由于文法含有左递归而引起回溯,例如，文法： S Sa S b 对当前输入串 baa#， 对于字符 b，可选用产生式 S b，b为终结符，不能继续推导，回溯 选用产生式 S Sa ，再选S Sa 最后选 S b,5.5 确定的自顶向下分析方法,自顶向下分析方法有： 递归子程序法递归过程 预测分析方法无回溯的自顶向下分析,5.5.1递归子程序法,将一个非终结符A的文法规则看作识别A的过程的定义. 文法中的每个非终结符号对应一个递归过程 根据输入句子的当前单词，确定所选用的产生式。 当存在多个候选产生式时，按照LL(1)形式唯一的确定一个产生式进行推导。,对于产生

30、式右部的终结符号，则将其与输入单词匹配；对于产生式右部的非终结符号，则调用相应的递归过程。 重复以上过程，构造关于输入句子的最左推导。,递归子程序法,5.5.2 预测分析方法,预测分析器 预测分析程序 先进后出栈 预测分析表 仅预测分析表与文法有关,非递归的预测分析方法 对于像汇编语言、Fortran等不具有递归机制的语言，需要非递归的分析方法。 非递归分析方法比递归分析方法的效率高,预测分析方法,根据输入串模拟出推导过程。这里将推导产生的句型看作一个二元组： (已匹配的符号串 | 未匹配的符号串) matched unmatched 初态：matched = ； unmatched = S(文法开始符号) 终态：matched = 句子； unmatched = ,预测分析方法的思想,句型的存储：1、已匹配的符号串不必存储。2、由于是最左推导，因此，