在其他的抽象语法中删除Ambiguity来编写DCG解析器Prolog

Question

P =>程序K =>阻止

S =>单指令

C =>命令

E =>表达

B => Boolean-expr

I =>标识符

N>数字

P :: = K.

K :: =开始C结束

C :: = C1; C2 | 小号

S :: = I:= E | 如果(B)则S | 如果(B)那么S1否则S2 | 而(B)做S | 重复C直到(B)| K | 打印E.

E :: = - E | E1 + E2 | E1 - E2 | E1 E2 | E1 div E2 | E1 mod E2 | (E)| 我| ñ

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

我应该删除E和B中的歧义,以便我可以在prolog中编写DCG解析器.

Answer 1

Prolog从上至下进行评估，然后可以采用LL 语法技术。DCG比LL（1）更强大，但是仍然必须消除左递归。

B更易于处理：将生产要素留给生产。

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

E更难，因为未命中mul令牌引入了更多的歧义。姑且

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

DCG中的epsilon（空生产）可以这样写

epsilon --> [].

如果您需要处理优先级和关联性（在B和E中），则需要做更多的工作。您可以参考此较早的答案以获取有效的方案。