Làm cách nào để thiết kế các phần của cây cú pháp trừu tượng?

Question

Tôi đang viết một thông dịch viên C# từ đầu cho trải nghiệm học tập, và cho đến nay mọi thứ đã diễn ra suôn sẻ. Tôi có đầy đủ chức năng C# lexer mà kết quả đầu ra tất cả các loại thẻ để phân tích cú pháp. Tôi biết làm thế nào tôi sẽ phân tích các thẻ, nhưng tôi không chắc làm thế nào tôi nên cấu trúc AST của tôi (cây cú pháp trừu tượng).

Ví dụ, nếu tôi có một đoạn mã đơn giản:

using System.Xml; 

gì cây sẽ trông như thế khi phân tích cú pháp?

Như thế này?

UsingDirective 
    Identifier(System) 
     Identifier(Xml) 

hoặc như thế này?

UsingDirective 
    Identifier(System) 
    Identifier(Xml) 

Nếu tôi có thể nhận được một số đề xuất và/hoặc ví dụ như làm thế nào tôi có thể cấu trúc thứ như định danh với dấu chấm trong họ, nếu/else if/else, khai báo biến/chuyển nhượng kết hợp trong một tuyên bố (int i = 0;), định nghĩa chức năng, v.v. sẽ hữu ích. Tôi chỉ cần có một ý tưởng tốt hơn về cách cấu trúc cây và tôi có thể tự mình tìm ra phần còn lại. Cảm ơn.

Answer 1

Tôi đã viết một vài phân tích cú pháp trong quá khứ, và tôi nói chung sẽ đi cho một cái gì đó như thế này:

UsingDirective 
    IdentifierList 
    Identifier (LeftNode) (System) 
    Identifier (RightNode) (Xml) 

Trong trường hợp này using System.Collections.Generic

UsingDirective 
    IdentifierList 
     IdentifierList (LeftNode) 
      Identifier (LeftNode) (System) 
      Identifier (RightNode) (Collections) 
     Identifier (RightNode) (Generic) 

Không giống như Roslyn, tôi thích giữ AST của tôi ánh sáng bằng cách không bao gồm các thẻ như là dấu chấm phẩy, từ khóa using vv vì trình biên dịch không cần đến chúng.

Trình phân tích cú pháp mà tôi đã viết riêng cho IDE trông khác nhau - chúng mang theo tất cả những thứ bổ sung này cùng với nhiều thông tin hơn như số dòng và cột.

Answer 2

Bạn có thể xem cách Microsoft đang làm điều này với Roslyn. Bạn có thể thấy ở đó họ đã khai báo cây cú pháp như thế nào cho C# (và VB.NET) và thậm chí bạn có thể sử dụng nó thay vì các phần của trình thông dịch của bạn trước khi bạn viết chúng.

Cụ thể, Roslyn cây cú pháp cho thị using của bạn trông như thế này:

UsingDirective 
    UsingKeyword 
    QualifiedName 
     IdentifierName (System) 
     DotToken 
     IdentifierName (Xml) 
    SemicolonToken 

Vì vậy, tương tự như phiên bản thứ hai của bạn, nhưng chi tiết hơn.

Tôi nghĩ rằng phiên bản đầu tiên của bạn không có ý nghĩa nhiều. Xml không phải là con của System ở cấp độ cú pháp (mặc dù bạn có thể có khái niệm "không gian tên cha" sau này ở cấp ngữ nghĩa).