Thực hiện cây C++ n-ary để sử dụng trong phân tích cú pháp gốc đệ quy

Question

Tôi vẫn còn hơi mới với C++ nên chịu đựng với tôi. Tôi đang thực hiện một thông dịch viên cho một ngôn ngữ giả định được gọi là Core được mô tả bằng ngữ pháp BNF. Cho đến nay tôi đã thực hiện một tokenizer cung cấp cho tôi một hàng đợi tốt đẹp của các thẻ đại diện cho một chương trình Core. Bây giờ tôi đang trong quá trình viết Trình phân tích cú pháp/Executer lấy đầu ra từ trình mã thông báo và sử dụng nó để điền một đối tượng của lớp ParseTree (mà tôi phải thiết kế) bằng cách sử dụng phân tích cú pháp gốc đệ quy. Tôi hiểu các nguyên tắc cơ bản về cách thực hiện điều này nhưng gặp sự cố khi triển khai lớp ParseTree. Các sản phẩm được mô tả bởi BNF lõi thường có 2-5 ký hiệu đầu cuối/nonterminal nhưng một số có thể có đến 20 vì vậy tôi cần một cây n-ary nơi mỗi nút có thể có số lượng con khác nhau.

Tôi cho rằng lớp ParseTree không nhất thiết phải sử dụng cây để thực hiện nhưng có vẻ có ý nghĩa nhất (Có cấu trúc dữ liệu khác có thể tốt hơn/dễ hơn không?). Tôi không biết về bất kỳ thùng chứa nào trong STL phù hợp với hóa đơn cho những gì tôi cần. Tôi đã nhìn vào cây tài sản Boost nhưng từ những gì tôi có thể nói rằng sẽ không làm việc hoặc. Tôi không muốn tái tạo lại bánh xe và thực hiện một cây từ đầu nếu có thể. Ngoài ra, tôi bị giới hạn bởi không thể sử dụng bất kỳ thư viện bên ngoài nào ngoài Boost. Cách tốt nhất để thực hiện ParseTree của tôi là gì? Có bất kỳ triển khai cây nào được thực hiện tốt mà tôi có thể sử dụng không?

Answer 1

Tôi khuyên bạn nên sử dụng cây nhị phân 'con trái, phải anh em' để biểu thị cây phân tích cú pháp. Nó là sự thay thế của cây n-ary. Bất kỳ cây n-ary nào cũng có thể được biểu diễn bằng cách sử dụng cây con đầu tiên, cây anh em tiếp theo 'cây BINARY.

Khái niệm này là như sau: nếu A có ba người con: B, C và D và C có 2 trẻ em E và F như sau

   A 
      /| \ 
      B C D 
       /\ 
      E F 

này có thể được biểu diễn dưới dạng

   A 
      /
      B 
       \ 
       C 
      /\ 
      E D 
       \ 
       F 

tức là trẻ em luôn đi đến nút bên trái và các anh chị em đến nút bên phải. Nó rất dễ dàng để xây dựng quá và các traversal đặt hàng trước của cây này là giống như các traversal đặt hàng trước của một cây n-ary.

cây n-ary đặt hàng trước traversal:

display (node, level) { 
    if (!node) return; 
    print node; 
    display (node->left, level+1); 
    display (node->right, level+1); 
} 

con anh chị em nhị phân cây đặt hàng trước travesal

display (node, level) { 
    if (!node) return; 
    print node; 
    display (node->left, level+1); 
    display (node->right, level); 
} 

Làm thế nào để xây dựng cây này:

1. Throw your terminals and non-terminals in a Stack. 
2. When you want to combine n nodes under parent node 'p', pop 'n' elements from stack, making the last pop as the right child of the current pop. 
3. Finally make the nth pop the left child of node 'p'.