Priorité de la fonction dans l'algorithme Shunting-yard

Je travaille sur l' algorithme Shunting-yard , comme décrit par wikipedia.

La description de l'algorithme lorsqu'il s'agit d'opérateurs est la suivante:

Si le jeton est un opérateur, o1, alors:

alors qu'il y a un jeton d'opérateur, o2, en haut de la pile d'opérateurs, et

o1 is left-associative and its precedence is less than or equal to
that of o2, or

o1 is right associative, and has precedence less than that of o2,

puis pop o2 hors de la pile d'opérateurs, dans la file d'attente de sortie;

poussez o1 sur la pile de l'opérateur.

Cependant, ils donnent l'exemple suivant:

Contribution: sin max 2 3 / 3 * 3.1415

Lorsque l'algorithme atteint le /jeton, la description de ce qui doit se produire est la suivante:

Token |        Action       |   Output (in RPN) |   Operator Stack
...
/     | Pop token to output | 2 3 max           | / sin 
...

Ils maxsortent le jeton de fonction du stacket le mettent dans le queue. Selon leur algorithme, cela semble signifier que le jeton de fonction est à la fois un opérateur et a une priorité inférieure à celle de l' /opérateur.

Il n'y a aucune explication quant à savoir si c'est le cas ou non. Alors, pour l' Shunting-yardalgorithme, quelle est la priorité d'une fonction? Les fonctions sont-elles associatives à droite ou à gauche? Ou wikipedia est-il simplement incomplet / inexact?

Je crois que la réponse directe est simplement que les fonctions ne sont pas des opérateurs. À partir de la page que vous avez liée:

Si le jeton est un jeton de fonction, poussez-le sur la pile.

C'est tout ce qu'il faut dire, car le cas de fonction (préfixe à postfix) est beaucoup plus simple que le cas d'opérateur (infixe à postfix).

Pour les questions complémentaires: Les notions de priorité et d'associativité ne sont nécessaires qu'en raison de l'ambiguïté héritée dans toute expression avec plusieurs opérateurs d'infixe. Les jetons de fonction utilisent déjà la notation de préfixe, donc ils n'ont tout simplement pas ce problème. Vous n'avez pas besoin de savoir si sinou maxa une "priorité plus élevée" pour déterminer ce qui maxdoit être évalué en premier; c'est déjà clair d'après l'ordre des jetons. C'est pourquoi les ordinateurs préfèrent la notation pré / postfix pour commencer, et pourquoi nous avons cet algorithme pour convertir infix en pré / postfix.

Vous devez avoir une sorte de règle pour le début et la fin des arguments d'une fonction lorsqu'aucune parenthèse n'est présente, vous pouvez donc dire que les fonctions "ont priorité" sur les opérateurs ou vice versa. Mais contrairement aux opérateurs d'infixe, une seule règle cohérente pour toutes les fonctions suffit pour rendre leurs compositions sans ambiguïté.

