Discussion :

[Franck.H]

Question pour ceux qui s'y connaissent... Pour étude, occupation et satisfaction personnelle, je réfléchi sur la création de mon propre langage de script interprété. Je sais gros sujet mais là n'est pas la question vu que c'est un projet purement personnel donc pas de message là dessus

Je me posais simplement une question, pourquoi choisir flex/bison plutôt que le parsing manuel ou inversement comme le cas de python par exemple où c'est fait manuellement ? Quels sont les avantages et inconvenient quant à ces deux choix ?

Est-ce un choix stratégique ou personnel ? Ou est-ce que c'est un choix technique, ... ou autre ?


pour vos avis éclairé

[Obsidian]

Bonjour,

Flex et Bison sont, comme tu le sais probablement, les alter-egos GNU de Lex & Yacc, qui sont les outils « historiques ». En plus, ils fonctionnent encore très bien même s'ils pourraient être remis un peu au goût du jour, notamment au niveau des langages orientés objet.

Au niveau du parsing en lui-même, maintenant, ça revient à demander en quoi les expressions régulières sont un avantage, par rapport à une lecture manuelle de la chaîne de caractères. En fait, le traitement des langages a fait l'objet d'études dont on a notablement dégagé la hiérarchie de Chomsky, par exemple.

Et, à dire vrai, lorsque l'on a commencé à décrire des langages de cette façon, on ne revient plus en arrière. :-) En plus, quand ton langage commence à gagner en complexité, c'est la façon la plus sûre de détecter les ambiguïtés, c'est-à-dire les expressions qui peuvent être interprétées de deux manières différentes, même en fonction du contexte.

Maintenant, pour répondre à ta question, l'intérêt se situe surtout sur la forme, c'est-à-dire la capacité à décrire des langages en utilisant des grammaires normalisées ou tout comme. Par contre, même s'il marche bien, la qualité du code produit n'est pas extraordinaire.

[Franck.H]

C'est vrai que le cas de l'écriture voir avant tout même la bonne compréhension à la relecture d'un source flex ou bison, n'est pas très claire. Les tutoriels n'étant pas légions ca décourage vite l'utilisation de ces outils.

Bon, maîtrisant parfaitement le parsing de fichiers texte manuellement, cela reste un bon exercice de le faire soi-même vu que je connais très très mal flex et bison... à moins que tu connaisse un excellent tutoriel en français de préférence mais par contre très pédagogique

Cela dit, ca ne reste qu'un exercice personnel, même si ca n'aboutit à rien ou pas grand chose ce n'est pas grave, j'aurais préféré utiliser cette expérience personnelle pour étudier ces outils.

[Obsidian]

Les tutoriels n'étant pas légions ca décourage vite l'utilisation de ces outils.

Ça, ce n'est pas vrai. Il suffit de chercher « Lex & Yacc » dans Google pour en avoir des tonnes. À dire vrai, il y a plus de tutoriels que de demandes d'aide pour Lex & Yacc. :-) Il y a même un vieil O'reilly qui leur est consacré.

Bon, maîtrisant parfaitement le parsing de fichiers texte manuellement, cela reste un bon exercice de le faire soi-même vu que je connais très très mal flex et bison... à moins que tu connaisse un excellent tutoriel en français de préférence mais par contre très pédagogique

À dire vrai, je partagerais bien un de mes anciens devoirs faits jadis en cours parce que l'exercice est intéressant, mais je crois savoir que le sujet est toujours distribué aux étudiants actuels, donc… chut. :-)

Par contre, ça dépend de ce que tu entends par « maîtriser parfaitement » le parsing. Est-ce que tu lis ton fichier mot à mot et que tu agis au cas par cas, ou bien est-ce que tu définis une grammaire à l'avance ? Dans le premier cas, comment écrirais-tu un parser de fichiers *.c, par exemple ?

[Franck.H]

Ça, ce n'est pas vrai. Il suffit de chercher « Lex & Yacc » dans Google pour en avoir des tonnes. À dire vrai, il y a plus de tutoriels que de demandes d'aide pour Lex & Yacc. :-) Il y a même un vieil O'reilly qui leur est consacré.

Mouais j'en ai déjà trouvé quelques-uns mais pour le moment rien de bien concret à part les bases mais pas forcément d'exemple concret avec étude de cas par exemple. Par contre des infos balancées à la hâte, ca pas de soucis

