在Prolog中解析而无需削减？

| 我在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的软键/确定的选择的感兴趣的答案中也将是。     
2020-02-24 4 条评论
分享

没有找到相关结果

    已邀请:

    催备南菠亨

            削减并不是为了提高效率，而是致力于第一个解决方案（请参阅！/ 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.
    显然，在这种情况下，只需要由形成令牌的最长字符序列组成的第一个解决方案。给定上面的示例，因此我不同意\“ false \”：expression // 1模棱两可，因为number // 1和symbolr // 1是。在Mercury中，可以使用确定性声明cc_nondet提交解决方案（如果有）。     
    2020-02-24 0 0
    分享

    炬卤遁蝎变

            您在这里遇到了一个非常深层次的问题。在削减的地方 添加了注释“最长输入匹配项”。但是你实际上所做的是承诺 到第一个解决方案，它将为非终端non2ѭ（但不一定为
    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.
        
    2020-02-24 0 0
    分享

    芭隘的盘石

            您可以使用已经在解析表达式语法（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目标，但实际上并未消耗输入列表。现在，如果需要的话，它可以用来代替切口，它给人的是更具声明性的感觉。为了解释这个想法，让我们假设的语法没有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 cut版本中，您将获得空白列表的成功。 但是您也可以用另一种方式处理错误，我仅以错误示例为例，以突出显示否定版本的工作方式。 在其他设置中，例如CYK解析器，可以使求反非常有效，它可以使用已放置在图表中的信息。 最好的祝福     
    2020-02-24 0 0
    分享
    为什么被折叠? 0 个回复被折叠

    要回复问题请先登录或注册

    或代码 OrCode.com 备案号：粤ICP备15020848号-1
    Escape time: 0.057788848876953