Disambiguating Context-Free Grammars by Selecting the Minimum-Cost Parse Tree

Le langage est un système de règles qui nous permet de construire des idées complexes à partir de parties simples. Dans le monde de l'informatique, ces règles sont appelées grammaires, et elles indiquent à une machine comment comprendre une chaîne de code ou une phrase. Idéalement, un ensemble de règles devrait conduire à une seule interprétation possible pour toute entrée donnée. Cependant, de nombreuses grammaires utilisées pour décrire les langages de programmation sont ambiguës, ce qui signifie qu'une seule chaîne de texte peut être interprétée de plusieurs manières conflictuelles. Un exemple classique est une phrase comportant deux opérations, comme l'addition et la multiplication de nombres. Sans instructions claires, un ordinateur ne peut pas savoir s'il doit d'abord additionner puis multiplier, ou multiplier d'abord puis additionner. De même, dans une chaîne d'instructions « if », un ordinateur pourrait ne pas savoir à quelle condition une instruction « else » appartient. Pour qu'un ordinateur fonctionne correctement, il doit choisir exactement une interprétation, mais les règles elles-mêmes ne fournissent souvent pas de vainqueur clair.

Pendant des décennies, la méthode standard pour gérer cette confusion a été de forcer les règles à être moins ambiguës en les réécrivant à la main ou en ajoutant des déclarations spéciales qui indiquent à l'ordinateur quel chemin prendre lorsqu'il est bloqué. Ces méthodes fonctionnent bien pour des types spécifiques de problèmes, mais elles nécessitent une intervention humaine et peuvent parfois briser la structure originale du langage. Une nouvelle approche, proposée par Mina Hematikarimkhani, traite le problème non pas comme un puzzle à résoudre en réécrivant les règles, mais comme un défi d'optimisation. Au lieu d'essayer de supprimer les mauvaises réponses, cette méthode demande à l'ordinateur d'évaluer chaque interprétation possible et de sélectionner celle qui est la plus « économique » selon un ensemble de critères spécifiques.

L'idée centrale est d'attribuer un coût à chaque structure possible en forme d'arbre que l'ordinateur construit pour comprendre le texte. Dans ce système, un arbre représente une façon d'analyser la phrase. Le coût n'est pas une valeur monétaire, mais un score basé sur trois facteurs. Premièrement, le système compte le nombre de fois où l'arbre viole les modèles préférés de l'utilisateur, tels que les règles sur l'ordre de priorité des opérations. Deuxièmement, il compte le nombre de nœuds dans l'arbre, ce qui aide à empêcher l'ordinateur de rester bloqué dans des boucles infinies. Enfin, si deux arbres ont le même score, un identifiant unique départage l'égalité pour garantir que l'ordinateur choisisse toujours exactement le même résultat. L'ordinateur conserve ensuite l'arbre ayant le score total le plus bas. Parce que le système pénalise les mauvais choix plutôt que de les interdire purement et simplement, il garantit que chaque phrase valide du langage recevra exactement une interprétation, même si celle-ci implique certaines violations de règles.

Pour trouver ce meilleur arbre, les chercheurs utilisent une méthode appelée programmation dynamique, qui est une façon de résoudre des problèmes complexes en les décomposant en morceaux plus petits et chevauchants. Imaginez l'ordinateur regardant une phrase et essayant de trouver la meilleure façon de comprendre chaque petit fragment de celle-ci, puis en combinant ces fragments pour comprendre l'ensemble. Pour des cas simples, comme décider l'ordre des opérations, l'ordinateur n'a besoin de regarder que les voisins immédiats. Cependant, pour des situations plus complexes, telles que le problème du « else » orphelin (dangling else) où une clause « else » pourrait appartenir à un « if » proche ou à un « if » lointain, l'ordinateur doit regarder plus loin dans la structure. Pour gérer cela, les chercheurs ont introduit le concept de profil. Pendant que l'ordinateur construit une petite partie de l'arbre, il crée également un résumé bref, ou profil, qui indique à la structure parente ce qui se trouve en dessous, comme le fait qu'une branche se termine par un type de règle spécifique. Cela permet à l'ordinateur de prendre des décisions éclairées sur des parties distantes de la phrase sans avoir à reconstruire l'arbre entier à chaque fois.

La méthode fonctionne pour n'importe quel ensemble de règles, y compris ceux qui contiennent des étapes vides ou des références circulaires qui confondraient d'autres systèmes. Lors des tests, les chercheurs ont appliqué cette technique à divers exemples, incluant des expressions mathématiques avec des opérateurs mixtes et des instructions conditionnelles imbriquées. Dans chaque cas, le système a identifié avec succès l'arbre le plus approprié. Par exemple, face à une chaîne contenant à la fois une addition et une multiplication, le système a choisi l'arbre qui respectait la priorité mathématique standard, attribuant un coût plus élevé à l'arbre qui violait cette règle. Face à des instructions « if » imbriquées, il a correctement rattaché le « else » au « if » le plus proche, ce qui est la convention standard en programmation. Le système a également géré les cas où aucune règle spécifique n'était fournie, adoptant par défaut un choix cohérent et déterministe basé sur la structure même de l'arbre.

Bien que la méthode soit puissante, l'auteur est clair sur ses limites. Le temps nécessaire pour exécuter l'algorithme augmente considérablement à mesure que l'entrée devient plus grande, ce qui la rend trop lente pour les exigences de haute vitesse des compilateurs de production modernes qui traitent des millions de lignes de code chaque seconde. Au lieu de cela, les chercheurs suggèrent que cette approche est mieux adaptée aux outils devant gérer des grammaires arbitraires définies par l'utilisateur, tels que les éditeurs de langage, les outils d'analyse statique ou les logiciels éducatifs où la reproductibilité et la gestion de règles complexes et désordonnées sont plus importantes que la vitesse brute. La qualité du résultat dépend entièrement des modèles fournis par l'utilisateur ; si les règles sont incomplètes ou contradictoires, le système retournera tout de même un résultat, mais il peut ne pas être celui que l'humain avait prévu. La méthode ne résout pas le problème mathématique fondamental de déterminer si une grammaire est ambiguë en premier lieu, mais elle offre un moyen fiable de naviguer dans cette ambiguïté une fois rencontrée.

Ce travail représente un changement dans notre façon de concevoir le traitement du langage. Plutôt que d'essayer de forcer les règles d'un langage à être parfaites avant même qu'un ordinateur ne les voie, il permet à l'ordinateur d'explorer toutes les possibilités et de choisir la meilleure selon un standard clair et mesurable. Il reconnaît que l'ambiguïté est une caractéristique de nombreux langages naturels et artificiels et propose un moyen de la gérer sans perdre la structure originale du langage. En traitant la désambiguïsation comme une recherche du coût minimum, les chercheurs ont créé un outil qui est flexible, robuste et capable de gérer la réalité désordonnée des grammaires complexes, garantissant que pour chaque phrase valide, il existe toujours une réponse claire et reproductible.