Vaincre la récursivité gauche : correction de la grammaire d’un décompilateur C++
Cet article détaille le parcours de l’auteur pour résoudre les problèmes de récursivité gauche et de récursivité gauche mutuelle dans une grammaire sans contexte (CFG) lors de la réécriture du décompilateur C++ de RizinOrg, rz-libdemangle. Il commence par expliquer les concepts de récursivité gauche et de récursivité gauche mutuelle, en montrant à l’aide d’exemples simples et de diagrammes d’état comment transformer les grammaires récursives gauches en grammaires récursives droites pour éviter la récursivité infinie. L’auteur partage ensuite un problème réel rencontré dans le décompilateur Itanium ABI, présentant une grammaire complexe avec récursivité gauche et récursivité gauche mutuelle, et comment il a utilisé des macros et des transformations de grammaire intelligentes pour résoudre ces problèmes, évitant ainsi les erreurs de dépassement de pile.