prolog - 消除抽象语法中的歧义以编写 DCG 解析器 Prolog

Question

P => 程序
K => 块

S => 单命令

C => 命令

E => 表达式

B => bool 表达式

我 => 标识符

N > 数字

P::= K。

K::= 开始 C 结束

C::= C1 ; C2 |秒

S::= I := E |如果 (B) 那么 S | if (B) then S1 else S2 |而 (B) 做 S |重复 C 直到 (B) |克|打印E

E::= − E | E1 + E2 | E1 - E2 | E1 E2 | E1 div E2 | E1 模式 E2 | (E) |我| N

B::= E1 = E2 | E1 > E2 | E1 < E2 | E1 != E2 |不是 B | B1和B2 | B1 或 B2 | (乙)

我应该消除 E 和 B 中的歧义，以便我可以在 prolog 中编写 DCG 解析器。

Answer 1

Prolog 自上而下求值，然后 LL grammar techniques可以适应。 DCG 比 LL(1) 更强大，但仍然必须消除左递归。
B更容易处理:留下生产要素。

B ::= E Bx | not B | (B)
Bx ::= = E | > E | < E | != E | and B | or B

E更难，因为想念 mul token 引入了更多的歧义。姑且

E ::= − E | (E) | I | N | El
El ::= Ex E | epsilon
Ex ::= + El | − El | div El | mod El

DCG中的epsilon(空生产)可以这样写

epsilon --> [].

如果您需要处理优先级和关联性(在 B 和 E 中)，您将需要做更多的工作。您可以引用 this工作模式的旧答案。