Par contre, ça dépend de ce que tu entends par « maîtriser parfaitement » le parsing. Est-ce que tu lis ton fichier mot à mot et que tu agis au cas par cas, ou bien est-ce que tu définis une grammaire à l'avance ? Dans le premier cas, comment écrirais-tu un parser de fichiers *.c, par exemple ?

Je parlais de manière générale, pour le moment je n'est même pas encore produit un seul fichier source, c'est en cours d'étude tout simplement

Niveau syntaxe pas de soucis, je la maîtrise étant donné que je veut me rapprocher le plus possible du C, mon langage préféré

[Franck.H]

Il y a même un vieil O'reilly qui leur est consacré.

Je viens de trouver un livre sur Flex & Bison: Amazon.fr: John Levine: Livres en anglais@@AMEPARAM@@http://ecx.images-amazon.com/images/I/41UCO-psy7L.@@AMEPARAM@@41UCO-psy7L et assez récent apparemment (2009), je vais me le commander je crois

[Obsidian]

Pour faire simple, on va dire que Lex & Yacc sont très utilisés pour écrire des compilateurs.

Si tu veux t'initier à Lex & Yacc et avoir un exemple concret, le mieux est encore d'essayer de réaliser la calculatrice à quatre opérations (en gérant les priorités). L'exercice est considéré comme le « Hello World » de ces outils.

Maintenant, pour en exploiter pleinement la puissance et l'intérêt, il faut quelques notions de langages formels. Lex & Yacc sont deux outils distincts, mais dont l'utilisation est similaire et qui sont faits pour travailler de concert.

Lex est un « lexer », c'est-à-dire un outil qui va te permettre de reconnaître des « lexons », c'est-à-dire des unités lexicales. Pour cela, tu vas définir une collection d'expression régulières, qui vont retrouver linéairement ces lexons au sein du texte que tu analyses. Ces unités lexicales peuvent être des mots, mais également des choses plus évoluées telles que des nombres, par exemple. Or, ceux-ci sont en nombre infini, donc il est impossible de tous les énumérer, mais il est tout-à-fait possible, à voir la manière dont un mot est écrit, de dire s'il s'agit bien d'un nombre ou pas.

Dès lors, une fois reconnu comme tel, tu n'as plus besoin, dans un premier temps, de connaître sa valeur exacte. Si, par exemple, le mot que tu viens de lire suit un signe « = » qui lui même suit un nom de variable (donc une affection, en C) et que cette variable est numérique, la seule chose que tu aies besoin de savoir est que ce mot est un nombre, quelle que soit sa forme.

De là, Yacc te permet d'écrire des règles de grammaire combinant ces lexons, de reconnaître les textes respectant ce langage. La plupart du temps, donc, il s'agira de langages informatiques. Cela dit, rien ne t'interdit, en théorie, de réécrire les règles de grammaire de la langue française et t'en servir comme add-on pour ton traitement de texte. Par contre, il faudra prévoir plusieurs années de travail.

Enfin, et ce n'est pas là leur moindre intérêt, dans un outil comme dans l'autre, tu peux associer à chaque règle quelques lignes de code, exécutées lorsque ladite règle est vérifiée. Tu vas t'en servir en faisant la calculatrice, par exemple.

Maintenant, la hiérarchie de Chomsky est importante pour savoir ce qui doit être fait avec Lex et ce qui doit être fait avec Yacc. Une question pertinente étant alors « peut-on tout reconnaître avec une expression régulière » ? Un début de réponse ici.

[Franck.H]

Ok J'ai déjà commandé mon livre et on verra après ce que ca donne Mais c'est vrai qu'en étudiant un peu autour de tout ce qu'il y a à faire, ces outils épargne tout de même une énorme quantité de travail, je ne comprend pas pourquoi avec Python par exemple, il aient décidé de ne pas les utiliser

[Obsidian]

Je ne sais pas ce qu'il en est du développement de Python en particulier mais, comme on l'a dit, il faut déjà avoir été sensibilisé au sujet pour en voir l'intérêt. Par contre, effectivement, une fois que l'on voit de quoi il s'agit, on se dit que réinventer la roue de ce côté est un travail aussi considérable qu'inutile.

Le problème est que c'est également un gros fil à la pâte : le code généré est important et pas formidable, et il impose la présence de ces outils sur la plate-forme de compilation. Si je devais sortir un produit grand public, j'y réfléchirais également.

