Why are static parser generators more prevalent than dynamic ones?

Question

A parser is a something that takes an input string and spits out an AST.

A parser generator is something that takes a grammar and spits out a parser.

A static parser generator is something that takes a grammar and spits out the code for a parser.

A dynamic parser generator is something that takes a grammar at runtime and spits out a parser at runtime.

---

This blows my mind, because metaprogramming is generally harder than the runtime alternative. I understand why it is more efficient, I understand why it is less erroneous; what I don't understand is how it came to be the norm.

Entering the world of parsers was frustrating. I couldn't understand why everyone kept pointing to Yacc or Bison. I just wanted my program to take an arbitrary EBNF, an arbitrary input string; and spit out the AST.

"Each language has a well defined EBNF available somewhere, in some standard "grammar file" format. I can write an editor to support any language!"

"Okay, not happening. What in the heck are parser combinators? They look cool, but there's no easy way to convert an EBNF to one."

"Okay... so I have the EBNF somehow, how on earth do I parse my text? What?! Generate an entire parser?!"

---

I've been thinking about this. Here is what I've come up with:

• Computers were slow. Compilers were necessary. At the time, writing something that generated a parser seemed saner than writing it by hand.
• Parsers are hard to reason about, so much so that writing one that is dynamically generated is actually tougher than one statically.
• Some individual decided that static parser generators were they way to go, wrote a successful implementation which is now the norm because of popular usage.

I'm probably wrong, hence this question:

Why are static parser generators more prevalent than dynamic ones?

Answer 1

[Nitpicking: Parsers parse; they discover substructure and tell your input is a valid phrase you specified langauge. They (mostly) don't build ASTs. You can often enhance your parser description [See Bison or many others] with code that does this from parser callbacks that occur when subphrases are recognized].

The real reason is that for any particular tool, the grammar doesn't change very fast. You don't need a dynamic parser generator. yes, earlier machines were smaller, and couldn't afford one either space or timewise.

Current workstations have enough capacity so that space isn't an issue anymore. Now the problem is either performance or engineering inconvenience.

Performance wise, you can probably get a dynamic parser generator to produce parsers that run as fast as static ones, so that isn't really the issue.

What is an issue is to use a dynamic parser generator, I have to include in my application. Unless it is designed as an easy to use plug-in, that's going to be awkward. Worse, the one I can get/want/is good probably doesn't match my language; Bison won't plug into java easily because it is C code. So building my application gets harder.

Now, if somebody builds a stunningly good dynamic parser generator and puts it in the library of the language you are using, then you might be good to go. (Check out Perl's MARPA for one of these).

But, now we're back to, do you need dynamic parser generation? If not, the static ones are just fine and are generally pretty damn good.

If you insist... from your application, fork a subtask to run a static parser generator, and import its results into your application. Voila, dynamic parser generation from a static parser generator.

You won't find many takers.

[I've personally built parsers for dozens of languages. Always managed to succeed with the static parser generator scheme].

[Now, my peeve with parser generators is that they typically don't build ASTs, and that's always harder to implement than defining the grammar. You can get them to do this if you make the right rules; the parser generator I use does this automatically (see bio) and that's a big win for big grammars].