quantitativer Vergleich von AST-Formen

8

Wie könnte man die Form abstrakter Syntaxbäume ähnlicher Quellcode-Programme (C, C ++, Go oder irgendetwas mit GCC kompiliertes ...) vergleichen?

Ich denke, dass die Plagiatserkennung im Quellcode solche Techniken verwenden würde, aber ich habe keine Ahnung, wie das heißen würde ...

Zum Beispiel könnte die Vereinheitlichung verwendet werden, um AST zu vergleichen, aber es gibt nur eine boolesche Antwort. Ich suche nach einer Technik, die eine numerische "Distanz" oder eine Art numerischer Vektoren angibt (um später z. B. zu maschinellem Lernen oder Klassifizierungsalgorithmen oder einer anderen Big-Data-Sache zu gelangen).

Verweise auf Big Data oder maschinelle Lernansätze für große Mengen an Quellcode sind ebenfalls willkommen.

(Entschuldigung für eine so breite oder unscharfe Frage, ich weiß nicht, welche Terminologie ich verwenden soll)

Ich möchte nicht einfach zwei ASTs oder Programme vergleichen. Ich möchte eine große Anzahl von Programmen (z. B. die Hälfte eines Debian-Distributionsquellcodes) verarbeiten und darin ähnliche Routinen finden. Ich habe bereits MELT , um an internen GCC-Darstellungen (Gimple) zu arbeiten, und ich möchte darüber hinaus nutzen, daher mehrere Metriken (welche - zyklomatische Komplexität ist wahrscheinlich nicht ausreichend) in z. B. einer Datenbank speichern und vergleichen und verarbeiten ...

Nachträge: Gefunden über das MOSS- System und das Papier, aber es scheint sich überhaupt nicht um die syntaktische Form zu kümmern. Schauen Sie sich auch die Baumbearbeitungsentfernung an .

Gefunden auch (dank Jérémie Salvucci) Michel Chilowicz 'Doktorarbeit (auf Französisch, November 2010) über die Suche nach Ähnlichkeit im Quellcode

parsing syntax machine-learning big-data Basile Starynkevitch
quelle
Sie möchten es also auf die altmodische Art des maschinellen Lernens mit handgefertigten Funktionen tun? Für Sprachthemen war Deep Learning in den letzten Jahren recht erfolgreich ... Ich würde mir vorstellen, dass die Formen der Kontrollfluss- und Datenflussdiagramme zur Charakterisierung von Code nützlich sein könnten - aber die Verringerung der Baumähnlichkeit zur Diagrammähnlichkeit ist möglicherweise nicht so ein hilfreicher Vorschlag.
Patrick
Ich bin offen für andere Ideen und suche Referenzen und Terminologie.
Basile Starynkevitch

Antworten:

6

Ein Ansatz wäre, die Quelle in XML zu kompilieren und dann zu untersuchen, wie unterschiedlich die beiden Quellbits sind. In der Java-Welt verwendet das statische Analysetool pmd dies beispielsweise, um nach Warnhinweisen zu suchen.

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

wird 'kompiliert' zu:

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

Und an diesem Punkt würden Sie Code vergleichen, indem Sie sagen: "Der Unterschied zwischen diesem Code und diesem Code besteht darin, dass dieser Name unterschiedlich ist." Da es sich bei dem oben genannten tatsächlich um XML handelt, kann dies mit einer beliebigen Anzahl vorhandener XML-Vergleichstools durchgeführt werden. Oder wenn Sie nach einer Reihe sind, könnte man einen anwenden Baum Editierdistanz Algorithmus darauf (verwandte Frage SO ).

Ein anderer Ansatz besteht darin, die 'Signatur' der Codeform zu betrachten. Die Signaturumfrage wurde von Ward Cunningham durchgeführt

Alt-Text

Diese Legende ist etwas schwer zu lesen:

  • 14m bedeutet 14 Methoden
  • 294L ist 294 Zeilen.
  • . ist eine nicht leere Zeile
  • ' ist ein Kommentar
  • | (grün) ist eine einzelne Zeile if Anweisung.
  • (.) (grün) ist eine einzelne Aussage in einem if Blocks
  • [(.)] (braun) ist eine einzelne Aussage innerhalb eines if innerhalb einer Schleife.
  • {.} ist eine Methode mit einer einzelnen Anweisung.
  • [.] (rot) ist eine einzelne Anweisung innerhalb einer Schleife
  • ([.]) (dunkelrot) ist eine einzelne Anweisung innerhalb einer Schleife innerhalb eines if-Blocks.

Beim Vergleichen von zwei Codesätzen wird dann der Bearbeitungsabstand zwischen zwei Zeichenfolgen mit einer sehr begrenzten Sprache betrachtet.

Thomas Owens
quelle