5

P => 程序 K => 块

S => 单命令

C => 命令

E => 表达式

B => 布尔表达式

I => 标识符

N > 数字

P ::= K。

K ::= 开始 C 结束

C ::= C1 ; C2 | 小号

S ::= 我 := E | 如果 (B) 则 S | 如果 (B) 则 S1 否则 S2 | 而（B）做S | 重复 C 直到 (B) | ķ | 打印 E

E ::= - E | E1 + E2 | E1 - E2 | E1 E2 | E1 分区 E2 | E1 模组 E2 | (五) | 我 | ñ

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

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

4

2 回答 2

5

Prolog 自上而下评估，然后可以调整LL语法技术。DCG 比 LL(1) 更强大，但仍然必须消除左递归。

B更容易处理：留下生产要素。

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

E 更难，因为miss multoken 引入了更多的歧义。姑且

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

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

epsilon --> [].

如果您需要处理优先级和关联性（在 B 和 E 中），您将需要更多的工作。您可以参考这个较旧的答案以获取工作模式。

于 2012-10-30T08:37:57.233 回答
3

@chac 已经给了你一个很好的答案，向你展示了解决这个问题的常用方法。

让我以另一种方式阅读您的问题：您“应该删除 E 和 B 中的歧义，以便”您“可以在 Prolog 中编写 DCG 解析器”。这意味着，您只需要消除歧义，就可以在 Prolog 中编写 DCG 解析器。有一个好消息：编写 DCG 解析器根本不需要消除任何歧义！方法如下：

歧义的来源是像

C ::= C ; C

或其他运算符 + - 并列 div mod 和

让我坚持一个简化的语法：

E ::= E + E | “1”

我们可以将其编码为

e --> "1".
e --> e, "+", e.

不幸的是，Prolog 不会因类似的查询而终止

?- L = "1+1+1", phrase(e,L).
L = "1+1+1" ;
ERROR: Out of local stack

实际上，它终止了，但这只是因为我的计算机的内存是有限的......

甚至不适合：

?- L = "1", phrase(e,L).
L = "1" ;
ERROR: Out of local stack

这是一个模棱两可的问题吗？不！这只是 Prolog 的一个程序问题，不能直接处理左递归。这是一种让 Prolog 处理它的方法：

e([_|S],S) --> "1"。
e([_|S0],S) --> e(S0,S1), "+", e(S1,S)。

?- L = "1+1+1", 短语(e(L,[]),L)。
L = "1+1+1" ;
L = "1+1+1" ;
错误的。

?- L = "1", 短语(e(L,[]),L)。
L = "1" ;
错误的。

目前我们只定义了一个语法，大多数时候你也有兴趣看看对应的语法树：

e(整数 (1), [_|S],S) --> "1"。
e( plus(L,R), [_|S0],S) --> e( L, S0,S1), "+", e( R, S1,S)。

?- L = "1+1+1", 短语(e(Tree, L,[]),L)。
L = "1+1+1",
树 = plus(integer(1),plus(integer(1),integer(1))) ;
L = "1+1+1",
树 = plus(plus(integer(1),integer(1)),integer(1)) ;
错误的。

现在，我们看到plus! 您的原始语法都将其接受为 (1+1)+1 和 1+(1+1)，只要相应的语义保证观察到关联性，这本身就不是问题。大多数情况下，这被消除为左结合，因此意味着 (1+1)+1，但并非所有中缀运算符都是如此。

于 2012-10-30T16:44:59.760 回答