资源描述：
《教案5编译原理》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第5章自上而下语法分析第1讲讲授内容：确定的自上而下语法分析的基本思想，FIRST集合，FOLLOW合，SELECT集合的定义以及求法，确定的白上而下语法分析方法，把某些非LL(1)文法转换成LL(1)文法。本讲重点：本讲是本课程的重点内容，也是难理解的内容之一。FIRST集合，FOLLLOW集合，SELECT集合的定义的背景和求法，都要求学生有较强的抽象思维能力。讲授方法：本章对学生的数学和思维能力要求很高，所以在讲授吋，首先通过例子引出FIRST集合，FOLLOW集合，SELECT集合的定义的背景，讲清楚自上而下的分析思想，然后，对以
2、上三个集合进行定义，只有把定义搞懂了，才能理解求以上三个集合的算法。作业：P901,2,3,4,6(2),6(3),7(1),7(2)在以后的章节中(即语法分析中)，我们用一个字符表示一个单词，如SUM二FIRST+SECOND,写成S二a+b。因此，在语法分析中，我们只考虑语法是否正确，而不考虑单词是否正确。单词的正确与否由词法分析子程序完成。语法分析，即判断句子是否符合文法，分为自上而下和自下而上两种，而自上而下又分为确定的和不却说的；而自下而上又分为LR(K)分析法和算符优先分析法。本章介绍确定的自上而下分析法。5.1确定的自上而下
3、分析思想从文法的开始符号出法，从左到右逐一读入字符，根据当前的输入字符和当前句型最左边的非终结符，可以唯一地选择产生式，往下推导，直至推导出要分析的句子。例5.1S-pAS-qBA—cAdAfaB—b分析输入串W=pccadd推导过程如下：S=>pA=>pcAd=>pccAdd=>pccadd可以看出，符号串pccadd是文法的句子。在推导过程屮，为了和当前符号匹配，每推导一步产生式的选择只有一种(由当前句型最左边的非终结符和当前扫描符号决定性)。上例的文法有三个特点：产生式右部以终结符开始；若一非终结符有多个产生式，则它们的右部以不同的
4、终结符例5.2S—ApS-*BqAfaAfcABfbB-dB输入串w=ccap推导过程如下:开始；无空空产生式。S=>Ap=>cAp=>ccAp=>ccap该文法有三个特点：产生式右部不全以终结符开始；若一非终结符有多个产生式，则它们的右部以不同的终结符开始；无空空产生式。［注］在推导的第一步，是用产生式SfAp还是用产生式S->Bq?因为Ap可能推导出的第一个(最左)终结符为{a,c},而Bq为{b,d},而当前的输入字符为c,故选择S->Apo定义5。1设G二(VT,VN,S,P)是一个上下文无关文法，FIRST(a)={a
5、a=>a
6、3,aeVT,a,BWV*}若«=>e,则规定a=>eFIRST(a)。(即字符串a可能推出的开始符号集)例S-ApS-BqA—aAcAB-bB—dBFIRST(Ap)={a,c}FIRST(Bq)二{b,d}FIRST(dB)={d}FIRST(a)={a)尽管产生式S-Ap和S-Bq以非终结符开始，但它们右部的FIRST集合没有公共元素，所以面对当前输入字符，仍然只有一种选择S->Apo例5.3S-aAS-dAbASA—£输入串w=abd推导过程如下：S=>aA=>abAS=>abS=>abd我们观察推导的第三步：“bAS二〉abS,
7、即选择了产生式A-£,因为当前输入符号为d,而当前句型最左非终结符A的非空产生式右部的FIRST集合为{b,£},不含有d,不能匹配，而FIRST(S)={a,d},所以对d的匹配只能依靠A后面的ST，故选择了产生式A—£。可以看出，当某一非终结符含有空产生式时，它的非空产生式右部的FIRST集合两两不相交，并与在当前句型中紧跟在该非终结符右边可能出现的终结符集合也不相交,则仍可唯一地选择产生式。定义5。2设G是一个上下文无关文法，FOLLOW(A)二{a
8、S二〉....・Aa}若S=>A,则规定#eFOLLOW(A)其中，#为句子括号。
9、若文法中关于A的产生式有两条，A-a,B-B,若a和B不能同时推出£,设A不能推出£,B能推出£,若FIRST(a)fl(FIRST(B)UFOLLOW(A))二①时，则对推导过程中，非终结符A仍可唯一地选择产生式。具体地，若文法中关于A的产生式有：A—a,A-*e,设a不能推出空，若FIRST(a)AFOLLOW(A)二①时，则可以唯一选择产生式。即若当前输入符号出现在FIRST(a)中，则选择A-a；若当前输入符号不出现在FIRST(a)中，则选择A-a。定义5。3上下文无关文法的产生式A-a,若右部不能推出空,则SELECT(A->
10、a)=FIRST(a),若右部能推出空，则SELECT(A->a)二FIRST(a)UFOLLOW(A)定义5。3—个上下文无关文法是I丄(1)文法的充要条件是对每个非终结符A的任意两个不同的
