编译原理讲义 (第五章 :语法分析 - 自底向上分析技术 ) 南京大学计算机系 赵建华 概论 从输入符号出发，试图把它归约成识别 符号。每一步都寻找特定得某个类型的 短语（一般是简单短语）进行归约。 在分析过程中，每次归约的都是最左边 的简单短语（或其它短语）。 从语法树的角度，以输入符号为树的末 端结点，试图向根结点方向往上构造语 法树。 基本问题 如何找出进行直接归约的简单短语？ 将找到的简单短语归约到哪个非终结符 号？ 讨论前提 和自顶向下技术同样，不考虑符号的具 体构成方式。 文法是压缩了的。 识别过程是从左到右，自底向上进行的 。一般都采用规范归约：每一步都是对 句柄进行归约（特例除外）。 基本方法 基本都采用移入 -归约方法。 使用一个栈来存放归约得到的符号。 在分析的过程中，识别程序不断地 移入 符号。移入的符号暂时存放在一个栈中 。一旦在栈中已经移入的（或者归约得 到的）符号串中包含了一个句柄时，将 这个句柄 归约 成为相应的非终结符号。 基本方法（续） 归约中的动作有 4类 移入：读入一个符号并把它归约入栈。 归约：当栈中的部分形成一个句柄（栈顶的 符号序列）时，对句
