Como alguém pode comparar a forma das árvores de sintaxe abstrata de programas similares de código-fonte (C, C ++, Go ou qualquer coisa compilada com o GCC ...)?
Acho que a detecção de plágio no código-fonte usaria essas técnicas, mas não tenho idéia de como isso seria chamado ...
Por exemplo, a unificação pode ser usada para comparar o AST, mas fornece apenas uma resposta booleana. Eu estou procurando por alguma técnica que dê alguma "distância" numérica ou algum tipo de vetor numérico (para ser alimentado posteriormente, por exemplo, algoritmos de aprendizado de máquina ou classificação, ou alguma outra coisa de big data).
Todas as referências a big data ou abordagens de aprendizado de máquina em um grande conjunto de códigos-fonte também são bem-vindas.
(Desculpe por uma pergunta tão ampla ou confusa, não sei qual terminologia usar)
Não quero simplesmente comparar dois ASTs ou programas. Eu quero processar um grande conjunto de programas (por exemplo, metade de um código-fonte de distribuição Debian) e encontrar dentro dele rotinas semelhantes. Eu já tenho o MELT para trabalhar em representações internas do GCC (Gimple) e quero aproveitar acima disso, portanto, armazeno várias métricas (quais? A complexidade ciclomática provavelmente não é suficiente) em, por exemplo, alguns bancos de dados e os compara e processa ...
Adendo: Encontrado sobre o sistema e o papel MOSS , mas parece não se importar com a forma sintática. Também olhando para a distância de edição em árvore .
Também foi encontrada (graças a Jérémie Salvucci) a tese de doutorado de Michel Chilowicz (em francês, novembro de 2010) sobre Procurando similaridade no código-fonte
fonte
Respostas:
Uma abordagem seria compilar a fonte em XML e, em seguida, analisar a diferença entre os dois bits da fonte. Por exemplo, no mundo Java, a ferramenta de análise estática pmd faz isso como uma abordagem para procurar coisas a serem avisadas.
é 'compilado' para:
E nesse ponto você compararia o código dizendo "a diferença entre esse código e esse código é que esse nome é diferente". Como o acima é realmente xml, isso pode ser feito com qualquer número de ferramentas de comparação xml existentes. Ou, se você estava atrás de um número, poderia aplicar um algoritmo de distância de edição em árvore ( questão relacionada ao SO ).
Outra abordagem é observar a 'assinatura' da forma do código. A Pesquisa de Assinaturas foi realizada por Ward Cunningham
Essa lenda é um pouco difícil de ler:
14m
significa 14 métodos294L
é 294 linhas..
é uma linha não em branco'
é um comentário|
(verde) é umaif
declaração de linha única .(.)
(verde) é uma única instrução dentro de umif
bloco[(.)]
(marrom) é uma única instrução dentro deif
um loop interno.{.}
é um método com uma única instrução.[.]
(vermelho) é uma única instrução dentro de um loop([.])
(vermelho escuro) é uma única instrução dentro de um loop dentro de um bloco if.A comparação de dois conjuntos de códigos é observar a distância de edição entre duas strings com um idioma muito limitado.
fonte