Bất kỳ sự khác biệt nào giữa các thuật ngữ phân tích cây và cây phái sinh?

Question

Thuật ngữ AST (Cây cú pháp trừu tượng), cây phân tích cú pháp và cây dẫn xuất được nhóm lại bởi những người khác nhau khi đề cập đến kết quả phân tích cú pháp văn bản phù hợp với ngữ pháp. Giả sử chúng ta đang nói về phân tích ngôn ngữ máy tính, sự khác biệt của họ có đủ phút để chúng ta có thể sử dụng các thuật ngữ này thay thế cho nhau không? Nếu không, làm thế nào để chúng tôi sử dụng các điều khoản một cách chính xác?

Answer 1

AFAIK, "cây phái sinh" và "phân tích cây" là giống nhau.

Abstract syntax tree

Trong khoa học máy tính, một cây trừu tượng cú pháp (AST), hay chỉ là cây cú pháp, là một cây đại diện của cấu trúc cú pháp trừu tượng của mã nguồn viết bằng một ngôn ngữ lập trình. Mỗi nút của cây biểu thị một cấu trúc xuất hiện trong mã nguồn. Cú pháp là 'trừu tượng' theo nghĩa là nó không đại diện cho mọi chi tiết xuất hiện trong cú pháp thực.

Parse tree

Một cây cú pháp bê tông hoặc phân tích cây hoặc phân tích cây là một (ra lệnh, bắt rễ) cây đại diện cho cấu trúc cú pháp của một chuỗi theo một số ngữ pháp chính thức. Trong một cây phân tích cú pháp, các nút bên trong được gắn nhãn bởi các thiết bị phi đầu cuối của ngữ pháp, trong khi các nút lá được gắn nhãn bởi các đầu cuối của ngữ pháp.

Lấy nguồn a = (1 + 2) * 3; ví dụ. Cây phân tích cú pháp có thể trông giống như:

ASSIGNMENT 
// |  \ 
// |  \ 
a = expression ; 
    / \ 
expression \ 
/| \  \ 
    ( + )  * 
    /\  \ 
    1 2  3 

trong khi trừu tượng cây cú pháp có thể trông giống như:

ASSIGNMENT 
/ \ 
a expression 
    / \ 
expression * 
    |  \ 
    +   3 
    /\ 
    1 2 

Answer 2

Parse/thức chiết khấu/cây cú pháp bê tông đều từ đồng nghĩa cho khái niệm tương tự.

Những cây như vậy thường chỉ được sử dụng trong các cuộc thảo luận lý thuyết, vì chúng chứa rất nhiều chi tiết dường như không cần thiết để xử lý ngôn ngữ; trong một cây biểu thức, bạn có thực sự cần một nút để biểu diễn "(" và cái khác đại diện cho ")" không?

Khái niệm về một "cú pháp trừu tượng" là cây đại diện cho cấu trúc chương trình đến mức chi tiết đủ để xử lý trong thực tế; bạn thường không tìm thấy các nút cho "(...)".

Câu hỏi thú vị: AST có thể tính trực tiếp từ CST không? Câu trả lời là phải có, nhưng mọi người hầu như không bao giờ làm điều đó. Những gì họ có xu hướng làm là xây dựng các nút "cú pháp trừu tượng" khi trình phân tích cú pháp chạy, và sử dụng ad hoc (quy tắc giảm bớt thủ tục quy tắc) để tập hợp các nút từ các phân tích cú pháp con với nút keo cho phụ huynh. IMHO, họ làm điều này bởi vì tất cả chúng tôi đã được đưa lên YACC, và đó là cách nó được thực hiện theo truyền thống. (Chúng tôi cũng từng đốt lửa với đá lửa). Có một lý do nhỏ hơn; làm theo cách này cho phép trình biên dịch hoàn toàn kiểm soát cấu trúc của AST và anh ta có thể tạo ra một cái khá nhỏ về mặt chi tiết. Như một cây đặc biệt không thể tính toán được từ CST, ngoại trừ bởi cùng một tính toán đặc biệt được nhúng trong các hành động của trình phân tích cú pháp.

Tôi đã sử dụng một cách tiếp cận khác: my tools tính toán AST trực tiếp từ CST, nghĩa là bằng cách xóa các chi tiết không liên quan, ví dụ: bỏ các nút đại diện cho mã thông báo mang giá trị không (ví dụ:, những mã thông báo vô nghĩa '(' ') cũng như từ khoá), nén các chuỗi sản phẩm đơn nhất và chuyển đổi cây phải hoặc trái tương đương với danh sách, thành các nút danh sách thực. Ưu điểm của việc này là trình phân tích cú pháp có thể tính toán AST trực tiếp từ các quy tắc ngữ pháp. Không có xung quanh với tập tin đính kèm thủ tục. Không hiểu sai. Không còn lo lắng về thực tế là our COBOL grammar có 3500 quy tắc và tôi sẽ cần goo thủ tục cho mỗi người trong số họ, và tôi phải thay đổi ngữ pháp của mình hàng trăm lần để làm cho nó đúng và fiddle với goo mỗi lần. Và các công cụ của chúng tôi hoạt động như thể chúng hoạt động trực tiếp trên CST, giúp bạn dễ dàng nghĩ về các thao tác trên cây, đặc biệt nếu bạn đang nhìn thẳng vào các quy tắc ngữ pháp. (Điều này cũng làm cho khớp mẫu sử dụng cú pháp bề mặt dễ dàng hơn nhiều: đối với bất kỳ đoạn mẫu nào, có một AST tính trực tiếp tương ứng).

Vì vậy, sự khác biệt giữa AST và CST là thực tế về tiện ích. Nhưng tôi nghĩ rằng họ nên được coi là chỉ là biểu diễn đẳng cấu.

Answer 3

Tôi sẽ sử dụng thuật ngữ phân tích cây khi cây được tạo bằng phân tích cú pháp, đó là khi đánh giá xem chuỗi đầu vào đã cho thuộc ngôn ngữ hay không và xác định sản phẩm nào phải được sử dụng để sắp xếp lại chuỗi.

A cây phái sinh sẽ có hình dạng giống hệt nhau, nhưng sẽ được tạo bởi quá trình tạo chuỗi từ một sản phẩm cụ thể.

Định nghĩa chính thức của phân tích là tìm nguồn gốc cho chuỗi đầu vào cho, vì vậy không có thắc mắc nguồn gốc và cây phân tích cú pháp đều giống nhau.

bê tông so trừu tượng cây cú pháp khác nhau trong đó các cựu có một nút lá cho mỗi thẻ trong chuỗi đầu vào, trong khi sau này bỏ qua bất kỳ thẻ có thể được gọi bằng cách kiểm tra ngữ pháp. Một cây con cú pháp cụ thể cho if <expr> then <statement> else <statement> end sẽ có lá cho nếu, sau đó, khác, và cuối, và một trong những trừu tượng sẽ không được. Cây cú pháp cụ thể cho (2+3) sẽ là:

e 
    | 
(e) 
/|\   
| | | 
n + n 

Một trừu tượng sẽ chỉ:

+ 
| | 
n n