Contenu | Rechercher | Menus

Annonce

Si vous avez des soucis pour rester connecté, déconnectez-vous puis reconnectez-vous depuis ce lien en cochant la case
Me connecter automatiquement lors de mes prochaines visites.

À propos de l'équipe du forum.

#1 Le 18/09/2009, à 19:55

Webanix

Exercice de création de son propre compilateur

Bonjour, je suis étudiant en informatique en 2e année et je connais le C++ et l'assembleur entre autres, mais n'ai pas encore suivi de cours de théorie des langages et de la compilation. J'aimerais (pour l'exercice, par curiosité), tenter de créer un petit compilateur simple.

Vu que ça doit être simple, j'aimerais créer mon propre langage, hyper basique, impératif, dans le genre de C mais en beaucoup plus simple évidemment smile . L'idéal serait de créer un compilo qui produit d'abord de l'assembleur (NASM de préférence), ça serait un bon exercice de style.

Ma seule inconnue reste le langage dans lequel je vais créer mon compilo wink Il faudrait, j'imagine, un langage permettant beaucoup de travailler avec des strings, vu que dans un premier temps je voudrais simplement écrire un compilo/programme qui recevant un fichier .x le convertit en un .asm en NASM. Il faudrait donc de puissantes fonctions pour l'analyse lexicale, syntaxique et sémantique du code. Je ne sais pas si C est approprié pour ça, mais je vais peut-être commencer par celui-là. A mon avis, il faudrait pouvoir utiliser quelque chose comme des regex...

Si vous avez une idée ou que mon exercice vous tente vous aussi => post big_smile

Hors ligne

#2 Le 19/09/2009, à 10:17

jofab

Re : Exercice de création de son propre compilateur

Bonjour,
c'est tres bon exercice (et tres interessant), je t'encourage wink
Bon visiblement tu connais les expressions rationnelles, c'est bien. As-tu déjà travailler sur une grammaire ? J'imagine que non si tu n as pas fait de th des lang... Connais tu les automates à états ?

