prolog - Change DCG to be deterministic

Question

how to change this gramma to be deterministic

e --> [].
e --> "*".
e --> s_e.
e --> e, s_e.
s_e --> ("a",e);("b",e).

I just dont know where to put cut to avoid backtracking.

Answer 1

您可以按如下方式重写最后一条规则：

s_e --> "a", e.
s_e --> "b", e.

现在进行以下削减可能是有意义的：

s_e --> "a", !, e.
s_e --> "b", !, e.

您也可以使用 (;)/2 以原始紧凑形式放置切口，但我发现上面的内容更透明。如果 s_e 没有使用相同的输入列表多次调用，则上述内容有效。

但是您的语法有一个缺陷， e 是左递归的，并且 s_e 将使用相同的输入列表多次调用。意味着您的语法将例如循环否定句子，即它将无法拒绝它们，并且您的语法将在重做肯定句子后循环，即当输入被接受时。

因此，您还需要消除左递归，因为普通的 Prolog 深度拳头搜索无法处理它。最简单的方法是用一个新的非终结符右递归替换它。也就是说，您可以编写 e 的产生式，如下所示：

 e --> s_e, rest_e.
 e --> "*", rest_e.
 e --> [].

 rest_e --> s_e, rest_e.
 rest_e --> "*", rest_e.
 rest_e --> [].

我们也可以进行切割：

 e --> s_e, !, rest_e.
 e --> "*", !, rest_e.
 e --> [].

 rest_e --> s_e, !, rest_e.
 rest_e --> "*", !, rest_e.
 rest_e --> [].

此外，在多个空 e 产生式不再通过 s_e 进入 e 本身的意义上，上述语法也略有修改。它也更贪婪，因为 sub e 产品总是被完全解析。所以例如这句话：

 aaa

仅解析为：

 a(a(a))

而不是：

 a(a)a

或者：

 aa(a)

或者：

 aaa

但否则它应该接受与 DCG 自下而上执行并且不会出现左递归问题的句子相同的句子。

此致