使用 DCG [SICStus] 解析语法

Question

到目前为止，我必须解析一个广泛的语法（为了创建一个语法分析器），问题是我在代码的某处得到了冗余，但我不知道它在哪里。

部分语法；

Grammar_types

Type :: =     Basic_Type
            | "PP" "(" Type ")"
            | Type "*" Type
            | "struct" "("    (Ident ":" Type)+","    ")"
            | "(" Type ")" .


Basic_Type :: = "ZZ"| "BOOL" | "STRING" | Ident .

我尝试在没有 DCG 的情况下分析这个语法，解析示例 Id :: = Id ((Id) * ",") *

Example_1

"id","id_0(id1,id2,..)"

Code_1

Entete_ (ID, Id, Ids) - atom_concat(XY,')', ID), 
                        atom_concat(XX,Ids, XY),check_ids(Ids),
                        atom_concat(Id,'(',XX),check_id(Id) ,!.
...

但在一些搜索中，我发现 DCG 是最有效的解析器之一，所以我回来获取下面的代码；

Code_2

type(Type) -->     "struct(", idents_types(Type),")"
                 | "PP(",ident(Type),")"
                 | "(",type(Type),")"
                 | type(Type),"*",type(Type)
                 | basic_type(Type)
                 | "error1_type".

...

Example_Syntaxe ;

"ZZ" ; "PP(ZZ*STRING)" ; "struct(x:personne,struct(y:PP(PP))" ; "ZZ*ZZ" ...

测试

| ?- phrase(type(L),"struct(aa:struct())").
! Resource error: insufficient memory
% source_info

我认为问题在这里 (idents_types)

| ?- phrase(idents_types(L),"struct(aa:STRING)").
    ! Resource error: insufficient memory

预期结果

     | ?- type('ZZ*struct(p1:STRING,p2:PP(STRING),p3:(BOOL*PP(STRING)),p4:PP(personne*BOOL))').
p1-STRING
STRING
p2-PP(STRING)
STRING
p3-(BOOL*PP(STRING))
STRING
BOOL
p4-PP(personne*BOOL)
BOOL
personne
ZZ
yes

所以我的问题是，为什么我会收到冗余错误，我该如何解决？

Answer 1

您在类型//1 上有一个 left recursion。

type(Type) --> ... | type(Type),"*",type(Type) | ...

您可以查看 this question 了解更多信息。

DCG 借用的自上而下的解析器必须具有先行驱动正确方向分析的符号。

如上文 link 所示，此问题的通常解决方案是引入一个服务非终结符，该服务非终结符离开了罪魁祸首规则的关联递归应用程序，或者是 epsilon（终止递归）。

一个epsilon规则写成

rule --> [].

转换可能需要相当多的思考...在 this answer 中，我建议采用自下而上的替代实现方式，如果语法无法转换，对于实际或理论问题（LR 语法），这可能是值得的比 LL 更通用）。

您可能想尝试这种头脑简单的转换，但可以肯定的是它留下了一些有待解决的细节。

type([Type,T]) --> "struct(", idents_types(Type),")", type_1(T)
                 | "PP(",ident(Type),")", type_1(T)
                 | "(",type(Type),")", type_1(T)
                 | basic_type(Type), type_1(T)
                 | "error1_type", type_1(T).
type_1([Type1,Type2,T]) --> type(Type1),"*",type(Type2), type_1(T).
type_1([]) --> [].

编辑

我修复了您和我的代码中的几个问题。现在它解析示例...

type([Type,T]) --> "struct(", idents_types(Type), ")", type_1(T)
                 | "PP(", type(Type), ")", type_1(T)
                 | "(", type(Type), ")", type_1(T)
                 | basic_type(Type), type_1(T)
                 | "error1_type", type_1(T).

% my mistake here...
type_1([]) --> [].
type_1([Type,T]) --> "*",type(Type), type_1(T).

% the output Type was unbound on ZZ,etc
basic_type('ZZ') --> "ZZ".
basic_type('BOOL') --> "BOOL".
basic_type('STRING') --> "STRING".
basic_type(Type) --> ident(Type).

% here would be better to factorize ident(Ident),":",type(Type)
idents_types([Ident,Type|Ids]) -->   ident(Ident),":",type(Type),",",
                                     idents_types(Ids).
idents_types([Ident,Type])     -->   ident(Ident),":",type(Type).
idents_types([])               -->   []. 

% ident//1 forgot to 'eat' a character
ident(Id) --> [C], { between(0'a,0'z,C),C\=0'_},ident_1(Cs),{ atom_codes(Id,[C|Cs]),last(Cs,L),L\=0'_}.
ident_1([C|Cs]) --> [C], { between(0'a,0'z,C);between(0'0,0'9,C);C=0'_ },
                    ident_1(Cs).
ident_1([])     --> [].

使用 DCG [SICStus] 解析语法

Parsing grammar using DCG [SICStus]

prolog

dcg