10 ms·
Parsing: The Solved Problem That Isn't (2011)
- jeffreyrogers 12y agoThis is a really interesting post. The same author recently posted another article that discusses some of the ideas from the conclusion of this post. You can find that article here: http://tratt.net/laurie/blog/entries/an_editor_for_composed_programs http://tratt.net/laurie/blog/entries/an_editor_for_composed_...
- dkarapetyan 12y agoThe more generic term for a lot of the stuff he talks about in that post falls under projectional editors and programming language workbenches. JetBrains MPS is one of the tools among many that help with building such editors. Here's a good talk by Markus Völter on using tools like JetBrains MPS.
- timdumol 12y agoI think you forgot to put in the link :)
- dkarapetyan 12y agohttp://www.infoq.com/presentations/tools-language-workbench http://www.infoq.com/presentations/tools-language-workbench
- sparkie 12y ago"The more generic term" is really a term that was re-invented by Fowler, who is no stranger to inventing new terms for old concepts. Syntax Directed Editor is a much older term.
- girvo 12y agoThis 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.
- jbzz 12y agoParsing Techniques by Dick Grune is THE bible for parsing.
- dkarapetyan 12y agoIt is a nice reference but you won't learn anything from that if you're a beginner. It's super heavy on theory and very light on implementation.
- thesz 12y agoI think you get it backwards. I learned a lot and PTAPG introduction specifically says that it avoids heavy theory. It has all algorithms required in very understandable presentation. It also says what this or that algorithm does to exploit that or this feature from grammar structure.
- dkarapetyan 12y agoStart here: http://nathansuniversity.com/ http://nathansuniversity.com/. All the stuff in the dragon book is designed for limited memory and limited computing capability environments. There is no reason to worry about LL(k) parse table size or predict and follow sets when you don't have to. For most practical purposes you can get away with basic recursive descent or PEG parsers. The link I pointed you to starts with peg.js which is PEG parser generator in JavaScript. If you get through PL101 then picking up the stuff in the dragon book or any other book on parsing and compiling technology will be much easier. Another resource I like is "Compiler Design: Virtual Machines" (http://smile.amazon.com/Compiler-Design-Machines-Reinhard-Wilhelm/dp/3642149081 http://smile.amazon.com/Compiler-Design-Machines-Reinhard-Wi...). Still going through that one but it is very readable and if you go through PL101 then you'll have all the tools to implement the virtual machines described in that book. It is much easier to write a compiler to target machine code or some other language like C when you've built a few targets yourself and understand the trade-offs involved. There's also http://www.greatcodeclub.com/ http://www.greatcodeclub.com/. I think one of the projects is a simple virtual machine and another one is a compiler. Well worth the admission price if you're a beginner and want some help getting started. Hanselman's rule about finiteness of keystrokes applies and I recently wrote some notes about budding PL enthusiasts: http://www.scriptcrafty.com/tips-for-the-budding-pl-enthusiast/ http://www.scriptcrafty.com/tips-for-the-budding-pl-enthusia....
- wslh 12y agoI just found this "old" article looking for an easy to use parser in C++ (in Visual Studio, GCC, and CLang). I think the current state of parsers in C++ is... how to say it... terrible! flex and bison doesn't look like C++, Boost Spirit too much ado, ANTLR4 doesn't support it yet and setting up ANTLR3 in Visual Studio can be explained in a few steps if it were explained in a straightforward way. When you look at the simplicity of OMeta[1] you feel the difference. But I am not aware of any (production ready) OMeta implementation for C++. [1] http://tinlizzie.org/ometa/ http://tinlizzie.org/ometa/
- stormbrew 12y agoIf you don't mind incredibly long compile times for any moderately complex grammar, PEGTL is pretty straightforward compared to other alternatives.
- tjaerv 12y agohttp://code.google.com/p/pegtl/ http://code.google.com/p/pegtl/
- muyuu 12y agoBoth are based in Bryan Ford's packrat (PEG is Ford's too). OMeta is more like PEGTL in that it's a set of facilities/library at a highish level, more than a particular grammar system (they're all packrat parsers). http://bford.info/packrat/ http://bford.info/packrat/ It's all about descent parsing and memoisation (thus the name).
- stormbrew 12y agopegtl is not actually a packrat parser. Not all PEGs and absolutely not all recursive descent parsers are packrats. And actually, my experience with packrat parsers (mostly in ruby) in other languages has been that they actually slow things down on moderately or more complex grammars by massively exploding memory use and thus allocation pressures. Turning it off can make it faster, especially on complex grammars. It's a pretty good case study in how optimizing an O(n^2) worst case to O(n) does not always improve things. That said, I'm not against the principle, but the shotgun approach to it can be brutally bad. You really only want to memoize the paths that are actually likely to backtrack. Or simple grammars where O(n^2) memory use is not going to balloon your memory use too much it's a clear win.
- logicalshift 12y agoMy day job used to involve parsing some fairly ill-formed languages, so I developed this: https://github.com/Logicalshift/TameParse https://github.com/Logicalshift/TameParse I noticed with the languages I was working on, the problems could be resolved by being smarter with the lookahead: this parser allows for context-free lookahead matching to resolve (or detect and defer) ambiguities. That makes it possible to do neat things like parse C snippets without full type information or deal with keywords that aren't always keywords (eg, await in C#).
- sshine 12y agoI've wondered why most existing LALR(1) parser generators are not replaced with LR parser generators with a higher look-ahead than 1. This improvement, considering that our computational power today does not justify these restrictions any more, would be Pareto-optimal even while it is being decided what completely alternative strategies (PEGs, boolean grammars, parser combinators, etc.) will take over.
- wslh 12y agoANTLR is LL(*).
- dkarapetyan 12y agoRight. It's kinda impressive what it can do. On one end of the spectrum it has all the power of PEGs and on the other it has the predicative capabilities of LL(k) so there is basically no restriction on the kind of grammar it can generate parsers for.
- falsedan 12y agoJeffrey 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 https://metacpan.org/pod/Marpa::R2#A-simple-calculator
- hardmath123 12y agoYeah, 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/individual/2012/08/the-solved-problem-that-isnt-is.html http://jeffreykegler.github.io/Ocean-of-Awareness-blog/indiv...
- ronsavage 12y agoMarpa's homepage: http://savage.net.au/Marpa.html http://savage.net.au/Marpa.html
- reirob 12y agoSeems to be written in C: "Marpa is available as a open-source library. It is written in C, and the C library can be used directly or via a Perl interface." http://jeffreykegler.github.io/Ocean-of-Awareness-blog/individual/2012/08/the-solved-problem-that-isnt-is.html http://jeffreykegler.github.io/Ocean-of-Awareness-blog/indiv...
- schoen 12y agoIt may also relevant to mention the language-theoretic security research program ("LANGSEC"). http://langsec.org/ http://langsec.org/ They've pointed out that the difficulty of parsing, and in a sense our overconfidence that we can just code up parsers for random languages and input formats when we need them, is a pretty pervasive source of security bugs. A lot of those bugs can occur when you have two different parsers that have a different notion of what language they're supposed to recognize, so it's possible to construct an input whose meaning the two parsers disagree on. That can have pretty serious ramifications if, for example, the first parser is deciding whether a requested action is authorized and the second parser is carrying out the action! I'm kind of sad about this because I love whipping up regular expressions to extract data even from things that regular expressions technically can't handle correctly. But there's a good argument to be made that this habit is playing with fire much of the time, at least in systems that will end up handling untrusted input. And the Shellshock bug is a recent example of the way that your intuitions about whether your software will "handle untrusted input" in some use case can go out of date.
- dkarapetyan 12y agoSee also this paper: http://www.ieee-security.org/TC/SPW2014/papers/5103a198.PDF http://www.ieee-security.org/TC/SPW2014/papers/5103a198.PDF. The authors implement a pdf file format parser and find bugs in pretty much all of the existing implementations. Basically pdf is a pretty shitty file format with several ill-defined corner cases. This is one of the reasons PDFs tend to be vectors for security breaches.
- nly 12y agoHow comforting it is that the paper is presented as a PDF ;)
- schoen 12y agoThe lead author (Andreas Bogk) presented an earlier version of this work at the Chaos Communication Camp in 2011 ("Certified Programming With Dependent Types"). http://events.ccc.de/camp/2011/Fahrplan/events/4426.en.html http://events.ccc.de/camp/2011/Fahrplan/events/4426.en.html I went to that talk, and found it to be probably the most advanced and difficult math lecture I'd ever attended! (I was very grateful to see such mathematical sophistication brought to bear to protect PDF users, which is almost all of us.)
- jdnier 12y agoInstaparse, a parsing library for Clojure, tries to make context-free grammars "as easy to use as regular expressions." It uses an EBNF input format that should be familiar to many programmers. https://github.com/Engelberg/instaparse https://github.com/Engelberg/instaparse
- keithflower 12y agoA tool I like in this space is Stephen Chang's Parsack, "a basic Parsec-like monadic parser combinator library implementation in Racket." http://stchang.github.io/parsack/parsack.html http://stchang.github.io/parsack/parsack.html
- sklogic 12y agoHow 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.
- jbangert 12y agoOne 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)
- sklogic 12y agoI like this idea! Mind if I steal it for my PEG generator? This is probably the best property of PEGs, they're extremely extensible and flexible, you can add features not possible in any other parsing technology, including high order parsers, dynamic extensibility, etc.
- sovande 12y agoAnother issue is that it uses at least the same memory as the the input. Not that I'm a PEG expert, but it also basically feels like a formalised recursive decent parser. Nothing wrong with that, but changing the grammar afterwards can have a rippling effect and require much more work than with a traditional LALR parser.
- sklogic 12y agoHow is it so? If you're referring to the Packrat memoisation (which is not the only possible PEG implementation), you can do a lot of memory optimisation, like discarding memoised entries based on some rules (e.g., once a top-level entry, like a function or a class definition is parsed, all the alternative interpretations can be thrown away). You can memoise complex entries but re-parse simple tokens. And many, many more.
- c3d 12y agoThe XL programming language (http://xlr.sf.net 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-reconciling-lisp-and-c.html 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.
- justinpombrio 12y agoJudging from the article, if you parsed "if 3", you'd get back out (prefix if 3) instead of an error, since `if` is just a regular prefix operator. So, presumably there's some sort of well-formedness checking that goes on after parsing? Does anyone know more? The website says very little.
- breuleux 12y agoYeah that puzzles me a bit too. Multifix operators are not more complicated than prefix/postfix/infix (well, only marginally). For instance, you can give each operator a left priority and a right priority and merge them when they meet with the same priority. Then `if x then y else z` would become (if/then/else x y z) or something like that. I think that's saner and easier to handle than what he does.
- justinpombrio 12y agoYeah, that's what I was expecting too. And then XL could claim to have only five node types: integer, real, text, name, and multifix :-)
- jblow 12y agoIt 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.
- wodenokoto 12y agoThat's horrible advice. Some problems are really complex and can't be solved just by working from A to B. Your parser will probably not end up being able to handle the problems outlined in the article unless you take that theory into account before starting to program.
- jblow 12y agoYou never know, you might be talking to someone with actual experience.
- l_dopa 12y agoThis approach might be why several ubiquitous languages have needlessly ambiguous grammars. Decades of writing tools to be bug-compatible with the original implementation is much harder than learning a tiny bit of theory.
- chriswarbo 12y ago> Just write code to parse the language in a straightforward way. This approach is why many consider parsing to be a solved problem, so it's certainly a valid approach. However, it's not the only valid approach. For example, "straightforward" parsers often give terrible error messages: when the intended branch (eg. if/then/else) fails, the parser will backtrack and try a more general alternative (eg. a function call). Not only does this give an incorrect error (eg. "no such function 'esle'"), but it might actually succeed! In which case, the parser will be in the wrong state to parse the following text, and gives a non-sensical message (eg. "unexpected '('" several lines later). This is an important problem, since these messages can only be decyphered by those who know enough about the syntax to avoid hitting them very often! Inexperienced users will see error messages over and over again, and have no idea that they're being asked to fix non-existent errors in incorrect positions.
- parrt 12y agoI should add Adaptive LL(* ), ALL(* ), of ANTLR 4 to the mix here. It handles any grammar you give it and generates a correct parser except for one small caveat: no indirect left-recursion. It's the culimation of 25 years of focused effort to take LL-based parsing to the limit of power while maintaining simplicity and efficiency. See tool shootout in OOPSLA '14 paper I just presented http://www.antlr.org/papers/allstar-techreport.pdf http://www.antlr.org/papers/allstar-techreport.pdf Until we change the requirements of a parser generator, I'm done. :)