将语法转换为序言

Question

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

S -> T S | T

T -> 字符 F 分号 | int F 分号

F -> 编号 | id G

G -> 逗号 F

对于 "char id semicolon" 或 "int id comma id semicolon char id semicolon" 之类的事情 return 如此有效。

我正试图将它变成一个序言程序来识别这个语法。我到目前为止是：

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 comma id semicolon"。我不知道如何制作它所以它在分号之前有一个可变数量的 "id comma id" ，或者甚至在第一个之后有一个全新的变量定义。此站点上关于同一事物的其他问题通常必须处理像这样设置的语法，而不是那些可以具有可变输入量的语法。

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

其次，如何让它识别可变数量的 "id" 后跟逗号。所以如果我想让它识别 "char id semicolon" 以及 "char id comma id semicolon".

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, []).

将语法转换为序言

Converting grammar into prolog

grammar

prolog