J'essaie de m'enseigner l'usage du bison. Le bison de la page de manuel (1) dit à propos du bison:

Générez un analyseur syntaxique déterministe LR ou LR généralisé (GLR) en utilisant les tables d'analyseur LALR (1), IELR (1) ou canonique LR (1).

Qu'est-ce qu'un analyseur IELR? Tous les articles pertinents que j'ai trouvés sur le World Wide Web sont payants.

L'algorithme d'analyse IELR (1)

L' algorithme d'analyse IELR (1) a été développé en 2008 par Joel E. Denny dans le cadre de son doctorat. recherche sous la supervision de Brian A. Malloy à l'Université Clemson. L'algorithme IELR (1) est une variante de l'algorithme dit "minimal" LR (1) développé par David Pager en 1977 , qui est lui-même une variante de l' algorithme d'analyse LR (k) inventé par Donald Knuth en 1965 . L'IE dans l'IELR (1) signifie l'élimination de l'insuffisance (voir la dernière section).

Algorithmes LR (1)

La partie LR (1) de IELR (1) représente L eft à droite, D dérivation la plus à droite avec 1 jeton d'anticipation. Les analyseurs LR (1) sont également appelés analyseurs canoniques. Cette classe d'algorithmes d'analyse utilise une stratégie d'analyse ascendante et de réduction de décalage avec une pile et une table de transition d'état déterminant l'action suivante à effectuer pendant l'analyse.

Historiquement, les algorithmes LR (1) ont été désavantagés par les besoins importants en mémoire pour leurs tables de transition. L'amélioration de Pager a été de développer une méthode de combinaison des états de transition lorsque la table de transition est générée, ce qui réduit considérablement la taille de la table. Ainsi, l'algorithme de Pager rend les analyseurs LR (1) compétitifs par rapport à d'autres stratégies d'analyse en termes d'efficacité d'espace et de temps. L'expression «analyseur LR (1) minimal» fait référence à la taille minimale de la table de transition introduite par l'algorithme de Pager.

Limitations de l'algorithme de pager

Les algorithmes minimaux LR (1) produisent la table de transition basée sur une grammaire d'entrée particulière pour la langue à analyser. Différentes grammaires peuvent produire la même langue. En effet, il est possible pour une grammaire non LR (1) de produire un langage analysable LR (1). En pratique, les générateurs d'analyseurs LR (1) acceptent des grammaires non LR (1) avec une spécification pour résoudre les conflits entre deux transitions d'état possibles ("conflits de réduction de décalage") pour tenir compte de ce fait. Denny et Malloy ont constaté que l'algorithme de Pager ne parvient pas à générer des analyseurs suffisamment puissants pour analyser les langues LR (1) lorsqu'il est fourni certaines grammaires non LR (1) même si la grammaire non LR (1) génère un langage LR (1).

Denny et Malloy montrent que cette limitation n'est pas uniquement théorique en démontrant que Gawk et Gpic, deux logiciels matures largement utilisés, effectuent des actions d'analyseur incorrectes.

Améliorations de l'IELR (1)

Denny et Malloy ont étudié la source des lacunes de l'algorithme de Pager en comparant la table de transition générée par l'algorithme de Pager à la table de transition d'une grammaire LR (1) équivalente et ont identifié deux sources de ce qu'ils appellent des insuffisances qui apparaissent dans la table de transition de Pager. algorithme mais pas dans la table de transition LR (1). L'algorithme IELR (1) ( Elimination Elimination LR (1)) de Denny et Malloy est un algorithme conçu pour éliminer ces insuffisances lors de la génération de la table de transition dont la taille est pratiquement identique à celle de l'algorithme de Pager.

Un article qui prétend l'introduire: IELR (1): Tableaux d'analyse syntaxique LR (1) pratiques pour les grammaires non LR (1) avec résolution des conflits (via archive.org) par Joel E. Denny et Brian A. Malloy, Clemson University , est disponible gratuitement sur le site de Malloy.

Ce qu'ils valent, c'est une chose à laquelle je ne peux pas répondre. (Personnellement, je ne comprends pas la nécessité d'une telle analyse CFG paralysée - pourquoi limiter votre pouvoir expressif lorsque vous pouvez simplement utiliser GLR ? Ce qui est logique pour moi est quelque chose comme TAG ou PEG (ils semblent naturels et ajoutent un pouvoir expressif) ou arbre grammaires (pour les langages tels que XML, dans lesquels la reconnaissance des arbres d'analyse n'est pas problématique par conception.)