解析Prolog中的表达式并返回抽象语法 [英] Parsing an expression in Prolog and returning an abstract syntax

问题描述

我必须编写parse(Tkns，T)，它以令牌列表的形式接收数学表达式并找到T，然后返回表示抽象语法的语句，并尊重操作的顺序和关联性.

I have to write parse(Tkns, T) that takes in a mathematical expression in the form of a list of tokens and finds T, and return a statement representing the abstract syntax, respecting order of operations and associativity.

例如

?- parse( [ num(3), plus, num(2), star, num(1) ], T ).

T = add(integer(3), multiply(integer(2), integer(1))) ;
No

我尝试如下实现+和*

I've attempted to implement + and * as follows

parse([num(X)], integer(X)).
parse(Tkns, T) :-
  (  append(E1, [plus|E2], Tkns),
     parse(E1, T1),
     parse(E2, T2),
     T = add(T1,T2)
  ;  append(E1, [star|E2], Tkns),
     parse(E1, T1),
     parse(E2, T2),
     T = multiply(T1,T2)
  ).

找到正确答案后，还会返回不遵循关联性或操作顺序的答案.

Which finds the correct answer, but also returns answers that do not follow associativity or order of operations.

ex)

parse( [ num(3), plus, num(2), star, num(1) ], T ). 

也返回

mult(add(integer(3), integer(2)), integer(1))

和

parse([num(1), plus, num(2), plus, num(3)], T)

当只返回前者时，返回等价于1 + 2 + 3和1+(2 + 3).

returns the equivalent of 1+2+3 and 1+(2+3) when it should only return the former.

有什么办法可以使它正常工作吗?

Is there a way I can get this to work?

更多信息:我只需要实现+，-，*，/，求反(-1，-2等)，所有数字都是整数.提示该代码的结构与语法类似

more info: I only need to implement +,-,*,/,negate (-1, -2, etc.) and all numbers are integers. A hint was given that the code will be structured similarly to the grammer

<expression> ::= <expression> + <term>
              |  <expression> - <term>
              |  <term>

      <term> ::= <term> * <factor>
              |  <term> / <factor>
              |  <factor>

    <factor> ::= num
              |  ( <expression> )

仅同时实现了求反.

Edit2:我发现了用Prolog( http://www.cs.sunysb.edu/~warren/xsbbook/node10.html ).有什么办法可以修改它以打印语法的左手派生(打印"，即Prolog解释器将输出"T = [正确答案]")

I found a grammar parser written in Prolog (http://www.cs.sunysb.edu/~warren/xsbbook/node10.html). Is there a way I could modify it to print a left hand derivation of a grammar ("print" in the sense that the Prolog interpreter will output "T=[the correct answer]")

推荐答案

删除左递归将带您走向基于DCG的语法.

Removing left recursion will drive you towards DCG based grammars.

但是有一种有趣的替代方法:实现自下而上解析.

But there is an interesting alternative way: implement bottom up parsing.

在Prolog中这有多难?好吧，正如佩雷拉(Pereira)和希伯(Shieber)在他们的精彩著作中所展示的 序言和自然语言分析"真的很容易:从6.5章起

How hard is this in Prolog ? Well, as Pereira and Shieber show in their wonderful book 'Prolog and Natural-Language Analysis', can be really easy: from chapter 6.5

默认情况下，Prolog提供从上到下，从左到右的回溯解析算法，用于 DCG.

Prolog supplies by default a top-down, left-to-right, backtrack parsing algorithm for DCGs.

众所周知，这种自上而下的解析算法将循环运行 左递归规则(请参阅程序2.3的示例).

It is well known that top-down parsing algorithms of this kind will loop on left-recursive rules (cf. the example of Program 2.3).

尽管有一些技术可用- 能够从上下文无关的语法中删除左递归，但是这些技术不是 可以很容易地推广到DCG，而且它们可以通过以下方式增加语法大小: 大因素.

Although techniques are avail- able to remove left recursion from context-free grammars, these techniques are not readily generalizable to DCGs, and furthermore they can increase grammar size by large factors.

作为替代方案，我们可以考虑实现自下而上的解析方法 直接在Prolog中.在各种可能性中，我们将在这里考虑左角 方法是它对DCG的一种改进.

As an alternative, we may consider implementing a bottom-up parsing method directly in Prolog. Of the various possibilities, we will consider here the left-corner method in one of its adaptations to DCGs.

为便于编程，左角DCG解释器的输入语法以DCG表示法的细微变化表示.的右侧 规则以列表形式而不是文字的结合形式给出.因此，规则是单位从句 的形式，例如

For programming convenience, the input grammar for the left-corner DCG interpreter is represented in a slight variation of the DCG notation. The right-hand sides of rules are given as lists rather than conjunctions of literals. Thus rules are unit clauses of the form, e.g.,

s ---> [np, vp].

或

optrel ---> [].

术语由单词(w，PT)形式的字典单位从句引入.

Terminals are introduced by dictionary unit clauses of the form word(w,PT).

很显然，考虑完成本次讲座，该书可免费免费获得 (请参见信息页面中的最后一本书).

Clearly, consider to complete the lecture, the book is freely available (see the last book entry in info page).

现在让我们尝试编写一个自底向上的处理器:

Now let's try writing a bottom up processor:

:- op(150, xfx, ---> ).

parse(Phrase) -->
    leaf(SubPhrase),
    lc(SubPhrase, Phrase).

leaf(Cat) --> [Word], {word(Word,Cat)}.
leaf(Phrase) --> {Phrase ---> []}.

lc(Phrase, Phrase) --> [].

lc(SubPhrase, SuperPhrase) -->
    {Phrase ---> [SubPhrase|Rest]},
    parse_rest(Rest),
    lc(Phrase, SuperPhrase).

parse_rest([]) --> [].
parse_rest([Phrase|Phrases]) -->
    parse(Phrase),
    parse_rest(Phrases).

% that's all! fairly easy, isn't it ?

% here start the grammar: replace with your one, don't worry about Left Recursion
e(sum(L,R)) ---> [e(L),sum,e(R)].
e(num(N)) ---> [num(N)].

word(N, num(N)) :- integer(N).
word(+, sum).

例如产生的

phrase(parse(P), [1,+,3,+,1]).
P = e(sum(sum(num(1), num(3)), num(1))) 

请注意，使用的左递归语法为e ::= e + e | num

note the left recursive grammar used is e ::= e + e | num

这篇关于解析Prolog中的表达式并返回抽象语法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！