Les membres ayant 30 points peuvent parler sur les canaux annonces, projets et hs du chat.

Forum Casio - Projets de programmation


Index du Forum » Projets de programmation » Compylateur
Shadow15510 Hors ligne Administrateur Points: 4981 Défis: 16 Message

Compylateur

Posté le 08/05/2020 14:00

Bonjour à tous !

Il y a quelques temps j'ai fait un 'compilateur' qui permet d'exécuter un algorithme en langage naturel en le 'traduisant' en Python. Le code est atroce et repose sur un remplacement entre les commandes en langage naturel et les commandes en Python (à coup de dictionnaires et de tests conditionnels )… J'aimerais faire de ce projet un 'vrai' compilateur (on reste sur du Python ). Et j'ai quelques questions :

- La phase d'analyse lexicale repose pour l'instant sur une recherche et un replacement, avec un dictionnaire qui contient en clés les commandes en langage naturel, et en items, les commandes correspondantes en Python… Je me doute que ce n'est pas pertinent… En fait l'analyse lexicale est mélangée à la phase d'analyse syntaxique.

- Comment faire pour basculer du langage naturel au Python ? Faut-il forcément passer par un hard code, ou est-ce que d'autre technique plus esthétiques existent ?

- L'analyse syntaxique est un bête replace basé sur un dico… Du coup ça revient à la question précédente : comment éviter le hard code ?

- La phase sémantique… Je ne suis pas sûr d'avoir bien compris toutes les subtilités… Dans mon cas, après le remplacement bête et méchant, la syntaxe Python n'est pas bonne, du coup je passe à travers différents tests conditionnels pour avoir un 'vrai' script fonctionnel… Encore une fois le hard code à coup de if me plaît moyen…

- En derniers je refait un passage sur mon code généré et j'ajoute les alinéas. Est-ce que je devrais les gérer plus tôt (je pense à la phase d'analyse syntaxique… mais le placement des alinéas dépend du contexte du code, et sur une ligne donnée je vois pas trop comment faire…

Merci d'avance !


1, 2, 3, 4 ··· 10 ··· 17, 18, 19 Suivante
Lephenixnoir Hors ligne Administrateur Points: 20809 Défis: 143 Message

Citer : Posté le 08/05/2020 14:12 | #


- La phase d'analyse lexicale repose pour l'instant sur une recherche et un replacement, avec un dictionnaire qui contient en clés les commandes en langage naturel, et en items, les commandes correspondantes en Python… Je me doute que ce n'est pas pertinent… En fait l'analyse lexicale est mélangée à la phase d'analyse syntaxique.

Ça ne pourrait suffire que si la grammaire du langage naturel était celle de Python, sauf que... non ! Il faut interpréter un minimum le langage naturel, sujets/verbes/compléments, prépositions, la structure de la phrase, et tout ça.

- La phase sémantique… Je ne suis pas sûr d'avoir bien compris toutes les subtilités…

Aha, tu as fait de la recherche ! Après l'analyse lexicale et syntaxique, tu te retrouves avec des choses comme des phrases "sujet-verbe-complément". La phase d'analyse sémantique c'est le moment où tu vas chercher que est le sens du verbe et donc quelle action il faut effectuer (par exemple).

- En derniers je refait un passage sur mon code généré et j'ajoute les alinéas. Est-ce que je devrais les gérer plus tôt (je pense à la phase d'analyse syntaxique… mais le placement des alinéas dépend du contexte du code, et sur une ligne donnée je vois pas trop comment faire…

La génération de code est tout à la fin, touche pas au texte avant d'avoir tout fini.
Shadow15510 Hors ligne Administrateur Points: 4981 Défis: 16 Message

Citer : Posté le 08/05/2020 14:20 | #


Il faut interpréter un minimum le langage naturel


C'est le problème… Je ne vois pas comment me passer de mon dictionnaire… ^^' Si toute mes commandes ne sont pas inscrites en dur quelques part, comment je peux savoir que est supérieur à ça se transforme en : > ? Avec un dictionnaire c'est facile… mais si c'est pas hard codé… ?

J'ai essayé de me documenter un peu sur la chaîne de compilation (merci Wikipédia \o/ )

La génération de code est tout à la fin


