dyngenpar.h

Go to the documentation of this file.

/* DynGenPar: Dynamic Generalized Parser
   Copyright (C) 2010-2012 Kevin Kofler <kevin.kofler@chello.at>

   Support by the Austrian Science Fund FWF under contract numbers
   P20631 and P23554 is gratefully acknowledged.

   This program is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation, either version 2 of the License, or
   (at your option) any later version.

   This program 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/>. */

// Don't use pragma once here, Qt Jambi doesn't support it.
#ifndef DYNGENPAR_H
#define DYNGENPAR_H

#include <QString>
#include <QList>
#include <QStringList>
#include <QHash>
#include <QMultiHash>
#include <QSet>
#include <QPair>
#include <QQueue>
#include <QSharedData>
#include <QVariant>
#include <QVector>

// Tell GCC that qFatal does not return.
#if defined(__GNUC__) && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ > 4))
#define qFatal(x...) (qFatal(x), __builtin_unreachable())
#endif

namespace DynGenPar {

// --- general data structures (both context-free grammars and PMCFGs) ---

#ifdef DYNGENPAR_INTEGER_CATEGORIES
typedef int Cat;
#define IS_EPSILON(cat) (!(cat))
typedef int CatArg;
#else


typedef QString Cat;
#define IS_EPSILON(cat) ((cat).isNull())


typedef const Cat &CatArg;
#endif

template<class MultiHashType>
  QHash<typename MultiHashType::key_type,
        QList<typename MultiHashType::mapped_type> >
  multiHashToListHash(const MultiHashType &multiHash)
{
  QHash<typename MultiHashType::key_type,
        QList<typename MultiHashType::mapped_type> > result;
  QHashIterator<typename MultiHashType::key_type,
                typename MultiHashType::mapped_type> it(multiHash);
  while (it.hasNext()) {
    it.next();
    result[it.key()].append(it.value());
  }
  return result;
}

struct NextTokenConstraints {

  QList<Cat> expect;

  QList<Cat> taboo;
  bool operator==(const NextTokenConstraints &other) const {
    return expect == other.expect && taboo == other.taboo;
  }
};
uint qHash(const NextTokenConstraints &nextTokenConstraints);

class Action;
class Rule : public QList<Cat> {
  public:
    Rule() : QList<Cat>(), action(0) {}
    explicit Rule(const QVariant &label)
      : QList<Cat>(), action(0), lbl(label) {}
    explicit Rule(const QList<Cat> &list)
      : QList<Cat>(list), action(0), lbl() {}
    Rule(const QList<Cat> &list, const QVariant &label)
      : QList<Cat>(list), action(0), lbl(label) {}
    QVariant label() const {return lbl;}
    void setLabel(const QVariant &label) {lbl = label;}
    NextTokenConstraints nextTokenConstraints;
    Action *action;
    Rule &operator+=(const QList<Cat> &other) {
      QList<Cat>::operator+=(other);
      return *this;
    }
    Rule &operator+=(const Cat &value) { // QList always wants a const &
      QList<Cat>::operator+=(value);
      return *this;
    }
    Rule &operator<<(const QList<Cat> &other) {
      QList<Cat>::operator<<(other);
      return *this;
    }
    Rule &operator<<(const Cat &value) { // QList always wants a const &
      QList<Cat>::operator<<(value);
      return *this;
    }
    void add(const Cat &value) { // QList always wants a const &
      append(value);
    }
    QList<Cat> &toList() { return (QList<Cat> &) *this; }

  private:
    QVariant lbl;
};

typedef QHash<Cat, QList<Rule> > RuleSet;
typedef QSet<Cat> TokenSet;


struct Cfg {
  Cfg() : rules(), tokens(), startCat() {}
  Cfg(const RuleSet &r, const TokenSet &t, CatArg sc)
    : rules(r), tokens(t), startCat(sc) {}
  RuleSet rules;
  TokenSet tokens;
  Cat startCat;
  bool isToken(CatArg cat) const {return tokens.contains(cat);}
  void addToken(CatArg cat) {tokens.insert(cat);}
};

typedef QSet<Cat> Predictions;

struct MultiPrediction {
  MultiPrediction() : fullLiteral(), cat() {}
  MultiPrediction(const QList<Cat> &fullLit, CatArg c)
    : fullLiteral(fullLit), cat(c) {}
  QList<Cat> fullLiteral; 
  Cat cat; 

