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].

我的tokenizer的主要规则是:

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

这似乎不起作用; 返回的解析(我得到许多解析)似乎没有删除注释.我很担心我的评论规则不必要地效率低下,并且可能引起很多不必要的回溯.我也很紧张,whites//0因为dcg/basics是确定性的; 然而,这个方程的一部分似乎有效,它只是将它与评论跳过相结合似乎没有.

作为最后一点,我没有看到如何使用此处的行/列信息将传播解析错误处理回用户.感觉就像我必须跟踪和穿过某种当前的行/列信息并将其写入令牌,然后如果我想做类似于llvm的操作,可能会尝试重建该行.那是公平还是有"推荐做法"？

整个代码可以在这个仓促中找到.

Answer 1

它目前看起来仍然有点奇怪(unreadableNamesLikeInJavaAnyone?),但它的核心是非常可靠的,所以我只对代码的某些方面和问题有一些评论:

1. 将lexing与解析分开是完全合理的.它也是一个完全可以接受的解决方案,用于存储行和列信息以及每个令牌,留下表单的令牌(例如)l_c_t(Line,Column,Token)或Token-lc(Line,Column)解析器进行处理.
2. 评论总是令人讨厌,或者我应该说,通常不是很好吗？DCG中有用的模式通常用于最长匹配,在某些情况下您已经使用过,但尚未使用anything//0.因此,重新排序这两条规则可能会帮助您跳过所有要评论的内容.
3. 关于确定性:可以提交匹配的第一个解析,但只执行一次,并抵制混淆声明性语法的诱惑.
4. 在DCG中,使用|而不是优雅;.
5. tokenize//1？来吧!那只是tokens//1.它在各个方向都有意义.

Answer 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.

so（掩盖字面转换）

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 的这种更严格的定义还允许删除带有关键字前缀的一些歧义标识符：重新编码关键字//1 就像

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

会正确识别

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

您的 string//1 （OT：与库（dcg/basics）的不幸冲突：string//1）是实现简单“错误恢复策略”的简单候选者：

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

这是“报告错误并插入丢失的标记”的示例，因此解析可以继续......