编译原理 第五章ppt.ppt

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

1、1自顶向下语法分析方法2语法分析是编译程序的核心部分，作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子(程序)，目前语法分析常用的方法有自顶向下（自上而下）分析和自底向上（自下而上）分析两大类。本章主要介绍确定的自顶向下分析思想和对文法的要求。3自顶向下分析法---面向目标的分析方法，从文法的开始符号出发企图推导出与输入的单词串完全相匹配的句子，若输入串是给定文法的句子，则必能推出，反之必出错。分为确定的和不确定的两种。确定的分析方法需对文法有一定的限制，实现方法简单、直观，便于手工构造或自动生成语法分析器，是目前常用的方法之

2、一。不确定的方法即带回溯的分析方法，实际上是一种穷举的试探方法，效率低，代价高，因而极少使用。4句型:有文法G[S]，若S=>*x，且x∈V*则称x是文法G[S]的句型。　符号=>*表示经过0步或若干步的推导。句子:有文法G[S]，若S=>*x，且x∈VT*，则称x是文法G[S]的句子。例：G[S]：S→0S1，S→01可有推导S=>0S1=>00S11=>000S111=>000011115最左（最右）推导：在推导的任何一步αβ(其中α、β是句型)，都是对α中的最左（右）非终结符进行替换。　　最右推导被称为规范推导。　　由规范推导所

3、得的句型称为规范句型6句型的分析句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。　　在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号。7句型分析的有关问题①如何选择使用哪个产生式进行推导？　　假定要被替换的最左非终结符号是V，且左部为V的规则有n条：V→A1

4、A2

5、…

6、An，那么如何确定用哪个右部去替换V呢？　　②如何识别可归约的串？　　在自下而上的分析方法中，在分析程序

7、工作的每一步，都是从当前串中寻找一个子串，看它是否能归约到文法的某个非终结符号，该子串称为“可归约串”。8确定的自顶向下分析思想确定的自顶向下分析方法，要解决从某文法的开始符号出发，对给定的输入符号串如何根据当前的输入符号(单词符号)唯一地确定选用哪个产生式替换相应非终结符往下推导，或如何构造一棵相应的语法树9例5.1若有文法G1[S]:S→pA

8、qBA→cAd

9、aB→dB

10、c识别输入串w=pccadd是否是G1[S]的句子试探推导过程：S=>pA=>pcAd=>pccAdd=>pccadd试探成功。10这个文法有以下两个特点：　　①每个

11、产生式的右部都由终结符号开始。　　②如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。对于这样的文法显然在推导过程中完全可以根据当前的输入符号决定选择哪个产生式往下推导，因此分析过程是唯一确定的。11例5.2若有文法G2[S]:S→Ap

12、BqA→a

13、cAB→b

14、dB识别输入串w=ccap是否是G2[S]的句子，那么试探推出输入串的推导过程为：S=>Ap=>cAp=>ccAp=>ccap试探推导成功。文法的特点是：①产生式的右部不全是由终结符开始。　　②如果两个产生式有相同的左部，它们的右部是由不同的终结符或非终结符开始。　

15、　③文法中无空产生式。12对于产生式中相同左部含有非终结符开始的产生式时，在推导过程中选用哪个产生式不像例5.1文法那样直观第一个符号是c，这时从S出发选择S→Ap还是选择S→Bq，需要知道，Ap或Bq它们的开始符号集合是什么13例5.3若有文法G3[S]:S→aA

16、dA→bAS

17、ε识别输入串w=abd是否是G3[S]的句子　　试探推导出abd的推导过程为：S=>aA=>abAS=>abS=>abd试探推导成功。在abAS=>abS时，因当前面临输入符号为d，而最左非终结符A的产生式右部的开始符号集合都不包含d，但有ε，因此对于d的匹配自

18、然认为只能依赖于在可能的推导过程中A的后面的符号，所以这时选用产生式A→ε往下推导，而当前A后面的符号为S，S产生式右部的开始符号集合包含了d，所以可匹配。文法的特点是：文法中含有空产生式。14从5.3可以看出：当某一非终结符A的产生式中含有空产生式时，它的非空产生式右部的开始符号集两两不相交，并与在推导过程中紧跟A后边可能出现的终结符集也不相交，仍可构造确定的自顶向下分析。15LL(1)文法的定义和判别一个文法能否用确定的自顶向下分析与文法中相同左部的每个产生式右部的开始符号集合有关，当有右部能=>*ε时则与其左部非终结符的后跟符号集合也

19、有关。16一个文法符号串的开始符号集合设G=(VT，VN，S，P)是上下文无关文法FIRST(α)={a

20、α=>*aβ,a∈VT，α,β∈V*}若α=>*ε,则规定ε∈FIRST