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)

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

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

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

Answer 1

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

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

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

Answer 2

STRING @ STRING @ STRING

可能由A ⇒ B @(B @ B)或A ⇒ (B @ B) @ B 导致，因为

B --> B @ B

解决方案是引入一个新的类似 B 的非终结符，并用该非终结符替换出现的次数。这引入了不对称性，您会在许多语法中找到。

很高兴弄清楚我留给你的其余部分。