  bool operator==(const MultiPrediction &other) const {
    return fullLiteral == other.fullLiteral && cat == other.cat;
  }
};
typedef QMultiHash<QList<Cat>, MultiPrediction> MultiPredictions;
typedef QMultiHash<Cat, NextTokenConstraints> ConstrainedPredictions;

struct ConstrainedMultiPrediction {
  ConstrainedMultiPrediction()
    : fullLiteral(), cat(), nextTokenConstraints() {}
  ConstrainedMultiPrediction(const QList<Cat> &fullLit, CatArg c)
    : fullLiteral(fullLit), cat(c), nextTokenConstraints() {}
  ConstrainedMultiPrediction(const QList<Cat> &fullLit, CatArg c,
                             NextTokenConstraints ntc)
    : fullLiteral(fullLit), cat(c), nextTokenConstraints(ntc) {}
  QList<Cat> fullLiteral; 
  Cat cat; 
  NextTokenConstraints nextTokenConstraints; 

  bool operator==(const ConstrainedMultiPrediction &other) const {
    return fullLiteral == other.fullLiteral && cat == other.cat
           && nextTokenConstraints == other.nextTokenConstraints;
  }
};
typedef QMultiHash<QList<Cat>, ConstrainedMultiPrediction>
  ConstrainedMultiPredictions;

struct FullRule {
  FullRule() : cat(), rule(), epsilonsSkipped(0), ruleno(0) {}
  FullRule(CatArg c, const Rule &r, int epsSkipped, int n)
    : cat(c), rule(r), epsilonsSkipped(epsSkipped), ruleno(n) {}
  Cat cat;
  Rule rule;
  int epsilonsSkipped;

  int ruleno;
};

struct Node;
class Alternative : public QList<Node> {
  public:
    Alternative() : QList<DynGenPar::Node>() {}
    explicit Alternative(const QVariant &label)
      : QList<DynGenPar::Node>(), lbl(label) {}
    explicit Alternative(const QList<DynGenPar::Node> &list)
      : QList<DynGenPar::Node>(list), lbl() {}
    Alternative(const QList<DynGenPar::Node> &list, const QVariant &label)
      : QList<DynGenPar::Node>(list), lbl(label) {}
    QVariant label() const {return lbl;}
    void setLabel(const QVariant &label) {lbl = label;}
    Alternative &operator+=(const QList<DynGenPar::Node> &other) {
      QList<DynGenPar::Node>::operator+=(other);
      return *this;
    }
    Alternative &operator+=(const DynGenPar::Node &value) {
      QList<DynGenPar::Node>::operator+=(value);
      return *this;
    }
    Alternative &operator<<(const QList<DynGenPar::Node> &other) {
      QList<DynGenPar::Node>::operator<<(other);
      return *this;
    }
    Alternative &operator<<(const DynGenPar::Node &value) {
      QList<DynGenPar::Node>::operator<<(value);
      return *this;
    }
    void add(const DynGenPar::Node &value) {
      append(value);
    }
    QList<DynGenPar::Node> &toList() {
      return (QList<DynGenPar::Node> &) *this;
    }

  private:
    QVariant lbl;
};

struct Node {
  Node() {} 
  Node(CatArg c) : cat(c) {children.append(Alternative());}
  Node(CatArg c, const QVariant &d) : cat(c), data(d) {
    children.append(Alternative());
  }
  Cat cat;
  QVariant data;
  QList<Alternative> children;
  bool operator==(const Node &other) const {
    return cat == other.cat && data == other.data && children == other.children;
  }
};

class PseudoCatScope;
class PseudoCatScopeData : public QSharedData {
  public:

    QHash<Cat, QPair<QPair<Node, NextTokenConstraints>, int> > pConstraints;

    QHash<Cat, QPair<int, PseudoCatScope> > mcfgConstraints;
};
class PseudoCatScope {
  public:
    PseudoCatScope() : d() {}
    QHash<Cat, QPair<QPair<Node, NextTokenConstraints>, int> > &pConstraints() {
      ensureNonNull();
      return d->pConstraints;
    };
    QHash<Cat, QPair<int, PseudoCatScope> > &mcfgConstraints() {
      ensureNonNull();
      return d->mcfgConstraints;
    };
    bool hasPConstraint(CatArg cat) const {
      return d ? d->pConstraints.contains(cat) : false;
    };
    bool hasMcfgConstraint(CatArg cat) const {
      return d ? d->mcfgConstraints.contains(cat) : false;
    };
    QPair<QPair<Node, NextTokenConstraints>, int> pConstraint(CatArg cat) const
    {
      return d ? d->pConstraints.value(cat)
               : QPair<QPair<Node, NextTokenConstraints>, int>();
    };
    QPair<int, PseudoCatScope> mcfgConstraint(CatArg cat) const {
      return d ? d->mcfgConstraints.value(cat) : QPair<int, PseudoCatScope>();
    };
    bool isNull() const { return !d.constData(); }
    const PseudoCatScopeData *data() const { return d.constData(); }
    bool operator==(const PseudoCatScope &other) const { return d == other.d; }
  private:
    QSharedDataPointer<PseudoCatScopeData> d;
    void ensureNonNull() {
      if (!d.constData()) d = new PseudoCatScopeData;
    }
};
inline uint qHash(const PseudoCatScope &scope) {
  return qHash(scope.data());
}

struct Match {
  Match() : len(0), tree(), ruleno(0), scope(), nextTokenConstraints() {}
  Match(int l, Node t, int n, PseudoCatScope s)
    : len(l), tree(t), ruleno(n), scope(s), nextTokenConstraints() {}
  Match(int l, Node t, int n, PseudoCatScope s, const NextTokenConstraints &nt)
    : len(l), tree(t), ruleno(n), scope(s), nextTokenConstraints(nt) {}
  int len;
  Node tree;
  int ruleno; 

