在Prolog中不使用cut进行语法分析？
我在Prolog中找到了这个解析lisp的很好的代码片段(来自here)：
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([]) --> [].但是，表达式使用了cut。我假设这是为了提高效率。有没有可能编写这样的代码，让它在没有cut的情况下高效地工作？
也会对涉及水星的软削减/承诺选择的感兴趣的答案。
回答 3
Stack Overflow用户
发布于 2011-06-16 01:08:21
使用cut不是为了提高效率，而是为了提交第一个解决方案(参见!/0："single solution: longest match“旁边的注释)。如果你注释掉!/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.显然，在这种情况下，只需要由形成标记的最长字符序列组成的第一种解决方案。考虑到上面的例子，我不同意"false"：表达式//1是模棱两可的，因为数字//1和symbolr//1是模糊的。在水星中，您可以使用确定性声明cc_nondet来提交解决方案。
Stack Overflow用户
发布于 2011-06-16 01:02:01
你在这里碰到了一个相当深的问题。在裁剪的位置，您添加了注释“最长输入匹配”。但您实际做的是提交第一个解决方案，它将为非终端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.Stack Overflow用户
发布于 2011-06-22 03:52:09
您可以使用已经在解析表达式语法(PEGs)中找到其位置，但在DCGs中也可用的构造。即DCG目标的否定。在别号中添加感叹号(!)带参数用于否定，即！e.在DCG中，DCG目标的否定是由(+)运算符表示的，在普通的Prolog子句和查询中，(+)运算符已经被用于普通的否定作为失败。
因此，让我们首先解释一下(+)在DCGs中是如何工作的。如果您有以下形式的产生式规则：
A --> B, \+C, D.然后将其转换为：
A(I,O) :- B(I,X), \+ C(X,_), D(X,O).这意味着尝试解析C DCG目标，但不实际使用输入列表。现在，如果需要的话，它可以用来替换cut，并且它给人更多一点声明的感觉。为了解释这个想法，让我们假设with有一个没有ws//0的语法。因此，表达式的原始子句集//1将是：
expressions([E|Es]) --> expression(E), !, expressions(Es).
expressions([]) --> [].通过否定，我们可以将其转换为下面的无切割形式：
expressions([E|Es]) --> expression(E), expressions(Es).
expressions([]) --> \+ expression(_).不幸的是，上面的变体效率很低，因为解析表达式的尝试被进行了两次。一次在第一个规则中，然后在第二个规则中进行否定。但您可以执行以下操作，并且只检查表达式开头的否定：
expressions([E|Es]) --> expression(E), expressions(Es).
expressions([]) --> \+ symbol(_), \+ number(_), \+ "(", \+ "'".如果你尝试否定，你会发现你得到了一个相对严格的解析器。如果您试图解析输入的最大前缀，并且想要检测一些错误，这一点很重要。试一试：
?- phrase(expressions(X),"'",Y).在检查表达式的第一个符号的否定版本中，您应该会失败。因此，在cut和cut free版本中，您将成功处理空列表。
但你也可以用另一种方式来处理错误，我只是做了一个错误的例子来强调一下否定版本是如何工作的。
在其他设置中，例如CYK解析器，可以使否定相当有效，它可以使用已放置在图表中的信息。
诚挚的问候
https://stackoverflow.com/questions/6358556
复制相似问题