DeSR Dependency Parser

src/State.cpp

/*
**  DeSR
**  src/State.cpp
**  ----------------------------------------------------------------------
**  Copyright (c) 2008  Giuseppe Attardi (attardi@di.unipi.it).
**  ----------------------------------------------------------------------
**
**  This file is part of DeSR.
**
**  DeSR is free software; you can redistribute it and/or modify it
**  under the terms of the GNU General Public License, version 3,
**  as published by the Free Software Foundation.
**
**  DeSR is distributed in the hope that it will be useful,
**  but WITHOUT ANY WARRANTY; without even the implied warranty of
**  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
**  GNU General Public License for more details.
**
**  You should have received a copy of the GNU General Public License
**  along with this program.  If not, see <http://www.gnu.org/licenses/>.
**  ----------------------------------------------------------------------
*/

#include "State.h"
#include "Parser.h"
#include "conf_feature.h"

// standard

// IXE library
#include "text/WordSet.h"

using namespace std;
using namespace IXE;
using namespace Tanl::Text;
using namespace Tanl::Classifier;

namespace Parser {

// feature model
conf_feature    features("Features");

// used to split SVMs.
conf_feature    SplitFeature("SplitFeature");

conf<bool>      ClosestChildren("ClosestChildren", false);

conf<bool>      PrepChildEntityType("PrepChildEntityType", false);

conf<bool>      StackSize("StackSize", true);
conf<bool>      InputSize("InputSize", false);
conf<bool>      InPunct("InPunct", false);
conf<bool>      VerbCount("VerbCount", true);
conf<bool>      UseChildPunct("UseChildPunct", true);
conf<int>       PastActions("PastActions", 1);
conf<bool>      WordDistance("WordDistance", true);
conf<bool>      PunctCount("PunctCount", true);
conf<bool>      MorphoAgreement("MorphoAgreement", false);
conf<bool>      MorphoSplit("MorphoSplit", false);
conf<bool>      LexChildNonWord("LexChildNonWord", true);

conf<bool>      CompositeActions("CompositeActions", false);

// Feature combinations
conf<bool>      SecondOrder("SecondOrder", false);
conf<bool>      FeatPairs("FeatPairs", false);

conf<bool>      RightToLeft("RightToLeft", false);

conf<bool>      ShowActions("ShowActions", false);

WordSet actionTable;

// pattern for detecting punctuation:
RegExp::Pattern State::ispunct("^\\p{P}+$",
                               PCRE_UTF8 | PCRE_NO_UTF8_CHECK);
RegExp::Pattern State::nonWordAscii("^[^$0-9_-zA-Z]+$");

char const* mkAction(char const* a, string const& dep)
{
  if (CompositeActions) {
    char action[128];
    sprintf(action, "%s%s", a, dep.c_str());
    return *actionTable.insert(action).first;
  } else {
    return *actionTable.insert(a).first;
  }
}

char const* actionString(char const* a)
{
    return *actionTable.insert(a).first;
}

//======================================================================
// SentenceInfo

SentenceInfo::SentenceInfo(Sentence& sentence, GlobalInfo* info) :
  globalInfo(info)
{
  if (sentence.empty())
    return;
  if (RightToLeft)
    sentence.reverse();
  // count punctuations
  punctCount.push_back(State::ispunct.test(sentence[0]->token->form));
  for (unsigned i = 1; i < sentence.size(); ++i) {
    Token* token = sentence[i]->token;
    punctCount.push_back(punctCount[i-1] + State::ispunct.test(token->form));
  }
}

//======================================================================
// State

State::State(Sentence const& sent, GlobalInfo* info) :
  sentence(sent),
  rootNode(new TreeToken(0, "#NULL")),
  sentenceInfo(new SentenceInfo(sentence, info)),
  action(0),
  previous(0)
{
  // initialize input
  input.resize(sentence.size());
  std::copy(sentence.rbegin(), sentence.rend(), input.begin());
  // initialize stack
  stack.push_back(rootNode);
}

bool State::hasNext()
{
   return !input.empty();
}

inline State* State::Shift()
{
  TreeToken* next = input.back();
  stack.push_back(next);
  input.pop_back();
  action = "S";         // makes history
  return this;
}

inline State* State::Right(Action action)
{
  // pop top and add it as left child to next token
  if (stack.size() == 1)
    return 0;
  TreeToken* top = copy(stack.back());
  stack.pop_back();
  TreeToken* next = copy(input.back());
  input.back() = next;
  next->left.push_back(top);
  top->linkHead(next->id, 0);
  if (CompositeActions)
    top->linkLabel(action+1);
  this->action = actionString(action);  // get unique copy
  return this;
}

inline State* State::Left(Action action)
{
  // pop top, add to it next token as right child and replace next
  TreeToken* top = copy(stack.back());
  TreeToken* next = copy(input.back());
  top->right.push_back(next);
  if (CompositeActions) {
    if (stack.size() > 1) {
      stack.pop_back();
      input.back() = top;
    } else {
      // optimize, anticipating Shift
      input.pop_back();
    }
  } else {
    if (stack.size()) {
      stack.pop_back();
      input.back() = top;
    }
  }
  next->linkHead(top->id, 0);
  if (CompositeActions)
    next->linkLabel(action+1);
  this->action = actionString(action);  // get unique copy
  return this;
}

inline State* State::right(Action action)
{
  int n = action[1] - '0';
  // pop n-th top and add it as left child to next token
  if (stack.size() <= n) {      // stack n
    // Don't extract DummyRoot
    //cerr << "Improper action " << action << endl;
    return 0;
  }
  TreeToken* nthTop = copy(stack[stack.size() - n]);
  stack.erase(stack.end() - n);
  TreeToken* next = copy(input.back());
  next->left.push_back(nthTop);
  nthTop->linkHead(next->id, 0);
  if (CompositeActions) {
    nthTop->linkLabel(action+2);
    // move back
    input.push_back(stack.back());
    stack.pop_back();
  } // else move back is delayed after DepLeft, see below
  this->action = actionString(action);  // get unique copy
  return this;
}

inline State* State::left(char const* action)
{                       // l2, l3, l4
  int n = action[1] - '0';
  // add next token as right child to n-th top,
  // move n tokens from stack to input
  if (stack.size() <= n) {
    //cerr << "Improper action " << action << endl;
    return 0;
  }
  TreeToken* nthTop = copy(stack[stack.size() - n]);
  TreeToken* next = copy(input.back());
  nthTop->right.push_back(next);
  next->linkHead(nthTop->id, 0);
  if (CompositeActions)
    next->linkLabel(action+2);
  // move first token
  input.back() = stack.back();
  stack.pop_back();
  if (CompositeActions)
    if (n == stack.size())
      n--;                      // don't pop rootNode
  // move n-1 tokens back to input
  for (int i = 0; i < n-2; i++) {
    input.push_back(stack.back());
    stack.pop_back();
  }
  input.push_back(nthTop);
  stack.pop_back();
  this->action = actionString(action);  // get unique copy
  return this;
}

inline State* State::DepLink(Action action)
{
  TreeToken* next = input.back();
  switch (action[0]) {
  case 'R':
  case 'r':
    // add dependency link to the leftmost child of next
    next->left.back()->linkLabel(action+1);
    // if previous action was an r_i,
    // complete previous action by moving back one token to input
    if (this->action[0] == 'r') {
      input.push_back(stack.back());
      stack.pop_back();
    }
    this->action = actionString(action);        // get unique copy
    return this;

  case 'L':
  case 'l':
    // add dependency link to the rightmost child of next
    next->right.back()->linkLabel(action+1);
    // if stack is empty complete previous action by doing a Shift
    if (stack.empty()) {        // link to rootNode, restore it
      input.pop_back();
      stack.push_back(next);
    }
    this->action = actionString(action);        // get unique copy
    return this;
  }
  return this;
}

State* State::Extract()
{
  // move second stack token to Extracted and Shift
  if (stack.size() < 3 ||       // stack (2 + root)
      input.size() < 1) {       // impossible to extract
    cerr << "Improper action " << action << endl;
    return 0;
  }
  TreeToken* nthStack = stack[stack.size() - 2];
  extracted.push_back(nthStack);
  stack.erase(stack.end() - 2);
  // Shift
  TreeToken* next = input.back();
  stack.push_back(next);
  input.pop_back();
  action = "E";
  return this;
}

State* State::Insert()
{
  // move token from extracted to next
  if (extracted.empty()) {
    cerr << "Improper action " << action << endl;
    return 0;
  }
  input.push_back(extracted.back());
  extracted.pop_back();
  action = "I";
  return this;
}

State* State::transition(Action action)
{
# ifdef DEBUG_1
  showStatus();
  cerr << "Action: " << action << endl;
# endif
  switch (action[0]) {
  case 'S':
    if (input.empty())
      return this;              // extra dummy Shift at end of sequence
    return Shift();
  case 'R':
    if (stack.size() == 1) {    // stack root
      // Don't extract DummyRoot
      // Force a Shift
      return Shift();
    }
    return Right(action);
  case 'L':
    return Left(action);
  case 'r':                     // r2, r3, r4
    return right(action);
  case 'l':                     // l2, l3, l4
    return left(action);
  case 'D':                     // DepLink
    return DepLink(action);
  case 'E':
    return Extract();
  case 'I':
    return Insert();
  }
  return 0;
}

// action is supplied only during training
void State::predicates(Features& preds, Action action)
{
  preds.clear();
  // special case: it helps learning to do a Shift
  if (stack.empty()) {     // happens only after Left action to rootNode
    preds.push_back("(");
    if (CompositeActions)
      return;
  }
  // may be redundant
  if (input.empty()) {
    preds.push_back(")");
    return;
  }

  // Token features
  tokenFeatures(preds);

  // Extracted stack features
  char feature[256];
  if (extracted.size()) {
    Token* tok = extracted.back()->token;
    string const* lemma = tok->getLemma();
    if (lemma && !lemma->empty()) {
      sprintf(feature, "EL%s", lemma->c_str());
      preds.push_back(feature);
    } else {
      sprintf(feature, "EW%s", tok->form.c_str());
      preds.push_back(feature);
    }
    string const* pos = tok->getPos();
    if (pos && !pos->empty()) {
      sprintf(feature, "EP%s", pos->c_str());
      preds.push_back(feature);
    }
  }

  // Morpho agreement
  if (MorphoAgreement && stack.size() > 1) {
    Token* top = stack.back()->token;
    Token* next = input.back()->token;
    if (top->morpho.number && top->morpho.number == next->morpho.number)
      preds.push_back("=N");
    if (top->morpho.gender && top->morpho.gender == next->morpho.gender)
      preds.push_back("=G");
  }

  // Sentence context predicates
  if (StackSize && stack.size() > 2) // stack 1
    preds.push_back("((");
  if (InputSize && input.size() > 1)
    preds.push_back("))");
  if (VerbCount) {
    Language const* lang = sentence.language;
    int vc = 0;
    FOR_EACH (vector<TreeToken*>, stack, it) {
      if ((*it)->token->isVerb(lang))
        vc++;
    }
    if (vc) {
      sprintf(feature, "VC%d", vc);
      preds.push_back(feature);
    }
  }

  // Punctuation presence
  int id = input.back()->id;
  if (id > 1) {
    // Punctuation balance (odd/even count)
    if (InPunct && sentenceInfo->punctCount[id-2]%2)
      preds.push_back(".");
    // Punctuation presence
    if (PunctCount && sentenceInfo->punctCount[id-2]) {
      sprintf(feature, ".%d", sentenceInfo->punctCount[id-2]);
      preds.push_back(feature);
    }
  }
  if (UseChildPunct) {
    // notice if there is a punctuation among children of top
    // Useful to handle properly phrases like:
    // fabricante de " software "
    if (stack.size() > 1) {
      TreeToken* top = stack.back();
      FOR_EACH (vector<TreeToken*>, top->left, it) {
        if (ispunct.test((*it)->token->form)) {
          sprintf(feature, "1.<%s", (*it)->token->form.c_str());
          preds.push_back(feature);
          break;
        }
      }
      for (vector<TreeToken*>::reverse_iterator it = top->right.rbegin();
           it != top->right.rend(); it++) {
        if (ispunct.test((*it)->token->form)) {
          sprintf(feature, "1.>%s", (*it)->token->form.c_str());
          preds.push_back(feature);
          break;
        }
      }
    }
    if (input.size()) {
      TreeToken* next = input.back();
      // notice if there is a punctuation among children of next
      FOR_EACH (vector<TreeToken*>, next->left, it) {
        if (ispunct.test((*it)->token->form)) {
          sprintf(feature, ".<0%s", (*it)->token->form.c_str());
          preds.push_back(feature);
          break;
        }
      }
      for (vector<TreeToken*>::reverse_iterator it = next->right.rbegin();
           it != next->right.rend(); it++) {
        if (ispunct.test((*it)->token->form)) {
          sprintf(feature, ".>0%s", (*it)->token->form.c_str());
          preds.push_back(feature);
          break;
        }
      }
    }
  }
  // History features
  State const* s = this;
  for (int i = 0; i < PastActions && s; i++, s = s->previous) {
    if (s->action) {
      sprintf(feature, "A%d%s", i, s->action);
      preds.push_back(feature);
    }
  }
  // Focus word distance
  if (WordDistance && stack.size()) {
    int d = abs((int)input.back()->id - (int)stack.back()->id) - 1;
    sprintf(feature, "%d", min(d, 4));
    preds.push_back(feature);
  }

  // Global corpus features
  // add entity type (time/location) of children of prepositions
  if (PrepChildEntityType)
    prepChildEntities(preds);

  if (SecondOrder) {
    // add all pairs
    size_t predNo = preds.size();
    for (unsigned i = 0; i < predNo; i++) {
      for (unsigned j = i+1; j < predNo; j++) {
        // combine in alphabetical order
        string combo = (preds[i].compare(preds[j]) < 0) ?
          preds[i] + '#' + preds[j] : preds[j] + '#' + preds[i];
        preds.push_back(combo.c_str());
      }
    }
  }
  // Features for predicting DEPREL
  if (!CompositeActions) {
    // add pair with POS of tokens to be linked
    switch (action[0]) {
    case 'R':
    case 'r': {
      TreeToken* next = input.back();
      string const* npos = next->token->getPos();
      string const* nlpos = next->left.back()->token->getPos();
      if (npos && nlpos) {
        sprintf(feature, "d%s%s", nlpos->c_str(), npos->c_str());
        preds.push_back(feature);
      }
      break;
    }
    case 'L':
    case 'l': {
      TreeToken* next = input.back();
      string const* npos = next->token->getPos();
      string const* nrpos = next->right.back()->token->getPos();
      if (npos && nrpos) {
        sprintf(feature, "D%s%s", nrpos->c_str(), npos->c_str());
        preds.push_back(feature);
      }
      break;
    }
    }
  }
}

// positions on the stack are numbered -1, -2, ...
// positions on input are numbered 0, 1, 2, ...
void State::tokenFeatures(Features& preds)
{
  char feature[256];
  Token* next = input.back()->token;
  set<TreeToken*> lexChildNonWordTokens;

  FOR_EACH (FeatureSpecs, features.value, fit) {
    char const* attrName = fit->first;
    int attrIndex = next->attrIndex(attrName);
    char featId = 'A' + attrIndex;              // feature type identifier
    FOR_EACH (set<TokenPath*>, fit->second, tit) {
      // find token
      TokenPath const& tp = **tit;
      TreeToken* tok;
      if (tp.root < 0) {
        if (-tp.root > (int)stack.size() - 1) // -1 because of root node
          continue;
        tok = stack[stack.size() + tp.root]; // no -1 because numbered from -1
      } else {
        if (tp.root >= (int)input.size())
          continue;
        tok = input[input.size() - 1 - tp.root];
      }
      tok = tok->follow(tp, sentence);
      if (tok) {
        string const* item = tok->get(attrName);
        if (item && !item->empty()) {
          // skip empty attributes
          if (tp.root < 0)
            sprintf(feature, "%d%c%s%s", -tp.root, featId, tp.Code(), item->c_str());
          else
            sprintf(feature, "%c%d%s%s", featId, tp.root, tp.Code(), item->c_str());
          preds.push_back(feature);

          if (LexChildNonWord &&
              lexChildNonWordTokens.find(tok) == lexChildNonWordTokens.end()) {
            // notice if there are puctuation or non ASCII word characters in children
            lexChildNonWordTokens.insert(tok); // add to list to avoid repeating for same token on different features
            FOR_EACH (vector<TreeToken*>, tok->left, it) {
              if (nonWordAscii.test((*it)->token->form)) {
                //sprintf(feature, "1./%s", (*it)->token->form.c_str());
                sprintf(feature, ".%d/", tp.root);
                preds.push_back(feature);
                break;
              }
            }
            for (vector<TreeToken*>::reverse_iterator it = tok->right.rbegin();
                 it != tok->right.rend(); it++) {
              if (nonWordAscii.test((*it)->token->form)) {
                //sprintf(feature, "1.\\%s", (*it)->token->form.c_str());
                sprintf(feature, ".%d\\", tp.root);
                preds.push_back(feature);
                break;
              }
            }
          }
        }
      }
    }
  }

  // compute the split feature, for use in choosing among multiple SVMs.
  FeatureSpecs splits = SplitFeature.value;
  FeatureSpecs::const_iterator split = splits.begin();
  if (split != splits.end()) {
    char const* attrName = split->first;
    FOR_EACH (set<TokenPath*>, split->second, tit) {
      // find token
      TokenPath const& tp = **tit;
      TreeToken* tok;
      if (tp.root < 0) {
        if (-tp.root > (int)stack.size() - 1) // -1 because of root node
          continue;
        tok = stack[stack.size() + tp.root]; // no -1 because numbered from -1
      } else {
        if (tp.root >= (int)input.size())
          continue;
        tok = input[input.size() - 1 - tp.root];
      }
      tok = tok->follow(tp, sentence);
      if (tok) {
        string const* feat = tok->get(attrName);
        if (feat)
          splitFeature = *feat; // do not trim feat->substr(0, 2);
        else                    // FIXME: throw Error
          cerr << "Missing split feature" << endl;
      }
    }
  }
}

void State::prepChildEntities(Features& preds)
{
  // FIXME: should deal also with non-projective actions (r2, l2 etc.)
  Language const* lang = sentence.language;
  GlobalInfo* info = sentenceInfo->globalInfo;
  if (stack.size() > 1) {
    TreeToken* top = stack.back();
    if (top->token->isPreposition(lang)) {
      // find noun child
      // FIXME: right is right also for right-to-left languages?
      FOR_EACH (vector<TreeToken*>, top->right, it) {
        if ((*it)->token->isNoun(lang)) {
          string const* noun = (*it)->token->getLemma();
          if (noun && !noun->empty()) {
            int tc = info->timeLemmas.count(*noun);
            int lc = info->locLemmas.count(*noun);
            // 'tarda' appears in both categories
            if (tc >= info->freqRatio * lc)
              preds.push_back("1TIME");
            if (lc >= info->freqRatio * tc)
              preds.push_back("1LOC");
            if (tc || lc)
              break;
          }
        }
      }
    }
  }
  // same with next
  TreeToken* next = input.back();
  if (next->token->isPreposition(lang)) {
    // find noun child
    // FIXME: right is right also for right-to-left languages?
    FOR_EACH (vector<TreeToken*>, next->right, it) {
      if ((*it)->token->isNoun(lang)) {
        string const* noun = (*it)->token->getLemma();
        if (noun && !noun->empty()) {
          int tc = info->timeLemmas.count(*noun);
          int lc = info->locLemmas.count(*noun);
          // 'tarda' appears in both categories
          if (tc >= info->freqRatio * lc)
            preds.push_back("TIME0");
          if (lc >= info->freqRatio * tc)
            preds.push_back("LOC0");
          if (tc || lc)
            break;
        }
      }
    }
  }
}

void State::showStatus() {
  cerr << "Stack:" << endl;
  FOR_EACH (vector<TreeToken*>, stack, it)
    (*it)->print(cerr);
  cerr << "Next:" << endl;
  if (input.size())
    input.back()->print(cerr);
}

// ======================================================================
// TrainState

TrainState::TrainState(Sentence const& sent, GlobalInfo* info) :
  State(sent, info),
  annotated(sentence)
{
  // count dependents for each node (used to determine when arc can be created)
  dependents.resize(sentence.size());
  FOR_EACH (Sentence, sentence, sit) {
    int head = (*sit)->linkHead();
    if (head)
      dependents[head-1]++;
  }
  // clear all dependencies.
  // Even during training, we should only see dependencies
  // that have been created during parsing.
  FOR_EACH (vector<TreeToken*>, input, sit) {
    (*sit)->linkHead(0);
    (*sit)->linkLabel("");
  }
  // add global info from sentence
  if (PrepChildEntityType)
    info->extract(sentence);
}

#define ORIG(tok) annotated[(tok)->id-1]

Action TrainState::nextAction()
{
  if (input.size() == 0)
    return 0;
  TreeToken* next = input.back();
  int nextHead = annotated[next->id-1]->linkHead();
  string const& nextLabel = annotated[next->id-1]->linkLabel();
  if (stack.empty())    // Shouldn't happen.
    return "S";
  TreeToken* top = stack.back();
  if (top->id && ORIG(top)->linkHead() == next->id) {
    // right arc: top -> next
    if (input.size() > 1 &&
        ORIG(input[input.size()-2])->linkHead() == top->id) {
      // non projective link: next2 -> top
      // Shift, followed by 'l2'
      return "S";
    } else if (top->id &&
               dependents[top->id-1]) {
      // top has still unresolved dependents
      return "S";
    } else {
      // action 'R'
      dependents[next->id - 1]--;
      return mkAction("R", ORIG(top)->linkLabel());
    }
  } else if (nextHead == top->id) {
    // left arc: next -> top
    if (stack.size() > 2 &&     // stack 1
        ORIG(stack[stack.size()-2])->linkHead() == next->id) {
      // non projective link: top2 -> next
      TreeToken* dep = stack[stack.size()-2];
      if (dependents[dep->id-1]) {
        return "E";
      } else {
        // action 'r2'
        dependents[next->id - 1]--;
        return mkAction("r2", ORIG(dep)->linkLabel());
      }
    } else if (stack.size() > 3 && // stack 2
               ORIG(stack[stack.size()-3])->linkHead() == next->id &&
               dependents[stack[stack.size()-3]->id - 1] == 0) {
      // right arc: top3 -> next
      // action 'r3'
      dependents[next->id - 1]--;
      TreeToken* dep = stack[stack.size()-3];
      return mkAction("r3", ORIG(dep)->linkLabel());
    } else if (dependents[next->id - 1]) {
      // next has unresolved dependencies
      return "S";
    } else {
      // action 'L'
      // pop top and replace next
      if (stack.size() > 1) {   // except on rootNode
        dependents[top->id - 1]--;
      }
      return mkAction("L", nextLabel);
    }
  } else if (stack.size() > 1 &&
             stack[stack.size()-2]->id == nextHead &&
             dependents[next->id - 1] == 0) {
    // left arc: next -> top2
    // action 'l2'
    // move up to 2 tokens from stack to input, i.e. go back
    TreeToken* nthTop = stack[stack.size()-2];
    // move top token
    if (stack.size() == 2) {
      // Special case: non-projective link to root.
      // This may happens when there are multiple roots, sometimes
      // because of annotations errors like in line 25640 of
      // danish_ddt_train.conll.
      // Don't pop rootNode, so do nothing.
    } else {
      dependents[nthTop->id - 1]--;
      // move second token
    }
    return mkAction("l2", nextLabel);
  } else if (stack.size() > 2 &&
             stack[stack.size()-3]->id == nextHead &&
             dependents[next->id - 1] == 0) {
    // left arc: next -> top3
    // action 'l3'
    if (stack.size() > 3)
      dependents[stack[stack.size()-3]->id - 1]--;
    return mkAction("l3", nextLabel);
  } else if (stack.size() > 3 && // stack 3
             stack[stack.size()-4]->id == nextHead &&
             dependents[next->id - 1] == 0) {
    // left arc: next -> top4
    // action 'l4'
    if (stack.size() > 4)
      dependents[stack[stack.size()-4]->id - 1]--;
    return mkAction("l4", nextLabel);
  } else if (stack.size() > 2 && // stack 1
             ORIG(stack[stack.size()-2])->linkHead() == next->id &&
             dependents[stack[stack.size()-2]->id - 1] == 0) {
    // right arc: top2 -> next
    // action 'r2'
    dependents[next->id - 1]--;
    TreeToken* dep = stack[stack.size()-2];
    return mkAction("r2", ORIG(dep)->linkLabel());
  } else if (stack.size() > 3 && // stack 2
             ORIG(stack[stack.size()-3])->linkHead() == next->id &&
             dependents[stack[stack.size()-3]->id - 1] == 0) {
    // right arc: top3 -> next
    // action 'r3'
    dependents[next->id - 1]--;
    TreeToken* dep = stack[stack.size()-3];
    return mkAction("r3", ORIG(dep)->linkLabel());
  } else if (extracted.size() &&
             nextHead == extracted.back()->id) {
    // bring back last extracted
    // action 'I'
    return "I";
  } else
    return "S";
}

Event* TrainState::next()
{
  Action action = nextAction();
  Event* ev = new Event(action);
  predicates(ev->features, action);
  return ev;
}

// ======================================================================
// ParseState

bool ParseState::hasNext()
{
  bool res = State::hasNext();
  if (!res) {
    // sometimes there are more than one root nodes
    if (stack.size() > 2) {
      // connect nodes to root
#     ifdef DEBUG
      cerr << "Multiple roots: " << stack.size() << endl;
#     endif
      Language const* lang = sentence.language;
      // find root
      int root = 0;
      int rootSize = 0;         // size of subtree
      FOR_EACH (vector<TreeToken*>, stack, sit) {
        TreeToken* node = *sit;
        if (node->linkHead() == 0) {
          int size = node->size();
          // FIXME: use better heuristics
          string const* tokPos = node->token->getPos();
          if (size > rootSize && tokPos && lang->rootPos(*tokPos)) {
            root = node->id;
            rootSize = size;
          }
        }
      }
      TO_EACH (vector<TreeToken*>, stack, sit) {
        TreeToken* node = *sit;
        if (node->linkHead() == 0 && node->id != root) {
          node->linkHead(root);
          if (node->linkLabel().empty())
            node->linkLabel(Language::DEFAULT_ROOT_LABEL);
        }
      }
    }
  }
  return res;
}

Context* ParseState::next()
{
  Features preds;
  predicates(preds);            // get contextual features
  // convert them to PIDs
  context.clear();
  FOR_EACH (Features, preds, it) {
    string const& pred = *it;
    if (predIndex.find(pred.c_str()) != predIndex.end())
      context.add(predIndex[pred.c_str()]);
  }
  return &context;
}

ParseState* ParseState::transition(Action action)
{
  // don't allow extracted token to survive beyond punctuation
  if (extracted.size() && input.size() &&
      (action[0] == 'S' || action[0] == 'L') &&
      ispunct.test(input.back()->token->form))
    action = "I";

  return (ParseState*)(new ParseState(*this))->State::transition(action);
}

} // namespace Parser

 

Copyright © 2005-2007 G. Attardi. Generated on 13 Aug 2009 by doxygen 1.5.7.1.