4 ms·
This is pretty clever. There's a video by Jonathan Blow, creator of Braid and currently making a programming language called Jai, that talks about parsing expre
by tgb 6y ago
This is pretty clever. There's a video by Jonathan Blow, creator of Braid and currently making a programming language called Jai, that talks about parsing expressions with order of operations. He gives an simple approach that apparently was discovered recently (though he didn't remember the paper name) that does this in a single pass and hardly any more complicated than what you wrote. You can see it here [1]. He also trashes on using yacc/bison before that and on most academic parsing theory.
[1] https://www.youtube.com/watch?v=MnctEW1oL-E&t=4578s https://www.youtube.com/watch?v=MnctEW1oL-E&t=4578s
- westurner 6y agoReverse Polish notation (RPN) > Converting from infix notation https://en.wikipedia.org/wiki/Reverse_Polish_notation#Converting_from_infix_notation https://en.wikipedia.org/wiki/Reverse_Polish_notation#Conver... > Shunting-yard algorithm https://en.wikipedia.org/wiki/Shunting-yard_algorithm https://en.wikipedia.org/wiki/Shunting-yard_algorithm Infix notation supports parentheses. Infix notation: 3 + 4 × (2 − 1) RPN: 3 4 2 1 − × +
- mucinoab 6y agoI would like to know the name of that paper if anyone knows.
- ynfnehf 6y agoIt sounds a lot like Pratt parsing, or at least the way I usually implement it. But I don't what paper he is referring to.
- lioeters 6y agoI believe he was talking about Pratt parsing in the video. Top Down Operator Precedence - Vaughan R. Pratt - https://tdop.github.io/ https://tdop.github.io/ What he called "priority" is called "binding power" in the paper.
- Leszek 6y agoI like Jonathan Blow and all, but he should be careful with trashing academic parsing theory if he thinks that Pratt parsing was only discovered "in the last few years".