secara kuantitatif membandingkan bentuk AST

Bagaimana kita bisa membandingkan bentuk pohon sintaksis abstrak dari program kode sumber serupa (C, C ++, Go, atau apa pun yang dikompilasi dengan GCC ...)?

Saya kira deteksi plagiarisme pada kode sumber akan menggunakan teknik-teknik seperti itu, tetapi saya tidak tahu bagaimana itu disebut ...

Misalnya, unifikasi dapat digunakan untuk membandingkan AST, tetapi hanya memberikan jawaban boolean. Saya sedang mencari beberapa teknik yang memberikan beberapa "jarak" numerik, atau semacam vektor numerik (untuk kemudian diumpankan misalnya untuk pembelajaran mesin atau algoritma klasifikasi, atau beberapa hal big data lainnya).

Referensi apa pun untuk big data atau pendekatan pembelajaran mesin pada set besar kode sumber juga diterima.

^{(Maaf untuk pertanyaan yang luas atau kabur, saya tidak tahu terminologi apa yang digunakan)}

Saya tidak hanya ingin membandingkan dua AST atau program. Saya ingin memproses serangkaian besar program (misalnya setengah dari kode sumber distribusi Debian) dan menemukan di dalamnya rutinitas yang sama. Saya sudah memiliki MELT untuk mengerjakan representasi internal GCC (Gimple) dan saya ingin meningkatkannya, karenanya menyimpan beberapa metrik ( kompleksitas siklomatik mana yang mungkin tidak cukup) dalam misalnya beberapa database dan membandingkan & memprosesnya ...

Tambahan: Ditemukan tentang sistem MOSS & kertas, tetapi tampaknya tidak peduli tentang bentuk sintaksis sama sekali. Juga melihat ke jarak edit pohon .

Ditemukan juga (terima kasih kepada Jérémie Salvucci) Tesis PhD Michel Chilowicz (dalam bahasa Prancis, November 2010) tentang Mencari Kesamaan dalam Kode Sumber

Salah satu pendekatan akan mengkompilasi sumber ke XML dan kemudian melihat betapa berbedanya dua bit sumber. Sebagai contoh, di dunia Java, alat analisis statis PMD melakukan ini sebagai pendekatannya untuk mencari hal-hal yang perlu diperingatkan.

class Example {
 void bar() {
  while (baz)
   buz.doSomething();
 }
}

akan 'dikompilasi' ke:

CompilationUnit
 TypeDeclaration
  ClassDeclaration:(package private)
   UnmodifiedClassDeclaration(Example)
    ClassBody
     ClassBodyDeclaration
      MethodDeclaration:(package private)
       ResultType
       MethodDeclarator(bar)
        FormalParameters
       Block
        BlockStatement
         Statement
          WhileStatement
           Expression
            PrimaryExpression
             PrimaryPrefix
              Name:baz
           Statement
            StatementExpression:null
             PrimaryExpression
              PrimaryPrefix
               Name:buz.doSomething
              PrimarySuffix
               Arguments

Dan saat itu Anda akan membandingkan kode dengan mengatakan "perbedaan antara kode ini dan kode itu adalah bahwa nama ini berbeda." Karena di atas sebenarnya xml, ini bisa dilakukan dengan sejumlah alat perbandingan xml yang ada. Atau jika Anda mengejar angka, seseorang dapat menerapkan algoritma jarak edit pohon di atasnya ( pertanyaan SO terkait ).

Pendekatan lain adalah dengan melihat 'tanda tangan' dari bentuk kode. The Signature Survey dilakukan oleh Ward Cunningham

Legenda itu agak sulit dibaca:

• 14m berarti 14 metode
• 294L adalah 294 baris.
• . adalah garis yang tidak kosong
• ' adalah komentar
• |(hijau) adalah ifpernyataan baris tunggal .
• (.)(hijau) adalah pernyataan tunggal di dalam ifblok
• [(.)](Coklat) adalah pernyataan tunggal di ifdalam loop di dalam.
• {.} adalah metode dengan pernyataan tunggal.
• [.] (Merah) adalah pernyataan tunggal di dalam satu lingkaran
• ([.]) (merah tua) adalah pernyataan tunggal di dalam loop di dalam blok if.

Membandingkan dua set kode kemudian melihat jarak sunting antara dua string dengan bahasa yang sangat terbatas.