将模棱两可的语言转换为明确的

Question

我被布置了一项家庭作业任务，将以下语法转换为无歧义的。

A --> B
A --> ε
B --> B @ B
B --> STRING
B --> DOUBLE(STRING)

其中 A 和 B 是非终结符，STRING 和 DOUBLE 是非终结符。

我可以得出它是不明确的，因为可以为一个字符串构造两个不同的解析树，例如：

STRING @ STRING @ DOUBLE(STRING)。

到目前为止，我有：

A --> B | ε
B --> B @ DOUBLE(STRING)
B --> C
C --> C @ STRING | STRING | DOUBLE(STRING)

然而它并不完整，因为字符串如：

字符串@双（字符串）@字符串

无法制作。我如何将此语法转换为无歧义的？

Answer 1

STRING @ STRING @ STRING

可能来自 A ⇒ B @(B @ B) 或 A ⇒ (B @ B) @ B 因为

B --> B @ B

解决方案是引入一个新的类 B 非终结符，并用该非终结符替换出现的位置。这引入了一种不对称性，你会在许多语法中发现它。

剩下的事情交给你了。

Answer 2

继续Joop的回答，你可以引入一个新的符号D来消除围绕B --> B @ B的歧义：

A --> D
A --> ε
D --> D @ B
D --> B
B --> STRING
B --> DOUBLE(STRING)

进行此更改后，该语言中的任何字符串都只能使用一棵树。

Converting ambiguous language to unambiguous