Journal Détection de la syntaxe d'un langage informatique via un analyseur statistique naïf de type Bayésien

Posté par Octplane (site web personnel) le 28 juin 2012 à 14:06. Licence CC By‑SA.

Étiquettes :

juin

2012

Cher journal,

J'ai décidé d'essayer une petite expérience. J'ai constaté que la plupart des site de "paste" demandent toujours la syntaxe du morceau de code qu'on a collé et franchement, ça m'énerve un peu, parce qu'il ne faut pas être bien malin pour le voir avec ses yeux. En plus, leurs listes déroulantes sont toujours d'une longueur infinie et je trouve jamais le langage que je suis en train de coller (comment ça ? syslog, c'est pas un langage ?). Bref, c'était pénible.

Je me suis dit qu'il était peut être possible de faire cette detection en utilisant un programme. J'ai cherché un peu et la plupart des morceaux de code qui trainent sur la toile sont basés sur l'extension du fichier (Github fait ça par exemple). C'est bien pratique quand on a le fichier sur le disque, mais pas quand on te colle 10 lignes de code; dommage Eliane.

Finalement, je me suis dit, c'est peut être possible via un algo de type Bayésien. Accessoirement, je me suis dit que cela pourrait être un bon moyen d'apprendre un nouveau langage et j'ai choisi Go pour plusieurs raisons:

Il se compile en natif (il va sûrement plus vite que d'autres langages, donc, surtout pour parser des Mo de sources)
Il est multiplateforme (y compris sous windows, dis donc !)
Il semble plus simple que C/C++ (pour lesquels je manque malheureusement de compétences, patience et tolérance pour les indirections et autres pointeurs)
Il est supporté par Google et donc, y a sûrement un paquet de gars qui ont écrit sur code en Go avant moi.

D'ailleurs, pour ma bibliothèque Bayésienne, je suis tombé sur [jbrukh/bayesian](https://github.com/jbrukh/bayesian] dans Github et ça m'arrangeait bien, parce que le background statistique du filtrage Bayésien, a priori, je ne le possède pas.

J'ai attaqué la programmation en faisant un programme d'apprentissage pour indexer des langages à partir de fichiers que j'aurais en local (ce qui est assez ironique quand on pense que je finis par regarder l'extension d'un fichier avant de le cataloguer).

Ensuite, j'ai fait une petit Application Google App Engine qui permet de tester tout cela. Si tu es curieux, tu peux aller sur http://copie-privee.appspot.com/ et essayer avec tes snippets. Evite autre chose que du perl, ruby, python et objective-c.

Ca marche assez mal, mais clairement, tu mets un peu de ruby ou de go, il arrive à le voir. Si ça fait une erreur 500, c'est parce que mon code est pas très robuste, na !

Ca marche mal, pour plusieurs raisons:

c'est un prototype tout pourri, qui gère mal les erreurs
appengine est trop petit pour me permettre de charger un fichier de stats assez conséquent (limitation à 32MB par fichier, l'index que j'ai calculé avec 23000 documents en fait le double)
ma tokenisation est assez maladroite: j'indexe les commentaires et les noms de variable, et ça, c'est moche…

Cependant, la preuve de concept fonctionne assez bien. Voici les directions dans lesquelles je veux faire évoluer le projet:

le faire marcher ailleurs que sur GAE
Indexer du c++, c, perl, shell en volume suffisant pour que cela fonctionne un peu
Trouver une astuce pour tokenizer différemment et avoir des index à la fois plus efficaces et plus compact
Tester si indexer une simple grammaire pour chaque language (et rien de plus) ne donne pas quelque chose d'intéressant
Tester si indexer des n-grams (un peu comme les chaînes de Markov) ne donne pas de meilleurs résultats. J'en suis presque convaincu, mais il faut absolument symboliser le code pour rendre ça efficace.

Finalement, tout est open-source, alors si tu t'ennuies ce soir, tu peux jouer avec : https://github.com/octplane/go-code-classifier

A bientôt :)

# Dans la meme veine...

Posté par Allan Simon (site web personnel) le 28 juin 2012 à 14:23. Évalué à 4.