D'autre part, le O'reilly est un bon livre mais il traite de l'utilisation de l'outil en lui-même. Ce n'est pas un cours. Tu peux déjà jeter un œil à la page Wikipédia de l'analyse syntaxique ainsi que la nôtre.

Après, essaie d'écrire la calculatrice à quatre opérations avec Yacc. L'idée générale est de gérer, outre la reconnaissance des nombres et des opérateurs, la priorité des opérations entre elles, et cela se fait en amont, sur la forme. C'est-à-dire que si tes règles de grammaires sont bien écrites, les priorités dans ton calcul se feront d'elles-mêmes, sans que tu aies besoin d'écrire une ligne de code pour les prendre en compte.

[pfeuh]

Salut,

L'idéal serait de pouvoir trouver un tutoriel ici, sur developpez.com

A+

Pfeuh

[Franck.H]

Bin je serais peut-être en mesure d'en faire un quand j'aurais apprivoisé la bête

[Obsidian]

Mouais. Je pourrais peut-être me dévouer, mais je ne suis pas sûr d'être l'expert qu'il faut. Il faudrait surtout une rubrique adaptée, car la plus proche pour le moment reste le forum C. C'est nécessaire car les outils sont très liés au langage C, mais leur objet principal en reste complètement détaché.

Bon. Quand tu fais de la reconnaissance de langage, il y a généralement trois étapes :

1. L'analyse lexicale ;
2. L'analyse syntaxique ;
3. L'analyse sémantique.

La première sert à reconnaître les unités lexicales, en elle-même, soit de façon simple les mots que ton langage contient, et qui sont reconnus comme valides. Ça peut être une liste de mots-clés, mais ça peut être un nombre par exemple. L'ensemble des nombres est infini, mais ces nombres sont quand même formés d'une certaine manière. Dans le même esprit, tu peux définir une suite de caractères comme un « nom de variable » si elle en respecte les règles (généralement une lettre suivie d'un ensemble de lettre ou de chiffres).

La seconde te permet de savoir si une phrase est bien construite avec ces lexons. C'est-à-dire : si elle respecte les règles de grammaire. Utiliser des mots-clés valides mais dans le désordre conduit à une erreur de syntaxe. Il est à noter que dans la plupart des langages informatiques, ces deux phases sont généralement confondues et aboutissent toutes deux à un « syntax error ». Mais certains frameworks, comme GTK, sont capables de faire le distingo.

La troisième consiste à analyser le sens de ta phrase. Là, on sort du cadres des langages formels, précisément parce qu'on travaille sur le fond et plus sur la forme.

Exemple : je veux travailler sur un sous-ensemble (très restreint) de la langue française. Celui-là même qui me permet de dire « Je suis français. » à l'affirmatif, ou « Suis-je français ? » à l'interrogatif. On voit d'emblée qu'il s'agit des mêmes mots disposés différemment, mais selon des règles strictes. La phrase « Je français suis » utilise également les mêmes mots mais ne veut rien dire.

1) Je commence par définir les signes indivisibles qui me permette de faire des compositions, soit mon alphabet : donc en l'occurrence, les lettres A à Z en minuscules et majuscules, les espaces, et éventuellement la ponctuation, donc le tiret, le point d'interrogation et le point final. Ceci fait, je définis un vocabulaire qui n'utilise que cet alphabet : « je » , « suis » , « français », « - », « ? » et « . ».

De là, je peux nommer mes unités lexicales si je le souhaite : « je » = SUJET, « suis » = VERBE, « français » = COMPLEMENT.

2) Je définis mes règles de GRAMMAIRE :

phrasecorrecte = affirmation | interrogation
affirmation = SUJET VERBE COMPLEMENT POINT
interrogation = VERBE SUJET COMPLEMENT

On note que les règles dépendent les unes des autres. Il faut donc une règle de départ, appelée « axiome », considérée comme vraie. En mathématique, on la nommera explicitement. Dans YACC, ce sera tout simplement la première de la liste (donc, ici, « phrasecorrecte »). Le « | » est un OU.

3) L'analyse sémantique : elle se fait a posteriori, quand le langage utilisé est reconnu par ton parser, donc réputé correct. Par exemple, je peux écrire « deux plus deux égalent cinq ». C'est faux d'un point de vue mathématique, mais cela reste une phrase tout-à-fait correcte — et légale — en français.

La suite un peu plus tard. :-)