坚持将 cfg 转换为 dcg

Question

我正在尝试自学 prolog 并为简单的算术 cfg 实现解释器：

<expression> --> number
<expression> --> ( <expression> )
<expression> --> <expression> + <expression>
<expression> --> <expression> - <expression>
<expression> --> <expression> * <expression>
<expression> --> <expression> / <expression>

到目前为止，我已经在 swi-prolog 中编写了它，它遇到了下面描述的许多错误；

expression(N) --> number(Cs), { number_codes(N, Cs) }.
expression(N) --> "(", expression(N), ")".
expression(N) --> expression(X), "+", expression(Y), { N is X + Y }.
expression(N) --> expression(X), "-", expression(Y), { N is X - Y }.

number([D|Ds]) --> digit(D), number(Ds).
number([D])    --> digit(D).

digit(D) --> [D], { code_type(D, digit) }.

使用

进行测试

phrase(expression(X), "12+4").

给出 X = 16，这很好。还有

phrase(expression(X), "(12+4)").

作品和短语（表达式（X），“12+4+5”）。还可以

但正在尝试

phrase(expression(X), "12-4").

导致 "ERROR: Out of local stack" 除非我注释掉“+”规则。虽然我可以添加两个以上的数字，但括号不能递归工作（即“(1+2)+3”挂起）。

我确定解决方案很简单，但我无法从我找到的在线教程中找出答案。

Answer 1

原则上你所做的一切都是正确的。你是对的：答案很简单。

但是

左递归在定子句语法中是致命的；症状正是您所看到的行为。

如果您在 expression 上设置一个监视点并使用跟踪工具，您可以看到您的堆栈不断增长，而解析器却毫无进展。

gtrace.
spy(expression).
phrase(expression(N),"12-4").

如果仔细考虑 Prolog 执行模型，您就会明白发生了什么。

我们尝试将“12-4”解析为表达式。

我们的调用堆栈包含从第 1 步开始对 expression 的调用，我将其写为 expression(1).
通过"expression"的第一个子句，我们成功地将“12”解析为表达式，并且我们记录了一个选择点，以备稍后需要回溯时使用。事实上我们需要立即回溯，因为涉及 phrase 的父请求说我们要解析整个字符串，但我们没有：我们还有“-4”要解析。所以我们失败了，回到选择点。我们已经证明 "expression" 的第一个子句没有成功，所以我们重试第二个子句。

调用堆栈：expression(1).
我们尝试使用 "expression" 的第二个子句解析“12-4”，但立即失败（初始字符不是“(”)。所以我们失败并重试第三条。

调用堆栈：expression(1).
第三个子句要求我们从输入的开头解析一个表达式，然后找到一个“+”和另一个表达式。所以我们现在必须尝试将输入的开头解析为表达式。

调用堆栈：expression(4) expression(1).
我们尝试将“12-4”的开头解析为一个表达式，成功解析为“12”，与步骤1相同。我们记录一个选择点，以备回溯时使用稍后。

调用堆栈：expression(4) expression(1).
我们现在恢复从第 4 步开始的尝试，将“12-4”解析为针对 "expression" 的第 3 条的表达式。我们已经完成了第一步；现在我们必须尝试将“-4”解析为 "expression" 的第 3 条右侧的剩余部分，即 "+", expression(Y)。但“-”不是“+”，所以我们立即失败，回到最近记录的选择点，即第 5 步中记录的选择点。接下来的事情是尝试找到一种不同的解析方式作为表达式输入。我们使用 "expression".
的第二个子句继续搜索
调用堆栈：expression(4) expression(1).
第二个子句再次失败。所以我们继续"expression"的第三个子句。这要求我们在输入的开头寻找一个表达式（作为确定我们当前对 "expression" 的两次调用是成功还是失败的一部分）。所以我们再次调用"expression"。

调用堆栈：expression(7) expression(4) expression(1).

可以看到每次我们把对expression的调用添加到栈中，都会成功，找加号，失败，再试，最终到达第三个子句，此时我们将把另一个调用压入堆栈并重试。

简答：左递归在 DCG 中是致命的。

它在递归下降解析器中也是致命的，解决方法大同小异：不要向左递归。

你的语法的非左递归版本是：

expression(N) --> term(N).
expression(N) --> term(X), "+", expression(Y), { N is X + Y }.
expression(N) --> term(X), "-", expression(Y), { N is X - Y }.
term(N) --> number(Cs), { number_codes(N, Cs) }.
term(N) --> "(", expression(N), ")".

但是，这会使“-”具有正确的关联性，并且在许多情况下需要重复重新解析初始项，因此用于生产的代码中的一种常见方法是做一些不太像您开始使用的 BNF 的事情，但更多像下面的 EBNF 版本：

expression = term {("+"|"-") term}
term = number | "(" expression ")".

我学会写它的方式（很久以前我已经不记得是谁写的了）是这样的（一开始我觉得它很丑，但它在你身上成长）：

expression(N) --> term(X), add_op_sequence(X,N).
add_op_sequence(LHS0, Result) -->
    "+", term(Y),
    {LHS1 is LHS0 + Y},
    add_op_sequence(LHS1,Result).
add_op_sequence(LHS0, Result) -->
    "-", term(Y),
    {LHS1 is LHS0 - Y},
    add_op_sequence(LHS1,Result).
add_op_sequence(N,N) --> [].

term(N) --> number(Cs), { number_codes(N, Cs) }.
term(N) --> "(", expression(N), ")".

到目前为止累积的值在 add_op_sequence 的左侧参数中向下传递，最终（当序列以空产生式结束时）作为结果向上传递。

被称为'left-corner parsing'的解析策略是处理这个问题的一种方法；关于在自然语言处理中使用 Prolog 的书籍几乎总是会讨论它。

坚持将 cfg 转换为 dcg

Stuck on translating a cfg to dcg

prolog

context-free-grammar

dcg