Ocaml chuỗi phân tích cú pháp để làm cho cây

Question

Tôi có một vấn đề tương tự như sau:

How to print a tree structure into a string fast in Ocaml?

Nhưng trong một cách ngược lại, rằng tôi đã có một chuỗi và muốn phân tích nó lại trở thành một cái cây.

Ví dụ, tôi có

type expr = 
    Number of int 
|Plus of expr*expr 
|Prod of expr*expr 

và tôi có một chuỗi như 1 + 2 * 3 + 4 (một chút khác biệt so với các liên kết ở trên, giả sử * có procedence cao hơn +)
Sau đó, tôi muốn kết quả của tôi là một loại expr Prod(Plus(1,2), Plus(3, 4))

tôi tìm thấy một liên kết mà có thể nói chuyện về vấn đề này, nhưng không chắc chắn nếu đó là một cách để thực hiện vấn đề của tôi:

Parsing grammars using OCaml

Vui lòng chia sẻ một số ý tưởng, cảm ơn bạn.

Answer 1

Đây là vấn đề phân tích tiêu chuẩn: phải đối mặt trong tất cả các trình biên dịch/phiên dịch/etc ... Có một số cách để tấn công vấn đề này, mà về cơ bản đun sôi xuống như sau:

• Viết riêng của bạn đệ quy parser gốc
• Sử dụng một phân tích cú pháp được tạo ra từ một máy phát điện phân tích cú pháp

nghe có vẻ giống như những gì bạn đang làm việc trên là một cái gì đó mà bạn cần một cú pháp trừu tượng Tree ("cây" bạn đề cập đến trong bài toán). Bạn có thể dễ dàng sử dụng trình tạo trình phân tích cú pháp OCaml để thực hiện những việc như vậy, một trình tốt sẽ là Menhir. Trong khi bạn cũng có thể viết trình phân tích cú pháp của riêng mình, sử dụng công cụ như Menhir hoặc ocamlyacc để làm điều đó cho bạn là một giải pháp rất linh hoạt và nhanh chóng (so với rối tung xung quanh với sự yuckiness của giao dịch với không LL (1) những thứ trong một trình phân tích cú pháp gốc đệ quy đơn giản).

Answer 2

Phân phối OCaml chứa ocamlyacc công cụ để thực hiện chính xác những gì bạn cần (các công cụ khác tồn tại, như Kristopher đã chỉ ra).

Để có giải thích tốt về ocamlyacc, hãy xem ví dụ this tutorial và related example nơi trình phân tích cú pháp cho ngôn ngữ biểu thức nhỏ (tương tự như ngôn ngữ của bạn) được xác định.