什么是OPG?
OPG代表运算符优先语法。具有后者属性的语法称为运算符优先语法。它是ε-freeOperatorGrammar,其中优先关系<.,=。和.>是不相交的,即如果a.>b存在,那么b.>a将不存在。
Example1-验证以下语法是否是运算符语法。
E→EAE|(E)|id
A→+|-|*
解决方案
不,它不是运算符Grammar,因为它不满足运算符Grammar的属性2。
因为它在生产E→EAE的RHS上包含两个相邻的非终结符。
我们可以通过将A的值代入
E→EAE。
E→E+E|E−E|E∗E|(E)|ID。
Example2-检查以下语法是否为OPG
E→E+E|E∗E|(E)|id
解决方案
比较生产E→E+E的RHS与αaAβ
&进一步,A→γb$与E→E+E进行比较。
所以,应用规则(2),我们得到一个<.b,这意味着。
+<。+………………………………………….(1)
比较E→E+E与αAbβ
&进一步A→γa$与E→E+E进行比较。
所以,应用规则(3),我们得到a.>b这意味着
+。>+……………………………………(2)
从关系(1),我们有+<。+
从关系(2),我们有+。>+
∴优先关系是不明确的并且不是唯一的。因此,给定的运算符语法不是OPG。
Example3-检查以下语法是否为OPG
E→E+T|T
T→T∗F|F
F→(E)|id
解决方案
比较E+T与αaAβ。
∴a=+,A=T&进一步比较A→γb$与T→T*F
∴b=*
所以,应用规则(2),我们得到一个<.b,这意味着。
+<。+………………………………………….(1)
代ê→T的在生产ë→E+牛逼,我们得到
E→T+T
比较T+T与αAbβ
∴b=+,A=T
进一步比较A→γa$与T→T*F。
所以,应用规则(3),我们得到a.>b这意味着
+。>+……………………………………(2)
从关系(1),我们有+<。+
从关系(2),我们有+。>+
因此,这两种关系都表明乘法运算符(*)比加法运算符(+)具有更高的优先级。
因此,没有歧义。
因此,语法是OPG。