时间戳

首页 > 解决方案 > Prolog 错误：预期为 `character'，找到 `"((.).)"'（字符串）

prolog - Prolog 错误：预期为 `character'，找到 `"((.).)"'（字符串）

问题描述

我的目标是以括号表示法打印具有 N 个节点的所有形式的树，可以根据上下文无关语法定义如下：

T → 树为空

T → (TT) 具有左右子节点的节点

例如，所有具有 3 个节点的树将如下所示：

（（（。）。）。）

（（（。（。））。）

((.).(.))

(.((.).))

(.(.(.)))

我在 Prolog 中编写了以下代码，


form1(Prev, Next) :- 
    string_concat("(", Prev, Inter),
    string_concat(Inter, ".)", Next).
form2(Prev, Next) :- 
    string_concat("(.", Prev, Inter),
    string_concat(Inter, ")", Next).

tree(1, ["(.)"]) :- !.

tree(N, Strings) :-
    A is N - 1, tree(A, PrevStrings1),
    maplist(form1 , PrevStrings1, List1),
    maplist(form2 , PrevStrings1, List2),
    append(List1, List2, Result),
    Strings is Result.

但我得到这个错误：

?- tree(2, L).
ERROR: Type error: `character' expected, found `"((.).)"' (a string)
ERROR: In:
ERROR:    [9] _3182 is ["((.).)","(.(.))"]
ERROR:    [7] <user>

我没有在我的代码中引用字符。怎么了？

标签： prologdcg

解决方案

解决此类问题的最佳方法是首先从抽象表示开始。抽象意味着所有语法细节都已被删除。你真正想要的是以下形式的树

is_tree(empty).
is_tree(node(Left, Right)) :-
   is_tree(Left),
   is_tree(Right).

然后，基于此表示，您可以使用您最喜欢的语法花哨来定义一个具体的表示。

:- set_prolog_flag(double_quotes, chars).

tree(empty) --> "".
tree(node(Left, Right)) -->
   "(",
   tree(Left),
   ".",
   tree(Right),
   ")".

?- length(Text, N), phrase(tree(Tree), Text).
Text = [],
N = 0,
Tree = empty ;
Text = ['(','.',')'],
N = 3,
Tree = node(empty,empty) ;
Text = ['(','.','(','.',')',')'],
N = 6,
Tree = node(empty,node(empty,empty)) ;
Text = ['(','(','.',')','.',')'],
N = 6,
Tree = node(node(empty,empty),empty) ...

为了提高答案的可读性，请使用 [library(double_quotes)代表SWI和SICStus。

?- use_module(double_quotes).

?- length(Text, N), phrase(tree(Tree), Text).
Text = [],
N = 0,
Tree = empty ;
Text = "(.)",
N = 3,
Tree = node(empty,empty) ;
Text = "(.(.))",
N = 6,
Tree = node(empty,node(empty,empty)) ;
Text = "((.).)",
N = 6,
Tree = node(node(empty,empty),empty) ;
Text = "(.(.(.)))",
N = 9,
Tree = node(empty,node(empty,node(empty,empty))) ;
Text = "(.((.).))",
N = 9,
Tree = node(empty,node(node(empty,empty),empty)) ...

最后，您现在可以完全跳过抽象语法树，因此：

tree --> "".
tree --> "(", tree, ".", tree, ")".

?- length(Text, N), phrase(tree, Text).
Text = [],
N = 0;
Text = "(.)",
N = 3;
Text = "(.(.))",
N = 6;
Text = "((.).)",
N = 6;
Text = "(.(.(.)))",
N = 9;
Text = "(.((.).))",
N = 9 ...

乍一看，这种紧凑的语法似乎更可取，但在许多情况下它非常不方便。特别是，如果您正在设计一个新语法，并且您不确定您的语法是否包含歧义。在之前的版本的帮助下，证明这样的事情是非常简单的。

推荐阅读