  PseudoCatScope scope;
  NextTokenConstraints nextTokenConstraints;
};

struct ActionInfo {
  ActionInfo() : tree() {}
  ActionInfo(const Node &t) : tree(t) {}
  Node tree;
};

class Action {
  public:
    virtual ~Action() {}
    virtual void execute(const ActionInfo &info) = 0;
};


// --- data structures for DAG-structured parse stacks ---

class StackItem;
class StackItemData : public QSharedData {
  public:
    virtual ~StackItemData() {}
    virtual StackItemData *clone() = 0;
    virtual int type() const = 0;
    virtual void addParent(const StackItem &parent) = 0;
    virtual void setParents(const QList<StackItem> &parents) = 0;
};

class UnifiedStackItemData : public StackItemData {
  public:
    UnifiedStackItemData() : usageCount(0) {}
    virtual ~UnifiedStackItemData() {}
    unsigned refUsage() const {return usageCount++;}
    unsigned derefUsage() const {return --usageCount;}
  private:
    mutable unsigned usageCount;
};

class StackItem {
  public:
    StackItem() : d() {} 
    StackItem(const QList<StackItem> &parents, CatArg cat, CatArg effCat,
              int pos, const PseudoCatScope &scope); 
    StackItem(const QList<StackItem> &parents, CatArg cat, CatArg effCat,
              const PseudoCatScope &scope); 
    StackItem(const StackItem &parent, int dummy); 
    StackItem(const StackItem &parent, const Rule &rule, int len, int curr,
              int i, const Node &tree, const PseudoCatScope &scope, int ruleno,
              const NextTokenConstraints &nextTokenConstraints); 
    StackItem(const StackItem &parent, CatArg target, int pos, int len);
    StackItem(const StackItem &parent, CatArg cat,
              const PseudoCatScope &scope); 
    StackItem(const StackItem &parent, const QList<Node> &leaves, int i,
              const Node &tree, const PseudoCatScope &scope,
              const NextTokenConstraints &nextTokenConstraints); 
    int type() const {return d ? d->type() : -1;}
    void addParent(const StackItem &parent) {d->addParent(parent);}
    void setParents(const QList<StackItem> &parents) {d->setParents(parents);}
    const StackItemData *data() const {return d.constData();}
  private:
    QSharedDataPointer<StackItemData> d;
};

class StackItemType0 : public StackItemData {
  public:
    StackItemType0(const QList<StackItem> &parents, CatArg cat, CatArg effCat,
                   int pos, const PseudoCatScope &scope)
      : m_parents(parents), m_cat(cat), m_effCat(effCat), m_pos(pos),
        m_scope(scope) {}
    virtual ~StackItemType0() {}
    virtual StackItemData *clone() {return new StackItemType0(*this);}
    virtual int type() const {return 0;}
    virtual void addParent(const StackItem &parent) {m_parents.append(parent);}
    virtual void setParents(const QList<StackItem> &parents) {
      m_parents = parents;
    }
    const QList<StackItem> &parents() const {return m_parents;}
    Cat cat() const {return m_cat;}
    Cat effCat() const {return m_effCat;}
    int pos() const {return m_pos;}
    PseudoCatScope scope() const {return m_scope;}
  private:
    QList<StackItem> m_parents;
    Cat m_cat, m_effCat;
    int m_pos;
    PseudoCatScope m_scope;
};

class StackItemType1 : public StackItemData {
  public:
    StackItemType1(const QList<StackItem> &parents, CatArg cat, CatArg effCat,
                   const PseudoCatScope &scope) :
      m_parents(parents), m_cat(cat), m_effCat(effCat), m_scope(scope) {}
    virtual ~StackItemType1() {}
    virtual StackItemData *clone() {return new StackItemType1(*this);}
    virtual int type() const {return 1;}
    virtual void addParent(const StackItem &parent) {m_parents.append(parent);}
    virtual void setParents(const QList<StackItem> &parents) {
      m_parents = parents;
    }
    const QList<StackItem> &parents() const {return m_parents;}
    Cat cat() const {return m_cat;}
    Cat effCat() const {return m_effCat;}
    PseudoCatScope scope() const {return m_scope;}
  private:
    QList<StackItem> m_parents;
    Cat m_cat, m_effCat;
    PseudoCatScope m_scope;
};


class StackItemType2 : public UnifiedStackItemData {
  public:
    StackItemType2(const StackItem &parent) : m_parent(parent) {}
    virtual ~StackItemType2() {}
    virtual StackItemData *clone() {return new StackItemType2(*this);}
    virtual int type() const {return 2;}
    virtual void addParent(const StackItem &) {
      qFatal("cannot call addParent on type 2 item");
    }
    virtual void setParents(const QList<StackItem> &) {
      qFatal("cannot call setParents on type 2 item");
    }
    const StackItem &parent() const {return m_parent;}
  private:
    StackItem m_parent;
};

class StackItemType3 : public StackItemData {
  public:
    StackItemType3(const StackItem &parent, const Rule &rule, int len, int curr,
                   int i, const Node &tree, const PseudoCatScope &scope,
                   int ruleno, const NextTokenConstraints &nextTokenConstraints)
      : m_parent(parent), m_rule(rule), m_len(len), m_curr(curr), m_i(i),
        m_tree(tree), m_scope(scope), m_ruleno(ruleno),
        m_nextTokenConstraints(nextTokenConstraints) {}
    virtual ~StackItemType3() {}
    virtual StackItemData *clone() {return new StackItemType3(*this);}
    virtual int type() const {return 3;}
    virtual void addParent(const StackItem &) {
      qFatal("cannot call addParent on type 3 item");
    }
    virtual void setParents(const QList<StackItem> &) {
      qFatal("cannot call setParents on type 3 item");
    }
    const StackItem &parent() const {return m_parent;}
    Rule rule() const {return m_rule;}
    int len() const {return m_len;}
    int curr() const {return m_curr;}
    int i() const {return m_i;}
    Node tree() const {return m_tree;}
    PseudoCatScope scope() const {return m_scope;}
    int ruleno() const {return m_ruleno;}
    NextTokenConstraints nextTokenConstraints() const {
      return m_nextTokenConstraints;
    }
  private:
    StackItem m_parent;
    Rule m_rule;
    int m_len, m_curr, m_i;
    Node m_tree;
    PseudoCatScope m_scope;
    int m_ruleno;
    NextTokenConstraints m_nextTokenConstraints;
};


class StackItemType4 : public UnifiedStackItemData {
  public:
    StackItemType4(const StackItem &parent, CatArg target, int pos, int len)
      : m_parent(parent), m_target(target), m_pos(pos), m_len(len) {}
    virtual ~StackItemType4() {}
    virtual StackItemData *clone() {return new StackItemType4(*this);}
    virtual int type() const {return 4;}
    virtual void addParent(const StackItem &) {
      qFatal("cannot call addParent on type 4 item");
    }
    virtual void setParents(const QList<StackItem> &) {
      qFatal("cannot call setParents on type 4 item");
    }
    const StackItem &parent() const {return m_parent;}
    Cat target() const {return m_target;}
    int pos() const {return m_pos;}
    int len() const {return m_len;}
  private:
    StackItem m_parent;
    Cat m_target;
    int m_pos, m_len;
};

class StackItemType5 : public StackItemData {
  public:
    StackItemType5(const StackItem &parent, CatArg cat,
                   const PseudoCatScope &scope)
      : m_parent(parent), m_cat(cat), m_scope(scope) {}
    virtual ~StackItemType5() {}
    virtual StackItemData *clone() {return new StackItemType5(*this);}
    virtual int type() const {return 5;}
    virtual void addParent(const StackItem &) {
      qFatal("cannot call addParent on type 5 item");
    }
    virtual void setParents(const QList<StackItem> &) {
      qFatal("cannot call setParents on type 5 item");
    }
    const StackItem &parent() const {return m_parent;}
    Cat cat() const {return m_cat;}
    PseudoCatScope scope() const {return m_scope;}
  private:
    StackItem m_parent;
    Cat m_cat;
    PseudoCatScope m_scope;
};

class StackItemType6 : public StackItemData {
  public:
    StackItemType6(const StackItem &parent, const QList<Node> &leaves, int i,
                   const Node &tree, const PseudoCatScope &scope,
                   const NextTokenConstraints &nextTokenConstraints)
      : m_parent(parent), m_leaves(leaves), m_i(i), m_tree(tree),
        m_scope(scope), m_nextTokenConstraints(nextTokenConstraints) {}
    virtual ~StackItemType6() {}
    virtual StackItemData *clone() {return new StackItemType6(*this);}
    virtual int type() const {return 6;}
    virtual void addParent(const StackItem &) {
      qFatal("cannot call addParent on type 6 item");
    }
    virtual void setParents(const QList<StackItem> &) {
      qFatal("cannot call setParents on type 6 item");
    }
    const StackItem &parent() const {return m_parent;}
    QList<Node> leaves() const {return m_leaves;}
    int i() const {return m_i;}
    Node tree() const {return m_tree;}
    PseudoCatScope scope() const {return m_scope;}
    NextTokenConstraints nextTokenConstraints() const {
      return m_nextTokenConstraints;
    }
  private:
    StackItem m_parent;
    QList<Node> m_leaves;
    int m_i;
    Node m_tree;
    PseudoCatScope m_scope;
    NextTokenConstraints m_nextTokenConstraints;
};

inline StackItem::StackItem(const QList<StackItem> &parents, CatArg cat,
                            CatArg effCat, int pos,
                            const PseudoCatScope &scope)
{
  d = new StackItemType0(parents, cat, effCat, pos, scope);
}

inline StackItem::StackItem(const QList<StackItem> &parents, CatArg cat,
                            CatArg effCat, const PseudoCatScope &scope)
{
  d = new StackItemType1(parents, cat, effCat, scope);
}

inline StackItem::StackItem(const StackItem &parent, int)
{
  d = new StackItemType2(parent);
}

inline StackItem::StackItem(const StackItem &parent, const Rule &rule, int len,
                            int curr, int i, const Node &tree,
                            const PseudoCatScope &scope, int ruleno,
                            const NextTokenConstraints &nextTokenConstraints)
{
  d = new StackItemType3(parent, rule, len, curr, i, tree, scope, ruleno,
                         nextTokenConstraints);
}

inline StackItem::StackItem(const StackItem &parent, CatArg target, int pos,
                            int len)
{
  d = new StackItemType4(parent, target, pos, len);
}

inline StackItem::StackItem(const StackItem &parent, CatArg cat,
                            const PseudoCatScope &scope)
{
  d = new StackItemType5(parent, cat, scope);
}

inline StackItem::StackItem(const StackItem &parent, const QList<Node> &leaves,
                            int i, const Node &tree,
                            const PseudoCatScope &scope,
                            const NextTokenConstraints &nextTokenConstraints)
{
  d = new StackItemType6(parent, leaves, i, tree, scope, nextTokenConstraints);
}


// --- token source abstraction ---

class AbstractLexerStateData : public QSharedData {
  public:
    virtual ~AbstractLexerStateData() {}
    virtual AbstractLexerStateData *clone() = 0;
};

class LexerState {
  public:
    LexerState() : d() {}
    LexerState(AbstractLexerStateData *data) : d(data) {}
    void clear() { d = 0; }
    bool isNull() const { return !d.constData(); }
    const AbstractLexerStateData *data() const { return d.constData(); }
    bool operator==(const LexerState &other) const { return d == other.d; }
  private:
    QSharedDataPointer<AbstractLexerStateData> d;
};

class TokenSource {
  public:
    TokenSource() : currPos(0) {}
    virtual ~TokenSource() {}

