《编译原理》第章自下而上语法分析.pdf

编译原理 武汉大学计算机学院 编译原理课程组 自上而下语法分析 · 基本思想 · 存在的问题 · 解决方法 消除左递归 FIRST集、FOLLOW集 · LL(1)文法 · LL(1)方法 LL(1)分析表的构造 · 递归子程序法 递归子程序的构造 6.1 自下而上语法分析 1． 自下而上语法分析的基本思想 从输入的符号串开始，利用文法的产生式步步向上归约，试图 归约到文法的识别符号。如果从语法树的角度看，自下而上分析的 过程是以输入符号串作为末端结点符号串，向着根结点的方向往上 构造语法树，使识别符号正好是该语法树的根结点。 相应于高级语言的编译过程，自下而上语法分析就是从该高 级语言文法的源程序或与其等价的单词串出发，试图归约得到该 文法的开始符号——程序。 6.1 自下而上语法分析 2．基本实现技术 ——移进-归约法 引进一个后进先出的栈来存放符号，按照扫描顺序把当前输入符 号下推入栈中(移进) ，然后查看栈顶的符号串是否可以被归约。 栈 # X X X …X X …X a a ……a # 输入串 1 2 3 i i+1 j k k+1 m x 当前句型 6.1 自下而上语法分析 栈 # X X X …X X …X a a ……a # 输入串 1 2 3 i i+1 j k k+1 m x 当前句型 移进——读入下一个输入符号并把它下推进栈。 归约——把栈顶符号串替换为相应的非终结符号。 接受—— 当栈顶除#外仅有识别符号，输入也到#时，结束工作。 报错—— 当识别出错误时，调用出错处理子程序处理或停止。 栈S 输入串 栈S 输入串 # a a ……a # #Z # 1 2 n OK! 6.1 自下而上语法分析 3. 自下而上语法分析遇到的基本问题 例如，对文法G[S]： S →aAcBe A →b A →Ab B →d 分析符号串abbcde。 6.2 短语和句柄 1．短语、直接短语与句柄 设有文法G[Z] ，w=xuy是它的一个句型，如果有 * + Z ⇒xUy 且 U ⇒u 则称句型xuy 中的子串u为句型xuy(相对于非终结符号U)的短语。 句型xuy 相对于非终结符号U + 特别地，如果前述条件中U ⇒u为 U⇒u 则称u为句型xuy的直接（简单）短语。 句型的最左直接（简单）短语称为句柄。 6.2 短语和句柄