什么是OPG?

OPG 代表运算符优先语法。具有后者属性的语法称为运算符优先语法。它是ε -free Operator Grammar,其中优先关系<., =。和 .> 是不相交的,即如果 a . > b 存在,那么 b .> a 将不存在。

Example1 - 验证以下语法是否是运算符语法。

E → EAE |(E)|id

A → +| - | *

解决方案

不,它不是运算符 Grammar,因为它不满足运算符 Grammar 的属性 2。

因为它在生产 E → E A E 的RHS 上包含两个相邻的非终结符。

我们可以通过将 A 的值代入

E → EA E。

E → E + E |E − E |E ∗ E |(E) | ID。

Example2 - 检查以下语法是否为 OPG

E → E + E|E ∗ E|(E)|id

解决方案

比较生产 E → E + E 的 RHS 与 α a A β

Α一种Aβ
E+Eε

& 进一步,A → γ b $与 E → E + E 进行比较。

A →Γb$
E →+

所以,应用规则(2),我们得到一个 <.b ,这意味着。

+ <。+………………………………………….(1)

比较 E → E + E 与 α A b β

ΑΑbβ
E+

& 进一步 A → γ a $与 E → E + E 进行比较。

A →Γa$
E →+

所以,应用规则(3),我们得到 a .> b 这意味着

+ 。> +……………………………………(2)

从关系(1),我们有 + <。+

从关系(2),我们有 + 。> +

∴ 优先关系是不明确的并且不是唯一的。因此,给定的运算符语法不是 OPG。

Example3 - 检查以下语法是否为 OPG

E → E + T|T

T → T ∗ F|F

F → (E)|id

解决方案

比较 E + T 与 α a A β。

Α一种Aβ
E+Tε

∴ a = +, A = T & 进一步比较 A → γ b $与 T → T * F

A →γb$
T →*F

∴ b = *

所以,应用规则(2),我们得到一个 <.b ,这意味着。

+ <。+………………………………………….(1)

ê→T的在生产ë→E +牛逼,我们得到

E → T + T

比较T + Tα A b β

Α一种bβ
Ε+

∴ b = +, A = T

进一步比较A → γ a $与 T → T * F。

Α →γa$
Ε →*F

所以,应用规则(3),我们得到 a .> b 这意味着

+ 。> +……………………………………(2)

从关系(1),我们有 + <。+

从关系(2),我们有 + 。> +

因此,这两种关系都表明乘法运算符 (*) 比加法运算符 (+) 具有更高的优先级。

因此,没有歧义。

因此,语法是 OPG。