    Cat nextToken() {
      tree = Node();
      Cat result = readToken();
      if (!IS_EPSILON(result)) {
        // If the implementation of readToken didn't create a parse tree, create
        // the default one: a leaf node.
        if (tree.children.isEmpty()) tree = Node(result);
        currPos++;
      }
      return result;
    }
    Node parseTree() {
      return tree;
    }

    virtual bool matchParseTree(const Node &treeToMatch) {
      return treeToMatch.cat == tree.cat;
    }
    int currentPosition() {return currPos;}

    virtual bool rewindTo(int pos, const LexerState & = LexerState()) {
      tree = Node();
      return (pos == currPos);
    }
    virtual LexerState saveState() {return LexerState();}
  protected:
    virtual Cat readToken() = 0;

    bool simpleRewind(int pos) {
      tree = Node(); // destroy saved parse tree
      if (pos > currPos) // cannot rewind forward
        return false;
      currPos = pos;
      return true;
    }
    int currPos;

    Node tree;
};

class ListTokenSource : public TokenSource {
  public:
    ListTokenSource() : TokenSource() {}
    virtual ~ListTokenSource() {}
    QList<Cat> inputTokens;
    virtual bool rewindTo(int pos, const LexerState & = LexerState()) {
      return simpleRewind(pos);
    }
  protected:
    virtual Cat readToken() {
      if (currPos < inputTokens.size())
        return inputTokens.at(currPos);
      return Cat();
    }
};


struct TextPosition {
  TextPosition() : line(0), col(0) {}
  TextPosition(int l, int c) : line(l), col(c) {}

