Apa contoh paling sederhana di luar sana untuk menjelaskan perbedaan antara Pohon Parse dan Pohon Sintaks Abstrak?

Menurut pemahaman saya, pengurai membuat pohon pengurai, dan kemudian membuangnya. Namun, ia juga dapat memunculkan pohon sintaksis abstrak, yang seharusnya digunakan oleh kompiler.

Saya mendapat kesan bahwa baik pohon parse dan pohon sintaksis abstrak dibuat di bawah tahap parsing. Lalu dapatkah seseorang menjelaskan mengapa ini berbeda?

Pohon parse juga dikenal sebagai pohon sintaksis beton.

Pada dasarnya, pohon abstrak memiliki informasi yang lebih sedikit daripada pohon beton. Pohon beton mengandung setiap elemen dalam bahasa, sedangkan pohon abstrak telah membuang potongan-potongan yang tidak menarik.

Misalnya ungkapan: (2 + 5) * 8

Betonnya terlihat seperti ini

  ( 2  + 5 )  * 8
  |  \ | / |  | |
  |   \|/  |  | |
   \___|__/   | |
       \______|/

Sedangkan pohon abstrak memiliki:

2  5 
 \/   
  +  8
   \/
   *

Dalam kasus konkret tanda kurung dan semua bagian bahasa telah dimasukkan ke dalam pohon. Dalam kasus abstrak kurung hilang, karena informasinya telah dimasukkan ke dalam struktur pohon.

Hal pertama yang perlu Anda pahami adalah bahwa tidak ada yang memaksa Anda untuk menulis parser atau kompiler dengan cara tertentu. Secara khusus, itu tidak selalu berarti bahwa hasil parser harus berupa pohon. Ini bisa berupa struktur data apa saja yang cocok untuk mewakili input.

Misalnya, bahasa berikut:

prog:
      definition 
    | definition ';' prog
    ;

definition: .....

dapat direpresentasikan sebagai daftar definisi. (Nitpickers akan menunjukkan bahwa daftar adalah pohon yang merosot, tetapi bagaimanapun juga.)

Kedua, tidak perlu berpegangan pada pohon parse (atau struktur data apa pun yang dikembalikan parser). Sebaliknya, kompiler biasanya dibangun sebagai urutan lintasan, yang mengubah hasil lintasan sebelumnya. Oleh karena itu tata letak keseluruhan kompiler bisa jadi:

parser :: String             -> Maybe [Definitions]      -- parser
pass1  :: [Definitions]      -> Maybe DesugaredProg      -- desugarer
pass2  :: DesugaredProg      -> Maybe TypedProg          -- type checker
pass3  :: TypedProg          -> Maybe AbstractTargetLang -- code generation
pass4  :: AbstractTargetLang -> Maybe String             -- pretty printer

compiler :: String           -> Maybe String    -- transform source code to target code
compiler source = do
   defs  <- parser source
   desug <- pass1 defs
   typed <- pass2 desug
   targt <- pass3 typed
   pass4 targt

Intinya: Jika Anda mendengar orang berbicara tentang pohon parse , pohon syntac abstrak , pohon sintaks beton dll, selalu mengganti dengan struktur data yang sesuai untuk tujuan tertentu , dan Anda baik-baik saja sedang.