Viết trình phân tích cú pháp (cho ngôn ngữ đánh dấu): Lý thuyết & Thực hành

Question

Tôi muốn viết một trình phân tích cú pháp thành ngữ cho một ngôn ngữ đánh dấu như Markdown. Phiên bản của tôi sẽ hơi khác một chút, nhưng tôi nhận thấy ít nhất là một nhu cầu nhỏ đối với một cái gì đó như thế này trong Clojure, và tôi muốn nhận được nó.

Tôi không muốn sử dụng một loạt các RegExes (mặc dù tôi nhận ra một số có thể sẽ là cần thiết), và Tôi muốn tạo ra một thứ gì đó mạnh mẽ và độc đáo Clojure.

Tôi đã bắt đầu một vài nỗ lực khác nhau (chủ yếu là trên giấy), nhưng tôi rất vui với họ, vì tôi cảm thấy như thể tôi chỉ đang ứng biến. Điều đó sẽ ổn, nhưng tôi đã thực hiện rất nhiều khám phá bằng ngôn ngữ của Clojure trong một hoặc hai tháng qua, và muốn, ít nhất là một phần, đi theo con đường của những người khổng lồ.

Tôi muốn một số gợi ý hoặc đề xuất hoặc tài nguyên (sách từ O'Reilly sẽ rất tuyệt vời - yêu tôi một số sách điện tử - nhưng Amazon hoặc ở bất cứ nơi nào cũng sẽ tuyệt vời). Bất cứ điều gì bạn có thể cung cấp.

EDIT Brian Carper có bài đăng thú vị trên using ANTLR from Clojure.

Ngoài ra còn có clojure-pg và fnparse, là trình tạo trình phân tích cú pháp Clojure. fnparse thậm chí có vẻ như nó có một số tài liệu phong nha.

Vẫn đang tìm kiếm tài nguyên vv! Chỉ cần nghĩ rằng tôi muốn cập nhật những điều này với một số phát hiện của riêng tôi.

Answer 1

Ngoài ra còn có clj-peg dự án, cho phép xác định PEG ngữ pháp cho dữ liệu phân tích

Answer 2

Điều tốt nhất tôi có thể nghĩ là Terrence Parr - anh chàng dẫn đầu số ANTLR parser generator - đã viết một ngôn ngữ đánh dấu được ghi là here. Dù sao, có mã nguồn ở đó để xem xét.

Answer 3

Hai dịch giả đánh dấu chức năng là;

• Pandoc, một markdown thực hiện trong Haskell với source on github
• Simple_markdown thực hiện trong OCaml.

Answer 4

Một chưa được đề cập ở đây là clarsec, một cổng của thư viện phân tích cú pháp của Haskell.

Gần đây tôi đã có một nhiệm vụ tương tự để xây dựng trình phân tích cú pháp trong Clojure. Tôi đã đi khá xa xuống con đường fnparse, đặc biệt bằng cách sử dụng (chưa phát hành) fnparse 3 mà bạn có thể tìm thấy trong chi nhánh develop trên github. Nó được chia làm hai dạng: hound (đặc biệt cho LL (1) các trình phân tích cú pháp lookahead đơn) và cat, là một trình phân tích cú pháp gói. Cả hai đều là các trình phân tích cú pháp chức năng được xây dựng trên các monads (như clarsec). fnparse có một số công việc ấn tượng - khả năng tạo tài liệu cho trình phân tích cú pháp của bạn, xây dựng các thông báo lỗi, v.v. là gọn gàng. Tài liệu về nhánh phát triển không tồn tại mặc dù không phải là tài liệu chức năng, mà thực sự khá tốt. Cuối cùng, tôi đánh một số khối đường với cố gắng làm cho LL (k) làm việc. Tôi nghĩ rằng nó có thể làm cho nó hoạt động, nó chỉ là khó mà không có một bộ phong nha của các ví dụ về cách làm cho backtracking hoạt động tốt. Tôi cũng rất quen thuộc với các trình phân tích cú pháp phân chia lexing và phân tích cú pháp mà tôi khó nghĩ theo cách đó. Tôi vẫn rất quan tâm đến điều này như một giải pháp tốt trong tương lai.

Trong thời gian chờ đợi, tôi đã quay trở lại Antlr, rất mạnh mẽ, được truyền đi tốt, được ghi chép đầy đủ (trong 2 cuốn sách), v.v. Nó không có bản sao của Clojure nhưng tôi hy vọng trong tương lai, điều này sẽ làm cho việc phân tích cú pháp thực sự tốt đẹp. Tôi đang sử dụng nó cho lexing, phân tích cú pháp, chuyển đổi cây, và templating qua StringTemplate. Nó đã không hoàn toàn không có va chạm, nhưng tôi đã có thể tìm ra giải pháp khả thi cho mọi vấn đề cho đến nay. Thuật toán phân tích cú pháp LL (*) độc đáo của Antlr cho phép bạn viết các ngữ pháp thực sự có thể đọc được nhưng vẫn làm cho chúng khá hiệu quả (và tinh chỉnh dần dần nếu chúng không).