朱朝霞

摘要：语法分析是编译程序的核心部分，其任务是检查词法分析器输出的单词序列是否是源语言中的句子。该文以编译程序自底向上语法分析为主线，探讨自底向上语法分析归约中的句柄求解问题，希望对编译原理的课程教学有启发作用。

关键词：编译器； 自底向上语法分析；句柄；栈；归约

中图分类号：TP314.51 文献标识码：A 文章编号：1009-3044（2016）33-0110-02

语法分析是编译程序的核心部分，其任务是检查词法分析器输出的单词序列是否是源语言中的句子，亦即是否符合源语言的语法规则。完成句型的分析，主要有两种方式：一种是使用推导方式推导出句子，即自顶向下的语法分析方法；另一种是利用归约方式识别句子，即自底向上的语法分析方法。本文以编译程序自底向上语法分析为主线，探讨自底向上语法分析归约中的句柄求解问题，希望对编译原理的课程教学有启发作用。

1 自底向上语法分析

自底向上语法分析，也称移进-归约分析，指从给定的输入符号串w出发，试图将其归约为文法的开始符号。其实现思想是对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄或可归约串时，就用该产生式的左部非终结符代替相应右部的文法符号串，重复这一过程直到归约到栈中只剩下文法的开始符号时为分析成功。

在自底向上的分析过程中，最关键的问题是句柄的识别问题，即每次规约时按当前句型的句柄进行规约。……