Prolog DCG: Viết ngôn ngữ lập trình lexer

Question

Tôi đang cố gắng giữ cho trình phân tích cú pháp và trình phân tích cú pháp riêng biệt, dựa trên lời khuyên mơ hồ của cuốn sách Phân tích ngôn ngữ Prolog và tự nhiên, thực sự không đi sâu vào chi tiết về lexing/tokenizing. Vì vậy, tôi cho nó một shot và nhìn thấy một số vấn đề nhỏ mà chỉ cho tôi rằng có cái gì đó rõ ràng tôi đang mất tích.

Tất cả các trình phân tích cú pháp nhỏ của tôi dường như không hoạt động; tại thời điểm này đây là một đoạn mã của tôi:

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

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

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

Đó là một chút lặp đi lặp lại nhưng có vẻ như nó hoạt động. Sau đó, tôi có một số thứ mà tôi không hoàn toàn yêu thương và tôi hoan nghênh đề xuất về, nhưng dường như để làm việc:

Nguyên tắc chính cho tokenizer tôi là thế này:

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

Đó là chưa hoàn hảo; Tôi sẽ thấy int được phân tích cú pháp thành in,id(t) vì keyword(X) xuất hiện trước id(X). Vì vậy, tôi đoán đó là câu hỏi đầu tiên.

Câu hỏi lớn hơn tôi có là tôi không thấy cách tích hợp đúng các nhận xét vào tình huống này. Tôi đã thử các cách sau:

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

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

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

Điều này dường như không hoạt động; các phân tích cú pháp trả về (và tôi nhận được nhiều phân tích cú pháp) dường như không xóa nhận xét. Tôi lo lắng rằng quy tắc bình luận của tôi là không cần thiết không hiệu quả và có thể gây ra rất nhiều backtracking không cần thiết. Tôi cũng lo lắng rằng whites//0 từ dcg/khái niệm cơ bản là xác định; Tuy nhiên, một phần của phương trình dường như hoạt động, nó chỉ tích hợp nó với nhận xét bỏ qua mà dường như không.

Lưu ý cuối cùng, tôi không thấy cách xử lý các lỗi phân tích cú pháp ngược lại cho người dùng có thông tin dòng/cột từ đây. Nó cảm thấy như tôi sẽ phải theo dõi và thread thông qua một số loại dòng/cột thông tin hiện tại và viết nó vào các thẻ và sau đó có thể cố gắng xây dựng lại dòng nếu tôi muốn làm một cái gì đó tương tự như cách llvm hiện nó. Đó là công bằng hay là có một "thực hành được đề nghị" ở đó?

Toàn bộ mã có thể được tìm thấy in this haste.

Answer 1

Tôi có mã này để hỗ trợ báo cáo lỗi, bản thân nó phải được xử lý cẩn thận, rắc các thông báo có ý nghĩa và 'bỏ qua các quy tắc' xung quanh mã. Nhưng không có sẵn sàng để sử dụng thay thế: một DCG là một công cụ tính toán tốt đẹp, nhưng nó không thể cạnh tranh out-of-the-box với các công cụ phân tích chuyên biệt, có thể phát ra các thông báo lỗi tự động, khai thác các tính chất lý thuyết của văn phạm tiếng nhắm mục tiêu ...

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

thẻ // 3 chỉ là một cách sử dụng Ví dụ, trong phân tích cú pháp này, tôi đang xây dựng một AST có thể chỉnh sửa, vì vậy tôi lưu trữ các vị trí để có thể thuộc tính đúng từng phần lồng nhau trong một biên tập viên ...

chỉnh sửa

một cải tiến nhỏ cho id // 1: SWI-Prolog đã chuyên code_type/2 cho rằng:

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

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

như vậy (glossing qua chuyển đổi theo nghĩa đen)

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([]) --> []. 

tùy thuộc vào thái độ của bạn để khái quát đoạn nhỏ, và các chi tiết ngữ pháp thực tế, id_rest // 1 có thể là được viết theo kiểu thời trang có thể tái sử dụng và được xác định là

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(_, []) --> []. 

định nghĩa chặt chẽ hơn này của id // 1 cũng sẽ cho phép loại bỏ một số định danh không rõ ràng với từ khóa pr efix: recoding từ khóa // 1 như

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

sẽ xác định đúng

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

bạn chuỗi // 1 (OT: những gì không may đụng độ với thư viện (DCG/cơ bản): string // 1) là một ứng cử viên dễ dàng để thực hiện một 'chiến lược phục hồi lỗi' đơn giản:

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

Đây là một ví dụ về 'lỗi báo cáo và chèn thiếu token', do đó phân tích cú pháp có thể tiếp tục ...

Answer 2

Nó hiện vẫn trông hơi lạ (unreadableNamesLikeInJavaAnyone?), nhưng trong lõi của nó là khá vững chắc, vì vậy tôi chỉ có một vài ý kiến ​​về một số khía cạnh của mã và các câu hỏi:

1. tách Lexing từ phân tích cú pháp có ý nghĩa hoàn hảo. Nó cũng là một giải pháp hoàn toàn chấp nhận được để lưu trữ thông tin dòng và cột cùng với mỗi mã thông báo, để lại mã thông báo (ví dụ) của biểu mẫu l_c_t(Line,Column,Token) hoặc Token-lc(Line,Column) để trình phân tích cú pháp xử lý.
2. Nhận xét luôn khó chịu, hoặc tôi nên nói, thường không làm tổ? Một mẫu hữu ích trong DCG thường là để đi cho trận đấu dài nhất mà bạn đã sử dụng trong một số trường hợp, nhưng chưa phải cho anything//0. Vì vậy, sắp xếp lại hai quy tắc có thể giúp bạn bỏ qua mọi thứ có nghĩa là được nhận xét.
3. Về chủ nghĩa xác định: Bạn có thể cam kết phân tích cú pháp đầu tiên phù hợp, nhưng chỉ thực hiện một lần và chống lại sự cám dỗ làm hỏng ngữ pháp khai báo.
4. Trong DCG, thanh lịch là sử dụng | thay vì ;.
5. tokenize//1? Nào! Đó chỉ là tokens//1. Nó có ý nghĩa trong mọi hướng.