在没有削减的情况下解析Prolog？

Question

我发现这个很好的片段用于解析Prolog中的lisp(从这里开始):

ws --> [W], { code_type(W, space) }, ws.
ws --> [].

parse(String, Expr) :- phrase(expressions(Expr), String).

expressions([E|Es]) -->
    ws, expression(E), ws,
    !, % single solution: longest input match
    expressions(Es).
expressions([]) --> [].

% A number N is represented as n(N), a symbol S as s(S).

expression(s(A))         --> symbol(Cs), { atom_codes(A, Cs) }.
expression(n(N))         --> number(Cs), { number_codes(N, Cs) }.
expression(List)         --> "(", expressions(List), ")".
expression([s(quote),Q]) --> "'", expression(Q).

number([D|Ds]) --> digit(D), number(Ds).
number([D])    --> digit(D).

digit(D) --> [D], { code_type(D, digit) }.

symbol([A|As]) -->
    [A],
    { memberchk(A, "+/-*><=") ; code_type(A, alpha) },
    symbolr(As).

symbolr([A|As]) -->
    [A],
    { memberchk(A, "+/-*><=") ; code_type(A, alnum) },
    symbolr(As).
symbolr([]) --> [].

但是表达式使用了切割.我假设这是为了提高效率.是否可以编写此代码,以便它可以有效地工作而不会削减？

也会有感兴趣的答案涉及Mercury的软切/承诺选择.

Answer 1

你在这里触及一个非常深刻的问题.在剪切的地方你添加了评论"最长的输入匹配".但你实际上做的是承诺第一个解决方案,它将产生非终端的"最长输入匹配",ws//0但不一定是expression//1.

许多编程语言基于最长输入匹配来定义其令牌.这通常会导致非常奇怪的效果.例如,一个数字后面可能会紧跟许多编程语言中的字母.Pascal,Haskell,Prolog和许多其他语言就属于这种情况.例如 if a>2then 1 else 2,有效的Haskell.有效的Prolog:X is 2mod 3.

鉴于此,定义一种编程语言可能是一个好主意,因此它根本不依赖于这些特征.

当然,您希望优化语法.但我只能建议首先明确一个明确的定义.

至于效率(和纯度):

eos([],[]).

nows --> call(eos).
nows, [W] --> [W], { code_type(W, nospace) }.

ws --> nows.
ws --> [W], {code_type(W, space)}, ws.

Answer 2

剪切不是用于提高效率,而是用于提交第一个解决方案(请参阅!/ 0旁边的注释:"单一解决方案:最长输入匹配").如果您注释掉!/ 0,您将得到例如:

?- parse("abc", E).
E = [s(abc)] ;
E = [s(ab), s(c)] ;
E = [s(a), s(bc)] ;
E = [s(a), s(b), s(c)] ;
false.

很明显,在这种情况下,只需要由形成令牌的最长字符序列组成的第一种解决方案.鉴于上面的例子,我因此不同意"假":表达式// 1是不明确的,因为数字// 1和符号// 1是.在Mercury中,您可以使用确定性声明cc_nondet提交解决方案(如果有).