Journal Exercices de compilations

Posté par .
Tags : aucun
0
5
mar.
2005
Hello,

je dois inventer des exercices pour un cours de compilation.

Il faudrait un projet qui soit faisable quelques heures par semaines sur 7-8 semaines.

Est-ce que quelqu'un a une idée intéressante/ludique pour les étudiants plutôt que l'ultra classique: invention d'un language à 2 balles, écriture d'un compilateur pour ce langage.

Merci
  • # un truc simple ...

    Posté par (page perso) . Évalué à 3.

    ... quoique.

    Un language type C (du moins ses fonctionnalitées de base) avec fonctions, boucles, tests et tout ça ...
    le compilateur doit generer un fichier assembleur qui correspond au programme (language assembleur fictif, instructions de base comme sauts, tests, calls, interruptions etc ... une ou deux douzaines d'instructions seraient surement deja plus que necessaire).
    le tout associé a un assembleur maison lui aussi qui convertit le fichier assembleur en bytecode.
    Reste a écrire une machine virtuelle pour executer tout ca, la VM dispose aussi d'un jeu d'interruptions genre BIOS qui permet d'appeler des fonctions interessantes (comme afficher une image depuis une chaine passée sur la pile ou un truc du genre) (le "BIOS" peut etre fourni par le sujet, ca evitera de deborder trop loin hors de la compilation)
    Ca nous fait donc deux deux organes de compilation qui traitent de deux languages a la sémantique différente, et un automate d'exécution.
    (j'ai eu a faire un projet de ce type en licence, en gros deux nuits blanches pour faire un truc gruiiiik mais qui marchait plutot bien)
    • [^] # Re: un truc simple ...

      Posté par . Évalué à 1.

      Hm ca m'a l'air bien long pour du 7-8 semaines a raison de kk heures par semaines... A mon avis tout le monde n'est pas capable de faire ca en 2 nuits blanches comme toi :p (ou alors si tout le monde dans ta promo était capable j'aurais du aller la ou tu es allé, je me serais moins fait chier ;)

      J'ai deja eu a faire un assembleur éditeur de lien MIPS et un compilo : c'etait deux projets assez long (bien que chacuns bien plus complet que ce que tu décris).

      Et puis ca rentre quand meme un petit peu dans "l'ultra classique: invention d'un language à 2 balles, écriture d'un compilateur pour ce langage." que l'auteur du journal ne souhaite pas :p
      • [^] # Re: un truc simple ...

        Posté par . Évalué à 3.

        On pourrait aussi enfin implémenter les fonctions dans MultiDeskOS ...
      • [^] # Re: un truc simple ...

        Posté par . Évalué à 1.

        Dans le même ordre d'idée, mon prof de compilation (en faites "Théorie des langages et compilation") nous a demandé de coder en Java une machine à pile qui interprete un langage assembleur. Pour cela nous avions deux heures de TP plus la semaine qui suivait.

        Ça se fait bien (environs 6h de boulot) et c'est plutôt intéressant de voir comment fonctionnent nos machines (x86) même si je sais que leurs fonctionnement est quand même plus complexe.

        A propos d'un cours de compilation, je ne vois pas ce que tu peux vraiment faire d'original. De toute façon, le départ est un langage, la finalité est un code exécutable. Evidement tu peux prendre ce que tu veux, ex : convertir un fichier LaTeX en un fichier PDF. (c'est plus un traducteur qu'un compilateur ça)
    • [^] # Re: un truc simple ...

      Posté par (page perso) . Évalué à 2.

      ca ressemble étrangement au truc ultra-classique avec langage à 2 balles qu'il aimerait éviter :)
  • # hmmm

    Posté par (page perso) . Évalué à 3.

    y as le deplacement du cheval, le mort pion, la resolution de labyrinthe par fork modere ( ie: ne pas lancer les 10 000 fork en une fois, mais brider a 10 ou 100 par seconde ), un client/server de chat ala 'talk',

    ce sont tous des projets qui se codent en 2 a 6h suivant le viveau de logique de l eleve, mais ca donne pas mal de fil a retordre.

    Apres il y as les trucs que je n ai pas encore code: un simulateur de fourmiliere: 100 fourmies se deplacent sur une surface de 1000x1000; sur cette surface il y as un morceau de sucre sur chaque case dont les coordonnes modulo 10 sont nulles: 10x10, 10x20, 10x30, 20x10 ... quand une fourmie rencontre un morceau de sucre, elle le prend, et continues la balade; quand elle rencontre un second morceau de sucre, elle laisse le premier avec le second, et se casse ailleurs.

    Le but est de voir la colonie evoluer en temps reel avec une GUI, et d etudier combien de temps il faut pour ne former plus qu un gros tas de sucre.

    il s agit en fait d une simulation theorique d un exercice classique de robotique: 10 robots avec des pions dans un carre, combien de temps faut il au robot pour regroupper les pions.

    La tu as au moins de l IA , GUI, et multitasking, et pourquoi pas introduire un peu d objet ou le client/server quelque part ...

    Enfin, le plus dans tous ces projets, c est de faire ecrire des makefile generiques pour compilation automatique de gros projets:
    projet: toutes les targets dans le Makefile, un README, un dossier src et un dossier doc
    un make doit par default construire a la fois les docs (en latex) et les binaires
    le dossier src contiendra un ou des dossier libs; le make devra se propager recursivement dans tous les sous dossiers ... mais le Makefile ne devra PAS contenir en dur la liste des dossier de recursivite ni la liste des fichiers sources a compiler: tout doit etre dynamique

    Tu trouvera de tels Makefiles dans http://doublehp.ath.cx/tmp/part1/(...) (le dossier sera detruit d ici 4j). Note que celui dans part1/lib ne contient aucune target, mais sais forwarder les requettes recursivement dans les sous libs ...

    ( avec arret de la compilation en cas d erreur )
    • [^] # Re: hmmm

      Posté par . Évalué à 5.

      A mon avis les cours de compilation c'est pas vraiment apprendre a se servir d'une chaine de compilation, mais plutot apprendre a concevoir un compilo
    • [^] # Re: hmmm

      Posté par . Évalué à 3.

      Comme le but de la finalite finale c'est d'etre didactique a tendance pedagogique avec un soupcon de main(s) dans le cambouis, je suppose que je vais repondre a cote de la plaque mais bon...

      Pour la partie sur les Makefiles, il y existe deja un outil qui fait ca (plutot bien je trouve) : Configuration Management Tool (CMT[1] pour les intimes).

      Il gere les dependances cycliques entre differents paquets d'un gros projet.
      On peut definir et appliquer des actions (genre une action doc, une action check pour les tests unitaires,...)

      On peut aussi lui passer n'importe quelle commande shell qui sera appliquee dans tous les paquets qui dependent d'un certain paquet.
      Et il aussi interface a un RCM (CVS pour l'instant mais SVN pointe le bout de son nez).

      Last but not least il est sous CeCILL et sa maintenance est garantie pour 20 ans (le temps que les experiences de physique des particules qui l'utilisent s'arretent de leur belle mort).
      Code avec vos sous (enfin ceux qui paient des impots ;)

      [1] CMT http://www.cmtsite.org(...)
    • [^] # Re: hmmm

      Posté par (page perso) . Évalué à 6.

      Un truc que je n'ai jamais utilisé pendant mes études, c'est un outil de gestion de conf.

      Je pense ce serait une bonne chose de passer quelques heures à expliquer aux élèves en info les bases de make, ant et cvs, puis d'exiger que tous les projets soient "rendu" sous forme d'un composant à checkahouter.
      • [^] # Re: hmmm

        Posté par (page perso) . Évalué à 2.

        tu as tout a fait raison, parce que les cours de C sous Borland, puis les projet sous Visual ... question comprehension de comment ca marche, on as fait mieux.

        Je migre peu a peu vers les outils automatiques; j utilise les Makefile depuis 1 an; je vais bientot passer aux ./configure ... et peut etre l an prochain a automake/autoconf :)

        Mais se former tout seul, c est trop la lutte.
        • [^] # Re: hmmm

          Posté par . Évalué à 3.

          sauf qu'a mon avis le monsieur il cherche un sujet de compilation (avec du lex et yacc quoi, pas gcc -c blabla).

          Je me souviens que mon sujet de compilation était assez interessant : on avait un compilateur pour un langage fictif genre java (en simplifié) et on devait lui ajouter des fonctionnalités manquantes. Par exemple le support des boucles for, la verification des bornes lors d'un accés à une table, les methodes virtuelles, ... On avait une liste d'amélioration possible et on devait en implementer 3 ou 4 au minimum. Ca permet de régler la quantité de travail demandé et de travailler sur un truc assez complexe, proche de la "réalité" (et pas simplement sur une évaluateur d'expressions arithmétiques). Le problème c'est que ça demande une masse de travail enorme pour le prof ou le chargé de demo et que le niveau des étudiants doit être assez élevé.

          Sinon, pour eviter de les deborder avec des langages comme le c ou le c++ (je sors d'une école où le simple fait de prononcer ces noms faisait flipper la moitié de la promo (j'étais dans l'autre moitié)), tu peux aller voir du coté d'Antlr : www.antlr.org , je l'utilise intensivement en ce moment et c'est du pur bonheur ! Il peut générer des parser en java, c# ou c++ (et peut être python aussi).
          • [^] # Re: hmmm

            Posté par (page perso) . Évalué à 1.

            j ai pas mal trippe en Prolog avant Noel ... mais tu as raison, lex doit etre sympa. J aurais bien aime avoir des cours comme ca ... c est clairement plus interessant que faire du C pendant 3 ans ou on te repete 6 fois le meme cours ( par cession de 6 mois), et ou les bons captent du premier coup, et les mauvais jamais.
        • [^] # Re: hmmm

          Posté par (page perso) . Évalué à 4.

          > je vais bientot passer aux ./configure ... et peut etre l an prochain a automake/autoconf

          Un conseil: apprends d'abord autoconf, et après, tu regarderas du coté des ./configure, tu auras une bonne surprise (hint: le ./configure est généré automatiquement par autoconf ;-)
          • [^] # Re: hmmm

            Posté par (page perso) . Évalué à 2.

            Un conseil: n'apprend jamais autoconf et automake. Tu perdras plus de temps a les utiliser qu'a developper du soft. A la place, apprends un truc super simple et qui a un vrai futur, comme scons ou qmake (pour les petits projets).
  • # interpreteur XSLT ?

    Posté par (page perso) . Évalué à 3.

    le plan pourrait etre :

    - qq manipulation autour de XML & XSLT
    - parseur iteratif
    - parseur recursif
    - modelisation selon DOM
    - recherche dans un document XML : XPath
    - chargement dynamique de composant du language

    sans entrer dans des problemes lourds sous jacents, cela peut etre un bon exercice surtout qu'il y a la libxml2 et la libxslt qui peuvent servir de modele.

    meme si cela à l'air compliqué, je ne parle aucunement de faire une version complete des specs XML/DOM/XPATH/XSLT mais juste d'un truc de demonstration pour exposer les bases.
    • [^] # Re: interpreteur XSLT ?

      Posté par . Évalué à 4.

      > il y a la libxml2 et la libxslt qui peuvent servir de modele.

      ou demander directement à Daniel Veillard si il a en tête un projet qui puisse cadrer dans les objectifs du cours. Comme ca en plus, c'est du code utile ! http://xmlsoft.org/(...)

      De facon général, je pense que les profs devraient participer plus au projets open source,
      "Bonjour, j'ai x élèves pendant x temps, voici leurs compétances, voici les contraintes du cours (contenu), est-ce que vous auriez un projet qui puisse coller ?"

      Bien encadré, il y a surement moyen de faire avancer le schmilblick.
  • # Une idée

    Posté par . Évalué à 2.

    > Est-ce que quelqu'un a une idée intéressante/ludique pour les étudiants plutôt que l'ultra classique: invention d'un language à 2 balles, écriture d'un compilateur pour ce langage.

    Optimiser GCC ? /o\

    « Je vous présente les moines Shaolin : ils recherchent la Tranquillité de l'Esprit et la Paix de l'Âme à travers le Meurtre à Main Nue »

    • [^] # Re: Une idée

      Posté par (page perso) . Évalué à 2.

      en 7-8 semaines, tu peux déjà demander: « regarder les sources de GCC et essayer de comprendre par quel bout peut bien se tenir cette chose étrange ».
  • # Tigrou?

    Posté par . Évalué à 5.

    Plutôt que d'inventer un (énième) langage bidon à but pédagogique, pourquoi ne pas en utiliser un qui existe et qui est fait pour ça: Tiger.

    Ce langage est décrit dans les livres de la série "Modern Compiler Implementation in <insert your favorite language here>". Pas besoin d'aller jusqu'au bout, leur faire participer aux grandes étapes de l'écriture du compilateur devrait déjà être très formateur.

    Autrement, un cours de compilation où l'on n'écrit pas (de près ou de loin) un compilateur ... j'ai du mal. Si c'est le temps qui te manque, tu peux te limiter aux phases de parsing, m'enfin bon.
  • # En espérant aider

    Posté par . Évalué à 2.

    J'me souviens quand j'étais en 2ième année de DEUG MIAS (Math Info et Applications aux Sciences), on avait eut comme projet d'écriture d'un compilateur LOGO en CAML. Perso j'avais beaucoup aimé.
    Les TPs étaient sous forme de notions a comprendre, et d' "écriture" du compilateurs (c'etait sous la forme de programme 'troué', on devait completer certaines parties).
    On avait commencé par la parti d'affichage (la tortu et les fonctions), puis ecriture du compilo (analyseur lexical puis syntaxique), puis mettre un "sens" et enfin "generation de code" et "machine virtuelle".
    Bon comme on avait pas un bon niveau, l'idée de faire un "gros" projet via un texte a trou était rigolo.
  • # Manipulation d'informations personnelles

    Posté par . Évalué à 4.

    Fais-leur écrire un petit langage qui manipule des informations personnelles genre todo, contact, rdv : c'est tout-de-suite plus motivant qu'un interpréteur / compilateur de langage informatique...

    Exemples (au hasard):

    - lister tous les rdv entre maintenant et demain:

    list all rdv starting between now and ( tomorrow morning )

    - lister toutes les tâches de priorité >=4

    list all tasks having priority >= 4
  • # Parrot ?

    Posté par . Évalué à 3.

    Tu peux peut-être utiliser la vm de perl6.

    Sois compiler un langage dessus, soit rajouter des "instructions assembleur", je pensais à des instructions SIMD, (genre 2 double ou 4 float). Ainsi certaine boucle de calcul perl pourrait en bénéficier.

    "La première sécurité est la liberté"

  • # marrant je viens d'en faire un

    Posté par . Évalué à 4.

    je viens justement de rendre un projet du meme type la semaine passé, et franchement pour un cours de compilation, à part écrire un compilateur, je ne vois pas mieux.
    Peut-être que pour toi qui est expérimenté cela semble barbant mais moi, n'ayant jamais écris de compilateur auparavant (et je suppose fortement que tes élèves sont dans le même ca) j'ai trouvé cela passionant.

    Bien sur tu pourrait faire écrire à tes étudiants un quelcquonque parser de document vers un autre format, mais un compilateur sonne beaucoup mieux dans l'oreille d'un étudiant et leur donnera l'impression d'avoir réalisé quelque chose d'important.


    Voila le projet que nous avons du réaliser : http://www.ulb.ac.be/di/ssd/ggeeraer/lg/enonceProjet1.ps(...)
    et la page des TP : http://www.ulb.ac.be/di/ssd/ggeeraer/lg/(...)
    note : ce n'est que sur le 1er projet, on utilise une grammaire LL a rendre LL1 et il faut ecrire les analyseurs syntaxique et lexical à la main. Le second portera sur une grammaire LR et l'utilisation de Lex et Yacc (Flex et Bison)
  • # Une alternative à IASL?

    Posté par . Évalué à 3.

    Plop, je sais pas si je vais dire une connerie immonde (ou pas) mais pour réparer une table DSDT sous linux il faut obligatoirement passer par le compilateur d'intel (IASL). Cela pourrait être intéressant d'avoir une alternative libre, non ?

    http://linuxfr.org/tips/263.html(...)
    http://www.intel.com/technology/iapc/acpi/downloads.htm(...)
    • [^] # Re: Une alternative à IASL?

      Posté par . Évalué à 2.

      Mais à mon avis, on a pas le droit d'obliger les étudiants à mettre leur code sous une licence libre. Enfin, je peux me tromper, mais je ne vois pas pourquoi un prof pourrait m'obliger à faire du libre si je n'en avais pas envie.

      Bon après certains accepteraient de la faire, je suppose.
      • [^] # Re: Une alternative à IASL?

        Posté par (page perso) . Évalué à 3.

        Les étudiants ne sont a priori pas propriétaires de leur code (en tout cas, c'est comme ça que ca se passe dans l'école ou j'ai enseigné). En pratique, ils en font bien ce qu'ils veulent, mais en théorie, non (en fait, on s'est servi de ça pour demander a un ancien de virer le projet qu'il avait mis sur sa page web et sur lequel nos étudiants allaient pomper ;-).
  • # Idee

    Posté par (page perso) . Évalué à 2.

    Va voir du cote des sujets de l' IFPC (International Functional Programming Contest), il me semlbe qu'il y avait quelques exercices interessant ou l'ecriture d'un compilateur etait un plus.

    Sinon, quitte a ecrire un langage, fait leur ecrire un langage qui leur apprend aussi des notions de qualite logicielle. Genre un langage prouvable, ou bien un langage a la eiffel, avec pre et post-assertion, ou bien un langage comme Ada, ou tous les intervalles de donnes sont parfaitement controlle.

    L'idee etant de trouver un langage avec des caracteristiques plus robuste que la moyenne de ceux qu'ils manipulent (C etant le pire).
  • # Parlons nature...

    Posté par . Évalué à 1.

    Un des TP qui m'avais le plus intéressé pendant mes cours de compilation avait été la génération de plantes.
    Ca ce base sur un langage dans le genre :

    depth 7 ;
    angle 20 ;

    X ;
    X --> F [ + X ] F [ - X ] + X ;
    F --> F F ;

    Et ça fait pousser un arbre, une fougère, de l'herbe ou tout autre végétaux magnifiques en 2D. En plus tu peux mettre en question bonus de passer l'appli en 3D, comme ça même tes meilleurs élèves aurons de quoi s'occuper ;)

    Sinon, tu peux jeter un oeil sur la fourmie de lancton, le jeu de la vie de Conway ou la simulation d'épidemie ou de feu.
    Un exemple pour les feux de foret:

    // 0 : rien
    // 1 : arbre non brule
    // 15 -> 2 : feu

    fireAround is (0,1)+(1,0)+(-1,0)+(0,-1)+(1,1)+(1,-1)+(-1,1)+(-1,-1).

    state (0,0)-1 when (0,0)>2.
    state 0 when (0,0)=2.

    state 15 when (0,0)=1 & fireAround>16.

    80 columns.
    80 lines.
    16 states.

    put ?2.
    put 0 from (79,0) to (79,79).
    put ? from (0,0) to (0,79).


    Si tu veux plus de renseignement, envoie moi un mail, j'ai les sources sous la main.
  • # port de gcc

    Posté par . Évalué à 2.

    ya pleins de cpu qui n'ont pas leur port de gcc..

    http://sourceforge.net/projects/tic54x-gcc(...)

    le port de gcc pour que l'on puisse développer tranquillement pour le neuros sous linux:
    http://open.neurosaudio.com/(...)

Suivre le flux des commentaires

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