Intéressant j'ai codé il y a pas longtemps un détecteur de langues automatique pour Tatoeba (langue naturelle du coup) un peu près dans la meme veine (pour l'instant j'utilise une méthode naive a base comme toi d'apprentissage et pondération de N-gramme pour donner la langue la plus probable)

Je suis bientôt en vacances je vais essayer de regarder ton code et de mettre le mien accessible en ligne, voir s'il y a moyen de s'inspirer.
- [^] # Re: Dans la meme veine...
  
  Posté par Octplane (site web personnel) le 28 juin 2012 à 14:43. Évalué à 3.
  
  Ha ben oui, ça peut intéressant. Mon code n'est vraiment rocket science, à vrai dire… C'est écrit dans quel langage ?
  
  Bonnes vacances !
# 32 Mo ?

Posté par Nicolas Boulay (site web personnel) le 28 juin 2012 à 14:45. Évalué à 4.

J'imagine que les 32 Mo sont les stat sur les token de tes fichiers de tests ?

A mon avis tu peux le filtrer à mort, pour virer tout ce qui apparait peu et tout ce qui trop proche de 50%.

A mon avis, faire des stats sur la grammaire doit avoir de bien meilleur résultat.

Il est aussi possible de faire des stats sur la prédiction de présence d'un mot après un autre mot. Dans le cas d'un langage de programmation, tu peux peut-être faire ressortir la structure en arbre des grammaire. En gros, tu ne parses pas ton code comme une suite de mot mais comme une suite de boite qui s'emboite.

Je ne sais pas si c'est possible, mais un code source est hautement hiérarchique, cela devrait aider à identifié le langage.

"La première sécurité est la liberté"
- [^] # Re: 32 Mo ?
  
  Posté par Octplane (site web personnel) le 28 juin 2012 à 15:11. Évalué à 1.
  
  Pas bête l'idée du filtre. J'y avais pas pensé "de base". Je vais regarder cette solution avant de m'attaquer à la recherche des grammaires de l'ensemble des langage de programmation connus…
  
  Pour le coup des boites dans les boites, c'est pas mal, mais il faut arriver à trouver les limites des boites justement. Sans parser, ca me paraît par évident. Essayer d'isoler des motifs qui se répètent dans le code indexé ?
  - [^] # Re: 32 Mo ?
    
    Posté par Nicolas Boulay (site web personnel) le 28 juin 2012 à 15:25. Évalué à 3.
    
    Pour les boites, peut-être que tu peux les trouver par apprentissage. Ou alors, tu peux guider le truc avec le codage en dure de tout les symboles qui vont par 2 : (),[], /* */….
    
    "La première sécurité est la liberté"
    - [^] # Re: 32 Mo ?
      
      Posté par Ontologia (site web personnel) le 29 juin 2012 à 10:13. Évalué à 2.
      
      En gros, si je comprend bien, tu utiliserais un lexer universelle et tu constuirais ton apprentissage sur le résultat du lexer ?
      
      « Il n’y a pas de choix démocratiques contre les Traités européens » - Jean-Claude Junker
      - [^] # Re: 32 Mo ?
        
        Posté par Nicolas Boulay (site web personnel) le 29 juin 2012 à 10:40. Évalué à 2.
        
        le lexer universelle serait là uniquement pour détecter une forme hiérarchique. Le reste est identique.
        
        Cela permet de détecter des forme comme if (…) then … ou
        if (…) …} // impossible de mettre l'accolade ouvrante : #### Votre titre
        
        "La première sécurité est la liberté"
# listes déroulantes sont toujours d'une longueur infinie

Posté par __o le 28 juin 2012 à 15:01. Évalué à 3.

Quand la liste a le focus (ou quand elle est ouverte), tapes les premières lettres de ton langage, et regarde la magie :)
- [^] # Re: listes déroulantes sont toujours d'une longueur infinie
  
  Posté par Octplane (site web personnel) le 28 juin 2012 à 15:11. Évalué à 3.
  
  J'ai pas de clavier. :-(
  - [^] # Re: listes déroulantes sont toujours d'une longueur infinie
    
    Posté par __o le 28 juin 2012 à 15:25. Évalué à 2.
    
    Si tu codes en parlant à ta machine, je suis sûr que ça marche aussi.
    
    Sinon, je sais pas comment tu codes, mais ça m'intéresse ;)
    - [^] # Re: listes déroulantes sont toujours d'une longueur infinie
      
      Posté par AP le 28 juin 2012 à 16:18. Évalué à 4.
      
      Référence obligée… :)
      https://www.youtube.com/watch?v=hShY6xZWVGE
