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

第5章自顶向下语法分析方法 语法分析（Syntax Analysis）是编译程序的核心部分。词法分析只是将字符形式的源程序中的各个单词识别出来，形成单词的机内表示形式，但是这些单词串如何构成更大的语法成分——语句，那就由语法分析来完成。语法分析的主要任务就是“组词成句”，即在词法分析识别出单词串的基础上，根据语言的语法规则，识别出各类语法成分，如“语句”、“程序”等。 将完成语法分析任务的程序称为语法分析程序，也称为语法分析器或简称分析器。 程序设计语言的语法结构是用上下文无关文法描述的，因此，语法分析器的实现原理就是按所给定的文法G，识别输入符号串α是否为一个句子（即α∈L(G)成立吗？），同时检查和处理语法错误。语法分析的关键是句型识别问题。给定一串单词（即文法的终结符），怎样知道它是不是该文法产生的一个句子呢？可以利用推导，或者利用语法树来进行判断。一般来说，语法分析的过程就是为一个句子建立语法树的过程。 语法分析的方法很多，按照建立语法树的不同方向，通常将语法分析分为两类，一类是自顶向下分析法，另一类是自底向上分析法。 本章主要介绍自顶向下分析法，自底向上分析法。 第4章教学内容 语法分析的任务； 确定的自顶向下语法分析的基本思想； LL(1)文法的定义和判别方法； 非LL(1)文法到LL(1)文法的等价变换； 确定的自顶向下分析方法： 递归下降分析法 预测分析法 自底向上语法分析的基本思想； 短语、直接短语和句柄的定义，以及如何利用语法树寻找短语、直接短语和句柄。 自底向上语法分析方法： 优先分析法 LR分析法 一、自顶向下的语法分析思想 【自顶向下（top - down ）分析法的基本思想】自顶向下语法分析的基本思想是以文法的开始符号为树根，采用最左推导，试图自上而下地为输入的单词串构造一棵语法树。若语法树的端末节点从左向右排列恰好是输入串，则该输入串就是文法的句子，否则就不是。 这种分析过程实质是一种试探过程，是反复使用不同产生式来匹配输入串的过程。 示例 【例4.1】设有以下文法G1[S]: S→aAB A→bA|c B→dBe|de 输入串abbcde的最左推导如下： S ? aAB ? abAB ? abbAB ? abbcB ? abbcde 因此，输入串abbcde是该文法G1的句子。 下面从建立语法树来看句子的推导过程。为了自顶向下地构造输入串abbcde的语法树，首先按文法的开始符号产生根节点S，再根据产生式规则自顶向下地生长这棵语法树。语法树的建立过程如图所示。 自顶向下分析法也称面向目标的分析方法，在对输入串进行最左推导的过程中，在选择产生式时其实是一种试探方法，如果每一步选择产生式来匹配的时候都能够每选必中，则这种方法称为确定的分析方法；否则在选择产生式时面临多种可能，不知道选择哪一个产生式合适，就是不确定的分析方法。 因此自顶向下分析法又可分为确定的和不确定的两种，确定的分析方法对文法有一定的限制，但由于实现方法简单、直观，便于手工构造或自动生成语法分析器，因而仍是目前常用的方法之一。不确定的方法即带回溯的分析方法，这种方法实际上是一种穷举的试探方法，因此效率低，代价高，因而极少使用。 1. 不确定的自顶向下分析 不确定的自顶向下分析法的基本思想是，对任何输入串α试图用一切可能的办法，从文法的开始符号出发，自上而下的为它建立一棵语法树。如果试探成功，则α为相应文法的句子，否则α就不是文法句子。这种分析过程本质上是一种穷举试探过程，是反复使用不同规则，谋求匹配输入串的过程。因此这种匹配过程往往一次不能成功，需要重新匹配，称为回溯。 引起回溯的原因在于文法中关于某个非终结符的产生式有多个时，而根据面临的输入符无法唯一确定选择哪个产生式来匹配，从而引起回溯。 自顶向下分析法中存在的问题 回溯问题 左递归问题 回溯问题 回溯时需要恢复到出错点位置，删去曾经匹配过的符号，还包括一些语义处理。因此处理回溯是一项复杂的工作，在回溯时，要清除在回溯之前编译程序所做的大量记录工作，然后重新开始记录，这就降低了语法分析的效率。避免回溯是自顶向下语法分析中需要解决的问题之一。 回溯的具体表现 回溯具体表现为下列两种情况： 1. 由于相同左部的产生式的候选式的FIRST集交集不为空而引起回溯。 2.由于相同左部非终结符的候选式存在能推导出ε的产生式，且该非终结符的FOLLOW集中含有其它候选式的FIRST集的元素。 表现一示例 由于相同左部的产生式的候选式的FIRST集交集不为空而引起回溯： 【例4．6】设有文法G6[S]为： S→xAy A→**|* 串x*y的分析过程