Là je crois qu'on touche un problème : le code est généré au fur est à mesure >_<'… Pour l'instant le """compilateur""" ne génère pas vraiment de code : il retouche juste l'algorithme langage naturel (en remplaçant certaines commandes par d'autre, etc) de manière à pour l'exécuter en Python après…
"Ce n'est pas parce que les chose sont dures que nous ne les faisons pas, c'est parce que nous ne les faisons pas qu'elles sont dures." Sénèque

Lephenixnoir Hors ligne Administrateur Points: 20809 Défis: 143 Message

Citer : Posté le 08/05/2020 14:22 | #


Tu dois bien sûr avoir quelque part la sémantique du langage naturel... ça peut être un dictionnaire mais ça ne suffira pas car il y a plein de façon d'écrire "supérieur" quand tu comptes les accords (féminin/pluriel) et les synonymes. Il faut abstraire un peu. Et oui, c'est difficile. En fait, c'est tout le coeur du problème !

Là je crois qu'on touche un problème : le code est généré au fur est à mesure >_<'… Pour l'instant le """compilateur""" ne génère pas vraiment de code : il retouche juste l'algorithme langage naturel (en remplaçant certaines commandes par d'autre, etc) de manière à pour l'exécuter en Python après…

Oui, c'est ce que tu expliquais. Il faut que tu décolles très vite de ça parce que sinon tu seras incapable d'altérer la structure syntaxique du programme. Tu dois parser ton programme en un truc abstrait et ensuite générer du Python à partir de zéro.

Ajouté le 08/05/2020 à 14:24 :
Pour la partie un peu technique, vois par exemple ça et vite fait ça.
Shadow15510 Hors ligne Administrateur Points: 4981 Défis: 16 Message

Citer : Posté le 08/05/2020 14:25 | #


Donc je dois inventer une sorte de truc abstrait entre le langage naturel et le python ?

Okay, je regarde ça ! Merci
"Ce n'est pas parce que les chose sont dures que nous ne les faisons pas, c'est parce que nous ne les faisons pas qu'elles sont dures." Sénèque

Lephenixnoir Hors ligne Administrateur Points: 20809 Défis: 143 Message

Citer : Posté le 08/05/2020 14:26 | #


Essaie déjà d'inventer une forme abstraite pour le langage naturel seulement et tu verras après comment tu vas vers le Python.
Shadow15510 Hors ligne Administrateur Points: 4981 Défis: 16 Message

Citer : Posté le 08/05/2020 14:35 | #


Donc pour l'instant : traduire le langage naturel vers une forme abstaite…

Il faut nécessairement passer par des catégories… (c'est pas très rigoureux dit comme ça ) En gros faut que j'arrive à déterminer quel mot est une commande (pour, si, tant que), quel mot est une variable, et enfin les autres 'truc' (par exemple est supérieur à, mais c'est l'idée du 'supérieur à' qu'il faut saisir et non le mot lui-même… ?). La dernière catégorie est bordélique… faudra que je trie les opérateurs de relations (<, > =, !=…) de l'affectation

Pour identifier les mots, et donc les classifier, il faut donc se baser sur la logique du programme : si j'ai une commande conditionnelle, j'ai forcément une condition après, c'est à dire une ou deux variable reliées par un opérateur. En plus ces conditions peuvent être séparée par des opérateurs logiques…
"Ce n'est pas parce que les chose sont dures que nous ne les faisons pas, c'est parce que nous ne les faisons pas qu'elles sont dures." Sénèque

Lephenixnoir Hors ligne Administrateur Points: 20809 Défis: 143 Message

Citer : Posté le 08/05/2020 14:39 | #


Dans un langage habituel, tu as des mots-clés qui introduisent de la structure. En français aussi. Ta phrase est découpée en propositions indiquées par différents délimiteurs comme des virgules, ou des temps (un peu compliqué, peut-être à gérer plus tard !), avec des lieurs comme des prépositions...

Par exemple dans "Si x est supérieur à 4, quitter le programme" tu as deux propositions (une conditionnelle et une infinitive) ; la première contient un sujet "x", un verbe "est", un adjectif "supérieur" et un COI je suppose ("à 4"), et tu dois analyser tout ça et construire une forme abstraite.

Ensuite tu sais que l'adjectif supérieur à une sémantique de comparaison, et donc tu sais que "est(x, supérieur, 4)" peut se traduire vers "x > 4", etc etc.
Shadow15510 Hors ligne Administrateur Points: 4981 Défis: 16 Message

Citer : Posté le 08/05/2020 14:47 | #


Dans l'idée, je pense suivre la chaîne à la lettre, pour éviter de me perdre

Du coup dans l'analyse lexicale, je sépare les mots… Donc a priori un split sur les espaces suffit…

Ensuite l'analyse syntaxique permet de 'classifier' le mot isolé par l'analyse lexicale, et de lui attribuer une sémantique… Mais c'est là que le bât blesse… pour pouvoir trouver la sémantique, il faut forcément que ce soit mis quelque part… J'arrive pas à concevoir comment on peut trouver cette sémantique…
"Ce n'est pas parce que les chose sont dures que nous ne les faisons pas, c'est parce que nous ne les faisons pas qu'elles sont dures." Sénèque

Lephenixnoir Hors ligne Administrateur Points: 20809 Défis: 143 Message

Citer : Posté le 08/05/2020 14:51 | #


Du coup dans l'analyse lexicale, je sépare les mots… Donc a priori un split sur les espaces suffit…

Presque mais quand même pas parce que la ponctuation est aussi à isoler et à prendre en compte !

Ensuite l'analyse syntaxique permet de 'classifier' le mot isolé par l'analyse lexicale, et de lui attribuer une sémantique… Mais c'est là que le bât blesse… pour pouvoir trouver la sémantique, il faut forcément que ce soit mis quelque part… J'arrive pas à concevoir comment on peut trouver cette sémantique…

Tu dois pas la trouver, tu dois la coder dans ton programme. Mais tu dois la coder intelligemment si tu veux pas que ton programme finisse par contenir les définitions abstraites de la moitié des mots de la langue française...
Shadow15510 Hors ligne Administrateur Points: 4981 Défis: 16 Message

Citer : Posté le 08/05/2020 14:55 | #


Okay… Je sens que ça va être dur et long xDD Je pense voir ça un peu plus tard

Je pense commencer par faire des petits programmes… Je pensais à un truc comme ça : on donne une phrase, et le programme doit donner le sujet ? Au début, avec des phrases simples, et finir avec des trucs plus complexes…
"Ce n'est pas parce que les chose sont dures que nous ne les faisons pas, c'est parce que nous ne les faisons pas qu'elles sont dures." Sénèque

Lephenixnoir Hors ligne Administrateur Points: 20809 Défis: 143 Message

Citer : Posté le 08/05/2020 15:00 | #


Voilà, donc ce que tu décris c'est l'analyseur syntaxique (le parser). Donne tout d'un coup : sujet/verbe/COD/etc. La première étape c'est d'avoir une grammaire du genre

phrase := proposition POINT
proposition := sujet verbe complément?
sujet := MOT
verbe := MOT
complément := MOT

puis tu peux raffiner ensuite pour n'accepter en verbe que les mots qui sont réellement des verbes, etc etc.
Shadow15510 Hors ligne Administrateur Points: 4981 Défis: 16 Message

Citer : Posté le 08/05/2020 15:11 | #


Du coup le sujet est toujours en premier… ?

Ici, tu déclares en quelques sorte les sémantiques… ? Dans le projet final j'aurais donc un truc un peu comme ça :

commandes := MOT
opérateur de relation := SYMBOLE
opérateur logique := MOT
variable := MOT
condition := commande variable opérateur de relation variable


Mais toutes ces données, on les stocke comment, dans mon cas c'est du Python, du coup je fais un dico ?
Si reprends ton exemple de grammaire j'ai un truc comme ça :

grammaire = {"phrase":"proposition+POINT", "proposition":"sujet+verbe+complément", "sujet":"MOT"}


Je suis en train de lire ça : https://fr.wikipedia.org/wiki/Analyse_lexicale
"Ce n'est pas parce que les chose sont dures que nous ne les faisons pas, c'est parce que nous ne les faisons pas qu'elles sont dures." Sénèque

Lephenixnoir Hors ligne Administrateur Points: 20809 Défis: 143 Message

Citer : Posté le 08/05/2020 15:29 | #


Dans le projet final j'aurais donc un truc un peu comme ça

Non, ça c'est une grammaire de langage de programmation. C'est pas du tout du langage naturel !

Mais toutes ces données, on les stocke comment, dans mon cas c'est du Python, du coup je fais un dico ?

Non tu utilises un générateur de parser où la syntaxe sera décrite un peu comme j'ai écrit avec les := et lui se démerde pour te générer un arbre de syntaxe.

Ce dont on parle là c'est l'analyse syntaxique, pas lexicale.
Shadow15510 Hors ligne Administrateur Points: 4981 Défis: 16 Message

Citer : Posté le 08/05/2020 15:31 | #


Un générateur de parser… ? C'est pas à moi de le faire ?
"Ce n'est pas parce que les chose sont dures que nous ne les faisons pas, c'est parce que nous ne les faisons pas qu'elles sont dures." Sénèque

Lephenixnoir Hors ligne Administrateur Points: 20809 Défis: 143 Message

Citer : Posté le 08/05/2020 15:35 | #


Générer des parsers à partir de grammaires est une tâche très courante dès qu'on joue avec des langages. Ça a été automatisé il y a de longues années. Tu balances la grammaire, il te sort un parser, puis tu lui balances les tokens qui sortent du lexer et t'obtiens la phrase structurée.
Disperseur Hors ligne Membre Points: 1784 Défis: 1 Message

Citer : Posté le 08/05/2020 16:22 | #


Je m'incruste un peu mais ce sujet m'intéresse énormément
Quelle forme prends un parser ? C'est un fichier intermédiaire entre le programme et l’exécution ?

@Shadow: Après pour simplifier un peu tu peux imposer une sorte de "syntaxe" à l'utilisateur. Par exemple certains mots qui sont invariables et utiles dans la description d'une tache tels que "si", "alors" et "sinon"..
Mes meilleurs jeux
N'hésitez pas, notez !

Jeux BasicCasio / CBasicCasio:
-World Tank War II
-Apollo 11
-GeoGraph ! Élu Jeu du Mois de Mars 2019 !
Jeux C:
-Planétarium 2 ! Chef d'Oeuvre !


√(2+2-2+2-2+2+2-2-2-2) = 0
Shadow15510 Hors ligne Administrateur Points: 4981 Défis: 16 Message

Citer : Posté le 08/05/2020 16:33 | #


Ouaip, bien sûr
C'est déjà plus ou moins le cas, ma première version ne gérant pas toute la langue française

Ajouté le 10/05/2020 à 17:31 :
Hey !

@Disperseur : Content de voir que tu t'intéresse au projet ! Désolé j'avais zappé le haut de ton message… Au niveau de ta question sur le parser je n'ai pas la réponse faisant mes premiers pas dans ce monde aussi ! J'essayerai de penser à faire un dépôt git pour le projet.

Bon, j'ai pris le partit de faire un lexer moi-même cela me permet d'avoir un premier degré de 'souplesse'.

Par exemple les comparaisons sont toujours introduites par le mot est et se finissent par à ou de. Du coup quand je trouve un est lors de l'analyse lexicale, j'isole la comparaison qui est faite et j'ajoute un token à ma liste : COMP_SUP, COMP_INF…

Du coup ça permet du même coup de clarifier un peu les patterns : une condition va être de la forme : EXPR COMP_… EXPR. EXPR est un token spécial qui permet de sauver du code source. Par exemple, pour les variables il faut sauvegarder le nom, celui-ci est stocké avec le token EXPR. Ce token peut aussi contenir des choses plus complexes.

Les conditions peuvent être liées entre elles par des opérateurs logiques d'où les tokens : LOGI_OR et LOGI_AND (j'ai pas mis les autres opérateurs logiques, pour le not, la raison est qu'on a tendance à parer au plus simple quand on parle et qu'on ira pas s'amuser à mettre : si a n'est pas différent de b…)

Juste pour revenir sur les tokens de comparaisons, la génération de ceux-ci reposent sur des .find mais sans rechercher le mot entier, comme .find("sup") pour rechercher un est supérieur à.

Autre problème à résoudre, le mot est est également utilisé dans la déclaration des variables… pour l'instant c'est fixé grâce à la recherche du mot un qui est toujours présent dans la déclaration des variables : a est un entier, chaîne est une chaîne de caractère… Le dernier marche du fait qu'il n'y a pas d'espace après un dans la recherche.

Les boucles itératives sont gérées (mais c'est pas très propres…), je me base sur un pattern qui est très répandu : FOR var_incrémentée MOT MOT valeur_départ MOT valeur_arrivée Par exemple : pour i allant de 0 à 5 ça marche aussi pour cet orthographe : pour i variant entre 0 et 8 ou encore : pour i variant de 0 à 15 en fait les mots n'ont aucune importance : seul le pour est recherché, tout le reste est basé sur le fait qu'on a souvent le mot pour, la variable incrémentée, deux mots quelconques la valeur de début, un mot, la valeur de fin. Au niveau des tokens j'obtiens des trucs comme :
TOKEN(FOR, None)
TOKEN(EXPR, i)
TOKEN(INTER_ST, None)
TOKEN(EXPR, 0)
TOKEN(INTER_TO, None)
TOKEN(EXPR, 5)
TOKEN(INTER_END, None)


Le premier 'paramètre' du token correspond à son 'type' en quelque sorte et le second à sa 'valeur' (uniquement dans le cas d'une expression). Je ne sais pas si c'est très régulier… c'est du maison mais pour l'instant la liste générée est bonne !
"Ce n'est pas parce que les chose sont dures que nous ne les faisons pas, c'est parce que nous ne les faisons pas qu'elles sont dures." Sénèque

Lephenixnoir Hors ligne Administrateur Points: 20809 Défis: 143 Message

Citer : Posté le 10/05/2020 17:39 | #


Ça l'air sympa tout ça. Avant que tu partes trop loin dans la mauvaise direction, attention aux points suivants :

Du coup quand je trouve un est lors de l'analyse lexicale, j'isole la comparaison qui est faite et j'ajoute un token à ma liste : COMP_SUP, COMP_INF…

Non, ça c'est le travail du parser !

Ce token peut aussi contenir des choses plus complexes.

Un token ne doit jamais contenir des informations structurées ! Ça aussi, c'est le job du parser.

Juste pour revenir sur les tokens de comparaisons, la génération de ceux-ci reposent sur des .find mais sans rechercher le mot entier, comme .find("sup") pour rechercher un est supérieur à.

C'est pas propre ça... ^^"

Autre problème à résoudre, le mot est est également utilisé dans la déclaration des variables… pour l'instant c'est fixé grâce à la recherche du mot un qui est toujours présent dans la déclaration des variables : a est un entier, chaîne est une chaîne de caractère…

Vraie solution : utiliser un parser.

Les boucles itératives sont gérées (mais c'est pas très propres…), je me base sur un pattern qui est très répandu : FOR var_incrémentée MOT MOT valeur_départ MOT valeur_arrivée

Voilà, ça c'est exactement une règle de grammaire et c'est ton parser qui se démerde pour repérer ce "motif" dans le flux de token.
Zezombye Hors ligne Rédacteur Points: 1741 Défis: 13 Message

Citer : Posté le 10/05/2020 17:43 | #


"pour I entre 0 et 8" ça devrait aussi être valide

Accepter n'importe quel mot ça me parait foireux, il faut whitelister une liste de mots.
Divers jeux : Puissance 4 - Chariot Wars - Sokoban
Ecrivez vos programmes basic sur PC avec BIDE
Shadow15510 Hors ligne Administrateur Points: 4981 Défis: 16 Message

Citer : Posté le 10/05/2020 17:46 | #


Mais la liste de token ne peut pas seule suffire… Comment je sais quelle variable à quel nom ? Comment je peux afficher du texte ?

Concrètement mon lexer doit associer à chaque mot du code source un token… ? Mais pour le nom des variables par exemple ?

@Zez : Ouaip, c'est pas bête comme idée, d'autant plus qu'à ce niveau les mots sont assez répétitifs
"Ce n'est pas parce que les chose sont dures que nous ne les faisons pas, c'est parce que nous ne les faisons pas qu'elles sont dures." Sénèque

1, 2, 3, 4 ··· 10 ··· 17, 18, 19 Suivante

LienAjouter une imageAjouter une vidéoAjouter un lien vers un profilAjouter du codeCiterAjouter un spoiler(texte affichable/masquable par un clic)Ajouter une barre de progressionItaliqueGrasSoulignéAfficher du texte barréCentréJustifiéPlus petitPlus grandPlus de smileys !
Cliquez pour épingler Cliquez pour détacher Cliquez pour fermer
Alignement de l'image: Redimensionnement de l'image (en pixel):
Afficher la liste des membres
:bow: :cool: :good: :love: ^^
:omg: :fusil: :aie: :argh: :mdr:
:boulet2: :thx: :champ: :whistle: :bounce:
valider
 :)  ;)  :D  :p
 :lol:  8)  :(  :@
 0_0  :oops:  :grr:  :E
 :O  :sry:  :mmm:  :waza:
 :'(  :here:  ^^  >:)

Σ π θ ± α β γ δ Δ σ λ
Veuillez donner la réponse en chiffre
Vous devez activer le Javascript dans votre navigateur pour pouvoir valider ce formulaire.

Si vous n'avez pas volontairement désactivé cette fonctionnalité de votre navigateur, il s'agit probablement d'un bug : contactez l'équipe de Planète Casio.

Planète Casio v42 © créé par Neuronix et Muelsaco 2004 - 2021 | Il y a 44 connectés | Nous contacter | Qui sommes-nous ? | Licences et remerciements

Planète Casio est un site communautaire non affilié à Casio. Toute reproduction de Planète Casio, même partielle, est interdite.
Les programmes et autres publications présentes sur Planète Casio restent la propriété de leurs auteurs et peuvent être soumis à des licences ou copyrights.
CASIO est une marque déposée par CASIO Computer Co., Ltd