Grammaire


h1 4/20/2007 11:54:00 AM

J'ai parlé ici-même, il y a presque un an, d'une petite astuce pour obtenir un langage sans point-virgule dans les séquences, juste un peu whitespace-sensitive, tout en utilisant le générateur de parser (ocaml)yacc. Je suis toujours dans cette optique, car je veux garder cette syntaxe légère, et je crois toujours qu'écrire mon parser à la main est source d'emmerdes au moins à long terme.

Résume de l'épisode précédent: le seul endroit où le retour à la ligne compte, c'est pour distinguer f ; (1,2) de f(1,2). Bien sûr la première expression n'a peu d'intérêt, la séquence ne servant qu'aux effets de bord que f ne fait pas, mais cela ne se voit pas au stage de l'analyse syntaxique. Ma solution a été d'introduire un token VARLPAR qui regroupe la variable et la parenthèse qui la suit si elles ne sont pas séparées par un retour à la ligne.

Second épisode: liquidsoap est en plein boom. Nous avons de nouveaux contributeurs, de nouveaux utilisateurs, on parle de nous, de nouvelles idées sont implémentées, etc.

Une de ces idées est le cross-fading intelligent. Au lieu de passer au cross-fading une fonction de transition qui décrit comment sont combinés les débuts et fins de piste, on y passe une liste de (condition,transition). La condition est une fonction à qui le smart_cross passe les puissances du signal sonore de part et d'autre de la transition. L'opérateur choisit la première fonction de transition dont la condition est validée. On peut ainsi choisir de superposer, fader, en fonction du volume des débuts et fin de piste. Romain a commencé à coder dans utils.liq l'utilisation du smart cross selon la description que mouke de bide-et-musique nous a faite.

Cet opérateur amène le besoin de coder dans notre langage de script des expressions arithmétiques, des comparaisons, etc. Et j'ai donc du étendre la grammaire. Pour faire simple, disons qu'on ajoute *, /, + et -.

Premier conflit: comment distinguer f(x) \n -1 de f(x)-1. Les deux sont naturels, on ne peut en éliminer aucun d'office. A moins d'empêcher le programmeur d'éclater ses expressions arithmétiques sur plusieurs lignes, ce qui est peu naturel et de toute façon difficilement réalisable dans mon cadre.

La solution vient de zmdkrbou, qui me propose de distinguer les expressions closes cexpr et les expressions générales expr. Une expression close peut être utilisée sans ambiguité dans une séquence: pour cela on limite les symboles pouvant apparaitre en tête, i.e. on élimine donc les négatifs -42, qui ne sont présents que dans les expressions générales. On peut obtenir une expression close représentant un négatif en l'entourant de parenthèses. Dans la plupart des règles, on peut continuer à utiliser des expressions générales, mais la règle de séquençage d'expression est restreinte aux expressions closes. Ainsi f(x) - 1, où que soient les retours à la ligne, sera la valeur de f(x) décrémentée de 1. Et on écrira f(x) (-1) (en général sur deux lignes, mais rien n'oblige) pour signifier qu'on évalue f(x) et qu'on retourne -1.

On tient le bon bout, mais l'histoire ne s'arrête pas là, et yacc m'en a fait baver. On a dans notre grammaire la règle (1) expr: cexpr, qui dit qu'une expression close est aussi une expression, et la règle (2) cexpr: cexpr PLUS expr. J'avais laissé un expr à droite du PLUS car l'ambiguité vue ci-dessus n'est présente qu'en début d'expression.

Sachant que l'automate d'analyse syntaxique doit décider de ce qu'il fait en ne regardant qu'un symbole en avant, comment savoir dans la situation cexpr PLUS ... si la cexpr doit être considérée comme une expr, auquel cas on réduit la règle (1), ou s'il faut avancer dans la règle (2) en mangeant de suite le +. L'automate est bête, pour lui une addition peut arriver après une expression générale car une expression générale peut être, en particulier, close. On ne peut le guider qu'avec des priorités, je mets donc une priorité plus faible à la coercion (1) qu'à la règle (2).

Et là, c'est le drame. Les priorités entre l'addition et la multiplication ne sont plus du tout respectées, l'analyseur parenthèse tout à droite comme un sale. On lui donne 2*3+1 il lit 2*(3+1). Après masse de bataille, je m'aperçois que la formulation de la règle (2), bien qu'inambigue, pose problème. On a expr: cexpr PLUS expr | cexpr MULT expr .... Le problème est que l'automate défavorise maintenant la coercion expr:cexpr. Du coup quand il voit le + après le 3 il ne va pas réduire l'expression close 3 en expression pour réduire ensuite l'expression close 2*3. Il va préférer manger le +, ce qui conduit à réduire l'expression close 3+1 en premier.

Au final la règle (2) doit s'écrire cexpr: cexpr PLUS cexpr. Et on n'y perd pas trop. On ne peut plus écrire 3+-1 mais il faut parenthéser en 3+(-1).

La morale: c'est toujours possible d'utiliser le couple lex/yacc pour une syntaxe sans point-virgule, en limitant énormément la sensibilité aux blancs (espace et retour à la ligne), ouf. Par contre l'automate de yacc est bien bête sur une production du type expr: cexpr.

Un jour faudra que je voie si c'est si difficile de ne pas ignorer les retours à la ligne à l'analyse syntaxique, et de les traiter explicitement partout dans la grammaire. A priori c'est lourd, comme il ne compte pas dans la majorité des cas. Mais une astuce n'est pas à exclure..

Libellés : , ,

0 commentaires:

Un commentaire ?

< Accueil