第5章自顶向下的语法分析方法ppt课件.ppt

《第5章自顶向下的语法分析方法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章自顶向下的语法分析方法语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子(程序)。目前语法分析常用的方法有:1、自顶向下（自上而下）分析2、自底向上（自下而上）分析自顶向下分析法也就是从文法的开始符号出发企图推导出与输入的单词串完全相匹配的句子，若输入串是给定文法的句子，则必能推出，反之必然出错。回顾在“文法和语言”一章中介绍的关于句子、句型和语言的定义及什么叫最左推导、最右推导和规范推导的基本概念。句型、句子、语言的定义句型:有文法G[S]，若Sx，且x∈V*则称x是文

2、法G[S]的句型。　　符号表示经过0步或若干步的推导。句子:有文法G[S]，若Sx，且x∈VT*，则称x是文法G[S]的句子。　　例：G[S]：S→0S1，S→01可有推导S0S100S11000S11100001111说明00001111是G[S]的句子。句型的分析句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。最左（最右）推导：在推导的任何一步αβ，都是对α中的最左（右）非终结符进行替换。最右推导被称为规范推导。　　由规范推导所得的句型称为规范句型。句型分析的有关问题①

3、如何选择使用哪个产生式进行推导？假定要被替换的最左非终结符号是V，且左部为V的规则有n条：V→A1

4、A2

5、…

6、An，那么如何确定用哪个右部去替换V呢？②如何识别可归约的串？在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中寻找一个子串，看它是否能归约到文法的某个非终结符号，该子串称为“可归约串”。5.1确定的自顶向下分析思想确定的自顶向下分析方法:首先要解决从某文法的开始符号出发，对给定的输入符号串如何根据当前的输入符号(单词符号)唯一地确定选用哪个产生式替换相应非终结符往下推导.例5.

7、1若有文法G1[S]:S→pA

8、qBA→cAd

9、aB→dB

10、c识别输入串w=pccadd是否是G1[S]的句子　　试探推导过程：SpApcAdpccAddpccadd试探成功。这个文法有以下两个特点：　　①每个产生式的右部都由终结符号开始。　　②如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。即每个产生式的右部的开始终结符不同。对于这样的文法显然在推导过程中完全可以根据当前的输入符号决定选择哪个产生式往下推导，因此分析过程是唯一确定的。例5.2若有文法G2[S]:S→Ap

11、BqA

12、→a

13、cAB→b

14、dB识别输入串w=ccap是否是G2[S]的句子，那么试探推出输入串的推导过程为：SApcApccApccap试探推导成功。文法的特点是：①产生式的右部不全是由终结符开始。　　②如果两个产生式有相同的左部，它们的右部是由不同的终结符或非终结符开始。　　③文法中无空产生式。对于产生式中相同左部含有非终结符开始的产生式时，在推导过程中选用哪个产生式不像例5.1文法那样直观，对于W=ccap为输入串时，其第一个符号是c，这时从S出发选择S→Ap还是选择S→Bq，需要知道，Ap或Bq它

15、们的开始终结符号集合是什么？因为c是包含在Ap的开始终结符号集合中，且不包含在Bq的开始终结符号集合中，则选择S→Ap往下进行推导。S→Ap

16、BqA→a

17、cAB→b

18、dB一个文法符号串的终结符的首符集定义如下：定义5.1设G=(VT，VN，S，P)是上下文无关文法FIRST(α)={a

19、α  aβ,a∈VT，α,β∈V*}若α  ε,则规定ε∈FIRST(α)．G2：S→Ap

20、BqA→a

21、cAB→b

22、dB不难求出在例5.2文法G2中FIRST(Ap)={a,c}FIRST(Bq)={b,d}因此有

23、FIRST(Ap)∩(FIRST(Bq)=这样文法G中，两个产生式有相同的左部，它们的右部是由不同的终结符或非终结符开始。但它们右部的符号串可能推导出的First集不相交，因而可以根据当前的输入符号是属于哪个产生式的FIRST集而决定选择相应产生式进行推导，因此仍能构造确定的自顶向下分析。例5.3若有文法G3[S]:S→aA

24、dA→bAS

25、ε识别输入串w=abd是否是G3[S]的句子　　试探推导出abd的推导过程为：SaAabASabSabd试探推导成功。文法的特点是：文法中含有空产生式。从以上

26、推导过程中我们可以看到在第2步到第3步的推导中，因当前面临输入符号为d，而最左非终结符A的产生式右部的开始符号集合都不包含d，但有ε，因此对于d的匹配自然认为只能依赖于在可能的推导过程中A的后面的符号，所以这时选用产生式A→ε往下推导，而当前A后面的符号为S，S产生式右部的开始的终结符号集合包含了d，所以可匹配。当一个文法中相同左部非终结符的右部存在能ε的情况则必须知道该非终结符的后跟符号的集合中的符号是否可以唯一地确定选择哪个产生式。为此，我们定义一个文法非终结符的