Live data from Hacker News

Top Down Operator Precedence (1973)

tdop.github.io

11–20 of 20 posts

Re: Top Down Operator Precedence (1973)

#11

I 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

It took me a number of readings before I figured it out, back in the day. I summarized my understanding in http://eli.thegreenplace.net/2010/01/02/top-down-operator-pr... -- hope it's helpful

Re: Top Down Operator Precedence (1973)

#13

The 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.

There seem to be a number of places where you've changed hyphens to em-dashes. (E.g.: "This argument is independent of whether we specify program control explicitly, as in Algol—like languages, or implicitly, as in Planner—Conniver-like languages.") It's a bit confusing to read. Would you possibly mind fixing this? Thank you!

Re: Top Down Operator Precedence (1973)

#14
post #5

Worth 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.

Wrong post?

Re: Top Down Operator Precedence (1973)

#15

Earlier quoted context omitted.

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.

Wrong post?

Just a strong digression. It's sadly common to have badly recorded talks which is surprising considering the era.

Re: Top Down Operator Precedence (1973)

#16
post #12

Why not hard-code the operator precedence into the BNF? Like the K&R book does it.

If you're using something that generates a parser for you—like bison or yacc—then sure, you can express your grammar like that, and there are advantages to doing so. On the other hand, if you don't have something like that available—say, you're working in a language where nobody has written a yacc clone yet, so there's no way for you to generate a parser from a BNF description—then implementing a Pratt parser is a lot easier than implementing a parser generator.

Even if you have alternatives, there are still situations in which you might want to use a Pratt parser. It's much easier to understand the internals of this kind of parser than understand the shift/reduce rules of an LL(k) grammar, and Pratt parsers have the nice property that you can easily modify them at runtime, making it easy to switch to alternate grammars in particular contexts—e.g., directly parsing SQL within particular delimiters is a pretty trivial task that is somewhat more difficult with a BNF-style grammar.

EDIT: Actually, a better final example would be user-defined operators with arbitrary precedence and branching. There is no way of expressing this directly in a BNF-style grammar, but it is trivial with a Pratt parser.

Re: Top Down Operator Precedence (1973)

#17

Earlier quoted context omitted.

Wrong post?

Just a strong digression. It's sadly common to have badly recorded talks which is surprising considering the era.

Yeah, it doesn't help that conference organizers tend to discourage the audience from doing their own recordings.

Re: Top Down Operator Precedence (1973)

#18
post #17

Earlier quoted context omitted.

Just a strong digression. It's sadly common to have badly recorded talks which is surprising considering the era.

Yeah, it doesn't help that conference organizers tend to discourage the audience from doing their own recordings.

Why is that ? Copyrights or syndicated revenue ? Professional conference recording seems quite pricey[1]. Maybe there can be a middle ground solution.

[1] There's a crowdfunding to help pay for some lambda talks, it was around 15k. I don't know the details though, if it's for many days in many rooms

Re: Top Down Operator Precedence (1973)

#19

The 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.

There seem to be a number of places where you've changed hyphens to em-dashes. (E.g.: "This argument is independent of whether we specify program control explicitly, as in Algol—like languages, or implicitly, as in Planner—Conniver-like languages.") It's a bit confusing to read. Would you possibly mind fixing this? Thank you!

I collected up a number of nits like this, plus some more meaningful transcription errors, into a branch, and have sent a pull request: https://github.com/tdop/tdop.github.io/pull/2

Re: Top Down Operator Precedence (1973)

#20
post #11

I 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

It took me a number of readings before I figured it out, back in the day. I summarized my understanding in http://eli.thegreenplace.net/2010/01/02/top-down-operator-pr... -- hope it's helpful

I found http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-e... really useful as well.
Post reply on HN