Can Marpa be used to speed up Perl interpreter's parsing?

Question

Can the existing Marpa parser be used to improve parsing of Perl 5 (e.g., replace all or chunks of existing Perl interpreter's parser)?

I am asking on a theoretical level, e.g. ignoring practical considerations such as "if it can, it would cost 10,000 man hours of work".

If not, what are the specific issues preventing the use of Marpa? (again, preferably theoretical ones).

For background of why this is interesting, Jeffrey Kegler (Marpa's author) has posted a somewhat famous article "Perl Cannot Be Parsed: A Formal Proof" on PerlMonks in 2008, which was influenced by his then-current work on Marpa.

Answer 1

Thanks for asking. The perlmonks post and my current parsing work address two different if related questions. Question 1: Is Perl parsing, in its full generality, decidable by a Turing machine? Question 2: Can Marpa, as a practical matter, parse Perl 5?

You might compare the two questions: "Is the behavior of every C program decidable?" and "Can machine X run programs compiled in C?" The answers are, respectively, "no" and "yes for all practical purposes and reasonable choices of X". So my perlmonks post (updated here) is about the theoretical question of whether the syntax of Perl programs in, in its full generality, decidable. Note that the decidability of Perl parsing in that context has nothing to do with Marpa, recursive descent, bison, etc. -- it's about Turing machines.

Question 2 is "Can Marpa drive a practical Perl 5 parser?" The current Perl 5 parser is LALR, with a separate lexer and lots of procedural assistance. Marpa is more powerful than LALR, allows a separate lexer, and offers much more help to procedural code than LALR does. I addressed the speed question in a recent blog post: "Is Earley parsing fast enough?" What I've just said is very telegraphic -- but I hope it will do to outline how I'd justify my "yes" answer to Question 2.

No deep architectural problem stands in the way of a Marpa-driven Perl 5 parser. At this point, it's really a question of comfort level.