使用 DCG 解析表达式

Question

我尝试用 DCG 解析标识符列表，但我没能做到，

例子

                          ::=
                            |
                          __|____
                         |       |
                        Id     Id,'(',Ids,')'.
                                       _|_
                                      |   |
                                     Id   Id,

-

ids ::= id.
ids ::= id(id1,id2,...).

要验证的标识符示例

  exp1 = 'id_0'
  exp3 = 'id_1(i)'
  exp2 = 'id_2(i1,i2)'

代码编辑

id([Id]) --> [Id].
id([Id|Ids]) --> [Id,'('], ids(Ids), [')'].

ids([Id]) --> [Id].
ids([Id|Ids]) --> [Id], ids(Ids).

谁能告诉我问题出在哪里？

Answer 1

让我们先看看你目前描述的是什么（例如）id//1，使用最一般的查询：

?- phrase(id(Is), Ls).
Is = Ls, Ls = [_G884] ;
Is = [_G884|_G885],
Ls = [_G884, '(', ids(_G885), ')'].

尝试最一般的查询通常是了解有关关系的更多信息的好方法。在这种情况下，我们已经注意到两个非常重要的事情：

关于令牌列表 Ls，第一个解决方案显然 比预期的更通用。您添加到此程序（同时保留 logical-purity）的任何子句都无法消除此缺陷。因此，您需要使第一条规则更具体。
第二个答案描述的标记实际上与语法不匹配，因为它们包含具体标记ids(_)。这表明您将 DCG 规则名称与要描述的标记混合在一起。

首先，让我们首先集中描述我们想要描述的代币列表。这在一定程度上简化了代码，因为我们不必一次处理这么多事情。

我建议你从以下开始：

ids --> [id].
ids --> [id,'('], ids_, [')'].

ids_ --> ids, more_ids_.

more_ids_ --> [].
more_ids_ --> [,], ids_.

请注意允许我们指定 "more of the same" 的有用模式，它可以是 nothing 或 comma 然后 "the same".

我想您最终会使其更通用，例如，除了具体标记 id 之外，还接受其他标识符。从上面的代码中可以清楚地看出执行此操作的位置，我将其作为一个简单的练习。

请注意，我们已经可以使用它来查看我们是否正在描述仅个预期的令牌列表：

?- length(Ls, _), phrase(ids, Ls).
Ls = [id] ;
Ls = [id, '(', id, ')'] ;
Ls = [id, '(', id, ',', id, ')'] ;
Ls = [id, '(', id, '(', id, ')', ')'] ;
etc.

我正在使用 length/2 进行公平枚举。

一旦您确定您正在描述所有且仅描述您想要的标记列表，您就可以开始将这些标记列表与其他 Prolog 术语相关联。这往往会涉及到(=..)/2等项之间的关系。

Answer 2

我认为你错过了一个 DCG，当翻译成 Prolog 时，处理方块之间的符号作为 terminals。

所以，你的子句像

id([Id|Ids]) --> [Id,'(',ids(Ids),')'].

被视为失败，除非给出了终端的特定模式。让我们试试，在 SWI-Prolog 中：

1 ?- [user].
id([Id|Ids]) --> [Id,'(',ids(Ids),')'].
|: 
true.

2 ?- phrase(id(L), [me,'(',ids([1,2,3]),')']).
L = [me, 1, 2, 3].

您可以看到 ids/1 未作为非终端处理。

使用 DCG 解析表达式

parsing an expression using DCG

prolog

dcg