删除DCG中的左递归 - Prolog

Question

我在这个语法中有一个左递归的小问题.我正在尝试在Prolog中编写它,但我不知道如何删除左递归.

<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 }.

我写过类似的东西,但它根本不起作用.如何更改它以使该程序正常工作？

Answer 1

你的程序的问题确实是左递归；应该将其删除，否则您将陷入无限循环

\n\n

要删除立即左递归，请替换表单的每个规则

\n\n

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

\n\n

和：

\n\n

A -> b1 A\'|b2 A\'|....\nA\' -> \xce\xb5 | a1 A\'| a2 A\'|....\n

\n\n

所以函数是

\n\n

function -> atom, functionR.\nfuntionR -> [].\n

\n\n

维基页面

\n