编译原理中算符优先分析的教学探讨

文章编号：1672-5913(2008)12-0080-03

摘要：算符优先分析法是编译原理课程中的重点和难点之一。本文针对相等、小于和大于优先关系，分析了优先归约关系的本质，提出了优先关系和最左素短语的分析模型。

关键词：编译原理；归约；优先关系；最左素短语

中图分类号：G642

文献标识码：B

1引言

计算机科学与技术学科强调4个方面的专业能力：计算思维能力，算法设计与分析能力，程序设计与实现能力，计算机系统的认知、分析、设计和运用能力。这也是计算机科学与其他学科的重要区别。相关的理论是计算机学科的基础。理论方面的知识是计算机的真正灵魂。理论是从计算机应用当中抽象出来的，目的在于使用抽象出来的理论去更好地指导实践[1]。

程序设计与实现能力在编译原理课程得到了具体的体现。编译原理是计算机学科中少有的从实践到理论，再从理论到实践的一门专业课程。编译技术不断进步，已经成为计算机科学中发展最迅速、最成熟的一个重要分支。编译技术集中体现了计算机科学发展的重要成果与精华[2]。

程序语言及其编译的研究在计算机科学中的始终处于非常重要的地位。编译程序构造的基本原理和技术蕴涵计算机科学解决问题的思路和抽象、解决问题的方法，也广泛应用于一般软件的设计和实现，其中的设计思想、算法、思维方式和技术都可能会对学生今后的发展产生比较大的影响。编译原理对计算机专业的学生的重要性与高等数学对理科学生的重要性几乎可以相提并论。同时，由于这门课程涉及其他多门课程的知识，使得它成为大学阶段中最难学的课程之一。

自下而上语法分析中的算符优先分析方法是是编译原理课程中的重点和难点之一。算符优先分析法使用终结符号之间的归约顺序进行语法结构的分析。在算术表达式中，有运算符号的优先级和结合性的规定，而算符优先分析法的实质就是仿效表达式的计算过程而设计的。其本质是对终结符之间的优先关系和最左素短语进行分析。

2终结符之间的优先关系

2.1算符优先文法

上下文无关文法G，如果没有形如

Pε

或

P...QR...

的产生式，则称G为算符文法。

算符优先分析方法考虑的是可能相邻的两个终结符之间的归约顺序问题(模仿算术表达式中相邻的两个运算符之间的计算的顺序问题)。

对算符文法G,a,bÎVT 优先关系定义为

(1) 若G有P...ab...或P...aQb...， 则a=b

(2) 若G有P...aQ...且QÞ+b… 或 QÞ+Rb...，则a

(3) 若G有P...Qb... 且QÞ+...a 或 QÞ+…aR，则a>b

若算符文法G的任何终结符a、b之间的优先关系至多只有=、>、

2.2优先关系模型

对于3种优先关系，分别建立对应的优先关系分析模型，自然引入构造优先关系表所需要的FIRSYVT和LASTVT集合。

(1) 相等优先关系

若文法G 有

P...ab...或P...aQb...

则a与b是一起归约为P的(当然，还要连同其他的一些符号)。因此，a与b的归约顺序是一致的(相等的)，即 a=b。相等优先关系模型如图1所示。

图1相等相等优先关系模型图

(2) 小于优先关系

若文法G有

P...aQ... 且Q Þ+b…或QÞ+Rb...

那么，需要先规约包含b的最左素短语为Q，然后才可能规约…aQ…为P。即a

图2小于优先关系模型图

而对于Q Þ+b…或QÞ+Rb... ，定义FIRSTVT集合为

FIRSTVT(Q)={a|QÞ+a… 或QÞ+Ra…，aÎVT,R ÎVN}

(3) 大于相等优先关系

若G中有

P...Qb...且QÞ+...a或QÞ+…aR

那么，需要先规约包含a的最左素短语为Q，然后才可能规约…Qb…为P。即a>b。大于优先关系模型如图3所示。

图3大于优先关系6模型图

对于QÞ+...a或QÞ+…aR，定义LASTVT集合为

LASTVT(Q)={a|QÞ+...a 或 QÞ+…aR，aÎVT,R ÎVN}

2.3特殊符号#的优先关系

对于算符优先分析方法，需要使用#作为待分析串的开始和结束标记，也需要定义#与其他终结符号的优先归约关系。

对文法进行改造，增加开始符号S′，增加产生式S′#S#。

使得开始标记#的优先归约关系小于FIRSTVT(S)的所有元素，即开始标记#的优先归约关系小于待分析串所有可能开始的字符；而LASTVT(S)的所有元素优先归约关系大于结束标记#，即待分析串所有可能结束的字符优先归约关系大于结束标记#。

开始和结束标记#的优先归约关系是最低的。

2.4其他相关问题

(1) 相同终结符的优先关系未必是=

(2) 有aa

(3)a、b之间未必一定有优先关系

(4) 两个终结符之间若没有优先关系，则表示两个终结符不可能相邻，这也是算符优先分析方法判断语法错误的依据。

3最左素短语的判断

句型的一般形式为：

#N1a1N2a2…NnanNn+1#

最左素短语是满足条件的最左子串NjajNj+1…NiaiNi+1

其中，条件为

aj-1

aj=aj+1=…=ai-1=ai

ai>ai+1

最左素短语的出现依据的是终结符号归约顺序的转折。最左素短语模型如图4所示。

图4最左素短语模型图

4总结

实际教学证明，此模型可有效地帮助学生理解优先关系的定义和算符优先分析方法的原理和技术。

参考文献

[1] 蒋宗礼，姜守旭.形式语言与自动机理论(第2版)[M].北京:清华大学出版社.2007.

[2] 龚天富.语言及编译(第2版)[M]. 北京:电子工业出版社,2003.

[3]Andrew W.Apple.现代编译器的Java实现[M].北京:电子工业出版社,2004.

[4]Dick Grune etc.Modern Compiler Design[M].JOHN WILEY&SONS,LTD,2002.

[5] 余胜泉，张建伟.信息时代的教学与实践[M].北京:高等教育出版社,2005.

“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文”