What are the arguments against parsing the Cthulhu way?

Question

I have been assigned the task of implementing a Domain Specific Language for a tool that may become quite important for the company. The language is simple but not trivial, it already allows nested loops, string concatenation, etc. and it is practically sure that other constructs will be added as the project advances.

I know by experience that writing a lexer/parser by hand -unless the grammar is trivial- is a time consuming and error prone process. So I was left with two options: a parser generator à la yacc or a combinator library like Parsec. The former was good as well but I picked the latter for various reasons, and implemented the solution in a functional language.

The result is pretty spectacular to my eyes, the code is very concise, elegant and readable/fluent. I concede it may look a bit weird if you never programmed in anything other than java/c#, but then this would be true of anything not written in java/c#.

At some point however, I've been literally attacked by a co-worker. After a quick glance at my screen he declared that the code is uncomprehensible and that I should not reinvent parsing but just use a stack and String.Split like everybody does. He made a lot of noise, and I could not convince him, partially because I've been taken by surprise and had no clear explanation, partially because his opinion was immutable (no pun intended). I even offered to explain him the language, but to no avail.

I'm positive the discussion is going to re-surface in front of management, so I'm preparing some solid arguments.

These are the first few reasons that come to my mind to avoid a String.Split-based solution:

• you need lot of ifs to handle special cases and things quickly spiral out of control
• lots of hardcoded array indexes makes maintenance painful
• extremely difficult to handle things like a function call as a method argument (ex. add( (add a, b), c)
• very difficult to provide meaningful error messages in case of syntax errors (very likely to happen)
• I'm all for simplicity, clarity and avoiding unnecessary smart-cryptic stuff, but I also believe it's a mistake to dumb down every part of the codebase so that even a burger flipper can understand it. It's the same argument I hear for not using interfaces, not adopting separation of concerns, copying-pasting code around, etc. A minimum of technical competence and willingness to learn is required to work on a software project after all. (I won't use this argument as it will probably sound offensive, and starting a war is not going to help anybody)

What are your favorite arguments against parsing the Cthulhu way?*

*of course if you can convince me he's right I'll be perfectly happy as well

Answer 1

The critical difference between the two approaches is, that the one he considers to be the only correct way is imperative and yours is declarative.

• Your approach explicitly declares rules, i.e. the rules of the grammar are (almost) directly encoded in your code, and the parser library automatically transforms raw input into parsed output, while taking care of state and other things that are hard to handle. Your code is written within one single layer of abstraction, which coincides with the problem domain: parsing. It's reasonable to assume parsec's correctness, which means the only room for error here is, that your grammar definition is wrong. But then again you have fully qualified rule objects and they are easily tested in isolation. Also it might be worth noting, that mature parser libraries ship with one important feature: error reporting. Decent error recovery when parsing went wrong is not trivial. As proof, I invoke PHP's parse error, unexpected T_PAAMAYIM_NEKUDOTAYIM :D

• His approach manipulates strings, explicitly maintains state and lifts up the raw input manually to parsed input. You have to write everything yourself, including error reporting. And when something goes wrong, you are totally lost.

The irony consist in that the correctness of a parser written with your approach is relatively easily proven. In his case, it is almost impossible.

There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.

C. A. R. Hoare

Your approach is the simpler one. All it precludes is for him to broaden his horizon a bit. The result of his approach will always be convoluted, no matter how broad your horizon.
To be honest, it sounds to me, that the guy is just an ignorant fool, who is suffering from the blub syndrome, arrogant enough to assume you are wrong and yell at you, if he doesn't understand you.

In the end however, the question is: who is going to have to maintain it? If it's you, then it's your call, no matter what anybody says. If it's going to be him, then there's only two possibilities: Find a way to make him understand the parser library or write an imperative parser for him. I suggest you generate it from your parser structure :D

Answer 2

A parsing expression grammar (such as the Packrat parser approach) or parser combinator isn't reinventing parsing. These are well established techniques in the functional programming world and, in the right hands, it can be more readable than the alternatives. I've seen a pretty convincing demonstration of PEG in C# a few years back that would actually make it my tool of first resort for relatively simple grammars.

If you have an elegant solution using parser combinators or a PEG, it should be a relatively easy sell: it's fairly extensible, usually relatively easy to read once you get over your fear of functional programming, and is sometimes easier to read than typical parser generator tools offer, though that depends very much on the grammar and the level of experience you have with either toolset. It's also pretty easy to write tests for. Of course, there are some grammar ambiguities that can result in pretty awful parsing performance in worst case scenarios (or lots of memory consumption with Packrat), but average case is pretty decent and actually some grammar ambiguities are better handled with PEG than LALR, as I recall.

