Index: src/dgp/Makefile =================================================================== --- src/dgp/Makefile (revision 5f4d9c3b32eea7b6643a751aa75bdb05b7d41576) +++ src/dgp/Makefile (revision e7de6cc88c605c4f810cbc852e843294b4b0e8ac) @@ -1,3 +1,5 @@ + include ../../config.mak + SHELL = /bin/sh @@ -6,13 +8,10 @@ CMDLINE_FILE='"../dgp/cmdline.h"' + #vpath %.o . -ifeq ($(BUILD_STATIC), yes) - LDFLAGS += -static -endif +CXXFLAGS = -g -static -CXXFLAGS += -O2 - -sources = main.cc grammar.cc symbol.cc mgraph.cc sgraph.cc dgp0.cc cmdline.cc \ +sources = main.cc grammar.cc symbol.cc mgraph.cc sgraph.cc dgp1.cc cmdline.cc \ $(COMMON_PATH)/common.cc global.cc @@ -23,10 +22,10 @@ ${bin}: ${objs} - $(CXX) $(CXXFLAGS) -D _CMDLINE_FILE=$(CMDLINE_FILE) -o $@ ${objs} $(LDFLAGS) + ${CXX} ${CXXFLAGS} -D _CMDLINE_FILE=$(CMDLINE_FILE) -o $@ ${objs} include $(sources:.cc=.d) %.o: %.cc - $(CXX) -D _CMDLINE_FILE=$(CMDLINE_FILE) -c ${CXXFLAGS} -o $@ $< + ${CXX} -D _CMDLINE_FILE=$(CMDLINE_FILE) -c ${CXXFLAGS} -o $@ $< %.d: %.cc @@ -35,22 +34,22 @@ rm -f $@.$$$$ -# stare: -# cmdline.cc cmdline.h : cmdline.ggo -# gengetopt --c-extension=cc -i cmdline.ggo -# nowe + cmdline.cc cmdline.h: cmdline.ggo - $(GENGETOPT) -i cmdline.ggo --c-extension=cc --conf-parser + gengetopt -i cmdline.ggo --c-extension=cc --conf-parser cmdline.ggo: cmdline_dgp.ggo ../common/cmdline_common.ggo cat cmdline_dgp.ggo ../common/cmdline_common.ggo > cmdline.ggo -# endnowe + +.PHONY: clean clean: - rm ${bin} ${objs} cmdline.cc cmdline.h - rm -rf *.d + rm -f ${bin} ${objs} cmdline.* + rm -f *.d +.PHONY: prof prof: dgp gprof dgp ~/tmp/dgp-pl/gmon.out > dgp.prof + .PHONY: install @@ -58,7 +57,4 @@ ifdef BIN_DIR install -m 0755 dgp $(BIN_DIR) - install -m 0755 dgc $(BIN_DIR) - install -m 0755 canonize $(BIN_DIR) - install -m 0755 tre $(BIN_DIR) endif @@ -67,6 +63,3 @@ ifdef BIN_DIR rm $(BIN_DIR)/dgp - rm $(BIN_DIR)/dgc - rm $(BIN_DIR)/canonize - rm $(BIN_DIR)/tre endif Index: src/dgp/Makefile.user =================================================================== --- src/dgp/Makefile.user (revision 5f4d9c3b32eea7b6643a751aa75bdb05b7d41576) +++ (revision ) @@ -1,3 +1,0 @@ - -gram.dgp: gram.dgc - dgc -c cats.dgc < gram.dgc > gram.dgp Index: src/dgp/boubble.cc =================================================================== --- src/dgp/boubble.cc (revision e7de6cc88c605c4f810cbc852e843294b4b0e8ac) +++ src/dgp/boubble.cc (revision e7de6cc88c605c4f810cbc852e843294b4b0e8ac) @@ -0,0 +1,21 @@ + +#include "boubble.hh" + + + + + +Boubble mktestboubble() +{ + + Role::add("conj"); + Role::add("ccmpl"); + + list ul,dl; + dl.push_back(Role("conj")); + dl.push_back(Role("ccmpl")); + + + BoubbleAction act; + Boubble* b0 = new Boubble(ul,dl, act); +} Index: src/dgp/boubble.hh =================================================================== --- src/dgp/boubble.hh (revision e7de6cc88c605c4f810cbc852e843294b4b0e8ac) +++ src/dgp/boubble.hh (revision e7de6cc88c605c4f810cbc852e843294b4b0e8ac) @@ -0,0 +1,223 @@ +#ifndef _BOUBBLE_HH_ +#define _BOUBBLE_HH_ + +#include +#include +#include + +#include "thesymbols.hh" + + +enum Dir {UP=0,DOWN=1,AT_TARGET=2}; + +// class BoubbleAction +// { +// public: +// void apply() {}; +// private: + +// }; + + + +class Boubble +{ +public: + Boubble(list u, list d, LongRel l, int s=-1); + Boubble(const char* pathstr, const char* l, int s=-1); + + Dir dir(); + LongRel rel(); + int src(); + void src(int s); + + Role next(); + + Boubble* step(Role r, Dir d); + + bool is_at_target(); + + bool operator==(Boubble const& b) const; + bool operator!=(Boubble const& b) const; + bool operator<(Boubble const& b) const; + + void as_cstr(char* s); + friend std::ostream& operator<<(std::ostream&, const Boubble&); + +private: + + int _src; + list _upath; + list _dpath; + LongRel _rel; + +}; + +//---------------------------------------------------------------------------------------------------- + +inline +Boubble::Boubble(list u, list d, LongRel l, int s) : _upath(u), _dpath(d), _rel(l), _src(s) {} + +//---------------------------------------------------------------------------------------------------- + +inline +Boubble::Boubble(const char* pathstr, const char* l, int s) +{ + Dir dir = UP; + const char* p = pathstr; + while(*p) + { + if(*p=='^') { dir = DOWN; p++; } + else if(isalpha(*p)) + { + char buf[80]; + sscanf(p,"%[a-zA-Z0-9_]",buf); + dir == UP ? _upath.push_back(Role(buf)) : _dpath.push_back(Role(buf)); + p += strlen(buf); + } + else + p++; + } + + _rel = LongRel(l); + _src = s; +} + +//---------------------------------------------------------------------------------------------------- + +inline +Dir Boubble::dir() +{ + if(!_upath.empty()) + return UP; + else if(!_dpath.empty()) + return DOWN; + else return AT_TARGET; +} + +//---------------------------------------------------------------------------------------------------- + +inline +LongRel Boubble::rel() +{ return _rel; } + +//---------------------------------------------------------------------------------------------------- + +inline +int Boubble::src() +{ return _src; } + +//---------------------------------------------------------------------------------------------------- + +inline +void Boubble::src(int s) +{ _src=s; } + +//---------------------------------------------------------------------------------------------------- + +inline +Role Boubble::next() +{ + if(!_upath.empty()) + return _upath.front(); + else if(!_dpath.empty()) + return _dpath.front(); + else return Role("NULL"); +} + +//---------------------------------------------------------------------------------------------------- + +inline +Boubble* Boubble::step(Role r, Dir d) +{ + if(d==UP && !_upath.empty() && _upath.front() == r) + { + Boubble* newboubble = new Boubble(_upath,_dpath,_rel,_src); + newboubble->_upath.pop_front(); + return newboubble; + } + + if(d==DOWN && _upath.empty() && !_dpath.empty()) + { + Boubble* newboubble = new Boubble(_upath,_dpath,_rel,_src); + newboubble->_dpath.pop_front(); + return newboubble; + } + return NULL; +} + +//---------------------------------------------------------------------------------------------------- + +inline +bool Boubble::is_at_target() +{ return _upath.empty() && _dpath.empty(); } + +//---------------------------------------------------------------------------------------------------- + +inline +bool Boubble::operator==(Boubble const& b) const +{ + return _src==b._src && _upath==b._upath && _dpath==b._dpath && _rel==b._rel; +} + +//---------------------------------------------------------------------------------------------------- + +inline +bool Boubble::operator!=(Boubble const& b) const +{ + return !(*this==b); +} + +//---------------------------------------------------------------------------------------------------- + +inline +bool Boubble::operator<(Boubble const& b) const +{ + if(_src < b._src) return true; + if(_rel < b._rel) return true; + if(this < &b) return true; + return false; +} + +//---------------------------------------------------------------------------------------------------- + +inline +std::ostream& operator<<(std::ostream& o, const Boubble& b) +{ + o << "["; + + o << b._src << "|"; + + bool cont=false; + for(list::const_iterator i = b._upath.begin(); i != b._upath.end(); ++i) + { + if(cont) o << ','; + o << i->str(); + cont = true; + } + o << '^'; + cont=false; + for(list::const_iterator i = b._dpath.begin(); i != b._dpath.end(); ++i) + { + if(cont) o << ','; + o << i->str(); + cont = true; + } + o << ':'; + o << b._rel.str(); + o << "]"; +} + +//---------------------------------------------------------------------------------------------------- + +inline +void Boubble::as_cstr(char* s) +{ + stringstream oss; + oss << *this; + strcpy(s,oss.str().c_str()); +} + +//==================================================================================================== + +#endif Index: src/dgp/canonize =================================================================== --- src/dgp/canonize (revision 5f4d9c3b32eea7b6643a751aa75bdb05b7d41576) +++ (revision ) @@ -1,50 +1,0 @@ -#!/usr/bin/perl - -#package: UAM TExt Tools -#component: canonize -#version: 1.0 -#author: Tomasz Obrebski - -use lib "/usr/local/lib/utt"; -use lib "$ENV{'HOME'}/.local/lib/utt"; - -use strict; -use Getopt::Long; -use attr; - - -my $help; - -GetOptions("help|h" => \$help); - -if($help) -{ - print <<'END' - -Transforms syntactic categories to their canonical form. - -Usage: canonize - -Options: - --help -h Help. - -END -; - exit 0; -} - -#$|=1; - -my %tra; - -while(<>) -{ - s/$attr::pos_re\/$attr::avlist_re/trans($&)/ge; - print; -} - -sub trans -{ - my $cat=shift; - exists($tra{$cat}) ? $tra{$cat} : ( $tra{$cat} = attr::canonize $cat ); -} Index: src/dgp/cmdline.ggo =================================================================== --- src/dgp/cmdline.ggo (revision 5f4d9c3b32eea7b6643a751aa75bdb05b7d41576) +++ (revision ) @@ -1,52 +1,0 @@ -package "dgp" -version "0.1" - -option "grammar" g "Grammar file" - string no typestr="filename" - -option "long" l "Long output" - flag off - -option "debug" d "Debug mode." - flag off - -option "info" - "Print info. -h - heads d - dependents -s - sets -c - constraints n - node/arc counts t - parse time -" -string no default="h" -#section "Common UTT options" - - -option "input" f "Input file" string no - -option "output" o "Output file for succesfully processed segments" string no - -option "fail" e "Output file for unsuccesfully processed segments " string no - -option "only-fail" - "Print only segments the program failed to process" flag off hidden - -option "no-fail" - "Print only segments the program processed" flag off hidden - -option "copy" c "Copy succesfully processed segments to standard output" flag off - -option "process" p "Process segments with this tag" string no multiple - -option "select" s "Select only segments with this field" string no multiple - -option "ignore" S "Select only segments without this field" string no multiple - -option "output-field" O "Output field name" string no - -option "input-field" I "Input field name" string no multiple - -option "interactive" i "Toggle interactive mode" flag off - -option "config" - "Configuration file" string typestr="FILENAME" no - -option "one-field" 1 "Print all results in one segments (creates ambiguous annotation)" flag off - -option "one-line" - "Print annotation alternatives as additional fields" flag off - -option "language" - "Language." string no Index: src/dgp/const.hh =================================================================== --- src/dgp/const.hh (revision 5f4d9c3b32eea7b6643a751aa75bdb05b7d41576) +++ src/dgp/const.hh (revision e7de6cc88c605c4f810cbc852e843294b4b0e8ac) @@ -3,8 +3,10 @@ #define MAXTYPES 32 +#define MAXCATS 4096 #define MAXFLAGS 64 -#define MAXNODES 1024 +#define MAXPROPS 16 +#define MAXNODES 2048 #define MAXCONSTRS 32 -#define MAXLINE 256 +#define MAXLINE 512 #define MAXFORMLEN 64 #define MAXDESCRLEN 80 Index: src/dgp/dgc =================================================================== --- src/dgp/dgc (revision 5f4d9c3b32eea7b6643a751aa75bdb05b7d41576) +++ (revision ) @@ -1,292 +1,0 @@ -#!/usr/bin/perl - -#package: UAM Text Tools -#component: dgc (dg compiler) -#version: 1.0 -#author: Tomasz Obrebski - -# wymaga niejawnie programu canonize!!!! -use lib "/usr/local/lib/utt"; -use lib "$ENV{'HOME'}/.local/lib/utt"; - -use strict; -use Getopt::Long; -use Data::Dumper; -use attr; -use File::HomeDir; - -my $systemconfigfile='/usr/local/etc/utt/dgc.conf'; -my $userconfigfile=home()."/.utt/dgc.conf"; - -Getopt::Long::Configure('no_ignore_case_always'); - -my $help=0; -my $catfile=0; -my $dicfile=0; -my $gramfile=0; -my $outputfile=0; - -#read configuration files########################### -my $file; -foreach $file ($systemconfigfile, $userconfigfile){ - if(open(CONFIG, $file)){ - while () { - 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; - } - - } - close CONFIG; - } -} -######################################################### - -GetOptions("help|h" => \$help, - "categories|c=s" => \$catfile, - "dictionary|d=s" => \$dicfile, - "grammar|g=s" => \$gramfile, - "outputfile|o=s" => \$outputfile); - -my $homedir = $ENV{'HOME'}; -$catfile =~ s/~/$homedir/; -$dicfile =~ s/~/$homedir/; -$gramfile =~ s/~/$homedir/; -$outputfile =~ s/~/$homedir/; - - -if($help) -{ - print <<'END' -Usage: dgc [OPTIONS] - -Options: - --categories -c filename List of syntactic categories. - --dictionary -d filename Dictionary. - --grammar -g filename List of grammar rules. - --outputfile -o filename Output file name. - --help -h Help. -END -; - exit 0; -} - -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 $nreq=0; -my $nlink=0; -my $nflag=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!"); -} - - -loadcats($catfile) if $catfile; -extractcats($dicfile) if $dicfile; - - -my $cats_re = qr/(?:$attr::cat_re\s*(?:,\s*$attr::cat_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!"); -} - -while() -{ - s/#.*//; - s/^\s+//; - s/\s+$//; - if(/^AGR\s+(\S+)\s+(\S+)$/) - { - 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) - { - if(attr::match @$cat, @{$cats{$atomcat}}) - { - print OUTPUT "REQ ".$atomcat." $2\n"; - ++$nreq; - } - } - } - elsif(/^LEFT\s+\S+$/) - { - ++$nleft; - print OUTPUT "$_\n"; - } - elsif(/^RIGHT\s+\S+$/) - { - ++$nright; - print OUTPUT "$_\n"; - } - elsif(my ($hs,$ds,$r) = /^LINK\s+($cats_re)\s+($cats_re)\s+(\S+)$/) - { - print OUTPUT "#$_\n"; - for my $h ($hs =~ /$attr::cat_re/g) - { - for my $d ($ds =~ /$attr::cat_re/g) - { - addlinks($h,$d,$r); - } - } - } - elsif(/^FLAG\s+\S+$/) - { - ++$nflag; - print OUTPUT "$_\n" - } - elsif(/^$/) { - # pomijamy puste linie oraz komentarze - } - else - { - print STDERR "Illegal format: $_\n"; - } -} - - -sub addlinks -{ - my ($h,$d,$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 "; - print OUTPUT $atomhead." "; - print OUTPUT $atomdep." $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 LINK statements\n", $nlink; -printf STDERR "%6d FLAG statements\n", $nflag; - - -sub extractcats -{ - my $file = shift; - open DICFILE, "canonize $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, "canonize $file |"; - while() - { - tr/ \t\n//d; - next if !$_ || exists $cats{$_}; - print OUTPUT "CAT $_\n"; - ++$ncat; - $cats{$_}=attr::parse($_); - } - close CATFILE; -} - Index: src/dgp/dgp0.cc =================================================================== --- src/dgp/dgp0.cc (revision 5f4d9c3b32eea7b6643a751aa75bdb05b7d41576) +++ src/dgp/dgp0.cc (revision e7de6cc88c605c4f810cbc852e843294b4b0e8ac) @@ -6,6 +6,4 @@ extern SGraph sgraph; -SNode* snodes; - extern bool debug; @@ -16,6 +14,6 @@ void set_initial_constraints(int node) { - snodes[node].prop.forbidden.reset(); - snodes[node].prop.required=grammar.obl[snodes[node].mnode->cat]; + sgraph[node].prop.forbidden.reset(); + sgraph[node].prop.required=grammar.is_obl(mgraph[sgraph[node].mnode].cat); } @@ -23,11 +21,11 @@ bool changing_constraints(int head, Role role) { - return grammar.sgl[role] || snodes[head].prop.required[role]; + return grammar.is_sgl(role) || sgraph[head].prop.required[role]; } void apply_constraints(int head, Role role) { - if(grammar.sgl[role]) snodes[head].prop.forbidden.set(role); - snodes[head].prop.required.reset(role); + if(grammar.is_sgl(role)) sgraph[head].prop.forbidden.set(role); + sgraph[head].prop.required.reset(role); } @@ -35,5 +33,5 @@ { NodeProp ret=headprop; - if(grammar.sgl[role]) ret.forbidden.set(role); + if(grammar.is_sgl(role)) ret.forbidden.set(role); ret.required.reset(role); return ret; @@ -44,5 +42,5 @@ NodeProp ret=headprop; - if(grammar.sgl[role]) ret.forbidden.set(role); + if(grammar.is_sgl(role)) ret.forbidden.set(role); ret.required.reset(role); return ret; @@ -52,5 +50,5 @@ { for(vector::iterator ps=mnode.snodes.begin(); ps!=mnode.snodes.end(); ++ps) - if(snodes[*ps].prop==p && snodes[*ps].LH==newheadLH && snodes[*ps].LV==newheadLV) + if(sgraph[*ps].prop==p && sgraph[*ps].LH==newheadLH && sgraph[*ps].LV==newheadLV) return *ps; return -1; @@ -59,11 +57,6 @@ void connect_left(list::iterator h, list::iterator d, Role r) { - NodeProp &oldheadprop = snodes[*h].prop; - NodeProp newheadprop; - bitset newheadLV; - bitset newheadLH; - bitset newheadLD; - - newheadprop=compute_prop_left(oldheadprop,r); + NodeProp &oldheadprop = sgraph[*h].prop; + NodeProp newheadprop = compute_prop_left(oldheadprop,r); int newheadind; @@ -72,9 +65,9 @@ else { - newheadLH = snodes[*h].LH; - newheadLV = snodes[*d].LV; - newheadLD = snodes[*h].LD; - - newheadind = get_node(*(snodes[*h].mnode), newheadprop, newheadLH, newheadLV); + bitset newheadLH = sgraph[*h].LH; + bitset newheadLV = sgraph[*d].LV; + bitset newheadLD = sgraph[*h].LD; + + newheadind = get_node(mgraph[sgraph[*h].mnode], newheadprop, newheadLH, newheadLV); if( newheadind < 0 ) { @@ -82,69 +75,63 @@ list::iterator nextit=h; ++nextit; nodelist.insert(nextit,newheadind); - snodes[newheadind].LH=newheadLH; - snodes[newheadind].in_LH=true; - snodes[newheadind].LV.reset(); - snodes[newheadind].LD = newheadLD; + 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); } else - snodes[newheadind].LD |= newheadLD; // TYLKO DLA LD + sgraph[newheadind].LD |= newheadLD; // TYLKO DLA LD } - snodes[newheadind].deps.push_back(Arc(*d,r,*h)); - - if(snodes[*d].saturated()) snodes[newheadind].LV |= snodes[*d].LV; - snodes[newheadind].LD.set(*d); - if(snodes[*d].saturated()) snodes[newheadind].LD |= snodes[*d].LD; - - if(debug) - sgraph.print_arc(stderr,*d,newheadind,r,0), sgraph.print_node_debug(stderr," U ",newheadind); -} - + sgraph[newheadind].deps.push_back(Arc(*d,r,*h)); + + 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,*d,newheadind,r,0), sgraph.print_node_debug(stderr," U ",newheadind); +} void connect_right(list::iterator h, list::iterator d, Role r) { - NodeProp &oldheadprop = snodes[*h].prop; - NodeProp newheadprop; - bitset newheadLV; - bitset newheadLH; - bitset newheadLD; + NodeProp &oldheadprop = sgraph[*h].prop; + NodeProp newheadprop = compute_prop_right(oldheadprop,r); int newheadind; - newheadprop = compute_prop_right(oldheadprop,r); if(oldheadprop==newheadprop) newheadind = *h; else { - newheadLH = snodes[*h].LH; - newheadLV = snodes[*h].LV; - newheadLD = snodes[*h].LD; - - newheadind = get_node(*(snodes[*h].mnode), newheadprop, newheadLH, newheadLV); + bitset newheadLH = sgraph[*h].LH; + bitset newheadLV = sgraph[*h].LV; + bitset newheadLD = sgraph[*h].LD; + + newheadind = get_node(mgraph[sgraph[*h].mnode], newheadprop, newheadLH, newheadLV); if( newheadind < 0 ) { newheadind = sgraph.clone(*h,newheadprop); - snodes[newheadind].LH=newheadLH; - snodes[newheadind].in_LH=false; - snodes[newheadind].LV=newheadLV; - snodes[newheadind].LD=newheadLD; list::iterator nextit=h; ++nextit; nodelist.insert(nextit,newheadind); + sgraph[newheadind].LH=newheadLH; + sgraph[newheadind].LD=newheadLD; + sgraph[newheadind].in_LH=false; + sgraph[newheadind].LV=newheadLV; if(debug) sgraph.print_node_debug(stderr," C ",newheadind); } else - snodes[newheadind].LD |= newheadLD; // TYLKO DLA LD + sgraph[newheadind].LD |= newheadLD; // TYLKO DLA LD } - snodes[*d].heads.push_back(Arc(newheadind,r,*h)); - - snodes[*d].LH.set(newheadind); - - if(snodes[newheadind].saturated()) snodes[*d].LH |= snodes[newheadind].LH; - - if(debug) - sgraph.print_arc(stderr,newheadind,*d,r,1), sgraph.print_node_debug(stderr," U ",*d); + sgraph[*d].heads.push_back(Arc(newheadind,r,*h)); + + sgraph[*d].LH.set(newheadind); + + if(sgraph[newheadind].saturated()) sgraph[*d].LH |= sgraph[newheadind].LH; + + if(debug) sgraph.print_arc(stderr,newheadind,*d,r,1), sgraph.print_node_debug(stderr," U ",*d); } @@ -156,7 +143,7 @@ if(sgraph.visible(*i,*j) && sgraph.saturated(*i)) { - Roles& ji_roles = grammar.connect[snodes[*j].mnode->cat][snodes[*i].mnode->cat]; + Roles& ji_roles = grammar.connectable( mgraph[sgraph[*j].mnode].cat, mgraph[sgraph[*i].mnode].cat ); for(RolesIter r=ji_roles.begin(); r!=ji_roles.end();++r) - if(grammar.check_constr(snodes[*j].prop,snodes[*i].prop,0,*r)) + if(grammar.check_constr(sgraph[*j].prop,sgraph[*i].prop,0,*r)) connect_left(j,i,*r); } @@ -169,7 +156,7 @@ if(sgraph.visible(*i,*j)) { - Roles& ij_roles = grammar.connect[snodes[*i].mnode->cat][snodes[*j].mnode->cat]; + Roles& ij_roles = grammar.connectable( mgraph[sgraph[*i].mnode].cat, mgraph[sgraph[*j].mnode].cat ); for(RolesIter r=ij_roles.begin(); r!=ij_roles.end();++r) - if(grammar.check_constr(snodes[*i].prop,snodes[*j].prop,1,*r)) + if(grammar.check_constr(sgraph[*i].prop,sgraph[*j].prop,1,*r)) connect_right(i,j,*r); } @@ -182,8 +169,8 @@ for(++i; i!=nodelist.end(); ++i) { - for(vector::iterator da=sgraph.nodes[*i].deps.begin()--; da!=sgraph.nodes[*i].deps.end(); ++da) - sgraph.nodes[da->dst].heads.push_back(Arc(*i,da->role,da->anc)); - for(vector::iterator ha=sgraph.nodes[*i].heads.begin(); ha!=sgraph.nodes[*i].heads.end(); ++ha) - sgraph.nodes[ha->dst].deps.push_back(Arc(*i,ha->role,ha->anc)); + for(vector::iterator da=sgraph[*i].deps.begin()--; da!=sgraph[*i].deps.end(); ++da) + sgraph[da->dst].heads.push_back(Arc(*i,da->role,da->anc)); + for(vector::iterator ha=sgraph[*i].heads.begin(); ha!=sgraph[*i].heads.end(); ++ha) + sgraph[ha->dst].deps.push_back(Arc(*i,ha->role,ha->anc)); } } @@ -192,5 +179,4 @@ void dgp0() { - snodes=sgraph.nodes; nodelist.clear(); @@ -198,7 +184,8 @@ processed=nodelist.begin(); - for(int m=0; m nodelist; +list::iterator processed; + +//==================================================================================================== + +void set_initial_constraints(int node) +{ + sgraph[node].prop.forbidden.reset(); + sgraph[node].prop.required=grammar.is_obl(sgraph.cat(node)); + sgraph[node].prop.attached.reset(); + sgraph[node].prop.flags=grammar.initial_flags(sgraph.cat(node)); +} + +//---------------------------------------------------------------------------------------------------- + +bool changing_constraints(int head, Role role) +{ + return grammar.is_sgl(role) || sgraph[head].prop.required[role]; +} + +//==================================================================================================== + +NodeProp compute_head_prop(NodeProp headprop, const Link& link, list bs, FlagSet& depflags) +{ + NodeProp ret=headprop; + + if(grammar.is_sgl(link.role)) + { + ret.forbidden.set(link.role); + ret.attached.set(link.role); + } + ret.required.reset(link.role); + + ret.required |= (grammar.constr_include(link.role) & ~ret.attached); + ret.forbidden |= grammar.constr_exclude(link.role); + + ret.boubbles=bs; + ret.flags |= ( depflags & grammar.pass_flags(link.role) ); + + if(link.props[Prop("INIT")]) ret.init_attached=true; + if(link.props[Prop("FIN")]) ret.fin_attached=true; + + return ret; +} + +//---------------------------------------------------------------------------------------------------- + +NodeProp compute_dep_prop(NodeProp depprop, const Link& link, list bs) +{ + NodeProp ret=depprop; + ret.boubbles=bs; + return ret; +} + +//==================================================================================================== + +int find_existing_node(int mnodeind, NodeProp p, bitset& newheadLH, bitset& newheadLV) +{ + MNode& mnode = mgraph[mnodeind]; + 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; +} + +//==================================================================================================== + +list receive_boubbles(int node, Role role, Dir dir) +{ + list ret; + for(list::iterator b = sgraph[node].prop.boubbles.begin(); b!=sgraph[node].prop.boubbles.end(); b++) + { + Boubble* new_boubble = (*b)->step(role,dir); + if(new_boubble) + ret.push_back(new_boubble); + } + return ret; +} + +//---------------------------------------------------------------------------------------------------- + +list collect_head_boubbles(int head, int dep, Role role) +{ + list new_boubbles = grammar.trigger_boubbles(sgraph.cat(dep),role,UP); + + for(list::iterator b = new_boubbles.begin(); b != new_boubbles.end(); b++) + (*b)->src(dep); + + list received_boubbles = receive_boubbles(dep,role,UP); + + new_boubbles.insert(new_boubbles.begin(),received_boubbles.begin(),received_boubbles.end()); + + return new_boubbles; +} + +//---------------------------------------------------------------------------------------------------- + +list collect_dep_boubbles(int head, int dep, Role role) +{ + list new_boubbles = grammar.trigger_boubbles(sgraph.cat(head), role, DOWN); + + for(list::iterator b = new_boubbles.begin(); b != new_boubbles.end(); b++) + (*b)->src(head); + + list received_boubbles = receive_boubbles(head,role,DOWN); + + new_boubbles.insert(new_boubbles.begin(),received_boubbles.begin(),received_boubbles.end()); + + return new_boubbles; +} + +//==================================================================================================== + +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); + 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); + + 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); + 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); + + 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); + sgraph[newheadind].LH=newheadLH; + sgraph[newheadind].LD=newheadLD; + sgraph[newheadind].in_LH=false; + sgraph[newheadind].LV=newheadLV; + + if(debug) sgraph.print_node_debug(stderr,"C ",newheadind,*h); + + 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); + sgraph[newind].LH=LH; + sgraph[newind].LD=LD; + sgraph[newind].in_LH=true; //??????? + sgraph[newind].LV.reset(); + + if(debug) sgraph.print_node_debug(stderr,"C ",newind,*d); + + return newind; +} + +//==================================================================================================== + +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; + + NodeProp newheadprop = compute_head_prop(oldheadprop,l,new_head_boubbles,olddepprop.flags); + + int newheadind; + if(oldheadprop==newheadprop) + 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 ) + sgraph[newheadind].LD |= newheadLD; + else + newheadind = create_new_head_node_left(h,newheadprop,newheadLH,newheadLD,newheadLV); + } + + + + NodeProp newdepprop = compute_dep_prop(olddepprop,l,new_dep_boubbles); + + int newdepind; + + if(olddepprop==newdepprop) + 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 ) + sgraph[newdepind].LD |= newdepLD; // TYLKO DLA LD + else + newdepind = create_new_dep_node_left(d,newdepprop,newdepLH,newdepLD,newdepLV); + } + + 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); +} + +//---------------------------------------------------------------------------------------------------- + +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); + + int newheadind; + + if(oldheadprop==newheadprop) + 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 ) + sgraph[newheadind].LD |= newheadLD; // TYLKO DLA LD + else + newheadind = create_new_head_node_right(h,newheadprop,newheadLH,newheadLD,newheadLV); + } + + NodeProp &olddepprop = sgraph[*d].prop; + NodeProp newdepprop = compute_dep_prop(olddepprop,l,new_dep_boubbles); + + int newdepind; + + if(olddepprop==newdepprop) + 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 ) + sgraph[newdepind].LD |= newdepLD; // TYLKO DLA LD + else + newdepind = create_new_dep_node_right(d,newdepprop,newdepLH,newdepLD,newdepLV); + } + + + + + sgraph[newdepind].heads.push_back(Arc(newheadind,l.role,*h,*d)); + + sgraph[newdepind].LH.set(newheadind); + + // sgraph[*d].prop.merge_boubbles(new_dep_boubbles); + + if(sgraph[newheadind].saturated()) sgraph[newdepind].LH |= sgraph[newheadind].LH; + + 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); + +} + +//==================================================================================================== + +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!!! + list::iterator ri = ji_links.begin(); + if(ri == ji_links.end()) { if(debug) fprintf(stderr,"no roles\n"); } + else + { + for(; ri != ji_links.end(); ++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); + + 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 + { + if(debug) fprintf(stderr,"success\n"); + connect_left( j, i, **ri, new_head_boubbles, new_dep_boubbles); + } + } + } + } +} + + +//---------------------------------------------------------------------------------------------------- + +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 ); + list::iterator ri = ij_links.begin(); + if(ri == ij_links.end()) { if(debug) fprintf(stderr,"no roles\n"); } + else + { + for(; ri != ij_links.end(); ++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); + + 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 + { + if(debug) fprintf(stderr,"success\n"); + connect_right( i, j, **ri, new_head_boubbles, new_dep_boubbles ); + } + } + } + } +} + +//==================================================================================================== + +void reverse_links() +{ + list::iterator i = nodelist.begin(); + for(++i; i!=nodelist.end(); ++i) + { + for(vector::iterator da=sgraph[*i].deps.begin()--; da!=sgraph[*i].deps.end(); ++da) + sgraph[da->dst].heads.push_back(Arc(*i,da->role,da->headanc,da->depanc)); + for(vector::iterator ha=sgraph[*i].heads.begin(); ha!=sgraph[*i].heads.end(); ++ha) + sgraph[ha->dst].deps.push_back(Arc(*i,ha->role,ha->headanc,ha->depanc)); + } +} + +//==================================================================================================== + +void dgp1() +{ + + nodelist.clear(); + nodelist.push_back(0); // BOS + processed=nodelist.begin(); + + for(int m=0; m::iterator cursor=processed; + while(++cursor != nodelist.end()) + { + try_connect_dependents(cursor); + try_connect_heads(cursor); + processed=cursor; + } + + } + reverse_links(); +} Index: src/dgp/dgp1.hh =================================================================== --- src/dgp/dgp1.hh (revision e7de6cc88c605c4f810cbc852e843294b4b0e8ac) +++ src/dgp/dgp1.hh (revision e7de6cc88c605c4f810cbc852e843294b4b0e8ac) @@ -0,0 +1,12 @@ +#ifndef _DGP0_HH +#define _DGP0_HH + +#include "grammar.hh" +#include "sgraph.hh" +#include "mgraph.hh" + +// API + +void dgp1(); + +#endif Index: src/dgp/go =================================================================== --- src/dgp/go (revision 5f4d9c3b32eea7b6643a751aa75bdb05b7d41576) +++ (revision ) @@ -1,13 +1,0 @@ -if test -f Makefile.go; -then - make -f Makefile.go gram.dgp; - tok |\ - lem -p W |\ - canonize |\ - sen |\ - gph -p W -p BOS -p EOS -r BOS |\ - dgp -i ds -p W -p BOS -p EOS -g gram.dgp -else - echo "Invalid configuration! Run utt_make_config.pl first." -fi - Index: src/dgp/grammar.cc =================================================================== --- src/dgp/grammar.cc (revision 5f4d9c3b32eea7b6643a751aa75bdb05b7d41576) +++ src/dgp/grammar.cc (revision e7de6cc88c605c4f810cbc852e843294b4b0e8ac) @@ -1,37 +1,61 @@ -#include +#include #include "grammar.hh" -bool (*constraint[MAXCONSTRS])(int head, int dep); - - -int chk_type(const char* s, int lineno) // SIDE EFECTS! -{ - if(Role::index(s)>0) return 1; - - fprintf(stderr,"%8d: Invalid type '%s'. Line ignored.\n",lineno,s); - return 0; -} - -int chk_cat(const char* s, int lineno) -{ - if(Cat::index(s)>0) return 1; - - fprintf(stderr,"%8d: Invalid category '%s'. Line ignored.\n",lineno,s); - return 0; -} +//bool (*constraint[MAXCONSTRS])(int head, int dep); + +//==================================================================================================== +//inline !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! +bool chk_type(const char* s) { return Role::index(s)>0; } // PRZENIEŠÆ DO Role +//---------------------------------------------------------------------------------------------------- +//inline !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! +bool chk_long(const char* s) { return LongRel::index(s)>0; } // jw +//---------------------------------------------------------------------------------------------------- +//inline !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! +bool chk_cat(const char* s) { return Cat::index(s)>0; } //jw +//---------------------------------------------------------------------------------------------------- +//inline !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! +bool chk_flag(const char* s) { return Flag::index(s)>0; } //jw +//==================================================================================================== + +void grammar_error(int lineno, string s="Grammar error.") +{ + fprintf(stderr,"%8d: %s Line ignored.\n",lineno,s.c_str()); +} + +//==================================================================================================== void Grammar::add_category(const char* s) { Cat::add(s); - if(Cat::count()>cats_sz) + + if(connect.size() <= Cat::count()) { - cats_sz += 16; - connect.resize(cats_sz); - for(int i=0; itypes_sz) - { - types_sz += 16; - lt.resize(types_sz); - gt.resize(types_sz); - } -} - -void Grammar::add_flag(const char* s) -{ - Flag::add(s); - if(Flag::count()>flags_sz) - { - flags_sz += 16; - pass.resize(flags_sz); - } -} - + + if(lt.size() <= Role::count()) lt.resize(Role::count()+RESIZE_DELTA); + if(gt.size() <= Role::count()) gt.resize(Role::count()+RESIZE_DELTA); + if(pass.size() <= Role::count()) pass.resize(Role::count()+RESIZE_DELTA); + if(include.size() <= Role::count()) include.resize(Role::count()+RESIZE_DELTA); + if(exclude.size() <= Role::count()) exclude.resize(Role::count()+RESIZE_DELTA); + for(int i=0; i boubble_list, Boubble* bp) const +{ + for(list::const_iterator bi = boubble_list.begin(); bi != boubble_list.end(); bi++ ) + if(**bi == *bp) return true; + return false; +} + +//---------------------------------------------------------------------------------------------------- + +void Grammar::add_triggers(Cat src, Cat dest, LongRel l) +{ + for(list::const_iterator b=boubbles.begin(); b!=boubbles.end(); b++) + if((*b)->rel() == l) + { + list& boubble_list = ((*b)->dir()==UP) ? uptrigger[src][(*b)->next()] : dntrigger[src][(*b)->next()] ; + if(!contains_boubble(boubble_list,*b)) + boubble_list.push_back(*b); + } +} + +//==================================================================================================== void Grammar::set_lt(Role s, Role t) @@ -85,6 +126,69 @@ +void Grammar::compute_triggers() +{ + //init uptrigger array + uptrigger.resize(Cat::count()); + for(int i=0; i::const_iterator b=boubbles.begin(); b!=boubbles.end; b++) + // if(b->dir()==UP && ) +} + +//==================================================================================================== + +list Grammar::trigger_boubbles(Cat c, Role r, Dir d) +{ + list boubble_list = (d == UP) ? uptrigger[c][r] : dntrigger[c][r]; + list ret; + for(list::iterator b = boubble_list.begin(); b != boubble_list.end(); ++b) + ret.push_back((*b)->step(r,d)); + return ret; +} + +//==================================================================================================== + +Flag parse_flags(const char* s, const char* v) +{ + char buf[16][17]; + int n=sscanf(s,"%[A-Z]%[+-]%[A-Z]%[+-]%[A-Z]%[+-]%[A-Z]%[+-]%[A-Z]%[+-]%[A-Z]%[+-]%[A-Z]%[+-]%[A-Z]%[+-]", + buf[0],buf[1],buf[2],buf[3],buf[4],buf[5],buf[6],buf[7],buf[8],buf[9],buf[10],buf[11],buf[12],buf[13],buf[14],buf[15],buf[16]); + for(int i=2; i<=n; i+=2) + if(strcmp(buf[i-1],v)==0) + return Flag(buf[i-2]); + return Flag("NULL"); +} + + +PropSet parse_props(const char* s) +{ + PropSet ret; + char buf[8][17]; + int n=sscanf(s,"&%[A-Z]&%[A-Z]&%[A-Z]&%[A-Z]&%[A-Z]&%[A-Z]&%[A-Z]&%[A-Z]",buf[0],buf[1],buf[2],buf[3],buf[4],buf[5],buf[6],buf[7]); + for(int i=1; i<=n; i++) + ret.set(Prop(buf[i-1])); + return ret; + +} + + bool Grammar::read(FILE* f) { + + //>>> TU? + + Prop::add("INIT"); + Prop::add("FIN"); + + //<<< TU? + + int lineno=0; char line[MAXLINE]; // line has the structure: key [arg1 [arg2 [arg3]]] @@ -93,59 +197,262 @@ char arg2[MAXLINE]; char arg3[MAXLINE]; + char arg4[MAXLINE]; while(fgets(line,MAXLINE,f)) - { - lineno++; - int fields=sscanf(line,"%s %s %s %s",key,arg1,arg2,arg3); - - if(fields<1 || key[0]=='#') continue; // skip empty lines and comments - - if (strcmp(key,"CAT")==0 && fields>=2) { - add_category(arg1); + lineno++; + int fields=sscanf(line,"%s %s %s %s %s",key,arg1,arg2,arg3,arg4); + + if(fields<1 || key[0]=='#') continue; // skip empty lines and comments + + if(fields>1 && arg1[0] == '#') fields=1; + if(fields>2 && arg2[0] == '#') fields=2; + if(fields>3 && arg3[0] == '#') fields=3; + if(fields>4 && arg4[0] == '#') fields=4; + + if (strcmp(key,"CAT")==0 && fields==2) + { + add_category(arg1); + } + else if(strcmp(key,"ROLE")==0 && fields==2) + { + add_type(arg1); + } + else if(strcmp(key,"SGL")==0 && fields==2) + { + if(chk_type(arg1)) + set_sgl(arg1); + else + grammar_error(lineno); + } + else if(strcmp(key,"LEFT")==0 && fields==2) + { + if(chk_type(arg1)) + set_left(arg1); + else + grammar_error(lineno); + } + else if(strcmp(key,"RIGHT")==0 && fields==2) + { + if(chk_type(arg1)) + set_right(arg1); + else + grammar_error(lineno); + } + else if(strcmp(key,"INITR")==0 && fields==2) + { + if(chk_type(arg1)) + set_init(arg1); + else + grammar_error(lineno); + } + else if(strcmp(key,"FINR")==0 && fields==2) + { + if(chk_type(arg1)) + set_fin(arg1); + else + grammar_error(lineno); + } + else if(strcmp(key,"INITF")==0 && fields==2) + { + if(chk_flag(arg1)) + set_initf(arg1); + else + grammar_error(lineno); + } + else if(strcmp(key,"FINF")==0 && fields==2) + { + if(chk_flag(arg1)) + set_finf(arg1); + else + grammar_error(lineno); + } + else if(strcmp(key,"REQ")==0 && fields==3) + { + if( chk_cat(arg1) && chk_type(arg2) ) + set_obl(arg1,arg2); + else + grammar_error(lineno); + } + else if(strcmp(key,"CONSTRE")==0 && fields==3) + { + if( chk_type(arg1) && chk_type(arg2) ) + set_exclude(arg1,arg2); + else + grammar_error(lineno); + } + else if(strcmp(key,"CONSTRI")==0 && fields==3) + { + if( chk_type(arg1) && chk_type(arg2) ) + set_include(arg1,arg2); + else + grammar_error(lineno); + } + else if(strcmp(key,"LONG")==0 && fields ==3) + { + add_long(arg1,arg2); + } + else if(strcmp(key,"LINK")==0 && fields==4) + { + 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'; + + // 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) ) + set_connect(cat1,parse_flags(flags1,"+"),parse_flags(flags1,"-"),cat2,parse_flags(flags2,"+"),parse_flags(flags2,"-"),type,parse_props(props)); + else if( chk_cat(cat1) && chk_cat(cat2) && chk_long(type) ) + { + set_longrel(cat1,cat2,type); + add_triggers(cat1,cat2,type); + } + else + grammar_error(lineno); + } + // else if(strcmp(key,"LINK")==0 && fields==5) + // { + // if( chk_cat(arg1) && chk_cat(arg2) && chk_type(arg4) ) + // set_connect(arg1,arg2,arg3,arg4); + // else + // grammar_error(lineno); + // } + // FLAG DECLARATION + else if(strcmp(key,"FLAG")==0 && fields==2) + { + add_flag(arg1); + } + else if(strcmp(key,"SET")==0 && fields==3) + { + if( chk_cat(arg1) && chk_flag(arg2) ) + set_set(arg1,arg2); + else + grammar_error(lineno); + } + else if(strcmp(key,"PASS")==0 && fields==3) + { + if( chk_type(arg1) && chk_flag(arg2) ) + set_pass(arg1,arg2); + else + grammar_error(lineno); + } + + else fprintf(stderr,"Statement not recognized in line %d. Ignored.\n", lineno); } - else if(strcmp(key,"ROLE")==0 && fields>=2) - { - add_type(arg1); - } - else if(strcmp(key,"SGL")==0 && fields>=2) - { - if(chk_type(arg1,lineno)) - set_sgl(arg1); - } - else if(strcmp(key,"LEFT")==0 && fields>=2) - { - if(chk_type(arg1,lineno)) - set_left(arg1); - } - else if(strcmp(key,"RIGHT")==0 && fields>=2) - { - if(chk_type(arg1,lineno)) - set_right(arg1); - } - else if(strcmp(key,"REQ")==0 && fields>=3) - { - if(chk_cat(arg1,lineno) + chk_type(arg2,lineno) == 2) - set_obl(arg1,arg2); - } - else if(strcmp(key,"LINK")==0 && fields>=4) - { - if(chk_cat(arg1,lineno) + chk_cat(arg2,lineno) + chk_type(arg3,lineno) == 3) - set_connect(arg1,arg2,arg3); - } - // FLAG DECLARATION - else if(strcmp(key,"FLAG")==0 && fields>=2) - { - add_flag(arg1); - } - - else fprintf(stderr,"Invalid line %d. Ignored.\n", lineno); - } - -// compute_gt(); - + + // compute_gt(); + return true; } + + +void Grammar::write(ostream& os) +{ + for(Cat i=1; ihflagplus||l->hflagminus) + { + os << ";"; + if(l->hflagplus) os << (l->hflagplus).str() << "+"; + if(l->hflagminus) os << (l->hflagminus).str() << "-"; + } + os << "\t" << d.str(); + if(l->dflagplus||l->dflagminus) + { + os << ";"; + if(l->dflagplus) os << (l->dflagplus).str() << "+"; + if(l->dflagminus) os << (l->dflagminus).str() << "-"; + } + os << "\t" << (l->role).str(); + for(Prop p=0; pprops[p]) + os << "&" << p.str(); + os << endl; + } + + for(LongRel i=1; i::const_iterator b = boubbles.begin(); b != boubbles.end(); b++) + os << "BOUBBLE\t" << **b << endl; + + for(Cat c=1; c::const_iterator b=uptrigger[c][r].begin(); b!=uptrigger[c][r].end(); b++) + os << "TRIGGER-UP\t" << c.str() << "\t" << r.str() << "\t" << (*b)->rel().str() << endl; + + for(Cat c=1; c::const_iterator b=dntrigger[c][r].begin(); b!=dntrigger[c][r].end(); b++) + os << "TRIGGER-DN\t" << c.str() << "\t" << r.str() << "\t" << (*b)->rel().str() << endl; + + for(Flag i=1; i::const_iterator b=uptrigger[c][r].begin(); b!=uptrigger[c][r].end(); b++) + fprintf(f,"#TRIGGER\t%s\t%s\t%s\n",c.str(),r.str(),(*b)->rel().str()); + + for(Cat c=1; c::const_iterator b=dntrigger[c][r].begin(); b!=dntrigger[c][r].end(); b++) + fprintf(f,"#TRIGGER\t%s\t%s\t%s\n",c.str(),r.str(),(*b)->rel().str()); + for(Flag i=1; i PropSet; + +const PropSet EmptyPropSet = PropSet(); + +const FlagSet EmptyFlagSet = FlagSet(); + +//==================================================================================================== +// class Link +//==================================================================================================== + +struct Link +{ + Link(Role r, Flag dfplus="NULL", Flag dfminus="NULL") : role(r), dflagplus(dfplus), dflagminus(dfminus) { } + Link(Role r, PropSet ps=EmptyPropSet, Flag hfp="NULL", Flag hfm="NULL", Flag dfp="NULL", Flag dfm="NULL") + : role(r), props(ps), hflagplus(hfp), hflagminus(hfm), dflagplus(dfp), dflagminus(dfm) { } + //Link(Role r) : role(r), dflagplus("NULL") { } + Role role; - FlagSet hflags; - FlagSet dflags; + Flag hflagplus; + Flag hflagminus; + Flag dflagplus; + Flag dflagminus; + PropSet props; + + bool operator<(const Link& l) const + { + if(role < l.role) return true; + if(hflagplus < l.hflagplus) return true; + if(hflagminus < l.hflagminus) return true; + if(dflagplus < l.dflagplus) return true; + if(dflagminus < l.dflagminus) return true; + if(props.to_ulong() < l.props.to_ulong()) return true; + return false; + } + }; +typedef set Links; + +//==================================================================================================== +// class Grammar +//==================================================================================================== class Grammar @@ -25,55 +63,182 @@ public: - // enum CONSTR { SGL, OBL, LEFT, RIGHT, INIT, NONINIT, FIN, NONFIN }; - - Grammar() : types_sz(0), cats_sz(0), flags_sz(0) {} ; + static const int RESIZE_DELTA=16; + + Grammar() {} ; + + Roles& connectable(Cat h, Cat d); + Roles connectable(Cat h, Cat d, FlagSet f, FlagSet df); + + list connectable2(Cat h, Cat d, FlagSet hfs, FlagSet dfs); + + bool check_constr(NodeProp& hprop, NodeProp& dprop, int dir, Role role); + bool check_constr2(NodeProp& hprop, NodeProp& dprop, int dir, const Link& link); + + bool check_longrel(Cat hcat, Cat dcat, LongRel rel); + bool is_sgl(Role r); + RoleSet is_obl(Cat c); + + RoleSet& constr_include(Role r) { return include[r]; }; + RoleSet& constr_exclude(Role r) { return exclude[r]; }; - int types_sz; - int cats_sz; - int flags_sz; - - vector< vector< Roles > > connect; + FlagSet initial_flags(Cat c) { return set[c]; } + FlagSet pass_flags(Role r) { return pass[r]; } + + list trigger_boubbles(Cat c, Role r, Dir d); + + bool read(FILE* f); + void write(ostream& os); + void write(FILE* f); + +private: + RoleSet sgl; - vector< RoleSet > obl; + vector< RoleSet > obl; //[Cat] RoleSet left; RoleSet right; - vector< RoleSet > lt; - vector< RoleSet > gt; - - - // vector< vector< vector< - vector< FlagSet > set; - vector< FlagSet > pass; - - bool read(FILE* f); - void write(FILE* f); + RoleSet init; + RoleSet fin; + FlagSet initf; + FlagSet finf; + + vector< RoleSet > lt; //[Role] + vector< RoleSet > gt; //[Role] + + vector< FlagSet > set; //[Cat] + // vector< FlagSet > rset; //[Role] + vector< FlagSet > pass; //[Role] + + vector< vector< Roles > > connect; //[Cat][Cat] + + vector< vector< Links > > connect1; //[Cat][Cat] + + vector< RoleSet > include; //[Role] + vector< RoleSet > exclude; //[Role] + + vector< vector< LongRels > > longrel; //[Cat][Cat] + + list< Boubble* > boubbles; + + vector< vector< list > > uptrigger;//[Cat][Role] + vector< vector< list > > dntrigger;//[Cat][Role] void add_category(const char* s); void add_type(const char* s); - void add_flag(const char* s); - - void set_sgl(Role r) { sgl.set(r); } - void set_obl(Cat c, Role r) { obl[c].set(r); } - void set_left(Role r) { left.set(r); } - void set_right(Role r) { right.set(r); } - void set_order(Role r, Role s) { lt[s].set(r); } - void set_connect(Cat c, Cat d, Role r) { connect[c][d].insert(r); } + void add_flag(const char* s) { Flag::add(s); } + void add_long(const char* l, const char* p) { LongRel::add(l); boubbles.push_back( new Boubble(p,l) ); } + void add_triggers(Cat h, Cat d, LongRel l); + + void set_sgl(Role r) { sgl.set(r); } + void set_obl(Cat c, Role r) { obl[c].set(r); } + void set_left(Role r) { left.set(r); } + void set_right(Role r) { right.set(r); } + void set_init(Role r) { init.set(r); } + void set_fin(Role r) { fin.set(r); } + void set_initf(Flag f) { initf.set(f); } + void set_finf(Flag f) { finf.set(f); } + void set_order(Role r, Role s) { lt[s].set(r); } + + // void set_connect(Cat c, Cat d, Role r) { connect[c][d].insert(r); } + // void set_connect(Cat c, Cat d, Flag f, Role r) { connect1[c][d].insert(Link(r,f)); } + + void set_connect(Cat h, Flag hfp, Flag hfm, Cat d, Flag dfp, Flag dfm, Role r, PropSet ps ) { connect1[h][d].insert(Link(r,ps,hfp,hfm,dfp,dfm)); } + + void set_include(Role r, Role s) { include[r].set(s); } + void set_exclude(Role r, Role s) { exclude[r].set(s); } + void set_longrel(Cat c, Cat d, LongRel l){ longrel[c][d].insert(l); } + void set_set(Cat c, Flag f) { set[c].set(f); } + void set_pass(Role r, Flag f) { pass[r].set(f); } void set_lt(Role r, Role s); void compute_gt(); - - - bool check_constr(NodeProp& hprop, NodeProp& dprop, int dir, Role role); + void compute_triggers(); + bool contains_boubble(const list boubble_list, Boubble* bp) const; }; -inline bool Grammar::check_constr(NodeProp& hprop, NodeProp& dprop, int dir, Role role) +//---------------------------------------------------------------------------------------------------- + +inline +Roles& Grammar::connectable(Cat h, Cat d) +{ + return connect[h][d]; +} + +//---------------------------------------------------------------------------------------------------- + +inline +Roles Grammar::connectable(Cat h, Cat d, FlagSet hfs, FlagSet dfs) // ZBYT WOLNE!!!!!!!!!!!!!!!!!!!!!!!!!! (-> Roles&) +{ + Roles ret; + for(Links::const_iterator l = connect1[h][d].begin(); l != connect1[h][d].end(); l++) + if( (l->hflagplus==0 || hfs[l->hflagplus]) && (l->hflagminus==0 || !hfs[l->hflagminus]) ) + if( (l->dflagplus==0 || dfs[l->dflagplus]) && (l->dflagminus==0 || !dfs[l->dflagminus]) ) + ret.insert(l->role); + return ret; +} + +//---------------------------------------------------------------------------------------------------- + +inline +list Grammar::connectable2(Cat h, Cat d, FlagSet hfs, FlagSet dfs) // ZBYT WOLNE!!!!!!!!!!!!!!!!!!!!!!!!!! (-> Roles&) +{ + list ret; + for(Links::const_iterator l = connect1[h][d].begin(); l != connect1[h][d].end(); l++) + if( (l->hflagplus==0 || hfs[l->hflagplus]) && (l->hflagminus==0 || !hfs[l->hflagminus]) ) + if( (l->dflagplus==0 || dfs[l->dflagplus]) && (l->dflagminus==0 || !dfs[l->dflagminus]) ) + ret.push_back(&(*l)); + return ret; +} + +//---------------------------------------------------------------------------------------------------- + +inline +bool Grammar::check_constr(NodeProp& hprop, NodeProp& dprop, int dir, Role role) // dir: 0-left 1-right { return !hprop.forbidden[role] && - ( !right[role] || dir==1 ) && - ( !left[role] || dir==0 ) + ( dir==1 || !right[role] ) && + ( dir==0 || !left[role] ) && + ( dir==1 || (hprop.attached&init).none() ) && + ( dir==0 || (hprop.attached&fin).none() ) ; } +//---------------------------------------------------------------------------------------------------- + +inline +bool Grammar::check_constr2(NodeProp& hprop, NodeProp& dprop, int dir, const Link& link) // dir: 0-left 1-right +{ + return + !hprop.forbidden[link.role] && + ( dir==1 || !right[link.role] ) && + ( dir==0 || !left[link.role] ) && + ( dir!=0 || !hprop.init_attached ) && + ( dir!=1 || !hprop.fin_attached ) + ; +} + +//---------------------------------------------------------------------------------------------------- + +inline +bool Grammar::check_longrel(Cat hcat, Cat dcat, LongRel rel) +{ + return longrel[hcat][dcat].find(rel) != longrel[hcat][dcat].end(); +} + +//---------------------------------------------------------------------------------------------------- + +inline bool Grammar::is_sgl(Role r) +{ + return sgl[r]; +} + +//---------------------------------------------------------------------------------------------------- + +inline RoleSet Grammar::is_obl(Cat c) +{ + return obl[c]; +} + +//==================================================================================================== #endif Index: src/dgp/main.cc =================================================================== --- src/dgp/main.cc (revision 5f4d9c3b32eea7b6643a751aa75bdb05b7d41576) +++ src/dgp/main.cc (revision e7de6cc88c605c4f810cbc852e843294b4b0e8ac) @@ -11,5 +11,5 @@ #include "sgraph.hh" #include "grammar.hh" -#include "dgp0.hh" +#include "dgp1.hh" #include "../common/common.h" #include "cmdline.h" @@ -25,5 +25,5 @@ Grammar grammar; MGraph mgraph; -SGraph sgraph; +SGraph sgraph(mgraph); FILE* grammarf; @@ -65,4 +65,11 @@ fclose(grammarf); + + + // grammar.write(cout); + // exit(0); + + + mgraph.clear(); sgraph.clear(); @@ -83,5 +90,5 @@ if(strcmp(segtype,"EOS")==0) { - dgp0(); // parametry!!! MGraph, SGraph, Grammar + dgp1(); // parametry!!! MGraph, SGraph, Grammar output(); @@ -105,5 +112,5 @@ if(seg_mnode[si]>=0) { - MNode& m=mgraph.nodes[seg_mnode[si]]; + MNode& m=mgraph[seg_mnode[si]]; for(vector::iterator s=m.snodes.begin(); s!=m.snodes.end(); ++s) { Index: src/dgp/mgraph.cc =================================================================== --- src/dgp/mgraph.cc (revision 5f4d9c3b32eea7b6643a751aa75bdb05b7d41576) +++ src/dgp/mgraph.cc (revision e7de6cc88c605c4f810cbc852e843294b4b0e8ac) @@ -4,17 +4,22 @@ #include "const.hh" -#include +#include int MGraph::add_node(char* seg) { - nodes[n].clear(); + MNode newnode; + newnode.clear(); - char field1[80], field3[80], descr[256], gph[256]; + char field1[80], field3[80], field4[256], descr[256], gph[256]; char* cat; getfield(seg,"1",field1); - nodes[n].pos=atoi(field1); + newnode.pos=atoi(field1); getfield(seg,"3",field3); + + getfield(seg,"4",field4); + strcpy(newnode.form,field4); + if(!getfield(seg,"lem",descr)) strcpy(descr,"?,?"); @@ -23,11 +28,10 @@ if(*cat) ++cat; -// Cat::add(cat); if(Cat::index(cat)>0) - nodes[n].cat=cat; + newnode.cat=cat; else - nodes[n].cat="NULL"; + newnode.cat="NULL"; - nodes[n].pred.clear(); + newnode.pred.clear(); char* tok; @@ -41,5 +45,5 @@ char* ids=strtok(gph,":"); - if(n!=atoi(ids)){fprintf(stderr,"Invalid node id in line ?. Program aborted.\n"); exit(1); } + if(size() != atoi(ids)) {fprintf(stderr,"Invalid node id in line ?. Program aborted.\n"); exit(1); } char *preds; @@ -47,8 +51,9 @@ { previd=atoi(preds); - nodes[n].pred.push_back(&nodes[previd]); + newnode.pred.push_back(previd); } - return n++; + nodes.push_back(newnode); + return nodes.size()-1; } Index: src/dgp/mgraph.hh =================================================================== --- src/dgp/mgraph.hh (revision 5f4d9c3b32eea7b6643a751aa75bdb05b7d41576) +++ src/dgp/mgraph.hh (revision e7de6cc88c605c4f810cbc852e843294b4b0e8ac) @@ -8,26 +8,33 @@ #include "../common/common.h" + +using namespace std; + class MNode { public: - char type[MAXFORMLEN]; + int pos; + char form[256]; Cat cat; - int pos; - vector pred; + vector pred; vector snodes; void clear() { snodes.clear(); }; }; - + class MGraph { - public: +public: - MNode nodes[MAXNODES]; - int n; + void clear() { nodes.clear(); } + int size() { return nodes.size(); } + int add_node(char* seg); + MNode& operator[](int i) { return nodes[i]; } - void clear() { n=0; }; - int add_node(char* seg); +private: + + vector nodes; + }; Index: src/dgp/sgraph.cc =================================================================== --- src/dgp/sgraph.cc (revision 5f4d9c3b32eea7b6643a751aa75bdb05b7d41576) +++ src/dgp/sgraph.cc (revision e7de6cc88c605c4f810cbc852e843294b4b0e8ac) @@ -1,35 +1,35 @@ #include "global.hh" #include "sgraph.hh" -#include "mgraph.hh" #include "grammar.hh" #include "const.hh" -#include +#include +#include +extern MGraph mgraph; -int SGraph::add_base_snode(MNode* mn) +//==================================================================================================== + +int SGraph::add_base_snode(int mnodeind) { - int nodeind=n; - SNode &node=nodes[n]; + SNode& newnode = makenewnode(); - node.clear(); + newnode.mnode=mnodeind; - node.mnode=mn; - - for(vector::iterator pm=node.mnode->pred.begin(); pm!=node.mnode->pred.end(); ++pm) - for(vector::iterator ps=(*pm)->snodes.begin(); ps!=(*pm)->snodes.end(); ++ps) + for(vector::iterator pm=mgraph[newnode.mnode].pred.begin(); pm!=mgraph[newnode.mnode].pred.end(); ++pm) + for(vector::iterator ps=mgraph[*pm].snodes.begin(); ps!=mgraph[*pm].snodes.end(); ++ps) if(nodes[*ps].in_LH) { - node.LV.set(*ps); - if(nodes[*ps].saturated()) node.LV |= nodes[*ps].LH; + newnode.LV.set(*ps); + if(nodes[*ps].saturated()) newnode.LV |= nodes[*ps].LH; } - mn->snodes.push_back(nodeind); - ++n; + mgraph[newnode.mnode].snodes.push_back(lastnodeind()); - node.in_LH=true; + newnode.in_LH=true; - return nodeind; + return lastnodeind(); } +//==================================================================================================== void SGraph::update_left(int headind, int depind) @@ -37,5 +37,5 @@ SNode &head=nodes[headind], &dep=nodes[depind]; - if(dep.saturated()) head.LV |= dep.LV, head.LD |= dep.LD; + if(dep.saturated()) head.LV |= dep.LV, head.LD |= dep.LD; } @@ -46,66 +46,82 @@ dep.LH.set(headind); - if(head.saturated()) - dep.LH |= head.LH; -} + if(head.saturated()) dep.LH |= head.LH; +} +//==================================================================================================== int SGraph::clone(int ancind, NodeProp newprop) { - int newind = n++; - SNode &newnode=nodes[newind]; + SNode &newnode=makenewnode(); SNode &ancnode = nodes[ancind]; - newnode.clear(); + + newnode.prop=newprop; newnode.mnode=ancnode.mnode; - newnode.mnode->snodes.push_back(newind); - return newind; + mgraph[newnode.mnode].snodes.push_back(lastnodeind()); + + return lastnodeind(); } - -//------------------------------------------------------------------------- -//------------------------------------------------------------------------- - +//==================================================================================================== int SGraph::print_node(FILE* f, int n, unsigned int info) { - char buf[1000]; - sprint_node(buf,n,info); + char buf[50000]; + sprint_node(buf,n,-1,info); fputs(buf,f); } -int SGraph::sprint_node(char* buf, int nodeind, unsigned int info) +//---------------------------------------------------------------------------------------------------- + +int SGraph::print_node_debug(FILE* f, const char* pref, int n, int anc) +{ + char buf[50000]; + sprint_node_debug(buf,pref,n,anc); + fputs(buf,f); +} + +//---------------------------------------------------------------------------------------------------- + +void SGraph::print_arc(FILE* f, int head, int dep, Role role, int dir) // 0 - left, 1 - right +{ + if(dir==0) + fprintf(f,"#A %s:%d <-- %d\n", role.str(), dep, head); + else + fprintf(f,"#A %s:%d --> %d\n", role.str(), head, dep); +} + +//==================================================================================================== + +int SGraph::sprint_node(char* buf, int nodeind, int anc, unsigned int info) { char* buf0=buf; - char descr[256]; - char nodeinfo[16]; SNode &node=nodes[nodeind]; buf+=sprintf(buf," dgp:%d",nodeind); + if(anc>=0) buf+=sprintf(buf,"(%d)",anc); buf+=sprintf(buf, saturated(nodeind) ? ";s" : ";u"); + if (info&HEADS || info&DEPS) + buf+=sprintf(buf,";"); + bool cont=false; + if (info&HEADS) - { - buf+=sprintf(buf,";"); for(vector::iterator h=node.heads.begin(); h!=node.heads.end(); ++h) { if(cont) buf+=sprintf(buf,","); else cont=true; - buf+=sprintf(buf,"++%s-%d/%d",h->role.str(),h->dst,h->anc); + buf+=sprintf(buf,"++%s-%d(%d~%d)",h->role.str(),h->dst,h->headanc,h->depanc); } - } - + if (info&DEPS) - { - buf+=sprintf(buf,";"); for(vector::iterator d=node.deps.begin(); d!=node.deps.end(); ++d) { // if(! nodes[d->dst].saturated()) continue; // NIE DRUKUJ NIENASYCONYCH PODRZEDNIKOW if(cont) buf+=sprintf(buf,","); else cont=true; - buf+=sprintf(buf,"--%s-%d/%d",d->role.str(),d->dst,d->anc); + buf+=sprintf(buf,"--%s-%d(%d~%d)",d->role.str(),d->dst,d->headanc,d->depanc); } - } if (info&SETS) @@ -113,13 +129,13 @@ int ord=0; buf+=sprintf(buf,";{"); - for(vector::iterator pm=node.mnode->pred.begin(); pm!=node.mnode->pred.end(); ++pm) - for(vector::iterator ps=(*pm)->snodes.begin(); ps!=(*pm)->snodes.end(); ++ps) + for(vector::iterator pm=mgraph[node.mnode].pred.begin(); pm!=mgraph[node.mnode].pred.end(); ++pm) + for(vector::iterator ps=mgraph[*pm].snodes.begin(); ps!=mgraph[*pm].snodes.end(); ++ps) buf+=sprintf(buf, ord++ ? ",%d" : "%d", *ps); buf+=sprintf(buf,"};{"); - ord=0;for(int j=0; j<=n; ++j) if(node.LV[j]) buf+=sprintf(buf, ord++ ? ",%d" : "%d", j); + ord=0;for(int j=0; j",(cont++)?",":"",i.str()); + if(node.prop.init_attached) + buf+=sprintf(buf,""); + if(node.prop.fin_attached) + buf+=sprintf(buf,""); + + stringstream oss; + for(list::iterator b = node.prop.boubbles.begin(); b != node.prop.boubbles.end(); b++) + oss << (cont++ ? "," : "") << **b; + buf+=sprintf(buf,oss.str().c_str()); } @@ -141,25 +170,14 @@ -int SGraph::sprint_node_debug(char* buf, const char* pref, int n) +int SGraph::sprint_node_debug(char* buf, const char* pref, int n, int anc) { char *buf0 = buf; buf+=sprintf(buf,"#%s",pref); - buf+=sprint_node(buf,n,HEADS|DEPS|SETS|CONSTRAINTS); + + buf+=sprintf(buf,"%-16s",form(n)); + + buf+=sprint_node(buf,n,anc,HEADS|DEPS|SETS|CONSTRAINTS); buf+=sprintf(buf,"\n"); return buf-buf0; } -int SGraph::print_node_debug(FILE* f, const char* pref, int n) -{ - char buf[1000]; - sprint_node_debug(buf,pref,n); - fputs(buf,f); -} - -void SGraph::print_arc(FILE* f, int left, int right, Role role, int dir) // 0 - left, 1 - right -{ - fprintf(f,"# %s:%s.%02d %s %s.%02d\n", - role.str(),nodes[left].mnode->type,left, - dir ? "-->" : "<--", - nodes[right].mnode->type,right); -} Index: src/dgp/sgraph.hh =================================================================== --- src/dgp/sgraph.hh (revision 5f4d9c3b32eea7b6643a751aa75bdb05b7d41576) +++ src/dgp/sgraph.hh (revision e7de6cc88c605c4f810cbc852e843294b4b0e8ac) @@ -9,38 +9,168 @@ #include "const.hh" +#include "mgraph.hh" #include "thesymbols.hh" - - -class MNode; - - +#include "boubble.hh" + + +using namespace std; + +//==================================================================================================== +// CLASS Arc +//==================================================================================================== struct Arc { int dst; Role role; - int anc; + int headanc; + int depanc; - Arc(int d, Role r, int a) : dst(d), role(r), anc(a) {}; - }; - + Arc(int d, Role r, int ha, int da) : dst(d), role(r), headanc(ha), depanc(da) {}; +}; + +//==================================================================================================== +// CLASS NodeProp +//==================================================================================================== struct NodeProp { - bitset required; - bitset forbidden; - - bool operator==(const NodeProp& p) - { return required==p.required && forbidden==p.forbidden; } - - void clear() - { required.reset(), forbidden.reset(); } - -}; - + NodeProp(); + NodeProp(const NodeProp& p); + ~NodeProp(); + + bool operator==(const NodeProp& p); + NodeProp& operator=(const NodeProp& p); + + void clear_boubbles(); + void merge_boubbles(list new_boubbles); + + void copy(const NodeProp& p); + void clear(); + + RoleSet required; + RoleSet forbidden; + RoleSet attached; + + bool init_attached; + bool fin_attached; + + FlagSet flags; + + list boubbles; +}; + +//---------------------------------------------------------------------------------------------------- + +inline +bool NodeProp::operator==(const NodeProp& p) +{ + if(required != p.required) return false; + if(forbidden != p.forbidden) return false; + if(attached != p.attached) return false; + if(flags != p.flags) return false; + 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()) + return false; + + return true; +} + +//---------------------------------------------------------------------------------------------------- + +inline +void NodeProp::clear_boubbles() +{ + for(list::iterator b = boubbles.begin(); b!=boubbles.end(); b++) + delete *b; + boubbles.clear(); +} + +//---------------------------------------------------------------------------------------------------- + +inline +void NodeProp::merge_boubbles(list new_boubbles) +{ + boubbles.merge(new_boubbles); +} + +//---------------------------------------------------------------------------------------------------- + +inline +void NodeProp::copy(const NodeProp& p) +{ + required=p.required; + forbidden=p.forbidden; + attached=p.attached; + flags=p.flags; + init_attached=p.init_attached; + fin_attached=p.fin_attached; + for(list::const_iterator b = p.boubbles.begin(); b!=p.boubbles.end(); b++) + boubbles.push_back(new Boubble(**b)); +} + +//---------------------------------------------------------------------------------------------------- + +inline +NodeProp::~NodeProp() +{ + clear_boubbles(); +} +//---------------------------------------------------------------------------------------------------- + +inline +NodeProp::NodeProp() +{ + clear(); +} + +//---------------------------------------------------------------------------------------------------- + +inline +NodeProp::NodeProp(const NodeProp& p) +{ + copy(p); +} + +//---------------------------------------------------------------------------------------------------- + +inline +NodeProp& NodeProp::operator=(const NodeProp& p) +{ + clear(); + copy(p); + return *this; +} + +//---------------------------------------------------------------------------------------------------- + +inline +void NodeProp::clear() +{ + required.reset(); + forbidden.reset(); + attached.reset(); + init_attached=false; + fin_attached=false; + clear_boubbles(); +} + +//==================================================================================================== +// CLASS SNode +//==================================================================================================== struct SNode { - MNode* mnode; + int mnode; NodeProp prop; @@ -54,9 +184,20 @@ vector deps; - void clear() { prop.clear(), LV.reset(), LD.reset(), LH.reset(), heads.clear(), deps.clear(); } - bool saturated() { return prop.required.none(); } -}; - - + void clear(); + bool saturated(); +}; + +//---------------------------------------------------------------------------------------------------- +inline +void SNode::clear() +{ prop.clear(), LV.reset(), LD.reset(), LH.reset(), heads.clear(), deps.clear(); } +//---------------------------------------------------------------------------------------------------- +inline +bool SNode::saturated() +{ return prop.required.none(); } + +//==================================================================================================== +// SGraph CLASS +//==================================================================================================== class SGraph @@ -64,35 +205,44 @@ public: - SNode nodes[MAXNODES]; - int n; // number of nodes - - enum Output { HEADS=1, DEPS=2, SETS=4, CONSTRAINTS=8 }; - - SGraph() : n(0) {} - - void clear() { n=0; } - - int add_base_snode(MNode* mn); - int clone(int ancind, NodeProp newprop); + enum Output { HEADS=1, DEPS=2, SETS=4, CONSTRAINTS=8, BOUBBLES=16 }; + + SGraph(MGraph& mg) : mgraph(mg) { clear(); } + + SNode& operator[](const int i) { return nodes[i]; } + + void clear() { nodes.clear(); } + int add_base_snode(int mnodeind); + int clone(int ancind, NodeProp newprop); void update_left(int headind, int depind); void update_right(int headind, int depind); - bool visible(int left, int right); bool saturated(int node); - //-------------------------------------------------------------------- - - void read(FILE* f); - void write(FILE* f, list nodelist, unsigned int info); - - int sprint_node(char* buf, int n, unsigned int info); + Cat cat(int i) const { return mgraph[nodes[i].mnode].cat; } + char* form(int i) const { return mgraph[nodes[i].mnode].form; } + int print_node(FILE* f, int n, unsigned int info); - int sprint_node_debug(char* buf, const char* pref, int n); - int print_node_debug(FILE* f, const char* pref, int n); + int print_node_debug(FILE* f, const char* pref, int n, int anc); void print_arc(FILE* f, int left, int right, Role role, int dir); // 0 - left, 1 - right -}; - + //private: + + int size() {return nodes.size(); } + +private: + + MGraph& mgraph; + + vector nodes; + + int lastnodeind() { return nodes.size()-1; } + SNode& makenewnode() { nodes.push_back(SNode()); nodes.back().clear(); return nodes.back(); } + + int sprint_node(char* buf, int n, int anc, unsigned int info); + int sprint_node_debug(char* buf, const char* pref, int n, int anc); +}; + +//---------------------------------------------------------------------------------------------------- inline bool SGraph::visible(int left, int right) @@ -101,4 +251,6 @@ } +//---------------------------------------------------------------------------------------------------- + inline bool SGraph::saturated(int node) { @@ -106,3 +258,5 @@ } +//---------------------------------------------------------------------------------------------------- + #endif Index: src/dgp/symbol.hh =================================================================== --- src/dgp/symbol.hh (revision 5f4d9c3b32eea7b6643a751aa75bdb05b7d41576) +++ src/dgp/symbol.hh (revision e7de6cc88c605c4f810cbc852e843294b4b0e8ac) @@ -3,7 +3,6 @@ #include -//#include #include -#include +#include #include #include @@ -58,5 +57,5 @@ /// Symbol class template. /** The template argument determines the symbol space. - Each space is created with symbol "NULL" with indexed 0 already in. + Each space is created with symbol "NULL" with index 0 already in. */ @@ -104,5 +103,10 @@ Symbol(const char * s) : val(defs[s]) {}; - + + Symbol(string s) : val(defs[(char*)s]) {}; + + + bool empty() const { return val==0; } + /// Symbol to char* conversion. If symbol is invalid, NULL is returned. const char* str() const { return (val>=0 && val -typedef Symbol<1> Cat; +using namespace std; -typedef Symbol<2> Role; -typedef list RoleList; -typedef list::iterator RoleListIter; -typedef bitset RoleSet; -typedef set Roles; -typedef Roles::iterator RolesIter; +typedef Symbol<1> Cat; +typedef bitset CatSet; -typedef Symbol<3> Constr; -typedef list ConstrList; +typedef Symbol<2> Role; +typedef list RoleList; +typedef list::iterator RoleListIter; +typedef bitset RoleSet; +typedef set Roles; +typedef Roles::iterator RolesIter; + +typedef Symbol<3> Constr; +typedef list ConstrList; typedef list::iterator ConstrListIter; -typedef Symbol<4> Rel; +typedef Symbol<4> LongRel; +typedef set LongRels; -typedef Symbol<5> Flag; -typedef bitset FlagSet; +typedef Symbol<5> Flag; +typedef bitset FlagSet; + +typedef Symbol<6> Prop; +typedef bitset PropSet; #endif Index: src/dgp/tre =================================================================== --- src/dgp/tre (revision 5f4d9c3b32eea7b6643a751aa75bdb05b7d41576) +++ (revision ) @@ -1,304 +1,0 @@ -#!/usr/bin/ruby -I /usr/local/lib/utt -I $HOME/.local/lib/utt - -$: << "#{ENV['HOME']}/.local/lib/utt" -$: << "/usr/local/lib/utt" - -require 'getoptlong' -require 'seg.rb' - -opts = GetoptLong.new( -[ '--help', '-h', GetoptLong::NO_ARGUMENT ], -[ '--debug', '-d', GetoptLong::NO_ARGUMENT ], -[ '--format', '-F', GetoptLong::REQUIRED_ARGUMENT ], -[ '--info', '-I', GetoptLong::REQUIRED_ARGUMENT ], -[ '--only-trees','-t', GetoptLong::NO_ARGUMENT ]) - -$helptext= -"The program generates trees from the graph output by dgp. dgp must\n"+ -"must be run with '-i ds' option.\n\n"+ -"Command: tre [options]\n\n"+ -"Options:\n"+ -"--help -h Print help (this text) and exit.\n"+ -"--debug -d Verbose output. For developers only.\n"+ -"--format=s -F s Output format. Recognized values:\n"+ -" a root + list of arcs\n"+ -" p parenthesized notation\n"+ -" h human readable indented tree format\n"+ -" Multiple values are allowed. (default p)\n"+ -"--info=s -I s Information printed. Recognized values:\n"+ -" n node identifier\n"+ -" f surface form\n"+ -" m morphological information\n"+ -" l arc labels\n"+ -"--only-trees -t Do not copy input. Print trees only.\n" - -$DEBUG=false -$FORMAT='p' -$INFO='DEFAULT' -$ONLYTREES=false - -opts.each do |opt, arg| - case opt - when '--help' - print $helptext - exit 0 - when '--debug' - $DEBUG=true - when '--format' - $FORMAT=arg - when '--info' - $INFO=arg - when '--only-trees' - $ONLYTREES=true - else - print "Unknown option #{opt}. Ignored.\n" - end -end - -if $INFO=='DEFAULT' - case $FORMAT - when 'p','a' - $INFO='nl' - when 'h' - $INFO='fmnl' - end -end - -$dgpsep=';' - -def tre(input) - $gphid=[] - $form=[] - $lem=[] - nodes=[] - count=0 - seg=Seg.new - for line in input - print line unless $ONLYTREES - seg.set(line) - if dgp=seg['dgp'] - if nodes==[] && seg[3]!='BOS' - print "A sentence must start with BOS segment. Aborting.\n" - return - end - - id=dgp[/^\d+/].to_i - - if gph=seg['gph'] - $gphid[id]=gph[/^\d+/].to_i - else - print "No gph field. Aborting.\n" - return - end - - $form[$gphid[id]]=seg[4] - $lem[$gphid[id]]=seg['lem'] - - nodes[id] = [seg[1].to_i,dgp] - - if seg[3]=='EOS' - $pref = "#{seg[1]} #{seg[2]} SYN *" - parsegraph(nodes) - printgraph if $DEBUG - $thetrees=[] - gentrees2 - for t in $thetrees - count += 1 - t1=ground(t) - case $FORMAT - when /a/ - print "#{$pref} tre:#{count} arc:" - printarcs(t1[0],t1[1]) - print "\n" - when /p/ - print "#{$pref} tre:#{count} par:" - printpar(t1[0],t1[1]) - print "\n" - when /h/ - print "#\n# tree #{count}\n# ------\n" - printtree(t1[0],t1[1],0) - end - end - nodes=[] - end - end - end -end - - -def nodeinfo(id) - info="" - if $INFO =~ /n/ - info += id.to_s - info += '.' if $INFO =~ /[fm]/ - end - if $INFO =~ /f/ - info += $form[id] - info += ';' if $INFO =~ /m/ - end - if $INFO =~ /m/ - info += $lem[id] - end - info -end - - -def printarcs(root,arcs) - print nodeinfo(root) - for a in arcs - print ';' - print "#{a[2]}:" if $INFO =~ /l/ - print nodeinfo(a[0])+'-'+nodeinfo(a[1]) - end -end - -def printtree(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(arc[1],arcs,o+1) - end -end - -def printpar(root,arcs) - print nodeinfo(root) - deps = arcs.select{ |a| a[0]==root }.sort{|a,b| a[1]<=>b[1] } - unless deps == [] - print '(' - cont=false - for arc in deps - if cont then print ',' else cont=true end - print arc[2],':' if $INFO =~ /l/ - printpar(arc[1],arcs) - end - print ')' - end -end - - -def parsegraph(nodes) - - $n =nodes.length - $sat =[]; - - $vis =[]; - $succ=[]; - $lhs =[]; - $arcs=[]; - $pos=[] - - for dgp in nodes - - parts = dgp[1].split($dgpsep,6) - - if parts[3]==nil || parts[4]==nil || parts[5]==nil - $stderr.print "ERR: tre requires dgp be called with '--info s' option. Aborting.\n" - exit - end - - i = parts[0].to_i - $pos[i] = dgp[0].to_i - $sat << i if parts[1]=="s" - $arcs |= parts[2].split(',').map{ |a| case a - when /\-\-(\w+)-(\d+)\/(\d+)/ - [i, $2.to_i, $1, $3.to_i] - when /\+\+(\d+)-(\w+)\/(\d+)/ - [$1.to_i, i, $2, $3.to_i] - end } - $succ |= parts[3][1..-2].split(',').map{|x| [x.to_i,i]} - $vis |= parts[4][1..-2].split(',').map{|x| [x.to_i,i]} - $lhs |= parts[5][1..-2].split(',').map{|x| [x.to_i,i]} + [[i,i]] - - end -end - - -def ground(t) - [ $gphid[t[0]] , t[1].map{|a| [$gphid[a[0]],$gphid[a[1]],a[2]]} ] -end - - -def gentrees2() - $thetrees=[]; - bos=0; eos=$n-1; - roots = (1...eos).select{|i| $vis.include? [i,eos]}.select{|i| $vis.include? [bos,i]} - if $DEBUG then print "ROOTS: #{roots.inspect}\n" end - for i in roots - $theroot=i - for r in buildR(i , eos, []) - (rmin,rmax,rtree) = r - buildR(bos, rmin, rtree) - end - end -end - - -def buildR(min, max, tree) - 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[1],a[3],tree+[a]) - (rmin,rmax,rarcs) = r - for l in buildR(min,rmin,rarcs) - (lmin,lmax,larcs) = l - trees << [lmin,rmax,larcs] - end - end - end - for i in (0...$n).select{|i| $succ.include?([i,max])}.select{|i| $lhs.include?([min,i])} - for l in buildL(min,i,tree) - (lmin,lmax,larcs) = l - trees << [lmin,lmax,larcs] - end - end - trees -end - - -def buildL(min,max,tree) - if $DEBUG then print "buildL--#{min}--#{max}--#{tree.inspect}\n" end - if $pos[min]==$pos[max] - if min==0 && max==0 - $thetrees.push [$theroot,tree] - if $DEBUG then print "adding tree: #{tree.inspect}\n" end - end - return [[max,max,tree]] - end - trees=[] - 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],max,tree+[arc]) - (rmin,rmax,rarcs) = r - for l in buildL(min,rmin,rarcs) - (lmin,lmax,larcs) = l - trees << [lmin,lmax,larcs] - end - end - end - trees -end - - -def printgraph() - - print "N: #{$n}\n" - print "SAT: #{set_to_s($sat)}\n" - print "SUCC: #{rel_to_s($succ)}\n" - print "VIS: #{rel_to_s($vis)}\n" - print "LHS: #{rel_to_s($lhs)}\n" - print "ARCS: #{arcs_to_s($arcs)}\n" -end - -def set_to_s(s) "{#{s.join(',')}}" end -def rel_to_s(r) "{#{r.map{|p| "(#{p[0]},#{p[1]})"}.join(',')}}" end -def arc_to_s(q) "-#{q[0]}-#{q[2]}-#{q[1]}/#{q[3]}" end -def arcs_to_s(a) "{#{a.map{|q| arc_to_s(q)}.join(',')}}" end - -###################################################################### - -tre($stdin)