自动机无歧义语法

如果语法不包含歧义，则语法可以是明确的，这意味着对于给定的输入字符串，语法不包含一个以上最左导数，一个以上最右导数或一个以上解析树。

要将歧义语法转换为歧义语法，我们将应用以下规则：

1.如果在生产规则中使用了左关联运算符（，-，*，/），则在生产规则中应用左递归。左递归表示右侧最左边的符号与左侧的非终结符相同。例如，

X → Xa

2.如果在生产规则中使用了权限关联运算符（^），则在生产规则中应用权限递归。右递归表示左侧最右边的符号与右侧的非终结符相同。例如，

X → aX

范例1：

考虑文法G如下：

S → AB | aaB
A → a | Aa
B → b

确定语法G是否模棱两可。如果G不明确，则构造与G等价的明确语法。

解：

让我们派生字符串“ aab”

由于有两个不同的解析树用于派生相同的字符串，因此给定的语法是模棱两可的。

明确的语法将是：

S → AB
A → Aa | a
B → b

范例2：

证明给定的语法是模棱两可的。另外，找到等效的明确语法。

S → ABA
A → aA | ε
B → bB | ε

解：

给定的语法是模棱两可的，因为我们可以为字符串aa派生两个不同的解析树。

明确的语法是：

S → aXY | bYZ | ε
Z → aZ | a
X → aXY | a | ε
Y → bYZ | b | ε

范例3：

证明给定的语法是模棱两可的。另外，找到等效的明确语法。

E → E + E
E → E * E
E → id

解：

让我们导出字符串“ id id * id”

由于有两个不同的解析树用于派生相同的字符串，因此给定的语法是模棱两可的。

明确的语法将是：

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

范例4：

检查给定的语法是否模棱两可。另外，找到等效的明确语法。

S → S + S
S → S * S
S → S ^ S
S → a

解：

给定的语法是模棱两可的，因为字符串aab的派生可以用以下字符串表示：

明确的语法将是：

S → S + A |
A → A * B | B
B → C ^ B | C
C → a