I did some studying on non-determinism.

An example of a non-deterministic algorithm is mergesort.

use sort '_mergesort';
my @sorted =
    sort { substr($a, 0, 1) cmp substr($b, 0, 1) }
    qw( foo bar baz );
[download]

It is guarantees that the results will the sorted, but the relative ordering of baz and bar is not specified. Therefore, mergesort is non-deterministic.

Let's see if we can replicate the same situation with the parser.

The goals of Perl's parser include the production of functions.

package Mod;

BEGIN {
    my ($sub) =
        map "sub { $_ }",
        join ' ',
        map "$_();",
        sort { substr($a, 0, 1) cmp substr($b, 0, 1) }
        qw( foo bar baz );
}

sub foo { print "$foo\n" };
sub bar { print "$bar\n" };
sub baz { print "$baz\n" };

1;
[download]

The parser produces a function that calls foo(), bar() and baz(), but the order in which the calls are organized is not specified. Therefore, the parser is non-deterministic.

I don't know what that means wrt Perl's parsability, since I don't know I don't know how that's defined.