# Linguist

Posté par Dorian le 28 juin 2012 à 15:12. Évalué à 6.

Github utilise Linguist.

« En fait, le monde du libre, c’est souvent un peu comme le parti socialiste en France » Troll
- [^] # Re: Linguist
  
  Posté par Octplane (site web personnel) le 28 juin 2012 à 15:22. Évalué à 1.
  
  Ha oui, je m'aperçois qu'ils ont rajouté un système de classification bayésienne que je n'avais pas vu à l'époque. Y a même le fichier de tokens. Grmbl. Si j'avais su/vu.
  - [^] # Re: Linguist
    
    Posté par Arthur Geek (site web personnel) le 28 juin 2012 à 16:07. Évalué à 2.
    
    Grmbl. Si j'avais su/vu.
    
    Au moins tu t'es lancé dans un truc plutôt intéressant et formateur.
    
    Moi, j'en serais resté au stade de "faudrait faire ça" et j'aurais laissé mon poil dans la main décider.
    
    Faut dire que j'ai du mal à me lancer durablement dans le code.
    
    Prochainement, je vous proposerai peut-être un commentaire constructif.
    - [^] # Re: Linguist
      
      Posté par Narmer le 28 juin 2012 à 16:18. Évalué à 2.
      
      Faut dire que j'ai du mal à me lancer durablement dans le code
      
      Installer vous sur le divan je vous prie.
      Parlez moi de votre enfance
# Bonne première impression

Posté par purplepsycho le 28 juin 2012 à 15:15. Évalué à 2.
J'ai testé avec
```
#include <stdio.h>
int main(void) {
    puts("hello");
    return 0;
}
```
Ça m'a renvoyé «Objective-C» : bon début, on a hate de voir plus de langage
# Le go est lent!

Posté par devnewton 🍺 (site web personnel) le 28 juin 2012 à 16:40. Évalué à 3.

