将语法转换为prolog

Question

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

S - > TS | Ť

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

F - > id | id G.

G - >逗号F.

因此,对于像"char id semicolon"或"int id comma id semicolon char id semicolon"这样的东西,它会有效地返回.

我试图把它变成一个prolog程序来识别这个语法.到目前为止我所拥有的是:

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",或者甚至在第一个之后有一个全新的变量定义.关于同一件事,在这个网站上的其他问题通常必须处理像这样设置的语法,而不是那些可以有可变数量输入的语法.

编辑:所以问题是双重的.首先,我如何使它识别两个不同的变量定义,一个接一个.我想我必须改变最后一行才能完成这个,但我不确定如何.

其次,如何让它识别可变数量的"id",后跟逗号.因此,如果我希望它识别"char id semicolon"以及"char id comma id semicolon".

Answer 1

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

S - > TS | T
T - > char F分号| int F分号
F - > id | id G
G - >逗号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, []).