算符文法

一個文法，如果它的任何產生式的右部都不含兩個相繼（並列）的非終結符，即不含如下形式的產生式：

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

其中P,Q,R,是非終結符。

稱該文法G為算符文法（operator grammar）,也稱OG文法。

....代表由終結符和非終結符組成的任意序列，包括空字。

基本介紹

• 中文名：算符文法
• 外文名：Operator grammar
• 別類1：套用
• 別類2：例子

套用

算符優先文法 （operator precedence grammar）簡稱 OPG文法 。

·算符優先關係的定義：文法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)

因為+ *之間同時存在兩種優先關係

所以不是算符優先文法。