编译原理select()集合的求法

资源描述

《编译原理select()集合的求法》由会员分享，可在线阅读，更多相关《编译原理select()集合的求法（100页珍藏版）》请在金锄头文库上搜索。

1、编译原理第一章编译程序概述第二章 PL/0编译程序的实现第三章文法和语言第四章词法分析第五章自顶向下语法分析方法第六章自底向上优先分析方法第七章 LR分析方法第八章语法制导翻译和中间代码生成第九章符号表第一章代码优化第一一章代码生成第5章自顶向下语法分析方法语法分析是编译程序的核心部分：在词法分析的基础上，识别单词符号序列是否是给定文法的正确句子（程序）。常用方法自顶向下分析自底向上分析确定不确定算符优先分析 LR分析自顶向下语法分析方法自顶向下分析法就是从文法的开始符号出发，试图推导出与输入的单词串完全匹配的句子。如果能够推导出，则该输入

2、串是给定文法的句子；如果不能推导出，则该输入串不是给定文法的句子。自顶向下语法分析要解决的关键问题假定要被代换的最左非终结符号是B，且有n条规则：BA1|A2|An，那么如何确定用哪个右部去替代B？自顶向下语法分析方法自顶向下分析法分确定性和不确定性两种。自顶向下的确定性分析法对文法有一定的限制，但实现简单直观，便于手工或自动构造；自顶向下的不确定性分析法是带有回溯的分析方法，效率低，代价高，极少使用。第5章自顶向下语法分析方法一、确定的自顶向下分析思想二、LL(1)文法的判别三、某些非LL(1)文法到LL(1)文法等价变换四、不确定的自顶向下分析思想五、确定的自顶

3、向下分析方法自顶向下语法分析要解决的关键问题假定要被代换的最左非终结符号是B，且有n条规则：BA1|A2|An，那么如何确定用哪个右部去替代B？一、确定的自顶向下分析思想1、方法：从开始符号出发，不断替换非终结符，根据当前的单词符号就可以唯一选定要替换的产生式。例1：文法G(S)：SpASqBAcAdAa输入串 W=pccadd 自顶向下的推导过程为: SPASPAcdAcdASPAcdAcdASPAcdAa相应的语法树：SpA pcAd pccAdd pccadd例1：文法G(S)：SpASqBAcAdAa该文法的特点：（1）每个产生式的右部都由终结符号开始；（2 ）如果两个产生式

4、有相同的左部，则它们的右部由不同的终结符开始。对于这样的文法，其推导过程可以根据当前的输入符号决定选择哪个产生式往下推导，因此，分析过程是唯一确定的。例2：文法G(S)为： S ApS BqA acABbdB 该文法的特点：（1）产生式的右部不全是由终结符号开始；（2 ）如果两个产生式有相同的左部，则它们的右部由不同的终结符或非终结符开始。（3）无空产生式。ccap如何根据输入串的第1个符号来确定产生式呢？例2：文法G(S)为： S ApS BqA acABbdB 当输入W=ccap推导：自顶向下的推导过程为：例2：文法G(S)为： S ApS BqA acABbdB 当输入W=cc

5、ap推导：自顶向下的推导过程为：S Ap cAp ccAp ccap语法树为：SAPSAPcASAPcAcASAPcAcAa例2：文法G(S)为： S ApS BqA acABbdB 该文法的特点：（1）产生式的右部不全是由终结符号开始；（2 ）如果两个产生式有相同的左部，则它们的右部由不同的终结符或非终结符开始。（3）无空产生式。ccap如何根据输入串的第1个符号来确定产生式呢？ 2、开始符号集合的定义：设G=（VT，VN， P ，S ）是上下文无关文法，开始符号集合为First()= a | a，aVT，、 V* 规则右部的开始符号集包括所有终结符 a，使得规则右部经过若干推导后得到

7、针对产生式规则的右部产生开始符号集合如何根据输入串的第1个符号来确定产生式呢？根据当前输入符号属于哪个产生式右部的开始符号集合而决定选择相应产生式进行推导。例3：文法GS ： S aA | d A bAS| 若输入W=abd，则推导过程为：SaASaAbASSaAbASd例3：文法GS ： S aA | d A bAS| 若输入W=abd，则推导过程为：S aA abAS abS abd语法树为：当某一非终结符的产生式中含有空产生式时，第二步推导的产生式该如何确定呢？根据后跟符号集合确定3、后跟符号集合的定义：设G=（VT，VN，P，S）是上下文无关文法，AVN，S 是开始符号，Fo

