Tóm tắt Cú pháp đại diện cây trong C++

Question

Tôi đã có giao diện mã thông báo tạo danh sách mã thông báo. Tôi có cơ chế làm việc cho trình phân tích cú pháp. Nó thực sự độc đáo và hoạt động như một sự quyến rũ. Điều duy nhất mà tôi nhớ là cấu trúc cơ bản của AST. Làm thế nào các cây, các nút và các báo cáo nên được đại diện trên mức độ trừu tượng. Tôi không cần thực hiện bất kỳ một ý tưởng nhanh như thế nào nó sẽ giống như trong hệ thống phân cấp lớp? Tôi đang làm việc trên một ngôn ngữ hướng đối tượng. Vâng, tôi đã nhận ra rằng tôi sẽ cần hai loại báo cáo. Một số giá trị trả về câu lệnh "expression" và câu lệnh kiểu kiểm soát dòng lệnh không trả về. Cảm ơn bạn rất nhiều.

Answer 1

Nếu ngôn ngữ của bạn là bắt buộc/c-như, các kịch bản phổ biến bắt đầu bằng từ trên hệ thống phân cấp được phân chia trong 2 siêu kiểu:

• Biểu
• Tuyên Bố

Chương trình này là một danh sách của tuyên bố, đó là một tuyên bố chính nó.

Bạn có thể muốn có một lớp cho loại câu lệnh mở rộng lớp cơ sở câu lệnh.

Một kịch bản điển hình trông giống như:

• khối statement (một danh sách các câu lệnh)
• ite (nếu then else)
• cho (một biểu hiện cho vòng lặp với danh sách báo cáo khởi của nó, kiểm tra, báo cáo gia tăng và chặn
• trong khi (tương tự, nhưng chỉ kiểm tra biểu thức
• khai báo biến
• gán (Bao gồm + = - = ++ -, bạn có thể quấn tất cả trong một lớp học với một lĩnh vực khai thác, một lval và một rval)
• Chức năng cuộc gọi (void một)

Đối với các biểu thức:

• Bop (hoạt động nhị phân, bất kỳ thứ gì có 2 toán hạng và 1 toán tử tức là + - * /% | & & & || == <
• UOP (hoạt động unary, bất cứ điều gì mà có 1 toán hạng và 1 nhà điều hành tức là ~!)
• Chức năng cuộc gọi (không-trống cái)
• biểu có điều kiện (exp val đúng:? Sai val)

Điều tốt về việc có 2 sự trừu tượng này (biểu thức và câu lệnh) là bên trong tất cả các lớp của bạn, bạn sẽ có kiểu trừu tượng và có thể truy cập AST với mẫu khách truy cập.

Ví dụ, một số lớp học sẽ giống như thế này (giả):

class Ite extends Statement { 
    Expression condition; 
    Statement ifBranch; 
    Statement elseBranch; 
} 


class Bop extends Expression { 
    BOperator operator; // +, -. * or whatever 
    Expression left;  // Left operand 
    Expression right; // Right operand 
} 


class StatementBlock extends Statement { 
    List<Statement> statements; 
} 


class Assignment extends Statement { 
    AOperator assignOp; // = += -= etc. 
    LVal lvalue;   // The lvalue cannot be an arbitrary expression, you will usually have a specific type for it 
    Expression rvalue; // Right value 
} 

Ngoài ra, bạn sẽ cần một số cách để đại diện cho loại (đối với AST, chỉ cần loại tĩnh là đủ, nếu bạn dự án để thực hiện một số back-end là tốt, bạn sẽ cần một số loại động quá).

Các kiểu tĩnh thường có thể được chỉ định với một số liệt kê, nếu bạn không có kế hoạch hỗ trợ các mảng có kích thước cố định cần thông tin kích thước. Nếu bạn muốn các mảng có kích thước cố định với kích thước, bạn có thể thực hiện một lớp cho kiểu và có kiểu mảng chứa thông tin kích thước bổ sung.

enum Type { 
    CHAR, 
    SHORT, 
    INT, 
    LONG, 
    FLOAT, 
    DOUBLE, 
    ARRAY 
} 

class Float extends StaticType { 
    final Type type = Type.FLOAT; 
} 

class Array extends StaticArray { 
    final Type type = Type.ARRAY; 

    int size; 
} 

Sau đó, bạn sẽ khởi tạo một thể hiện StaticType cho mọi loại trong AST, ví dụ: khi người dùng khai báo biến. Bạn sẽ có thể sử dụng cùng một hệ thống phân cấp nếu bạn dự định thực hiện kiểm tra kiểu tĩnh trong tương lai.

Đối với việc chạy/giải thích mã trong biểu mẫu AST, bạn sẽ cần Bộ nhớ sẽ chứa ngăn xếp/đống chứa thông tin về bộ nhớ thời gian chạy. Tại thời điểm đó, bạn sẽ cần phải lưu trữ các giá trị cùng với thông tin kiểu của chúng.