Prolog DCG：编写编程语言词法分析器

Question

Prolog DCG：编写编程语言词法分析器

7

目前我试图将词法分析器和语法分析器分开，基于书籍《Prolog and Natural Language Analysis》的建议，该书对词法分析/标记化并没有详细说明。所以我正在尝试，并且发现几个小问题，这表明我可能遗漏了一些显而易见的东西。

所有我的小型标记解析器似乎都工作得很好；目前这是我的代码片段：

:- use_module(library(dcg/basics)).

operator('(')  --> "(".      operator(')')  --> ")".
operator('[')  --> "[".      operator(']')  --> "]".
% ... etc.

keyword(array)    --> "array".
keyword(break)    --> "break".
% ... etc.

虽然有点重复，但似乎还是有效的。然后我有一些自己不完全满意的东西，希望能得到建议，但它们似乎也起作用:

id(id(Id)) -->
    [C],
    {
        char_type(C, alpha)
    },
    idRest(Rest),
    {
        atom_chars(Id, [C|Rest])
    }.
idRest([C|Rest]) -->
    [C],
    {
        char_type(C, alpha) ; char_type(C, digit) ; C = '_'
    },
    idRest(Rest).
idRest([]) --> [].

int(int(Int)) --> integer(Int).

string(str(String)) -->
    "\"",
    stringContent(Codes),
    "\"",
    {
        string_chars(String, Codes)
    }.
stringContent([C|Chars]) -->
    stringChar(C), stringContent(Chars).
stringContent([]) --> [].

stringChar(0'\n) --> "\\n".
stringChar(0'\t) --> "\\t".
stringChar(0'\") --> "\\\"".
stringChar(0'\") --> "\\\\".
stringChar(C) --> [C].

我的标记器的主要规则是这样的：

token(X) --> whites, (keyword(X) ; operator(X) ; id(X) ; int(X) ; string(X)).

它并不完美；我会看到 int 解析成 in,id(t)，因为 keyword(X) 在 id(X) 之前。所以我想这是第一个问题。

我更大的问题是我不知道如何将注释正确地集成到这种情况中。我尝试了以下方法：

skipAhead --> [].
skipAhead --> (comment ; whites), skipAhead.

comment --> "/*", anything, "*/".
anything --> [].
anything --> [_], anything.

token(X) --> skipAhead, (keyword(X) ; operator(X) ; id(X) ; int(X) ; string(X)).

这似乎不起作用；返回的解析结果（我得到了很多解析结果）似乎没有删除注释。我担心我的注释规则可能是不必要的低效率，并且可能会引起许多不必要的回溯。我还担心来自dcg/basics的whites//0是确定性的；然而，方程的那部分似乎是有效的，只是将其与跳过注释集成起来似乎行不通。

最后，我不知道如何将解析错误传播回带有行/列信息的用户。感觉好像我必须追踪和线程一些当前的行/列信息，并将其写入令牌，然后尝试重新构建行，如果我想做类似于llvm的事情。这合理吗？还是有一个“推荐做法”？

整个代码可以在此处找到。

- Daniel Lyons

对于comment//0感到紧张的好理由是：phrase(comment,"/**/*/")是正确的，但应该失败。 - false

2个回答

2

我有一段代码用于支持错误报告，但这段代码必须小心处理，需要在代码周围添加有意义的消息和“跳过规则”。但是，没有现成的替代方案：DCG是一个不错的计算引擎，但它不能与专门的解析引擎相竞争。这些解析引擎能够自动发出错误消息，并利用目标语法的理论属性...

:- dynamic text_length/1.

parse_conf_cs(Cs, AST)   :-
    length(Cs, TL),
    retractall(text_length(_)),
    assert(text_length(TL)),
    phrase(cfg(AST), Cs).
....
%%  tag(?T, -X, -Y)// is det.
%
%   Start/Stop tokens for XML like entries.
%   Maybe this should restrict somewhat the allowed text.
%
tag(T, X, Y) -->
    pos(X), unquoted(T), pos(Y).
....

%%  pos(-C, +P, -P) is det.
%
%   capture offset from end of stream
%
pos(C, P, P) :- text_length(L), length(P, Q), C is L - Q.

tag//3只是一个示例用法，在我正在构建的可编辑AST解析器中，我存储位置以便能够在编辑器中正确归属每个嵌套部分...

编辑

对id//1的一个小改进：SWI-Prolog有专门的code_type/2代码用于此操作：

1 ?- code_type(0'a, csymf).
true.

2 ?- code_type(0'1, csymf).
false.

所以（略过文字转换）

id([C|Cs]) --> [C], {code_type(C, csymf)}, id_rest(Cs).

id_rest([C|Cs]) --> [C], {code_type(C, csym)}, id_rest(Cs).
id_rest([]) --> [].

根据你对于概括小片段的态度以及实际语法细节，id_rest//1可以以可重用的方式编写并变得确定性更强。

id([C|Cs]) --> [C], {code_type(C, csymf)}, codes(csym, Cs).

% greedy and deterministic
codes(Kind, [C|Cs]) --> [C], {code_type(C, Kind)}, !, codes(Kind, Cs).
codes(Kind, []), [C] --> [C], {\+code_type(C, Kind)}, !.
codes(_, []) --> [].

这个更严格的id//1定义也可以消除关键字前缀标识符的一些歧义：将类似于recoding keyword//1的关键字//1重新编码。

keyword(K) --> id(id(K)), {memberchk(K, [
    array,
    break,
...
]}.

将正确识别

?- phrase(tokenize(Ts), `if1*2`).
Ts = [id(if1), *, int(2)] ;

你的字符串//1（OT:与库（dcg / basics）：string // 1不幸冲突）很容易成为实现简单“错误恢复策略”的候选：

stringChar(0'\") --> "\\\\".
stringChar(0'") --> pos(X), "\n", {format('unclosed string at ~d~n', [X])}.

这是一个“报告错误并插入缺失标记”的示例，以便解析可以继续进行...

- CapelliC

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mat · Accepted Answer

它目前看起来有点奇怪(像Java中的不可读名称吗?)，但在其核心部分它相当稳定，所以我只对代码和问题的一些方面提出了少数意见:

将词法分析与语法分析分开是很有道理的。同时在每个标记中存储行和列信息是一个完全可接受的解决方案，留下标记(例如)l_c_t(Line,Column,Token)或Token-lc(Line,Column)供解析器处理。
注释总是令人讨厌，或者说通常不够嵌套？在DCG中一个有用的模式经常是去找最长匹配，你已经在某些情况下使用了这种方式，但还没有用于anything//0。因此，重新排序这两个规则可能会帮助你跳过所有要被注释掉的内容。
关于确定性：承诺匹配的第一个解析结果是可以的，但只需执行一次，并抵制破坏声明性语法的诱惑。
在DCG中，使用|而不是;是优雅的。
tokenize//1？别开玩笑了！那只是tokens//1。在所有方面都有意义。