Prolog DCG: Написание языка программирования lexer

Question

Я пытаюсь на данный момент держать мой лексер и парсер отдельно, основываясь на неопределенном совете книги Пролог и анализ естественного языка, который действительно не вдавался в подробности о lexing/tokenizing. Поэтому я даю ему шанс и вижу несколько незначительных проблем, которые указывают мне, что я вижу что-то очевидное.

Все мои маленькие маркеры-парсеры, похоже, работают нормально; на данный момент это фрагмент моего кода:

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

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

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

Это немного повторяющиеся, но это, кажется, работает. Тогда у меня есть некоторые вещи, которые мне не совсем нравится, и будет приветствовать предложения, но это похоже на работу:

Основное правило для моего 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. Является ли это честным или существует «рекомендуемая практика»?

Весь код может быть найден in this haste.

Answer 1

У меня есть этот код для поддержки отчетов об ошибках, которые должны обрабатываться с осторожностью, разбрызгивать значимые сообщения и «пропускать правила» вокруг кода. Но нет готовой альтернативы: 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. 

тег // 3 это просто пример использования, в этом парсер, я в здании редактируемой AST, так что я сохранить позиции, чтобы иметь возможность правильно приписать каждую вложенную часть в редакторе ...

редактировать

небольшое повышение для идентификатора // 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(_, []) --> []. 

это строже определение идентификатора // 1 также позволят устранить некоторые идентификаторы неоднозначности WRT с ключевым словом пр EFix: перекодирование ключевого слова // 1 как

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

правильно определить

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

Вашей строка // 1 (OT: что несчастного столкновение с библиотекой (DCG/основа): строка // 1) простой кандидат для реализации «стратегии восстановления ошибок» просты:

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

Это пример «ошибка отчета и вставки отсутствуют маркер», так что синтаксический анализ может продолжайте ...

Answer 2

В настоящее время она по-прежнему выглядит немного странно (unreadableNamesLikeInJavaAnyone?), но в основном это довольно твердое, поэтому у меня есть только несколько замечаний по поводу некоторых аспектов коды и вопросов:

1. Разделительных лексических от разбор имеет смысл. Это также вполне приемлемое решение для хранения информации о строках и столбцах вместе с каждым токеном, оставляя токены (например) формы l_c_t(Line,Column,Token) или Token-lc(Line,Column) для анализатора.
2. Комментарии всегда неприятны, или я должен сказать, часто не-нечестность? Полезный образец в DCG часто приходится на самое длинное совпадение, которое вы уже используете в некоторых случаях, но еще не для anything//0. Таким образом, переупорядочение двух правил может помочь вам пропустить все, что должно быть прокомментировано.
3. Что касается детерминизма: это нормально, чтобы выполнить первый синтаксический анализ, который соответствует, но сделать это только один раз и противостоять соблазну испортить декларативную грамматику.
4. В DCG, изящно использовать | вместо ;.
5. tokenize//1? Давай! Это всего лишь tokens//1. Это имеет смысл во всех направлениях.