Câu hỏi Sự khác biệt giữa cây phân tích và AST là gì?


Chúng được tạo ra bởi các giai đoạn khác nhau của một quá trình biên dịch? Hay chúng chỉ là những cái tên khác nhau cho cùng một thứ?


76
2018-02-17 08:19


gốc


Parse Tree là kết quả của ngữ pháp của bạn với các hiện vật của nó (bạn có thể viết vô số các ngữ pháp cho cùng một ngôn ngữ), một AST giảm Parse Tree gần nhất có thể với ngôn ngữ. Một số ngữ pháp cho cùng một ngôn ngữ sẽ cho các cây phân tích cú pháp khác nhau nhưng sẽ dẫn đến cùng một AST. (bạn cũng có thể giảm các tập lệnh khác nhau (các phân tích cú pháp khác nhau từ cùng một ngữ pháp) sang cùng một AST) - Guillaume86
Câu trả lời SO này thảo luận chi tiết về sự thiếu hụt: stackoverflow.com/a/1916687/120163 - Ira Baxter


Các câu trả lời:


Điều này được dựa trên Bộ đánh giá biểu thức ngữ pháp của Terrence Parr.

Ngữ pháp cho ví dụ này:

grammar Expr002;

options 
{
    output=AST;
    ASTLabelType=CommonTree; // type of $stat.tree ref etc...
}

prog    :   ( stat )+ ;

stat    :   expr NEWLINE        -> expr
        |   ID '=' expr NEWLINE -> ^('=' ID expr)
        |   NEWLINE             ->
        ;

expr    :   multExpr (( '+'^ | '-'^ ) multExpr)*
        ; 

multExpr
        :   atom ('*'^ atom)*
        ; 

atom    :   INT 
        |   ID
        |   '('! expr ')'!
        ;

ID      : ('a'..'z' | 'A'..'Z' )+ ;
INT     : '0'..'9'+ ;
NEWLINE : '\r'? '\n' ;
WS      : ( ' ' | '\t' )+ { skip(); } ;

Đầu vào

x=1
y=2
3*(x+y)

Parse Tree

Cây phân tích cú pháp là một biểu diễn cụ thể của đầu vào. Cây phân tích cú pháp giữ lại tất cả thông tin của đầu vào. Các hộp trống đại diện cho khoảng trắng, tức là kết thúc của dòng.

Parse Tree

AST

AST là một biểu diễn trừu tượng của đầu vào. Lưu ý rằng các parens không có trong AST vì các kết hợp có thể lấy được từ cấu trúc cây.

AST

Để biết thêm thông tin, hãy xem Trình biên dịch và trình tạo trình biên dịch pg. 23
hoặc là Cây cú pháp trừu tượng trên pg. 21 in Cú pháp và ngữ nghĩa của ngôn ngữ lập trình 


80
2018-03-25 22:14



Làm thế nào để bạn lấy được AST từ cây phân tích cú pháp? Phương pháp đơn giản hóa một cây phân tích thành một AST là gì? - CMCDragonkai
Không có thuật toán cụ thể nào lấy được AST từ cây phân tích cú pháp. Những gì đi vào AST là nhiều hơn một sở thích cá nhân nhưng phải chứa đủ thông tin để hoàn thành nhiệm vụ. Tôi loại trừ các parens từ AST bằng cách sử dụng ANTLR ! nhà điều hành trong ngữ pháp vì chúng không cần thiết, nhưng theo mặc định thì ANTLR sẽ bao gồm chúng. Tôi nghĩ cây phân tích như cho bạn mọi thứ cho dù bạn có cần hay không, và AST sẽ cho bạn mức tối thiểu. Hãy nhớ rằng bạn sẽ đi qua cây rất nhiều, vì vậy kích thước vấn đề. - Guy Coder
Bạn có nghĩa là như CST (cây cú pháp cụ thể) so với AST (cây cú pháp trừu tượng)? - CMCDragonkai
Các hành động / quy tắc ngữ nghĩa được nhúng trong tệp cú pháp của trình phân tích cú pháp hoặc trình phân tích cú pháp là cách phân tích ngữ nghĩa thông thường và tạo AST, trong khi cây phân tích hiếm khi, nếu được xây dựng hoặc sử dụng bởi mã người dùng, ngoại trừ có lẽ để xác minh tính chính xác của trình phân tích cú pháp. - Barry
Lãi: Biểu đồ ngữ nghĩa trừu tượng - Guy Coder


Từ những gì tôi hiểu, AST tập trung nhiều hơn vào các mối quan hệ trừu tượng giữa các thành phần của mã nguồn, trong khi cây phân tích tập trung vào việc thực hiện ngữ pháp được sử dụng bởi ngôn ngữ, bao gồm các chi tiết nitpicky. Chúng chắc chắn không giống nhau, vì thuật ngữ khác cho "phân tích cây" là "cây cú pháp cụ thể".

tôi đã tìm thấy cái này trang cố gắng giải quyết câu hỏi chính xác này.


15
2018-02-17 08:30





Các Sách DSL Martin Fowler giải thích điều này một cách độc đáo. AST chỉ chứa tất cả các phần tử 'hữu ích' sẽ được sử dụng để xử lý tiếp, trong khi cây phân tích chứa tất cả các tạo phẩm (dấu cách, dấu ngoặc, ...) từ tài liệu gốc bạn phân tích cú pháp


9
2018-02-17 08:36





Lấy bài tập pascal Tuổi: = 42;

Cây cú pháp sẽ trông giống như mã nguồn. Dưới đây tôi đặt dấu ngoặc xung quanh các nút. [Tuổi] [: =] [42] [;]

Một cây trừu tượng sẽ trông như thế này [=] [Tuổi] [42]

Việc gán sẽ trở thành một nút với 2 phần tử, Age và 42. Ý tưởng là bạn có thể thực hiện nhiệm vụ.

Cũng lưu ý rằng cú pháp pascal biến mất. Do đó, có thể có nhiều hơn một ngôn ngữ tạo ra cùng một AST. Điều này rất hữu ích cho các công cụ tập lệnh ngôn ngữ chéo.


3
2017-08-04 14:26





Trong phân tích các nút bên trong cây phân cách không phải là thiết bị đầu cuối, lá là thiết bị đầu cuối. Trong các nút bên trong cây cú pháp là toán tử, lá là toán hạng.


1
2017-11-25 12:56