Linksrekursion bezwingen: Korrektur der Grammatik eines C++-Demanglers

Dieser Artikel beschreibt den Weg des Autors bei der Lösung von Problemen mit Linksrekursion und gegenseitiger Linksrekursion in einer kontextfreien Grammatik (CFG) während der Umschreibung des C++-Demanglers rz-libdemangle von RizinOrg. Er beginnt mit der Erklärung der Konzepte Linksrekursion und gegenseitige Linksrekursion und zeigt anhand einfacher Beispiele und Zustandsdiagramme, wie man linksrekursive Grammatiken in rechtsrekursive Grammatiken umwandelt, um unendliche Rekursion zu vermeiden. Der Autor teilt dann ein reales Problem, das im Itanium-ABI-Demangler aufgetreten ist, und zeigt eine komplexe Grammatik mit Linksrekursion und gegenseitiger Linksrekursion, und wie er Makros und intelligente Grammatiktransformationen verwendet hat, um diese Probleme zu lösen und so Stack-Overflow-Fehler zu vermeiden.