Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Shunting-yard algorithm

en.wikipedia.org

Post reply on HN
Print view View original

11–20 of 27 posts

Re: Shunting-yard algorithm

#11

Post by abecedarius »

wenc wrote: post #10
akhilcacharya wrote: post #6

This is one of those algorithms that everyone should understand or memorize. I had variations of this algorithm in the coding interviews or coding challenges of 6 companies (!) my last cycle.

> This is one of those algorithms that everyone should understand or memorize. Understand... perhaps; it is a fascinating algorithm. It's also not complicated at all. Memorize? Perhaps for code challenges, interviews and special occasions like that... but I haven't found it to be useful enough to commit to memory because in order to parse truly arbitrary expressions, you need to remember much more than just the the s…

A good way to rederive table-driven expression parsing on the spot is to start with recursive descent and notice how it makes a recursive call for every level of precedence, even the levels where "nothing happens" because there's no operator of that precedence level at this place in the input. Use the table to call the "right place in the grammar" directly. This works out to be the precedence-climbing algorithm.

I guess you'd get to the shunting yard from there by turning the remaining recursion into an explicit stack, but I haven't worked that out to check.

Re: Shunting-yard algorithm

#12

Post by wenc »

abecedarius wrote: post #11
wenc wrote: post #10

Earlier quoted context omitted.

> This is one of those algorithms that everyone should understand or memorize. Understand... perhaps; it is a fascinating algorithm. It's also not complicated at all. Memorize? Perhaps for code challenges, interviews and special occasions like that... but I haven't found it to be useful enough to commit to memory because in order to parse truly arbitrary expressions, you need to remember much more than just the the s…

A good way to rederive table-driven expression parsing on the spot is to start with recursive descent and notice how it makes a recursive call for every level of precedence, even the levels where "nothing happens" because there's no operator of that precedence level at this place in the input. Use the table to call the "right place in the grammar" directly. This works out to be the precedence-climbing algorithm. I gu…

That sounds about right. I usually use this simple snippet as my starting point [1]. As you can see, to implement a working stack evaluator one has to do a little bit more than just handle infix operators.

[1] PyParsing Simple Calc - see the evaluateStack() function. https://github.com/pyparsing/pyparsing/blob/master/examples/...

Re: Shunting-yard algorithm

#13

Post by userbinator »

chubot wrote: post #7

My blog links to some runnable Python code for this algorithm, with tests: Code for the Shunting Yard Algorithm http://www.oilshell.org/blog/2017/04/22.html https://github.com/bourguet/operator_precedence_parsing It seems like there are 2 common algorithms for expressions: the shunting yard algorithm and Pratt parsing [1]. As best as I can tell, which one you use is a coin toss. I haven't been able to figure out any…

I haven't been able to figure out any real difference.

The biggest difference is that Pratt/precedence climbing does not require manipulating an extra stack, but instead uses the normal procedure stack in the same manner as recursive descent. This leads to somewhat simpler code. I've seen far more uses of recursive descent/Pratt than shunting-yard.

Re: Shunting-yard algorithm

#14

Post by chubot »

userbinator wrote: post #13
chubot wrote: post #7

My blog links to some runnable Python code for this algorithm, with tests: Code for the Shunting Yard Algorithm http://www.oilshell.org/blog/2017/04/22.html https://github.com/bourguet/operator_precedence_parsing It seems like there are 2 common algorithms for expressions: the shunting yard algorithm and Pratt parsing [1]. As best as I can tell, which one you use is a coin toss. I haven't been able to figure out any…

I haven't been able to figure out any real difference. The biggest difference is that Pratt/precedence climbing does not require manipulating an extra stack, but instead uses the normal procedure stack in the same manner as recursive descent. This leads to somewhat simpler code. I've seen far more uses of recursive descent/Pratt than shunting-yard.

I understand that, but I think it's mostly a matter of opinion ("somewhat simpler"). It seems like the code comes out the same length either way, and they're both linear time algorithms.

I can't imagine any case where a user will care -- it's an internal detail. Whereas there are places where a user would notice if you used a CFG vs. a PEG.

A long time ago, people might have been concerned about the recursive calls of Pratt parsing, but it seems like a non-issue now.

I do think Pratt parsing is easier to understand, but that might be because I encountered it first.

Re: Shunting-yard algorithm

#16

Post by User23 »

zzzcpan wrote: post #9
cdoxsey wrote: post #3

This algorithm is great. I was working on a new metric alert evaluation system and built an expression parser for things like: system.disk.free{*} / 1024 by {host} The naive approach to parsing will result in the wrong order of operations, since they'll just be done in the order they appear: x + y * z => (x + y) * z Rather than: x + (y * z) As it should be. The shunting yard algorithm will rearrange the expressions.…

Just the other day I was thinking about how all this infix business is needlessly complicated and leads to subtle bugs and hard to understand code. Like every time I encounter an uncommon operator in some language I have to lookup its precedence. So much time wasted trying to satisfy this silly familiarity with math notation. Only imagine how much easier things could be if all infix operators were, for example, left…

I've always thought it would be cool to have a language where functions were tagged as distributive, associative, symmetric/commutative, and monotonic and the optimizer (and editor!) used these properties to determine optimizations or simplifications. Note that this would be for all expressions, not just arithmetical ones.

I vaguely recall hearing about some fancy C++ template based techniques for accomplishing this, actually, but haven't looked into it.

Re: Shunting-yard algorithm

#17

Post by stevefan1999 »

cdoxsey wrote: post #3

This algorithm is great. I was working on a new metric alert evaluation system and built an expression parser for things like: system.disk.free{*} / 1024 by {host} The naive approach to parsing will result in the wrong order of operations, since they'll just be done in the order they appear: x + y * z => (x + y) * z Rather than: x + (y * z) As it should be. The shunting yard algorithm will rearrange the expressions.…

because essentially, Shunting yard algorithm is just a LR(0) parser, it awaits sufficient information first in a post-order manner (shifting), then each time you push to the final queue if a production is found (reducing)

Re: Shunting-yard algorithm

#18

Post by Insanity »

It's a neat algorithm :) When learning Go I made an implementation of Shunting-Yard at some point: https://github.com/DylanMeeus/GoPlay/blob/master/ExpressionP...

As part of something else I was trying. As I was just learning Go at that point, the code is not that clean :D But AFAIK it did work. My memory is a bit hazy on that :)

Re: Shunting-yard algorithm

#19

Post by fooker »

IIAOPSW wrote: post #2

I was hoping for an algorithm that solves railway shunting problems. Anyone know of something that does that? https://en.wikipedia.org/wiki/Train_shunting_puzzle

Encode it into a SAT instance and use a solver.

Re: Shunting-yard algorithm

#20

Post by saagarjha »

User23 wrote: post #16
zzzcpan wrote: post #9

Earlier quoted context omitted.

Just the other day I was thinking about how all this infix business is needlessly complicated and leads to subtle bugs and hard to understand code. Like every time I encounter an uncommon operator in some language I have to lookup its precedence. So much time wasted trying to satisfy this silly familiarity with math notation. Only imagine how much easier things could be if all infix operators were, for example, left…

I've always thought it would be cool to have a language where functions were tagged as distributive, associative, symmetric/commutative, and monotonic and the optimizer (and editor!) used these properties to determine optimizations or simplifications. Note that this would be for all expressions, not just arithmetical ones. I vaguely recall hearing about some fancy C++ template based techniques for accomplishing this,…

Swift has operator precedence levels, and you are free to use them for your own operators: https://developer.apple.com/documentation/swift/swift_standa...
Post reply on HN