语法分析器

Question

当涉及到prolog时，我是一个非常绿色的人，但本质上，我要做的是实现递归来解析语法规则。我所拥有的似乎在逻辑上是正确的，但显然不是因为我没有得到预期的结果。

下面是我要解析的规则：

S -> X Y Z
X -> a X | a
Y -> b Y | b
Z -> c Y | c

下面是prolog代码：

match(X, [X|T], T).

xs(X0, X):- match(a, X0, X).
xs(X0, X):- xs(X0, X).
ys(X0, X):- match(b, X0, X).
ys(X0, X):- ys(X0, X).
zs(X0, X):- match(c, X0, X).
zs(X0, X):- zs(X0, X).

s(X0, X):- xs(X0, X1), ys(X1, X2), zs(X2, X).

任何帮助，以了解我所做的错事，将不胜感激。

干杯。

Answer 1

也许语法翻译必须完成，比如

xs(X0, X):- match(a, X0, X).
xs(X0, X):- match(a, X0, X1), xs(X1, X).
...

我建议看看DCG必须提供的翻译：

s --> x,y,z.
x --> [a], x | [a].
y --> [b], y | [b].
z --> [c], y | [c].

查阅并列出结果

z(A, C) :-
    (   A=[c|B],
        y(B, C)
    ;   A=[c|C]
    ).

y(A, C) :-
    (   A=[b|B],
        y(B, C)
    ;   A=[b|C]
    ).

x(A, C) :-
    (   A=[a|B],
        x(B, C)
    ;   A=[a|C]
    ).

s(A, D) :-
    x(A, B),
    y(B, C),
    z(C, D).

Answer 2

在每个XS、YS、ZS方法中，递归调用时都需要再次调用match。