编译原理4章4详解.ppt

第四章 作业 P81 1、2、3 * 第四章 自顶向下语法分析方法 4.1语法分析器的功能： 语法分析是整个编译过程的核心部分，它完成的任务是：按照文法从源程序单词串(符号串)中识别各类语法成分，判断所给出的单词串是否是给定文法的正确句子，并为语义分析和代码生成做准备。 语法分析器 词法分析器 编译程序 后续部分 符号表 源程序 单词符号 取下一 单词符号 语法分析树 4.2 不确定的自顶向下分析 一、算法思想： 对于任一输入符号串，试用一切可能的办法从树根结点出发根据文法自上向下的为输入串建立一棵语法树。 二、举例：设有文法G[S]:(1) S?cAd(2) A?ab|a 给定输入串w=cad,试给出分析过程 S cad (1)据初始符号产生根结点S, 并让读指针指向输入串首符号c S cad (2)据S的产生式发展语法树 c A d S cad (3)用S的子结点(cAd)匹配输入串，首符号匹配，读指针向下移动 c A d S cad (4)A有两个选择，选择第一个进行试探，发展语法树。 c A d a b c S cad (5)子树A的最左子结点与指针所指符号匹配，指针移动，与A的第二个结点匹配，失败！回溯。 A d a b S cad (6)回溯要把A的第一个选择所生长的子树销掉，并把分析指针恢复到进入A时的值。 c A d S cad (7)用A的第二个选择生成语法树 c A d a S cad (8)A的子结点与当前符号匹配，指针移动，S的第三结点d进入工作，匹配成功 c A d a 三、对应最左推导： 以上为输入符号串建立语法树的过程，实际上也是一个建立最左推导序列的过程，显然有：S?cAd?cad，之所以使用最左推导，是因为我们对输入串是从左到右扫描的，只有使用最左推导，才能按扫描顺序去匹配输入串。 四、存在问题：p68 1.左递归问题：自顶向下分析方法，在匹配过程中，假若用到非终结符号U去匹配输入串，而U为左递归的(例如：U?U…)，那么为了用它的右部匹配输入串，又要用到非终结符号U，循环往复，没有终止。若文法存在间接递归，也有相同问题发生。 2.回溯问题：对某个非终结符，当有多条规则时，需采用逐个选择的方法，若不能匹配需要回溯，代价高，效率低。 4.3 确定的自顶向下分析思想 一、算法思想： 对于任一输入符号串，从文法的识别符号出发，根据当前的输入符号，唯一的确定一个产生式，用产生式的右部的符号串替代相应的非终结符往下推导，或构造一棵语法树。若能推导出输入串或构造语法树成功则输入串是句子，否则不是。 二、举例：(1)文法G[S]:S?pA |qB A?cAd|a 输入串w=pccadd S p A A c d A c d a 对应最左推导： S?pA?pcAd?pccAdd?pccadd 文法特点： (1)每个产生式的右部都由终结符号开始；(2)两个产生式若左部相同，则其右部以不同的终结符号开始；(3)无空产生式U?? 方法：根据产生式右部的首符号选择产生式。 (2)文法G[S]:S?Ap | Bq A?cA | aB?dB | b 输入串w=ccap S A p c A c A a 对应最左推导： S?Ap?cAp?ccAp?ccap 文法特点： (1)每个产生式的右部并非都由终结符号开始；(2)两个产生式若左部相同，则其右部以不同的终结符号或非终结符号开始，且首符号集不相交；(3)无空产生式U?? 方法：根据产生式右部的首符号选择产生式。 (3)文法G[S]:S?aA | d A?bAS | ?输入串w=abd S a A A b S ? d 对应最左推导： S?aA?abAS?abS?abd 文法特点： (1)有空产生式U??；(2)两个产生式若左部相同，则其对应的首符号集不相交并且与其后继符号集也不相交； 方法：根据产生式的可选集选择产生式。 例题(1)(2)(3)的共同特点： 1)没有左递归2)在每一步推导中，都可以根 据输入串的当前符号唯一的确 定一个产生式去匹配。 4.3.2 几个重要集合 一、首符号集： 设有文法G=(VT, VN, S, P)是上下文无关文法，则符号串x的首符号集合定义为： First(x)={a |x ? * ay, a?VT, y?V*}， ? * 若x ?, 则??First(x). First(x)={a |x ? * a…, a?VT