[Perl-flat-commit-notify] SF.net SVN: perl-flat: [100] trunk/perl-flat

[notifies s. of c. c. <per...@li...>]

Revision: 100
          http://svn.sourceforge.net/perl-flat/?rev=100&view=rev
Author:   estrabd
Date:     2007-02-19 13:48:47 -0800 (Mon, 19 Feb 2007)

Log Message:
-----------
created node list for DFA, next step is dft creation

Modified Paths:
--------------
    trunk/perl-flat/dev-scripts/bdetest.pl
    trunk/perl-flat/lib/FLAT/DFA.pm
    trunk/perl-flat/lib/FLAT/NFA.pm
    trunk/perl-flat/lib/FLAT.pm

Modified: trunk/perl-flat/dev-scripts/bdetest.pl
===================================================================
--- trunk/perl-flat/dev-scripts/bdetest.pl	2007-02-19 14:59:39 UTC (rev 99)
+++ trunk/perl-flat/dev-scripts/bdetest.pl	2007-02-19 21:48:47 UTC (rev 100)
@@ -8,8 +8,6 @@
 use FLAT::Regex::WithExtraOps;
 
 my $dfa = FLAT::Regex->new($ARGV[0])->as_nfa->as_dfa;
-if ($dfa->is_valid($ARGV[1])) {
-  print "valid" 
-} else {
-  print "not valid" 
-}
+
+use Data::Dumper;
+print Dumper($dfa->as_node_list);

Modified: trunk/perl-flat/lib/FLAT/DFA.pm
===================================================================
--- trunk/perl-flat/lib/FLAT/DFA.pm	2007-02-19 14:59:39 UTC (rev 99)
+++ trunk/perl-flat/lib/FLAT/DFA.pm	2007-02-19 21:48:47 UTC (rev 100)
@@ -80,6 +80,8 @@
         if $num != 1;
 }
 
+#### transformations
+
 sub trim_sinks {
   my $self = shift;
   my $result = $self->clone();
@@ -157,10 +159,49 @@
 
 }
 
+# DFT stuff in preparation for DFA pump stuff;
+sub as_node_list {
+    my $self = shift;
+    my %node = ();
+    for my $s1 ($self->get_states) {
+      for my $s2 ($self->get_states) {
+         my $t = $self->get_transition($s1, $s2);
+         if (defined $t) {
+           # array of symbols that $s1 will go to $s2 on...
+	   push(@{$node{$s1}{edges}{$s2}},split(',',$t->as_string)); 
+         }
+      }
+    }
+  return %node;
+}
+
+# returns a tree stucture resulting from a dft of the DFA;
+sub as_depth_first_tree {
+  my $self = shift;
+  # data structure to do dft over
+  my %nodes = $self->as_node_list();
+  my %dflabels = (); # "global" lookup table for dflable
+  my %parents  = (); # "global" lookup table for parents
+  my $recurse_level = 0; # tracks recurse level
+  my $search = sub {
+    $recurse_level++;
+    
+    # leave
+    $recurse_level--;
+  };
+  
+  # start the recursive dft search
+  my $tree = $search->($self->get_starting());
+  # return tree
+  return $tree;
+}
+
 # creates table used by a FLAT::DFA::Validator object to assess
-# the validity of a given string
+# the validity of a given string <-- executes symbols over DFA
+# if there is not transition for given state and symbol, it fails immediately
+# if the current state we're in is not final when symbols are exhausted, then it fails
 
-sub is_valid {
+sub is_valid_string {
   my $self = shift;
   my $string = shift;
   chomp $string;

Modified: trunk/perl-flat/lib/FLAT/NFA.pm
===================================================================
--- trunk/perl-flat/lib/FLAT/NFA.pm	2007-02-19 14:59:39 UTC (rev 99)
+++ trunk/perl-flat/lib/FLAT/NFA.pm	2007-02-19 21:48:47 UTC (rev 100)
@@ -316,16 +316,6 @@
 
 ######## transformations
 
-# returns a tree stucture resulting from a dft of the FA;
-sub as_depth_first_tree {
-  my $search = 
-  sub {
-    # anonymous sub called by $search->(..)
-  };
-  
-  
-}
-
 # subset construction
 sub as_dfa {
     my $self = shift;

Modified: trunk/perl-flat/lib/FLAT.pm
===================================================================
--- trunk/perl-flat/lib/FLAT.pm	2007-02-19 14:59:39 UTC (rev 99)
+++ trunk/perl-flat/lib/FLAT.pm	2007-02-19 21:48:47 UTC (rev 100)
@@ -181,7 +181,7 @@
   if (@_) 
   { my $FA = FLAT::Regex::WithExtraOps->new(shift @_)->as_pfa()->as_nfa->as_dfa(); 
     foreach (@_)
-    { if ($FA->is_valid($_)) {
+    { if ($FA->is_valid_string($_)) {
         print "(+): $_\n";
       } else {
         print "(-): $_\n";
@@ -194,7 +194,7 @@
       if ($. == 1) { #<-- uses first line as regex!
         $FA = FLAT::Regex::WithExtraOps->new($_)->as_pfa()->as_nfa->as_dfa();
       } else {
-	if ($FA->is_valid($_)) {
+	if ($FA->is_valid_string($_)) {
 	  print "(+): $_\n";
         } else {
 	  print "(-): $_\n";


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.