删除DCG中的左递归-Prolog [英] Removing left recursion in DCG - Prolog

问题描述

在此语法中，左递归存在一个小问题.我正在尝试用Prolog编写它，但是我不知道如何删除左递归.

I've got a small problem with left recursion in this grammar. I'm trying to write it in Prolog, but I don't know how to remove left recursion.

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

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

I've written something like that, but it won't work at all. How to change it to get this program working?

推荐答案

@thanosQR的答案是相当不错的，但它适用于比DCG更通用的上下文，并且需要对分析树"进行更改.有效地，解析的结果"已被删除，这不是很好.

The answer from @thanosQR is fairly good, but applies to a more general context than DCG, and requires a change in the Parse Tree. Effectively, the 'outcome' of parsing has been removed, that's not good.

如果您只想解析表达式，我在此处发布了一些有用的内容.

If you are interested just in parsing expressions, I posted here something useful.

这篇关于删除DCG中的左递归-Prolog的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！