Hacker News new | past | comments | ask | show | jobs | submit login

I believe you're right for the recursive version (though a recursive version of shunting yard makes very little sense), but this distinction largely evaporates with an explicit stack.

E.g. Pratt is basically writing a generic recursive descent component ("parse left; parse operand; parse right") and then passing down a precedence where you terminate the subtree parse. That's a large part of the appeal - it slots seamlessly into a recursive descent parser without looking "alien", and it was what I started with. It's nice because it is top down.

The naive way of making the stack explicit here is to "push" a fake stack frame when you would have recursed, and pop when you would have exited. But to do all tree of the parse_left/parse_operand/parse_right triple this way you then need to push additional frames to run those steps one after each other, and you end up with something really ugly. But if you trace the processing of those additional frames, what you will see then is quickly that you can drop them by just splitting the stack into operands and operators. Then you have shunting yard.

So you're sort of right that a naive translation of Pratt that retains the top-down nature of recursive Pratt is distinct from shunting yard, but once you simplify it the before/after distinction evaporates, as there's nothing in between to make the decision before/after.

I think the distinction is large enough that it makes sense to treat them as different algorithms, but the transformation is still mostly a mechanical exercise. Each step is fairly straightforward.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: