算符文法

编辑：见识网互动百科时间：2019-11-24 19:34:44

本词条缺少信息栏、名片图，补充相关内容使词条更完整，还能快速升级，赶紧来编辑吧！

一个文法，如果它的任何产生式的右部都不含两个相继（并列）的非终结符，即不含如下形式的产生式：

P-->....QR....,

其中P,Q,R,是非终结符。

称该文法G为算符文法（operator grammar）,也称OG文法。

....代表由终结符和非终结符组成的任意序列，包括空字。

算符文法应用

算符优先文法（operation priority grammar）简称 OPG文法 ^[1] 。

·算符优先关系的定义：文法G是一个不含e-产生式的算符文法，定义终结符a、b之间的优先关系

①a = b,G中有P→...ab...或P→...aQb...(在同一产生式中)

　　②a < b,G中有P→...aR...的产生式,且R=>b...或R=>Qb...(注意ab相邻)

　　③a > b,G中有P→...Rb...的产生式,且R=>...a或R=>...aQ(注意ab相邻)

E→E+E | E*E | (E) | i 证明不是算符优先文法。

因为：E→E+E，E→E*E 则有 + < *(由规则2)

又因为：E→E*E, E→E+E 则有+ > *(由规则3)

因为+ *之间同时存在两种优先关系

所以不是算符优先文法。

参考资料