donc ce qu'il te faut (pour faire simple) c'est
1 . definir ton langage et une grammaire qui va avec,
2. faire un analyseur lexical qui va parser le source en accord avec ta grammaire (si ta grammaire est bien choisi, c'est vraiment simple)
tu dois, pendant l'analyse, representer ce que tu recuperes du fichier source dans une representation interne (le mieux etant un arbre).
3. generer le code en parcourant l'arbre.

pour definir ta grammaire, tu dois dire ce qu'est un programme :
un programme c'est une collection d'instructions
ensuite tu dois dire ce qu'une instruction :
instruction -> boucle | if | ...
ensuite tu dois definir chacune des instructions :
if -> 'if' condition 'then' instruction
...

apres globalement, pour traduire ca en programme, si tu as bien pense ta grammaire, ca te donne une fonction par regle +/-.
mon exemple est plutot bof, il faut vraiment ce pencher sur cette partie, car c'est la plus importante... Si elle est mal pensee tu va galerer, si elle est bien pensee tu n'auras jamais à revenir en arriere dans l'analyse du flux du fichier source.

pour ce qui est de certaines regles comme la definition d'un identificateur ou d'un nombre, utilise plutot des automates à etats (qui reconnaissent une regex)
par exemple un identificateur c'est [a-zA-Z_][a-zA-Z0-9_]*

voila quelques pistes pour debuter...
Bon courage...
ps : pour ce qui est du langage, tu peux faire en ce que tu veux et le c est bien. Sinon il y a lex et yacc (bison et flex) qui sont fait pour ca. Tu donnes une grammaire et les operations à faire et il fait tout pour toi mais c'est moins interessant car tu ne vois pas tout les mecanismes. C'est clair que si tu veux apprendre, il est pref. de faire les choses soit meme...

Hors ligne

#3 Le 19/09/2009, à 11:32

Webanix

Re : Exercice de création de son propre compilateur

Merci pour ta réponse

J'ai commencé dès hier soir à définir mon langage, mais de manière beaucoup moins poussée que ce que tu décris. En gros, voici un exemple de programme écrit dans ce langage :

1   INTEGER note
2   ASSIGN 14 TO note
3   CHAR mention 
4   IF note UNDER 12 GOTO 8
5   IF note UNDER 14 GOTO 10
6   IF note UNDER 16 GOTO 12
7   GOTO 14
8   ASSIGN D TO mention
9   GOTO 15
10 ASSIGN C TO mention
11 GOTO 15
12 ASSIGN B TO mention
13 GOTO 15
14 ASSIGN A TO mention
15 PRINT mention

C'est juste un premier exercice facile où je n'aurai qu'à changer chaque instruction par une instruction assembleur. L'analyse lexicale est très facile : on sait découper très facilement le programme en instructions, puis chaque instruction en plusieurs mots. A partir du premier mot, on reconnait le type de l'instruction et on appelle la fonction équivalente qui se charge d'analyser le reste de la ligne pour trouver les paramètres de l'instruction.
Je pense qu'à ce stade une seule passe est nécessaire. Il faut toutefois gérer une ou deux erreurs de compilation possible, donc c'est un bon début.

Après, je passerai à quelque chose de plus formel comme tu le suggères, avec une structure en arbre. J'ai notamment lu un peu de la norme C++ et je comprends comment fonctionnerait la spécification du langage.
Par contre, je ne sais pas comment utiliser des expressions rationnelles en C. Je ne sais pas ce que sont les automates à état, mais je vais me renseigner smile

Hors ligne

#4 Le 19/09/2009, à 12:09

Watchwolf

Re : Exercice de création de son propre compilateur

regarde des tutoriaux sur lex&yacc (ou flex&bison) c'est exactement ce qu'il te faut. ce sont des outils permettant d'écrire des compilateurs en utilisant une grammaire.

Hors ligne

#5 Le 19/09/2009, à 13:16

jofab

Re : Exercice de création de son propre compilateur

Webanix a écrit :

Par contre, je ne sais pas comment utiliser des expressions rationnelles en C. Je ne sais pas ce que sont les automates à état, mais je vais me renseigner smile

pour info (pour utiliser les regex en c) : http://nicolasj.developpez.com/articles/regex/
toutefois pour ton probleme, il ne faut pas utiliser ca. Il faut que tu crees des automates pour les expressions que tu veux reconnaitre sur ton flux de characteres (identificateurs, nombres...).

Watchwolf a écrit :

regarde des tutoriaux sur lex&yacc (ou flex&bison) c'est exactement ce qu'il te faut. ce sont des outils permettant d'écrire des compilateurs en utilisant une grammaire.

Comme je l'ai dit dans mon post, ca dépend si son pb est d'avoir un compilo pour son langage ou si son but est d'apprendre comment faire et comment fonctionne un compilo. Dans le premier cas, ok pour lex et yacc dans le second cas, non (en tout cas pas tout de suite)

Hors ligne

#6 Le 19/09/2009, à 14:36

Watchwolf

Re : Exercice de création de son propre compilateur

jofab a écrit :
Webanix a écrit :

Par contre, je ne sais pas comment utiliser des expressions rationnelles en C. Je ne sais pas ce que sont les automates à état, mais je vais me renseigner smile

pour info (pour utiliser les regex en c) : http://nicolasj.developpez.com/articles/regex/
toutefois pour ton probleme, il ne faut pas utiliser ca. Il faut que tu crees des automates pour les expressions que tu veux reconnaitre sur ton flux de characteres (identificateurs, nombres...).

Watchwolf a écrit :

regarde des tutoriaux sur lex&yacc (ou flex&bison) c'est exactement ce qu'il te faut. ce sont des outils permettant d'écrire des compilateurs en utilisant une grammaire.

Comme je l'ai dit dans mon post, ca dépend si son pb est d'avoir un compilo pour son langage ou si son but est d'apprendre comment faire et comment fonctionne un compilo. Dans le premier cas, ok pour lex et yacc dans le second cas, non (en tout cas pas tout de suite)

la première chose qu'il doit faire c'est apprendre à écrire une grammaire comem tu l'as dit. Or Lex&Yacc ermet de facilement tester une grammaire et les tutos donnent souvent quelques exemples de grammaire simples. Apprend à écrire des grammaires juste avec internet c'est plutot difficile alors une approche pratique avec lex&yacc est une bonne idée je pense.

Après on peut écrire un compilo sans utiliser de grammaires mais ce n'est faisable que pour des langages simples.

Dernière modification par Watchwolf (Le 19/09/2009, à 14:36)

Hors ligne

#7 Le 24/10/2009, à 14:05

mariach

Re : Exercice de création de son propre compilateur

trés interéssant bah chapeau
moi aussi chui en 2éme année informatique et j'étudie théorie des langages
il me parait que c bien compliquée mais je vais bien essayer
bonne continuation les gars

Hors ligne

#8 Le 24/10/2009, à 17:01

swilmet

Re : Exercice de création de son propre compilateur

Dans GNU Linux Magazine France il y avait toute une série d'articles d'un gars qui créait un compilateur en OCaml.
Sinon pour bien comprendre comment fonctionne un compilateur, le mieux c'est d'acheter un bon bouquin.

Hors ligne

#9 Le 24/10/2009, à 17:17

helly

Re : Exercice de création de son propre compilateur

très interressant mais STP essaye de faire honneur a notre langue et faire un langage en francais, c'ets tellement rare ...je sais même pas si ca existe ...


Archlinux-wmii-dwb.
Un problème résolu ? Faites le savoir en mettant [résolu] à côté du titre de votre topic.
Un problème non résolu ? Faites le savoir en insultant ceux qui cherchent à vous aider.
Un site bleu super remasterised©, un wiki cherchant des volontaires pour traduire un site.

Hors ligne

#10 Le 25/10/2009, à 12:34

nicolas66

Re : Exercice de création de son propre compilateur

Bien sûr. On peut notamment citer Linotte, Logo et LSE.


"The computer was born to solve problems that did not exist before." (B. Gates)

Hors ligne

#11 Le 25/10/2009, à 13:33

helly

Re : Exercice de création de son propre compilateur

hooo j'en apprend dis donc ^^


Archlinux-wmii-dwb.
Un problème résolu ? Faites le savoir en mettant [résolu] à côté du titre de votre topic.
Un problème non résolu ? Faites le savoir en insultant ceux qui cherchent à vous aider.
Un site bleu super remasterised©, un wiki cherchant des volontaires pour traduire un site.

Hors ligne

#12 Le 25/10/2009, à 18:15

swilmet

Re : Exercice de création de son propre compilateur

Le pseudo-code aussi lol

Hors ligne

#13 Le 26/10/2009, à 07:37

Le Farfadet Spatial

Re : Exercice de création de son propre compilateur

Salut à tous !

   Un excellent ouvrage sur les compilateurs :

      Compilateurs
      Dick GRUNE, Henri E. BAL, Ceriel J. H. Jacobs et Koen G. LANGENDOEN
      Dunod

   À bientôt.

                                                                                                                                    Le Farfadet Spatial

Hors ligne

#14 Le 26/10/2009, à 08:48

rniamo

Re : Exercice de création de son propre compilateur

soit tu utilises flex/yacc et dérivés soit tu te fais tout : automates etc


< Quelques un des mes programmes  | Cuisine Facile (pour les gourmands) | Fast MVC for PHP >
        \   ^__^
         \  (o o)\_______
            (___)\            )\

