憋屈平移CFG到DCG

我想教自己序言和实施一个解释为一个简单的算术CFG：憋屈平移CFG到DCG

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

到目前为止，我已经在SWI-序言写这本击中下面描述的错误数量;

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").

原因“出错：本地栈”除非我注释掉“+”规则。虽然我可以添加两个以上的数字，括号不会递归地工作（即“（1 + 2）+3”挂起）。

我确定解决方案很简单，但我一直无法从我找到的在线教程中弄清楚。

来源

2015-03-31 joeblog

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

但是。

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

如果您在expression上设置了一个间谍点并使用跟踪工具，则可以监视堆栈的增长，增长和增长，而解析器根本没有任何进展。

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

如果您仔细考虑了Prolog执行模型，可以看到发生了什么。

我们试图解析“12-4”作为表达式。

我们的调用栈包含此调用，从步骤1到expression，我将写expression（1）。
我们成功地通过“表达式”的第一个子句解析“12”作为表达式，并且我们记录了一个选择点，以备日后需要回溯。事实上，我们需要立即回溯，因为涉及phrase的父请求表示我们要解析整个字符串，而我们没有：我们仍然有“-4”。所以我们失败了，回到选择点。我们已经表明，“表达式”的第一个子句不成功，所以我们重试第二个子句。

调用堆栈：expression（1）。
我们尝试解析“12-4”使用“表达”第二条，但立即失败（初始字符不是“（”）。因此，我们会失败，重试对第三条款。

调用堆栈：expression（1）。
第三个条款要求我们从输入开始处解析表达式，然后找到一个“+”和另一个表达式。所以我们现在必须尝试将输入的开始解析为表达式。

调用堆栈：expression（4）expression（1）。
我们尝试将“12-4”的开头解析为一个表达式，并以“12”结束，就像在步骤1中一样。我们记录了一个选择点，以备日后需要回溯。

调用堆栈：expression（4）expression（1）。
我们现在恢复在步骤4中开始的尝试，将“12-4”解析为针对“表达式”的子句3的表达式。我们已经完成了第一步;现在我们必须尝试解析“-4”作为“表达式”第3条右边的余下部分，即"+", expression(Y)。但“ - ”不是“+”，所以我们立即失败，并返回到最近记录的选择点，即步骤5中记录的选择点。接下来要尝试找到解析作为表达式输入。我们用“表达式”的第二个子句继续搜索。

调用堆栈：expression（4）expression（1）。
第二个子句再次失败。所以我们继续“表达”的第三个条款。这要求我们在输入的开头寻找一个表达式（作为确定我们当前对“表达式”的两个调用是否可以成功或失败的一部分）。所以我们再次称之为“表情”。

调用堆栈：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的左侧参数向下传递，最终（当序列与空生产结束）传回了结果是。

称为“左角解析”的解析策略是处理此问题的一种方法;关于在自然语言处理中使用Prolog的书籍几乎总是在讨论它。

来源

2015-04-01 02:53:07

非常感谢那非常全面的答案。 – joeblog 2015-04-01 10:05:18

憋屈平移CFG到DCG

回答

相关问题