  void reset() { line = col = 0; }

  void countCharacter(unsigned char c) {
    // ignore CR
    if (c == '\r') return;

    if (c == '\n') { // LF
      line++;
      col = 0;
    } else col++; // horizontal character
  }

  int line; 
  int col; 
};


// --- data structures for PMCFGs (in standard representation) ---

struct Term {
  Term() : arg(-1), component(0), token() {}
  Term(int a, int c) : arg(a), component(c), token() {}
  Term(CatArg t) : arg(-1), component(0), token(t) {}
  int arg, component;
  Cat token;
  bool isComponent() const {return arg >= 0;}
  bool isToken() const {return arg < 0;}
  bool operator==(const Term &other) const {
    return arg == other.arg && component == other.component
           && token == other.token;
  }
};

class Sequence : public QList<Term> {
  public:
    NextTokenConstraints nextTokenConstraints;

    Sequence() : QList<Term>(), nextTokenConstraints() {}
    explicit Sequence(const NextTokenConstraints &ntc)
      : QList<Term>(), nextTokenConstraints(ntc) {}
    explicit Sequence(const QList<Term> &list)
      : QList<Term>(list), nextTokenConstraints() {}
    Sequence(const QList<Term> &list, const NextTokenConstraints &ntc)
      : QList<Term>(list), nextTokenConstraints(ntc) {}
    Sequence &operator+=(const QList<Term> &other) {
      QList<Term>::operator+=(other);
      return *this;
    }
    Sequence &operator+=(const Term &value) {
      QList<Term>::operator+=(value);
      return *this;
    }
    Sequence &operator<<(const QList<Term> &other) {
      QList<Term>::operator<<(other);
      return *this;
    }
    Sequence &operator<<(const Term &value) {
      QList<Term>::operator<<(value);
      return *this;
    }
    void add(const Term &value) {
      append(value);
    }
    QList<Term> &toList() {
      return (QList<Term> &) *this;
    }
};

class Function: public QList<Sequence> {
  public:
    Function() : QList<Sequence>() {}
    explicit Function(const QList<Sequence> &list) : QList<Sequence>(list) {}
    Function &operator+=(const QList<Sequence> &other) {
      QList<Sequence>::operator+=(other);
      return *this;
    }
    Function &operator+=(const Sequence &value) {
      QList<Sequence>::operator+=(value);
      return *this;
    }
    Function &operator<<(const QList<Sequence> &other) {
      QList<Sequence>::operator<<(other);
      return *this;
    }
    Function &operator<<(const Sequence &value) {
      QList<Sequence>::operator<<(value);
      return *this;
    }
    void add(const Sequence &value) {
      append(value);
    }
    QList<Sequence> &toList() {
      return (QList<Sequence> &) *this;
    }
};

struct Pmcfg {



