Parser - Page 1

Je suis en train de me lancer dans un compilateur on-calc (j'ai (re-?)découvert un algo d'analyse d'expression qui permettrait de réduire les coûts en place mémoire et en puissance processeur).

L'algo prend les tokens du fichier source les uns après les autres, et construit à la volée un arbre syntaxique.

Je m'explique : supposons que l'expression suivante soit à analyser : 2+3*4

L'arbre construit sera (je mets les parenthèses pour représenter les branches ) :
Cet algo devrait être plus rapide (pour les expressions uniquement) que les approches traditionnelles shift&reduce ou top-down.
1) (2) - une valeur simple
2) ((2) + (?)) - on ajoute l'opérateur -> l'expression est incomplète
3) ((2) + (3)) - on complète l'expression avec la valeur suivante
4) ((2) + ((3) * (?))) - on ajoute l'opérateur * : en parcourant l'arbre, on se rend compte que le * a la priorité sur le +. L'expression suivante serait par exemple fausse (((2) + (3)) * (?)).
5) ((2) + ((3) * (4))) - on complète l'expression

Est-ce que je suis sur une bonne voie (je m'adresse aux personnes qui ont déjà implémenté un compilo; Nitro ?) ?

Ces expérimentations devraient bientôt déboucher sur un compilo on-calc, interfacé avec Genlib et optimisé vitesse de compilation.

Tu fais un compilo C ???
Ben bon courage !!!
dsl, je ne peux pas t'aider, par contre...
[edit]Edité par jackiechan91 le 03-04-2002 à 18:29:50[/edit]

Si tu pouvais faire un compilo Caml, ca serait sympa

bon courage ... certains s'y sont déja frotté ...

Je te conseil de reflechir avant de commencer, parce que ton idée là, ce n'est qu'un détail par rapport au vrai travail qu'il y a derriere...
Voila en gros comment fonctionne CC (basé sur C68III avec un backend réécrit pour etre compatible avec AS):
D'abord le compilateur parse et tokenize les lignes de codes et stock le résultat dans un arbre, avec quelques optimisations triviales. Ensuite la phase d'allocation des registres (il y a des théories compliquées rien que sur cette phase, notamment la méthode par coloration de graphe), puis l'arbre est passé au "backend", c'est-a-dire la partie du compilateur qui va générer les instructions asm. Le backend va transformer chaque noeud de l'arbre en blocks d'instructions (forme tokenisée d'assembleur). Ces blocks, qui sont chainés, sont optimisés par l'optimisateur "peephole", qui est en fait une base de données de bouts de codes génériques et leurs optimisations possibles, et enfin la liste d'instruction est écrite dans le fichier de sortie (génération de modes d'adressages compatibles, etc...), pret à etre assemblé.

Bien sur on peut faire plus simple, mais moins bien. Et aussi un facteur important c'est la robustesse du code generé.. si il y a des bugs bizarres personne ne l'utilisera, et c'est assez compliqué de debugger un compilateur j'en sais quelque chose

Azur est un peu plus simple que ce que tu décris Nitro Voila pourquoi il optimise mal (presque pas ).

MadKeyboard : heu je veux pas te décourager, mais bon bon bon bon bon bon bon bon courage .... Je pensais que ça serait (relativement bien sûr) simple quand j'ai débuté Azur... Et plus j'avance plus je me rend compte que j'aurais besoin de temps pour arriver au bout... Je suis dessus depuis 1 an et demi, mes 4500 lignes de code (que ça en 1 ans 1/2 ? ben oui quand on part avec aucune connaissance et qu'en plus on passe son temps à vouloir un truc complètement débogué, on avance lentement... mais sûrement ) ce n'est pas encore la moitié de ce qu'il va me falloir probablement !

Je vais faire un compilateur simple et rapide (en vitesse de compilation), même si le code généré est dégueu.

L'argument : ça va être difficile de concurrencer les "géants" comme TIGCC dont les sources font plusieurs mio de lignes de code. Les programmeurs qui veulent un exécutable optimisé peuvent faire appel à un compilateur PC. Un compilo on-calc est un outil de prototypage essentiellement; on ne lui en voudra pas si le code généré est un peu lourd.

Mon idée est d'axer le compilateur sur la simplicité (= programme plus petit et moins de bugs), et la rapidité d'exécution.

Architecture :

- première étape : stockage des caractères du flux d'entrée en attendant de dégager un token complet, et passage de ce token au deuxième niveau
- deuxième étape : accepte les tokens; 4 états possibles : essaie de compléter une fonction, un bloc, une instruction ou une expression (pile)
-> dès qu'une expression est complétée, optimisations triviales sur l'arbre (constantes par ex.) et émission du code
- troisième niveau : émission du code pour les expressions, instructions, blocs et fonctions (y.c. épilogue, prologue) et construction/résolution des tables d'offsets pour les instructions de contrôle

Les besoins en mémoire RAM devraient être faibles : je compte environ 8 ko au maximum.

Le compilateur ne devrait pas être énorme non plus ; je vais essayer de rester en dessous des 24 ko.

Le langage proposé sera propriétaire; mais le compilateur devrait fonctionner également en mode traduction ANSI C.

La première étape de ce projet est d'obtenir un compilateur pour un langage fonctionnant uniquement avec le type "word" (une sorte de sous-BASIC).

Enfin, on verra...

J'ai pigé !!! Tu nous es en train de nous inventer exactement un compilo Azur

J'avais exactement les mêmes objectifs que toi. J'ai abandonné le langage Azur et porté mon compilo pour le C parceque tout le monde me disait que ça tomberait dans l'oubli étant donné qu'il leur faudrait apprendre un nouvreau langage, pas portable

[edit]Edité par Thibaut le 06-04-2002 à 21:49:05[/edit]

dommage pour Azur ....

moi je le conserve ;p

Thibaut > Je le fais pour le fun et pour un projet de trimestre, donc pour le compilo C, j'ai pas trop le temps...
De toute manière, je pense devoir réviser toutes mes idées d'ici à un mois (le temps de programmer sérieusement dessus)... je vais tout faire pour éviter que ce prog. marche sur les plate-bandes d'un compilo C. Le langage sera clairement inspiré de C, exactement comme l'ont fait avant moi les développeurs de Java/Javascript et j'en passe :-).

Le topic passe dans la rubrique "projets".