删除DCG中的左递归 - 序言

我在这个语法中遇到了一个左递归的小问题。我试图在Prolog中编写它，但我不知道如何去除左递归。删除DCG中的左递归 - 序言

<expression> -> <simple_expression> 
<simple_expression> -> <simple_expression> <binary_operator> <simple_expression> 
<simple_expression> -> <function> 
<function> -> <function> <atom> 
<function> -> <atom> 
<atom> -> <number> | <variable> 

<binary_operator> -> + | - | * |/

expression(Expr) --> simple_expression(SExpr), { Expr = SExpr }. 
simple_expression(SExpr) --> simple_expression(SExpr1), binary_operator(Op), simple_expression(SExpr2), { SExpr =.. [Op, SExpr1, SExpr2] }. 
simple_expression(SExpr) --> function(Func), { SExpr = Func }. 
function(Func) --> function(Func2), atom(At), { Func = [Func2, atom(At)] }. 
function(Func) --> atom(At), { Func = At }.

我写过类似的东西，但它根本不起作用。如何改变它来获得这个程序的工作？

来源

2012-05-19 Finley Osbert

你的程序的问题确实是左递归;它应该被删除，否则你会陷入一个死循环

要删除立即左递归替换形式的每个规则

A->A a1|A a2|....|b1|b2|....

有：

A -> b1 A'|b2 A'|.... 
A' -> ε | a1 A'| a2 A'|....

所以功能将是

function -> atom, functionR. 
funtionR -> [].

wiki page

来源

2012-05-19 08:40:02

@thanosQR的答案相当不错，但适用于比DCG更通用的上下文，并且需要更改分析树。实际上，解析的“结果”已被删除，这并不好。

如果你只是在解析表达式，我发布here东西有用。

来源

2012-05-19 09:27:57 CapelliC

是的，通过改变语法和使用累加器来消除左递归的经典方法。花了我几年时间来跟随你的“这里”链接。 –

该问题仅出现在您使用反向链接之后。在前向链中，可以直接处理左递归语法规则。提供表格的文法规则：

NT ==> NT'

不要形成一个循环。如果将它们放置在身体的非终端之后，并且头部的非终端没有专门进入辅助计算的参数，也可以使用辅助计算，即{}/1。即自底向上状态。

这里是左递归语法的例子，在正向链完美地工作是这样的：

:- use_module(library(minimal/chart)). 
:- use_module(library(experiment/ref)). 

:- static 'D'/3. 

expr(C) ==> expr(A), [+], term(B), {C is A+B}. 
expr(C) ==> expr(A), [-], term(B), {C is A-B}. 
expr(A) ==> term(A). 

term(C) ==> term(A), [*], factor(B), {C is A*B}. 
term(C) ==> term(A), [/], factor(B), {C is A/B}. 
term(A) ==> factor(A). 

factor(A) ==> [A], {integer(A)}.

这里是一个link到图表解析器的源代码。从这个链接中，前向链接的源代码也可以找到。在下面的示例会话所示：

?- use_module(library(minimal/hypo)). 

?- chart([1,+,2,*,3], N) => chart(expr(X), N). 
X = 7

在解析图表解析器将填充图中的底向上的方式。对于上述制作中的每个非终端p/n，都会有p/n + 2的事实。以上是上例的图表结果：

:- thread_local factor/3. 
factor(3, 4, 5). 
factor(2, 2, 3). 
factor(1, 0, 1). 

:- thread_local term/3. 
term(3, 4, 5). 
term(2, 2, 3). 
term(6, 2, 5). 
term(1, 0, 1). 

:- thread_local expr/3. 
expr(3, 4, 5). 
expr(2, 2, 3). 
expr(6, 2, 5). 
expr(1, 0, 1). 
expr(3, 0, 3). 
expr(7, 0, 5).

来源

2012-05-19 16:27:26

我现在正在展示即将发布的Jekejeke Minlog 1.1.4版本的代码。它可能需要几周时间才能发布，您可以随时准备。 –

许多Prolog系统提供了表格。在许多情况下，使用制表终止也可以扩展到左递归语法。这里是一个解决方案，它利用了新的SWI-Prolog的桌游戏功能：

:- use_module(library(tabling)). 
:- table expr/3. 
:- table term/3. 
:- table factor/3. 

expr(C) --> expr(A), [+], term(B), {C is A+B}. 
expr(C) --> expr(A), [-], term(B), {C is A-B}. 
expr(A) --> term(A). 

term(C) --> term(A), [*], factor(B), {C is A*B}. 
term(C) --> term(A), [/], factor(B), {C is A/B}. 
term(A) --> factor(A). 

factor(A) --> [A], {integer(A)}.

由于这feature是SWI-Prolog的比较新的，它只是作品，因为当你在调试模式切换的时刻：

?- debug. 

?- phrase(expr(X), [1,+,2,*,3], []). 
X = 7

来源

2016-06-05 21:58:02

删除DCG中的左递归 - 序言

回答

相关问题