可能无限递归（循环）：用DCG解析规则

Question

我正在努力为一种命令式语言开发一个小型解析器，但我坚持使用非递归语法的定义。

我阅读了 this post 的解决方案，但我无法理解它，我将终端调用移到我的声明之上，但我对用于表达的不同语法感到困惑同一个意思。

我输入的token是下面一个[word(x),punct(:),punct(=),number(1)]

这是我用来解析这个列表的代码

parse(ListTokens, ListStmt) :-
    phrase(commands(ListStmt), ListTokens).

commands([]) --> [].
commands(Command) --> command(Command).
commands(Commands) --> [punct("(")], commands(Commands), [punct(")")].
commands([Command | Commands]) --> command(Command), [punct(";")], commands(Commands).

command(Skip) --> [keyword("skip")],
                  {Skip = skip()}.

command(Assign) --> a_expr(X), !, [punct(":")], [punct("=")], a_expr(Y), !,
                    {Assign = assign(X, Y)}.

command(While) --> [keyword("while")], b_expr(X), !, [keyword("do")], command(Commands), !,
                   {While = while(X, Commands)}.

a_expr(word(Name)) --> [var(Name)].
a_expr(number(Val)) --> [Val].

a_expr(Expr) --> a_expr(X), !, [punct("+")], a_expr(Y), !, {Expr = increment(X, Y)}.
a_expr(Expr) --> a_expr(X), !, [punct("-")], a_expr(Y), !, {Expr = decrement(X, Y)}.
a_expr(Expr) --> a_expr(X), !, [punct("*")], a_expr(Y), !, {Expr = multipl(X, Y)}.

b_expr(Expr) --> [punct("(")], b_expr(Expr), [punct(")")].
b_expr(True) --> [keyword("true")], {True = bool(1)}.
b_expr(False) --> [keyword("false")], {False = bool(0)}.
b_expr(Cmp) --> a_expr(X), !, [punct("=")], a_expr(Y), !, {Cmp = cmp(X, Y)}.
b_expt(Gt) --> a_expr(X), !, [punct(">")], a_expr(Y), !, {Gt = gt(X, Y)}.

结果报告如下，但我想有以下一个assign(x,1)

assign(number(word(x)),number(number(1)))

我认为问题出在以下几行，但我找不到错误，因为这是来自 this post 的解决方案，它使用了不同的语法

a_expr(word(Name)) --> [var(Name)].
a_expr(number(Val)) --> [Val].

你能帮我解决这个问题吗？

Answer 1

基本上，您的代码有两个问题。

一个是停止回溯的 bang 运算符 !。它是一个反模式，所以我建议不要使用它。

我非常喜欢可读代码，我认为您需要在语法中接受左递归，主要是因为您使用的语法非常可读。

我建议换

parse(ListTokens, ListStmt) :-
    phrase(commands(ListStmt), ListTokens).

commands([]) --> [].
commands(Command) --> command(Command).
commands(Commands) --> [punct("(")], commands(Commands), [punct(")")].
commands([Command | Commands]) --> command(Command), [punct(";")], commands(Commands).

command(Skip) --> [keyword("skip")],
                  {Skip = skip()}.

command(Assign) --> a_expr(X), !, [punct(":")], [punct("=")], a_expr(Y), !,
                    {Assign = assign(X, Y)}.

command(While) --> [keyword("while")], b_expr(X), !, [keyword("do")], command(Commands), !,
                   {While = while(X, Commands)}.

a_expr(word(Name)) --> [var(Name)].
a_expr(number(Val)) --> [Val].

a_expr(Expr) --> a_expr(X), !, [punct("+")], a_expr(Y), !, {Expr = increment(X, Y)}.
a_expr(Expr) --> a_expr(X), !, [punct("-")], a_expr(Y), !, {Expr = decrement(X, Y)}.
a_expr(Expr) --> a_expr(X), !, [punct("*")], a_expr(Y), !, {Expr = multipl(X, Y)}.

b_expr(Expr) --> [punct("(")], b_expr(Expr), [punct(")")].
b_expr(True) --> [keyword("true")], {True = bool(1)}.
b_expr(False) --> [keyword("false")], {False = bool(0)}.
b_expr(Cmp) --> a_expr(X), !, [punct("=")], a_expr(Y), !, {Cmp = cmp(X, Y)}.
b_expt(Gt) --> a_expr(X), !, [punct(">")], a_expr(Y), !, {Gt = gt(X, Y)}.

对于这一行，基本上，添加以下行 :- table a_expr//1. 以使用制表并接受左递归。（注意，你需要去掉所有的 bang 运算符）

:- table a_expr//1.

% other rules

% add this one, it is left recursion, but tanks to tabling
a_expr(Var)   --> [word(Name)], {Var = var(Name)}.
a_expr(Val)   --> [number(X)], {Val = X}.

a_expr(Expr) --> a_expr(X), [punct("+")], a_expr(Y), {Expr = increment(X, Y)}.
a_expr(Expr) --> a_expr(X), [punct("-")], a_expr(Y), {Expr = decrement(X, Y)}.
a_expr(Expr) --> a_expr(X), [punct("*")], a_expr(Y), {Expr = multipl(X, Y)}.

P.S：正如一个评论所建议的，您需要按照以下规则进行打字错误

b_expt(Gt) --> a_expr(X), !, [punct(">")], a_expr(Y), !, {Gt = gt(X, Y)}.

是b_expr

可能无限递归（循环）：用DCG解析规则

Probable infinite recursion (cycle): with DCG parsing rule

prolog

swi-prolog