  QList<Function> functions;

  RuleSet rules;

  TokenSet tokens;

  Cat startCat;

  RuleSet cfRules;


  QHash<int, QString> functionNames;
  QHash<QString, int> functionIndices;
  void addFunction(const QString &name, const Function &function) {
    int index = functions.size();
    functions.append(function);
    functionNames.insert(index, name);
    functionIndices.insert(name, index);
  }
  Function lookupFunction(const QVariant &id) const {
    if (id.type() == QVariant::Int) return functions.at(id.toInt());

    QString name = id.toString();
    if (!functionIndices.contains(name)) return Function();
    return functions.at(functionIndices.value(name));
  }
};

struct PmcfgComponentInfo {
  PmcfgComponentInfo() {}
  PmcfgComponentInfo(const Rule &rule)
    : pmcfgRule(rule), argPositions(rule.size()) {}
  Rule pmcfgRule;
  QVector<QVector<int> > argPositions; 
};

Node parseTreeToPmcfgSyntaxTree(const Node &parseTree);


// --- parse state struct, for bindings ---

struct ParseState {
  ParseState()
    : errorPos(-1), errorToken(), incrementalPos(-1), incrementalStacks(),
      incrementalMatches(), lexerState() {}
  // explicitly implement the default copy constructor to get it bound
  ParseState(const ParseState &other)
    : errorPos(other.errorPos), errorToken(other.errorToken),
      incrementalPos(other.incrementalPos),
      incrementalStacks(other.incrementalStacks),
      incrementalMatches(other.incrementalMatches), lexerState(other.lexerState)
      {}

  int errorPos;
  Cat errorToken;
  int incrementalPos;
  QList<StackItem> incrementalStacks;
  QList<Match> incrementalMatches;
  LexerState lexerState;

