Re: Perl and Context Free Grammar

[blokhead]

If you're dealing with CFGs in the strict theoretic sense, then there's an obvious naïve way to generate random strings: start with the starting nonterminal, and apply random productions until you are down to all terminals. The drawback being that with some grammars this may take forever (literally or figuratively) to remove all non-terminals. Here's one that generates strings with the same number of a's and b's:

my %cfg = (
  S => [qw/aB bA/],
  A => [qw/aS bAA a/],
  B => [qw/bS aBB b/]
);

my $string = 'S';
my $regex  = join "|" => keys %cfg;

print "$string\n"
    while $string =~ s/($regex)/ $cfg{$1}[ rand @{$cfg{$1}} ] /e;

print "$string\n";

There are better algorithms out there -- A quick googling found this paper which does a good job of explaining why the above method isn't that great, and presents a much better algorithm. Either of these may make a good starting point for your project.