Packrat Parsing: Simple, Powerful, Lazy, Linear Time [pdf] • Hacker News Board

Re: Packrat Parsing: Simple, Powerful, Lazy, Linear Time [pdf]

#21

Post by svat » Mon, Nov 16, 2020, 3:19 AM UTC

Syzygies wrote: post #19

Conservation of genius. Nice paper. Two columns. Why? In the 1980's computer science conferences like STOC and FOCS would hand out telephone-book sized proceedings, and it took two columns to squeeze it all in. Not relevant now, but the two columns make it that much harder to read on a tablet. I don't generally wish ill on anyone, but it's hard not to wish that the editors responsible for this idiotic convention woul…

Consider using k2pdfopt or some such tool.

Also, this paper is from ICFP 2002 whose proceedings were published in print form. Several libraries hold it: https://www.worldcat.org/title/proceedings-of-the-seventh-ac...

Anyway it appears that from 2017 onwards the ICFP proceedings are no longer published in print (they're published as part of PACMPL, an electronic journal), and indeed the ICFP 2020 papers for example (https://dl.acm.org/toc/pacmpl/2020/4/ICFP) are not in two columns anymore. So everything seems reasonable IMO.

Re: Packrat Parsing: Simple, Powerful, Lazy, Linear Time [pdf]

#22

Post by drmeister » Mon, Nov 16, 2020, 3:55 AM UTC

I use the esrap packrat parser in Common Lisp for computational chemistry file formats. I've written half a dozen parsers with it and had a few written for me by others. They are easy to write and easy to maintain - even when I don't look at them for a couple of years. I am happy to not have yacc and bison in my life anymore (no offense intended).

Re: Packrat Parsing: Simple, Powerful, Lazy, Linear Time [pdf]

#23

Post by teleforce » Mon, Nov 16, 2020, 4:13 AM UTC

This is an excellent Packrat parser library in the D language:

https://github.com/PhilippeSigaud/Pegged

If you want to understand the compile-time techniques available in D language that are being used by the Pegged library this is a handy guide:

https://wiki.dlang.org/User:Quickfur/Compile-time_vs._compil...

Re: Packrat Parsing: Simple, Powerful, Lazy, Linear Time [pdf]

#24

Post by bjoli » Mon, Nov 16, 2020, 8:20 AM UTC

espadrine wrote: post #16

amboo7 wrote: post #11

Latest developments: https://arxiv.org/abs/2005.06444

It is an interesting principle. If I am reading the page 20 graphs, though, the parsing time gets crushed by the competition when parsing programming languages (Java, in the example). It is only competitive for simple grammars. Beyond that, I feel like recursive descent parsers are the PostgreSQL of parsing: they are not exciting, but they get the job done well without fail. The rare cases where you need something el…

If you have a language that does TCO recursive descent parsers are fantastic to write. I wrote a JSON parser in guile scheme that was fast enough for My purposes in about 170 LOC.

It was extremely simple. No state variables, each function was its own state. The only place where there was any call stack buildup was of course in nested arrays/hashes, but guile doesn't do stack overflows, just out of memory, so that was less of an issue.

Re: Packrat Parsing: Simple, Powerful, Lazy, Linear Time [pdf]

#25

Post by gjvc » Mon, Nov 16, 2020, 11:36 AM UTC

Syzygies wrote: post #19

Conservation of genius. Nice paper. Two columns. Why? In the 1980's computer science conferences like STOC and FOCS would hand out telephone-book sized proceedings, and it took two columns to squeeze it all in. Not relevant now, but the two columns make it that much harder to read on a tablet. I don't generally wish ill on anyone, but it's hard not to wish that the editors responsible for this idiotic convention woul…

Narrow columns are easier to mark up with a pen for editing and note-making purposes.

On the other hand, I have often wondered why this convention was used so much, especially when some types of content would never reasonably fit into a single column (and people didn't want to float a graphic in there)

What sort of tablet are you using in 2020 which doesn't have the pinch-to-zoom functionality?

"two columns to squeeze it all in" Just use a single column and half the pages then...