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

问题描述

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

例如，

?- parse( [ num(3), plus, num(2), star, num(1) ], T ).T = 加(整数(3)，乘(整数(2)，整数(1)))；不

我尝试如下实现 + 和 *

parse([num(X)], integer(X)).解析(Tkns，T):-(追加(E1，[加|E2]，Tkns)，解析(E1，T1)，解析(E2，T2)，T = 添加(T1，T2);附加(E1，[星|E2]，Tkns)，解析(E1，T1)，解析(E2，T2)，T = 乘法(T1，T2)).

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

例如)

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) 的等价物.

有什么办法可以让它工作吗?

更多信息:我只需要实现 +、-、*、/、否定(-1、-2 等)，所有数字都是整数.给出了一个提示，代码的结构将与语法相似

<表达式>::= <表达式>+ <术语>|<表达>- <术语>|<术语><术语>::= <术语>* <因素>|<术语>/<因素>|<因素><因素>::= 数量|(<表达式>)

仅当也实现了否定.

Edit2:我找到了一个用 Prolog 编写的语法解析器 (http://www.cs.sunysb.edu/~warren/xsbbook/node10.html).有没有办法可以修改它以打印语法的左手推导(打印"，即 Prolog 解释器将输出T=[正确答案]")

解决方案

移除 左递归将推动您使用基于 DCG 的语法.

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

这在 Prolog 中有多难?好吧，正如 Pereira 和 Shieber 在他们精彩的书中所展示的那样Prolog 和自然语言分析"，非常简单:从第 6.5 章开始

<块引用>

Prolog 默认提供自上而下、从左到右的回溯解析算法DCG.

<块引用>

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

<块引用>

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

<块引用>

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

<块引用>

为方便编程，左角 DCG 解释器的输入语法以 DCG 符号的细微变化表示.的右侧规则以列表的形式给出，而不是文字的连词.因此规则是单元子句的形式，例如，

s --->[np，副总裁].

或

optrel --->[].

<块引用>

终端由 word(w,PT) 形式的字典单元子句引入.

考虑在继续之前完成讲座(在信息页面中按标题查找免费书籍条目).

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

:- op(150, xfx, ---> ).解析(短语)-->叶(副词)，lc(副短语，短语).叶(猫)-->[字]，{字(字，猫)}.叶(短语)-->{短语--->[]}.lc(短语，短语)-->[].lc(副词，超词)-->{短语--->[副短语|休息]},parse_rest(休息),lc(短语，超短语).parse_rest([]) -->[].parse_rest([短语|短语]) -->解析(短语)，parse_rest(短语).％ 就这样！相当容易，不是吗?% 这里开始语法:用你的替换，不用担心左递归e(总和(L，R))--->[e(L),sum,e(R)].e(num(N)) --->[数量(N)].单词(N，num(N)):-整数(N).字(+，总和).

例如产生

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

注意使用的左递归语法是e ::= e + e |编号

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.

For example,

?- 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 ). 

also returns

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

and

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

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?

Edit: 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> )

Only with negate implemented as well.

Edit2: 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]")

解决方案

Removing left recursion will drive you towards DCG based grammars.

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

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 supplies by default a top-down, left-to-right, backtrack parsing algorithm for DCGs.

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).

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.

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.

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].

or

optrel ---> [].

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

Consider to complete the lecture before proceeding (lookup the free book entry by title 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).

that for instance yields

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

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

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