[groovy2shoes]

I posted the link mostly in jest.

That being said, I still contend that a Perl 5 parser is still inextricably separable from the runtime. Any parser that wants to be fully compatible with Perl 5 will need to be able to also run Perl 5 code. That is, the parser will need to be coupled with the runtime.

A consequence of the parser needing to be able to execute arbitrary code is that the parser is undecidable. This follows from the halting problem, which is the point of the article I posted and is also pointed out in the one you posted.

As a sidenote, I find the distinction between "static" and "dynamic" parsing to be rather silly. The only people I've ever heard make that distinction are Perl apologetics. No need to be so defensive: parsing is allowed to be ambiguous, and it is allowed to be undecidable -- but it's not considered ideal.

[rurban]

Dynamic and static parsing is different to just calling eval within the parser.

"Dynamic parsing problems" such as solving the halting problem, by e.g. changing the prototypes or eval'ing code in BEGIN blocks are just small practical problems. In practice the parser only has to be GC-safe, which needs a few days work.

   | BEGIN b:block           { p2_eval(P, b) }

On the other hand the "dynamic vs static parsing" on perl11.org talks about compiling and extending parser rules at run-time, which needs a fast vm to do this. To be able to support macros. Not perl5, perl6 or nqp. Efficiency should be near the C level, but you shouldn't be forced to go the rakudo way with its insane bootstrapping and serialization overhead just to support BEGIN blocks in its stdlib and support run-time parsing. The JVM or .NET could do that, but I don't buy the overhead, esp. when you look at fast parser combinators in lua, lisp or look at maru, which is basically a jitting parser, bootstrapping itself.

The author

[groovy2shoes]

Of the two types of macros I'm familiar with, neither demands a "dynamic" parser. C-style macros (conceptually) work as a text pre-processor prior to the compiler's lexing phase. Lisp-style macros work on the syntax tree after the parse phase has finished.

In some Lisps, such as Common Lisp, macros are simply functions from syntax tree to syntax tree. Since these execute at compile time, you can still run into the same types of problems you get with Perl's BEGIN. Scheme's syntax-rules macros are more limited: they cannot execute arbitrary code, but they can do pattern matching and substitution on syntax trees. Despite this limitation, syntax-rules covers the vast majority of macro use cases. The term rewriting systems in Haskell and Cat are reasonably similar.

My point to all of this is that macros are no justification for "dynamic" parsing. The only distinction I can find of the two kinds of parsing is that a "dynamic" parser sometimes needs to execute bits of the program before it is able to progress. This is not necessary for macros!

As far as parser combinators go, I conjecture that they will not be powerful enough to deal completely with Perl's grammar. In general, they're limited to LL(k) grammars. Still, you may be able to jump through some hoops to get what you want out of them.