Index: src/compdic/compdic-create-fst =================================================================== --- src/compdic/compdic-create-fst (revision f4bf33ed04eb342d17a377035e58f078b78159c3) +++ (revision ) @@ -1,181 +1,0 @@ - -no_of_parts=0 - -while [ $# -gt 2 ] -do - case $1 - in - -p) - no_of_parts=$2 - shift 2 - ;; - - *) - echo "The arguments to use are" - echo "-p: number of parts" - shift 1 - ;; - esac -done - -if [ $# -lt 2 ] -then - echo "Usage:" - echo " compdic [-p ] " - echo "where" - echo " - file containig a list of words, one per line, iso-8859-2 encoded" - echo " - a file to which the compiled automaton in openfst format shoul be written" - exit 0 -fi - -if [ $no_of_parts -eq 0 ] -then - no_of_parts=$(( `cat $1 | wc -l` / 75000 + 1 )) -fi - - -echo number of parts: $no_of_parts - - -tempdir=`mktemp -d /tmp/compdic.XXXXXX` - -alphabet=`tempfile -d $tempdir` - -cat < $alphabet - 0 -a 1 -A 2 -ä 3 -± 4 -¡ 5 -b 6 -B 7 -c 8 -C 9 -æ 10 -Æ 11 -d 12 -D 13 -e 14 -E 15 -é 16 -ê 17 -Ê 18 -f 19 -F 20 -g 21 -G 22 -h 23 -H 24 -i 25 -I 26 -j 27 -J 28 -k 29 -K 30 -l 31 -L 32 -³ 33 -£ 34 -m 35 -M 36 -n 37 -N 38 -ñ 39 -Ñ 40 -o 41 -O 42 -ö 43 -ó 44 -Ó 45 -p 46 -P 47 -q 48 -Q 49 -r 50 -R 51 -s 52 -S 53 -¶ 54 -Š 55 -t 56 -T 57 -u 58 -U 59 -ü 60 -v 61 -V 62 -w 63 -W 64 -x 65 -X 66 -y 67 -Y 68 -z 69 -Z 70 -Œ 71 -¬ 72 -¿ 73 -¯ 74 -0 75 -1 76 -2 77 -3 78 -4 79 -5 80 -6 81 -7 82 -8 83 -9 84 -_ 85 -- 86 -? 87 -! 88 -~ 89 -; 90 -, 91 -/ 92 -* 93 -+ 94 -EOF - - -no_of_lines=$(( (`cat $1 | wc -l` / $no_of_parts) + 1 )) - -split -l $no_of_lines $1 $tempdir/part. - -automaton=$tempdir/output.fst - -cat < $automaton -EOF - -n=0 - -for f in $tempdir/part.* -do - temp1=`tempfile -d $tempdir` - temp2=`tempfile -d $tempdir` - temp3=`tempfile -d $tempdir` - - n=$(( $n + 1 )) - echo processing part $n - - cat $f |\ - lst2fstext |\ - fstcompile --acceptor --isymbols=$alphabet |\ - fstrmepsilon |\ - fstdeterminize > $temp1 - fstminimize $temp1 $temp2 - - fstunion $automaton $temp2 | fstrmepsilon | fstdeterminize > $temp3 - fstminimize $temp3 $automaton -done - -echo generating binary automaton file ... - -cat $automaton | fsttopsort > $2 -rm -r $tempdir - -#echo generating cats file ... - -#cat $1 | cut -d ',' -f 2 | sort -u $1.cats Index: src/compdic/compdic-fst-add =================================================================== --- src/compdic/compdic-fst-add (revision f4bf33ed04eb342d17a377035e58f078b78159c3) +++ (revision ) @@ -1,18 +1,0 @@ - -if [ $# -ne 2 ] -then - echo "Usage:" - echo " compdic-fst-add " - echo "where" - echo " - automaton in openfst format" - echo " - automaton in openfst format containing paths to be removed from " - exit 0 -fi - -tempdir=`mktemp -d /tmp/compdic.XXXXXX` - -automaton=$tempdir/output.fst - -fstunion $1 $2 | fstrmepsilon | fstdeterminize | fstminimize | fsttopsort > $automaton -mv $automaton $1 -rm -r $tempdir Index: src/compdic/compdic-fst-minus =================================================================== --- src/compdic/compdic-fst-minus (revision f4bf33ed04eb342d17a377035e58f078b78159c3) +++ (revision ) @@ -1,18 +1,0 @@ - -if [ $# -ne 2 ] -then - echo "Usage:" - echo " compdic-fst-remove " - echo "where" - echo " - automaton in openfst format" - echo " - automaton in openfst format containing paths to be removed from " - exit 0 -fi - -tempdir=`mktemp -d /tmp/compdic.XXXXXX` - -automaton=$tempdir/output.fst - -fstdifference $1 $2 | fsttopsort > $automaton -mv $automaton $1 -rm -r $tempdir Index: src/compdic/compdic-fst-update =================================================================== --- src/compdic/compdic-fst-update (revision f4bf33ed04eb342d17a377035e58f078b78159c3) +++ (revision ) @@ -1,43 +1,0 @@ - -if [ $# -lt 2 ] -then - echo "Usage:" - echo " compdic-fst-update ..." - echo "where" - echo " - file containig a list of words, one per line, iso-8859-2 encoded" - echo " - a file to which the compiled automaton (cor/kor format) shoul be written" - exit 0 -fi - -tempdir=`mktemp -d /tmp/compdic.XXXXXX` - -dict=$1 -shift - -dicplus=$tempdir/plus.dic -fstplus=$tempdir/plus.fst -dicminus=$tempdir/minus.dic -fstminus=$tempdir/minus.fst -tmpfst=$tempdir/tmp.fst - -touch $dicplus -touch $dicminus - -while (($#)) -do - echo processing $1 ... - cat $1 | egrep '^>' | sed -r 's/^> *//' >> $dicplus - cat $1 | egrep '^<' | sed -r 's/^< *//' >> $dicminus - shift -done - -echo updating $dict ... -compdic-create-fst $dicplus $fstplus -compdic-create-fst $dicminus $fstminus -fstdifference $dict $fstminus | fstdeterminize > $tmpfst -fstunion $tmpfst $fstplus | fstdeterminize | fstminimize > $tmpfst -mv ${dict} ${dict}~ -mv $tmpfst ${dict} - - -rm -r $tempdir Index: src/dgc/Makefile =================================================================== --- src/dgc/Makefile (revision e7de6cc88c605c4f810cbc852e843294b4b0e8ac) +++ src/dgc/Makefile (revision 3b02b04ff9c7c3446ca477cd84c2bc7f737c38b4) @@ -7,4 +7,5 @@ ifdef BIN_DIR install -m 0755 dgc $(BIN_DIR) + install -m 0755 l2src $(BIN_DIR) endif @@ -13,4 +14,5 @@ ifdef BIN_DIR rm $(BIN_DIR)/dgc + rm $(BIN_DIR)/l2src endif Index: src/dgc/dgc =================================================================== --- src/dgc/dgc (revision e7de6cc88c605c4f810cbc852e843294b4b0e8ac) +++ src/dgc/dgc (revision 3b02b04ff9c7c3446ca477cd84c2bc7f737c38b4) @@ -9,12 +9,16 @@ use lib "$ENV{'HOME'}/.local/lib/utt"; -use strict; +#use strict; use Getopt::Long; use Data::Dumper; use attr; use File::HomeDir; +use Parse::RecDescent; + +$::RD_HINT=1; +# use List::MoreUtils; my $systemconfigfile='/etc/utt/dgc.conf'; -my $userconfigfile=home()."/.utt/dgc.conf"; +my $userconfigfile=0; #home()."/.utt/dgc.conf"; Getopt::Long::Configure('no_ignore_case_always'); @@ -31,25 +35,12 @@ if(open(CONFIG, $file)){ while () { - chomp; - s/#.*//; - s/^\s+//; - s/\s+$//; + chomp; s/#.*//; s/^\s+//; s/\s+$//; next unless length; my ($name, $value) = split(/\s*=\s*/, $_, 2); - if(($name eq "categories")or($name eq "c")){ - $catfile=$value; - } - elsif(($name eq "dictionary")or($name eq "d")){ - $dicfile=$value; - } - elsif(($name eq "grammar")or($name eq "g")){ - $gramfile=$value; - } - elsif(($name eq "outputfile")or($name eq "o")){ - $outputfile=$value; - } - elsif(($name eq "help")or($name eq "h")){ - $help=1; - } + if(($name eq "categories")or($name eq "c")) { $catfile=$value; } + elsif(($name eq "dictionary")or($name eq "d")) { $dicfile=$value; } + elsif(($name eq "grammar")or($name eq "g")) { $gramfile=$value; } + elsif(($name eq "outputfile")or($name eq "o")) { $outputfile=$value; } + elsif(($name eq "help")or($name eq "h")) { $help=1; } } @@ -90,39 +81,118 @@ die("At least one of --cats and --dic must be given.\n") if !$catfile && !$dicfile; -my $ncat=0; -my $nrole=0; -my $nsgl=0; -my $nleft=0; -my $nright=0; -my $ninitr=0; -my $nfinr=0; -my $ninitf=0; -my $nfinf=0; -my $ninitc=0; -my $nfinc=0; -my $nreq=0; -my $nlink=0; -my $nflag=0; -my $nset=0; -my $npass=0; -my $nlong=0; -my $nconstr=0; -my $nclass=0; - -my %cats; -my %roles; -my %agr; -my %gov; - -if(!$outputfile) { - *OUTPUT = *STDOUT; -} -elsif($outputfile eq "-") { - *OUTPUT = *STDOUT; -} -else { - open(OUTPUT, ">$outputfile") or die("Can't open output file: $outputfile!"); -} - + +our %in; #gramatyka wej¶ciowa +our %idx; #indeks gramatyki wej¶ciowej (niektóre stwierdzenia) +our %out; #gramatyka wyj¶ciowa +our %class; #tablica klas + +our $attr_re = $attr::attr_re; +our $cat_re = $attr::cat_re; +our $cats_re = qr/(?:$attr::cat_re\s*(?:,\s*$attr::cat_re)*)/; +our $class_re = qr/(?:\@\w+)/; +our $av_re = $attr::av_re; +our $avlist_re = $attr::avlist_re; +our $role_re = qr/(?:[[:lower:][:digit:]_]+)/; +our $prop_re = qr/(?:[[:upper:]]+)/; +our $proplist_re = qr/(?:(?:\&$prop_re)+)/; + +my $inputlineno=0; + +our $statementgrammar = q( + +statement : statement1 ";" { $item[1] } + +statement1: /cat/i acat { ['cat', { cat=>$item{acat}, catexp=>attr::parse($item{acat}) }, $item{acat}] } + | /flag/i flag { ['flag', { flag=>$item{flag} }, $item{flag}] } + | /role/i role { ['role', { role=>$item{role} }, $item{role}] } + | /left/i role { ['left', { role=>$item{role} }, 0] } + | /right/i role { ['right', { role=>$item{role} }, 0] } + | /sgl/i role { ['sgl', { role=>$item{role} }, 0] } + | /req/i xcat role { ['req', { cats=>$item{xcat}, role=>$item{role} }, 0] } + | /agr/i role attr { ['agr', { role=>$item{role}, attr=>$item{attr} }, $item{role}] } + | /gov/i role xcat { ['gov', { role=>$item{role}, cats=>$item{xcat} }, $item{role}] } + | /init/i flagconstr { ['initf', { flag=>$item{flagconstr} }, 0] } + | /fin/i flagconstr { ['finf', { flag=>$item{flagconstr} }, 0] } + | /init/i role { ['initr', { role=>$item{role} }, 0] } + | /fin/i role { ['finr', { role=>$item{role} }, 0] } + | /set/i xcat flag { ['set', { cats=>$item{xcat}, flag=>$item{flag} }, 0] } + | /pass/i role flag { ['pass', { role=>$item{role}, flag=>$item{flag} }, 0] } + | /constre/i role role { ['constre', { role1=>$item[2], role2=>$item[3] }, 0] } + | /constri/i role role { ['constri', { role1=>$item[2], role2=>$item[3] }, 0] } + + | /link/i xcat optflags(?) xcat optflags(?) role prop(s?) + { ['link', { hcats=>$item[2], hflagconstr=>$item[3], + dcats=>$item[4], dflagconstr=>$item[5], + role=>$item[6], props=>$item[7] }, 0] } + + | /long/i role role(s? /,/) '^' role(s? /,/) + { ['long', { rel=>$item[2], up=>$item[3], down=>$item[5] }, 0] } + + | /class/i classname '=' xcat { ['class', { name=>$item{classname}, cats=>$item{xcat} }, $item{classname}] } + +acat: /$attr::cat_re/ + +attr: /$attr::attr_re/ + +xcat: classexpr + +role: /\w+/ + +flag: /\w+/ + +optflags: "//" flagconstr { $item[2] } + +flagconstr: /\w+[+-]/ + +prop: '&' /\w+/ { $item[2] } + +classname: /\$\w+[+-]/ + +classexpr : classexpr1 '|' classexpr { main::union($item[1],$item[3]) } + | classexpr1 '~' classexpr { main::intersection( $item[1], main::complement($item[3]) ) } + | classexpr1 + +classexpr1 : classexpr2 '&' classexpr1 { main::intersection($item[1],$item[3]) } + | classexpr2 + +classexpr2 : '~' classexpr2 { main::complement($item[2]) } + | classexpr3 + +classexpr3 : classexpr4 '/' /$attr::avlist_re/ { main::intersection($item[1], [main::extension('*/' . $item[3])] ) } + | classexpr4 + +classexpr4 : class + | cat + | '(' classexpr ')' { $item[2] } + +class : classname { $main::class{$item[1]} or @{[]} } + +cat : /$main::cat_re/ { [main::extension($item[1])] } + +); + +our $statementparser = Parse::RecDescent->new($statementgrammar); + +sub register +{ + my ($src, $statement, $data, $index) = @_ ; + $data->{line} = $inputlineno; + $data->{src} = $src; + push @{$in{$statement}}, $data; + push @{$idx{$statement}{$index}}, $data if($index); + + if ($statement eq 'class') { $class{ $data->{name} } = $data->{cats} } +} + + +if(!$outputfile) { *OUTPUT = *STDOUT; } +elsif($outputfile eq "-") { *OUTPUT = *STDOUT; } +else { open(OUTPUT, ">$outputfile") or die("Can't open output file: $outputfile!"); } + +if(!$gramfile) { *INPUT = *STDIN; } +elsif($gramfile eq "-") { *INPUT = *STDIN; } +else { open(INPUT, "cat $gramfile | m4 |") or die("Unable to open: $gramfile!"); } + +# *INPUT = *STDIN; ############### TYMCZASOWO loadcats($catfile) if $catfile; @@ -130,99 +200,306 @@ -my $cats_re = qr/(?:$attr::cat_re\s*(?:,\s*$attr::cat_re)*)/; -my $class_re = qr/(?:\@\w+)/; - -my $avlist_re = $attr::avlist_re; - -my $role_re = qr/(?:[[:lower:][:digit:]_]+)/; -my $prop_re = qr/(?:\&[[:upper:]]+)/; -my $proplist_re = qr/(?:$prop_re+)/; - -# class parse_class: -# /$attr::cat_re/g; - - -if(!$gramfile) { - *INPUT = *STDIN; -} -elsif($gramfile eq "-"){ - *INPUT = *STDIN; -} -else { - open(INPUT, $gramfile) or die("Unable to open: $gramfile!"); -} +# CZYTANIE GRAMATYKI DGC while() { + $inputlineno++; s/#.*//; s/^\s+//; s/\s+$//; - if(/^AGR\s+(\S+)\s+(\S+)$/) + s/\s+/ /g; + next unless $_; + my $result = $statementparser->statement("$_;"); + + # print "#input line $inputlineno\n"; + # print Dumper($result); + + if($result) { register($_, @{$result}) } else { print STDERR "ERROR at line $inputlineno\n" } +} + + +# GENEROWANIE GRAMATYKI DGP + +my $inline = 0; +my $outline = 0; + + +# print Dumper($idx{gov}->{subj}); + + +for my $x (@{$in{cat}}) { print_outin("CAT $x->{cat}", $x); } + +for my $x (@{$in{flag}}) { print_outin("FLAG $x->{flag}", $x); } + +for my $x (@{$in{role}}) { print_outin("ROLE $x->{role}", $x); } + +for my $x (@{$in{long}}) { print_outin("LONG $x->{rel} " . join(",",@{$x->{up}}) . "^" . join(",",@{$x->{down}}), $x) } + +for my $x (@{$in{left}}) { print_outin("LEFT $x->{role}", $x) if chk_role($x->{role}, $x) } + +for my $x (@{$in{right}}) { print_outin("RIGHT $x->{role}", $x) if chk_role($x->{role}, $x) } + +for my $x (@{$in{sgl}}) { print_outin("SGL $x->{role}", $x) if chk_role($x->{role}, $x) } + +for my $x (@{$in{req}}) +{ + if( chk_role($x->{role}, $x) ) { - push @{$agr{$1}}, $2; - } - elsif(/^GOV\s+(\S+)\s+(\S+)$/) - { - push @{$gov{$1}}, attr::parse($2); - } - elsif(/^ROLE\s+\S+$/) - { - $roles{$_}=1; - print OUTPUT "$_\n"; - } - elsif(/^SGL\s+\S+$/) - { - ++$nsgl; - print OUTPUT "$_\n"; - } - elsif(/^REQ\s+(\S+)\s+(\S+)$/) - { - print OUTPUT "#$_\n"; - my $cat = attr::parse $1; - for my $atomcat (keys %cats) + for my $atomcat (map{$_->{cat}} @{$x->{cats}}) { - if(attr::match @$cat, @{$cats{$atomcat}}) - { - print OUTPUT "REQ ".$atomcat." $2\n"; - ++$nreq; - } + print_outin("REQ $atomcat $x->{role}", $x); } } - elsif(/^LEFT\s+\S+$/) +} + +for my $x (@{$in{initr}}) { print_outin("INITR $x->{role}", $x) if chk_role($x->{role}, $x) } + +for my $x (@{$in{finr}}) { print_outin("FINR $x->{role}", $x) if chk_role($x->{role}, $x) } + +for my $x (@{$in{initf}}) { print_outin("INITF $x->{flag}", $x) } # SPRAWDZIÆ CZY FLAGA JEST ZADEKLAROWANA + +for my $x (@{$in{finf}}) { print_outin("FINF $x->{flag}", $x); } # SPRAWDZIÆ CZY FLAGA JEST ZADEKLAROWANA + +for my $x (@{$in{set}}) +{ + for my $atomcat (map{$_->{cat}} @{$x->{cats}}) { - ++$nleft; - print OUTPUT "$_\n"; + print_outin("SET $atomcat $x->{flag}", $x); + } +} + +for my $x (@{$in{pass}}) { print_outin("PASS $x->{role} $x->{flag}", $x); } + +for my $x (@{$in{constre}}) { print_outin("CONSTRE $x->{role1} $x->{role2}", $x) if chk_role($x->{role1}, $x) & chk_role($x->{role2}, $x) } + +for my $x (@{$in{constri}}) { print_outin("CONSTRI $x->{role1} $x->{role2}", $x) if chk_role($x->{role1}, $x) & chk_role($x->{role2}, $x) } + +for my $x (@{$in{link}}) +{ + my @agrs = @{ $idx{agr}->{$x->{role} } or [] }; + my @govs = @{ $idx{gov}->{$x->{role} } or [] }; + + my @deps = (@govs > 0) ? @{ intersection( $x->{dcats}, map { $_->{cats} } @govs ) } : @{ $x->{dcats} } ; + + for my $head ( @{ $x->{hcats} } ) + { + DEP: + for my $dep (@deps) + { + for my $agr (@agrs) + { + next DEP unless attr::agree(@{$head->{catexp}},@{$dep->{catexp}},$agr->{attr}); + } + my $hflagconstr = @{$x->{hflagconstr}} ? "//@{$x->{hflagconstr}}" : ""; + my $dflagconstr = @{$x->{dflagconstr}} ? "//@{$x->{dflagconstr}}" : ""; + my $props = join(map { "\&$_" } $x->{props}); + print_outin("LINK $head->{cat}$hflagconstr $dep->{cat}$dflagconstr $x->{role}$props",$x, @agrs, @govs); + } } - elsif(/^RIGHT\s+\S+$/) +} + + +sub chk_role +{ + ($role, $statement_details) = @_; + if($idx{role}{$role}) { 1; } else { print_error("undefined role", $statement_details); 0; } +} + +sub print_outin +{ + my ($out,@in) = (shift, @_); + print OUTPUT "$out\t\t#"; + printf OUTPUT " %04d@\"%s\"", $_->{line}, $_->{src} foreach @in; + print OUTPUT "\n"; +} + +sub print_error +{ + my ($message,@in) = (shift,@_); + print STDERR "ERROR: $message in statement "; + printf STDERR " %04d@\"%s\"", $_->{line}, $_->{src} foreach @in; + print STDERR "\n"; +} + + +sub extractcats +{ + my $file = shift; + open DICFILE, "$file"; + while() { - ++$nright; - print OUTPUT "$_\n"; + while(/,([^[:space:];]+)/g) + { + my $cat=$1; + next if !$cat; # || exists $cats{$cat}; +# print OUTPUT "CAT $1\n"; + register('cat', {src=>"CAT $cat", cat=>"$cat", catexp=>attr::parse($cat)}, $cat); + } } - elsif(/^INIT\s+[[:lower:]]\S*$/) + close DICFILE; +} + + +sub loadcats +{ + my $file = shift; + open CATFILE, "$file"; + while() { - ++$ninitr; - s/INIT/INITR/; - print OUTPUT "$_\n"; + tr/ \t\n//d; + next if !$_; # || exists $cats{$_}; +# print OUTPUT "CAT $_\n"; + register("CAT $_", 'cat', {cat=>"$_", catexp=>attr::parse($_)}, $_); } - elsif(/^FIN\s+[[:lower:]]\S*$/) - { - ++$nfinr; - s/FIN/FINR/; - print OUTPUT "$_\n"; - } - elsif(/^INIT\s+[[:upper:]]+[+-]$/) - { - ++$ninitf; - s/INIT/INITF/; - s/[+-]//g; - print OUTPUT "$_\n"; - } - elsif(/^FIN\s+[[:upper:]]+$/) - { - ++$nfinf; - s/FIN/FINF/; - s/[+-]//g; - print OUTPUT "$_\n"; - } + close CATFILE; +} + +sub extension +{ + my $cat = shift; + my $catexp = attr::parse($cat); + grep { attr::match(@{$_->{catexp}},@{$catexp}) } @{$in{cat}}; +} + +sub uniq { my %seen; grep { ! $seen{$_}++ } @_ } +sub union { [ uniq( map { @{$_} } @_ ) ] } +sub intersection { my $n=@_; my %seen; [ grep { ++$seen{$_} == $n } map { @{$_} } @_ ] } +sub complement { my %exclude; for $c (@{shift()}) { $exclude{$c}++ }; [ grep { ! $exclude{$_} } @{$in{cat}} ] } + +# printf STDERR "%6d CAT statements\n", 0+keys(%cats); +# printf STDERR "%6d ROLE statements\n", 0+keys(%role); +# printf STDERR "%6d SGL statements\n", @sgl+0; +# printf STDERR "%6d REQ statements\n", @req+0; +# printf STDERR "%6d LEFT statements\n", $nleft; +# printf STDERR "%6d RIGHT statements\n", $nright; +# printf STDERR "%6d INITR statements\n", $ninitr; +# printf STDERR "%6d FINR statements\n", $nfinr; +# printf STDERR "%6d INITF statements\n", $ninitf; +# printf STDERR "%6d FINF statements\n", $nfinf; +# printf STDERR "%6d INITC statements\n", $ninitc; +# printf STDERR "%6d FINC statements\n", $nfinc; +# printf STDERR "%6d LINK statements\n", $nlink; +# printf STDERR "%6d CLASS statements\n", $nclass; +# printf STDERR "%6d FLAG statements\n", $nflag; +# printf STDERR "%6d SET statements\n", $nset; +# printf STDERR "%6d PASS statements\n", $npass; + + +################################################################################## + +# while() +# { +# $inputlineno++; +# s/#.*//; +# s/^\s+//; +# s/\s+$//; +# s/\s+/ /g; +# if (/^CAT ($cat_re)$/) { register('cat', {src=>$&, cat=>attr::parse($1)}, $1); } +# elsif(/^FLAG (\S+)$/) { register('flag', {src=>$&, flag=>$1}, $1); } +# elsif(/^ROLE (\S+)$/) { register('role', {src=>$&, role=>$1}, $1); } +# elsif(/^LEFT (\S+)$/) { register('left', {src=>$&, role=>$1}, 0); } +# elsif(/^RIGHT (\S+)$/) { register('right', {src=>$&, role=>$1}, 0); } +# elsif(/^SGL (\S+)$/) { register('sgl', {src=>$&, role=>$1}, 0); } +# elsif(/^REQ (\S+) (\S+)$/) { register('req', {src=>$&, cat=>$1, role=>$2}, 0); } +# elsif(/^AGR (\S+) (\S+)$/) { register('agr', {src=>$&, role=>$1, attr=>$2}, $1); } +# elsif(/^GOV (\S+) (\S+)$/) { register('gov', {src=>$&, role=>$1, cat=>$2, catexp=>attr::parse($2)}, $1); } +# elsif(/^INIT ($role_re)$/) { register('initr', {src=>$&, role=>$1}, 0); } +# elsif(/^FIN ($role_re)$/) { register('finr', {src=>$&, role=>$1}, 0); } +# elsif(/^INIT ($av_re)$/) { register('initf', {src=>$&, flag=>$1}, 0); } +# elsif(/^FIN ($av_re)$/) { register('finf', {src=>$&, flag=>$1}, 0); } +# elsif(/^SET ($cat_re)\s+(\S+)$/) { register('set', {src=>$&, cat=>$1, flag=>$2}, 0); } +# elsif(/^PASS (\S+)\s+(\S+)$/) { register('pass', {src=>$&, role=>$1, flag=>$2}, 0); } +# elsif(/^CONSTRE (\S+)\s+(\S+)$/) { register('constre', {src=>$&, role1=>$1, role2=>$2}, 0); } +# elsif(/^CONSTRI (\S+)\s+(\S+)$/) { register('constri', {src=>$&, role1=>$1, role2=>$2}, 0); } + +# elsif(my ($hs,$hfs,$ds,$dfs,$r,$rprops) = /^LINK\s+($cats_re)((?:;$avlist_re)?)\s+($cats_re)((?:;$avlist_re)?)\s+($role_re)((?:$proplist_re)?)$/) +# { register('link', {src=>$&, hs=>$hs, hfs=>$hfs, ds=>$ds, dfs=>$dfs, r=>$r, props=>$rprops},0) } +# elsif(/^LONG\s+(\S+)((\s+<\S+)*)((\s+\S+>)*)$/) +# { +# my $rel = $1; +# my $ups = $2; +# my $downs = $4; + +# $ups =~ s///g; +# $downs =~ s/^\s+//; +# my @down = split(/\s+/,$downs) or (); + +# register('long', {src=>$&, rel=>$rel, up=>\@up, down=>\@down},0); + +# print OUTPUT "LONG $rel " . join(",",@up) . "^" . join(",",@down) . "\n"; +# } +# elsif(my ($cl,$cs) = /^CLASS\s+(\S+)\s*\=(.*)$/) +# { +# $class{$1} = $classparser->classexpr($2); +# } +# elsif(/^$/) +# { +# # pomijamy puste linie oraz komentarze +# } +# else +# { +# print STDERR "Illegal format: $_\n"; +# } +# } + + + +# sub is_cat { shift =~ /$attr::cat_re/; } +# sub is_role { $role{shift}; } +# sub is_flag { $flag{shift}; } + + +# sub print_in +# { +# my $data = shift(); +# printf "in@%04d ", $data->{line}; +# print $data->{src}; +# } + +# sub print_out +# { +# printf "out@%08d ", $outline++; +# print @_; +# } + +# sub addlinks +# { +# my ($l, $h,$hfs,$d,$dfs,$r,$rprops) = @_; + +# my @heads = extension($h); +# my @deps = extension($d); + +# my @deps_gov; +# DEP_GOV: +# for my $dep (@deps) +# { +# for my $gov (@govs) +# { +# next DEP_GOV unless attr::match(@{$dep->{catexp}},@{$gov->{catexp}}); +# } +# push @deps_gov, $dep; +# } + +# for my $head (@heads) +# { +# DEP: +# for my $dep (@deps_gov) +# { +# for my $agr (@agrs) +# { +# next DEP unless attr::agree(@{$head->{catexp}},@{$dep->{catexp}},$agr->{attr}); +# } +# print_outin("LINK $head->{cat}$hfs $dep->{cat}$dfs $r$rprops",$l, @agrs,@govs); +# } +# } +# } + + + + # elsif(/^INIT\s+([[:upper:]]\S*)$/) # { @@ -251,223 +528,2 @@ # } # } - elsif(my ($hs,$hfs,$ds,$dfs,$r,$rprops) = /^LINK\s+($cats_re)((?:;$avlist_re)?)\s+($cats_re)((?:;$avlist_re)?)\s+($role_re)((?:$proplist_re)?)$/) - { - print OUTPUT "#$_\n"; - for my $h ($hs =~ /$attr::cat_re/g) - { - for my $d ($ds =~ /$attr::cat_re/g) - { - addlinks($h,$hfs,$d,$dfs,$r,$rprops); - } - } - } - # elsif(my ($hs,$ds,$fs,$r) = /^LINK\s+($cats_re)\s+($cats_re)\s+(\S+)\s+(\S+)$/) - # { - # print OUTPUT "#$_\n"; - # for my $h ($hs =~ /$attr::cat_re/g) - # { - # for my $d ($ds =~ /$attr::cat_re/g) - # { - # addlinks1($h,$d,$fs,$r); - # } - # } - # } - elsif(/^FLAG\s+\S+$/) - { - ++$nflag; - print OUTPUT "$_\n" - } - elsif(/^SET\s+(\S+)\s+(\S+)$/) - { - print OUTPUT "#$_\n"; - my $cat = attr::parse $1; - my $flag = $2; - for my $atomcat (keys %cats) - { - if(attr::match @$cat, @{$cats{$atomcat}}) - { - print OUTPUT "SET ".$atomcat." $flag\n"; - ++$nset; - } - } - } - elsif(/^PASS\s+\S+\s+\S+$/) - { - ++$npass; - print OUTPUT "$_\n" - } - elsif(/^CONSTR[IE]\s+\S+\s+\S+$/) - { - ++$nconstr; - print OUTPUT "$_\n" - } - elsif(/^LONG\s+(\S+)((\s+<\S+)*)((\s+\S+>)*)$/) - { - ++$nlong; - my $rel = $1; - my $ups = $2; - my $downs = $4; - - $ups =~ s///g; - $downs =~ s/^\s+//; - my @down = split(/\s+/,$downs); - print OUTPUT "LONG $rel " . join(",",@up) . "^" . join(",",@down) . "\n"; - } - elsif(my ($cl,$cs) = /^CLASS\s+(\S+)\s*\:\s*(.*)/) - { - print OUTPUT "#$_\n"; - for my $c ($cs =~ /\S+/g) - { - my $cat = attr::parse $c; - - for my $atomcat (sort(keys %cats)) - { - if(attr::match @$cat, @{$cats{$atomcat}}) - { - print OUTPUT "CLASS $cl $atomcat\n"; - ++$nclass; - } - } - } - } - elsif(/^$/) { - # pomijamy puste linie oraz komentarze - } - else - { - print STDERR "Illegal format: $_\n"; - } -} - - -sub addlinks -{ - my ($h,$hfs,$d,$dfs,$r,$rprops) = @_; - - for my $a (@{$agr{$r}}) { print OUTPUT "#AGR $r $a\n"; } - for my $c (@{$gov{$r}}) { print OUTPUT "#GOV $r ".attr::unparse(@$c)."\n"; } - my $head = attr::parse $h; - my $dep = attr::parse $d; - - for my $atomhead (keys %cats) - { - if(attr::match @$head, @{$cats{$atomhead}}) - { - DEP: - for my $atomdep (keys %cats) - { - next DEP if ! attr::match @$dep, @{$cats{$atomdep}}; - - for my $a (@{$agr{$r}}) - { - next DEP if ! attr::agree(@{$cats{$atomhead}},@{$cats{$atomdep}},$a); - } - - for my $c (@{$gov{$r}}) - { - next DEP if ! attr::match(@$c,@{$cats{$atomdep}}); - } - - print OUTPUT "LINK $atomhead$hfs $atomdep$dfs $r$rprops\n"; - ++$nlink; - - } - } - } -} - - -sub addlinks1 -{ - my ($h,$d,$fs,$r) = @_; - - for my $a (@{$agr{$r}}) { print OUTPUT "#AGR $r $a\n"; } - for my $c (@{$gov{$r}}) { print OUTPUT "#GOV $r ".attr::unparse(@$c)."\n"; } - my $head = attr::parse $h; - my $dep = attr::parse $d; - - for my $atomhead (keys %cats) - { - if(attr::match @$head, @{$cats{$atomhead}}) - { - DEP: - for my $atomdep (keys %cats) - { - next DEP if ! attr::match @$dep, @{$cats{$atomdep}}; - - for my $a (@{$agr{$r}}) - { - next DEP if ! attr::agree(@{$cats{$atomhead}},@{$cats{$atomdep}},$a); - } - - for my $c (@{$gov{$r}}) - { - next DEP if ! attr::match(@$c,@{$cats{$atomdep}}); - } - - print OUTPUT "LINK $atomhead $atomdep $fs $r\n"; - ++$nlink; - - } - } - } -} - - -printf STDERR "%6d CAT statements\n", 0+keys(%cats); -printf STDERR "%6d ROLE statements\n", 0+keys(%roles); -printf STDERR "%6d SGL statements\n", $nsgl; -printf STDERR "%6d REQ statements\n", $nreq; -printf STDERR "%6d LEFT statements\n", $nleft; -printf STDERR "%6d RIGHT statements\n", $nright; -printf STDERR "%6d INITR statements\n", $ninitr; -printf STDERR "%6d FINR statements\n", $nfinr; -printf STDERR "%6d INITF statements\n", $ninitf; -printf STDERR "%6d FINF statements\n", $nfinf; -printf STDERR "%6d INITC statements\n", $ninitc; -printf STDERR "%6d FINC statements\n", $nfinc; -printf STDERR "%6d LINK statements\n", $nlink; -printf STDERR "%6d CLASS statements\n", $nclass; -printf STDERR "%6d FLAG statements\n", $nflag; -printf STDERR "%6d SET statements\n", $nset; -printf STDERR "%6d PASS statements\n", $npass; - - -sub extractcats -{ - my $file = shift; - open DICFILE, "$file"; - while() - { - while(/,([^[:space:];]+)/g) - { - my $cat=$1; - next if !$cat || exists $cats{$cat}; - $ncat++; - print OUTPUT "CAT $1\n"; - $cats{$cat}=attr::parse($cat); - } - } - close DICFILE; -} - - -sub loadcats -{ - my $file = shift; - open CATFILE, "$file"; - while() - { - tr/ \t\n//d; - next if !$_ || exists $cats{$_}; - print OUTPUT "CAT $_\n"; - ++$ncat; - $cats{$_}=attr::parse($_); - } - close CATFILE; -} - Index: src/dgp/boubble.hh =================================================================== --- src/dgp/boubble.hh (revision e7de6cc88c605c4f810cbc852e843294b4b0e8ac) +++ src/dgp/boubble.hh (revision 3b02b04ff9c7c3446ca477cd84c2bc7f737c38b4) @@ -26,4 +26,5 @@ Boubble(list u, list d, LongRel l, int s=-1); Boubble(const char* pathstr, const char* l, int s=-1); + // Boubble(const Boubble& b) {_src=b._src; _upath=b._upath; _dpath=b._dpath; _rel=b._rel; }; Dir dir(); @@ -138,5 +139,5 @@ } - if(d==DOWN && _upath.empty() && !_dpath.empty()) + if(d==DOWN && _upath.empty() && !_dpath.empty() && _dpath.front() == r) { Boubble* newboubble = new Boubble(_upath,_dpath,_rel,_src); Index: src/dgp/dgp1.cc =================================================================== --- src/dgp/dgp1.cc (revision a15e59b825ae3aa1d5f3555afaf4cdbf22beda62) +++ src/dgp/dgp1.cc (revision 3b02b04ff9c7c3446ca477cd84c2bc7f737c38b4) @@ -10,4 +10,8 @@ list nodelist; list::iterator processed; + + +void print_sets(int n); + //==================================================================================================== @@ -44,5 +48,5 @@ ret.forbidden |= grammar.constr_exclude(link.role); - ret.boubbles=bs; + ret.boubbles.merge(bs); //DOBRZE ret.flags |= ( depflags & grammar.pass_flags(link.role) ); @@ -58,5 +62,5 @@ { NodeProp ret=depprop; - ret.boubbles=bs; + ret.boubbles.merge(bs); //DOBRZE return ret; } @@ -67,7 +71,22 @@ { MNode& mnode = mgraph[mnodeind]; + int ret=-1; for(vector::iterator ps=mnode.snodes.begin(); ps!=mnode.snodes.end(); ++ps) - if(sgraph[*ps].prop==p && sgraph[*ps].LH==newheadLH && sgraph[*ps].LV==newheadLV) return *ps; - return -1; + { + if(debug) fprintf(stderr,"#find existing node: checking %d ... \n", *ps); + if(sgraph[*ps].prop==p) + if(sgraph[*ps].LH==newheadLH && sgraph[*ps].LV==newheadLV) + { + ret = *ps; + // fprintf(stderr,"FIND EXISTING NODE SUCCEEDED BEACAUSE OF LH/LV equality ()\n"); + } + else + { + // fprintf(stderr,"FIND EXISTING NODE FAILED BEACAUSE OF LH/LV inequality\n"); + } + } + + if(debug) fprintf(stderr,"\n"); + return ret; } @@ -83,4 +102,5 @@ ret.push_back(new_boubble); } + return ret; } @@ -120,39 +140,67 @@ //==================================================================================================== -int create_new_head_node_left(list::iterator h, NodeProp& newheadprop, bitset& newheadLH, bitset& newheadLD, bitset& newheadLV) -{ - int newheadind = sgraph.clone(*h,newheadprop); - list::iterator nextit=h; ++nextit; - nodelist.insert(nextit,newheadind); +void copy_links(int i, int j) +{ + sgraph[j].heads = sgraph[i].heads; + sgraph[j].deps = sgraph[i].deps; +} + + +void create_reverse_links(int n) +{ + for(vector::iterator a=sgraph[n].heads.begin(); a != sgraph[n].heads.end(); a++) + sgraph[a->dst].deps.push_back(Arc(n,a->role,a->headanc,a->depanc)); + + for(vector::iterator a=sgraph[n].deps.begin(); a != sgraph[n].deps.end(); a++) + sgraph[a->dst].heads.push_back(Arc(n,a->role,a->headanc,a->depanc)); +} + +//==================================================================================================== + +int create_new_head_node_left(int h, NodeProp& newheadprop, bitset& newheadLH, bitset& newheadLD, bitset& newheadLV) +{ + int newheadind = sgraph.clone(h,newheadprop); + // list::iterator nextit=h; ++nextit; + // nodelist.insert(nextit,newheadind); + nodelist.push_back(newheadind); sgraph[newheadind].LH=newheadLH; sgraph[newheadind].LD = newheadLD; sgraph[newheadind].in_LH=true; sgraph[newheadind].LV.reset(); - - if(debug) sgraph.print_node_debug(stderr,"C ",newheadind,*h); - + + copy_links(h,newheadind); + create_reverse_links(newheadind); + + if(debug) sgraph.print_node_debug(stderr,"C ",newheadind,h); + if(debug) print_sets(newheadind); return newheadind; } -int create_new_dep_node_left(list::iterator d, NodeProp& prop, bitset& LH, bitset& LD, bitset& LV) -{ - int newind = sgraph.clone(*d,prop); - list::iterator nextit=d; ++nextit; - nodelist.insert(nextit,newind); +int create_new_dep_node_left(int d, NodeProp& prop, bitset& LH, bitset& LD, bitset& LV) +{ + int newind = sgraph.clone(d,prop); + // list::iterator nextit=d; ++nextit; + // nodelist.insert(nextit,newind); + nodelist.push_back(newind); sgraph[newind].LH.reset(); sgraph[newind].LD=LD; sgraph[newind].in_LH=false; //??????? sgraph[newind].LV.reset(); - - if(debug) sgraph.print_node_debug(stderr,"C ",newind,*d); + + copy_links(d,newind); + create_reverse_links(newind); + + if(debug) sgraph.print_node_debug(stderr,"C ",newind,d); + if(debug) print_sets(newind); return newind; } -int create_new_head_node_right(list::iterator h, NodeProp& newheadprop, bitset& newheadLH, bitset& newheadLD, bitset& newheadLV) -{ - int newheadind = sgraph.clone(*h,newheadprop); - list::iterator nextit=h; ++nextit; - nodelist.insert(nextit,newheadind); +int create_new_head_node_right(int h, NodeProp& newheadprop, bitset& newheadLH, bitset& newheadLD, bitset& newheadLV) +{ + int newheadind = sgraph.clone(h,newheadprop); + // list::iterator nextit=h; ++nextit; + // nodelist.insert(nextit,newheadind); + nodelist.push_back(newheadind); sgraph[newheadind].LH=newheadLH; sgraph[newheadind].LD=newheadLD; @@ -160,14 +208,17 @@ sgraph[newheadind].LV=newheadLV; - if(debug) sgraph.print_node_debug(stderr,"C ",newheadind,*h); + copy_links(h,newheadind); + create_reverse_links(newheadind); + + if(debug) sgraph.print_node_debug(stderr,"C ",newheadind,h); + if(debug) print_sets(newheadind); return newheadind; } -int create_new_dep_node_right(list::iterator d, NodeProp& prop, bitset& LH, bitset& LD, bitset& LV) -{ - int newind = sgraph.clone(*d,prop); - list::iterator nextit=d; ++nextit; - nodelist.insert(nextit,newind); +int create_new_dep_node_right(int d, NodeProp& prop, bitset& LH, bitset& LD, bitset& LV) +{ + int newind = sgraph.clone(d,prop); + nodelist.push_back(newind); sgraph[newind].LH=LH; sgraph[newind].LD=LD; @@ -175,5 +226,9 @@ sgraph[newind].LV.reset(); - if(debug) sgraph.print_node_debug(stderr,"C ",newind,*d); + copy_links(d,newind); + create_reverse_links(newind); + + if(debug) sgraph.print_node_debug(stderr,"C ",newind,d); + if(debug) print_sets(newind); return newind; @@ -182,9 +237,9 @@ //==================================================================================================== -void connect_left(list::iterator h, list::iterator d, const Link& l, list& new_head_boubbles, list& new_dep_boubbles) -{ - - NodeProp &oldheadprop = sgraph[*h].prop; - NodeProp &olddepprop = sgraph[*d].prop; +void connect_left(int h, int d, const Link& l, list& new_head_boubbles, list& new_dep_boubbles) +{ + + NodeProp &oldheadprop = sgraph[h].prop; + NodeProp &olddepprop = sgraph[d].prop; NodeProp newheadprop = compute_head_prop(oldheadprop,l,new_head_boubbles,olddepprop.flags); @@ -192,20 +247,25 @@ int newheadind; if(oldheadprop==newheadprop) - newheadind = *h; + newheadind = h; else { - bitset newheadLH = sgraph[*h].LH; - bitset newheadLV = sgraph[*d].LV; - bitset newheadLD = sgraph[*h].LD; - - newheadind = find_existing_node(sgraph[*h].mnode, newheadprop, newheadLH, newheadLV); - if( newheadind >= 0 ) + bitset newheadLH = sgraph[h].LH; + bitset newheadLV = sgraph[d].LV; + bitset newheadLD = sgraph[h].LD; + + // vector newedge; + + newheadind = find_existing_node(sgraph[h].mnode, newheadprop, newheadLH, newheadLV); + if( newheadind >= 0) // W£¡CZONE sgraph[newheadind].LD |= newheadLD; else - newheadind = create_new_head_node_left(h,newheadprop,newheadLH,newheadLD,newheadLV); + { + newheadind = create_new_head_node_left(h,newheadprop,newheadLH,newheadLD,newheadLV); + sgraph[newheadind].edge.clear(); + sgraph[newheadind].edge_contains_self = false; + } + } - - NodeProp newdepprop = compute_dep_prop(olddepprop,l,new_dep_boubbles); @@ -213,56 +273,74 @@ if(olddepprop==newdepprop) - newdepind = *d; + newdepind = d; else { - bitset newdepLH = sgraph[*d].LH; - bitset newdepLV = sgraph[*d].LV; - bitset newdepLD = sgraph[*d].LD; - - newdepind = find_existing_node(sgraph[*d].mnode, newdepprop, newdepLH, newdepLV); - if( newdepind >= 0 ) + bitset newdepLH = sgraph[d].LH; + bitset newdepLV = sgraph[d].LV; + bitset newdepLD = sgraph[d].LD; + + newdepind = find_existing_node(sgraph[d].mnode, newdepprop, newdepLH, newdepLV); + if( newdepind >= 0) // W£¡CZONE sgraph[newdepind].LD |= newdepLD; // TYLKO DLA LD else - newdepind = create_new_dep_node_left(d,newdepprop,newdepLH,newdepLD,newdepLV); + { + newdepind = create_new_dep_node_left(d,newdepprop,newdepLH,newdepLD,newdepLV); + sgraph[newdepind].edge.clear(); + //sgraph[newdepind].edge.push_back(newdepind); // TO + sgraph[newdepind].edge_contains_self = true; // LUB TO + } } - - sgraph[newheadind].deps.push_back(Arc(newdepind,l.role,*h,*d)); - - if(sgraph[*d].saturated()) sgraph[newheadind].LV |= sgraph[*d].LV; - - sgraph[newheadind].LD.set(*d); - if(sgraph[*d].saturated()) sgraph[newheadind].LD |= sgraph[*d].LD; - - if(debug) sgraph.print_arc(stderr,newheadind,*d,l.role,0); - if(debug) sgraph.print_node_debug(stderr,"U ",newheadind,*h); - if(debug) sgraph.print_node_debug(stderr,"U ",*d,*d); + + + sgraph[newheadind].deps.push_back(Arc(newdepind,l.role,h,d)); + sgraph[newdepind].heads.push_back(Arc(newheadind,l.role,h,d)); + sgraph[newheadind].edge.push_back(newdepind); + + if(sgraph[d].saturated()) sgraph[newheadind].LV |= sgraph[d].LV; + + sgraph[newheadind].LD.set(d); + if(sgraph[d].saturated()) sgraph[newheadind].LD |= sgraph[d].LD; + + if(debug) sgraph.print_arc(stderr,newheadind,d,l.role,0); + if(debug) sgraph.print_node_debug(stderr,"U ",newheadind,h); + if(debug) print_sets(newheadind); + if(debug) sgraph.print_node_debug(stderr,"U ",newdepind,d); + if(debug) print_sets(newdepind); } //---------------------------------------------------------------------------------------------------- -void connect_right(list::iterator h, list::iterator d, const Link& l, list& new_head_boubbles, list& new_dep_boubbles) -{ - NodeProp &oldheadprop = sgraph[*h].prop; - - NodeProp newheadprop = compute_head_prop(oldheadprop,l,new_head_boubbles, sgraph[*d].prop.flags); +void connect_right(int h, int d, const Link& l, list& new_head_boubbles, list& new_dep_boubbles) +{ + NodeProp &oldheadprop = sgraph[h].prop; + + NodeProp newheadprop = compute_head_prop(oldheadprop,l,new_head_boubbles, sgraph[d].prop.flags); int newheadind; if(oldheadprop==newheadprop) - newheadind = *h; + newheadind = h; else { - bitset newheadLH = sgraph[*h].LH; - bitset newheadLV = sgraph[*h].LV; - bitset newheadLD = sgraph[*h].LD; - - newheadind = find_existing_node(sgraph[*h].mnode, newheadprop, newheadLH, newheadLV); - if( newheadind >= 0 ) + bitset newheadLH = sgraph[h].LH; + bitset newheadLV = sgraph[h].LV; + bitset newheadLD = sgraph[h].LD; + + newheadind = find_existing_node(sgraph[h].mnode, newheadprop, newheadLH, newheadLV); + + if(debug) fprintf(stderr,"#HEAD EXISTS %d\n",newheadind); + + if( newheadind >= 0) // W£¡CZONE sgraph[newheadind].LD |= newheadLD; // TYLKO DLA LD else - newheadind = create_new_head_node_right(h,newheadprop,newheadLH,newheadLD,newheadLV); + { + newheadind = create_new_head_node_right(h,newheadprop,newheadLH,newheadLD,newheadLV); + //if(!sgraph[h].edge.empty()) sgraph[newheadind].edge.push_back(newheadind); // TO + sgraph[newheadind].edge_contains_self = sgraph[h].edge_contains_self; // LUB TO + sgraph[newheadind].visible_as_neighbour = false; + } } - NodeProp &olddepprop = sgraph[*d].prop; + NodeProp &olddepprop = sgraph[d].prop; NodeProp newdepprop = compute_dep_prop(olddepprop,l,new_dep_boubbles); @@ -270,22 +348,29 @@ if(olddepprop==newdepprop) - newdepind = *d; + newdepind = d; else { - bitset newdepLH = sgraph[*d].LH; - bitset newdepLV = sgraph[*d].LV; - bitset newdepLD = sgraph[*d].LD; - - newdepind = find_existing_node(sgraph[*d].mnode, newdepprop, newdepLH, newdepLV); - if( newdepind >= 0 ) + bitset newdepLH = sgraph[d].LH; + bitset newdepLV = sgraph[d].LV; + bitset newdepLD = sgraph[d].LD; + + newdepind = find_existing_node(sgraph[d].mnode, newdepprop, newdepLH, newdepLV); + + if(debug) fprintf(stderr,"#DEP EXISTS %d\n",newdepind); + + if( newdepind >= 0) // W£¡CZONE sgraph[newdepind].LD |= newdepLD; // TYLKO DLA LD else - newdepind = create_new_dep_node_right(d,newdepprop,newdepLH,newdepLD,newdepLV); + { + newdepind = create_new_dep_node_right(d,newdepprop,newdepLH,newdepLD,newdepLV); + sgraph[newdepind].edge.clear(); + sgraph[newdepind].edge_contains_self = false; + } } - - - sgraph[newdepind].heads.push_back(Arc(newheadind,l.role,*h,*d)); + sgraph[newdepind].heads.push_back(Arc(newheadind,l.role,h,d)); + sgraph[newheadind].deps.push_back(Arc(newdepind,l.role,h,d)); + //sgraph[newdepind].edge.push_back(newheadind); sgraph[newdepind].LH.set(newheadind); @@ -296,6 +381,6 @@ if(debug) sgraph.print_arc(stderr,newheadind,newdepind,l.role,1); - if(debug) sgraph.print_node_debug(stderr,"U ",newheadind,*h); - if(debug) sgraph.print_node_debug(stderr,"U ",newdepind,*d); + if(debug) sgraph.print_node_debug(stderr,"U ",newheadind,h); + if(debug) sgraph.print_node_debug(stderr,"U ",newdepind,d); } @@ -323,22 +408,18 @@ } -// bool check_boubbles_at_target(list boubbles, int node) -// { -// for(list::iterator b = boubbles.begin(); b != boubbles.end(); ++b ) -// if( (*b)->is_at_target() && !grammar.check_longrel(sgraph.cat((*b)->src()), sgraph.cat(node), (*b)->rel()) ) -// return false; -// return true; -// } - -//==================================================================================================== - -void try_connect_dependents(list::iterator j) -{ - for(list::iterator i(j); i!=nodelist.begin(); --i) - if(sgraph.visible(*i,*j) && sgraph.saturated(*i)) - { - if(debug) {fprintf(stderr,"## %d <-- %d ... ",*i,*j); } - - list ji_links = grammar.connectable2( sgraph.cat(*j), sgraph.cat(*i), sgraph[*j].prop.flags, sgraph[*i].prop.flags); // ref do Roles!!! +//==================================================================================================== + +void try_connect_dependents(int j) +{ + // for(list::iterator i(j); i!=nodelist.begin(); --i) + // if(sgraph.visible(*i,*j) && sgraph.saturated(*i)) + LViterator lvi(sgraph,j); + int i; + while((i=lvi.next()) >= 0) + if(sgraph.saturated(i)) + { + if(debug) {fprintf(stderr,"## %d <-- %d ... ",i,j); } + + list ji_links = grammar.connectable2( sgraph.cat(j), sgraph.cat(i), sgraph[j].prop.flags, sgraph[i].prop.flags); // ref do Roles!!! list::iterator ri = ji_links.begin(); if(ri == ji_links.end()) { if(debug) fprintf(stderr,"no roles\n"); } @@ -346,12 +427,12 @@ { for(; ri != ji_links.end(); ++ri ) - if(!grammar.check_constr2(sgraph[*j].prop,sgraph[*i].prop,0,**ri )) + if(!grammar.check_constr2(sgraph[j].prop,sgraph[i].prop,0,**ri )) { if(debug) fprintf(stderr,"constraints failed\n"); } else { - list new_head_boubbles = collect_head_boubbles(*j,*i,(*ri)->role); - list new_dep_boubbles = collect_dep_boubbles(*j,*i,(*ri)->role); + list new_head_boubbles = collect_head_boubbles(j,i,(*ri)->role); + list new_dep_boubbles = collect_dep_boubbles(j,i,(*ri)->role); - if( !(check_boubbles_at_target(new_head_boubbles,*j) && check_boubbles_at_target(new_dep_boubbles,*i)) ) + if( !(check_boubbles_at_target(new_head_boubbles,j) && check_boubbles_at_target(new_dep_boubbles,i)) ) { if(debug) fprintf(stderr,"boubbles failed\n"); } else @@ -368,12 +449,17 @@ //---------------------------------------------------------------------------------------------------- -void try_connect_heads(list::iterator j) -{ - for(list::iterator i(j); i!=nodelist.begin(); --i) - if(sgraph.visible(*i,*j)) - { - if(debug) fprintf(stderr, "## %d --> %d ... ",*i,*j); - - list ij_links = grammar.connectable2( sgraph.cat(*i), sgraph.cat(*j), sgraph[*i].prop.flags, sgraph[*j].prop.flags ); +void try_connect_heads(int j) +{ + // for(list::iterator i(j); i!=nodelist.begin(); --i) + // if(sgraph.visible(*i,*j) && sgraph.saturated(*j)) + + LViterator lvi(sgraph,j); + int i; + while((i=lvi.next()) >= 0) + if(sgraph.saturated(j)) + { + if(debug) fprintf(stderr, "## %d --> %d ... ",i,j); + + list ij_links = grammar.connectable2( sgraph.cat(i), sgraph.cat(j), sgraph[i].prop.flags, sgraph[j].prop.flags ); list::iterator ri = ij_links.begin(); if(ri == ij_links.end()) { if(debug) fprintf(stderr,"no roles\n"); } @@ -381,12 +467,12 @@ { for(; ri != ij_links.end(); ++ri ) - if( !grammar.check_constr2( sgraph[*i].prop, sgraph[*j].prop, 1, **ri ) ) + if( !grammar.check_constr2( sgraph[i].prop, sgraph[j].prop, 1, **ri ) ) { if(debug) fprintf(stderr,"constraints failed\n"); } else { - list new_head_boubbles = collect_head_boubbles(*i,*j,(*ri)->role); - list new_dep_boubbles = collect_dep_boubbles(*i,*j,(*ri)->role); + list new_head_boubbles = collect_head_boubbles(i,j,(*ri)->role); + list new_dep_boubbles = collect_dep_boubbles(i,j,(*ri)->role); - if( !(check_boubbles_at_target(new_head_boubbles,*i) && check_boubbles_at_target(new_dep_boubbles,*j)) ) + if( !(check_boubbles_at_target(new_head_boubbles,i) && check_boubbles_at_target(new_dep_boubbles,j)) ) { if(debug) fprintf(stderr,"boubbles failed\n"); } else @@ -399,5 +485,60 @@ } } - + +//==================================================================================================== + +void update_sets() +{ + for(int n=0; n=0) + { + // printf(" %d",i); + sgraph[n].LV.set(i); + } + // printf("\n"); + + while((i=lhi.next())>=0) sgraph[n].LH.set(i); + while((i=ldi.next())>=0) sgraph[n].LD.set(i); + } +} + +//==================================================================================================== + +void print_sets(int n) +{ + LViterator lvi(sgraph,n); + LHiterator lhi(sgraph,n); + LDiterator ldi(sgraph,n); + + int i; + printf("LV[%d]: ",n); + while((i=lvi.next())>=0) + { + printf("%d ",i); + sgraph[n].LV.set(i); + } + + printf("LH[%d]: ",n); + while((i=lhi.next())>=0) + { + printf("%d ",i); + sgraph[n].LH.set(i); + } + printf("LD[%d]: ",n); + while((i=ldi.next())>=0) + { + printf("%d ",i); + sgraph[n].LD.set(i); + } + printf("\n"); +} + //==================================================================================================== @@ -430,15 +571,18 @@ nodelist.push_back(basenode); - if(debug) {sgraph.print_node_debug(stderr,"B ",basenode,-1);} // STDOUT!!! + if(debug) sgraph.print_node_debug(stderr,"B ",basenode,-1); // STDOUT!!! + if(debug) print_sets(basenode); list::iterator cursor=processed; while(++cursor != nodelist.end()) { - try_connect_dependents(cursor); - try_connect_heads(cursor); + if(debug) sgraph.print_node_debug(stderr,"> ",*cursor,-1); + try_connect_dependents(*cursor); + try_connect_heads(*cursor); processed=cursor; } } - reverse_links(); -} + // reverse_links(); + update_sets(); +} Index: src/dgp/grammar.cc =================================================================== --- src/dgp/grammar.cc (revision a15e59b825ae3aa1d5f3555afaf4cdbf22beda62) +++ src/dgp/grammar.cc (revision 3b02b04ff9c7c3446ca477cd84c2bc7f737c38b4) @@ -298,10 +298,35 @@ { char cat1[MAXLINE],flags1[MAXLINE],cat2[MAXLINE],flags2[MAXLINE],type[MAXLINE],props[MAXLINE]; - - if(sscanf(arg1,"%[^;];%s",cat1,flags1)==1) *flags1='\0'; - if(sscanf(arg2,"%[^;];%s",cat2,flags2)==1) *flags2='\0'; - if(sscanf(arg3,"%[^&]%s",type,props)==1) *props='\0'; + char* double_slash_position; + // pierwszy argument + // if(sscanf(arg1,"%[^;];%s",cat1,flags1)==1) *flags1='\0'; + if((double_slash_position=strstr(arg1,"//")) != NULL) // czy s± flagi + { + int cat_length=double_slash_position-arg1; + strncpy(cat1, arg1, cat_length); cat1[cat_length]='\0'; + strcpy(flags1, arg1+cat_length+2); + } + else + { + strcpy(cat1, arg1); + flags1[0]='\0'; + } + // drugi argument + // if(sscanf(arg2,"%[^;];%s",cat2,flags2)==1) *flags2='\0'; + if((double_slash_position=strstr(arg2,"//")) != NULL) // czy s± flagi + { + int cat_length=double_slash_position-arg2; + strncpy(cat2, arg2, cat_length); cat2[cat_length]='\0'; + strcpy(flags2, arg2+cat_length+2); + } + else + { + strcpy(cat2,arg2); + flags2[0]='\0'; + } + // trzeci argument + if(sscanf(arg3,"%[^&]%s",type,props)==1) props[0]='\0'; - // printf("line=%s\n\tcat1=%s flags1=%s cat2=%s flags2=%s type=%s props=%s\n",line,cat1,flags1,cat2,flags2,type,props); + // printf("line=%s\n\tcat1=<%s> flags1=%s cat2=<%s> flags2=%s type=<%s> props=%s\n",line,cat1,flags1,cat2,flags2,type,props); if( chk_cat(cat1) && chk_cat(cat2) && chk_type(type) ) @@ -346,5 +371,5 @@ // compute_gt(); - + return true; Index: src/dgp/main.cc =================================================================== --- src/dgp/main.cc (revision a15e59b825ae3aa1d5f3555afaf4cdbf22beda62) +++ src/dgp/main.cc (revision 3b02b04ff9c7c3446ca477cd84c2bc7f737c38b4) @@ -38,4 +38,5 @@ bool printtimeinfo=false; + void output(); @@ -43,4 +44,5 @@ { gengetopt_args_info args; + struct timeval readgrammar_starttime,readgrammar_endtime; if(cmdline_parser(argc,argv,&args) != 0) @@ -71,11 +73,19 @@ } + gettimeofday(&readgrammar_starttime,NULL); + grammar.read(grammarf); fclose(grammarf); + gettimeofday(&readgrammar_endtime,NULL); + if(printtimeinfo) + fprintf(stderr,"### START TIME: %10.2fms\n", (float)MICROSECONDSELAPSED(readgrammar_starttime,readgrammar_endtime)/1000 ); +//////////////////////////////////////////////////////////////////////////////////////////////////// +// TESTOWANIE POPRAWNOŠCI ODCZYTU GRAMATYKI // grammar.write(cout); // exit(0); +//////////////////////////////////////////////////////////////////////////////////////////////////// struct timeval starttime,afterinput,afterparse,endtime; @@ -101,5 +111,7 @@ { gettimeofday(&afterinput,NULL); + dgp1(); // parametry!!! MGraph, SGraph, Grammar + gettimeofday(&afterparse,NULL); output(); Index: src/dgp/sgraph.cc =================================================================== --- src/dgp/sgraph.cc (revision a15e59b825ae3aa1d5f3555afaf4cdbf22beda62) +++ src/dgp/sgraph.cc (revision 3b02b04ff9c7c3446ca477cd84c2bc7f737c38b4) @@ -28,4 +28,6 @@ newnode.in_LH=true; + newnode.edge.push_back(lastnodeind()); + return lastnodeind(); } @@ -55,6 +57,4 @@ SNode &newnode=makenewnode(); SNode &ancnode = nodes[ancind]; - - newnode.prop=newprop; @@ -178,4 +178,9 @@ buf+=sprint_node(buf,n,anc,HEADS|DEPS|SETS|CONSTRAINTS); + + buf+=sprintf(buf,"/"); + for(vector::iterator e = nodes[n].edge.begin(); e != nodes[n].edge.end(); e++ ) + buf += sprintf(buf,"%d ", *e); + buf+=sprintf(buf,"\n"); return buf-buf0; Index: src/dgp/sgraph.hh =================================================================== --- src/dgp/sgraph.hh (revision e7de6cc88c605c4f810cbc852e843294b4b0e8ac) +++ src/dgp/sgraph.hh (revision 3b02b04ff9c7c3446ca477cd84c2bc7f737c38b4) @@ -7,4 +7,5 @@ #include #include +#include #include "const.hh" @@ -71,16 +72,12 @@ if(init_attached != p.init_attached) return false; if(fin_attached != p.fin_attached) return false; - - list::const_iterator b1 = p.boubbles.begin(); - for(list::const_iterator b = boubbles.begin(); b != boubbles.end(); b++) - { - if(b1 == p.boubbles.end()) - return false; - if(!(**b == **b1)) - return false; - } - if(b1 != p.boubbles.end()) + + list::const_iterator b,b1; + for(b=boubbles.begin(), b1=p.boubbles.begin(); b != boubbles.end() && b1 != p.boubbles.end(); b++,b1++) + if(!(**b == **b1)) + return false; + if(b != boubbles.end() || b1 != p.boubbles.end()) return false; - + return true; } @@ -172,7 +169,13 @@ { + SNode() { visible_as_neighbour = true; } + int mnode; NodeProp prop; + + vector edge; + bool edge_contains_self; + bool visible_as_neighbour; bitset LV; @@ -231,4 +234,9 @@ int size() {return nodes.size(); } + friend class LViterator; + friend class LHiterator; + friend class LDiterator; + friend class LNiterator; + private: @@ -259,4 +267,274 @@ //---------------------------------------------------------------------------------------------------- +//---------------------------------------------------------------------------------------------------- + +class XXiterator +{ +protected: + + bool checked(int i) { return _checked[i]; } + void check(int i) { _checked.set(i); } + + void push(stack& s, int i) + { + if(!checked(i)) + { + s.push(i); + check(i); + } + } + + bitset _checked; +}; + +//---------------------------------------------------------------------------------------------------- +//---------------------------------------------------------------------------------------------------- + +class LViterator : public XXiterator +{ +public: + LViterator(SGraph& sg, int n, bool s); + int next(); + +private: + + SGraph& sgraph; + MGraph& mgraph; + stack waydown; + stack wayup; + bool strict; + + void push_ld(int i); + void push_lh(int i); + void push_ln(int i); +}; + +inline LViterator::LViterator(SGraph& sg, int n, bool s=true) : sgraph(sg), mgraph(sg.mgraph), strict(s) +{ + if(sg[n].edge_contains_self) // TO DODAÆ PO PRZEJŠCIU NA EDGE_CONTAINS_SELF + { + push_ld(n); + push_ln(n); + } + + for(vector::iterator i=sg[n].edge.begin(); i!=sg[n].edge.end(); ++i) + { + if(*i != n) + { + push_ld(*i); + push_ln(*i); + } + + } + // if(!strict) + // { + // push_ld(n); + // push_ln(n); + // } +} + +inline int LViterator::next() +{ + if(wayup.empty()) + { + if(waydown.empty()) + return -1; // + else + { + int k = waydown.top(); + waydown.pop(); + push_ld(k); + push_ln(k); + if(wayup.empty()) + return -1; // k NIE MA POPRZEDNIKÓW, NIE MO¯E TE¯ ZATEM MIEÆ LEWOSTRONNYCH PODRZÊDNIKÓW + else + { + int i = wayup.top(); + wayup.pop(); + push_lh(i); + return i; + } + } + + } + else + { + int i = wayup.top(); + wayup.pop(); + push_lh(i); + return i; + }; +} + +inline void LViterator::push_ld(int i) +{ + vector& arcs = sgraph[i].deps; + for(vector::iterator a = arcs.begin(); a != arcs.end(); ++a) + if(mgraph[sgraph[a->dst].mnode].pos < mgraph[sgraph[i].mnode].pos) + push(waydown,a->dst); +} + +inline void LViterator::push_lh(int i) +{ + vector& arcs = sgraph[i].heads; + for(vector::iterator a = arcs.begin(); a != arcs.end(); ++a) + if(mgraph[sgraph[a->dst].mnode].pos < mgraph[sgraph[i].mnode].pos) + push(wayup,a->dst); +} + +inline void LViterator::push_ln(int i) +{ + vector& mpredecessors = mgraph[sgraph[i].mnode].pred; + for(vector::iterator mp = mpredecessors.begin(); mp != mpredecessors.end(); ++mp) // poprzedniki w mgraph + { + vector& spredecessors = mgraph[*mp].snodes; + for(vector::iterator sp = spredecessors.begin(); sp != spredecessors.end(); ++sp ) + if(sgraph[*sp].visible_as_neighbour || !strict) + push(wayup,*sp); + } +} + + +//---------------------------------------------------------------------------------------------------- +//---------------------------------------------------------------------------------------------------- + +class LNiterator +{ +public: + LNiterator(SGraph& sg, int n); + + int next(); + +private: + + SGraph& sgraph; + MGraph& mgraph; + int thenode; + stack wayup; + + void push_ln(int i); +}; + +inline LNiterator::LNiterator(SGraph& sg, int n) : sgraph(sg), mgraph(sg.mgraph), thenode(n) +{ + push_ln(n); +} + +inline int LNiterator::next() +{ + if(wayup.empty()) + return -1; + else + { + int i = wayup.top(); + wayup.pop(); + return i; + }; +} + +inline void LNiterator::push_ln(int i) +{ + vector& mpredecessors = mgraph[sgraph[i].mnode].pred; + for(vector::iterator mp = mpredecessors.begin(); mp != mpredecessors.end(); ++mp) // poprzedniki w mgraph + { + vector& spredecessors = mgraph[*mp].snodes; + for(vector::iterator sp = spredecessors.begin(); sp != spredecessors.end(); ++sp ) + wayup.push(*sp); + } +} + + +//---------------------------------------------------------------------------------------------------- +//---------------------------------------------------------------------------------------------------- + +class LHiterator +{ +public: + LHiterator(SGraph& sg, int n); + + int next(); + +private: + + SGraph& sgraph; + MGraph& mgraph; + stack wayup; + + void push_lh(int i); +}; + +inline LHiterator::LHiterator(SGraph& sg, int n) : sgraph(sg), mgraph(sg.mgraph) +{ + push_lh(n); +} + +inline int LHiterator::next() +{ + if(wayup.empty()) + return -1; + else + { + int i = wayup.top(); + wayup.pop(); + push_lh(i); + return i; + }; +} + +inline void LHiterator::push_lh(int i) +{ + vector& arcs = sgraph[i].heads; + for(vector::iterator a = arcs.begin(); a != arcs.end(); ++a) + if(mgraph[sgraph[a->dst].mnode].pos < mgraph[sgraph[i].mnode].pos) + wayup.push(a->dst); +} + +//---------------------------------------------------------------------------------------------------- +//---------------------------------------------------------------------------------------------------- + +class LDiterator +{ +public: + LDiterator(SGraph& sg, int n); + + int next(); + +private: + + SGraph& sgraph; + MGraph& mgraph; + int thenode; + stack waydown; + + void push_ld(int i); +}; + +inline LDiterator::LDiterator(SGraph& sg, int n) : sgraph(sg), mgraph(sg.mgraph), thenode(n) +{ + push_ld(n); +} + +inline int LDiterator::next() +{ + if(waydown.empty()) + return -1; + else + { + int k = waydown.top(); + waydown.pop(); + push_ld(k); + return k; + } +} + +inline void LDiterator::push_ld(int i) +{ + vector& arcs = sgraph[i].deps; + for(vector::iterator a = arcs.begin(); a != arcs.end(); ++a) + if(mgraph[sgraph[a->dst].mnode].pos < mgraph[sgraph[thenode].mnode].pos) + waydown.push(a->dst); +} + + #endif Index: src/grp/grp =================================================================== --- src/grp/grp (revision 5f4d9c3b32eea7b6643a751aa75bdb05b7d41576) +++ src/grp/grp (revision 3b02b04ff9c7c3446ca477cd84c2bc7f737c38b4) @@ -13,5 +13,5 @@ my $LIB_DIR="/usr/local/lib/utt"; -my $systemconfigfile="/usr/local/etc/utt/grp.conf"; +my $systemconfigfile="/etc/utt/grp.conf"; my $userconfigfile=home()."/.utt/grp.conf"; Index: src/tre/tre =================================================================== --- src/tre/tre (revision e7de6cc88c605c4f810cbc852e843294b4b0e8ac) +++ src/tre/tre (revision 3b02b04ff9c7c3446ca477cd84c2bc7f737c38b4) @@ -156,5 +156,7 @@ for t in trees $count += 1 - t1=ground(t) + # t1=ground(t) + + t1=t span = $FOREST ? " span:" + (ground_tree_min(t1).to_s + ","+ground_tree_max(t1).to_s)+";" : "" @@ -170,5 +172,5 @@ when /h/ print "#\n# tree #{$count}\n# ------\n" - printtree(t1[0],t1[1],0) + printtree_dgp(t1[0],t1[1],0) end end @@ -178,18 +180,19 @@ def nodeinfo(id) info="" + gphid = $gphid[id] if $INFO =~ /o/ - info += $ord1[id].to_s + info += $ord1[gphid].to_s + '/' + gphid.to_s + '/' + id.to_s info += '.' if $INFO =~ /[nfm]/ end if $INFO =~ /n/ - info += id.to_s + info += gphid.to_s info += '.' if $INFO =~ /[fm]/ end if $INFO =~ /f/ - info += $form[id] + info += $form[gphid] info += ';' if $INFO =~ /m/ end if $INFO =~ /m/ - info += $lem[id] + info += $lem[gphid] end info @@ -215,4 +218,16 @@ print "%-16s" % (arc[2]+": ") printtree(arc[1],arcs,o+1) + end +end + +def printtree_dgp(root,arcs,o) + if o==0 + print "%-16s" % "root: " + end + print nodeinfo(root),"\n" + for arc in arcs.select{ |a| a[0]==root }.sort{|a,b| a[1]<=>b[1] } + print " "*(o+1) + print "%-16s" % (arc[2]+": ") + printtree_dgp(arc[1],arcs,o+1) end end @@ -341,5 +356,5 @@ def gentrees2 bos, eos $thetrees=[]; - roots = (1...eos).select{|i| $vis.include? [i,eos]}.select{|i| $vis.include? [bos,i]} + roots = (bos..eos).select{|i| $vis.include? [i,eos]}.select{|i| $vis.include? [bos,i]} if $DEBUG then print "ROOTS: #{roots.inspect}\n" end @@ -363,7 +378,8 @@ if $DEBUG then print "buildR--#{min}--#{max}--#{tree.inspect}\n" end trees=[] - for a in $arcs.select{|a| a[0]==max && $vis.include?([min,a[1]]) } - if $DEBUG then print "ARC: #{a.inspect}\n" end - for r in buildR(a[4],a[3],tree+[a]) #!!! buildR(a[1],a[3],tree+[a]) + for arc in $arcs.select{|a| a[0]==max && $vis.include?([min,a[1]]) } + if $DEBUG then print "ARC: #{arc.inspect}\n" end + for r in buildR(arc[1],arc[0],tree+[arc]) #!!! buildR(a[1],a[3],tree+[a]) + # for r in buildR(arc[4],arc[3],tree+[arc]) #!!! buildR(a[1],a[3],tree+[a]) (rmin,rmax,rarcs) = r for l in buildR(min,rmin,rarcs) @@ -395,5 +411,6 @@ for arc in $arcs.select{|a| a[1]==max && $lhs.include?([min,a[0]]) } if $DEBUG then print "ARC: #{arc.inspect}\n" end - for r in buildR(arc[3],arc[4],tree+[arc]) ### buildR(arc[3],max,tree+[arc]) + for r in buildR(arc[0],arc[1],tree+[arc]) ### buildR(arc[3],max,tree+[arc]) + #for r in buildR(arc[3],arc[4],tree+[arc]) ### buildR(arc[3],max,tree+[arc]) (rmin,rmax,rarcs) = r for l in buildL(min,rmin,rarcs)