Parsing Perl considered undecidable
By Tim Finin on Monday, January 28th, 2008 at 9:33 am.Jeffrey Kegler on perlmonks.org offers a proof that static parsing of Perl programs is undecidable in his post Perl Cannot Be Parsed: A Formal Proof. The approach is to show that parsing a tricky example (one short line of code!) can be reduced to solving the Halting problem. Here’s a piece of it.
Kennedy’s Lemma: If you can parse Perl, you can solve the Halting Problem.
To prove Kennedy’s Lemma, we assume that we can parse Perl. In particular this means we can take the following devilish snippet of code, concocted by Randal Schwartz, and determine the correct parse for it:whatever / 25 ; # / ; die “this dies!”;
Schwartz’s Snippet can parse two different ways: if whatever is nullary (that is, takes no arguments), the first statement is a division in void context, and the rest of the line is a comment. If whatever takes an argument, Schwartz’s Snippet parses as a call to the whatever function with the result of a match operator, then a call to the die() function.
See his post for the complete proof.
Related posts: • Overcoming addiction to Lisp; • State of the Union Parsing Tool; • List of Semantic web tools;
UMBC eBiquity Blog
