thurston

Sorry I didn't see the parent you were responding too, so my point is actually the same as you already made. Thanks.

Ragel has the advantage that CPU blowups happen at compile time, rather than run-time. Other risks aside, they would have avoided this problem had they been using ragel or something similar to pre-compile their patterns into deterministic machines.

What rarely gets discussed in this case was that old, working code was modified in a critical way in order to accommodate new code when that didn't need to be done at all. It was actually a failure in the software development process.

Initial list:

C, C++, Objective-C, Objective-C++, ASM, Crack, C#, D, Go, Java, JavaScript, Julia, OCaml, Ruby, Rust

Others can be added.

Well doing that would mean ragel would incorrectly read one character, rather than run off forever. Personally I'd rather have the latter. Much easier to catch with memory checkers. Eventually you try to read some thing you're not allowed to read, or blow something else up, instead of just read the first byte of the int following the buffer, or whatever.

There would have to be an additional bounds check when issuing a goto in an error action, but doing that is contrary to the simple execution model that ragel users have come to rely on.

Gotta ask the question, where was the testing when they altered 7 year old code without the involvement of the original developer?

Author of Ragel here.

An experienced Ragel programmer would know that when you start setting the EOF pointer you are enabling code paths that never executed before. Like, potentially buggy ones. Eek!

Thanks!

WRT Lua, not at this time, but it is one I would like to support. Won't be too much work to add it.

Keep using them is how you overcome this ;)

At their core they target different language classes. Ragel deals with regular, whereas LPeg deals with context-free grammars.

My pleasure, thank you for the note!

Not at this time. But yes Ragel 7 will make it much easier. The first round of new languages I added helped me polish the technique. Once 7 is out and vetted it will make sense to add more.

Same reason you would want to use yacc to write a parser. A grammar annotated with code is a nice way to express a parser. If the language happens to be regular, you can use ragel to generate a directly executable deterministic state machine. The code is simple and fast.

Ragel allows embedding actions into the subexpressions of a regular expression. This allows one to compose a parser using a single regular expression.

help me!

http://www.complang.org/dsnp/

Just plain old text as it came in. I see now that is not what you were referring to. You're talking about JSON, XML, etc I now think.

There is also a print_xml function, which puts the tree into XML, but it's mostly used for debugging at this point, not export to other systems. I'm hoping that with time these kinds of features will crop up.

They are related systems. DMS is much more mature.

Ya it's currently hard to find. 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.

Indeed I did not follow what you meant. I missed the "persistent" and saw ... "don't incur the cost of copying." I took that to mean that you were referring to not maintaining any history and using a single, mutable global state. It is with that understanding that I made the previous comment.

To address what you meant ... it's more a matter of what's practical. For example, to parse C++ one needs to do quite a bit of semantic analysis during parsing. A full implementation of the type system is necessary. Then the data structures change with every statement/clause parsed. Achieving this with persistent data structures is far too costly.

Yes I understand these techniques, in fact they are heavily in use in Colm, just not for maintaining the global state that is used for the parsing feedback loop.

I use the term "copy" in the general sense to make discussion easier. Conceptually, persistent data structures are a copy, even if they are optimized heavily to incur very little cost.

:) If I had my way this comment would be closer to the top. Not many grammar-based parsing systems can claim raw DNS parsing.

Colm has built-in serialization. There is still some work to do in this area though. Colm will preserve whitespace for minimal disruption of untransformed text, but figuring out what to do at the boundaries between modified and unmodified trees can be tricky.

You are right, people want to use general purpose languages for the more complex algorithms. I agree a means of embedding is necessary and I have kept this in mind, though not yet achieved it. I would very much like to be able to parse, transform, then have the option to import the data into another environment and carry on there.

To have both generalized parsing and context dependent parsing you need to somehow revert changes to the global state when you backtrack. You can do this by restoring it to old versions, which requires copying the state and keeping the history. The Colm approach is to keep only one global state, but store instructions for programmatically reverting the state while you backtrack.

Then you forgo generalized parsing.

Edit: indeed I did not follow what you meant.

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

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

If they are then I don't deserve to be called "Dr. Thurston!"

Grammar: http://svn.complang.org/colm/trunk/colm/lmparse.kl

That's not in the trunk yet ... it is queued.

There is also C#. It's been in testing for a while and there are a few known bugs. Should get worked out in the next release.

That's right. That patch is waiting to go out. Unfortunately I didn't get a release out in 2010. By spring I'm hoping to have one. It got stalled because I was trying to include a revamp of conditions and I got hung up wrestling with the complexity of that problem. I now know what I'm dealing with and my plan is to push out a 6.7 with all the submitted patches, then later on do 7.0 with the new condition stuff. It's gonna be awesome :)

I've also been distracted by another project, which is also going to be awesome :)