Using Split and a stack works with some simpler grammars than a PEG or can support, but it's highly likely that over time you'll either be reinventing recursive descent badly, or you'll have a flaky set of behaviors that you'll band-aid into submission at the cost of extremely unstructured code. If you only have simple tokenization rules it's probably not so bad, but as you add complexity, it will probably be the least maintainable solution. I'd reach for a parser generator instead.

Personally, my first inclination when I need to build a DSL would be to use something like Boo (.Net) or Groovy (JVM), since I get all of the strength of an existing programming language and incredible customizability by building macros and simple adjustments to the compiler pipeline, without having to implement the tedious stuff that I'd end up doing if I started from zero (loops, variables, object model, etc.). If I were in a shop doing Ruby or Lisp development, I'd just use the idioms that make sense there (metaprogramming, etc.)

But I suspect your real issue is either about culture or egos. Are you sure your coworker wouldn't equally have freaked out if you had used Antlr or Flex/Bison? I suspect that "arguing" for your solution may be a losing battle; you may need to spend more time doing a softer approach that uses consensus building techniques rather than appealing to your local management authority. Pair programming, and demonstrating how quickly you can turn out adjustments to the grammar without sacrificing maintainability, and doing a brownbag to explain the technique, its history, and so on, may go further than 10 bullet points and a "rude Q&A" at some confrontational meeting.

Answer 3

I am not well versed in parsing algorithms and the like, but I think the proof of the pudding is in the eating. So if all else fails, you could offer him to implement the parser his way. Then

• compare the time invested in either solutions,
• run both solutions through a comprehensive acceptance test to see which has less bugs, and
• have an independent judge compare the resulting code in size and clarity to yours.

For the testing to be really fair, you might want to have both solutions implement the same API, and use a common testbed (or a unit testing framework known by both of you). Both of you could write any number and kind of functional test cases and ensure that his own solution passes all of them. And of course, ideally neither of you should have access to the other's implementation before the deadline. The decisive test would then be to cross-test both solutions using the test suite developed by the other developer.

Answer 4

You have asked this as if you have a technical question, but as you probably already knew, there is no technical question here. Your approach is vastly superior to hacking something up at the character level.

The real problem is that your (presumably more experienced) colleague is insecure, and feels threatened by your knowledge. You will not persuade him with technical arguments; that will just make him more defensive. Instead you will have to find some way to alleviate his fears. I can't offer many suggestions, but you might try showing high regard for his knowledge of the legacy code.

Finally, if your manager agrees with his specious technical arguments and discards your solution, then I think you are going to have to look for another position. Clearly you would be more valuable, and more highly valued, in a more sophisticated organization.

Answer 5

I'll be brief:

Parsing the Cthulhu way is hard. That's the simplest and most convincing argument against it.

It can do the trick for simple languages; say, regular languages. It's probably won't be easier than a regular expression, though.

It can also do the trick for a bit more complex languages.

However, I'd like to see a Cthulhu parser for any language with nesting, or just "significantly stateful" - mathematical expressions, or your example (nested function calls).

Imagine what would happen if someone tried to cthulhu a parser for such (non-trivial context-free) language. Provided he's smart enough to write a correct parser, I'd bet that during coding he would "discover" first tokenizaton, and then recursive descent parsing - in some form.

After that, the thing's simple: "Hey look, you've written something that's called a recursive descent parser! Do you know that it can be generated automatically from a simple grammar description, just like regular expressions?

---

Long story short:
The only thing that can stop somebody from using the civilised approach is their ignorance of it.

Answer 6

Perhaps working on a good DSL semantics is also important (the syntax matters, but also the semantics). If you are not familiar with these issues, I would suggest reading some books, like Programming Languages Pragmatics (by M.Scott) and Christian Queinnec. Lisp In Small Pieces. Cambridge University Press, 1996.

Reading recent papers in the DSL conferences, e.g. DSL2011 should also help.

Designing & implementing a Domain Specific Language is difficult (and most of the difficulty is not parsing!).

I don't really understand what you mean by parsing the Cthulhu way; I guess you just mean to parse in a somehow bizarre fashion.

Answer 7

First define tokens so that they can be scanned easily. That means you have to keep them simple. For example implementing nestable /* */ comments is hard. Don't do that. Have a look at JSON how strings are defined, don't do anything more complex. And then define a language that can be parsed with a recursive descent parser. That's how Pascal was compiled, very easy.

And you remove everything from the language that is hard to parse. For example, using <> for templates in C++ causes major pain, so don't do that.

That's the trick: To make the parser simple, you define a language that can be parsed with a simple parser.