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

Parsing: The Solved Problem That Isn't (2011)

tratt.net

Post reply on HN
Print view View original

31–40 of 71 posts

Re: Parsing: The Solved Problem That Isn't (2011)

#31

Post by sandal »

girvo wrote: post #20

This is probably a good place to ask; I've wanted to build a language myself -- whats the best place to begin learning about parsers and the like? About a decade ago I asked this question and was told to read the "Dragon book" but I was far too young and lacked experience. Now I really want to get stuck into something outside of my day-to-day web stuff.

If you want to just see an example of building a parser, you could check out "Parsing JSON the hard way", which uses Racc:

https://practicingruby.com/articles/parsing-json-the-hard-wa...

Re: Parsing: The Solved Problem That Isn't (2011)

#32

Post by Dewie »

girvo wrote: post #20

This is probably a good place to ask; I've wanted to build a language myself -- whats the best place to begin learning about parsers and the like? About a decade ago I asked this question and was told to read the "Dragon book" but I was far too young and lacked experience. Now I really want to get stuck into something outside of my day-to-day web stuff.

The dragon book (at least the first edition) has 330 pages on parsing. 330 pages. IMO that is excessive for a beginner, given how relatively easy it is to implement a parser for a fairly standard language.

Re: Parsing: The Solved Problem That Isn't (2011)

#33

Post by keithrel »

girvo wrote: post #20

This is probably a good place to ask; I've wanted to build a language myself -- whats the best place to begin learning about parsers and the like? About a decade ago I asked this question and was told to read the "Dragon book" but I was far too young and lacked experience. Now I really want to get stuck into something outside of my day-to-day web stuff.

Just start writing the parser/compiler/interpreter for your language, today. You will quickly learn what you need, tokenizer/lexer, some way to represent the AST, how to represent types (if you have any), etc. Later start looking at the literature to see how "its really done". I find this approach takes more time perhaps but I have a much better appreciation for what I am reading afterwards (Oh that's why they did X!).

Re: Parsing: The Solved Problem That Isn't (2011)

#34

Post by sklogic »

girvo wrote: post #20

This is probably a good place to ask; I've wanted to build a language myself -- whats the best place to begin learning about parsers and the like? About a decade ago I asked this question and was told to read the "Dragon book" but I was far too young and lacked experience. Now I really want to get stuck into something outside of my day-to-day web stuff.

You may also want to take a look at this one: http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-e...

Re: Parsing: The Solved Problem That Isn't (2011)

#35

Post by sklogic »

How exactly "PEGs are rather inexpressive"? Still the same BNF, with some nice bells and whistles added. As for the left recursion, it's not a big deal. You mostly need left recursion for the binary expressions, and they are much better served by a Pratt parsing (which is trivial to mix with Packrat anyway).

I moved to PEG+Pratt exclusively and never needed anything beyond that, for even craziest grammars imaginable.

Re: Parsing: The Solved Problem That Isn't (2011)

#36

Post by jbangert »

sklogic wrote: post #35

How exactly "PEGs are rather inexpressive"? Still the same BNF, with some nice bells and whistles added. As for the left recursion, it's not a big deal. You mostly need left recursion for the binary expressions, and they are much better served by a Pratt parsing (which is trivial to mix with Packrat anyway). I moved to PEG+Pratt exclusively and never needed anything beyond that, for even craziest grammars imaginable.

One issue with PEG's (and other parsers) is that it doesn't address (unbounded) count fields (or bounded count fields in an elegant manner) or offsets. This means a pure PEG can't express e.g. PDF or ZIP files. To address this, we built a PEG-based parser generator with a few new features, Nail (paper at OSDI 14, github.com/jbangert/nail)

Re: Parsing: The Solved Problem That Isn't (2011)

#37

Post by c3d »

The XL programming language (http://xlr.sf.net) has a rather unique approach to parsing. There is a short article about it here: http://grenouille-bouillie.blogspot.fr/2010/06/xl-axioms-rec....

XL features 8 simple node types, 4 leafs (integer, real, text, name/symbol) and 4 inner nodes (infix, prefix, postfix and block). With that, you can use a rather standard looking syntax, yet have an inner parse tree structure that is practically as simple as Lisp. The scanner and parser together represent 1800 lines of C++ code with comments. In other words, with such a short parser, you have a language that reads like Python but has an abstract syntax tree that is barely more complicated than Lisp.

It's also the basis for the Tao 3D document description language used at Taodyne, so the approach has demonstrated its ability to work in an industrial project.

Re: Parsing: The Solved Problem That Isn't (2011)

#38

Post by jblow »

It is nice to see someone summarizing this kind of information. However, really this is a continuation of the academic attitude toward parsers making them MUCH harder than they have to be.

If you want to study grammars in an abstract sense, then think of them this way, and that's fine. If you want to build a parser for a programming language, don't use any of this stuff. Just write code to parse the language in a straightforward way. You'll get a lot more done and the resulting system will be much nicer for you and your users.

Re: Parsing: The Solved Problem That Isn't (2011)

#39

Post by hardmath123 »

falsedan wrote: post #9

Jeffrey Kegler's work on Marpa is pretty exciting, but hasn't got much traction (maybe due to the implementation languages: Perl and Knuth's Literate Programming). https://metacpan.org/pod/Marpa::R2#A-simple-calculator

Yeah, Marpa is quite amazing—it inspired me to build nearley. It's probably more powerful than any other parser generator out there right now (and the fastest, because it has Leo optimizations and Aycock-Horsepool nullables). In fact, Kegler responded to this same article with http://jeffreykegler.github.io/Ocean-of-Awareness-blog/indiv...

Re: Parsing: The Solved Problem That Isn't (2011)

#40

Post by rabarbers »

girvo wrote: post #20

This is probably a good place to ask; I've wanted to build a language myself -- whats the best place to begin learning about parsers and the like? About a decade ago I asked this question and was told to read the "Dragon book" but I was far too young and lacked experience. Now I really want to get stuck into something outside of my day-to-day web stuff.

I started with udacity course: https://www.udacity.com/course/cs262 it teached how to build simple javascript parser.
Post reply on HN