编译原理第四章复习.docVIP

语法分析和下推自动机 语法分析 语法分析就是识别一个符号串x∈V*，是否为某文法的一个句型（句子），因此是某个推导的构造过程。 在语言的实现过程中，把完成句型(句子)分析的程序称为语法分析程序或识别程序。 自上而下分析的概念 所谓自上而下分析法，就是从文法的开始符号出发，反复使用各种产生式，寻找“匹配”于输入符号串的推导序列。 自下而上分析的概念 所谓自下而上的方法则是从输入符号串开始，逐步进行“归约”，直至归约到文法的开始符号。 下推自动机PDA模型 见讲稿 1）PDA和FA的模型相比，多了一个下推栈。 2）PDA的动作由三个因素来决定：当前状态、读头所指向符号、下推栈栈顶符号。 3）一个输入串能被PDA所接受，仅当输入串读完，下推栈变空；或输入串读完，控制器到达某些终态。 自顶向下语法分析的基本思想 自顶向下的分析也称面向目标的分析方法，也就是从文法的开始符号出发企图推导出与输入的符号串完全相匹配的句子。 自顶向下的分析也可看成是以文法的开始符号为树根，采用最左推导逐步地为输入符号串自顶而下地构造一棵语法树。如果输入串中的每个终结符恰好自左向右地站在树的每个叶结点上（称语法树与输入串匹配），那么，该输入串就是文法的一个句子，否则不是。 自顶向下的分析方法又可分为确定的和不确定的两种。 带回溯的自上而下分析法的缺陷 1）如果文法存在左递归，语法分析会无限循环下去。 2）若产生式存在多个候选式，选择哪个进行推导完全是盲目的。 3）回溯会引起时间和空间的大量消耗。 4）如果被识别的语句是错的，算法无法指出错误的确切位置。 不带回溯的自上而下分析算法 在分析的每一步，根据当前的输入符号和下推自动机的当前状态即可正确决定下一步的动作的语法分析方法。 不带回溯的自上而下分析有两种：不带回溯的递归下降子程序法和预测分析法。 推导和分析树、推导树之间的关系 每一推导都对应一棵推导树;反之,一棵推导树可以对应多个推导. 推导树的叶子节点所对应的符号从左到右的连接得到的符号串是文法的一个句型. 如果叶子节点所对应的符号都是终结符,则得到文法的一个句子. 由推导树的任一子树的叶子节点所对应的符号串构成该文法的相对于那个子树根的一个短语. 推导树==某个串的推导(包括最左,最右推导) 推导树的根 == 文法的开始符号 推导树的内节点 ==文法的非终结符 推导树的叶子节点 == 文法的终结符或非终结符 推导树的子树 ==以该子树的根所对应的那个非终结符开始的推导 推导树的叶子节点从左到右的连接 ==该文法的一个句型 推导树的完全是终结符的叶子节点的连接 ==该文法的一个句子 推导树的子树的叶节点的连接==该推导树对应的那个句型相对于该子树根的短语. 推导树的直接子树的叶节点的连接==该推导树对应的那个句型相对于该子树根的直接短语. 推导树的最左直接子树的叶节点的连接==该推导树对应的那个句型相对于该子树根的最左直接短语(句柄). 左递归，直接左递归，间接左递归 左递归分为直接左递归和间接左递归 直接左递归： A (AB 间接左递归： P (AC , A(Pb 消除直接左递归 设有文法G=(VN, VT ,P,S)，其中产生式p为 A ( A (|( , ( (V+ ， ( ( V+ 且(不以A开头 将它转换为等价式: A (( A’ A’ ( ( A’|( 一般形式见讲稿。 消除间接左递归 见讲稿算法 产生回溯的原因 进行推导时，若产生式存在多个候选式，选择哪个候选式进行推导存在不确定性。 消除回溯的基本原则 对文法的任何非终结符，若能根据当前读头下的符号，准确的选择一个候选式进行推导，那么回溯就可以消除。 提取公共左因子 将某产生式A(((1| ((2|…. | ((n 改写为 A((A’ A’((1|(2|…. |(n 可通过反复提取左因子，就能把所有非终结符的所有候选首符集变为两两不相交。 递归下降子程序 对文法每个非终结符都有一个相应的过程用于分析该终结符所对应的产生式的右部的符号串；若遇到该符号串中的终结符号则进行匹配，若是非终结符则调用该非终结符对应的过程进行分析。由于右部的符号串可能含有与左部的非终结符相同的符号，因此该分析过程可能是递归的。 预测分析法 在PDA中加入预测分析之后，可以消除自上而下分析中出现回溯的现象。 预测分析程序用了一个预测分析表，它是预测分析程序分析时的主要依据。 预测分析表 预测分析表是一矩阵M[A,a]，其中行标A是非终结符，列标a是终结符或串结束符；矩阵元素M[A,a]是存放A的一个侯选式，指出当前栈顶符号为A且面临读入符号为a时应选的候选式；或者存放“出错标志”，指出A不该面临读入符号a。 预测分析程序算法描述 设栈顶符号为