4

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

4

3 回答 3

7

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

但是有一个有趣的替代方法：实现自下而上的解析。

这在 Prolog 中有多难？好吧，正如 Pereira 和 Shieber 在他们的精彩著作“Prolog 和自然语言分析”中所展示的那样，这真的很容易：从第 6.5 章开始

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

众所周知，这种自上而下的解析算法将在左递归规则上循环（参见程序 2.3 的示例）。

虽然技术可以从上下文无关文法中去除左递归，但这些技术并不容易推广到 DCG，而且它们可以大大增加文法大小。

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

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

s ---> [np, vp].

或者

optrel ---> [].

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

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

现在让我们尝试编写一个自下而上的处理器：

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

于 2013-12-11T15:11:57.200 回答
5

在修复你的程序之前，看看你是如何发现问题的！你假设一个特定的句子只有一个语法树，但你得到了其中的两个。所以本质上，Prolog 帮助您找到错误！

这是 Prolog 中非常有用的调试策略：查看所有答案。

接下来是您对语法进行编码的具体方式。事实上，你做了一件非常聪明的事情：你基本上编码了一个左递归语法 - 然而你的程序终止了一个固定长度的列表！那是因为您在每个递归中指出中间必须至少有一个元素用作运算符。因此，对于每个递归，必须至少有一个元素。那也行。然而，这种策略本质上是非常低效的。因为，对于规则的每个应用，它都必须考虑所有可能的分区。

另一个缺点是您不能再从语法树中生成句子。也就是说，如果您将定义用于：

?- parse(S, add(add(integer(1),integer(2)),integer(3))).

有两个原因：第一是目标T = add(...,...)太晚了。只需将它们放在append/3目标前面的开头即可。但更有趣的是，现在append/3并没有终止。这是相关的故障片（有关更多信息，请参见链接）。

解析（[num（X）]，整数（X））：-假。
解析（Tkns，T）：-
  ( T = 添加(T1,T2),
     附加（E1，[加|E2]，Tkns），假，
     解析（E1，T1），
     解析（E2，T2），
  ;  假, T = multiply(T1,T2) ,
      append(E1, [star|E2], Tkns) ,
      parse(E1, T1) ,
      parse(E2, T2) ,     
  ）。

@DanielLyons 已经为您提供了“传统”解决方案，该解决方案需要来自正式语言的各种证明。但我会坚持你在程序中编码的语法 - 翻译成 DCG - 内容如下：

expr(integer(X)) --> [num(X)]。
expr(add(L,R)) --> expr(L), [plus], expr(R)。
expr(multiply(L,R)) --> expr(L), [star], expr(R)。

使用此语法时，?- phrase(expr(T),[num(1),plus,num(2),plus,num(3)]).它不会终止。这是相关的切片：

expr(integer(X)) --> {false} , [num(X)]。
expr(add(L,R)) --> expr(L), {false} , [plus], expr(R)。
expr(multiply(L,R)) --> {false} expr(L), [star], expr(R)。

所以必须改变的是这个微小的部分。请注意，规则“知道”它需要一个终端符号，唉，终端出现得太晚了。如果它只发生在递归之前！但事实并非如此。

有一种解决此问题的通用方法：添加另一对参数来编码长度。

解析（T，L）：-
   短语（表达式（T，L，[]），L）。

expr(integer(X), [_|S],S) --> [num(X)]。
expr(add(L,R), [_|S0],S) --> expr(L, S0,S1), [plus], expr(R, S1,S)。
expr(multiply(L,R), [_|S0],S) --> expr(L, S0,S1), [star], expr(R, S1,S)。

这是一种非常通用的方法，如果您有不明确的语法，或者您不知道您的语法是否不明确，那么这种方法会特别有用。只需让 Prolog 为您思考！

于 2013-12-11T06:59:57.423 回答
1

正确的方法是使用 DCG，但您的示例语法是左递归的，这是行不通的。这是什么：

expression(T+E) --> term(T), [plus], expression(E).
expression(T-E) --> term(T), [minus], expression(E).
expression(T)   --> term(T).

term(F*T) --> factor(F), [star], term(T).
term(F/T) --> factor(F), [div], term(T).
term(F)   --> factor(F).

factor(N) --> num(N).
factor(E) --> ['('], expression(E), [')'].

num(N) --> [num(N)], { number(N) }.

这与您的示例语法之间的关系应该是显而易见的，从左递归到右递归的转换也是如此。我不记得我的自动机课上关于最左边推导的细节，但我认为它只有在语法模棱两可的情况下才会发挥作用，我不认为这个是。希望一位真正的计算机科学家能够出现并澄清这一点。

除了 Prolog 将使用的之外，我认为生成 AST 没有任何意义。产生式左侧括号内的代码是构建 AST 的代码（例如T+E第一条expression//1规则中的 ）。如果不希望出现这种情况，请相应地调整代码。

从这里开始，展示您的parse/2API 非常简单：

parse(L, T) :- phrase(expression(T), L).

因为我们使用的是 Prolog 自己的结构，所以结果看起来没有实际那么令人印象深刻：

?- parse([num(4), star, num(8), div, '(', num(3), plus, num(1), ')'], T).
T = 4* (8/ (3+1)) ;
false.

如果您喜欢使用，可以显示更多 AST-y 输出write_canonical/2：

?- parse([num(4), star, num(8), div, '(', num(3), plus, num(1), ')'], T),
   write_canonical(T).
*(4,/(8,+(3,1)))
T = 4* (8/ (3+1)) a

该部分*(4,/(8,+(3,1)))是 的结果write_canonical/1。您可以使用以下方法直接评估is/2：

?- parse([num(4), star, num(8), div, '(', num(3), plus, num(1), ')'], T),
   Result is T.
T = 4* (8/ (3+1)),
Result = 8 ;
false.
于 2013-12-11T06:02:07.433 回答