运算符优先级解析

运算符优先级语法是种移位减少解析方法。它适用于一小类运算符语法。

如果语法具有两个属性, 则称其为运算符优先级语法：

• 没有R.H.S.任何生产中都有一个∈。
• 没有两个非终端相邻。

运算符优先级只能在语法的终端之间建立。它忽略非终结符。

存在三个运算符优先级关系

a⋗b表示终端“ a”的优先级高于终端“ b”的优先级。

a⋖b表示终端“ a”的优先级低于终端“ b”的优先级。

a≐b表示终端“ a”和“ b”都具有相同的优先级。

优先级表：

解析动作

• 在给定输入字符串的两端, 都添加$符号。
• 现在从左到右扫描输入字符串, 直到遇到⋗。
• 在所有相等优先级上向左扫描, 直到遇到第一个最左⋖。
• 最左边的⋖和最右边的between之间的所有内容都是手柄。
• $ on $表示解析成功。

例

语法：

E → E+T/T
T → T*F/F
F → id

给定字符串：

w = id + id * id

让我们为它考虑一个解析树, 如下所示：

在上述树的基础上, 我们可以设计以下算子优先级表：

现在, 让我们借助上面的优先级表来处理字符串：