自顶向下语法分析方法课件.ppt

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

1、第5章自顶向下语法分析(Top-downSyntaxAnalysis)语法分析的主要工作：是识别由词法分析给出的单词序列是否是给定的正确句子（程序）。语法分析常用的方法：自顶向下的语法分析和自底向上的语法分析两大类。自顶向下分析思想自顶向下的方法：从文法的开始符号（设为〈程序〉）开始进行分析，逐渐推导的往下构造语法树，使其树叶正好构造出所给定的源程序串。自顶向下的主要思想：从开始符出发导出句型并一个符号一个符号地与给定终结符串进行匹配。如果全部匹配成功，则表示开始符号可推导出给定的终结符串。因此判定给定终结符号串是正确句子。自顶向下方法的关键：是确定在推导过程

2、中选择候选式的问题。当进行推导时，一个非终结符可能对应多个产生式，这样我们就无法事先知道应该用哪个产生式，因此实用都作了一些限制。以便在任何情况下都能确定应该用的产生式。自顶向下的缺点:在推导过程中，如果对文法不做限制。那么产生式的选择成为无根据的，只好一一去试所有可能的产生式，直至成功为止。这种方法的致命弱点是不断地回溯，大大影响速度。所以自顶向下分析法又分为确定的和不确定的两种：确定的分析方法需对文法有一定的限制，但由于实现方法简单，直观，便于手工构造或自动生成语法分析器，因此仍是目前常有的方法之一。不确定的方法即回溯的分析方法。这种方法实际上是一种穷举的

3、试探方法，因此效率低，代价高，因此极少使用。5.1确定的自顶向下分析思想例5.1若有文法G[S]：S→pAS→qBA→cAdA→a若有输入串w=pccadd.解：推导过程为：其相应的语法树见右图：SS这个文法的特点：[1]每个产生式的右部都由终结符号开始。[2]如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。显然对于这样的推导中完全可以根据当前的输入符号决定选择哪个产生式往下推导。因此分析过程是唯一的。pcAdcAdpccAddcAdpccaddapApA考察自顶向下的推导过程。例5.2：若有文法G2[S]：SApSBqAaAcABbBd

4、B若有输入串w=ccap。考察自顶向下的推导过程。解：自顶向下的推导过程为：其相应的语法树见右图：SS这个文法的特点：[1]产生式的右部不全是由终结符号开始。[2]如果两个产生式有相同的左部，它们的右部由不同的终结符或非终结符开始。[3]文法中无空产生式。ccApcAAppAAcApcccapa小结：在上述推导过程中，对于产生式中相同左部含有非终结符打头的右部时，在推导中选用哪个产生式是不能直接知道的。对输入串W=ccap为输入串时，其第一个符号为c，这时从S出发选择S→Ap，还是选择S→Bq。其根据是要知道A或B它们是否能推导以c打头的符号串，即它们

5、的首符集是什么。若c是Ap的首符集的元素，且不在Bq的首符集中，则选择S→Ap往下推导。反之，若c在Bq的首符集中，不在Ap的首符集中，则选择S→Bq往下推导。其它情况为不确定推导或出错。因此，在推导前有必要求出每个文法符号的首符集。一.首符集，后继符集与选择集的定义：定义4-1（首符集定义）：设G=(VN，VT，P，S）是上下文无关文法，α是G的任一符号串，则有：FIRST（α）={a

6、α*aβ,a∈VT，α、β∈V*}特别地，若α*ε，则规定ε∈FIRST(α)即：FIRST(α)是从α出发推导出的所有符号串首终结符或可能的ε构成的集合。这样在文法G2

7、中，关于S的两个产生式虽然都以非终结符开始，但它们右部符号串可以推导出首符集合互不相交，因此可根据当前的输入符号是属于哪个产生式右部的首符号集合而决定选择相应产生式进行推导。因此是确定的自顶向下分析。有文法G2[S]：SApSBqAaAcABbBdB例5.3:若有文法G3[S]:S→aAS→dA→bASA→ε若有输入串W=abd。考察自顶向下的推导过程。解：相应语法树为右图：SSaAaAabASbASabSεabdd当文法中有空产生式时,如例：小结：由此可以看出，当某一非终结符的产生式中含有空产生式时，它的非空产生式右部的首符号集两两不相交，并与在推导

8、过程中紧跟该非终结符右边可能出现的终结符集也不相交，则仍可构造确定的自顶向下分析。为此可定义一个文法符号的后继符集合为：（定义5.2）从上述推导过程中我们可以在第二步到第三步的推导中，即abASabS时，因当前面临输入符号为d，而最左非终结符A的产生式右部的开始集合都不包括d，但有ε，因此对于d的匹配自然认为只能依赖于在可能的推导过程中A的后面的符号。所以这时选用产生式A→ε往下推导，而当前A后面的符号为S，S产生式右部的开始符号包括了d，所以匹配。FOLLOW(A)={a

9、S*μAβ且a∈VT,a∈FIRST(β),μ∈VT*,β∈V*}或FOLLOW(

10、A)={a

11、S*…Aa…,a∈VT}