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

Posté par (page perso) . Licence CC by-sa
Tags :
20
28
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 (page perso) . É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 (page perso) . É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 . É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 (page perso) . É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 . É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 (page perso) . É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 . É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 . É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 :)

  • # Linguist

    Posté par (page perso) . É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 (page perso) . É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 (page perso) . É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 . É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 . É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 (page perso) . É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/

    http://devnewton.bci.im

  • # Combien ça marche bien ?

    Posté par (page perso) . É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 . É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 . É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.

  • # À mettre dans les tests

    Posté par . É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 (page perso) . É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 . É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 . É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 . Évalué à 1. Dernière modification le 05/07/12 à 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 (page perso) . É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 . É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 à ceux qui les ont postés. Nous n'en sommes pas responsables.