8 ms·
Colm programming language released: best parser-writer ever
- bdfh42 15y agoQuote "Colm does not yet have any documentation". Then I would hazard that it is not yet a language as without documentation it has no "grammar". At best it is a patois.
- thurston 15y agoGrammar: http://svn.complang.org/colm/trunk/colm/lmparse.kl http://svn.complang.org/colm/trunk/colm/lmparse.kl
- scscsc 15y agoThere seems to be a PhD thesis behind, so you should check it for the grammar.
- wzdd 15y agoTXL, its apparently predecessor, is very well documented (http://www.txl.ca/ http://www.txl.ca/). TXL is a very interesting approach to parsing and worth reading up on if you're interested in the area (or are waiting for documentation for Colm :)
- colomon 15y agoIt would be interesting to see someone who understood both this and Perl 6's grammars to do a comparison. Based on Colm's quick description and my rough understanding of Perl 6 grammars, they sound like they are roughly equally powerful. But I admit I'm not sure I understand what "transformation language" means...
- thurston 15y agoIf they are then I don't deserve to be called "Dr. Thurston!"
- deleted 15y ago[deleted]
- audreyt 15y agoInterestingly, I parsed thurston's response not as an appeal to authority, but as self-mocking humor (i.e. "wow, if Perl 6 does that too, maybe my PhD was unwarranted!"). I guess English parsing is non-deterministic too... :-)
- anigbrowl 15y agoGood grief. Have a sense of humor; the grandparent response was obviously made with tongue firmly in cheek.
- deleted 15y ago[deleted]
- audreyt 15y agoAlthough similar in expressive power, Colm offers instruction logging to auto-reverse global state changes upon backtracking, something Perl 6 grammars does not (yet) support; at the moment we need to manually manage them with embedded blocks.
- colomon 15y agoThanks!
- chocolateboy 15y agoRe: "reverse global state changes upon backtracking": this sounds similar to the (manual) "undo actions" supported by the Kelbt parser [1], perhaps unsurprisingly as it was developed by the same author :-) [1] http://www.complang.org/kelbt/ http://www.complang.org/kelbt/
- jws 15y agoNotice that the DNS example is parsing a binary DNS request, not a text file.
- thurston 15y ago:) If I had my way this comment would be closer to the top. Not many grammar-based parsing systems can claim raw DNS parsing.
- DrCatbox 15y agoI am more interested in DSNP, how come this project has not received more fame than the infamous Disapora? http://www.complang.org/dsnp/ http://www.complang.org/dsnp/
- thurston 15y agoThere are some difficult problems in that space. I've posted to HN and reddit a few times, but mostly I've been working on it quietly so I can focus. Lately, that's starting to change. I'll be talking about it at FSW 11 in Berlin in a few weeks.
- DrCatbox 15y agoMy google sense failed me this time around to find information on this FSW 11 in Berlin. Care to explain? Is it a conference, can anybody come? I am really interested in DSNP and am fairly well versed in GNU/Linux and can do some programming, Java and Python mostly. I work as a web-frontend developer guy. Can I be of some help? Do you need testers, peers, documenters?
- thurston 15y agoYa it's currently hard to find. http://d-cent.org/fsw2011/ http://d-cent.org/fsw2011/ I need help from people like you actually. What I've done. 1. defined the protocol 2. implmented it in a C++ daemon that a) talks to other daemons b) serves the content managers (frontend UIs) 3. written a (crappy) example content manager. What needs to happen next is step 3 needs to be repeated by other people who know what they are doing. They don't need to understand the details of the protocol, they just need to understand the basic model, which is just message broadcast, distributed agreement, etc. Email me for more details, will get back to you later tonight.
- ScottBurson 15y agoThurston claims that no previous grammar system supports his three requirements of generalized parsing, grammar-dependent scanning, and context-dependent parsing. I would argue that Prolog Definite Clause Grammars, which date back to the early 1970s, have all three of these properties. Furthermore, since the context is maintained functionally, by threading additional values through the productions, no "undo actions" are required; Prolog's built-in backtracking is all that's needed. Of course, the problem with DCGs is performance: they're exponential in the worst case. But I think they deserve mention in a dissertation like this anyway. Also, any backtracking parser risks exponential worst-case performance; it will be interesting to see how Colm avoids this fate (I've only read the first few pages yet).
- thurston 15y agoWhere is the grammar-dependent scanning? Note that threading the context through the parse tree while maintaining fully generalized parsing requires keeping all versions of the parsing context in memory. Consider making a C++ parser in that way ... ie every time you modify the structures you build in memory you make a copy of them first.
- swannodette 15y agoIf your data structures are persistent data structures you don't incur the costs of copying.
- thurston 15y agoThen you forgo generalized parsing. Edit: indeed I did not follow what you meant.
- swannodette 15y agoI don't follow.
- 15y ago
- haberman 15y agoFrom my quick scan of the thesis, the basic design seems to be a programming language in which you write both the parser and any transformations you want to perform. It's not clear whether there is an easily-accessible parse tree serialization that you can use to load the output into another language, or whether you'd have to invent that yourself. I think it's generally a hard sell if you try to convince people that they need to write their algorithms in your special language. Parsing tools deliver value because grammars are easier to write than the imperative code that implements those grammars. That value offsets the cost of having to learn a new special-purpose language. But imperative programming languages are already pretty good at tree traversal and transformation, so there's little benefit to using a special-purpose language for this. I think that the next big thing in parsing will be a runtime that easily integrates into other languages so that the parsing framework can handle only the parsing and all of the tree traversal and transformation can be performed using whatever language the programmer was already using. This requires much less buy-in to a special-purpose language.
- beza1e1 15y agoAntLR can do this, although it does not work that well. I used the C backend, which is pretty directly ported from the Java backend. C-in-Java-style is pretty awkward.
- haberman 15y agoANTLR is not the same as what I am describing. ANTLR generates code in each target language: I am talking about a common runtime that all languages call into. Think of it as a "parsing VM." Using this scheme, there would be no need to have separate backends for C and Java, the only thing you'd need to port is the bindings.
- beza1e1 15y agoWhy would that be a good idea? What advantage would a just-in-time parser generator have that a static parser generator does not?
- Barrasmara 15y agoThis kind of sounds like Semantic Design's DMS software Reengineering toolkit and the Parlanse language.
- thurston 15y agoThey are related systems. DMS is much more mature.
- Twisol 15y agoAdrian Thurston (the creator of Colm) is also responsible for the fantastic Ragel state machine generator.