Parsing Perl (statically) is undecidable. Yes, you heard that correctly. It is not unique in this, but it does have some properties which make it trickier than other programming languages that keep their grammars context-free. There is a proof of this by Jeffrey Kegler 1, 2, 3, because as Kegler writes:

Perl 5 is unparseable because it gives the programmer Turing-complete power before compile time.

In practice, most Perl can be parsed statically (which is why PPI exists), but this is just the worst-case scenario.

To understand why this is, we have to dig into the specifics of the perl interpreter.

Preparing the ground

What does it mean by compile time? Well, Perl has special code blocks that it runs at various points as it passes over the code. The big passes can be considered what are called the compile phase and run phase and most of the time, they do exactly what they sound like for each phase, but you can run code in the compile phase (early processing using BEGIN) and compile code in the run phase (eval).

An example is how:

print "1\n";
BEGIN { print "2\n" }
print "3\n";
BEGIN { print "4\n" }

gives the output

2
4
1
3

as the BEGIN lines fire off first as the source is being read in (note: BEGIN/END are from AWK). Using print is a trivial example here, but early processing can change how later code gets parsed.

Taking root

So, what goes on during this compile-phase? Some of this is covered in the perlguts documentation: as it compiles the code, perl builds a compile tree (or optree). The individual nodes of this tree are called OPs after the typedef struct op OP; with the actual struct op and its subclasses (structs that share the same base) in op.h.

Lifting a tree

This optree lives at the C level, but in 1996, Malcolm Beattie worked on "Perl Compiler Kit"1 that contains the B namespace of modules (which Malcolm describes in an article in The Perl Journal). This namespace includes the B.pm module for walking the optree in Perl code by constructing Perl objects that wrap the C structs. The namespace also contains several backends that emit an alternative representation of the optree:

• B::C: freezes the optree as C code that uses the Perl internal API to build the optree so that parsing can be skipped;
• B::CC: a partial backend that attempts to be an optimising compiler to C (e.g., unrolling operations); and
• Pretty-printers such as B::Terse, B::Concise, B::Deparse.

Eventually some of the B namespace became part of the Perl distribution itself since perl v5.005 (in 1998) and are updated as the Perl internals get updated. The B::C and B::CC backends are updated separately.

Walking the branches

To see what the optree for a given expression looks like, we can run

$ perl -MO=Concise -e 'my $x = 23; my $y = 37; my $z = $x + $y'
-e syntax OK
g  <@> leave[1 ref] vKP/REFC ->(end)
1     <0> enter v ->2
2     <;> nextstate(main 1 -e:1) v:{ ->3
5     <2> sassign vKS/2 ->6
3        <$> const(IV 23) s ->4
4        <0> padsv[$x:1,4] sRM*/LVINTRO ->5
6     <;> nextstate(main 2 -e:1) v:{ ->7
9     <2> sassign vKS/2 ->a
7        <$> const(IV 37) s ->8
8        <0> padsv[$y:2,4] sRM*/LVINTRO ->9
a     <;> nextstate(main 3 -e:1) v:{ ->b
f     <2> sassign vKS/2 ->g
d        <2> add[t4] sK/2 ->e
b           <0> padsv[$x:1,4] s ->c
c           <0> padsv[$y:2,4] s ->d
e        <0> padsv[$z:3,4] sRM*/LVINTRO ->f

This tree has two orders to it.

The tree represented by the indentation going from top to bottom here is the pre-order traversal that follows the syntactical order with three nextstate OPs (marking the start of a statement). Following these are various scalar assignments via the sassign OP. The first two sassign OPs are directly assigning an IV (integer value) literal via the const OP to the private SV (scalar value) via the padsv OP (each into $x and $y). The final sassign has an add OP as a child which accesses the previous two private SVs and then assigns to a final private SV $z.

The symbols along the left margin (g, 1, 2, 5, ...) and the ->{_symbol_} at the end of the lines are indicators of the execution order which threads over the same OP nodes (via the OP* op_next member of the OP struct). Following this from the enter OP, we can see the const OP for the IV 23 executes first within the first statement.

Pruning and grafting

There is more in-depth documentation in the perloptree POD found in the B-C distribution. Also, here I did not give much detail on what IV and SV are: these are discussed in

• perlguts,
• illguts or Illustrated Guts: illguts-0.49 dist, PDF, repo.

There are also a few tutorials:

• Where Wizards Fear To Tread by Simon Cozens
• Perl 5 Internals by Simon Cozens (Wayback Machine archive)

Of note, the exact layout of the tree and OPs used can vary across versions of the perl interpreter; therefore, the B modules such as B::Deparse are updated alongside these changes on each perl release to account for this, but code that uses them may need changes to remain compatible.

An example of this is the B::DeparseTree module which was created by Rocky Bernstein to determine which part of the code string a particular OP is derived from, but the tests have drifted away from newer perl releases (more about what motivated this tool at 4, 5, 6, 7, 8, 9).

Saving seeds

Even if the optree can change across versions, it can still be a useful tool. In 2005, Gary Jackson used the B modules to create a proof-of-concept type checker as a project (cf., G. Jackson. "Securing Perl with Type Inference". 2005.). The tests for the minimal type checker continue to work and I have created a repository that fixes some of the minor build bitrot. This can make for an initial prototype towards a more complete type checker.