Prolog Looping重做的 [英] Prolog Looping Redo's

问题描述

我正在尝试用Prolog(gnu)编写一个小程序，该程序将接受用户输入，并为问题这是该语法中的有效句子吗?"提供正确或错误的答案.在Prolog上找到可靠的文档时，我遇到了很多麻烦，如果有人有可靠的消息源将不胜感激.从我发现的情况来看，这段代码在大多数情况下应该有效.当我尝试跟踪执行时，会得到我不理解的奇怪结果.

I am trying to write a small program in Prolog(gnu) that will take user input and give true or false to the question "Is this a valid sentence in this grammar?" I have had a lot of trouble finding solid documentation on Prolog, and if anyone has a reliable source that would be appreciated. From what I have found, this code for the most part should work. When I try to trace the execution, I get strange results that I do not understand.

我现在使用的测试用例是当用户输入'a =(b + c)'时.问题在于从列表中删除最后一项会导致重做循环，我不确定为什么.

The test case I am working with now is when the user inputs 'a = ( b + c )'. The problem is that removing the last item from my list is causing a redo loop and I am unsure why.

% Grammar:
% <assign> → <id> = <expr>
% <expr> → <id> <op> <expr>
%        | ( <expr> )
%        | <id>  
% <op> → * | + | / | - 
% <id> → a | b | c 

op('+').
op('-').
op('*').
op('/').


id(a).
id(b).
id(c).
id('a').
id('b').
id('c').
id([a]).
id([b]).
id([c]).



%
% Determine if the Sentence is valid according to the grammar
%
% param (in): Sentence - A list of symbols that make up the sentence to be evaluated
%
assign(Sentence) :-
  list(Sentence), length(Sentence, Length), >=(Length, 3),   %precondition test
  =(Sentence, [First, Second | Tail] ),
  id(First),
  =(Second, '='),
  expr(Tail).

% Test if the list of symbols is a valid expression
expr(X) :-
  length(X, Length), Length >= 1,
  =(X, [First | Tail] ),

  ( Length = 1 ->
      id(X)

  ; Length >= 3, =(First,'(') ->
    =(Tail, [Second | Tail2] ),
    last(Last, Tail),
    append(Middle, [_], Tail),

    =(Last, ')'),
    expr(Middle)

  ; =(Tail, [Second | Tail2] ),
    id(First), 
    op(Second),
    expr(Tail2)
  ).

%
% Input a sentence, then decompose it into a list of symbols. 
% User input should be quoted, e.g., Enter a sentence: 'A = B * C'
%
% param (out): SentenceList  The list of symbols input by the user is bound to this variable
%
read_sentence(SentenceList) :-
   print('Enter a sentence: '),
   read_token(Input),
   write_term_to_chars(InputList, Input, []),
   delete(InputList, ' ', SentenceList).

%
% Start the program
%
start :-
  read_sentence(Sentence),
  assign(Sentence).

推荐答案

Prolog的语法可以简化符号处理.这是我编写代码的方式:

Prolog has a syntax that make simpler symbolic processing. Here is how I would wrote the code:

assign([First, '=' | Expr]) :-
    id(First),
    expr(Expr).

expr([First | Tail]) :-
    id(First), 
    right(Tail).
expr(['(' | Rest]) :-
    append(Expr, [')'|Follow], Rest),
    expr(Expr),
    right(Follow).

right([]).
right([Op|Expr]) :-
    op(Op),
    expr(Expr).

请注意使用模式匹配，而不是基于长度2的过程检查，等等

note the use of pattern matching, instead of the procedural check based on length/2, etc

assign([First, '=' | Expr]) :-
...

这意味着:如果参数是第二个位置带有'='的列表，而尾部是我们命名为Expr的列表，则仅使用此子句 .

this means: use this clause only if the argument is a list with '=' in second position and the tail is a list we name Expr.

(关于语法:经常，我们不需要引用原子，但是规则有些复杂.例如，这是一个有效的查询

(about syntax: often we don't need to quote atoms, but the rules are somewhat complex. For instance, this is a valid query

?- assign([c,=,a,+,b]).

无需在此处引用原子，因此代码可以为assign([First, = | Expr]) :- ...)

No need to quote atoms here, so the code could be assign([First, = | Expr]) :- ...)

然后，主体对第一个列表的元素(即id(First))和Expr进行适当的检查.

Then the body issues the appropriate check for first list'element (i.e. id(First)) and the Expr.

为了获得括号之间的Expr，我使用了惯用的方法

To get the Expr between parenthesis, I used an idiomatic approach

expr(['(' | Rest]) :-
    append(Expr, [')'|Follow], Rest),
...

只有在Rest包含Expr后跟')'的情况下，此append/3才能成功.

this append/3 can succeed only if Rest contains an Expr followed by ')'.

我认为您的原始方法错过了right(Follow). 我们需要它，因为语法在操作符之后是递归的.

I think your original approach missed the right(Follow). We need it because the grammar is recursive, after an operator...

这篇关于Prolog Looping重做的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！