Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number

Re: Perl and Context Free Grammar

by blokhead (Monsignor)
on Nov 19, 2003 at 14:11 UTC ( #308297=note: print w/replies, xml ) Need Help??

in reply to Perl and Context Free Grammar

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.


Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://308297]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (7)
As of 2021-04-13 17:49 GMT
Find Nodes?
    Voting Booth?

    No recent polls found