Apa perbedaan antara pohon parse dan AST?

94

Apakah mereka dihasilkan oleh tahapan proses kompilasi yang berbeda? Atau apakah mereka hanya nama yang berbeda untuk hal yang sama?

compiler-construction terminology compiler-theory abstract-syntax-tree parse-tree Thomson
sumber
Parse Tree adalah hasil dari tata bahasa Anda dengan artefaknya (Anda dapat menulis tak terhingga tata bahasa untuk bahasa yang sama), AST mengurangi Parse Tree sedekat mungkin dengan bahasa tersebut. Beberapa tata bahasa untuk bahasa yang sama akan memberikan pohon parse yang berbeda tetapi akan menghasilkan AST yang sama. (Anda juga dapat mengurangi skrip yang berbeda (pohon parse berbeda dari tata bahasa yang sama) ke AST yang sama)
Guillaume86
1
Jawaban SO ini membahas perbedaan secara rinci: stackoverflow.com/a/1916687/120163
Ira Baxter
1
Kemungkinan duplikat dari Apa perbedaan antara pohon parse dan pohon sintaks abstrak?
penasarandannii

Jawaban:

98

Ini didasarkan pada tata bahasa Penilai Ekspresi oleh Terrence Parr.

Tata bahasa untuk contoh ini:

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(); } ;

Memasukkan

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

Parse Tree

Pohon parse adalah representasi konkret dari input. Pohon parse menyimpan semua informasi masukan. Kotak kosong mewakili spasi, yaitu akhir baris.

Parse Tree

AST

AST adalah representasi abstrak dari input. Perhatikan bahwa tanda kurung tidak ada dalam AST karena asosiasinya diturunkan dari struktur pohon.

AST

Untuk penjelasan lebih lanjut lihat Compilers and Compiler Generators hal. 23
atau Pohon Sintaks Abstrak pada hal. 21 dalam Sintaks dan Semantik Bahasa Pemrograman

Guy Coder
sumber
5
Bagaimana Anda mendapatkan AST dari pohon parse? Apa metode menyederhanakan pohon parse menjadi AST?
CMCDragonkai
3
Tidak ada algoritme khusus untuk mendapatkan AST dari pohon parse. Apa yang dimasukkan ke dalam AST lebih merupakan preferensi pribadi tetapi harus berisi cukup info untuk menyelesaikan tugas. Saya mengecualikan parens dari AST dengan menggunakan ANTLR ! operator dalam tata bahasa karena tidak diperlukan, tetapi secara default ANTLR akan menyertakannya. Saya menganggap pohon parse memberi Anda segalanya baik Anda membutuhkannya atau tidak, dan AST memberi Anda nilai minimum. Ingatlah bahwa Anda akan sering melintasi pepohonan, jadi ukuran itu penting.
Guy Coder
2
Maksud Anda seperti CST (pohon sintaks konkret) vs AST (pohon sintaks abstrak)?
CMCDragonkai
Tindakan / aturan semantik yang disematkan dalam file sintaksis pembuat parser atau parser adalah cara yang biasa digunakan untuk analisis semantik dan membuat AST, sedangkan pohon parse jarang, jika pernah dibuat atau digunakan oleh kode pengguna, kecuali mungkin untuk verifikasi kebenaran parser.
Yang menarik: Grafik semantik abstrak
Guy Coder
16

Dari apa yang saya pahami, AST lebih fokus pada hubungan abstrak antara komponen kode sumber, sedangkan pohon parse berfokus pada implementasi sebenarnya dari tata bahasa yang digunakan oleh bahasa, termasuk detail yang tidak jelas. Mereka pasti tidak sama, karena istilah lain untuk "pohon parse" adalah "pohon sintaks konkret".

Saya menemukan halaman ini yang mencoba menjawab pertanyaan yang sama persis.

Ken Wayne VanderLinde
sumber
11

The book DSL dari Martin Fowler menjelaskan ini baik. AST hanya berisi semua elemen 'berguna' yang akan digunakan untuk pemrosesan lebih lanjut, sedangkan pohon parse berisi semua artefak (spasi, tanda kurung, ...) dari dokumen asli yang Anda parse

Wim Deblauwe
sumber
4

Ambil tugas pascal Umur: = 42;

Pohon sintaks akan terlihat seperti kode sumber. Di bawah ini saya meletakkan tanda kurung di sekitar node. [Usia] [: =] [42] [;]

Sebuah pohon abstrak akan terlihat seperti ini [=] [Age] [42]

Tugas menjadi node dengan 2 elemen, Usia dan 42. Idenya adalah Anda dapat melaksanakan tugas tersebut.

Perhatikan juga bahwa sintaks pascal menghilang. Jadi dimungkinkan untuk memiliki lebih dari satu bahasa yang menghasilkan AST yang sama. Ini berguna untuk mesin skrip lintas bahasa.

William Egge
sumber
1

Dalam simpul interior pohon parse adalah non terminal, daun adalah terminal. Dalam sintaksis node interior pohon adalah operator, daun adalah operan.

Roshani Patel
sumber