blocks|key|866827|text|你在这里碰到了一个相当深的问题。在裁剪的位置，您添加了注释“最长输入匹配”。但您实际做的是提交第一个解决方案，它将为非终端ws//0生成“最长的输入匹配”，但不一定为expression//1生成“最长的输入匹配”。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|866828|许多编程语言基于最长的输入匹配来定义它们的标记。这通常会导致非常奇怪的效果。例如，在许多编程语言中，数字后面可能紧跟一个字母。Pascal、Haskell、Prolog和许多其他语言就是这种情况。例如，if+a>2then+1+else+2是有效的Haskell。有效的Prolog：X+is+2mod+3.|866829|考虑到这一点，最好定义一种编程语言，使其完全不依赖于这些特性。|866830|当然，你会想要优化语法。但我只能建议从一个明确的定义开始。|866831|至于效率(和纯度)：|866832|eos([],[]).

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

ws+-->+nows.
ws+-->+[W],+{code_type(W,+space)},+ws.|code-block|syntax|javascript|866833|entityMap^0|1P|5|2B|D|0|2T|J|3Y|C|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|U|8|@$9|V|A|W|B|C]|$9|X|A|Y|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|Z|8|@$9|10|A|11|B|C]|$9|12|A|13|B|C]]|D|@]|E|$]]|$1|H|3|I|5|6|7|14|8|@]|D|@]|E|$]]|$1|J|3|K|5|6|7|15|8|@]|D|@]|E|$]]|$1|L|3|M|5|6|7|16|8|@]|D|@]|E|$]]|$1|N|3|O|5|P|7|17|8|@]|D|@]|E|$Q|R]]|$1|S|3|-4|5|6|7|18|8|@]|D|@]|E|$]]]|T|$]]

You are touching a quite deep problem here. At the place of the cut you have
added the comment "longest input match". But what you actually did was to commit
to the first solution which will produce the "longest input match" for the non-terminal <code>ws//0</code> but not necessarily for <code>expression//1</code>.

Many programming languages define their tokens based on the longest input match. This often leads to very strange effects. For example, a number may be immediately
followed by a letter in many programming languages. That's the case for Pascal, Haskell,
Prolog and many other languages. E.g. <code>if a>2then 1 else 2</code> is valid Haskell.
Valid Prolog: <code>X is 2mod 3.</code>

Given that, it might be a good idea to define a programming language such that it does not depend on such features at all.

Of course, you would then like to optimize the grammar. But I can only recommend to start with a definition that is unambiguous in the first place.

As for efficiency (and purity):

<pre><code>eos([],[]).

nows --&gt; call(eos).
nows, [W] --&gt; [W], { code_type(W, nospace) }.

ws --&gt; nows.
ws --&gt; [W], {code_type(W, space)}, ws.
</code></pre>

blocks|key|649593|text|使用cut不是为了提高效率，而是为了提交第一个解决方案(参见!/0："single+solution:+longest+match“旁边的注释)。如果你注释掉!/0，你会得到例如：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|649594|?-+parse("abc",+E).
E+=+[s(abc)]+;
E+=+[s(ab),+s(c)]+;
E+=+[s(a),+s(bc)]+;
E+=+[s(a),+s(b),+s(c)]+;
false.|code-block|syntax|javascript|649595|显然，在这种情况下，只需要由形成标记的最长字符序列组成的第一种解决方案。考虑到上面的例子，我不同意"false"：表达式//1是模棱两可的，因为数字//1和symbolr//1是模糊的。在水星中，您可以使用确定性声明cc_nondet来提交解决方案。|649596|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

The cut is not used for efficiency, but to commit to the first solution (see the comment next to the !/0: "single solution: longest input match"). If you comment out the !/0, you get for example:

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

It is clear that only the first solution, consisting of the longest sequence of characters that form a token, is desired in such cases. Given the example above, I therefore disagree with "false": expression//1 is ambiguous, because number//1 and symbolr//1 are. In Mercury, you could use the determinism declaration cc_nondet to commit to a solution, if any.

blocks|key|867091|text|您可以使用已经在解析表达式语法(PEGs)中找到其位置，但在DCGs中也可用的构造。即DCG目标的否定。在别号中添加感叹号(!)带参数用于否定，即！e.在DCG中，DCG目标的否定是由(%2B)运算符表示的，在普通的Prolog子句和查询中，(%2B)运算符已经被用于普通的否定作为失败。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|867092|因此，让我们首先解释一下(%2B)在DCGs中是如何工作的。如果您有以下形式的产生式规则：|867093|+A+-->+B,+\%2BC,+D.|code-block|syntax|javascript|867094|然后将其转换为：|867095|+A(I,O)+:-+B(I,X),+\%2B+C(X,_),+D(X,O).|867096|这意味着尝试解析C+DCG目标，但不实际使用输入列表。现在，如果需要的话，它可以用来替换cut，并且它给人更多一点声明的感觉。为了解释这个想法，让我们假设with有一个没有ws//0的语法。因此，表达式的原始子句集//1将是：|867097|expressions([E%7CEs])+-->+expression(E),+!,+expressions(Es).
expressions([])+-->+[].|867098|通过否定，我们可以将其转换为下面的无切割形式：|867099|expressions([E%7CEs])+-->+expression(E),+expressions(Es).
expressions([])+-->+\%2B+expression(_).|867100|不幸的是，上面的变体效率很低，因为解析表达式的尝试被进行了两次。一次在第一个规则中，然后在第二个规则中进行否定。但您可以执行以下操作，并且只检查表达式开头的否定：|867101|expressions([E%7CEs])+-->+expression(E),+expressions(Es).
expressions([])+-->+\%2B+symbol(_),+\%2B+number(_),+\%2B+"(",+\%2B+"'".|867102|如果你尝试否定，你会发现你得到了一个相对严格的解析器。如果您试图解析输入的最大前缀，并且想要检测一些错误，这一点很重要。试一试：|867103|?-+phrase(expressions(X),"'",Y).|867104|在检查表达式的第一个符号的否定版本中，您应该会失败。因此，在cut和cut+free版本中，您将成功处理空列表。|867105|但你也可以用另一种方式来处理错误，我只是做了一个错误的例子来强调一下否定版本是如何工作的。|867106|在其他设置中，例如CYK解析器，可以使否定相当有效，它可以使用已放置在图表中的信息。|867107|诚挚的问候|867108|entityMap^0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|1C|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|1D|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|1E|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|1F|8|@]|9|@]|A|$]]|$1|K|3|L|5|F|7|1G|8|@]|9|@]|A|$G|H]]|$1|M|3|N|5|6|7|1H|8|@]|9|@]|A|$]]|$1|O|3|P|5|F|7|1I|8|@]|9|@]|A|$G|H]]|$1|Q|3|R|5|6|7|1J|8|@]|9|@]|A|$]]|$1|S|3|T|5|F|7|1K|8|@]|9|@]|A|$G|H]]|$1|U|3|V|5|6|7|1L|8|@]|9|@]|A|$]]|$1|W|3|X|5|F|7|1M|8|@]|9|@]|A|$G|H]]|$1|Y|3|Z|5|6|7|1N|8|@]|9|@]|A|$]]|$1|10|3|11|5|F|7|1O|8|@]|9|@]|A|$G|H]]|$1|12|3|13|5|6|7|1P|8|@]|9|@]|A|$]]|$1|14|3|15|5|6|7|1Q|8|@]|9|@]|A|$]]|$1|16|3|17|5|6|7|1R|8|@]|9|@]|A|$]]|$1|18|3|19|5|6|7|1S|8|@]|9|@]|A|$]]|$1|1A|3|-4|5|6|7|1T|8|@]|9|@]|A|$]]]|1B|$]]