Hors ligne

#15 Le 26/10/2009, à 13:28

helly

Re : Exercice de création de son propre compilateur

swilmet a écrit :

Le pseudo-code aussi lol

même pô vrai,jsuis Made in Japan, même si je fais mes études en france , alors moi le pseudo code, c'est du jap !! big_smile


Archlinux-wmii-dwb.
Un problème résolu ? Faites le savoir en mettant [résolu] à côté du titre de votre topic.
Un problème non résolu ? Faites le savoir en insultant ceux qui cherchent à vous aider.
Un site bleu super remasterised©, un wiki cherchant des volontaires pour traduire un site.

Hors ligne

#16 Le 26/10/2009, à 21:24

Blabla404

Re : Exercice de création de son propre compilateur

Moi je conseillerais plutot le modern compiler implementation in {C, java, ML} c'est ce que j'avais utilisé en L3 et il y a dedans vraiment tout ce qu'il faut pour faire un langague non trivial avec la possibilité de faire des optimisations pas mal.
Apres tout depend de ce que tu veux faire mais la partie lexer/parser c'est à mon avis plutot chiant et ca n'apprend pas grand chose sur le fonctionnement d'un compilo donc autant utiliser lex/yacc.
Et si tu veux un truc qui soit juste fonctionnel en utilisant llvm tu peux ecrire un compilo pour un nouveau language super rapidement sans t'occuper des toutes les optims. Le code compilé étant souvent très bon. Pour prototyper un nouveau language je pense que c'est le top surtout qu'il te laisse pas mal de liberté si tu veux ajouter des optims maisons.

