comparación cuantitativa de formas AST

¿Cómo se puede comparar la forma de los árboles de sintaxis abstracta de programas de código fuente similares (C, C ++, Go o cualquier cosa compilada con GCC ...)?

Supongo que la detección de plagio en el código fuente usaría tales técnicas, pero no tengo idea de cómo se llamaría eso ...

Por ejemplo, la unificación podría usarse para comparar AST, pero solo da una respuesta booleana. Estoy buscando alguna técnica que proporcione cierta "distancia" numérica, o algún tipo de vectores numéricos (para luego alimentarlos, por ejemplo, al aprendizaje automático o los algoritmos de clasificación, o alguna otra cosa de big data).

Cualquier referencia a big data o enfoques de aprendizaje automático en un gran conjunto de código fuente también es bienvenida.

^{(Perdón por una pregunta tan amplia o confusa, no sé qué terminología usar)}

No quiero simplemente comparar dos AST o programas. Quiero procesar un gran conjunto de programas (por ejemplo, la mitad de un código fuente de distribución de Debian) y encontrar dentro de él rutinas similares. Ya tengo MELT para trabajar en las representaciones internas de GCC (Gimple) y quiero aprovechar esto, por lo tanto, almacenar varias métricas (¿cuáles? La complejidad ciclomática probablemente no sea suficiente) en, por ejemplo, alguna base de datos y compararlas y procesarlas ...

Addenda: Se encuentra sobre el sistema MOSS y el papel, pero no parece importarle la forma sintáctica. También mirando en la distancia de edición del árbol .

También se encuentra (gracias a Jérémie Salvucci) la tesis doctoral de Michel Chilowicz (en francés, noviembre de 2010) sobre la búsqueda de similitudes en el código fuente

Un enfoque sería compilar la fuente en XML y luego observar cuán diferentes son los dos bits de la fuente. Por ejemplo, en el mundo de Java, la herramienta de análisis estático pmd hace esto como su enfoque para buscar cosas sobre las que advertir.

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

se 'compila' para:

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

Y ese punto sería comparar código diciendo "la diferencia entre este código y ese código es que este nombre es diferente". Como lo anterior es en realidad xml, esto podría hacerse con cualquier cantidad de herramientas de comparación xml que existan. O si buscara un número, uno podría aplicar un algoritmo de distancia de edición de árbol ( pregunta SO relacionada ).

Otro enfoque es mirar la 'firma' de la forma del código. La encuesta de firma fue realizada por Ward Cunningham

Esa leyenda es un poco difícil de leer:

• 14m significa 14 métodos
• 294L es de 294 líneas.
• . es una línea no en blanco
• ' es un comentario
• |(verde) es una ifdeclaración de una sola línea .
• (.)(verde) es una declaración única dentro de un ifbloque
• [(.)](marrón) es una declaración única dentro de un ifbucle dentro de un bucle.
• {.} Es un método con una sola declaración.
• [.] (rojo) es una declaración única dentro de un bucle
• ([.]) (rojo oscuro) es una declaración única dentro de un bucle dentro de un bloque if.

Al comparar dos conjuntos de código, se observa la distancia de edición entre dos cadenas con un lenguaje muy limitado.