Cách chính xác để phân tích biểu thức S trong OOP

Question

Tôi đang tìm cách thực hiện trình đọc S-biểu thức (được sử dụng sau này với cả trình thông dịch Scheme và trình biên dịch), nhưng tôi đã tự hỏi làm cách nào (nếu có) tôi nên viết một AST cho nó.

Tôi đã đọc SICP và điều này khá đơn giản từ bên trong Đề án, nhưng tôi đang tìm cách triển khai trình biên dịch và trình biên dịch trong C++, theo kiểu OO. Vui lòng ghi nhớ rằng tôi đang làm điều này chỉ vì mục đích học tập, vì vậy tôi không thực sự tìm cách dễ nhất hoặc nhanh nhất để làm việc này, mà đúng hơn là cách sử dụng lại chính xác và có thể sử dụng lại được.

Tôi đã nhìn thấy trong một số triển khai Đề án mà mọi người phân tích s-biểu thức và các tế bào khuyết điểm dễ dàng đầu ra, một cái gì đó như thế này:

struct Sexpr 
    { 
    }; 

    struct Cons : public Sexpr 
    { 
    Sexpr* left; 
    Sexpr* right; 
    }; 

    struct IntAtom : Sexpr 
    { 
    int value; 
    }; 

Và một lớp con của Sexpr cho từng loại Scheme Atom, hoặc cái gì đó dọc những dòng đó.

Tôi không chắc chắn, nhưng điều này có vẻ như một hack với tôi ... Công việc này không nên được thực hiện bởi một thông dịch viên hơn là người đọc?

Điều tôi muốn biết là nếu điều này được coi là cách tốt nhất (hoặc chính xác) của việc đọc biểu thức S, hay đây là công việc của người thông dịch nhiều hơn trình phân tích cú pháp? Nếu trình phân tích cú pháp có AST riêng của nó thay vì dựa vào các ô chống lại?

Answer 1

Để theo dõi từ phía Scheme/vợt của hàng rào:

vợt (và một số triển khai Đề án khác) sử dụng một đại diện phong phú hơn cho các đối tượng cú pháp, để họ có thể có tài sản gắn liền với họ chỉ ra (trong vợt , ít nhất) bối cảnh mà chúng bị ràng buộc, vị trí nguồn đến từ đâu, thông qua trình biên dịch đã chèn chúng, và bất kỳ thông tin nào khác mà bạn có thể muốn lưu trữ (xem "thuộc tính cú pháp" trong Racket).

Thông tin bổ sung này cho phép những thứ như thông báo lỗi với con trỏ đến nguồn và macro hợp vệ sinh.

Xin lưu ý rằng tôi có nghĩa là "phong phú hơn" ở đây chỉ đơn giản là trong ý nghĩa "chứa nhiều giá trị hơn", không theo bất kỳ cách nào không có giá trị trung lập.

Tôi cũng nên thêm --- trước khi rơi vào Turing Tar Pit --- bạn cũng có thể đại diện cho thông tin chính xác này sử dụng bảng ở bên cạnh; giả sử bạn có so sánh con trỏ, không có sự khác biệt rõ ràng giữa việc đặt một giá trị bên trong một cấu trúc và sử dụng một bảng để kết hợp cấu trúc với giá trị.

Answer 2

Nếu bạn muốn trở thành hơi hoàn toàn trong cú pháp của bạn, bạn sẽ cần phải hỗ trợ

sexpr ::= atom | sexpr sexpr 
atom ::= nil | intatom | etc. 

Nhưng đó là tổng quát hơn so với hầu hết sexpr bạn sẽ gặp phải. Dạng đơn giản nhất và phổ biến nhất của S-expr trong LISP/Scheme giống như (a b c d) trong đó mỗi a, b, c, d là các nguyên tử hoặc danh sách. Ở dạng cặp, đây là [a [b [c [d nil]]]], có nghĩa là tất cả các mặt bên phải trong danh sách của bạn là danh sách.

Vì vậy, nếu bạn đang đi cho sạch, bạn có thể chỉ làm

class sexpr {}; 
class atom : sexpr {}; 
class s_list : forward_list<smart_ptr<sexpr>> {}; 

Answer 3

Trong khi người ta có lẽ có thể tranh luận qua lại hơn những gì các phương pháp tiếp cận “đúng” là, theo ý kiến ​​của tôi, cách tiếp cận bạn đề nghị-sử dụng các cấu trúc dữ liệu tương tự để đọc, biên dịch, đánh giá, xử lý và — là phương pháp sẽ dạy bạn nhiều nhất về những gì Lisp và câu thần chú "mã là dữ liệu", và cụ thể là nhà điều hành quote thực sự có nghĩa là gì (đó là một điều khá sâu sắc).

Nó cũng là, tình cờ, cách hầu hết các Lisps (thú vị, không bao gồm Đề án) truyền thống làm việc.

Vì vậy, có, để người đọc tạo dữ liệu Lisp: conses, symbols, Lisp numbers, strings, et cetera, chính xác những thứ mà mã Lisp cấp người dùng sẽ xử lý. Nó sẽ làm cho phần còn lại của việc thực hiện đơn giản hơn và mang tính hướng dẫn hơn.

Answer 4

Bạn có thể muốn xem this c/c++ s-expr parser library để biết ví dụ về cách thực hiện.

Dường như các đại diện cơ sở là:

struct elt { 
    int type; 
    char *val; 
    struct elt *list; 
    struct elt *next; 
}; 

Và tôi trích dẫn từ tài liệu của họ:

Từ một yếu tố có thể là một danh sách hoặc nguyên tử, cấu trúc phần tử có một chỉ số loại có thể là LIST hoặc VALUE. Nếu chỉ báo kiểu là LIST, thì thành viên cấu trúc "list" sẽ là một con trỏ tới phần đầu của danh sách được biểu diễn bởi phần tử này. Nếu chỉ báo loại là VALUE, thì thành viên cấu trúc "val" sẽ chứa nguyên tử được biểu diễn bằng phần tử dưới dạng chuỗi. Trong cả hai trường hợp, con trỏ "tiếp theo" sẽ trỏ đến phần tử tiếp theo của biểu thức s hiện tại.

Ngoài ra here là danh sách toàn bộ các triển khai khác của người đọc s-expr bằng nhiều ngôn ngữ có thể quan tâm.