Études-Mathématique/Syntaxe et précédence

From Lazi wiki
Jump to: navigation, search

Question

Jusqu'à présent la précédence des non opérateurs était infinie, mais je m'aperçois que pour certains opérateurs comme .o ce serait mieux une précédence infinie à droite. D'autre part si OP est un opérateur postfix, x OP y z devrait être compris comme "((x OP) y) z" alors que actuellement il est compris comme "(x OP) (y z)".

Comment réorganiser la syntaxe pour la précédence ?

Étude

Principes

Il nous faut assembler une liste de deux sortes d'éléments: les opérateurs et les non opérateurs (non-ops).

La précédence d'un opérateur donne la "force de colle" entre l'opérateur et et le non-op.

Précédence entre un opérateur et un non-op: c'est la précédence de l'opérateur.

Précédence entre deux non-op: c'est la précédence des non-ops.

Un opérateur a une précédence du côté où il s'accroche à un item. Les infix ont la même précédence à droite qu'à gauche.

La précédence d'un opérateur peut être égale ou dépasser celle des non-ops, c'est le cas par exemple pour ".o".

Niveaux de précédence recommandés (plus il y en a et plus on s'embrouille):

  • opérateurs logiques : 10
  • opérateurs faibles (comme l'addition) : 20
  • opérateurs forts (comme multiplication) : 30
  • non op : 40
  • opérateurs suppérieurs aux non-ops : 50

Suppression des infixs orientés à droite ?

Les opérateurs infixs "associatifs à droite" ne correspondent pas à une notion mathématique, mais à une syntaxe qui est une sorte d'inversion de lecture. Finalement ça me semble trop tordu, un peu comme si en français il y avait une syntaxe pour lire à l'envers. Les opérateurs "associatifs à droite" sont rares, et je n'en ai pas vu qui me semble correspondre à une bonne logique. D'autre part, avec les séparateurs, on peut avoir un comportement semblable pour peu que l'on ajoute un séparateur après chaque opérateur.

Donc cela me semble bien de supprimer cette fonctionnalité.

Ajout d'un séparateur ?

Présentation

Jusqu'à présent Lazi avait l'opérateur "." de précédence minimale. Mais ne serait-il pas mieux d'avoir un séparateur, qui a le rôle inverse des parenthèses ?

L'idée est qu'un séparateur sépare ce qui est des deux côté, c'est à dire que l'association entre le groupe de droite et de gauche se fait ainsi:

  • tout ce qui est à droite constitue un groupe
  • tout ce qui est à gauche et jusqu'au prochain séparateur constitue un groupe.

Contrairement à "$" en Haskell ou "." en Lazi, le séparateur peut se placer à côté d'un opérateur. Par exemple "x + y | × z" ou encore "a | b c d" ou "x + y . × z" ou encore "a . b c d".

Si op est un opérateur infix , "a | op ..." n'a pas de sens, ce qui aurait du sens est "a op | ... ". Donc il faut éliminer ce cas dans le parsing. De même que "a | postfix". Par contre cela a un sens à droite, par exemple "a op | ..." signifie "a op ( ... )".

Séparateur à précédence

On pourrait attribuer une précédence au séparateur: Cela équivaut à placer une parenthèse ouvrante à la place du séparateur et à la fermer à la prochaine précédence strictement inférieur. «|» aurait une précédence de 15 et «||» de 0. Donc dans "f | x + y | × z ∧b g c", comme ∧b et | ont la même précédence, cela revient à : "f ( (x + y) × z ) ∧b g c

Remarque: si l'opérateur à gauche du séparateur a une précédence inférieure à celle du séparateur (par exemple "x ∧b | c ∧b ...") : cela ne change pas la règle, c'est à dire que c'est la précédence du séparateur qui est prise en compte.

Remarque: x | y || z | t = (x y) (z t)

Si | a une précédence de 10 et l'opérateur postfix pf de 10 alors x | y z pf = (x (y z)) pf

Introduction de séparateurs

Quand peut-on remplacer des parenthèses par un séparateur ? La question se pose pour le rendu des formules.

Une règle qui me semble bien est de n'introduire un séparateur que s'il peut remplacer une paire de parenthèse en se plaçant à la place de la parenthèse ouvrante.

Conditions pour qu'un séparateur puisse remplacer une parenthèse ouvrante :

  • Si après la fin de la parenthèse on a rien ou une liaison plus faible (et c'est donc un opérateur postfix ou infix) que le séparateur que l'on veut introduire.
  • Si à l'intérieur de la parenthèse on a que des liaisons plus fortes que la précédence du séparateur. Il suffit de vérifier que tous les opérateurs ont une précédence plus grande.
  • Si il y a quelque chose après la fin de la parenthèse, alors le dernier élément à l'intérieur de la parenthèse n'est pas un ProtRight.

Calcul de la précédence après une parenthèse fermante: l'élément suivant est forcément soit:

  • un non-op ou une parenthèse ouvrante (dans ce cas la liaison est trop forte)
  • un infix
  • un postfix

Ce ne peut être un séparateur car on les introduit par la gauche.

Si on peut choisir le niveau de précédence d'un séparateur il faut prendre celui de plus grande précédence.

Comme on introduit les séparateurs par la gauche, peut-on introduire par la suite un séparateur qui change le sens du séparateur précédent ? Un séparateur n'est jamais à gauche d'un opérateur. Si on a introduire le premier séparateur, c'est qu'après la parenthèse on a un opérateur (les séparateurs on une précédence plus faible que les liaisons non-op). Pour que l'introduction d'un séparateur à droite soit gênante il faudrait qu'il soit à gauche de l'opérateur, ce qui est impossible. Donc la réponse est non.

Fonction de découpage

/Essais abandonnés


Par réduction des parenthèses, séparateurs, postfix, infix, opérateurs

Présentation

On réduit les parenthèses, les séparateur, les opérateurs postfix et préfixs, puis les infixs.

Remplacement des parenthèses

Les parenthèses que l'on a déjà ou celles produites par le remplacement des séparateurs sont éliminées par remplacement par un item non-op. Pour cela il suffit d'appliquer la fonction globale sur le contenu de la parenthèse.

Remplacement des séparateurs

L'idée est de remplacer les séparateurs par des parenthèses avant d'appliquer l'algorithme principal.

On remplace le séparateur par une parenthèse ouvrante qui se termine à la première précédence strictement plus petite qui n'est pas un préfix, ou alors à la fin.

Remarquons que la parenthèse fermante ne peux être que devant un séparateur, postfix ou infix.

Remplacement des préfixs

Il nous faut trouver son argument. Soit p sa précédence. On prend tous les éléments à sa droite de précédence strictement supérieure. Si on rencontre un préfix, on utilise la récursivité pour le remplacer (lui et son argument) immédiatement par un item non-op.

On réduit alors le préfix et l'argument ainsi: on calcul l'argument, puis l'application du préfix sur l'argument.

Par exemple :

  • prefix20 x infix30 y postfix20 = (prefix20 x infix30 y) postfix20

Remplacement des postfixs

On cherche le premier postfix, ainsi on ne peut rencontrer en argument que des non-op et infix. L'argument est tout ce qui précède l'opérateur et qui a une précédence supérieure ou égale.

Remplacement des infixs

L'expression ne contient plus que des non-op et des infixs. Pour n'importe quel infix, son argument à gauche est tout (application ou infix) ce qui a une précédence supérieure ou égale, et à droite tout ce qui a une précédence strictement supérieure.

En lisant la liste de gauche à droite, on peut utiliser un état:

  • début : on a encore rien lu
  • après un non-op :

Réponse

On réduit les opérateurs à prefix,postfix et infix. On introduit les séparateurs à précédence et on utilise comme méthode de parsing le "découpage à la précédence la plus faible v2".