9、qA a | cAB b | dB求Follow集。解：Follow(S)=#Follow(A)=pFollow(B)=q自上而下语法分析要解决的关键问题假定要被代换的最左非终结符号是B，且有n条规则：BA1|A2|An，那么如何确定用哪个右部去替代B？根据规则的选择集合来确定。4、选择集合的定义给定上下文无关文法的产生式A，AVN，V*，若，则Select（A）=First()，若，则Select(A)=（First()-）Follow(A) *给定输入串，根据产生式规则的选择集合选择产生式进行推导。5、LL(1)文法的定义：一个上下文无关文法是LL(1)文法的充分必要条件是对每个非

10、终结符A的两个不同产生式：A，A满足Select(A)Select(A)=，其中、不同时推出只有对满足LL(1)文法的句子，才能进行确定的自顶向下分析：给定输入串，就可以根据产生式规则的选择集合确定唯一的产生式进行推导。 LL(1)的含义：从左L向右扫描输入串，分析过程中采用最左L推导，只需向右看1个符号就可确定如何推导（选择哪个产生式进行推导）。例5：上例3文法： SaA|d AbAS|证明该文法为LL(1)文法。例5：上例3文法： SaA|d AbAS|证明该文法为LL(1)文法。不难看出：Select(Sa A)=First(aA)aSelect (Sd)= First(d)

11、=dSelect (AbAS)=bSelect (A)=（first()- ）follow(A)=a,d,#Select (S aA) Select(Sd) ad=Select(AbAS) Select(A)ba,d,#= 所以上述文法是LL(1)文法。 SAa aA *SaA abAS abAd S aA abAS abAaA 所以Follow(A)=a,d,#例：设文法GS为：S aAS | bA bA | 判别是否是LL(1)文法。解：Select(S aAS)=first(aAS)=aSelect ( S b ) =bSelect ( A bA ) =bSelect ( A ) =（f

12、irst()-）follow(A)=a,bSelect( SaAS ) Select(Sb ) a b =Select(A bA) Select(A )ba,b因此，该文法不是LL（1）文法，因而也就不可能用确定的自顶向下分析。当需要选用自顶向下分析技术时，首先必须判定所给的文法是否是LL(1)文法。二、 LL(1)文法的判别例：若文法GS为： S AB | bCA | bB | aDC AD | bD aS | c判别文法是否是LL(1)文法。解：(1) 计算first集：方法一：计算first 集合的算法：对于每一个文法符号xV，计算first(x)的方法如下：a) 若xVT，则

13、first(x)xb) 若xVN，且有xa，aVT，则afirst(x)c) 若xVN，x ，则first(x)d) 若xVN，y1，y2，yi都VN，产生式 xy1y2yn，当y1，y2，yi-1都时(1in)，则first(y1)， first(y2)， first(yi1) ，first(yi)都包含在first(x)中。a) e) 当上式中所有yi (1in)，b) 则first(x)first(y1) first(y2) first(yn) *first(S)=first(A)=first(B)=first(C)=first(D)=S AB | bCA | bB | aDC AD

14、| bD aS | c按上面的规则可得上例文法中每个文法符号的 first集合如下：first(S)=first(A)- first(B)- b=a,b, first(A)=b =b, first(B)= a=a, first(C)=first(A)- first(D) first(b)=a,b, cfirst(D)=a c=a,cS AB | bCA | bB | aDC AD | bD aS | c按上面的规则可得上例文法中每个文法符号的 first集合如下：一个文法符号串的first集合计算方法：如果文法符号串V*, =X1X2Xn,1、当X1，则first()=first(X1)2、当对任何j（1ji-1，2 i n），first(Xj)则first()=(first(X1)-) (first(X2)-) (first(Xi-1)-) first(Xi)3、当first(Xj)都含有时(1 j n)，则 first()=first(X1) first(X2) first(Xj) *根据上面规则，每个产生式的右部符号串开始符号集合为：first(AB)=first(bC)=first()=first(aD)=first

展开阅读全文