Il se compile en natif (il va sûrement plus vite que d'autres langages, donc, surtout pour parser des Mo de sources)

Il n'a pas de super résultats sur http://shootout.alioth.debian.org/

Le post ci-dessus est une grosse connerie, ne le lisez pas sérieusement.
# Combien ça marche bien ?

Posté par Jiehong (site web personnel) le 28 juin 2012 à 21:38. Évalué à 3.

Il te serait utile de chiffrer la « qualité » de la détection en calculant le score F1 par exemple.

Mais n'oublie surtout pas que si tu veux vraiment te lancer dans une méthode d'apprentissage avec des MMC ou des modèles n-grams (et plus), il va te falloir beaucoup de données. Plus d'auras de données et plus tes méthodes se concentreront sur ce qui est redondant (du coup, naturellement, les noms de variables ne seront pas pris en compte par exemple, le contenu des commentaires non plus mais peut-être que les 2 premiers caractères des commentaires sont précieux, etc.).

Pour en revenir à ton programme bayésien, n'oublie-pas qu'un a priori bien estimé peu grandement aider (ex : P(python|"import xxx") est élevé).
# Parsing compilation

Posté par jay le 29 juin 2012 à 01:48. Évalué à 1.

Hello,

ton projet à l'air sympa, mais je pense que tu aurais un meilleur résultat en faisant une analyse lexicale et un parseur. Comme si tu voulais compiler le code. Et avec le nombres d'erreurs retournées utiliser les probabilités pour décider quel langage choisir.

Je pense qu'on peut y arriver avec uniquement les probabilités/fréquences des mots en comparant avec bon corpus d'exemple de code. Les N-gram sont probablement les plus pertinent avec les probabilités. Seulement le nom des variables sont une perte de temps à analyser et peuvent être communes à plusieurs langages, de même pour les bibliothèques.
Enfin je veux dire que je pense que tu arrivera à un résultat approximatif pour beaucoup de travail alors qu'il existe une méthode presque exacte: essayer de compiler ton programme.

Sinon peut-être une idée : recherche des tokens d'un langage dans un code (token du C par exemple) et puis comparer la proportion de token au reste du code et ensuite tu utilise les probabilités avec ton corpus de code C.
- [^] # Re: Parsing compilation
  
  Posté par Shuba le 29 juin 2012 à 08:32. Évalué à 1.
  
  L'avantage de faire une analyse statistique avant, c'est que ça peut te permettre de choisir l'ordre dans lequel tu fais les tests lexicaux des différents langages, et donc d'avoir de meilleures performances qu'en testant tout les analyseurs lexicaux jusqu'à en obtenir un qui marche.
  - [^] # Re: Parsing compilation
    
    Posté par Axioplase ıɥs∀ (site web personnel) le 29 juin 2012 à 09:03. Évalué à 3.
    
    Tu sais, c'est à mon avis pas long de vérifier qu'un lexeur/parseur n'est pas le bon…
# À mettre dans les tests

Posté par 2PetitsVerres le 29 juin 2012 à 05:38. Évalué à 7.
```
#include "hello_world.c"

#if 0

print "Hello, Python!"

#endif
```
Tu détectes quoi ?

Tous les nombres premiers sont impairs, sauf un. Tous les nombres premiers sont impairs, sauf deux.
- [^] # Re: À mettre dans les tests
  
  Posté par Octplane (site web personnel) le 04 juillet 2012 à 20:13. Évalué à 1.
  
  Mon prototype qui utilise maintenant Github/linguist annonce du C++ (ou peut être Objective-C ou même C).. Z'en dites quoi ?
  - [^] # Re: À mettre dans les tests
    
    Posté par 2PetitsVerres le 05 juillet 2012 à 14:16. Évalué à 2.
    
    J'aurais plutôt dit du C ou du Python, mais je suppose que n'importe quel dérivé du C qui garde le préprocesseur doit pouvoir être bon. En modifiant un peu, ça doit aussi pouvoir être du whitespace.
    
    Tous les nombres premiers sont impairs, sauf un. Tous les nombres premiers sont impairs, sauf deux.
- [^] # Re: À mettre dans les tests
  
  Posté par 2PetitsVerres le 05 juillet 2012 à 14:21. Évalué à 3.
  Une version améliorée
```
#include <stdio.h>

#if 0
"""
#endif
int main(int argc, char * argv[]) {
  printf("Hello, World!");
  return 0;
}


#if 0
"""

print "Hello, World!"
#endif
```
  Tous les nombres premiers sont impairs, sauf un. Tous les nombres premiers sont impairs, sauf deux.
  - [^] # Re: À mettre dans les tests
    
    Posté par Shuba le 05 juillet 2012 à 15:57. Évalué à 1. Dernière modification le 05 juillet 2012 à 15:57.
    Une version obfusquée :
```
#include <stdio.h>
#define import
#define sys
import sys

#define s int main( int argc, char ** args ) { struct { int a; } c; char * str
s = "Hello, "
#define for ; printf(str); for ( 
#define i c.a
#define in = 1;
#undef sys
#define sys c
#define argv a < argc; ++c.a ) { char * zde = "
#undef s
#define s "; int zou = 1; zou
//#define i 1; printf(args[c.a]); zou = 0 
for i in sys.argv[1:]: s += i + " "
#define print ; printf("%s", args[i]); } printf("\n");
#undef s
#define s }
print s
```
    Malheureusement ça ne compile pas parfaitement, il faut appliquer le préprocesseur à la main puis compiler son output…
# Ohloh aussi

Posté par Philippe F (site web personnel) le 29 juin 2012 à 12:55. Évalué à 3.

Ohloh a aussi développé ce genre de truc, mais c'est pas du bayesien, je crois que la détection est manuelle :

https://github.com/blackducksw/ohcount

Ils utilisent ça pour comptabiliser les lignes de codes d'un projet donné, par langage.
# je crois que source-highlite le fait

Posté par Zylabon le 01 juillet 2012 à 15:44. Évalué à 1.

https://www.gnu.org/software/src-highlite/

si ça t’intéresse :)

Please do not feed the trolls

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.