18

我在 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 的软切/承诺选择感兴趣的答案。

4

3 回答 3

8

削减不是为了提高效率，而是致力于第一个解决方案（参见 !/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 是模棱两可的，因为 number//1 和 symbolr//1 是模棱两可的。在 Mercury 中，您可以使用确定性声明 cc_nondet 来提交解决方案（如果有）。

于 2011-06-15T17:08:20.587 回答
7

您在这里遇到了一个非常深刻的问题。在剪切的地方，您添加了注释“最长输入匹配”。但是您实际上所做的是致力于第一个解决方案，该解决方案将为非终端产生“最长输入匹配”，ws//0但不一定为expression//1.

许多编程语言根据最长的输入匹配来定义它们的标记。这通常会导致非常奇怪的效果。例如，在许多编程语言中，一个数字可能紧跟一个字母。Pascal、Haskell、Prolog 和许多其他语言就是这种情况。例如 if a>2then 1 else 2是有效的 Haskell。有效序言：X is 2mod 3.

鉴于此，定义一种完全不依赖于这些特性的编程语言可能是一个好主意。

当然，然后您想优化语法。但我只能建议首先从一个明确的定义开始。

至于效率（和纯度）：

eos([],[]).

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

ws --> nows.
ws --> [W], {code_type(W, space)}, ws.
于 2011-06-15T17:02:00.840 回答
4

您可以使用已经在解析表达式语法 (PEG) 中找到其位置但在 DCG 中也可用的构造。即对DCG目标的否定。在 PEG 中，带有参数的感叹号 (!) 用于否定，即 ! e. 在 DCG 中，对 DCG 目标的否定由 (\+) 运算符表示，在普通 Prolog 子句和查询中，它已经用于普通否定作为失败。

所以让我们首先解释一下 (\+) 在 DCG 中是如何工作的。如果您有以下形式的生产规则：

 A --> B, \+C, D.

然后将其翻译为：

 A(I,O) :- B(I,X), \+ C(X,_), D(X,O).

这意味着尝试解析 C DCG 目标，但没有实际使用输入列表。现在，如果需要，可以使用它来替换剪切，并且它给人一种更具声明性的感觉。为了解释这个想法，我们假设 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).

您应该在检查表达式的第一个符号的否定版本中失败。在剪辑版和免费剪辑版中，您将因此获得空列表的成功。

但是你也可以用另一种方式处理错误，我只是做了错误示例来强调否定版本的工作原理。

在其他设置中，例如 CYK 解析器，可以使否定非常有效，它可以使用已经放置在图表中的信息。

最好的祝福

于 2011-06-21T19:52:09.153 回答