Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask

Re: Perl and Context Free Grammar

by blokhead (Monsignor)
on Nov 19, 2003 at 09: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 cooling their heels in the Monastery: (10)
As of 2019-02-19 15:01 GMT
Find Nodes?
    Voting Booth?
    I use postfix dereferencing ...

    Results (104 votes). Check out past polls.

    • (Sep 10, 2018 at 18:53 UTC) Welcome new users!