Parse tree là gì?

Cây phân tích cú pháp (parse tree) cho thấy một cách tượng hình cách ký hiệu xuất phát (start symbol) của một văn phạm (grammar) dẫn xuất một chuỗi (string) trong ngôn ngữ (language). Nếu ký hiệu không kết thúc (nonterminal ) A có một luật sinh A → X Y Z, thì cây phân tích cú pháp (parse tree) có thể có một nút trong (internal node) có nhãn A với ba nút con (child node) có nhãn X, Y và Z, từ trái sang phải:

Về mặt hình thức, với một văn phạm phi ngữ cảnh (context-free grammar) đã cho, cây phân tích cú pháp cú pháp (parse tree) là một cây (tree) có các thuộc tính sau:

• Nút gốc (root node) được gắn nhãn bằng ký hiệu xuất phát.
• Mỗi nút lá (leaf node) được gắn nhãn bởi một ký hiệu kết thúc hoặc bởi ε.
• Mỗi nút trong được gắn nhãn bởi một ký hiệu không kết thúc
• Nếu A là ký hiệu không kết thúc cho một số nút trong và X1, X2,..., Xn là các nhãn con của nút đó từ trái sang phải thì phải có một luật sinh A → X1X2...Xn. Ở đây, X1, X2, ..., Xn mỗi cái đại diện cho một ký hiệu kết thúc hoặc không kết thúc. Là một trường hợp đặc biệt, nếu A → ε là một luật sinh, khi đó một nút có nhãn A có thể có một nút con duy nhất được dán nhãn.

Ví dụ nếu S → x1x2 …… xn là một luật sinh trong CFG, thì cây phân tích cú pháp sẽ như sau: