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.

Marcello

As a caveat, I would prefer - if possible - the answers that go beyond the trivial "no parser can parse Perl code because you can execute BEGIN code blocks during compile phase". E.g. show how and why Marpa can't be twined up up with a lexer the way perl's current parser seems to be based on my layman understanding; or why - even if it can - Marpa would be inferior to existing parser. – Marcello

I have sent the link of this question to Jeffrey Kegler's Marpa Google Groups, hopefully he will be interested in answering based on his oldish PerlMonks article "Perl Cannot Be Parsed: A Formal Proof" – Marcello

How could you tell without trying? – Oiler

@Oiler - presumably, someone (Mr Kegler ideally) familiar with both Marpa and Perl's parser can make judgements about suitability. I'm interested if there are deep architechural problems preventing this, NOT if some minor hacking needs to be done to align the edges. – Marcello

I was commenting on the question in the title. – Oiler

@Oiler - ah, I see. I was being somewhat unclear in the title, sorry. It was meant along the lines of "I am assuming that using Marpa will speed up parsing. So can we use Marpa in the first place to achieve that speedup"? – Marcello

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.

Lithometeor