算符优先文法简析和其基于Java的实现

摘 要：算符優先文法并不是一种规范的规约，但是它文法结构简单，易于实现;其终结符之间按照规约的先后关系排列优先级，这一特点很有利于初学者对于从下到上的语法分析思想的理解。

本文首先介绍算符优先分析相关的基本概念，包括优先关系表;之后将给出使用Java语言实现这一语法分析方法的示例代码段。

关键词：编译原理;从下到上分析方法;算符优先分析;优先关系表

一、相关知识储备

（一）基本概念

优先关系

最基本的优先关系是四则运算中的算符优先关系，乘号的优先级大于加和减;左括号的优先级大于乘号，等等。算符优先分析中的优先级关系并不是一成不变的，而是对位置敏感的。同样是加号和乘号，表达式中，加号出现在乘号的左边和右边的优先级可能会不同;而且，根据语法树中规约的先后顺序，在同一个表达式中，如果句型的规约顺序发生变化，相同位置关系下的两个终结符的优先关系也会变化。基本的算符优先关系有三种：优先关系等于、小于、大于。

算符文法

算符文法规定，文法的任何一个产生式的右部都不含两个相继（并列）的非终结符，也就是说每两个非终结符之间必含有至少一个终结符。这一规定是算符优先分析的精妙之处，极大地简化了文法的实现难度。

算符优先文法

成为算符优先文法有四个条件：

1.是算符文法;2.不含有ε产生式;3.对于任何一对终结符都有三种优先关系之一;

4.任何一对终结符最多只满足三种优先关系之一。

（二）优先关系表

优先关系表是使用代码实现算符优先分析的关键，该表使得终结符之间的优先关系得以存放在一个二维数组中。制作优先关系表之前，首先要做出每个非终结符的FIRST-VT集和LAST-VT集合。这两个集合都是根据文法的产生式得出的，具体得出方式在此不再详述。VT代表的是终结符，FIRST-VT指的是在各个非终结符的产生式中首次出现的终结符;相对应的，LAST-VT是指各个非终结符的产生式中最后出现的终结符。有了这两个集合之后，就对此时空白的优先关系表按行和按列填满。（以下内容中的小写字母代表终结符，大写字母代表非终结符）。

以下文法为例：

对于形如...aP...的产生式，是出现在左边的a和P的FIRSTVT（P）集作比较（a

对于形如...Pa...的产生式，是出现在右边的a和LASTVT（P）作比较（LASTVT（P）>a），此时要关注终结符a占据的列，是对优先关系表按列填满。

需要注意的是，不管是按行填满还是按列填满，表格中的优先关系大小永远表示的是该格所在行的终结符和该格所在列的终结符的优先关系。

最终示例优先关系表为：

二、算法实现

（一）算法思想

算符优先分析终究是一种自下而上的规约方法。在代码实现时，关键是使输入串和分析栈中的字符不断地进行优先级的比较。分析栈存放的是从输入串中读入的字符和规约的结果。大致过程是：

1.当分析栈中的字符优先级比输入串当前待输入的字符低或等于时，入栈一个字符;

2.重复执行1，直至分析栈栈顶的终结符优先级比栈外输入串的首字符高;此时由栈顶向下寻找并读取经过的字符，直到读到的字符的优先级比栈顶元素低，那么这时，从栈顶到该字符之前的字符，这一串就被称为“最左素短语”（含有且仅有一个终结符），是可以被规约的字符串，将这一串字符出栈，将规约的结果进栈;

3.重复步骤1和2，直至输入串所有字符处理完毕。

（二）示例代码段

寻找可规约串与移进字符

规约方法

参考文献

[1] 陈火旺，等.程序设计语言编译原理（第3版）[M].北京：国防工业出版社，2006： 89-98

作者简介：刘杨（1999——）男，汉族，河南信阳人，单位：河南大学计算机与信息工程学院，本科，软件工程专业，软件工程：