You could use a construct that has already found its place in Parsing Expression Grammars (PEGs) but which is also available in DCGs. Namely the negation of a DCG goal. In PEGs the exclamation mark (!) with an argument is used for negation, i.e. ! e. In DCG the negation of a DCG goal is expressed by the (\+) operator, which is already used for ordinary negation as failure in ordinary Prolog clauses and queries.

So lets first explain how (\+) works in DCGs. If you have a production rule of
the form:

<pre><code> A --&gt; B, \+C, D.
</code></pre>

Then this is translated to:

<pre><code> A(I,O) :- B(I,X), \+ C(X,_), D(X,O).
</code></pre>

Which means an attempt is made to parse the C DCG goal, but without actually consuming the input list. Now this can be used to replace the cut, if desired, and it gives a little bit more declarative feeling. To explain the idea lets assume that with have a grammar without ws//0. So the original clause set of expressions//1 would be:

<pre><code>expressions([E|Es]) --&gt; expression(E), !, expressions(Es).
expressions([]) --&gt; [].
</code></pre>

With negation we can turn this into the following cut-less form:

<pre><code>expressions([E|Es]) --&gt; expression(E), expressions(Es).
expressions([]) --&gt; \+ expression(_).
</code></pre>

Unfortunately the above variant is quite un-efficient, since an attempt to parse an expression is made twice. Once in the first rule, and then again in the second rule for the negation. But you could do the following and only check for the negation of the beginning of an expression:

<pre><code>expressions([E|Es]) --&gt; expression(E), expressions(Es).
expressions([]) --&gt; \+ symbol(_), \+ number(_), \+ "(", \+ "'".
</code></pre>

If you try negation, you will see that you get a relatively strict parser. This is important if you try to parse maximum prefix of input and if you want to detect some errors. Try that:

<pre><code>?- phrase(expressions(X),"'",Y).
</code></pre>

You should get failure in the negation version which checks the first symbol of the expression. In the cut and in the cut free version you will get success with the empty list as a result. 

But you could also deal in another way with errors, I have only made the error example to highlight a little bit how the negation version works.

In other settings, for example CYK parser, one can make the negation quite efficient, it can use the information which is already placed in the chart.

Best Regards

I found this nice snippet for parsing lisp in Prolog (from <a href="https://www.metalevel.at/lisprolog/" rel="nofollow noreferrer">here</a>):

<pre><code>ws --&gt; [W], { code_type(W, space) }, ws.
ws --&gt; [].

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

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

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

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

number([D|Ds]) --&gt; digit(D), number(Ds).
number([D]) --&gt; digit(D).

digit(D) --&gt; [D], { code_type(D, digit) }.

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

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

However expressions uses a cut. I'm assuming this is for efficiency. Is it possible to write this code so that it works efficiently without cut?

Would also be in interested answers that involve Mercury's soft-cut / committed choice.

Parsing in Prolog without cut?

我在Prolog中找到了这个解析lisp的很好的代码片段(来自)：ws --> [W], { code_type(W, space) }, ws.ws --> [].parse(String, Expr) :- phrase(expressions(Expr), String).expressions([E|Es]) ...

问在Prolog中不使用cut进行语法分析？
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在Prolog中不使用cut进行语法分析？EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在Prolog中不使用cut进行语法分析？
EN