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

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)

但是它并不像字符串那样完整，例如：

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

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

标签： grammarcontext-free-grammarambiguous-grammar

Answer 1

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

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

通过此更改，语言中的任何字符串都只能使用一棵树。