prolog - 将语法转换为序言

Question

所以我试图转换一种用编程语言定义变量定义的语法。这是我的第一个序言，它与典型的语言非常不同，所以我很困惑。语法如下:

S -> T S |

T -> char F 分号 | int F 分号

F -> id | id G

G -> 逗号 F

因此，对于“char id semicolon”或“int id comma id semicolon char id semicolon”之类的内容，它会有效地返回 true。

我试图将其变成一个序言程序来识别这个语法。到目前为止我所拥有的是:

type([char|T],T).
type([int|T],T).
def([id|T], T).
com([comma|T], T).
semi([semicolon|T], T).

vardef(L,S) :-
  type(L,S1),
  def(S1,S2),
  comma(S2,S3),
  def(S3,S4),
  semi(S4,S).

variable_definition(L) :-
  vardef(L,[]).

但是，这显然只能识别特定的“int/char id 逗号 id 分号”。我不知道如何制作它，因此它在分号之前有一个可变数量的“id comma id”，或者甚至在第一个之后有一个完整的新变量定义。该网站上有关同一事物的其他问题通常必须处理像这样设置的语法，而不是可以具有可变数量输入的语法。

编辑:所以问题有两个方面。首先，我如何使它能够识别两个不同的变量定义，一个接一个。我认为我必须更改最后一行才能完成此操作，但我不确定如何更改。

第二，如何让它识别可变数量的“id”，后跟逗号。因此，如果我希望它识别“char id 分号”以及“char id 逗号 id 分号”。

Answer 1

在 Prolog 中表达此类语法的最自然方式是使用 Prolog 的 DCG 表示法:

S -> T S | T
T -> char F semicolon | int F semicolon
F -> id | id G
G -> comma F

s --> t, s | t.
t --> [char], f, [semicolon] | [int], f, [semicolon].
f --> [id] | [id], g.
g --> [comma], f.

DCG 的好处在于它更直接地表达符号。然后您可以使用 phrase/2 来运行它:

| ?- phrase(s, [char, id, semicolon]).

true ? ;

no

您可以使用此语法在某种程度上生成有效的短语:

| ?- phrase(t, S).

S = [char,id,semicolon] ? ;

S = [char,id,comma,id,semicolon] ? ;

S = [char,id,comma,id,comma,id,semicolon] ? ;
...

但是...

| ?- phrase(s, S).

Fatal Error: local stack overflow (size: 16384 Kb, reached: 16384 Kb,
environment variable used: LOCALSZ)

单词s的定义方式是不终止的。我们可以通过稍后移动递归案例来解决这个问题:

s --> t | t, s.

然后:

| ?- phrase(s, S).

S = [char,id,semicolon] ? ;

S = [char,id,comma,id,semicolon] ? ;

S = [char,id,comma,id,comma,id,semicolon] ? ;
...

您可以通过列出谓词的 Prolog 代码来了解这是如何以标准表示法实现的:

| ?- listing(t).

% file: user

t(A, B) :-
        (   A = [char|C],
            f(C, D),
            D = [semicolon|B]
        ;   A = [int|E],
            f(E, F),
            F = [semicolon|B]
        ).

yes
| ?-

您可以更简洁地写为:

t([char|T], B) :-
    f(T, [semicolon|B]). 
t([int|T], B) :-
    f(T, [semicolon|B]).

这将被称为t(L, [])(相当于phrase(t, L)的结果)。

---

如果我们列出其余谓词，您可以按照您要求的形式获得完整的解决方案:

| ?- listing.
s(A, B) :-
        (   t(A, B)
        ;   t(A, C),
            s(C, B)
        ).

t(A, B) :-
        (   A = [char|C],
            f(C, D),
            D = [semicolon|B]
        ;   A = [int|E],
            f(E, F),
            F = [semicolon|B]
        ).

f(A, B) :-
        (   A = [id|B]
        ;   A = [id|C],
            g(C, B)
        ).

g([comma|A], B) :-
        f(A, B).

稍微重构(使其不那么冗长):

s(L, S) :-
    t(L, S).
s(L, S) :-
    t(L, S1),
    s(S1, S).

t([char|T], S) :-
    f(T, [semicolon|S]). 
t([int|T], S) :-
    f(T, [semicolon|S]).

f([id|S], S).
f([id|S1], S) :-
    g(S1, S).

g([comma|S1], S) :-
    f(S1, S).

从这里您可以调用:variable_definition(D) :- s(D, [])。