如何在Prolog中实现CFG？

Question

我正在尝试在序言中为此语法实现一个解析器：

Lines → Line ; Lines | Line
Line → Num , Line | Num
Num → Digit | Num
Digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

代码是：

parse(X) :- lines([X|T],T).

lines(X,A) :- line(X, Y), simecolon(Y, Z), lines(Z, A).
lines(X, Y) :- line(X, Y).

line(X, A) :- num(X, Y), comma(Y, Z), line(Z, A).
line(X, Y) :- num(X, Y).

%num(X, Y) :- num(X, Y).
%num(X, A) :- digit(X,A).
%num(X, Y) :- digit(X,T), num(T,Y).
num(X, Y) :- digit(X,Y).

simecolon([';' | T], T).
comma([',' | T], T).

digit([X | T], T) :-
   X = '0';
   X = '1';
   X = '2';
   X = '3';
   X = '4';
   X = '5';
   X = '6';
   X = '7';
   X = '8';
   X = '9'.

如果语法中的句子或列表，代码不会给出 true。例如，这应该是正确的，但代码给出错误：

?- parse(['3', '2', ',', '0', ';', '1', ',', '5', '6', '7', ';', '2']).

任何人都可以帮我编写这段代码吗？

Answer 1

了解如何使用 Prolog 的调试器！事情很快就会出错：

(1) 1 CALL  parse(['3', '2', ',', ...])
(2) 2 CALL  lines([['3', '2', ...]|_755], _755)

你的 parse/1 应该只是

parse(Cs) :- lines(Cs, []).

然后取消注释 num/2 中的递归子句，给出

num(X, Y) :- digit(X,T), num(T,Y).
num(X, Y) :- digit(X,Y).

一切正常！