use*_*588 4 parsing prolog dcg failure-slice
我必须编写 parse(Tkns, T) ，它以标记列表的形式接受数学表达式并找到 T，并返回一个表示抽象语法的语句，尊重操作顺序和关联性。
例如，
?- parse( [ num(3), plus, num(2), star, num(1) ], T ).
T = add(integer(3), multiply(integer(2), integer(1))) ;
No
我试图实现 + 和 * 如下
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)
).
哪个找到正确的答案，但也返回不遵循关联性或操作顺序的答案。
前任）
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 等）并且所有数字都是整数。提示代码的结构类似于语法
<expression> ::= <expression> + <term>
| <expression> - <term>
| <term>
<term> ::= <term> * <factor>
| <term> / <factor>
| <factor>
<factor> ::= num
| ( <expression> )
只有 negate 也实现了。
Edit2：我找到了一个用 Prolog ( http://www.cs.sunysb.edu/~warren/xsbbook/node10.html )编写的语法解析器。有没有一种方法可以修改它以打印语法的左手推导（“打印”，即 Prolog 解释器将输出“T=[正确答案]”）
删除左递归将推动您转向基于 DCG 的语法。
但是有一个有趣的替代方法：实现自下而上的解析。
这在 Prolog 中有多难？好吧，正如 Pereira 和 Shieber 在他们精彩的书“序言和自然语言分析”中所展示的那样，真的很容易：从第 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
在修复您的程序之前，先看看您是如何识别问题的！你假设一个特定的句子只有一个语法树，但你得到了两个。所以本质上，Prolog 帮助您找到了错误！
这是 Prolog 中一个非常有用的调试策略：查看所有答案。
接下来是您如何编码语法的具体方式。事实上，你做了一些非常聪明的事情：你基本上编码了一个左递归语法——然而你的程序终止于一个固定长度的列表！那是因为您在每个递归中都表明中间必须至少有一个元素作为运算符。因此，对于每个递归，必须至少有一个元素。那没关系。然而，这种策略本质上是非常低效的。因为，对于规则的每次应用，它都必须考虑所有可能的分区。
另一个缺点是您不能再从语法树中生成句子。也就是说，如果您将定义用于：
?- parse(S, add(add(integer(1),integer(2)),integer(3))).
原因有二：一是目标T = add(...,...)为时已晚。只需将它们放在append/3目标前面的开头即可。但更有趣的是，现在append/3并没有终止。这是相关的故障切片（有关更多信息，请参阅链接）。
parse([num(X)], integer(X)) :- false。 解析（Tkns，T）：- （ T = 添加（T1，T2）， append(E1, [plus|E2], Tkns), false,parse(E1, T1),parse(E2, T2), ; false ,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）：- 短语（expr（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 为您思考！