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