Top Down Operator Precedence (1973)
tdop.github.io
Top Down Operator Precedence (1973)
1–10 of 20 posts
Re: Top Down Operator Precedence (1973)
#2The only copy I could find was a PDF that contained images of the original paper, literally printed on paper. It seemed worth redoing and putting online properly.
I've tried not to change anything beyond the typography, but it's tricky to get perfect. It's on GitHub, so feel free to chip in.
Re: Top Down Operator Precedence (1973)
#3I read through the whole thing, but there's something about the writing style which I think makes it rather difficult to follow; even the Dragon Book was more straightforward.
If I'm not mistaken, this article describes the same thing, and it was far easier to read:
Re: Top Down Operator Precedence (1973)
#4I love the idea of remastering old papers for the web. While SVG and MathJax allow to easily include diagrams and math, this work shows that you can get away with using only Unicode.
To make the most of the capabilities of HTML, I would have made citations hoverable, so a tooltip can show the reference next to it without the need to go to the bottom.
Re: Top Down Operator Precedence (1973)
#5Worth noting is Doug Crockford's TDOP parser implementation in JavaScript, it's quite elegant: https://github.com/douglascrockford/TDOP/
As well as his accompanying talk, titled Syntaxation: https://www.youtube.com/watch?v=9e_oEE72d3U (sadly, the recording has gaps and is generally horrible; as far as I know he gave the talk only once).
Crockford's talk led me to the original paper and together they really expanded my horizon on how to make maintainable parsing engines. Thanks for putting in the effort and making it more accessible!
Re: Top Down Operator Precedence (1973)
#6Worth noting is Doug Crockford's TDOP parser implementation in JavaScript, it's quite elegant: https://github.com/douglascrockford/TDOP/ As well as his accompanying talk, titled Syntaxation: https://www.youtube.com/watch?v=9e_oEE72d3U (sadly, the recording has gaps and is generally horrible; as far as I know he gave the talk only once). Crockford's talk led me to the original paper and together they really expanded m…
Surprisingly, when people can shoot movies with their iPhones, we have nothing to help here. I'd love to see something similar to super-resolution, merging multiples audio sources into a 'higher' res one. And temporal markov graph-cut, to fill gaps as much as possible.
Re: Top Down Operator Precedence (1973)
#7I have used TDOP and made variations of it before (e.g. combining TDOP and PEG, as well as introducing a form sub-grammars, like what you get with CFGs). I could also see the similarity between TDOP and left corner parsing, which gave me a better grounding on it.
Still never really felt like I deeply understood it. I think there was some intuitive leap I just wasn't making. A lot of it had to do with the choice of left/right binding powers, and loop that does the comparison and chooses whether to keep extending or to "dive down" into a new sub-tree.
Perhaps if there was a slightly different formulation, or something that was just a plain obvious description or methodology for getting the numbers right I would finally get it.
Re: Top Down Operator Precedence (1973)
#8I read through the whole thing, but there's something about the writing style which I think makes it rather difficult to follow; even the Dragon Book was more straightforward. If I'm not mistaken, this article describes the same thing, and it was far easier to read: https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm
Talking about the shunting yard algorithm, it's funny how often trains and railroads have inspired programming concepts. Parsing, concurrency and recently Scott Wlaschin describe monads through railways http://fsharpforfunandprofit.com/posts/recipe-part2/.
ps: while searching for Wlaschin talk I stumbled upon that https://www.google.com/search?q=monad+railway+equipment #rimshot
Re: Top Down Operator Precedence (1973)
#9I read through the whole thing, but there's something about the writing style which I think makes it rather difficult to follow; even the Dragon Book was more straightforward. If I'm not mistaken, this article describes the same thing, and it was far easier to read: https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm
The Pratt/TDOP scheme is a decentralized or OO way to organize the same idea. I coded them both, at https://github.com/darius/sketchbook/blob/master/parsing/pre... and https://github.com/darius/sketchbook/blob/master/parsing/pra...
(My Pratt is smaller than my precedence-climbing here because I ended up actually using the latter, so it got some extras added.)
Re: Top Down Operator Precedence (1973)
#10The only copy I could find was a PDF that contained images of the original paper, literally printed on paper. It seemed worth redoing and putting online properly. I've tried not to change anything beyond the typography, but it's tricky to get perfect. It's on GitHub, so feel free to chip in.
Can you link to the scanned PDF and your GitHub repo? I've noticed a few places with mismatched brackets, such as "(....]", and wanted to check to see if they were mismatched in the original or if that's just a transcription error.
edit: Found the original at http://hall.org.ua/halls/wizzard/pdf/vaughan.pratt.tdop.pdf and your repo at https://github.com/tdop/tdop.github.io. Am reading the paper now, it's not one that I'd read before so thanks for posting it, and will send a pull request with suggested fixes when I'm done.