  void reset() { *this = ParseState(); }
};


// --- main class ---

class Parser {
  public:
    // interface methods
    Parser(TokenSource *tokenSource)
      : inputSource(tokenSource), lastGeneratedCat(0) {}
    virtual ~Parser() {}
    bool isToken(CatArg cat) const {return tokens.contains(cat);}
    void addToken(CatArg cat) {tokens.insert(cat);}
    bool isLiteral(const QList<Cat> &list) const;
    void initCaches();
    void addRule(CatArg cat, const Rule &rule);
    void loadCfg(const Cfg &cfg) {
      rules = cfg.rules;
      tokens = cfg.tokens;
      startCat = cfg.startCat;
      initCaches();
    }
    bool loadPmcfg(const Pmcfg &pmcfg);
    bool addPmcfgRule(Pmcfg &pmcfg, CatArg cat, const Rule &rule);
    QList<Match> parse(int *errorPos = 0, Cat *errorToken = 0,
                       int *incrementalPos = 0,
                       QList<StackItem> *incrementalStacks = 0,
                       QList<Match> *incrementalMatches = 0,
                       LexerState *lexerState = 0);
    QList<Match> parse(ParseState *parseState) {
      return parse(&parseState->errorPos, &parseState->errorToken,
                   &parseState->incrementalPos, &parseState->incrementalStacks,
                   &parseState->incrementalMatches, &parseState->lexerState);
    }
    Predictions computePredictions(const QList<StackItem> &stacks) const;
    Predictions computePredictions(const ParseState &parseState) const {
      return computePredictions(parseState.incrementalStacks);
    }
    QHash<Cat, QSet<Cat> > expandNonterminalPrediction(CatArg cat) const;
    QHash<Cat, QSet<Cat> > expandNonterminalPredictionC(CatArg cat);
    MultiPredictions computeMultiPredictions(const QList<StackItem> &stacks)
      const;
    MultiPredictions computeMultiPredictions(const ParseState &parseState) const
    {
      return computeMultiPredictions(parseState.incrementalStacks);
    }

    QHash<QList<Cat>, QList<MultiPrediction> >
      computeMultiPredictionsJava(const ParseState &parseState) const
    {
      return multiHashToListHash(computeMultiPredictions(parseState));
    }
    QHash<Cat, QSet<QList<Cat> > >
      expandNonterminalPredictionMulti(CatArg cat) const;
    QHash<Cat, QSet<QList<Cat> > >
      expandNonterminalPredictionMultiC(CatArg cat);
    ConstrainedPredictions computeConstrainedPredictions(
      const QList<StackItem> &stacks) const;
    ConstrainedPredictions computeConstrainedPredictions(
      const ParseState &parseState) const {
      return computeConstrainedPredictions(parseState.incrementalStacks);
    }

    QHash<Cat, QList<NextTokenConstraints> >
      computeConstrainedPredictionsJava(const ParseState &parseState) const
    {
      return multiHashToListHash(computeConstrainedPredictions(parseState));
    }
    QHash<Cat, QSet<Cat> > expandNonterminalPredictionC(CatArg cat,
      const NextTokenConstraints &nextTokenConstraints);
    QHash<Cat, QSet<Cat> > expandNonterminalPredictionC(CatArg cat,
      const QList<NextTokenConstraints> &nextTokenConstraintsList);
    ConstrainedMultiPredictions computeConstrainedMultiPredictions(
      const QList<StackItem> &stacks) const;
    ConstrainedMultiPredictions computeConstrainedMultiPredictions(
      const ParseState &parseState) const
    {
      return computeConstrainedMultiPredictions(parseState.incrementalStacks);
    }

    QHash<QList<Cat>, QList<ConstrainedMultiPrediction> >
      computeConstrainedMultiPredictionsJava(const ParseState &parseState) const
    {
      return multiHashToListHash(computeConstrainedMultiPredictions(
                                   parseState));
    }
    QHash<Cat, QSet<QList<Cat> > >
      expandNonterminalPredictionMultiC(CatArg cat,
      const NextTokenConstraints &nextTokenConstraints);
    QHash<Cat, QSet<QList<Cat> > >
      expandNonterminalPredictionMultiC(CatArg cat,
      const QList<NextTokenConstraints> &nextTokenConstraintsList);




    RuleSet rules;
    TokenSet tokens;
    Cat startCat;




    QHash<Cat, QPair<Cat, QList<Cat> > > pseudoCats;

    QHash<Cat, QPair<Cat, int> > componentCats;

    QHash<Cat, QList<Cat> > catComponents;

  protected:
    TokenSource *inputSource;

