Thông dịch viên dựa trên Prolog

Question

Tôi đã bị ướt chân với lập trình chức năng; Tôi quen thuộc (mặc dù không thành thạo) trong Haskell và PLT Scheme. Tôi đã sử dụng PLT Scheme để xây dựng ít thông dịch viên cho các ngôn ngữ đồ chơi (tham khảo PLAI) - Tôi tốt hơn với các ngôn ngữ mệnh lệnh.

Có ai có thể hướng dẫn tôi đến các tài nguyên tôi có thể sử dụng để xây dựng một thông dịch viên nhỏ về ngôn ngữ đồ chơi mà tôi chọn với Prolog không?

Answer 1

Tôi chủ yếu sử dụng swi-prolog nên hầu hết những gì tôi nói sẽ liên quan đến pri-prolog. Tuy nhiên, các triển khai prolog khác có thể có các vị từ/thư viện tương tự (có lẽ với một tên khác), vì vậy bạn có thể tìm kiếm các sách hướng dẫn của chúng và tìm chúng. Ngoài ra, tôi đang viết một trình biên dịch, không phải là một thông dịch viên, trong prolog vì vậy có thể một số phần không liên quan đến thông dịch viên.

SWI-Prolog's documentation site thực sự tốt cho việc tìm kiếm nội dung: sử dụng hộp tìm kiếm để tìm bất kỳ vị từ nào hoặc thực hiện tìm kiếm thông thường. Có rất nhiều thư viện nhưng bạn có thể muốn tự mình thực hiện một số nội dung để có được trải nghiệm. Bạn có thể kết thúc việc phát minh lại bánh xe nhưng nó sẽ hữu ích.

Cuốn sách "Nghệ thuật Prolog" (Sterling, Shapiro) có một chương dành riêng để xây dựng trình biên dịch ở dạng prolog (và nó cũng là một cuốn sách hay cho prolog).

Có thể có một số công cụ tương đương với lex/bison cho prolog; tôi chưa bao giờ thực sự tìm kiếm.
Imho, lexer là khá dễ dàng trong đồng bằng prolog; một cách tự nhiên, nó sẽ dựa nhiều vào kết hợp mẫu.

Đối với trình phân tích cú pháp, tôi khuyên bạn nên sử dụng DCG: ngữ pháp mệnh đề xác định: swi-prolog doc, google để biết thêm chi tiết.
Vấn đề là bạn sẽ phải phân tích cú pháp toàn bộ tệp (hoặc ít nhất là tôi không tìm thấy cách để thực hiện nó theo cách khác). Btw, lexer cũng có thể được thực hiện với DCG nhưng tôi không nghĩ rằng nó thực sự tốt hơn.

Nếu bạn chọn có mã trung gian, một cây cú pháp trừu tượng dễ tạo ra từ trình phân tích cú pháp (bạn cũng có thể đánh giá rất nhiều thứ trong quá trình phân tích cú pháp).
Về kiểm tra ngữ nghĩa: trong trình biên dịch của tôi cho một ngôn ngữ đồ chơi, tôi thực hiện hầu hết các kiểm tra ngữ nghĩa (phạm vi liên quan, gọi hàm) trong quá trình phân tích cú pháp và phần còn lại ở một bước riêng biệt. Đó là một lộn xộn

cụ hữu ích khác chút: Kiểm tra khẳng định/1, các biến toàn cầu, meta predicates (maplist/[2-6]).
không tinh khiết prolog và bạn có thể làm cho mã của bạn quá cấp bách bởi lạm dụng họ (và sau đó bạn có thể có một số thực sự khó chịu tác dụng phụ)

Đối với bảng biểu tượng (nếu bạn cần) bạn chỉ có thể sử dụng khẳng định/1 để thêm biến vị ngữ: swi-prolog sử dụng bảng băm động cho các biến vị ngữ động. cảnh báo: các biến vị ngữ động chậm hơn so với tĩnh, khi bạn hoàn thành bảng và sẽ không thực hiện bất kỳ thay đổi nào, hãy sử dụng compile_predicates/1 để làm cho chúng tĩnh. Ví dụ, khi tôi hoàn thành việc phân tích cú pháp ST của tôi đã sẵn sàng để tôi biên dịch nó. Một giải pháp khác cho ST là sử dụng association lists. chúng được thực hiện với cây AVL nên chi phí là O (log (N)).

Answer 2

Markus Triska (here trang chủ của mình) cho thấy một số điều có thể thú vị với bạn: ví dụ: toy LISP hoặc một số khó khăn đối với meta interpreters.