Les générateurs de parseurs peuvent aussi produire de bonnes erreurs.

Traduction d’un article publié en 2010 par Russ Cox, développeur Go.

• Le mythe s’était répandu selon lequel les générateurs syntaxiques comme yacc ne pouvaient pas produire de bons messages d’erreur de syntaxe.

• Mais ce problème avait déjà été résolu par Clinton Jeffery en 2003, et ce n’est pas un problème qui nécessite d’écrire un parseur à la main.

• En recherchant dans une table l’élément correspondant à l’état (bison) et au token d’entrée, on peut utiliser des erreurs meilleures qu’une simple erreur de syntaxe.

[lifthrasiir]

(Ce qui suit est une mise en forme de propos que j’ai écrits sur le serveur Discord Rust coréen.)

Le principal problème de cet article est donc de savoir si Go utilise actuellement un générateur de parseur. La réponse est non. Le parseur principal de Go est toujours écrit à la main. Je ne sais pas exactement pourquoi, mais il est très probable que le fait que rsc trouve cela acceptable n’ait pas suffi pour que les autres développeurs de Go le jugent acceptable eux aussi.

L’idée de Jeffrey est, si l’on raisonne en termes de compilateur, comparable à un peephole optimizer. Avant d’émettre le code machine, on conserve un nombre fixe des instructions machine récemment produites — d’où ce nom, puisqu’on observe cette fenêtre à travers un « trou de serrure » (peep-hole) — puis, lorsqu’un motif précis apparaît, on remplace immédiatement l’instruction concernée par une instruction plus rapide. Un peephole optimizer est un outil pratique qui peut être utilisé en parallèle d’autres passes d’optimisation plus générales, mais il ne peut pas, à lui seul, effectuer tous les types d’optimisations qu’un compilateur exige. De la même manière, l’approche qui consiste à générer des erreurs à partir des jetons récents ne peut pas couvrir toutes les erreurs de parsing. En outre, comme il s’agit d’une approche indépendante qui peut être appliquée même sans générateur de parseur, il n’est pas juste d’affirmer que l’existence de cette approche fait disparaître les problèmes des générateurs de parseur.

Personnellement, je ne pense pas que le concept de générateur de parseur soit mauvais en soi ; je pense plutôt que le problème vient de la manière de penser qu’un générateur de parseur « impose ». Quand on écrit un parseur, qu’il soit généré ou codé à la main, il faut par exemple tenir compte de la left recursion et de la right recursion, et l’on ne peut pas coder telle quelle une grammaire « naturelle ». Lorsqu’on le code à la main, on accepte ce coût ; mais si, même en utilisant un générateur de parseur, on doit écrire en se conformant à un sous-ensemble de « grammaire » lié à un algorithme de parsing particulier comme LL/LR, alors l’intérêt du générateur s’en trouve fortement réduit. (Des algorithmes comme GLR offrent certes un peu plus de marge de manœuvre, mais ils ont aussi leurs limites.) Si la plupart des implémentations de langages de niveau production n’utilisent pas aujourd’hui de générateurs de parseur, ou bien utilisent parfois des approches comme PEG — qui sont certes des générateurs de parseur, mais qui ne tirent absolument pas parti des avantages des générateurs généralistes —, ce n’est pas sans raison.

[dynalloc]

Je comprends qu’on puisse ne pas utiliser de générateur de parseur parce qu’on n’aime pas la grammaire qu’il impose, mais de là à affirmer qu’un générateur de parseur force les utilisateurs à adopter une grammaire particulière, c’est étrange.

Les générateurs de parseurs sont apparus pour aider à produire des tables d’analyse pour les grammaires LR, qui ont l’avantage d’un parsing en temps linéaire mais sont très difficiles à construire à la main. En revanche, générer des parseurs pour des grammaires context-sensitive non déterministes, ou des parseurs récursifs dont on ne sait pas quand l’analyse se terminera, ne fait probablement pas partie des centres d’intérêt des chercheurs et développeurs en générateurs de parseurs.

Par conséquent, je pense qu’un générateur de parseur n’est pas un programme qui idolâtre et impose des grammaires LR/LALR peu intuitives, mais un outil qui remplit bien son rôle en résolvant un problème très difficile : le parsing en temps linéaire et la production des tables d’analyse nécessaires à cet effet.

[lifthrasiir]

Presque tous les langages que l’on rencontre dans la pratique ont une grammaire LL(1), ce qui permet un parsing en temps linéaire sans avoir recours à un parseur LR. (Cela ne veut pas dire que la grammaire préférée pour ces langages est LL(1).) Dire qu’il faut utiliser un parseur LR pour obtenir un parsing en temps linéaire et qu’un générateur est nécessaire parce qu’il est difficile de construire la table d’analyse inverse l’ordre logique. En outre, le processus de construction de la table d’analyse n’est pas intrinsèquement complexe en soi (c’est la preuve de l’algorithme qui est difficile).