Pratt-Parsing verstehen: Der Aha-Moment kommt mit dem Shunting-Yard-Vergleich
Writing about pratt parsing so I remember it
Pratt-Parsing taucht im Informatikstudium kaum auf – weder im Dragon Book noch in den meisten Kursen. Der Autor baut einen Parser für C-Ausdrücke, stützt sich auf Pratts Originalpapier und Crafting Interpreters und beschreibt, wie der rekursive Aufrufbaum den expliziten Operator-Stack des Shunting-Yard-Algorithmus ersetzt. Der Vergleich macht den entscheidenden Unterschied greifbar: Subausdrücke entstehen durch Rekursion statt durch Stack-Manipulation, was Erweiterungen wie Klammern oder unäre Operatoren erheblich vereinfacht.
Der Hauptunterschied, der den Shunting-Yard-Algorithmus in einen Pratt-Parser verwandelt, besteht darin, statt eines expliziten Stacks für Operatoren den Call-Stack zu nutzen, um Subausdrücke zu betreten, wenn Operatoren sie benötigen.