  private:
    // helper methods
    Cat effectiveCat(CatArg cat) const;
    void processRule(CatArg cat, const Rule &rule, int skip, int ruleno,
                     QQueue<Cat> &nullableQueue, bool &clearEpsilonMatches);
    bool computePmcfgDimension(CatArg cat, const Rule &rule,
                               const Pmcfg &pmcfg);
    bool convertPmcfgRule(CatArg cat, const Rule &rule, const Pmcfg &pmcfg,
                          bool updateCaches);
    bool reachable(CatArg cat, CatArg target, QSet<Cat> mark);
    QList<FullRule> neighborhood(CatArg cat, CatArg target);
    void finalizeMatches(QList<Match> &matches, CatArg cat,
                         const PseudoCatScope &scope);
    void copyScope(QList<Match> &matches, const PseudoCatScope &scope);
    QList<Match> matchCFToEpsilon(CatArg cat, QSet<Cat> mark);
    QList<Match> matchEffectiveCatToEpsilon(CatArg cat, QSet<Cat> mark);
    QList<Match> matchToEpsilonRecurse(CatArg cat, QSet<Cat> mark,
                                       const PseudoCatScope &scope);
    QList<Match> matchToEpsilon(CatArg cat, const PseudoCatScope &scope);
    bool matchesTokenRecurse(CatArg cat, CatArg token, QSet<Cat> mark) const;
    bool matchesToken(CatArg cat, CatArg token) const;
    void collectLeaves(const Node &tree, QList<Node> &leaves);
    bool validateNextTokenConstraints(CatArg token,
      const NextTokenConstraints &nextTokenConstraints) const;
    QList<Match> match(CatArg cat, int pos, const PseudoCatScope &scope,
                       const StackItem &stack,
                       const NextTokenConstraints &nextTokenConstraints);
    QList<Match> matchRemaining(const Rule &rule, int len, int curr, int i,
                                const Node &tree, const PseudoCatScope &scope,
                                int ruleno, const StackItem &stack,
                                const NextTokenConstraints
                                  &nextTokenConstraints);
    Cat findFirstToken(const Node &tree);
    void unify(QList<Match> &matches);
    QList<Match> reduce(CatArg cat, CatArg target, int pos, int len,
                        const Node &tree, const StackItem &stack,
                        const PseudoCatScope &scope, int ruleno,
                        const NextTokenConstraints &nextTokenConstraints,
                        QSet<Cat> mark = QSet<Cat>());
    QList<Match> processStackItem(const StackItem &item,
                                  const QList<Match> &matches);
    QList<Match> processStack(const StackItem &stack, CatArg token);
    void computeUsageCounts(const StackItem &item);
    bool shift(int pos);
    void expandNonterminalPredictionRecurse(CatArg cat,
                                            QHash<Cat, QSet<Cat> > &result,
                                            QSet<Cat> &mark) const;
    void expandNonterminalPredictionRecurseC(CatArg cat,
                                             QHash<Cat, QSet<Cat> > &result,
                                             QSet<Cat> mark, int ruleno,
                                             const PseudoCatScope &scope,
                                             const NextTokenConstraints
                                               &nextTokenConstraints);
    void expandNonterminalPredictionMultiRecurse(CatArg cat,
      QHash<Cat, QSet<QList<Cat> > > &result, QSet<Cat> &mark) const;
    void expandNonterminalPredictionMultiRecurseC(CatArg cat,
      QHash<Cat, QSet<QList<Cat> > > &result, QSet<Cat> mark, int ruleno,
      const PseudoCatScope &scope,
      const NextTokenConstraints &nextTokenConstraints);
    int generateCat() { return --lastGeneratedCat; }

    QMultiHash<Cat, FullRule> initialGraph;
    QHash<QPair<Cat, Cat>, QList<FullRule> > neighborhoods;
    QSet<Cat> nullable;
    QHash<Cat, QList<Match> > epsilonMatches;

    QList<StackItem> nextStacks;
    QList<Match> currentMatches;
    LexerState currentLexerState;
    QHash<Cat, int> type0Indices;

    QHash<const StackItemData *, QList<Match> > collectedMatches;
    int errPos;
    Cat errToken;
    int lastGeneratedCat;
};

} // end namespace


// --- utility functions in the global namespace ---

Q_DECLARE_METATYPE(DynGenPar::PmcfgComponentInfo)

uint qHash(const QList<DynGenPar::Cat> &list);

template<>
  inline DynGenPar::StackItemData
    *QSharedDataPointer<DynGenPar::StackItemData>::clone()
{
  return d->clone();
}

template<>
  inline DynGenPar::AbstractLexerStateData
    *QSharedDataPointer<DynGenPar::AbstractLexerStateData>::clone()
{
  return d->clone();
}

#endif // DYNGENPAR_H