confrontando quantitativamente le forme AST

8

Come si può confrontare la forma degli alberi di sintassi astratta di programmi di codice sorgente simili (C, C ++, Go o qualsiasi cosa compilata con GCC ...)?

Immagino che il rilevamento di plagio sul codice sorgente userebbe tali tecniche, ma non ho idea di come si chiamerebbe ...

Ad esempio, l'unificazione potrebbe essere utilizzata per confrontare AST, ma fornisce solo una risposta booleana. Sto cercando una tecnica che fornisca una certa "distanza" numerica, o qualche tipo di vettori numerici (da inserire successivamente ad esempio per algoritmi di apprendimento automatico o di classificazione, o qualche altra cosa sui big data).

Anche i riferimenti ai big data o agli approcci di machine learning su un ampio set di codice sorgente sono i benvenuti.

(Ci scusiamo per una domanda così ampia o confusa, non so quale terminologia usare)

Non voglio semplicemente confrontare due AST o programmi. Voglio elaborare un ampio set di programmi (ad esempio la metà di un codice sorgente di distribuzione Debian) e trovare al suo interno routine simili. Ho già MELT per lavorare su rappresentazioni interne GCC (Gimple) e voglio sfruttare al di sopra di questo, quindi memorizzare diverse metriche (quali? complessità ciclomatica probabilmente non è sufficiente) ad esempio alcuni database e confronta & elaborali ...

Addenda: trovato sul MOSS system & carta, ma non sembra affatto interessata alla forma sintattica. Anche esaminando distanza di modifica dell'albero .

Trovato anche (grazie a Jérémie Salvucci) tesi di dottorato di Michel Chilowicz (in francese, novembre 2010 ) in Ricerca di similarità nel codice sorgente

    
posta Basile Starynkevitch 15.10.2015 - 22:48
fonte

1 risposta

6

Un approccio potrebbe essere quello di compilare la sorgente in XML e poi osservare quanto siano diversi i due bit della sorgente. Ad esempio, nel mondo Java, lo strumento di analisi statica pmd fa questo come approccio alla ricerca di cose per avvisare.

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

viene "compilato" in:

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

E a quel punto dovresti confrontare il codice dicendo "la differenza tra questo codice e quel codice è che questo nome è diverso." Come sopra è in realtà xml, questo potrebbe essere fatto con qualsiasi numero di strumenti di confronto xml che esistono. O se cercavi un numero, potresti applicare un algoritmo tree edit distance su (relativa domanda SO ).

Un altro approccio è guardare la "firma" della forma del codice. Il Signature Survey è stato fatto da Ward Cunningham (related: Come visualizzare il codice? )

Quella leggenda è un po 'difficile da leggere:

  • 14m significa 14 metodi
  • 294L è 294 righe.
  • . è una riga non vuota
  • ' è un commento
  • | (verde) è un'istruzione di riga singola if .
  • (.) (verde) è una singola istruzione all'interno di un blocco if
  • [(.)] (marrone) è una singola istruzione all'interno di un if all'interno di un ciclo.
  • {.} è un metodo con una singola istruzione.
  • [.] (rosso) è una singola istruzione all'interno di un ciclo
  • ([.]) (rosso scuro) è una singola istruzione all'interno di un ciclo all'interno di un blocco if.

Confrontando due serie di codici, osserviamo la distanza di modifica tra due stringhe con un linguaggio molto limitato.

    
risposta data 15.10.2015 - 23:07
fonte

Leggi altre domande sui tag