编译原理：算符优先文法

算符优先文法首先必须是算符文法，算符文法将终结符号作为文法的算符。

定义5.3 对于文法G，如果其任一产生式的右部都不含两个相继或并列的非终结符，即不含如下形式的产生式

P→…QR…

则称文法G为算符文法。

因此，算符文法句型的一般形式为

#N1a1N2a2…Nnan Nn+1#

其中，每个ai都是终结符，Ni是非终结符或ε。也就是说，算符文法的句型中包含多个终结符，任何两个终结符之间至多只有一个非终结符，保证了算符的相邻性。注意，算符文法句型中的相邻算符不一定是紧紧挨在一起的两个算符，也包括相隔一个非终结符的一对算符。

回顾4.2节，设计算术表达式文法时，为了去除文法的二义性而将算符依据优先级别进行分组，使得优先级别低的算符更接近语法分析树的根结点。换句话说，确保优先级别高的算符先被归约，而构成一个语法单位。因此，文法的产生式实际上包含了相邻算符的归约顺序，即算符的优先级别。为了形式化描述相邻算符的级别关系，引入终结符之间的三种优先关系。

定义5.4 假定G是一个不含ε产生式的算符文法。G的终结符号对a和b的优先关系包括如下三种形式。

(1)ab

当且仅当文法G中含有形如P→…ab…或P→…aQb…的产生式(www.xing528.com)

(2)ab

当且仅当G中含有形如P→…aR…的产生式，而且Rb…或RQb…

(3)ab

当且仅当G中含有形如P→…Rb…的产生式，而且R…a或R…aQ

注意，这三种优先关系是不对称的。例如，表达式i1+i2-i3中有+·＞-，但是在表达式i1-i2+i3中又有-+。

为了构造确定的算符优先分析，需要保证在分析的任意时刻，都能够依据算符之间的优先关系准确地决定应该采取移进还是归约动作，以及确定可归约串。

定义5.5 如果算符文法G中的任意一对终结符a和b，至多只满足下述三种关系之一

算符优先文法

则称G是一个算符优先文法。