显示语法。 S->aS|aSbS|Ɛ 是有歧义的,求无歧义语法

问题描述 投票:0回答:3

我有这个问题:

显示语法。 S->aS|aSbS|Ɛ 是有歧义的,求无歧义语法。

我尝试从互联网上尽我所能地学习有关歧义语法的知识,但大多数人都尝试使用相同的旧示例,我觉得它们没有正确传达将歧义语法转换为明确语法的方法。我知道没有一种确定的方法可以做到这一点。我尝试了各种尝试方法,这就是我得到的:

首先证明给定的语法是不明确的:尝试从上面的语法中得到 aab

你会发现至少有两种方法可以解决这个问题。

所以我想了想,想出了一个使用点击和试用的解决方案。

S -> aT|ε T -> aTbT | T -> aTbT | ε

我没有正确性证明,也没有太多扎实的想法来解释为什么我想出这个,但我至少无法使用这个新语法为 aab 制作两个不同的解析树。

这个答案正确吗?如果有人告诉我这是如何实际完成的及其背后的基本原理,而不是像我一样进行点击和尝试,我将非常感激。

context-free-grammar computation-theory ambiguous-grammar
3个回答
0
投票

S → U |
U→aS |
T → aTbT | Ɛ


0
投票
S -> aT | eps
T -> aSbS | eps

使用感应。规则引入歧义的唯一方法是规则本身不明确或者它所依赖的任何规则不明确。 S 不会引入歧义,因此 T 不会引入歧义,因为它只依赖于 S 并且本身并不歧义。


0
投票

S -> aSbT | bSaT |时间 T - > ab |巴|每股收益

© www.soinside.com 2019 - 2024. All rights reserved.