编译第五章终版.ppt

《编译第五章终版.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第5章自顶向下语法分析方法5.1确定的自顶向下分析思想5.2LL(1)文法的判别5.3某些非LL(1)文法到LL(1)文法的等价变换5.4不确定的自顶向下分析思想5.5确定的自顶向下分析方法5.6典型例题及解答引言1、语法分析的地位是编译程序的核心部分。2、语法分析的任务识别由词法分析得出的单词序列是否是给定文法的句子。3、语法分析方法自顶向下分析和自底向上分析自顶向下分析包括确定分析和不确定分析自底向上分析包括算符优先分析和LR分析引言4、语法分析的方式1）自上而下语法分析反复使用不同产生式进行推导以谋求与

2、输入符号串相匹配。2）自下而上语法分析对输入符号串寻找不同产生式进行归约直到文法开始符号。注：这里所说的输入符号指词法分析所识别的单词引言自顶向下分析法：也就是从文法的开始符号出发，企图推导出与输入的单词串完全相匹配的句子，若输入串是给定文法的句子，则必能推出，反之必然出错。自顶向下分析法又可分为确定的和不确定的两种。确定的分析方法:需对文法有一定的限制，但由于实现方法简单、直观，便于手工构造或自动生成语法分析器。不确定的方法:即带回溯的分析方法，这种方法实际上是一种穷举的试探方法，因此效率低，代价高，因而极

3、少使用。自下而上分析法：从输入串出发进行归约，最终归约为文法开始符。从叶结点出发，向上归结出以文法开始符为根结点的语法分析树。引言回顾在“文法和语言”一章中介绍的关于句子、句型和语言的定义及什么叫最左推导、最右推导和规范推导的基本概念。有文法G[S]，若S*x，且x∈V*则称x是文法G[S]的句型。有文法G[S]，若S*x，且x∈VT*，则称x是文法G[S]的句子。例：G[S]：S→0S1，S→01可有推导S0S100S11000S11100001111说明00001111是G[S]的句子。引言最

4、左（最右）推导：在推导的任何一步αβ(其中α、β是句型)，都是对α中的最左（右）非终结符进行替换。最右推导被称为规范推导。由规范推导所得的句型称为规范句型。句型的分析句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。举例：文法：G={VN,VT,S,P}P：S→aAcBeA→b

5、AbB→d判断输入串abbcde是否为文法的句子。（1）自顶向下最左推导：s⇒aAcBe⇒aAbcBe⇒abbcBe⇒abbcdeSAaBcebAbd文法：G={VN,VT,S,P}P：S→aAcBeA→b

6、AbB

7、→d判断输入串abbcde是否为文法的句子。（2）自底向上abbcdeabbcBeabAcBeaAcBeSSAaBcebAbd引言句型分析的有关问题①如何选择使用哪个产生式进行推导？假定要被替换的最左非终结符号是V，且左部为V的规则有n条：V→A1

8、A2

9、…

10、An，那么如何确定用哪个右部去替换V呢？②如何识别可归约的串？在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中寻找一个子串，看它是否能归约到文法的某个非终结符号，该子串称为“可归约串”。5.1确定的自顶向下分析思想例：若有文法G1[S]:

11、S→pA

12、qBA→cAd

13、aB→dB

14、b识别输入串w=pccadd是否是G1[S]的句子试探推导过程：SpApcAdpccAddpccadd5.1确定的自顶向下分析思想G1[S]:S→pA

15、qBA→cAd

16、aB→dB

17、b这个文法有以下两个特点：①每个产生式的右部都由终结符号开始。②如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。5.1确定的自顶向下分析思想若有文法G2[S]:S→Ap

18、BqA→a

19、cAB→b

20、dB识别输入串w=ccap是否是G2[S]的句子，那么试探推出输入串的推导过程

21、为：SApcApccApccap5.1确定的自顶向下分析思想G2[S]:S→Ap

22、BqA→a

23、cAB→b

24、dB文法的特点是：①产生式的右部不全是由终结符开始。②如果两个产生式有相同的左部，它们的右部是由不同的终结符或非终结符开始。③文法中无空产生式。FIRST集的定义:设G=(VT,VN,P，S)是上下文无关文法FIRST()={a

25、*a,a∈VT,,∈V*}FIRST()={a

26、*a……,a∈VT}若*ε则规定ε∈FRIST()FIRST()为的开始符号或首符号集。在文法

27、G2中，FIRST(Ap)＝{a,c}FIRST(Bq)＝{b,d}返回分析前两个确定的文法选择哪个产生式可以看其first集结论：因此当文法含有形如Ａαβ产生式时，其中A∈VN，α、β∈V*，若α和β都不能同时推导出空，则当FIRST(α)∩FIRST(β)=时，对于非终结符A的替换可唯一的确定候选。FIRST()集的构造：对每一个文法符号x(VN∪V),构造first(x)时，只要连续