论文部分内容阅读
摘要：语法分析是编译程序的核心部分，其任务是检查词法分析器输出的单词序列是否是源语言中的句子。该文以编译程序自底向上语法分析为主线，探讨自底向上语法分析归约中的句柄求解问题，希望对编译原理的课程教学有启发作用。
关键词：编译器； 自底向上语法分析；句柄；栈；归约
中图分类号：TP314.51 文献标识码：A 文章编号：1009-3044（2016）33-0110-02
语法分析是编译程序的核心部分，其任务是检查词法分析器输出的单词序列是否是源语言中的句子，亦即是否符合源语言的语法规则。完成句型的分析，主要有两种方式：一种是使用推导方式推导出句子，即自顶向下的语法分析方法；另一种是利用归约方式识别句子，即自底向上的语法分析方法。本文以编译程序自底向上语法分析为主线，探讨自底向上语法分析归约中的句柄求解问题，希望对编译原理的课程教学有启发作用。
1 自底向上语法分析
自底向上语法分析，也称移进-归约分析，指从给定的输入符号串w出发，试图将其归约为文法的开始符号。其实现思想是对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄或可归约串时，就用该产生式的左部非终结符代替相应右部的文法符号串，重复这一过程直到归约到栈中只剩下文法的开始符号时为分析成功。
在自底向上的分析过程中，最关键的问题是句柄的识别问题，即每次规约时按当前句型的句柄进行规约。自底向上语法分析方法主要有优先分析法和LR分析法。下面以两种分析法为例求解句型的句柄及可归约串问题。
2 优先分析法
优先分析法可分为简单优先分析法和算符优先分析法。简单优先分析法的基本思想是对一个文法按一定原则求出该文法所有符号即包括终结符和非终结符之间的优先关系，按照这种优先关系确定归约过程的句柄，其归约过程是一种规范归约。
算符优先分析的基本思想是只规定算符之间的优先关系，不考虑非终结符之间的优先关系，在归约过程中只要找到可归约串就归约，并不考虑归约到哪个非终结符名，其归约过程不是归范归约。
2.1 简单优先分析法中的句柄
简单优先分析法的分析算法：
先根据已知优先文法构造相应优先关系矩阵，并将文法的产生式保存，设置符号栈S：
1）将输入符号串a1 a2 an #依次逐个存入符号栈S中，直到遇到栈顶符号ai的优先性大于下一个待输入符号aj时，停止进栈；
2）以栈顶当前符号ai为句柄尾，由此向左在栈中找句柄的头符号ak，即找到ak-1的优先性小于ak为止；
3）由句柄ak ai在文法的产生式中查找右部为ak ai的产生式，若找到则用相应左部代替句柄，若找不到则为出错，此时可断定输入串不是该文法的句子；
4）重复上述三步直到归约完输入符号串，栈中只剩文法的开始符号为止。
对符号串#b（aa）b#的移进-归约分析过程中，根据算法及优先关系表求得归约的句柄依次分别为：a、Aa）、（B、bAb。
简单优先分析法中句柄的求解过程是每次察看句型中相邻的两个符号，通过两个符号的优先关系判定出前一个符号是句柄的尾。然后，再反向找出句柄的头。如下图所示：
图中U即为移进-归约分析过程中当前句型的句柄。
2.2 算符优先分析法中的句柄
自底向上的算符优先分析法，也称自左向右归约。由于算符优先分析法不考虑非终结符之间的优先关系，在归约过程中只要找到可归约串就归约，并不考虑归约到哪个非终结符名，因此算符优先分析过程中的句柄是一个最左素短语的求解过程。对一文法来说，需先求得句型的所有素短语，处于句型最左边的素短语即算符优先分析的句柄。一个算符优先文法的最左素短语形式为NiaiNi 1ai 1…ajNj 1，符号的优先关系应满足：ai-1aj 1。
使用算符优先分析法的规约过程与规范归约是不同的，以文法G[E]为例，
（1） E→E T （2） E→T （3） T→T*F （4） T→F （5） F→PF|P （6） P→（E） （7） P→i
如果对输入串#i i#进行规范归约分析过程需要12步，然而使用算符优先归约时只需要7步，分析过程中形成的归约串只有三个：i、i、E E。原因是算符优先分析中去掉了单非终结符归约，其归约过程是一种快速归约过程。
3 LR分析法
LR分析法是一种能根据当前分析栈中的符号串和向右顺序查看输入串的k个（k≥0）符号就可以唯一地确定分析器的动作是移进还是归约和用哪个产生式归约，因而也就能唯一地确定句柄。LR分析法是规范推导的逆过程，是一种规范归约。
LR分析过程：将文法的终结符和非终结符都看成有穷自动机的输入符号，每次把一个符号进栈看成已识别过了该符号，同时状态进行转换，当识别到可归前缀时，相当于在栈中形成句柄，认为达到了识别句柄的终态。
LR分析器的关键部分是分析表的构造。LR分析表是LR分析器的核心部分，是总控程序的依据。一张LR分析表包括两部分：一部分是“动作”（ACTION）表，表示当前状态下所面临輸入符应做的动作是移进、归约、接受或出错。另一部分是“状态转换”（GOTO）表，表示在当前状态下面临文法的输入符号时应转向的下一个状态。
对一个文法构造了它的LR分析表后就可以在LR分析器的总控程序控制下对输入串进行分析，即根据输入串的当前符号和分析栈的栈顶状态查找分析表应采取的动作，对状态栈和符号栈进行相应的操作即移进、归约、接受或报错。
LR分析法中的归约过程：
当在栈顶形成句柄为β时，则用β归约为相应的非终结符A，即当文法中有A→β的产生式，而β的长度为γ，则从状态栈和文法符号栈中自顶向下去掉γ个符号。并把A移入文法符号栈内，再把满足Sj=GOTO[Sm-γ，A]的状态移进状态栈，当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是‘#’，则为分析成功。
对符号串#baab#分析过程中，归约过程中求得的句柄依次为：ε、ε、aBa、bAb、AB。
4 结束语
在编译程序自底向上的语法分析过程中，最关键的问题是句柄的识别问题。简单优先分析法其归约过程是一种规范归约，准确、归范、但分析效率较低，实际使用价值不大。算符优先分析法其归约过程不是归范归约，但分析速度快、简单、直观，特别适于用手工方式来实现，很多编译程序都使用算符优先法分析表达式。LR分析法分析速度快，能准确、及时地指出输入串的语法错误及出错位置，比自底向上优先分析法对文法的限制要少得多，对大多数用无二义性的上下文无关文法描述的语言都可以用LR分析器予以识别。
参考文献：
[1] 蒋宗礼，姜守旭. 编译原理[M]. 北京：高等教育出版社， 2010.
[2] 张素琴， 吕映芝. 编译原理[M]. 北京：清华大学出版社， 2005.
[3] 张昱，陈意云. 编译原理与技术[M]. 北京：高等教育出版社， 2010.
[4] 陈火旺， 蒋伟进. 编译原理[M]. 长沙：中南大学出版社， 2005.
[5] 黄贤英，王柯柯. 编译原理及实践教程[M]. 北京：清华大学出版社， 2008.
关键词：编译器； 自底向上语法分析；句柄；栈；归约
中图分类号：TP314.51 文献标识码：A 文章编号：1009-3044（2016）33-0110-02
语法分析是编译程序的核心部分，其任务是检查词法分析器输出的单词序列是否是源语言中的句子，亦即是否符合源语言的语法规则。完成句型的分析，主要有两种方式：一种是使用推导方式推导出句子，即自顶向下的语法分析方法；另一种是利用归约方式识别句子，即自底向上的语法分析方法。本文以编译程序自底向上语法分析为主线，探讨自底向上语法分析归约中的句柄求解问题，希望对编译原理的课程教学有启发作用。
1 自底向上语法分析
自底向上语法分析，也称移进-归约分析，指从给定的输入符号串w出发，试图将其归约为文法的开始符号。其实现思想是对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄或可归约串时，就用该产生式的左部非终结符代替相应右部的文法符号串，重复这一过程直到归约到栈中只剩下文法的开始符号时为分析成功。
在自底向上的分析过程中，最关键的问题是句柄的识别问题，即每次规约时按当前句型的句柄进行规约。自底向上语法分析方法主要有优先分析法和LR分析法。下面以两种分析法为例求解句型的句柄及可归约串问题。
2 优先分析法
优先分析法可分为简单优先分析法和算符优先分析法。简单优先分析法的基本思想是对一个文法按一定原则求出该文法所有符号即包括终结符和非终结符之间的优先关系，按照这种优先关系确定归约过程的句柄，其归约过程是一种规范归约。
算符优先分析的基本思想是只规定算符之间的优先关系，不考虑非终结符之间的优先关系，在归约过程中只要找到可归约串就归约，并不考虑归约到哪个非终结符名，其归约过程不是归范归约。
2.1 简单优先分析法中的句柄
简单优先分析法的分析算法：
先根据已知优先文法构造相应优先关系矩阵，并将文法的产生式保存，设置符号栈S：
1）将输入符号串a1 a2 an #依次逐个存入符号栈S中，直到遇到栈顶符号ai的优先性大于下一个待输入符号aj时，停止进栈；
2）以栈顶当前符号ai为句柄尾，由此向左在栈中找句柄的头符号ak，即找到ak-1的优先性小于ak为止；
3）由句柄ak ai在文法的产生式中查找右部为ak ai的产生式，若找到则用相应左部代替句柄，若找不到则为出错，此时可断定输入串不是该文法的句子；
4）重复上述三步直到归约完输入符号串，栈中只剩文法的开始符号为止。
对符号串#b（aa）b#的移进-归约分析过程中，根据算法及优先关系表求得归约的句柄依次分别为：a、Aa）、（B、bAb。
简单优先分析法中句柄的求解过程是每次察看句型中相邻的两个符号，通过两个符号的优先关系判定出前一个符号是句柄的尾。然后，再反向找出句柄的头。如下图所示：
图中U即为移进-归约分析过程中当前句型的句柄。
2.2 算符优先分析法中的句柄
自底向上的算符优先分析法，也称自左向右归约。由于算符优先分析法不考虑非终结符之间的优先关系，在归约过程中只要找到可归约串就归约，并不考虑归约到哪个非终结符名，因此算符优先分析过程中的句柄是一个最左素短语的求解过程。对一文法来说，需先求得句型的所有素短语，处于句型最左边的素短语即算符优先分析的句柄。一个算符优先文法的最左素短语形式为NiaiNi 1ai 1…ajNj 1，符号的优先关系应满足：ai-1
使用算符优先分析法的规约过程与规范归约是不同的，以文法G[E]为例，
（1） E→E T （2） E→T （3） T→T*F （4） T→F （5） F→PF|P （6） P→（E） （7） P→i
如果对输入串#i i#进行规范归约分析过程需要12步，然而使用算符优先归约时只需要7步，分析过程中形成的归约串只有三个：i、i、E E。原因是算符优先分析中去掉了单非终结符归约，其归约过程是一种快速归约过程。
3 LR分析法
LR分析法是一种能根据当前分析栈中的符号串和向右顺序查看输入串的k个（k≥0）符号就可以唯一地确定分析器的动作是移进还是归约和用哪个产生式归约，因而也就能唯一地确定句柄。LR分析法是规范推导的逆过程，是一种规范归约。
LR分析过程：将文法的终结符和非终结符都看成有穷自动机的输入符号，每次把一个符号进栈看成已识别过了该符号，同时状态进行转换，当识别到可归前缀时，相当于在栈中形成句柄，认为达到了识别句柄的终态。
LR分析器的关键部分是分析表的构造。LR分析表是LR分析器的核心部分，是总控程序的依据。一张LR分析表包括两部分：一部分是“动作”（ACTION）表，表示当前状态下所面临輸入符应做的动作是移进、归约、接受或出错。另一部分是“状态转换”（GOTO）表，表示在当前状态下面临文法的输入符号时应转向的下一个状态。
对一个文法构造了它的LR分析表后就可以在LR分析器的总控程序控制下对输入串进行分析，即根据输入串的当前符号和分析栈的栈顶状态查找分析表应采取的动作，对状态栈和符号栈进行相应的操作即移进、归约、接受或报错。
LR分析法中的归约过程：
当在栈顶形成句柄为β时，则用β归约为相应的非终结符A，即当文法中有A→β的产生式，而β的长度为γ，则从状态栈和文法符号栈中自顶向下去掉γ个符号。并把A移入文法符号栈内，再把满足Sj=GOTO[Sm-γ，A]的状态移进状态栈，当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是‘#’，则为分析成功。
对符号串#baab#分析过程中，归约过程中求得的句柄依次为：ε、ε、aBa、bAb、AB。
4 结束语
在编译程序自底向上的语法分析过程中，最关键的问题是句柄的识别问题。简单优先分析法其归约过程是一种规范归约，准确、归范、但分析效率较低，实际使用价值不大。算符优先分析法其归约过程不是归范归约，但分析速度快、简单、直观，特别适于用手工方式来实现，很多编译程序都使用算符优先法分析表达式。LR分析法分析速度快，能准确、及时地指出输入串的语法错误及出错位置，比自底向上优先分析法对文法的限制要少得多，对大多数用无二义性的上下文无关文法描述的语言都可以用LR分析器予以识别。
参考文献：
[1] 蒋宗礼，姜守旭. 编译原理[M]. 北京：高等教育出版社， 2010.
[2] 张素琴， 吕映芝. 编译原理[M]. 北京：清华大学出版社， 2005.
[3] 张昱，陈意云. 编译原理与技术[M]. 北京：高等教育出版社， 2010.
[4] 陈火旺， 蒋伟进. 编译原理[M]. 长沙：中南大学出版社， 2005.
[5] 黄贤英，王柯柯. 编译原理及实践教程[M]. 北京：清华大学出版社， 2008.