Index: app/src/dgp/Makefile
===================================================================
--- app/src/dgp/Makefile	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
+++ app/src/dgp/Makefile	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
@@ -0,0 +1,38 @@
+
+
+SHELL = /bin/sh
+
+vpath %.o  o
+
+CXXFLAGS = -O2 -static
+
+sources = main.cc grammar.cc symbol.cc mgraph.cc sgraph.cc dgp0.cc cmdline.cc \
+          common.cc global.cc
+
+bin  = dgp
+
+# plik *.o sa umieszczane w podkatalogu o
+objs = $(sources:%.cc=o/%.o)
+
+${bin}: ${objs}
+	${CXX} ${CXXFLAGS} -o $@ ${objs}
+
+include $(sources:.cc=.d)
+
+o/%.o: %.cc
+	${CXX} -c ${CXXFLAGS} -o $@ $<
+
+%.d: %.cc
+	$(CC) -MM $(CPPFLAGS) $< > $@.$$$$; \
+	sed 's,\($*\)\.o[ :]*,o/\1.o $@ : ,g' < $@.$$$$ > $@; \
+	rm -f $@.$$$$
+
+cmdline.cc cmdline.h : cmdline.ggo
+	gengetopt --c-extension=cc -i cmdline.ggo
+
+clean:
+	rm ${bin} ${objs} cmdline.cc cmdline.h
+	rm -rf *.d
+
+prof: dgp
+	gprof dgp ~/tmp/dgp-pl/gmon.out > dgp.prof
Index: app/src/dgp/Makefile.user
===================================================================
--- app/src/dgp/Makefile.user	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
+++ app/src/dgp/Makefile.user	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
@@ -0,0 +1,3 @@
+
+gram.dgp: gram.dgc
+	dgc -c cats.dgc < gram.dgc > gram.dgp
Index: app/src/dgp/Seg.rb
===================================================================
--- app/src/dgp/Seg.rb	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
+++ app/src/dgp/Seg.rb	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
@@ -0,0 +1,31 @@
+
+class Seg
+  
+  def initialize(s="")
+    @line=s
+    self
+  end
+
+  def to_s
+    @line.chomp
+  end
+
+  def set(s)
+    @line=s
+    self
+  end
+
+  def field(key)
+    if key.class==Fixnum
+      @line.split[key-1]
+    elsif key.class==String
+      @line =~ /\s#{key}:(\S+)/; $1
+    end
+  end
+  alias [] field
+
+  def fields
+    @line.split
+  end
+
+end
Index: app/src/dgp/attr.pm
===================================================================
--- app/src/dgp/attr.pm	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
+++ app/src/dgp/attr.pm	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
@@ -0,0 +1,133 @@
+package attr;
+
+use locale;
+use strict;
+
+use Data::Dumper;
+
+our $pos_re    = qr/(?:[[:upper:]]+)/;
+our $attr_re   = qr/(?:[[:upper:]]+)/;
+our $val_re    = qr/(?:[[:lower:][:digit:]+?!*-]|<[^>\n]+>)/;
+our $av_re     = qr/(?:$attr_re$val_re+)/;
+our $avlist_re = qr/(?:$av_re+)/;
+our $cat_re    = qr/(?:$pos_re(?:\/$avlist_re)?)/;
+
+sub match(\@\@)
+{
+    my ($cat1,$avs1)= @{shift @_};
+    my ($cat2,$avs2)= @{shift @_};
+
+    if($cat1 ne $cat2 && $cat1 ne '*' && $cat2 ne '*')
+    {
+	return 0; 
+    }
+    else
+    {
+      ATTR:for my $attr (keys %$avs1)
+      {
+	  if(exists $avs2->{$attr})
+	  {
+	      for my $val (keys %{$avs1->{$attr}})
+	      {
+		  next ATTR if $avs2->{$attr}->{$val};
+	      }
+	      return 0;
+	      last ATTR;
+	  }
+      }
+    }
+
+    return 1;
+}
+
+sub agree(\@\@$)
+{
+    my $val1 = $_[0]->[1]->{$_[2]};
+    my $val2 = $_[1]->[1]->{$_[2]};
+
+    return 1 if !$val1 || !$val2;
+
+    for my $v (keys %$val1)
+    {
+	return 1 if exists $val2->{$v};
+    }
+    return 0;
+}
+
+# funkcja parse
+# arg:     deskrypcja
+# warto¶æ: referencja do tablicy [<cat>, <avs>],
+#          gdzie <avs> jest referencja do hasza, zawierajacego pary
+#          atrybut=>hasz warto¶ci (pary warto¶æ=>1), czyli np.
+
+#         [
+#           'ADJ',
+#           {
+#             'KOLEDZY' => {
+#                            '<alojzy>' => 1,
+#                            '<karol>' => 1,
+#                            '<jan>' => 1
+#                          },
+#             'C' => {
+#                      'p' => 1,
+#                      'a' => 1,
+#                      'i' => 1
+#                    },
+#             'N' => {
+#                      'p' => 1
+#                    }
+#           }
+#         ];
+
+sub parse ($)
+{
+    my ($dstr)=@_;
+    my $avs={};
+    my ($cat,$attrlist) = split '/', $dstr;
+  ATTR:
+#    while( $attrlist =~ /([[:upper:]]+)((?:[[:lower:][:digit:]+?!*-]|<[^>\n]+>)+)/g )
+    while( $attrlist =~ /($attr_re)($val_re+)/g )
+    {
+	my ($attrstr,$valstr)=($1,$2);
+	my %vals;
+	while($valstr =~ /$val_re/g)
+	{
+	    my $val = $&;
+	    next ATTR if $val eq '*';
+	    $val =~ s/^<([[:lower:]])>$/$1/;
+	    $vals{$val}=1;
+	}
+	
+	$avs->{$attrstr} = \%vals; # dlaczego to dziala? %vals jest lokalne
+    }
+    [$cat, $avs];
+}
+
+# funkcja unparse
+# arg:     jak warto¶æ parse
+# warto¶æ: deskrypcja - napis
+
+sub unparse (\@)
+{
+    my ($cat,$avs)= @{shift @_};
+    my $dstr=$cat;
+    my @attrs = keys %$avs;
+    if(@attrs)
+    {
+	$dstr .= '/';
+	for my $attr ( sort @attrs )
+	{
+	    $dstr .= $attr . (join '', sort keys %{$avs->{$attr}});
+	}
+    }
+    $dstr;
+}
+
+
+sub canonize ($)
+{
+    unparse @{parse @_[0]} ;
+}
+
+
+1;
Index: app/src/dgp/canonize
===================================================================
--- app/src/dgp/canonize	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
+++ app/src/dgp/canonize	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
@@ -0,0 +1,48 @@
+#!/usr/bin/perl
+
+#package:	UAM TExt Tools
+#component:	canonize
+#version:	1.0
+#author:	Tomasz Obrebski
+
+use strict;
+use Getopt::Long;
+use attr;
+#use File::HomeDir;
+#use lib "$ENV{HOME}/.utt/lib/perl";
+
+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: app/src/dgp/cmdline.ggo
===================================================================
--- app/src/dgp/cmdline.ggo	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
+++ app/src/dgp/cmdline.ggo	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
@@ -0,0 +1,42 @@
+package "dgp"
+version "0.1"
+
+option  "process"	p	"Process segments with this tag."
+				string no multiple
+
+option  "select"	s	"Select only segments with this field. [Not implemented.]" 
+				string no multiple
+
+option  "ignore"	S	"Select only segments without this field. [Not implemented]" 
+				string no multiple
+
+option  "input"		f	"Input file"
+				string typestr="filename" no
+
+option  "output"	o	"Output file"
+				string typestr="filename" no
+
+option  "failed"	e	"Fail file"
+				string typestr="filename" no
+
+option  "copy"		c	"Copy unprocessed"
+				flag off
+
+option	"grammar"	g	"Grammar file"
+				string typestr="filename" default="dgp.dg"
+
+option  "long"		l	"Long output"
+				flag off
+
+option  "interactive"	-	"Interactive use."
+				flag off
+
+option  "debug"		d	"Debug mode."
+				flag off
+
+option	"info"		i	"Print info. 
+h - heads         d - dependents
+s - sets
+c - constraints	  n - node/arc counts	t - parse time
+"
+				string default="gh"
Index: app/src/dgp/common.cc
===================================================================
--- app/src/dgp/common.cc	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
+++ app/src/dgp/common.cc	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
@@ -0,0 +1,39 @@
+#include <stdlib.h>
+#include <string.h>
+#include "common.h"
+
+FILE* inputf=stdin;
+FILE* outputf=stdout;
+FILE* failedf=stdout;
+bool copy_processed=0;
+
+void process_common_options(gengetopt_args_info args)
+{
+  if(args.help_given)
+      cmdline_parser_print_help ();
+
+  if(args.input_given)
+    if(!(inputf=fopen(args.input_arg,"r")))
+    {
+      fprintf(stderr,"No such file: %s.\n", args.input_arg);
+      exit(1);
+    }
+  
+  if(args.output_given)
+    if(!(outputf=fopen(args.output_arg,"w")))
+    {
+      fprintf(stderr,"Cannot open output file: %s.\n", args.output_arg);
+      exit(1);
+    }
+  
+  if(args.failed_given)
+      if(!(failedf=fopen(args.failed_arg,"w")))
+      {
+	fprintf(stderr,"Cannot open output file: %s.\n", args.failed_arg);
+	exit(1);
+      }
+
+
+  if(args.copy_given)
+    copy_processed=true;
+}
Index: app/src/dgp/common.h
===================================================================
--- app/src/dgp/common.h	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
+++ app/src/dgp/common.h	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
@@ -0,0 +1,277 @@
+#ifndef __COMMON_H
+#define __COMMON_H
+
+#include <stdio.h>
+#include <ctype.h>
+
+#include "cmdline.h"
+#include "const.hh"
+
+
+/**************************************************
+ * Stale dotyczace wejscia/wyjscia
+ */
+
+#define EMPTYFORM '*'
+#define INFIELD_SEP ':'
+#define MAXAUX 64
+#define FIELD_SEP " \t\n"
+
+/**************************************************/
+
+
+extern FILE* inputf;
+extern FILE* outputf;
+extern FILE* failedf;
+
+extern char* input_filename;
+extern char* output_filename;
+extern char* failed_filename;
+
+extern bool copy_processed;
+extern bool append_output;
+extern bool append_failed;
+
+extern void process_common_options(gengetopt_args_info args);
+
+
+
+/**************************************************/
+/*
+parameters:
+  -seg  - segment
+  -name - field name
+  +val  - field contents
+return value:
+  1 if specified field exists, 0 otherwise
+*/
+
+inline int getfield(const char* seg, const char* pref, char* val)
+{
+  const char* p=seg;
+
+  while(*p==' ') ++p;
+  
+ pos:
+  if(isdigit(*p) or *p=='*')
+    if(*pref=='1') return sscanf(p,"%s",val); else while(*p!=' ') ++p; 
+  else
+    if(*pref=='1') return 0; else goto type;
+
+  while(*p==' ') ++p;
+  
+ len:
+  if(isdigit(*p) or *p=='*')
+    if(*pref=='2') return sscanf(p,"%s",val); else while(*p!=' ') ++p; 
+  else
+    if(*pref=='2') return 0; else goto type;
+
+  while(*p==' ') ++p;
+  
+ type:
+
+  if(*pref=='3') return sscanf(p,"%s",val); else while(*p!=' ') ++p;
+
+  while(*p==' ') ++p;
+
+ form:
+  if(*pref=='4') return sscanf(p,"%s",val); else while(*p!=' ') ++p;
+
+  while(*p==' ') ++p;
+
+ annotation:
+  do p=strstr(p,pref); while(p!=NULL && *(p-1)!=' ' && *(p-1)!='\t');
+  
+  if(p==NULL) return 0;
+  else
+  {
+    p+=strlen(pref);
+    int len=strcspn(p,FIELD_SEP "\n\r\f\0");
+    strncpy(val,p,len);
+    val[len]='\0';
+    return 1;
+  }
+}
+
+
+/*
+parameters:
+  +seg - segment
+  -pref - prefix of the new field
+  -val  - contents of the new field
+return value:
+  1 - success, 0 - fail (limit on segment length exceeded)
+*/
+inline int addfield(char *seg, const char *pref, const char *val)
+     // zalozenie, ze seg konczy sie znakiem \n
+{
+  if(strlen(seg)+strlen(pref)+strlen(val) >= MAXLINE) return 0; // bezpieczniej, ale wolniej
+
+  int seglen=strlen(seg);
+  sprintf(seg+(seglen-1)," %s%s\n",pref,val);
+  return 1;
+}
+
+
+inline
+bool processseg(const char* s, gengetopt_args_info& args)
+{
+  bool ret = !args.process_given;
+  char field[MAXAUX];
+    
+  if(args.process_given)
+  {
+    getfield(s,"3",field);
+    for(int i=0; i<args.process_given; ++i)
+      if(strcmp(args.process_arg[i],field)==0)
+      {
+        ret=true;
+        break;
+      }
+  }
+
+  for(int i=0; i<args.select_given; ++i)
+    if(! getfield(s,args.select_arg[i],field))
+      ret=false;
+  
+  for(int i=0; i<args.ignore_given; ++i)
+    if(getfield(s,args.ignore_arg[i],field))
+      ret=false;
+
+  return ret;
+}
+
+
+/* DEPRICATED */
+
+
+/* definicja struktury wejscia/wyjscia
+ */
+struct Segment
+{
+  int filepos, len;
+  char* tag;
+  char* form;
+  char* aux[MAXAUX];
+  int auxn;
+
+  bool parse(char* line);
+  char* getfield(char* fieldname);
+  void print(char* line);
+  bool addfield(char* s);
+  bool clearfields();
+};
+
+/*
+ * Sprawdza czy nalezy przetwarzac dany segment.
+ */
+
+inline
+bool process_seg(Segment& s, gengetopt_args_info& args)
+{
+  bool ret = !args.process_given;
+
+  for(int i=0; i<args.process_given; ++i)
+    if(strcmp(args.process_arg[i],s.tag)==0)
+      {
+        ret=true;
+        break;
+      }
+
+  for(int i=0; i<args.select_given; ++i)
+    if(! s.getfield(args.select_arg[i]))
+      ret=false;
+
+  for(int i=0; i<args.ignore_given; ++i)
+    if(s.getfield(args.ignore_arg[i]))
+      ret=false;
+
+  return ret;
+}
+
+
+/*
+ * FUNKCJE OBSLUGUJACE WEJSCIE/WYJSCIE
+ */
+// napisy zostaj na miejscu (w line), tylko wskazniki sa ustawian
+// i zara dopisywane zera s dopisywane
+
+inline
+bool Segment::parse(char* line)
+{
+  auxn=0;
+  char* field;
+  if((field=strtok(line,FIELD_SEP))!=NULL)
+    filepos=atoi(field); // nie sprawdzana poprawnosc
+  else
+    return false;
+  if((field=strtok(NULL,FIELD_SEP))!=NULL)
+    len=atoi(field); // nie sprawdzana poprawnosc
+  else return false;
+  if((tag=strtok(NULL,FIELD_SEP))==NULL) return false;
+  if((form=strtok(NULL,FIELD_SEP))==NULL)
+    return false;
+/*   else */
+/*     if(form[0] == EMPTYFORM && form[1] =='\0') */
+/*       form=NULL; */
+
+  while((aux[auxn]=strtok(NULL,FIELD_SEP))!=NULL) ++auxn;
+
+  return true;
+}
+
+
+inline char* Segment::getfield(char* f)
+{
+  int flen=strlen(f);
+  for(int i=0; i<auxn; ++i)
+    if(strncmp(aux[i],f,flen)==0 && aux[i][flen]==INFIELD_SEP)
+      return aux[i]+flen+1;
+  return NULL;
+}
+
+inline bool Segment::clearfields() {
+  for (int i=0; i<auxn; ++i) {
+    //    free(aux[i]);
+    aux[i] = NULL;
+  }
+  auxn=0;
+  return true;
+}
+
+inline // NIEEFEKTYWNE
+void Segment::print(char* line)
+{
+  sprintf(line,"%04d %02d %s", filepos, len, tag);
+  if(form)
+    {
+      strcat(line," ");
+      strcat(line,form);
+    }
+  else
+    if(auxn)
+      strcat(line," *");
+
+  for(int i=0; i<auxn; ++i)
+    {
+      strcat(line," ");
+      strcat(line,aux[i]);
+    }
+
+  strcat(line,"\n");
+}
+
+
+inline
+bool Segment::addfield(char* s)
+{
+  if(auxn<MAXAUX)
+    {
+      aux[auxn++]=s;
+      return true;
+    }
+  else
+    return false;
+}
+
+#endif
Index: app/src/dgp/const.hh
===================================================================
--- app/src/dgp/const.hh	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
+++ app/src/dgp/const.hh	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
@@ -0,0 +1,12 @@
+#ifndef CONST_HH
+#define CONST_HH
+
+#define MAXTYPES 32
+#define MAXNODES 1024
+#define MAXCONSTRS 32
+#define MAXLINE 256
+#define MAXFORMLEN 64
+#define MAXDESCRLEN 80
+#define FIELDSEP " \n\t"
+
+#endif
Index: app/src/dgp/dgc
===================================================================
--- app/src/dgp/dgc	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
+++ app/src/dgp/dgc	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
@@ -0,0 +1,206 @@
+#!/usr/bin/perl
+
+#package:	UAM Text Tools
+#component:	dgc (dg compiler)
+#version:	1.0
+#author:	Tomasz Obrebski
+
+#use lib "ENV{HOME}/.utt/lib/perl";
+#use strict;
+use Getopt::Long;
+use Data::Dumper;
+
+use attr;
+#use File::HomeDir;
+
+my $help=0;
+my $catfile=0;
+my $dicfile=0;
+my $gramfile=0;
+
+my $ncat=0;
+my $nrole=0;
+my $nsgl=0;
+my $nleft=0;
+my $nright=0;
+my $nreq=0;
+my $nlink=0;
+
+GetOptions("help|h" => \$help,
+	   "catfile|c=s" => \$catfile,
+	   "dicfile|d=s" => \$dicfile,
+	   "gramfile|g=s" => \$gramfile);
+
+if($help)
+{
+    print <<'END'
+Usage: dgpcompile [OPTIONS]
+
+Options:
+   --cats -c filename		List of syntactic categories.
+   --dic  -d filename           Dictionary.
+   --help -h			Help.
+END
+;
+    exit 0;
+}
+
+die("At least one of --cats and --dic must be given.\n") if !$catfile && !$dicfile;
+
+my %cats;
+my %roles;
+my %agr;
+my %gov;
+
+loadcats($catfile) if $catfile;
+extractcats($dicfile) if $dicfile;
+
+
+$cats_re = qr/(?:$attr::cat_re\s*(?:,\s*$attr::cat_re)*)/;
+
+# class parse_class:
+# /$attr::cat_re/g;
+
+while(<>)
+{
+    if(/^\s*AGR\s+(\S+)\s+(\S+)\s*$/)
+    {
+	push @{$agr{$1}}, $2;
+    }
+    elsif(/^\s*GOV\s+(\S+)\s+(\S+)\s*$/)
+    {
+	push @{$gov{$1}}, attr::parse($2);
+    }
+    elsif(/^\s*ROLE\s+\S+\s*$/)
+    {
+	$roles{$_}=1;
+	print;
+    }
+    elsif(/^\s*SGL\s+\S+\s*$/)
+    {
+	++$nsgl;
+	print;
+    }
+    elsif(/^\s*REQ\s+(\S+)\s+(\S+)\s*$/)
+    {
+	print "#$_";
+	my $cat = attr::parse $1;
+	for my $atomcat (keys %cats)
+	{
+	    if(attr::match @$cat, @{$cats{$atomcat}})
+	    {
+		print "REQ ".$atomcat." $2\n";
+		++$nreq;
+	    }
+	}
+    }
+    elsif(/^\s*LEFT\s+\S+\s*$/)
+    {
+	++$nleft;
+	print;
+    }
+    elsif(/^\s*RIGHT\s+\S+\s*$/)
+    {
+	++$nright;
+	print;
+    }
+    elsif(($hs,$ds,$r) = /^\s*LINK\s+($cats_re)\s+($cats_re)\s+(\S+)\s*$/)
+    {
+	print "#$_";
+	for $h ($hs =~ /$attr::cat_re/g)
+	{
+	    for $d ($ds =~ /$attr::cat_re/g)
+	    {
+		addlinks($h,$d,$r);
+	    }
+	}
+    }
+    
+    else
+    {
+	print;
+    }
+}
+
+
+sub addlinks
+{
+    ($h,$d,$r) = @_;
+
+    for my $a (@{$agr{$r}}) { print "#AGR $r $a\n"; }
+    for my $c (@{$gov{$r}}) { print "#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 "LINK ";
+		print $atomhead." ";
+		print $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;
+
+
+sub extractcats
+{
+    my $file = shift;
+    open DICFILE, "canonize $file |";
+    while(<DICFILE>)
+    {
+	while(/,([^[:space:];]+)/g)
+	{
+	    $cat=$1;
+	    next if !$cat || exists $cats{$cat};
+	    $ncat++;
+	    print "CAT $1\n";
+	    $cats{$cat}=attr::parse($cat);
+	}
+    }
+    close DICFILE;
+}
+
+
+sub loadcats
+{
+    my $file = shift;
+    open CATFILE, "canonize $file |";
+    while(<CATFILE>)
+    {
+	tr/ \t\n//d;
+	next if !$_ || exists $cats{$_};
+	print "CAT $_\n";
+	++$ncat;
+	$cats{$_}=attr::parse($_);
+    }
+    close CATFILE;
+}
Index: app/src/dgp/dgp0.cc
===================================================================
--- app/src/dgp/dgp0.cc	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
+++ app/src/dgp/dgp0.cc	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
@@ -0,0 +1,217 @@
+#include "dgp0.hh"
+#include "global.hh"
+
+extern Grammar grammar;
+extern MGraph mgraph;
+extern SGraph sgraph;
+
+SNode* snodes;
+
+extern bool debug;
+
+list<int> nodelist;
+list<int>::iterator processed;
+
+
+void set_initial_constraints(int node)
+{
+  snodes[node].prop.forbidden.reset();
+  snodes[node].prop.required=grammar.obl[snodes[node].mnode->cat];
+}
+
+
+bool changing_constraints(int head, Role role)
+{
+  return grammar.sgl[role] || snodes[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);
+}
+
+NodeProp compute_prop_left(NodeProp headprop, Role role)
+{
+  NodeProp ret=headprop;
+  if(grammar.sgl[role]) ret.forbidden.set(role);
+  ret.required.reset(role);
+  return ret;
+}
+
+NodeProp compute_prop_right(NodeProp headprop, Role role)
+{
+  NodeProp ret=headprop;
+
+  if(grammar.sgl[role]) ret.forbidden.set(role);
+  ret.required.reset(role);
+  return ret;
+}
+
+int get_node(MNode& mnode, NodeProp p, bitset<MAXNODES>& newheadLH, bitset<MAXNODES>& newheadLV)
+{
+  for(vector<int>::iterator ps=mnode.snodes.begin(); ps!=mnode.snodes.end(); ++ps)
+    if(snodes[*ps].prop==p && snodes[*ps].LH==newheadLH && snodes[*ps].LV==newheadLV)
+      return *ps;
+  return -1;
+}
+
+void connect_left(list<int>::iterator h, list<int>::iterator d, Role r)
+{
+  NodeProp &oldheadprop = snodes[*h].prop;
+  NodeProp newheadprop;
+  bitset<MAXNODES> newheadLV;
+  bitset<MAXNODES> newheadLH;
+  bitset<MAXNODES> newheadLD;
+  
+  newheadprop=compute_prop_left(oldheadprop,r);
+  
+  int newheadind;
+  if(oldheadprop==newheadprop)
+    newheadind = *h;
+  else
+  {
+    newheadLH = snodes[*h].LH;
+    newheadLV = snodes[*d].LV;
+    newheadLD = snodes[*h].LD;
+
+    newheadind = get_node(*(snodes[*h].mnode), newheadprop, newheadLH, newheadLV);
+    if( newheadind < 0 )
+    {
+      newheadind = sgraph.clone(*h,newheadprop);
+      list<int>::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;
+      
+      if(debug) sgraph.print_node_debug(stderr," C ",newheadind);
+    }
+    else
+      snodes[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);
+}
+
+
+void connect_right(list<int>::iterator h, list<int>::iterator d, Role r)
+{
+  NodeProp &oldheadprop = snodes[*h].prop;
+  NodeProp newheadprop;
+  bitset<MAXNODES> newheadLV;
+  bitset<MAXNODES> newheadLH;
+  bitset<MAXNODES> newheadLD;
+  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);
+    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<int>::iterator nextit=h; ++nextit;
+      nodelist.insert(nextit,newheadind);
+      
+      if(debug) sgraph.print_node_debug(stderr," C ",newheadind);
+    }
+    else
+      snodes[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);
+  
+}
+
+
+void try_connect_dependents(list<int>::iterator j)
+{
+  for(list<int>::iterator i(j); i!=nodelist.begin(); --i)
+    if(sgraph.visible(*i,*j) && sgraph.saturated(*i))
+    {
+      Roles& ji_roles = grammar.connect[snodes[*j].mnode->cat][snodes[*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))
+          connect_left(j,i,*r);
+    }
+}
+
+
+void try_connect_heads(list<int>::iterator j)
+{
+  for(list<int>::iterator i(j); i!=nodelist.begin(); --i)
+    if(sgraph.visible(*i,*j))
+    {
+      Roles& ij_roles = grammar.connect[snodes[*i].mnode->cat][snodes[*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))
+          connect_right(i,j,*r);
+    }
+}
+
+
+void reverse_links()
+{
+  list<int>::iterator i = nodelist.begin();
+  for(++i; i!=nodelist.end(); ++i)
+    {
+      for(vector<Arc>::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<Arc>::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));
+    }
+}
+
+
+void dgp0()
+{
+  snodes=sgraph.nodes;
+
+  nodelist.clear();
+  nodelist.push_back(0); // BOS
+  processed=nodelist.begin();
+
+  for(int m=0; m<mgraph.n ; ++m)
+  {
+    int basenode = sgraph.add_base_snode(mgraph.nodes+m); // ma zwracaæ SNode*
+    set_initial_constraints(basenode);
+    nodelist.push_back(basenode);
+
+    if(debug) {sgraph.print_node_debug(stderr,"B  ",basenode);} // STDOUT!!!
+
+    list<int>::iterator cursor=processed;
+    while(++cursor != nodelist.end())
+    {
+      try_connect_dependents(cursor);
+      try_connect_heads(cursor);
+      processed=cursor;
+    }
+  }
+  reverse_links();
+}
Index: app/src/dgp/dgp0.hh
===================================================================
--- app/src/dgp/dgp0.hh	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
+++ app/src/dgp/dgp0.hh	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
@@ -0,0 +1,12 @@
+#ifndef _DGP0_HH
+#define _DGP0_HH
+
+#include "grammar.hh"
+#include "sgraph.hh"
+#include "mgraph.hh"
+
+// API
+
+void dgp0();
+
+#endif
Index: app/src/dgp/global.cc
===================================================================
--- app/src/dgp/global.cc	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
+++ app/src/dgp/global.cc	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
@@ -0,0 +1,5 @@
+
+#include "global.hh"
+
+bool debug = false;
+
Index: app/src/dgp/global.hh
===================================================================
--- app/src/dgp/global.hh	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
+++ app/src/dgp/global.hh	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
@@ -0,0 +1,1 @@
+extern bool debug;
Index: app/src/dgp/go
===================================================================
--- app/src/dgp/go	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
+++ app/src/dgp/go	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
@@ -0,0 +1,7 @@
+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
Index: app/src/dgp/gph
===================================================================
--- app/src/dgp/gph	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
+++ app/src/dgp/gph	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
@@ -0,0 +1,93 @@
+#!/usr/bin/perl
+
+#package:	UAM Text Tools
+#component:	gph
+#version:	1.0
+#author:	Tomasz Obrebski
+
+use strict;
+use Getopt::Long;
+
+
+my @process;
+my $help=0;
+my $reset;
+my $interactive=1;
+
+GetOptions("process|p=s" => \@process,
+	   "help|h" => \$help,
+	   "reset|r=s" => \$reset,
+	   "interactive|i" => \$interactive);
+
+if($help)
+{
+    print <<'END'
+Usage: gph [OPTIONS]
+
+Options:
+   -p tag		Process segments with this tag as nodes.
+   -r tag		Start new graph at this tag.
+   -f filename		Input file (NIE DZIALA).
+   -o filename		Output file (NIE DZIALA).
+   -i			Toggle interactive mode (default=on).
+END
+;
+    exit 0;
+}
+
+
+$|=1 if $interactive;
+
+my @prev;
+my $gph;
+
+my $n=0;
+
+while(<>)
+{
+    chomp;
+    my $do=0;
+
+    my @line = split /\s+/;
+
+    if($line[2] eq $reset)
+    {
+	$n=0;
+	@prev = ();
+    }
+
+    for my $p (@process)
+    {
+	$do=1 if $line[2] eq $p;
+    }
+
+    if($do)
+    {
+	my @preds = ();
+	shift @prev while @prev+0 && $prev[0]->[1] + $prev[0]->[2] < $line[0];
+	for my $p (@prev)
+	{
+	    push(@preds, $p->[0]) if $p->[1] + $p->[2] == $line[0];
+	}
+	push @prev, [$n, $line[0], $line[1]];
+	
+	$gph=' gph:'.$n.':'.join(',',@preds);
+
+	$n++;
+    }
+    else
+    {
+	for my $p (@prev)
+	{
+	    if($p->[1]+$p->[2] == $line[0])
+	    {
+		$p->[2] += $line[1];
+	    }
+	}
+
+	$gph='';
+
+    }
+
+    print $_.$gph."\n";    
+}
Index: app/src/dgp/grammar.cc
===================================================================
--- app/src/dgp/grammar.cc	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
+++ app/src/dgp/grammar.cc	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
@@ -0,0 +1,163 @@
+
+#include <stdio.h>
+
+#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;
+}
+
+void Grammar::add_category(const char* s)
+{
+  Cat::add(s);
+  if(Cat::count()>cats_sz)
+  {
+    cats_sz += 16;
+    connect.resize(cats_sz);
+    for(int i=0; i<cats_sz; ++i)
+      connect[i].resize(cats_sz);
+    obl.resize(cats_sz);
+  }
+}
+
+void Grammar::add_type(const char* s)
+{  
+  Role::add(s);
+  if(Role::count()>types_sz)
+  {
+    types_sz += 16;
+    lt.resize(types_sz);
+    gt.resize(types_sz);
+  }
+}
+
+
+void Grammar::set_lt(Role s, Role t)
+{
+  lt[s].set(t);
+  gt[t].set(s);
+  if(s==0||(int)t==0)
+    return;
+  else
+  {
+    for(int i=0; i<Role::count(); ++i)
+      if(lt[i][s])
+	set_lt(i,t);
+    for(int i=0; i<Role::count(); ++i)
+      if(lt[t][i])
+	set_lt(s,i);
+  }
+}  
+
+
+void Grammar::compute_gt()
+{
+  for(Role s=0; s<Role::count(); ++s)
+    for(Role t=0; t<Role::count(); ++t)
+      if(lt[s][t])
+	gt[t].set(s);
+}
+
+
+bool Grammar::read(FILE* f)
+{
+  int lineno=0;
+  char line[MAXLINE]; // line has the structure: key [arg1 [arg2 [arg3]]]
+  char key[MAXLINE];
+  char arg1[MAXLINE];
+  char arg2[MAXLINE];
+  char arg3[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);
+    }
+    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);
+    }
+
+    else fprintf(stderr,"Invalid line %d. Ignored.\n", lineno);
+  }
+
+//   compute_gt();
+
+  return true;
+  
+}
+
+void Grammar::write(FILE* f)
+{
+  for(Cat i=1; i<Cat::count(); ++i)
+    fprintf(f,"CAT\t%s\n",i.str());
+
+  for(Role i=1; i<Role::count(); ++i)
+    fprintf(f,"ROLE\t%s\n",i.str());
+
+  for(Role i=1; i<Role::count(); ++i)
+    if(sgl.test(i)) fprintf(f,"SGL\t%s\n",i.str());
+  
+  for(Role i=1; i<Role::count(); ++i)
+    if(left.test(i)) fprintf(f,"LEFT\t%s\n",i.str());
+
+  for(Role i=1; i<Role::count(); ++i)
+    if(right.test(i)) fprintf(f,"RIGHT\t%s\n",i.str());
+
+  for(Cat c=1; c<Cat::count(); ++c)
+    for(Role r=1; r<Role::count(); ++r)
+      if(obl[c].test(r)) fprintf(f,"REQ\t%s\t%s\n",c.str(),r.str());
+  
+  for(Cat c=1; c<Cat::count(); ++c)
+    for(Cat d=1; d<Cat::count(); ++d)
+      for(Role t=1; t<Role::count(); ++t)
+	if(connect[c][d].count(t))
+          fprintf(f,"LINK\t%s\t%s\t%s\n",c.str(),d.str(),t.str());
+}
+
Index: app/src/dgp/grammar.hh
===================================================================
--- app/src/dgp/grammar.hh	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
+++ app/src/dgp/grammar.hh	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
@@ -0,0 +1,63 @@
+#ifndef _GRAMMAR_HH
+#define _GRAMMAR_HH
+
+#include <bitset>
+#include <vector>
+#include <list>
+#include <set>
+
+#include "const.hh"
+#include "thesymbols.hh"
+#include "sgraph.hh"
+
+class Grammar
+{
+
+ public:
+
+  //  enum CONSTR { SGL, OBL, LEFT, RIGHT, INIT, NONINIT, FIN, NONFIN };
+
+  Grammar() : types_sz(0), cats_sz(0) { } ;
+  
+  int types_sz;
+  int cats_sz;
+
+  vector< vector< Roles > >    connect;
+  RoleSet                      sgl;
+  vector< RoleSet >            obl;
+  RoleSet                      left;
+  RoleSet                      right;
+  vector< RoleSet >            lt;
+  vector< RoleSet >            gt;
+
+  bool read(FILE* f);
+  void write(FILE* f);
+
+  void add_category(const char* s);
+  void add_type(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 set_lt(Role r, Role s);
+  void compute_gt();
+
+
+  bool check_constr(NodeProp& hprop, NodeProp& dprop, int dir, Role role);
+
+};
+
+inline bool Grammar::check_constr(NodeProp& hprop, NodeProp& dprop, int dir, Role role)
+{
+  return 
+    !hprop.forbidden[role] &&
+    ( !right[role] || dir==1 ) &&
+    ( !left[role] || dir==0 )
+    ;
+}
+
+
+#endif
Index: app/src/dgp/main.cc
===================================================================
--- app/src/dgp/main.cc	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
+++ app/src/dgp/main.cc	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
@@ -0,0 +1,120 @@
+
+/**
+ * Package:	UAM Text Tools
+ * Component:	dgp (dg parser)
+ * Version:	1.0
+ * Author:	Tomasz Obrebski
+ */
+
+#include "cmdline.h"
+#include "global.hh"
+#include "mgraph.hh"
+#include "sgraph.hh"
+#include "grammar.hh"
+#include "dgp0.hh"
+#include "common.h"
+
+#define MAXSEGMENTS 500
+
+char segment[MAXSEGMENTS][MAXLINE];
+int segcount=0;
+char seg_mnode[MAXSEGMENTS];
+
+Grammar grammar;
+MGraph mgraph;
+SGraph sgraph;
+
+FILE* grammarf;
+FILE* debugf=stdout;
+unsigned int info=0U;
+
+void output();
+
+main(int argc, char* argv[])
+{
+  gengetopt_args_info args;
+
+  if(cmdline_parser(argc,argv,&args) != 0) exit(1);
+
+  if(args.help_given) cmdline_parser_print_help ();
+
+  if(args.input_given)
+    if(!(inputf=fopen(args.input_arg,"r")))
+      fprintf(stderr,"dgp: input file not found: %s.\n", args.input_arg), exit(1);
+
+  if(args.output_given)
+    if(!(outputf=fopen(args.output_arg,"w")))
+      fprintf(stderr,"dgp: cannot open output file: %s.\n", args.output_arg), exit(1);
+
+  if(!(grammarf=fopen(args.grammar_arg,"r")))
+    fprintf(stderr,"dgp: grammar file not found: %s.\n", args.grammar_arg), exit(1);
+
+  if(args.debug_given) debug=true;
+
+  for(char* c=args.info_arg; *c!='\0' ; ++c)
+    switch(*c)
+    {
+    case 'h': info|=SGraph::HEADS; break;
+    case 'd': info|=SGraph::DEPS; break;
+    case 's': info|=SGraph::SETS; break;
+    case 'c': info|=SGraph::CONSTRAINTS; break;
+    }
+
+  grammar.read(grammarf);
+  fclose(grammarf);
+
+  mgraph.clear();
+  sgraph.clear();
+
+  char line[1000];
+  while (fgets(line, MAXLINE+1, inputf))
+  {
+    line[strlen(line)-1] = '\0';
+    strcpy(segment[segcount],line);
+
+    char segtype[80];
+
+    seg_mnode[segcount] = processseg(line, args) ? mgraph.add_node(line) : -1;
+
+    segcount++;
+
+    getfield(line,"3",segtype);
+    if(strcmp(segtype,"EOS")==0)
+    {
+      dgp0(); // parametry!!! MGraph, SGraph, Grammar
+      output();
+      
+      mgraph.clear();
+      sgraph.clear();
+      segcount=0;
+    }
+    //    if(args.interactive_flag) { fflush(outputf); fflush(failedf); }
+  }
+  
+  fclose(inputf);
+  fclose(outputf);
+  cmdline_parser_free(&args);
+  exit(0);
+}
+
+void output()
+{
+  for(int si=0; si<segcount; ++si)
+  {
+    if(seg_mnode[si]>=0)
+    {
+      MNode& m=mgraph.nodes[seg_mnode[si]];
+      for(vector<int>::iterator s=m.snodes.begin(); s!=m.snodes.end(); ++s)
+      {
+        fputs(segment[si],outputf);
+        sgraph.print_node(outputf, *s, info);
+        fputc('\n',outputf);
+      }
+    }
+    else
+    {
+      fputs(segment[si],outputf);
+      fputc('\n',outputf);
+    }
+  }
+}
Index: app/src/dgp/mgraph.cc
===================================================================
--- app/src/dgp/mgraph.cc	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
+++ app/src/dgp/mgraph.cc	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
@@ -0,0 +1,52 @@
+
+#include "mgraph.hh"
+#include "thesymbols.hh"
+#include "const.hh"
+#include "common.h"
+
+#include <stdio.h>
+
+int MGraph::add_node(char* seg)
+{
+  nodes[n].clear();
+  
+  char field1[80], field3[80], descr[256], gph[256];
+  char* cat;
+  
+  getfield(seg,"1",field1);
+  nodes[n].pos=atoi(field1);
+
+  getfield(seg,"3",field3);
+  if(!getfield(seg,"lem",descr)) strcpy(descr,"?,?");
+
+  cat=descr;
+  while(*cat!=',' && *cat ) ++cat;
+  if(*cat) ++cat;
+  
+  Cat::add(cat);
+  nodes[n].cat=cat;
+  
+  nodes[n].pred.clear();
+  
+  char* tok;
+  int previd;
+  
+  if(!getfield(seg,"gph",gph))
+  {
+    fprintf(stderr,"No gph field. Aborting (sorry).\n");
+    exit(1);
+  }
+
+  char* ids=strtok(gph,":");
+  if(n!=atoi(ids)){fprintf(stderr,"Invalid node id in line ?. Program aborted.\n"); exit(1); }
+  
+  char *preds;
+  while(preds=strtok(NULL,","))
+  {
+    previd=atoi(preds);
+    nodes[n].pred.push_back(&nodes[previd]);
+  }
+
+  return n++;
+}
+
Index: app/src/dgp/mgraph.hh
===================================================================
--- app/src/dgp/mgraph.hh	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
+++ app/src/dgp/mgraph.hh	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
@@ -0,0 +1,34 @@
+#ifndef _MGRAPH_HH
+#define _MGRAPH_HH
+
+#include <vector>
+
+#include "const.hh"
+#include "thesymbols.hh"
+#include "common.h"
+
+class MNode
+{
+public:
+
+  char           type[MAXFORMLEN];
+  Cat            cat;
+  int            pos;
+  vector<MNode*> pred;
+  vector<int>    snodes;
+
+  void           clear() { snodes.clear(); };
+};
+
+class MGraph
+{
+ public:
+
+  MNode nodes[MAXNODES];
+  int   n;
+
+  void clear() { n=0; };
+  int add_node(char* seg);
+};
+
+#endif
Index: app/src/dgp/sgraph.cc
===================================================================
--- app/src/dgp/sgraph.cc	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
+++ app/src/dgp/sgraph.cc	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
@@ -0,0 +1,164 @@
+#include "global.hh"
+#include "sgraph.hh"
+#include "mgraph.hh"
+#include "grammar.hh"
+#include "const.hh"
+#include <stdio.h>
+
+
+int SGraph::add_base_snode(MNode* mn)
+{
+  int nodeind=n;
+  SNode &node=nodes[n];
+
+  node.clear();
+
+  node.mnode=mn;
+
+  for(vector<MNode*>::iterator pm=node.mnode->pred.begin(); pm!=node.mnode->pred.end(); ++pm)
+    for(vector<int>::iterator ps=(*pm)->snodes.begin(); ps!=(*pm)->snodes.end(); ++ps)
+      if(nodes[*ps].in_LH)
+      {
+        node.LV.set(*ps);
+        if(nodes[*ps].saturated()) node.LV |= nodes[*ps].LH;
+      }
+
+  mn->snodes.push_back(nodeind);
+  ++n;
+
+  node.in_LH=true;
+
+  return nodeind;
+}
+
+
+void SGraph::update_left(int headind, int depind)
+{
+  SNode &head=nodes[headind], &dep=nodes[depind];
+
+  if(dep.saturated()) head.LV |= dep.LV, head.LD |= dep.LD;
+}
+
+
+void SGraph::update_right(int headind, int depind)
+{
+  SNode &head=nodes[headind], &dep=nodes[depind];
+
+  dep.LH.set(headind);
+  if(head.saturated())
+    dep.LH |= head.LH;
+}
+
+
+int SGraph::clone(int ancind, NodeProp newprop)
+{
+  int newind = n++;
+  SNode &newnode=nodes[newind];
+  SNode &ancnode = nodes[ancind];
+
+  newnode.clear();
+  newnode.prop=newprop;
+  newnode.mnode=ancnode.mnode;
+  newnode.mnode->snodes.push_back(newind);
+  return newind;
+}
+
+
+//-------------------------------------------------------------------------
+//-------------------------------------------------------------------------
+
+
+int SGraph::print_node(FILE* f, int n, unsigned int info)
+{
+  char buf[1000];
+  sprint_node(buf,n,info);
+  fputs(buf,f);
+}
+
+int SGraph::sprint_node(char* buf, int nodeind, unsigned int info)
+{
+  char* buf0=buf;
+  char descr[256];
+  char nodeinfo[16];
+
+  SNode &node=nodes[nodeind];
+
+  buf+=sprintf(buf," dgp:%d",nodeind);
+  buf+=sprintf(buf, saturated(nodeind) ? ";s" : ";u");
+
+  bool cont=false;
+  if (info&HEADS)
+  {
+    buf+=sprintf(buf,";");
+    for(vector<Arc>::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);
+    }
+  }
+  
+  if (info&DEPS)
+  {
+    buf+=sprintf(buf,";");
+    for(vector<Arc>::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);
+    }
+  }
+  
+  if (info&SETS)
+  {
+    int ord=0;
+    buf+=sprintf(buf,";{");
+    for(vector<MNode*>::iterator pm=node.mnode->pred.begin(); pm!=node.mnode->pred.end(); ++pm)
+      for(vector<int>::iterator ps=(*pm)->snodes.begin(); ps!=(*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);
+    buf+=sprintf(buf,"};{");
+    ord=0;for(int j=0; j<=n; ++j) if(node.LH[j]) buf+=sprintf(buf, ord++ ? ",%d" : "%d", j);
+    buf+=sprintf(buf,"};{");
+    ord=0;for(int j=0; j<=n; ++j) if(node.LD[j]) buf+=sprintf(buf, ord++ ? ",%d" : "%d", j);
+    buf+=sprintf(buf,"}");
+  }
+
+  if (info&CONSTRAINTS)//  buf+=sprint_node_constraints(buf,n);
+  {
+    buf+=sprintf(buf,";");
+    for(Role i=1; i<=Role::count(); ++i)
+      if(node.prop.forbidden[i]) buf+=sprintf(buf,"!%s",i.str());
+    for(Role i=1; i<=Role::count(); ++i)
+      if(node.prop.required[i]) buf+=sprintf(buf,"&%s",i.str());
+  }
+  
+//   buf+=sprintf(buf,"\n");
+  
+  return buf-buf0;
+}
+
+
+int SGraph::sprint_node_debug(char* buf, char* pref, int n)
+{
+  char *buf0 = buf;
+  buf+=sprintf(buf,"#%s",pref);
+  buf+=sprint_node(buf,n,HEADS|DEPS|SETS|CONSTRAINTS);
+  buf+=sprintf(buf,"\n");
+  return buf-buf0;
+}
+
+int SGraph::print_node_debug(FILE* f, 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: app/src/dgp/sgraph.hh
===================================================================
--- app/src/dgp/sgraph.hh	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
+++ app/src/dgp/sgraph.hh	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
@@ -0,0 +1,108 @@
+#ifndef _SGRAPH_HH
+#define _SGRAPH_HH
+
+#include <stdio.h>
+
+#include <list>
+#include <vector>
+#include <bitset>
+
+#include "const.hh"
+#include "thesymbols.hh"
+
+
+class MNode;
+
+
+struct Arc
+{
+  int dst;
+  Role role;
+  int anc;
+ 
+  Arc(int d, Role r, int a) : dst(d), role(r), anc(a) {};
+ };
+
+
+struct NodeProp
+{
+  bitset<MAXTYPES> required;
+  bitset<MAXTYPES> forbidden;
+
+  bool operator==(const NodeProp& p)
+  { return required==p.required && forbidden==p.forbidden; }
+
+  void clear()
+  { required.reset(), forbidden.reset(); }
+
+};
+
+
+struct SNode
+{
+  
+  MNode* mnode;
+
+  NodeProp prop;
+
+  bitset<MAXNODES> LV;
+  bitset<MAXNODES> LH;
+  bitset<MAXNODES> LD;
+  bool in_LH;
+
+  vector<Arc> heads;
+  vector<Arc> deps;
+
+  void clear()      { prop.clear(), LV.reset(), LD.reset(), LH.reset(), heads.clear(), deps.clear(); }
+  bool saturated()  { return prop.required.none(); }
+};
+
+
+
+class SGraph
+{
+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);
+  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<int> nodelist, unsigned int info);
+
+  int sprint_node(char* buf, int n, unsigned int info);
+  int print_node(FILE* f, int n, unsigned int info);
+  int sprint_node_debug(char* buf, char* pref, int n);
+  int print_node_debug(FILE* f, char* pref, int n);
+
+  void print_arc(FILE* f, int left, int right, Role role, int dir); // 0 - left, 1 - right
+
+};
+
+
+inline bool SGraph::visible(int left, int right)
+{
+  return nodes[right].LV[left];
+}
+
+inline bool SGraph::saturated(int node)
+{
+  return nodes[node].saturated();
+}
+
+#endif
Index: app/src/dgp/symbol.cc
===================================================================
--- app/src/dgp/symbol.cc	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
+++ app/src/dgp/symbol.cc	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
@@ -0,0 +1,39 @@
+#include "symbol.hh"
+
+// CLASS symbols
+
+//int Symbols::_no_of_spaces=0;
+
+Symbols::~Symbols()
+{
+  while(!table.empty())
+  {
+    free((void*)table.back());
+    table.pop_back();
+  }
+}
+
+void Symbols::load(const char* filename)
+{
+  ifstream f(filename);
+  char s[100];
+  while(f)
+  {
+    f >> s >> ws;
+    if(strlen(s)) add(s);
+  }
+}  
+
+void Symbols::add(const char* sym)
+{
+  if(hash.count(sym)==0)
+  {
+    char* symdup=strdup(sym);
+    hash[symdup]=table.size();
+    table.push_back(symdup);
+  }
+}
+
+
+//template<int space>
+//Symbols Symbol<space>::defs;
Index: app/src/dgp/symbol.hh
===================================================================
--- app/src/dgp/symbol.hh	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
+++ app/src/dgp/symbol.hh	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
@@ -0,0 +1,142 @@
+#ifndef _SYMBOL_HH
+#define _SYMBOL_HH
+
+#include <ext/hash_map>
+//#include <ext/hash_fun.h>
+#include <string>
+#include <fstream>
+#include <vector>
+#include <iostream>
+
+using namespace std;
+
+using __gnu_cxx::hash_map;
+using __gnu_cxx::hash;
+
+
+// Key comparison for the cstr_hash hash table
+struct eqstr
+{ 
+  bool operator()(const char * s, const char* t) const 
+  { return strcmp(s,t)==0; }
+};
+
+
+// Hash table for storing symbols
+
+typedef hash_map<const char*,int,hash<const char*>,eqstr> cstr_hash;
+
+// Symbol table. Provides access to symbols through their index or name.
+
+class Symbols
+{
+ public:
+
+  Symbols() { add("NULL"); };
+  ~Symbols();
+  
+  void load(const char* filename);
+
+  int operator[](const char* s) { return hash[s]; };
+  
+  const char* operator[](int i) { return table[i]; };
+
+  void add(const char* c);
+
+  int count() { return table.size(); };
+
+ private:
+    
+  std::vector<const char*> table;
+  cstr_hash hash;
+
+};
+
+//////////////////////////////////////////////////////////////////////
+
+/// Symbol class template. 
+/** The template argument determines the symbol space.
+    Each space is created with symbol "NULL" with indexed 0 already in.
+*/
+
+template <int space>
+class Symbol
+{
+ public:
+
+  /// Load the contents of the symbol table from file.
+  static void define(const char *filename) 
+  { defs.load(filename); }
+  
+  /// Add symbol s.
+  /** The string is duplicated.
+   */
+  static Symbol<space> add(const char* s) { defs.add(s); }
+      
+  /// Number of symbols.
+  static int count() { return defs.count(); };
+
+  /// First symbol.
+  static int first() { return 1; }
+
+  /// Last symbol.
+  static int last() { return defs.count()+1; }
+
+  /// Last symbol.
+  static int index(const char* s) { return defs[s]; }
+
+  /// Just for tests.
+  static void print();
+
+  /// 0-argument constructor, default value is 0 ("NULL").
+  Symbol() : val(0) {};
+
+  /// Constructing a symbol from its index.
+  /** No check is performed.
+  */
+
+  Symbol(int v) : val(v) {};
+  
+  /// Constructing a symbol from its name (string to Symbol conversion).
+  /** If s is not a symbol name, the value of 0 ("NULL") is assigned.
+  */
+
+  Symbol(const char * s) : val(defs[s]) {};
+  
+  /// Symbol to char* conversion. If symbol is invalid, NULL is returned.
+  const char* str() const { return (val>=0 && val<count())?defs[val]:NULL; };
+
+  /// Symbol to int& conversion.
+  /** Provides a way to iterate through symbols, eg:
+   *  for(Symbol<0> s=1; s; s++ ) ...
+      s=0; while(++s) ...
+   */
+  (operator int)() const { return val; };
+
+  Symbol operator++() {val++; return *this;}
+
+  //  bool operator<(Symbol& s) { return val < s.val; }
+
+
+ private:
+  static Symbols defs;
+  int val;
+};
+
+template <int space>
+void Symbol<space>::print()
+{
+  for(Symbol i=0; i<count(); ++i)
+    cout << (int)i << ": " << (const char*)i << endl;
+}
+
+template<int space>
+Symbols Symbol<space>::defs;
+
+template<int space>
+bool operator<(const Symbol<space>& s, const Symbol<space>& t)
+{
+  return (int)s < (int)t;
+}
+
+#endif
Index: app/src/dgp/thesymbols.hh
===================================================================
--- app/src/dgp/thesymbols.hh	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
+++ app/src/dgp/thesymbols.hh	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
@@ -0,0 +1,27 @@
+#ifndef __THESYMBOLS__HH
+#define __THESYMBOLS__HH
+
+#include "symbol.hh"
+#include "const.hh"
+
+#include <list>
+#include <set>
+#include <bitset>
+
+typedef Symbol<1> Cat;
+
+typedef Symbol<2> Role;
+typedef list<Role> RoleList;
+typedef list<Role>::iterator RoleListIter;
+typedef bitset<MAXTYPES> RoleSet;
+typedef set<Role> Roles;
+typedef Roles::iterator RolesIter;
+
+typedef Symbol<3> Constr;
+typedef list<Constr> ConstrList;
+typedef list<Constr>::iterator ConstrListIter;
+
+typedef Symbol<4> Rel;
+typedef Symbol<5> Flag;
+
+#endif
Index: app/src/dgp/tre.rb
===================================================================
--- app/src/dgp/tre.rb	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
+++ app/src/dgp/tre.rb	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
@@ -0,0 +1,297 @@
+#!/usr/bin/ruby
+
+require 'getoptlong'
+
+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
+
+load 'Seg.rb'
+
+$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)
+
+    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)
Index: app/src/dgp/uttcommon.c
===================================================================
--- app/src/dgp/uttcommon.c	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
+++ app/src/dgp/uttcommon.c	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
@@ -0,0 +1,2 @@
+#include "uttcommon.h"
+
Index: app/src/dgp/uttcommon.h
===================================================================
--- app/src/dgp/uttcommon.h	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
+++ app/src/dgp/uttcommon.h	(revision 0214596e4d70b25df913a24f19d50cb0f1b4a69f)
@@ -0,0 +1,146 @@
+#ifndef __COMMON_H
+#define __COMMON_H
+
+#include <stdio.h>
+
+/**************************************************
+ * Stale dotyczace wejscia/wyjscia
+ */
+
+#define MAXLINE 1024
+
+#define EMPTYFORM '*'
+#define INFIELD_SEP ':'
+#define MAXAUX 16
+#define FIELD_SEP " \t\n"
+
+
+/***************************************************************/
+/* problems with casing                                        */
+/* sprawdzenie wielkosci liter                                 */
+/* warto¶æ zwracana:                                           */
+/* 0 - wszystkie ma³e litery, 1 - pierwsza wielka, reszta male */
+/* 2 - wszystkie wielkie, 3 - inne                             */
+/***************************************************************/
+inline int casing(char* s)
+{
+  int ret = isupper(*s) ? 1 : 0;
+  while(*++s != '\0')
+  {
+    if(isupper(*s))
+    {
+      if(ret==1) ret=2;
+      else if(ret==0) ret=3;
+    }
+    else
+    {
+      if(ret==2) ret=3;
+    }
+  }
+  return ret;
+}
+
+// 
+inline void tolowers(char* s, char* d)
+{
+  *d=tolower(*s);
+  while(*s != '\0') * ++d = tolower(* ++s);
+}
+
+
+// przepisuje s do d
+// nadajac wielko¶æ liter zgodnie z warto¶ci± casing
+// casing - warto¶æ zwracana przez casing()
+// je¶li casing==3 przepisuje bez zmian (za ma³o informacji)
+inline void restorecasing(char *s, char *d, int casing)
+{
+  switch(casing)
+  {
+  case 0:
+  case 3:
+    *d=*s;
+    while(*s != '\0') * ++d = * ++s;
+    break;
+  case 1:
+    *d=toupper(*s);
+    while(*s != '\0') * ++d = * ++s;
+    break;
+  case 2:
+    *d=toupper(*s);
+    while(*s != '\0') * ++d = toupper(* ++s);
+    break;
+  }
+}
+
+
+/**************************************************/
+/*
+parameters:
+  -seg  - segment
+  -name - field name
+  +val  - field contents
+return value:
+  1 if specified field exists, 0 otherwise
+*/
+
+inline int getfield(char* seg, const char* pref, char* val)
+{
+  char* p=seg;
+
+  while(isspace(*p)) ++p;
+  
+ pos:
+  if(isdigit(*p) or *p=='*') while(!isspace(*p)) ++p; 
+  else goto type;
+
+  while(isspace(*p)) ++p;
+  
+ len:
+  if(isdigit(*p) or *p=='*') while(!isspace(*p)) ++p; 
+  else goto type;
+
+  while(isspace(*p)) ++p;
+  
+ type:
+  while(isspace(*p)) ++p; while(!isspace(*p)) ++p;
+
+  while(isspace(*p)) ++p;
+
+ form:
+  while(isspace(*p)) ++p; while(!isspace(*p)) ++p;
+
+ annotation:
+  do p=strstr(p,pref); while(p!=NULL && *(p-1)!=' ' && *(p-1)!='\t');
+  
+  if(p==NULL) return 0;
+  else
+  {
+    p+=strlen(pref);
+    int len=strcspn(p,FIELD_SEP "\n\r\f\0");
+    strncpy(val,p,len);
+    val[len]='\0';
+    return 1;
+  }
+}
+
+
+/*
+parameters:
+  +seg - segment
+  -pref - prefix of the new field
+  -val  - contents of the new field
+return value:
+  1 - success, 0 - fail (limit on segment length exceeded)
+*/
+inline int addfield(char *seg, const char *pref, const char *val)
+     // zalozenie, ze seg konczy sie znakiem \n
+{
+  if(strlen(seg)+strlen(pref)+strlen(val) >= MAXLINE) return 0; // bezpieczniej, ale wolniej
+
+  int seglen=strlen(seg);
+  sprintf(seg+(seglen-1)," %s%s\n",pref,val);
+  return 1;
+}
+
+
+#endif