Slash Boxes
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

use Perl Log In

Log In

[ Create a new account ]

Alias (5735)

  (email not shown publicly)

Journal of Alias (5735)

Monday January 21, 2008
07:05 PM

Perl Cannot Be Parsed: A Formal Proof

[ #35452 ]

This is possibly one of the most awesome emails I have ever received.


I saw the suggestion that parsing Perl 5 could be reduced to the
Halting Problem on your PPI man page, and have carried it out

I became interested because I've just released an alpha on CPAN of an
Earley's parser with LR(0) precomputation (
~jkegl/Parse-Marpa-0.202000/ ), and one potential application is as
an approach to Perl 5 static parsing. I wondered whether 100% is
achievable, and so determined to follow up on your hint.

Perl::Marpa is only in alpha at this point, but I'd be interested in
your thoughts about it, with relation to Perl 5 static parsing, and
in general. I think Parse::Marpa could have potential as a "utility

best, jeffrey kegler


Not being a mathematician, although I was pretty confident the Halting Problem applied to Perl 5, there's no way I'd be able to sit down and write an actual proof.

I also don't even know what a "Lemma" is (although I can guess from the context) which makes having a named one even more fun.

My hope for Perl 6 is that is WILL be statically parsable (I'm still not entirely sure if it is or not, but I worry that it won't be).

Once you can statically parse software, it allows code to have an understanding of it's own structure, and greatly enhances the diversity of automated tools that can be written, and thus improves the language one of the most practical dimension, "How easy is this to write".

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
More | Login | Reply
Loading... please wait.