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

Question

我目前正在尝试根据 Prolog 和自然语言分析 一书的模糊建议，将我的词法分析器和解析器分开，但确实行不通关于 lexing/tokenizing 的任何细节。所以我试了一下，看到了几个小问题，这些小问题向我表明我缺少一些明显的东西。

我所有的小令牌解析器似乎都工作正常；目前这是我的代码片段：

:- 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)).

这似乎行不通； return 的解析（我得到了很多解析）似乎没有删除评论。我很紧张我的评论规则不必要地低效并且可能会导致很多不必要的回溯。我也很紧张 dcg/basics 中的 whites//0 是确定性的；然而，等式的那部分似乎有效，它只是将它与似乎无效的评论跳过相结合。

最后一点，我看不出如何使用此处的 line/column 信息将解析错误传播回用户。感觉我必须通过某种当前 line/column 信息进行跟踪和串连，并将其写入令牌，然后如果我想做类似于 llvm 的操作，可能会尝试重建该行。这公平吗？那里有 "recommended practice" 吗？

可以找到完整的代码in this haste。

Answer 1

目前看起来还是有点奇怪(unreadableNamesLikeInJavaAnyone?)，但是内核还是很扎实的，所以我对代码的某些方面和问题只有几点意见：

将词法分析与解析分开非常有意义。这也是一个完全可以接受的解决方案，将行和列信息与每个标记一起存储，留下 l_c_t(Line,Column,Token) 或 Token-lc(Line,Column) 形式的标记（例如）供解析器处理。
评论总是很讨厌，或者我应该说，经常不讨厌？ DCG 中一个有用的模式通常是寻找最长的匹配，您在某些情况下已经在使用这种模式，但还没有用于 anything//0。因此，重新排序这两个规则可能会帮助您跳过所有要注释掉的内容。
关于确定性：提交第一个匹配的解析是可以的，但只做一次，并抵制弄乱声明性语法的诱惑。
在 DCG 中，使用 | 代替 ; 是优雅的。
tokenize//1？来吧！那只是 tokens//1。各方面都说得通。

Answer 2

我有这个代码来支持错误报告，它本身必须小心处理，在代码周围散布有意义的消息和 'skip rules'。但是没有现成的替代方案：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 like

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

会正确识别

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

你的 string//1（OT：不幸的是与 library(dcg/basics):string//1 发生了冲突）很容易实现一个简单的 'error recovery strategy':

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

是'report error and insert missing token'的例子，所以解析可以继续...

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

Prolog DCG: Writing programming language lexer

prolog

lexical-analysis

dcg