Hors ligne

#17 Le 27/10/2009, à 10:35

jofab

Re : Exercice de création de son propre compilateur

redoxx a écrit :

Moi je conseillerais plutot le modern compiler implementation in {C, java, ML}
Apres tout depend de ce que tu veux faire mais la partie lexer/parser c'est à mon avis plutot chiant et ca n'apprend pas grand chose sur le fonctionnement d'un compilo donc autant utiliser lex/yacc.
.

Un compilo c'est une sorte de traducteur : classiquement il y a une phase d'analyse lexicale (découpage du text en entité lexiale(lexem ou token)) suivie d'une analyse syntaxique (ou l'on génère un arbre pour representer le text que l'on analyse (parsing)). En suite il y a une phase d'analyse sémentique (vérification des types...) et enfin viens la génération du code et son optimisation.
Conclusion, dire que l'analyse lexicale et le parsing n'apprend rien sur le fonctionnement d'un compilo c'est oculter une bonne partie du travail du compilo... hmm:/:/
En revanche, je suis d'accord, modern compiler implementation in {C, java, ML} est à cote de moi et il est pas mal...

Hors ligne

#18 Le 27/10/2009, à 10:41

jofab

Re : Exercice de création de son propre compilateur

En livre en plus de ce qui est cite :
Parsing techniques a pratical guide de Dick Grune et Ceriel Jacobs qui a l'avantage d'etre librement telechargeable (la premiere edition)

Compilers
Principes, techniques et outils (Le livre du dragon)
Aho, Lamn, Sethi et Ullman

Hors ligne

#19 Le 27/10/2009, à 19:47

Link31

Re : Exercice de création de son propre compilateur

jofab a écrit :

Conclusion, dire que l'analyse lexicale et le parsing n'apprend rien sur le fonctionnement d'un compilo c'est oculter une bonne partie du travail du compilo... hmm:/:/

C'est le fonctionnement interne du parsing qui est particulièrement difficile et prise de tête à réaliser soi-même et qui ne sert pas à grand chose pour comprendre le fonctionnement général d'un compilateur.

Ça n'empêche pas d'écrire soi-même des règles lexicales et grammaticales (puis de les passer à un générateur de parser comme lex/yacc ou boost.spirit). C'est ce dernier point qui est le plus intéressant à étudier. Mais écrire un parser à la main c'est vraiment chercher les problèmes, pour un résultat pas forcément stable et optimisé...

Hors ligne

#20 Le 28/10/2009, à 09:43

jofab

Re : Exercice de création de son propre compilateur

Link31 a écrit :

C'est le fonctionnement interne du parsing qui est particulièrement difficile et prise de tête à réaliser soi-même et qui ne sert pas à grand chose pour comprendre le fonctionnement général d'un compilateur.

Ça n'empêche pas d'écrire soi-même des règles lexicales et grammaticales (puis de les passer à un générateur de parser comme lex/yacc ou boost.spirit). C'est ce dernier point qui est le plus intéressant à étudier. Mais écrire un parser à la main c'est vraiment chercher les problèmes, pour un résultat pas forcément stable et optimisé...

Oui et non : Ecrire une grammaire n'est pas si facile que ca mais bon, passons.
Ensuite le choix d'ecrire le parseur ou de le générer par des outils se fait à un autre niveau. Si la grammaire est LL (resp RL), le parseur s'ecrit à la main sans probleme et c'est meme plutot amusant. Si la grammaire est LR (resp RR), la oui il faut utiliser un outil...
Et puis meme si on utililse un outil pour générer le parser il faut comprendre comment un parseur LR fonctionne sinon 1/ C'est toujours dommage de ne pas apprendre qqc qui est à notre porté 2/ On risque de rater des choses

En dehors du pb du compilo, j'ai du écrire il y quelques années une interface pour saisir des expressions et des requettes. Bien, pour rendre l'interface plus attractive et performante, j'ai fait un systeme de coloration syntaxique et la j'ai du ecrire moi meme le parseur : j'etais bien content de savoir le faire et j'ai mis bcp moins de temps que si j'avais du ressortir lex/yacc...

Hors ligne