我在这个语法中遇到了一个关于左递归的小问题。我正在尝试用 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 }.
我写过类似的东西,但根本行不通。如何更改它才能使该程序运行?
你的程序的问题确实是左递归;应该将其删除,否则您将陷入无限循环
要删除立即左递归,请替换表单的每个规则
A->A a1|A a2|....|b1|b2|....
with:
A -> b1 A'|b2 A'|....
A' -> ε | a1 A'| a2 A'|....
所以函数是
function -> atom, functionR.
funtionR -> [].
维基页面 https://secure.wikimedia.org/wikipedia/en/wiki/Left_recursion
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)