Il existe deux cas différents à considérer, selon la syntaxe de votre langue. Si votre langue utilise des parenthèses pour indiquer l'application de la fonction (par exemple f(2+1)), la priorité n'est pas pertinente. La fonction doit être poussée sur la pile et sautée après (pour l'exemple ci-dessus, le résultat est 2 1 + f). Vous pouvez également traiter la fonction comme une valeur et la générer immédiatement, et générer une opération d'invocation de fonction après la parenthèse fermante (qui devrait sinon être traitée de la même manière que toute autre parenthèse), par exemple f 2 1 + $, où se $trouve l'opération d'invocation de fonction.

Si votre langage, cependant, n'utilise pas de parenthèses pour indiquer l'invocation d'une fonction, mais place plutôt l'argument directement après la fonction sans aucune ponctuation spéciale (par exemple f 2 + 1), comme c'est apparemment le cas pour l'exemple de Wikipedia, alors les choses sont un peu plus compliquées. Notez que l'expression que je viens de donner à ás est un exemple ambigu: f est-il appliqué à 2 et 1 ajouté au résultat, ou ajoutons-nous 2 et 1 ensemble, puis appelons f avec le résultat?

Encore une fois, il existe deux approches. Vous pouvez simplement pousser la fonction vers la pile d'opérateurs lorsque vous la rencontrez et lui affecter la priorité que vous souhaitez. C'est l'approche la plus simple, et c'est apparemment ce qu'a fait l'exemple cité. Il y a cependant des problèmes pratiques. Premièrement, comment identifiez-vous une fonction? Si vous avez un ensemble fini, c'est facile, mais si vous avez des fonctions définies par l'utilisateur, cela signifie que votre analyseur doit également être réinjecté dans votre environnement, ce qui peut devenir rapidement désordonné. Et comment gérez-vous les fonctions avec plusieurs arguments?

Mon sentiment est que pour ce style de syntaxe, l'utilisation de fonctions comme des valeurs plus pratiques pour un opérateur d'application de fonction est beaucoup plus logique. Ensuite, vous pouvez simplement injecter l'opérateur d'application chaque fois que vous lisez une valeur et la dernière chose que vous lisez était également une valeur, de sorte que vous n'avez pas besoin d'un moyen spécial de dire quels identificateurs sont des fonctions. Vous pouvez également travailler avec des expressions qui renvoient des fonctions (ce qui est difficile ou impossible avec le style de fonction en tant qu'opération). Et cela signifie que vous pouvez utiliser le curry pour gérer plusieurs fonctions d'argument, ce qui est une simplification massive par rapport à leur gestion directe.

La seule chose que vous devez alors décider est quelle est la priorité de l'application de la fonction. Le choix vous appartient, mais dans toutes les langues que j'ai utilisées qui fonctionnent comme ça, il a été l'opérateur le plus fortement contraignant dans la langue, et a été juste associatif. (La seule variation intéressante étant Haskell, qui en plus d'avoir la version fortement contraignante décrite, a également un synonyme pour cela avec le symbole $qui est l'opérateur le plus faiblement contraignant dans la langue, permettant des expressions comme f 2 + 1appliquer f à 2 et f $ 2 + 1appliquer à l'ensemble du reste de l'expression)

J'ai implémenté les «fonctions dans la cour de triage» demandées après avoir lu la pensée originale de Dijkstra (Pages 7-11 dans le document du compilateur Algol 60, https://ir.cwi.nl/pub/9251 ), et ayant besoin d'une solution robuste, j'ai a fait ce qui suit:

analyse:

• Appuyez sur le descripteur de fonction
• Poussez un crochet gauche de début d'argument "[" tout comme son début de parenthèse de sous-expression.
• Lire une séquence de liste d'arguments équilibrée "(" à ")" à partir de l'entrée
• Poussez-le dans le flux de jeton de sortie
• Poussez un support droit de fin d'argument "]" tout comme son "support de fermeture compensateur"

Infixe à postfixe (cour de manœuvre):

• Ajoutez une autre pile, la pile de fonctions, tout comme la pile d'opérateurs
• Lors de la numérisation d'un nom de fonction, poussez les informations de fonction dans la pile de fonctions
• Lorsqu'un crochet droit de fin d'argument est visible, faites apparaître la pile de fonctions pour sortir

Fonctionne parfaitement dans des tests robustes et des scénarios compliqués. Dans mon application (un expanseur contenant des expressions contenant des arguments en ligne de commande), je prends en charge les fonctions multi-arguments et une virgule "," pour les séparer, et celles-ci traversent tout le processus.

Les exemples ressemblent à "sqrt (3 ^ 2 + 4 ^ 2)" qui devient "3 2 ^ 4 2 ^ + sqrt" et finalement "5" qui est ce que le programme pense être l'argument. C'est bignum, donc "" binomial (64, 32) / gcd (binomial (64, 32), binomial (63, 31)) "==> grandes choses ==>" 2 "est utile." 123456 ^ 789 " est de 40 173 chiffres et le timing indique "evaluation = 0,000390 sec" sur mon MacBookPro, donc rapide.

Je l'utilise également pour développer des données dans des tableaux et trouver cela pratique. Quoi qu'il en soit, c'est mon astuce sur ma façon de gérer soigneusement les appels de fonction, les arguments multiples et l'imbrication profonde dans un contexte de triage de Dijkstra. Je viens de le faire aujourd'hui par réflexion indépendante. Je ne sais pas s'il existe de meilleures façons.