dyngenpar.cpp

Go to the documentation of this file.

/* DynGenPar: Dynamic Generalized Parser
   Copyright (C) 2010-2012 Kevin Kofler <kevin.kofler@chello.at>
   Copyright (C) 2014-2018 DAGOPT Optimization Technologies GmbH
                           written by Kevin Kofler <kofler@dagopt.com>

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

#include "dyngenpar.h"

uint qHash(const QList<DynGenPar::Cat> &list) {
  uint result = 0, i = 0;
  foreach (DynGenPar::CatArg cat, list)
    result += (++i) * qHash(cat);
  return result;
}

namespace DynGenPar {
bool Rule::serializeLabels = true;

bool Rule::serializeActions = true;

uint qHash(const NextTokenConstraints &nextTokenConstraints)
{
  return (qHash(nextTokenConstraints.expect) << 4)
         + qHash(nextTokenConstraints.taboo);
}


static void parseTreeToPmcfgSyntaxTreeUnify(Node &dest, const Node &src)
{
  if (src.cat != dest.cat || src.data != dest.data)
    qFatal("invalid parse tree: PMCFG unification failed (mismatched nodes)");

  // check for metavariables and do the trivial unification
  if (src.children.isEmpty()) return;
  if (dest.children.isEmpty()) {
    dest.children = src.children;
    return;
  }

  int s = dest.children.size();
  if (src.children.size() != s)
    qFatal("invalid parse tree: PMCFG unification failed (mismatched "
           "alternative counts)");
  for (int i=0; i<s; i++) {
    const Alternative &srcAlternative = src.children.at(i);
    Alternative &destAlternative = dest.children[i];
    int l = destAlternative.size();
    if (srcAlternative.size() != l
        || srcAlternative.label() != destAlternative.label())
      qFatal("invalid parse tree: PMCFG unification failed (mismatched "
             "alternatives)");
    for (int j=0; j<l; j++)
      parseTreeToPmcfgSyntaxTreeUnify(destAlternative[j], srcAlternative.at(j));
  }
}

static void parseTreeToPmcfgSyntaxTreeRecurse(const Node &parseTree,
                                              Node &syntaxTree)
{
  /* first copy the data (most useful if a token was passed as an argument to a
     PMCFG function, an extension to standard PMCFGs allowed by this
     implementation) */
  syntaxTree.data = parseTree.data;
  bool isFirst = true;
  foreach(const Alternative &alternative, parseTree.children) {
    // create a new alternative if this is not the first one
    if (isFirst)
      isFirst = false;
    else
      syntaxTree.children.append(Alternative());
    Alternative &newAlternative = syntaxTree.children.last();

    QVariant label = alternative.label();
    if (label.canConvert<PmcfgComponentInfo>()) {
      PmcfgComponentInfo componentInfo = label.value<PmcfgComponentInfo>();
      newAlternative.setLabel(componentInfo.pmcfgRule.label());
      int numArgs = componentInfo.pmcfgRule.size();
      for (int i=0; i<numArgs; i++) {
        CatArg arg = componentInfo.pmcfgRule.at(i);
        Node newChild(arg);
        const QVector<int> &argPositions = componentInfo.argPositions.at(i);
        if (argPositions.isEmpty())
          newChild.children.clear(); // no alternative == metavariable
        else {
          parseTreeToPmcfgSyntaxTreeRecurse(
            alternative.at(argPositions.first()), newChild);
          int s = argPositions.size();
          for (int i=1; i<s; i++) {
            Node tempChild(arg);
            parseTreeToPmcfgSyntaxTreeRecurse(alternative.at(
              argPositions.at(i)), tempChild);
            parseTreeToPmcfgSyntaxTreeUnify(newChild, tempChild);
          }
        }
        newAlternative.append(newChild);
      }
    } else newAlternative = alternative; // non-PMCFG category, copy parse tree
  }
}

Node parseTreeToPmcfgSyntaxTree(const Node &parseTree)
{
  Node syntaxTree(parseTree.cat);
  parseTreeToPmcfgSyntaxTreeRecurse(parseTree, syntaxTree);
  return syntaxTree;
}

QHash<QString, ActionDeserializer *> Action::deserializers;


bool Parser::isLiteral(const QList<Cat> &list) const
{
  foreach (CatArg cat, list)
    if (!isToken(cat)) return false;
  return true;
}


Cat Parser::effectiveCat(CatArg cat) const
{
  if (pseudoCats.contains(cat)) // convert pseudo-category
    return pseudoCats.value(cat).first;
  return cat; // not a pseudo-category, just return the original category
}


void Parser::initCaches(void)
{
  // clear caches
  initialGraph.clear();
  neighborhoods.clear();
  nullable.clear();
  epsilonMatches.clear();

  // search for nullable categories
  /* First consider only rules which directly expand to epsilon, i.e. with empty
     right hand side. */
  QHashIterator<Cat, QList<Rule> > it(rules);
  while (it.hasNext()) {
    it.next();
    Cat cat = it.key();
    foreach (const Rule &rule, it.value()) {
      if (rule.isEmpty()) {
        nullable.insert(cat);
        break;
      }
    }
  }
  /* Now consider rules which expand to nullable categories, inductively until
     no new nullables are added. This works because we do not have to consider
     directly or indirectly recursive rules, because those can only expand to
     epsilon if the category can already expand to epsilon without that rule. */
  unsigned newNullables;
  do {
    newNullables = 0u;
    it = rules;
    while (it.hasNext()) {
      it.next();
      Cat cat = it.key();
      if (nullable.contains(cat)) continue; // already nullable
      foreach (const Rule &rule, it.value()) {
        foreach (CatArg cati, rule) {
          if (!nullable.contains(effectiveCat(cati))) goto next_rule;
        }
        nullable.insert(cat);
        newNullables++;
        break;
next_rule:
        ;
      }
    }
  } while (newNullables);

  // now compute the initial graph
  it = rules;
  while (it.hasNext()) {
    it.next();
    Cat cat = it.key();
    // only keep the rule number if we need it, in order to allow unification
    bool keepRuleNumbers = componentCats.contains(cat);
    QList<Rule> ruleList = it.value();
    int n = ruleList.size();
    for (int i=0; i<n; i++) {
      /* For each nonempty rule (empty rules do not show up in the initial
         graph), we insert at least one edge from the first item in the rule
         to the left hand side, with 0 epsilons skipped. Then, as long as the
         first i categories are nullable and the (i+1)th category exists, we
         insert an edge with i epsilons skipped from the (i+1)th category to the
         left hand side. */
      const Rule &rule = ruleList.at(i);
      QListIterator<Cat> it(rule);
      int epsilonsSkipped=0;
      while (it.hasNext()) {
        Cat cati = effectiveCat(it.next());
        initialGraph.insert(cati, FullRule(cat, rule, epsilonsSkipped,
                                           keepRuleNumbers ? i : 0));
        if (!nullable.contains(cati)) break;
        epsilonsSkipped++;
      }
    }
  }
}


void Parser::processRule(CatArg cat, const Rule &rule, int skip, int ruleno,
                         QQueue<Cat> &nullableQueue, bool &clearEpsilonMatches)
{
  /* Continue processing the rule where we stopped when building the original
     initial graph. (If the rule is new, start at position 0.) As long as the
     first i categories are nullable and the (i+1)th category exists, we insert
     an edge with i epsilons skipped from the (i+1)th category to the left hand
     side.*/
  QListIterator<Cat> i(rule);
  int epsilonsSkipped=skip;
  while (i.hasNext()) {
    Cat cati = effectiveCat(i.next());
    initialGraph.insert(cati, FullRule(cat, rule, epsilonsSkipped, ruleno));
    if (!nullable.contains(cati)) break;
    epsilonsSkipped++;
  }
  if (epsilonsSkipped == rule.size()) { // !i.hasNext() is not sufficient!
    /* We reached the end of the rule, so the left hand side is now nullable
       and we have a new way to get epsilon matches. */
    clearEpsilonMatches = true;
    if (!nullable.contains(cat) && !nullableQueue.contains(cat))
      nullableQueue.enqueue(cat);
  }
}

void Parser::addRule(CatArg cat, const Rule &rule)
{
  // add the rule to the grammar
  QList<Rule> &ruleList = rules[cat];
  // only keep the rule number if we need it, in order to allow unification
  int ruleno = componentCats.contains(cat) ? ruleList.size() : 0;
  ruleList << rule;

  // update initialGraph and nullable
  QQueue<Cat> nullableQueue; // new nullable categories
  bool clearEpsilonMatches = false;
  /* first process the rule we just added:
     Add the new edges, if any, to the initial graph, and mark the category as
     nullable if the rule can match the empty string. */
  processRule(cat, rule, 0, ruleno, nullableQueue, clearEpsilonMatches);
  // now handle categories which have become nullable
  while (!nullableQueue.isEmpty()) {
    Cat newNullable = nullableQueue.dequeue();
    // mark the category as nullable
    nullable.insert(newNullable);
    /* now update the initial graph:
       We need to go through all the edges going out of this category in the
       initial graph and process the rule starting from where we stopped when
       building the initial graph (due to the non-nullable category). If we
       reach the end of the rule, the left hand side has become nullable as
       well, and is added to the queue if it wasn't already nullable. */
    foreach (const FullRule &rule, initialGraph.values(newNullable))
      processRule(rule.cat, rule.rule, rule.epsilonsSkipped+1, rule.ruleno,
                  nullableQueue, clearEpsilonMatches);
  }
  if (clearEpsilonMatches) {
    epsilonMatches.clear();
    neighborhoods.clear();
  } else if (!rule.isEmpty()) {
    // remove only those neighborhoods that are no longer valid
    typedef QPair<Cat, Cat> CatPair;
    QHashIterator<CatPair, QList<FullRule> > it(neighborhoods);
    QList<CatPair> invalidate;
    CatArg ruleFirst = rule.first();
    bool firstIsNullable = nullable.contains(ruleFirst);
    while (it.hasNext()) {
      it.next();
      const CatPair &key = it.key();
      if (reachable(cat, key.second, QSet<Cat>())
        && (firstIsNullable || reachable(key.first, ruleFirst, QSet<Cat>()))) {
        invalidate << key;
      }
    }
    foreach (const CatPair &key, invalidate) neighborhoods.remove(key);
  }
}


bool Parser::computePmcfgDimension(CatArg cat, const Rule &rule,
                                   const Pmcfg &pmcfg)
{
  // look the function up
  Function function = pmcfg.lookupFunction(rule.label());
  /* check if the dimension is consistent with existing rules for the category,
     if any; generate a list of components if we don't have any yet */
  int dim = function.size();
  if (dim == 1) {
    if (catComponents.contains(cat)) {
      qWarning("dimension mismatch: 1D function for multidimensional category");
      return false; // dimension mismatch
    }
  } else {
    if (rules.contains(cat)) {
      qWarning("dimension mismatch: multidimensional function for 1D category");
      return false; // dimension mismatch
    }
    if (catComponents.contains(cat)) {
      if (catComponents.value(cat).size() != dim) {
        qWarning("dimension mismatch: %dD function for %dD category", dim,
                 catComponents.value(cat).size());
        return false; // dimension mismatch
      }
    } else { // not known yet, we need to create a mapping
      QList<Cat> components;
      for (int i=0; i<dim; i++) {
        // generate an internal category for the component
#ifdef DYNGENPAR_INTEGER_CATEGORIES
        Cat component = generateCat();
#else
        Cat component = QString("%1[%2]").arg(cat).arg(i);
#endif
        components.append(component);
        componentCats.insert(component, qMakePair(cat, i));
      }
      catComponents.insert(cat, components);
    }
  }
  return true;
}


bool Parser::convertPmcfgRule(CatArg cat, const Rule &rule, const Pmcfg &pmcfg,
                              bool updateCaches)
{
  // look the function up
  Function function = pmcfg.lookupFunction(rule.label());
  /* get the list of components to use (assume that the dimensions have been
     already validated by computePmcfgDimension) */
  int dim = function.size();
  QList<Cat> components;
  if (dim == 1)
    components.append(cat);
  else
    components = catComponents.value(cat);

  // determine the number of used arguments of the function
  int numArgs = 0;
  foreach(const Sequence &sequence, function) {
    foreach(const Term &term, sequence) {
      if (term.isComponent() && term.arg >= numArgs)
        numArgs = term.arg + 1;
    }
  }

  // check that enough arguments were passed to the function
  if (rule.size() < numArgs) {
    qWarning("not enough arguments for PMCFG function");
    return false;
  }

  // find the components of the arguments passed
  QVector<QList<Cat> > argComponents(numArgs);
  for (int i=0; i<numArgs; i++) {
    CatArg arg = rule.at(i);
    if (catComponents.contains(arg))
      argComponents[i] = catComponents.value(arg);
    else if (pmcfg.rules.contains(arg) || pmcfg.cfRules.contains(arg)
             || pmcfg.tokens.contains(arg))
      argComponents[i].append(arg);
    else
      /* unused category, ignore the unreachable rule
         We do not know the correct dimension for the unused category. */
      return true;
  }

  // verify the dimensions of the arguments passed
  foreach(const Sequence &sequence, function) {
    foreach(const Term &term, sequence) {
      if (term.isComponent()
          && term.component >= argComponents.at(term.arg).size()) {
        qWarning("dimension mismatch: attempt to use component %d of a %dD "
                 "category", term.component, argComponents.at(term.arg).size());
        return false; // dimension mismatch
      }
    }
  }

  // determine the number of times each argument is used
  QVector<int> usageCounts(numArgs);
  foreach(const Sequence &sequence, function) {
    foreach(const Term &term, sequence) {
      if (term.isComponent())
        usageCounts[term.arg]++;
    }
  }

  // generate pseudo-categories
  QVector<QHash<int, Cat> > newPseudoCats(numArgs);
  foreach(const Sequence &sequence, function) {
    foreach(const Term &term, sequence) {
      if (term.isComponent() && usageCounts.at(term.arg) > 1) {
        if (!newPseudoCats[term.arg].contains(term.component)) {
#ifdef DYNGENPAR_INTEGER_CATEGORIES
          Cat pseudoCat = generateCat();
#else
          Cat pseudoCat = QString("Pseudo%1").arg(generateCat());
#endif
          newPseudoCats[term.arg].insert(term.component, pseudoCat);
        }
      }
    }
  }

  // record pseudo-categories
  for (int i=0; i<numArgs; i++) {
    const QHash<int, Cat> &pseudoCatHash = newPseudoCats.at(i);
    if (!pseudoCatHash.isEmpty()) {
      QList<Cat> pseudoCatList = pseudoCatHash.values();
      QHashIterator<int, Cat> it(pseudoCatHash);
      while (it.hasNext()) {
        it.next();
        Cat pseudoCat = it.value();
        pseudoCats.insert(pseudoCat, qMakePair(argComponents.at(i).at(it.key()),
                                               pseudoCatList));
      }
    }
  }

  // now finish evaluating the function and record the converted rule
  for (int i=0; i<dim; i++) {
    const Sequence &sequence = function.at(i);
    PmcfgComponentInfo componentInfo(rule);
    int s = sequence.size();
    for (int j=0; j<s; j++) {
      const Term &term = sequence.at(j);
      if (term.isComponent())
        componentInfo.argPositions[term.arg].append(j);
    }
    Rule internalRule(QVariant::fromValue(componentInfo));
    // copy next token constraints from the PMCFG sequence
    internalRule.nextTokenConstraints = sequence.nextTokenConstraints;
    /* Also try to use next token constraints from the PMCFG rule. That's not a
       good place to write them because the constraints will affect all
       components of a multi-dimensional rule, which is probably not what you
       want. But at least for 1D rules, it makes sense, and it costs us almost
       nothing to support this. (Appending an empty list is trivial.) */
    internalRule.nextTokenConstraints.expect.append(
      rule.nextTokenConstraints.expect);
    internalRule.nextTokenConstraints.taboo.append(
      rule.nextTokenConstraints.taboo);
    foreach (const Term &term, sequence)
      internalRule.append(term.isToken() ? term.token
                          : newPseudoCats.at(term.arg).isEmpty()
                            ? argComponents.at(term.arg).at(term.component)
                            : newPseudoCats.at(term.arg).value(term.component));

    CatArg catComponent = components.at(i);
    if (updateCaches)
      addRule(catComponent, internalRule);
    else
      rules[catComponent].append(internalRule);
  }

  return true;
}


bool Parser::loadPmcfg(const Pmcfg &pmcfg)
{
  // copy tokens, startCat and cfRules
  tokens = pmcfg.tokens;
  startCat = pmcfg.startCat;
  rules = pmcfg.cfRules;

  // convert functions and PMCFG rules to rules and pseudo-categories
  pseudoCats.clear();
  componentCats.clear();
  catComponents.clear();
  {
    QHashIterator<Cat, QList<Rule> > it(pmcfg.rules);
    while (it.hasNext()) {
      Cat cat = it.next().key();
      foreach (const Rule &rule, it.value())
        if (!computePmcfgDimension(cat, rule, pmcfg)) return false;
    }
  }
  {
    QHashIterator<Cat, QList<Rule> > it(pmcfg.rules);
    while (it.hasNext()) {
      Cat cat = it.next().key();
      foreach (const Rule &rule, it.value())
        if (!convertPmcfgRule(cat, rule, pmcfg, false)) return false;
    }
  }

  // initialize the initial graph and the caches
  initCaches();
  return true;
}


bool Parser::addPmcfgRule(Pmcfg &pmcfg, CatArg cat, const Rule &rule)
{
  if (!computePmcfgDimension(cat, rule, pmcfg)
      || !convertPmcfgRule(cat, rule, pmcfg, true)) return false;
  pmcfg.rules[cat].append(rule);
  return true;
}


bool Parser::reachable(CatArg cat, CatArg target, QSet<Cat> mark)
{
  if (cat == target) return true;
  mark.insert(cat);
  foreach (const FullRule &rule, initialGraph.values(cat)) {
    if (mark.contains(rule.cat)) continue;
    if (reachable(rule.cat, target, mark)) return true;
  }
  return false;
}


QList<FullRule> Parser::neighborhood(CatArg cat, CatArg target)
{
  // use cached value if we have it
  QPair<Cat, Cat> key(cat, target);
  if (neighborhoods.contains(key)) return neighborhoods.value(key);

  QList<FullRule> result;
  foreach (const FullRule &rule, initialGraph.values(cat)) {
    if (reachable(rule.cat, target, QSet<Cat>())) result.append(rule);
  }
  // cache the result for future reuse
  neighborhoods.insert(key, result);
  return result;
}

void Parser::finalizeMatches(QList<Match> &matches, CatArg cat,
                             const PseudoCatScope &scope)
{
  int s = matches.size();
  for (int i=0; i<s; i++) {
    Match &m = matches[i];
    PseudoCatScope childScope = m.scope;
    m.scope = scope;
    m.scope.pConstraints().insert(cat,
      qMakePair(qMakePair(m.tree, m.nextTokenConstraints), 0));
    foreach (CatArg cati, pseudoCats.value(cat).second)
      m.scope.mcfgConstraints().insert(cati, qMakePair(m.ruleno, childScope));
    m.ruleno = 0; // We don't need ruleno anymore.
  }
}

void Parser::copyScope(QList<Match> &matches, const PseudoCatScope &scope)
{
  if (scope.isNull()) return; // don't bother copying a null scope
  int s = matches.size();
  for (int i=0; i<s; i++)
    matches[i].scope = scope;
}

QList<Match> Parser::matchCFToEpsilon(CatArg cat, QSet<Cat> mark)
{
  QList<Match> result;
  bool haveNextTokenConstraints = false;

  mark.insert(cat);
  bool isFirst = true;
  foreach (const Rule &rule, rules.value(cat)) {
    // only consider nullable rules with only unmarked categories
    foreach (CatArg cati, rule) {
      if (!nullable.contains(cati) || mark.contains(cati)) goto next_rule;
    }
    {
      QList<Match> currentMatches;
      Node node(cat);
      node.children.first().setLabel(rule.label());
      currentMatches.append(Match(0, node, 0, PseudoCatScope()));
      if (!rule.nextTokenConstraints.expect.isEmpty()) {
        haveNextTokenConstraints = true;
        currentMatches.first().nextTokenConstraints.expect =
          rule.nextTokenConstraints.expect;
      }
      if (!rule.nextTokenConstraints.taboo.isEmpty()) {
        haveNextTokenConstraints = true;
        currentMatches.first().nextTokenConstraints.taboo =
          rule.nextTokenConstraints.taboo;
      }
      foreach (CatArg cati, rule) {
        int s = currentMatches.size();
        for (int i=0; i<s; ) {
          Match &m = currentMatches[i];
          const QList<Match> componentMatches 
            = matchToEpsilonRecurse(cati, mark, m.scope);
          if (componentMatches.isEmpty()) {
            if (i) currentMatches.swap(0, i);
            currentMatches.removeFirst();
            s--;
          } else {
            int cs = componentMatches.size();
            for (int j=1; j<cs; j++) {
              const Match &cm = componentMatches.at(j);
              Node newTree = m.tree;
              newTree.children.first().append(cm.tree);
              currentMatches.append(Match(m.len + cm.len, newTree, 0, cm.scope,
                                          m.nextTokenConstraints));
              if (!cm.nextTokenConstraints.expect.isEmpty()) {
                haveNextTokenConstraints = true;
                currentMatches.last().nextTokenConstraints.expect.append(
                  cm.nextTokenConstraints.expect);
              }
              if (!cm.nextTokenConstraints.taboo.isEmpty()) {
                haveNextTokenConstraints = true;
                currentMatches.last().nextTokenConstraints.taboo.append(
                  cm.nextTokenConstraints.taboo);
              }
            }
            const Match &cm = componentMatches.first();
            m.len += cm.len;
            m.tree.children.first().append(cm.tree);
            m.scope = cm.scope;
            if (!cm.nextTokenConstraints.expect.isEmpty()) {
              haveNextTokenConstraints = true;
              m.nextTokenConstraints.expect.append(
                cm.nextTokenConstraints.expect);
            }
            if (!cm.nextTokenConstraints.taboo.isEmpty()) {
              haveNextTokenConstraints = true;
              m.nextTokenConstraints.taboo.append(
                cm.nextTokenConstraints.taboo);
            }
            i++;
          }
        }
      }
      if (currentMatches.isEmpty()) goto next_rule;
      if (haveNextTokenConstraints) {
        /* We cannot just unify all the matches to one in this case. We will run
           the full unification process at the end. But clear the scopes. */
        int s = currentMatches.size();
        for (int i=0; i<s; i++) currentMatches[i].scope = PseudoCatScope();
        result.append(currentMatches);
        goto next_rule;
      }
      /* unify the matches:
         * if this is the first matching rule, make the first match the current
           result
         * otherwise, append the new alternative(s) from the first match to the
           current result
         * if there is more than one match, also append the alternative(s) from
           the additional matches */
      int i=0, s=currentMatches.size();
      if (isFirst) {
        isFirst = false;
        result.append(currentMatches.first());
        result.first().scope = PseudoCatScope(); // clear scope
        i++;
      }
      Match &firstResult = result.first();
      for (; i<s; i++)
        firstResult.tree.children.append(currentMatches.at(i).tree.children);
    }
next_rule:
    ;
  }
  /* unify the result now (as much as possible) if we have next token
     constraints, otherwise it is already unified to a single match */
  if (haveNextTokenConstraints) unify(result);
  return result;
}

QList<Match> Parser::matchEffectiveCatToEpsilon(CatArg cat, QSet<Cat> mark)
{
  QList<Match> result;

  /* if the effective category is 1-dimensional, don't bother about rule numbers
     and child scopes - they are not needed for P constraints (the only ones we
     can have on pseudo-categories for 1-dimensional effective categories) */
  if (!componentCats.contains(cat))
    return matchCFToEpsilon(cat, mark);

  mark.insert(cat);
  QList<Rule> ruleList = rules.value(cat);
  int s = ruleList.size();
  for (int i=0; i<s; i++) {
    const Rule &rule = ruleList.at(i);
    // only consider nullable rules with only unmarked categories
    foreach (CatArg cati, rule) {
      if (!nullable.contains(cati) || mark.contains(cati)) goto next_rule;
    }
    {
      QList<Match> currentMatches;
      Node node(cat);
      node.children.first().setLabel(rule.label());
      currentMatches.append(Match(0, node, i, PseudoCatScope(),
                                  rule.nextTokenConstraints));
      foreach (CatArg cati, rule) {
        int s = currentMatches.size();
        for (int i=0; i<s; ) {
          Match &m = currentMatches[i];
          const QList<Match> componentMatches
            = matchToEpsilonRecurse(cati, mark, m.scope);
          if (componentMatches.isEmpty()) {
            if (i) currentMatches.swap(0, i);
            currentMatches.removeFirst();
            s--;
          } else {
            int cs = componentMatches.size();
            for (int j=1; j<cs; j++) {
              const Match &cm = componentMatches.at(j);
              Node newTree = m.tree;
              newTree.children.first().append(cm.tree);
              currentMatches.append(Match(m.len + cm.len, newTree, m.ruleno,
                                          cm.scope, m.nextTokenConstraints));
              currentMatches.last().nextTokenConstraints.expect.append(
                cm.nextTokenConstraints.expect);
              currentMatches.last().nextTokenConstraints.taboo.append(
                cm.nextTokenConstraints.taboo);
            }
            const Match &cm = componentMatches.first();
            m.len += cm.len;
            m.tree.children.first().append(cm.tree);
            m.scope = cm.scope;
            m.nextTokenConstraints.expect.append(
              cm.nextTokenConstraints.expect);
            m.nextTokenConstraints.taboo.append(cm.nextTokenConstraints.taboo);
            i++;
          }
        }
      }
      // in this case, we cannot unify, so just append the matches to the result
      result.append(currentMatches);
    }
next_rule:
    ;
  }
  return result;
}

QList<Match> Parser::matchToEpsilonRecurse(CatArg cat, QSet<Cat> mark,
                                           const PseudoCatScope &scope)
{
  QList<Match> result;

  if (scope.hasPConstraint(cat)) {
    // handle P constraint
    QPair<QPair<Node, NextTokenConstraints>, int> pConstraint
      = scope.pConstraint(cat);
    if (!pConstraint.second) // only matches if length == 0
      result.append(Match(0, pConstraint.first.first, 0, scope,
                          pConstraint.first.second));
    return result;
  }

  // if this is a pseudo-category, it is not known yet, so get the effective
  // category (if this is not a pseudo-category, effCat is cat itself)
  Cat effCat = effectiveCat(cat);

  if (effCat != cat) { // cat is a pseudo-category
    if (mark.contains(effCat)) return result; // prevent infinite recursion
    mark.insert(cat);

    if (scope.hasMcfgConstraint(cat)) {
      // handle MCFG constraint
      QPair<int, PseudoCatScope> mcfgConstraint = scope.mcfgConstraint(cat);
      const Rule &rule = rules.value(effCat).at(mcfgConstraint.first);
      /* check if we can (possibly - there could be other PMCFG constraints
         preventing it) produce epsilon with this rule, and make sure the
         categories in the rule are not marked to prevent infinite recursion */
      foreach (CatArg cati, rule) {
        if (!nullable.contains(cati) || mark.contains(cati)) return result;
      }
      Node node(effCat);
      node.children.first().setLabel(rule.label());
      result.append(Match(0, node, mcfgConstraint.first, scope,
                          rule.nextTokenConstraints));
      foreach (CatArg cati, rule) {
        int s = result.size();
        for (int i=0; i<s; ) {
          Match &m = result[i];
          const QList<Match> componentMatches
            = matchToEpsilonRecurse(cati, mark, m.scope);
          if (componentMatches.isEmpty()) {
            if (i) result.swap(0, i);
            result.removeFirst();
            s--;
          } else {
            int cs = componentMatches.size();
            for (int j=1; j<cs; j++) {
              const Match &cm = componentMatches.at(j);
              Node newTree = m.tree;
              newTree.children.first().append(cm.tree);
              result.append(Match(m.len + cm.len, newTree, m.ruleno,
                                  cm.scope, m.nextTokenConstraints));
              result.last().nextTokenConstraints.expect.append(
                cm.nextTokenConstraints.expect);
              result.last().nextTokenConstraints.taboo.append(
                cm.nextTokenConstraints.taboo);
            }
            const Match &cm = componentMatches.first();
            m.len += cm.len;
            m.tree.children.first().append(cm.tree);
            m.scope = cm.scope;
            m.nextTokenConstraints.expect.append(
              cm.nextTokenConstraints.expect);
            m.nextTokenConstraints.taboo.append(cm.nextTokenConstraints.taboo);
            i++;
          }
        }
      }
    } else // no PMCFG constraints on this pseudo-category
      result = matchEffectiveCatToEpsilon(effCat, mark);

    finalizeMatches(result, cat, scope);
  } else { // cat is a true category
    result = matchCFToEpsilon(cat, mark);
    copyScope(result, scope);
  }

  return result;
}


QList<Match> Parser::matchToEpsilon(CatArg cat, const PseudoCatScope &scope)
{
  QList<Match> result;

  if (scope.hasPConstraint(cat)) {
    // handle P constraint
    QPair<QPair<Node, NextTokenConstraints>, int> pConstraint
      = scope.pConstraint(cat);
    if (!pConstraint.second) // only matches if length == 0
      result.append(Match(0, pConstraint.first.first, 0, scope,
                          pConstraint.first.second));
    return result;
  }

  // if this is a pseudo-category, it is not known yet, so get the effective
  // category (if this is not a pseudo-category, effCat is cat itself)
  Cat effCat = effectiveCat(cat);

  if (effCat != cat) { // cat is a pseudo-category
    if (scope.hasMcfgConstraint(cat)) {
      // handle MCFG constraint
      QPair<int, PseudoCatScope> mcfgConstraint = scope.mcfgConstraint(cat);
      const Rule &rule = rules.value(effCat).at(mcfgConstraint.first);
      /* check if we can (possibly - there could be other PMCFG constraints
         preventing it) produce epsilon with this rule */
      foreach (CatArg cati, rule) {
        if (!nullable.contains(cati)) return result;
      }
      Node node(effCat);
      node.children.first().setLabel(rule.label());
      result.append(Match(0, node, mcfgConstraint.first, scope,
                          rule.nextTokenConstraints));
      foreach (CatArg cati, rule) {
        int s = result.size();
        for (int i=0; i<s; ) {
          Match &m = result[i];
          const QList<Match> componentMatches = matchToEpsilon(cati, m.scope);
          if (componentMatches.isEmpty()) {
            if (i) result.swap(0, i);
            result.removeFirst();
            s--;
          } else {
            int cs = componentMatches.size();
            for (int j=1; j<cs; j++) {
              const Match &cm = componentMatches.at(j);
              Node newTree = m.tree;
              newTree.children.first().append(cm.tree);
              result.append(Match(m.len + cm.len, newTree, m.ruleno,
                                  cm.scope, m.nextTokenConstraints));
              result.last().nextTokenConstraints.expect.append(
                cm.nextTokenConstraints.expect);
              result.last().nextTokenConstraints.taboo.append(
                cm.nextTokenConstraints.taboo);
            }
            const Match &cm = componentMatches.first();
            m.len += cm.len;
            m.tree.children.first().append(cm.tree);
            m.scope = cm.scope;
            m.nextTokenConstraints.expect.append(
              cm.nextTokenConstraints.expect);
            m.nextTokenConstraints.taboo.append(cm.nextTokenConstraints.taboo);
            i++;
          }
        }
      }
    } else { // no PMCFG constraints on this pseudo-category
      // We cannot cache the result here because the scopes can change.
      /* FIXME: Well, we could cache the result with a dummy scope and then
                compute the union. Is that worth it? */
      result = matchEffectiveCatToEpsilon(effCat, QSet<Cat>());
    }

    finalizeMatches(result, cat, scope);
  } else { // cat is a true category
    // memoize the matches for efficiency
    // FIXME: this will probably need to get smarter (or disabled) for
    //        context-sensitive constraints
    if (epsilonMatches.contains(cat))
      result = epsilonMatches.value(cat);
    else {
      result = matchCFToEpsilon(cat, QSet<Cat>());
      epsilonMatches.insert(cat, result);
    }
    copyScope(result, scope);
  }

  return result;
}

bool Parser::matchesTokenRecurse(CatArg cat, CatArg token, QSet<Cat> mark) const
{
  // Handle the trivial case first.
  if (isToken(cat)) return cat == token;

  // Now cat is a nonterminal.
  mark.insert(cat);
  foreach (const Rule &rule, rules.value(cat)) {
    // an epsilon rule cannot match a token
    if (rule.isEmpty()) continue;
    // for each element of the rule, try matching that element to the token and
    // the rest to epsilon
    int l = rule.size();
    for (int i=0; i<l; i++) {
      CatArg cati = rule.at(i);
      /* Left recursion cannot match a token if it doesn't match without the
         recursion because tokens are atomic. */
      if (mark.contains(cati)) continue; // ignore left recursion
      for (int j=0; j<l; j++) {
        if (i == j) continue;
        if (!nullable.contains(rule.at(j))) goto skip_this_i; // match epsilon
      }
      if (matchesTokenRecurse(cati, token, mark)) return true; // match token
skip_this_i: ;
    }
  }

  // None of the rules matched.
  return false;
}


bool Parser::matchesToken(CatArg cat, CatArg token) const
{
  return matchesTokenRecurse(cat, token, QSet<Cat>());
}


void Parser::collectLeaves(const Node &tree, QList<Node> &leaves)
{
  if (isToken(tree.cat))
    leaves.append(tree);
  else {
    // consider only the first alternative - they must all match the same tokens
    foreach (const Node &node, tree.children.first())
      collectLeaves(node, leaves);
  }
}

bool Parser::validateNextTokenConstraints(CatArg token,
  const NextTokenConstraints &nextTokenConstraints) const
{
  foreach(CatArg expect, nextTokenConstraints.expect)
    if (!matchesToken(expect, token)) return false;
  foreach(CatArg taboo, nextTokenConstraints.taboo)
    if (matchesToken(taboo, token)) return false;
  return true;
}


QList<Match> Parser::match(CatArg cat, int pos, const PseudoCatScope &scope,
                           const StackItem &stack,
                           const NextTokenConstraints &nextTokenConstraints)
{
  QList<Match> result;

  if (scope.hasPConstraint(cat)) {
    // handle P constraint
    QPair<QPair<Node, NextTokenConstraints>, int> pConstraint
      = scope.pConstraint(cat);
    if (pConstraint.second) { // length != 0
      QList<Node> leaves;
      collectLeaves(pConstraint.first.first, leaves);
      /* check the next token constraints right now, it's no use keeping the
         type 6 item just to have the shift throw it away, and this way we don't
         have to keep 2 sets of next token constraints in the type 6 item (one
         for the first token and one for the next token after the last) */
      if (validateNextTokenConstraints(leaves.first().cat,
                                       nextTokenConstraints)) {
        StackItem type6(stack, leaves, 0, pConstraint.first.first, scope,
                        pConstraint.first.second);
        nextStacks.append(type6);
      }
    } else { // length == 0
      NextTokenConstraints newNextTokenConstraints = nextTokenConstraints;
      newNextTokenConstraints.expect.append(pConstraint.first.second.expect);
      newNextTokenConstraints.taboo.append(pConstraint.first.second.taboo);
      result.append(Match(0, pConstraint.first.first, 0, scope,
                          newNextTokenConstraints));
    }
    return result;
  }

  // if this is a pseudo-category, get the effective category (if this is not a
  // pseudo-category, effCat is cat itself)
  Cat effCat = effectiveCat(cat);

  if (scope.hasMcfgConstraint(cat)) {
    // handle MCFG constraint
    QPair<int, PseudoCatScope> mcfgConstraint = scope.mcfgConstraint(cat);
    const Rule &rule = rules.value(effCat).at(mcfgConstraint.first);

    // perform a top-down expansion of rule
    {
      StackItem type5(stack, cat, scope);
      Node node(effCat);
      node.children.first().setLabel(rule.label());
      result = matchRemaining(rule, 0, pos, 0, node, mcfgConstraint.second,
                              mcfgConstraint.first, type5,
                              nextTokenConstraints);
    }

    finalizeMatches(result, cat, scope);
  } else { // no PMCFG constraints on this category or pseudo-category
    // try epsilon matches first
    if (nullable.contains(effCat)) {
      result = matchToEpsilon(cat, scope);
      if (!nextTokenConstraints.expect.isEmpty()
          || !nextTokenConstraints.taboo.isEmpty()) {
        int s = result.size();
        for (int i=0; i<s; i++) {
          NextTokenConstraints &newNextTokenConstraints
            = result[i].nextTokenConstraints;
          newNextTokenConstraints.expect.append(nextTokenConstraints.expect);
          newNextTokenConstraints.taboo.append(nextTokenConstraints.taboo);
        }
      }
    }

    // now we want a nonempty match
    // prepare the parse stack for the next shift
    /* We do not store the next token constraints in the type 0 item because
       the type 3 parent already carries them, and they can be different for the
       different type 3 parents in the DAG-structured stack. */
    if (stack.type() < 0) { // toplevel match
      StackItem type0(QList<StackItem>(), cat, effCat, pos, scope);
      nextStacks.append(type0);
    } else { // subordinate match, i.e. nonempty stack
      // memoize type 0 item indices to build a graph-structured stack
      if (scope.isNull() && type0Indices.contains(cat))
        nextStacks[type0Indices.value(cat)].addParent(stack);
      else {
        QList<StackItem> parents;
        parents << stack;
        StackItem type0(parents, cat, effCat, pos, scope);
        if (scope.isNull()) type0Indices.insert(cat, nextStacks.size());
        nextStacks.append(type0);
      }
    }
  }

  // return the result (only epsilon matches, the rest is deferred)
  return result;
}


bool Parser::verifyLookaheadRule(const Rule &rule, int i, int &curr,
                                 int &remaining, QSet<Cat> &mark)
{
  while (i < rule.size()) {
    Cat cati = effectiveCat(rule.at(i++));
    if (isToken(cati)) {
      Cat lookahead = inputSource->nextToken();
      curr++;
      mark.clear();
      if (lookahead != cati) {
        return false;
      }
      if (!(--remaining)) {
        return true;
      }
    } else { // cati is a nonterminal
      if (!mark.contains(cati)) {
        mark.insert(cati);
        QList<Rule> catiRules = rules.value(cati);
        switch (catiRules.size()) {
          case 0:
            return false;
          case 1:
            {
              Rule catiRule = catiRules.first();
              if (!verifyLookaheadRule(catiRule, 0, curr, remaining, mark))
                return false;
              if (!remaining) return true;
            }
            break;
          default:
            foreach (const Rule &catiRule, catiRules) {
              Node parseTree = inputSource->parseTree();
              LexerState lexerState = inputSource->saveState();
              int currCopy = curr;
              int remainingCopy = remaining;
              QSet<Cat> markCopy = mark;
              if (!verifyLookaheadRule(catiRule, 0, currCopy, remainingCopy,
                                       markCopy)) {
                inputSource->rewindTo(curr, parseTree, lexerState);
                continue;
              }
              if (!remainingCopy) {
                curr = currCopy;
                remaining = 0;
                mark = markCopy;
                return true;
              }
              if (verifyLookaheadRule(rule, i, currCopy, remainingCopy,
                                      markCopy)) {
                curr = currCopy;
                remaining = remainingCopy;
                mark = markCopy;
                return true;
              }
              inputSource->rewindTo(curr, parseTree, lexerState);
            }
            return false;
        }
      }
    }
  }
  return true;
}


bool Parser::verifyLookahead(const StackItem &stack, CatArg cat, int pos,
                             int nTokens)
{
  switch (stack.type()) {
    case 0:
      qFatal("type 0 items not supported by verifyLookahead");
    case 1:
      {
        const StackItemType1 *data
          = static_cast<const StackItemType1 *>(stack.data());
        const QList<StackItem> &parents = data->parents();
        if (parents.isEmpty()) { // start category
          Node parseTree = inputSource->parseTree();
          LexerState lexerState = inputSource->saveState();
          Cat lookahead = inputSource->nextToken();
          bool ret = IS_EPSILON(lookahead);
          inputSource->rewindTo(pos, parseTree, lexerState);
          return ret;
        }
        foreach (const StackItem &parent, parents)
          if (verifyLookahead(parent, cat, pos, nTokens))
            return true;
        return false;
      }
    case 2:
      {
        const StackItemType2 *data
          = static_cast<const StackItemType2 *>(stack.data());
        const StackItem &parent = data->parent();
        return verifyLookahead(parent, cat, pos, nTokens);
      }
    case 3:
      {
        const StackItemType3 *data
          = static_cast<const StackItemType3 *>(stack.data());
        const StackItem &parent = data->parent();
        Node tree = data->tree();
        Rule rule = data->rule();
        int i = data->i() + 1;
        Node parseTree = inputSource->parseTree();
        LexerState lexerState = inputSource->saveState();
        int curr = pos;
        int remaining = nTokens;
        QSet<Cat> mark;
        bool ret = verifyLookaheadRule(rule, i, curr, remaining, mark);
        inputSource->rewindTo(pos, parseTree, lexerState);
        if (!ret) return false;
        if (!remaining) return true;
        return verifyLookahead(parent, tree.cat, curr, remaining);
      }
    case 4:
      {
        const StackItemType4 *data
          = static_cast<const StackItemType4 *>(stack.data());
        const StackItem &parent = data->parent();
        Cat target = data->target();
        Cat effCat = effectiveCat(cat);
        foreach (const FullRule &rule, neighborhood(effCat, target)) {
          Node parseTree = inputSource->parseTree();
          LexerState lexerState = inputSource->saveState();
          int i = rule.epsilonsSkipped + 1;
          int curr = pos;
          int remaining = nTokens;
          QSet<Cat> mark;
          bool ret = verifyLookaheadRule(rule.rule, i, curr, remaining, mark);
          inputSource->rewindTo(pos, parseTree, lexerState);
          if (ret) {
            if (!remaining) return true;
            if (verifyLookahead(stack, rule.cat, curr, remaining)) return true;
          }
        }
        if (effCat == target)
          return verifyLookahead(parent, target, pos, nTokens);
        else
          return false;
      }
    case 5:
      {
        const StackItemType5 *data
          = static_cast<const StackItemType5 *>(stack.data());
        const StackItem &parent = data->parent();
        Cat dataCat = data->cat();
        return verifyLookahead(parent, dataCat, pos, nTokens);
      }
    case 6:
      qFatal("type 6 items not supported by verifyLookahead");
    default:
      qFatal("invalid stack item type");
  }
}



QList<Match> Parser::matchRemaining(const Rule &rule, int len, int curr, int i,
                                    const Node &tree,
                                    const PseudoCatScope &scope, int ruleno,
                                    const StackItem &stack,
                                    const NextTokenConstraints
                                      &nextTokenConstraints)
{
  QList<Match> result;
  if (i < rule.size()) {
    QList<Match> matches;
    {
      StackItem type3(stack, rule, len, curr, i, tree, ruleno,
                      nextTokenConstraints);
      matches = match(rule.at(i), curr, scope, type3, nextTokenConstraints);
    }
    foreach (const Match &m, matches) {
      Node newTree = tree;
      newTree.children.first().append(m.tree);
      result.append(matchRemaining(rule, len+m.len, curr+m.len, i+1, newTree,
                                   m.scope, ruleno, stack,
                                   m.nextTokenConstraints));
    }
  } else {
    if (rule.action) {
      int lookaheadTokens = rule.action->lookaheadTokens();
      if (lookaheadTokens <= 0 // looking ahead 0 tokens is trivial
          || verifyLookahead(stack, tree.cat, inputSource->currentPosition(),
                             lookaheadTokens)) {
        ActionInfo info(tree, this);
        rule.action->execute(info);
      } else return result; // reject the matches if we are not executing the
                            // action, anything else would confuse the app
    }
    NextTokenConstraints newNextTokenConstraints = nextTokenConstraints;
    newNextTokenConstraints.expect.append(rule.nextTokenConstraints.expect);
    newNextTokenConstraints.taboo.append(rule.nextTokenConstraints.taboo);
    result.append(Match(len, tree, ruleno, scope, newNextTokenConstraints));
  }
  return result;
}


Cat Parser::findFirstToken(const Node &tree)
{
  CatArg cat = tree.cat;
  if (isToken(cat))
    return cat;
  else {
    // consider only the first alternative - they must all match the same tokens
    foreach (const Node &node, tree.children.first()) {
      Cat result = findFirstToken(node);
      if (!IS_EPSILON(result)) return result;
    }
    return Cat(); // This tree matches epsilon.
  }
}

void Parser::unify(QList<Match> &matches)
{
  int l = matches.size();
  if (l > 1) {
    /* For plain CFGs, we'd only need to match length and category here. We add
       the rule number and the scope for PMCFG matches and the next token
       constraints for scannerless parsing support. */
    QHash<QPair<QPair<QPair<int, Cat>, QPair<int, PseudoCatScope> >,
                NextTokenConstraints>, int>
      indexOfLenCat;
    {
      const Match &m = matches.first();
      indexOfLenCat.insert(qMakePair(qMakePair(qMakePair(m.len, m.tree.cat),
                                               qMakePair(m.ruleno, m.scope)),
                                     m.nextTokenConstraints), 0);
    }
    for (int i=1; i<l; ) {
      const Match &m = matches.at(i);
      QPair<QPair<QPair<int, Cat>, QPair<int, PseudoCatScope> >,
            NextTokenConstraints> key(qMakePair(qMakePair(m.len, m.tree.cat),
                                                qMakePair(m.ruleno, m.scope)),
                                      m.nextTokenConstraints);
      if (indexOfLenCat.contains(key)) {
        matches[indexOfLenCat.value(key)].tree.children.append(m.tree.children);
        matches.removeAt(i);
        l--;
      } else indexOfLenCat.insert(key, i++);
    }
  }
}


QList<Match> Parser::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)
{
  QList<Match> result;
  if (cat == target) result.append(Match(len, tree, ruleno, scope,
                                         nextTokenConstraints));
  QList<Match> matches;
  {
    StackItem type4(stack, target, pos, len);
    // for each rule to get towards the target category
    foreach (const FullRule &rule, neighborhood(cat, target)) {
      QList<Match> currentMatches;
      Node node(rule.cat);
      node.children.first().setLabel(rule.rule.label());
      int epsilonsSkipped = rule.epsilonsSkipped;
      // if we are reducing a pseudo-category, set the correct scope
      PseudoCatScope newScope;
      CatArg pseudoCat = rule.rule.at(epsilonsSkipped);
      if (pseudoCat != cat) {
        newScope.pConstraints().insert(pseudoCat,
          qMakePair(qMakePair(tree, nextTokenConstraints), len));
        foreach (CatArg cati, pseudoCats.value(pseudoCat).second)
          newScope.mcfgConstraints().insert(cati, qMakePair(ruleno, scope));
      }
      currentMatches.append(Match(0, node, rule.ruleno, newScope,
                                  nextTokenConstraints));
      /* Find the first token in the tree so we can validate the next token
         constraints of the epsilon matches. If we don't have epsilons skipped,
         don't bother doing this work.
         Also note that tree cannot be an epsilon tree because we never reduce
         epsilon. */
      Cat firstToken = Cat();
      if (epsilonsSkipped)
        firstToken = findFirstToken(tree);
      // match first items to epsilon
      for (int k=0; k<epsilonsSkipped; k++) {
        int s = currentMatches.size();
        for (int i=0; i<s; ) {
          Match &m = currentMatches[i];
          QList<Match> componentMatches = matchToEpsilon(rule.rule.at(k),
                                                         m.scope);
          /* Here, we need to validate the next token constraints in our epsilon
             matches against the first token of the tree we're reducing. */
          /* FIXME: Would it be more efficient to do this in neighborhood? It'd
                    help prediction in some (rare?) cases, too. But it'd make
                    neighborhoods dependent on the first token, which hurts
                    caching badly. */
          {
            int cs = componentMatches.size();
            for (int j=0; j<cs; ) {
              if (validateNextTokenConstraints(firstToken,
                    componentMatches.at(j).nextTokenConstraints)) j++; else {
                if (j) componentMatches.swap(0, j);
                componentMatches.removeFirst();
                cs--;
              }
            }
          }
          if (componentMatches.isEmpty()) {
            if (i) currentMatches.swap(0, i);
            currentMatches.removeFirst();
            s--;
          } else {
            int cs = componentMatches.size();
            for (int j=1; j<cs; j++) {
              const Match &cm = componentMatches.at(j);
              Node newTree = m.tree;
              newTree.children.first().append(cm.tree);
              currentMatches.append(Match(m.len + cm.len, newTree, m.ruleno,
                                          cm.scope, m.nextTokenConstraints));
            }
            const Match &cm
              = static_cast<const QList<Match> &>(componentMatches).first();
            m.len += cm.len;
            m.tree.children.first().append(cm.tree);
            m.scope = cm.scope;
            i++;
          }
        }
      }
      foreach (const Match &m, currentMatches) {
        Node newTree = m.tree;
        newTree.children.first().append(tree);
        // match remaining rule items
        matches.append(matchRemaining(rule.rule, 0, pos, epsilonsSkipped+1,
                                      newTree, m.scope, m.ruleno, type4,
                                      m.nextTokenConstraints));
      }
    }
  }
  // unify matches to a shared representation to avoid needless bifurcation
  unify(matches);
  {
    StackItem type2(stack, 0);
    foreach (const Match &m, matches) {
      Cat newCat = m.tree.cat;
      if (m.len)
        qFatal("length of a reduction increased in a non-shift codepath");
      // reduction with unchanged length
      // avoid infinite loops (if we have epsilon productions or redundant
      // X->...->X rules)
      mark.insert(cat);
      if (mark.contains(newCat)) continue;
      // now reduce the rule
      result.append(reduce(newCat, target, pos, len, m.tree, type2, m.scope,
                           m.ruleno, m.nextTokenConstraints, mark));
    }
  }
  // do another unification pass on the result
  unify(result);
  return result;
}


QList<Match> Parser::processStackItem(const StackItem &item,
                                      const QList<Match> &matches)
{
  StackItem nextItem = item;
  QList<Match> nextMatches = matches;
  tailcall: {
    const StackItem &item = nextItem;
    const QList<Match> &matches = nextMatches;
    // Do not bother proceeding any further with an empty list of matches, as
    // the result will necessarily be empty as well.
    if (matches.isEmpty()) return matches;
    switch (item.type()) {
      case 0:
        qFatal("type 0 items not supported by processStackItem");
      case 1:
        {
          const StackItemType1 *data
            = static_cast<const StackItemType1 *>(item.data());
          const QList<StackItem> &parents = data->parents();
          Cat cat = data->cat();
          Cat effCat = data->effCat();
          PseudoCatScope scope = data->scope();

          if (effCat != cat) // cat is a pseudo-category
            finalizeMatches(nextMatches, cat, scope);
          else
            copyScope(nextMatches, scope);

          if (parents.isEmpty()) // toplevel item
            return nextMatches;
          else if (parents.count() == 1) {
            nextItem = parents.first();
            goto tailcall;
          } else {
            branched = true;
            QList<Match> result;
            foreach (const StackItem &parent, parents)
              result.append(processStackItem(parent, nextMatches));
            return result;
          }
        }
        break;
      case 2:
        {
          const StackItemType2 *data
            = static_cast<const StackItemType2 *>(item.data());
          const StackItem &parent = data->parent();

          // skip unification if we know there is nothing further coming to this
          // unification point
          bool present;
          if (branched)
            present = collectedMatches.contains(data);
          else {
            if (priorityQueue.isEmpty()) {
              type_2_skip:
              nextItem = parent;
              goto tailcall;
            }
            int headDepth = priorityQueue.head().depth();
            int depth = data->depth();
            if (headDepth < depth) goto type_2_skip;
            if (headDepth == depth) {
              present = collectedMatches.contains(data);
              if (!present) goto type_2_skip;
            } else present = collectedMatches.contains(data);
          }

          // unify matches, deferring processing
          if (present) {
            QPair<bool, QList<Match> > &entry = collectedMatches[data];
            entry.first = true;
            entry.second.append(matches);
          } else {
            collectedMatches[data] = qMakePair(false, matches);
            priorityQueue.enqueue(item);
          }
          return QList<Match>();
        }
        break;
      case 3:
        {
          const StackItemType3 *data
            = static_cast<const StackItemType3 *>(item.data());
          const StackItem &parent = data->parent();
          Rule rule = data->rule();
          int len = data->len();
          int curr = data->curr();
          int i = data->i();
          Node tree = data->tree();
          int ruleno = data->ruleno();

          QList<Match> result;
          foreach (const Match &m, matches) {
            Node newTree = tree;
            newTree.children.first().append(m.tree);
            result.append(matchRemaining(rule, len+m.len, curr+m.len, i+1,
                                         newTree, m.scope, ruleno, parent,
                                         m.nextTokenConstraints));
          }

          nextMatches = result;
          nextItem = parent;
          goto tailcall;
        }
        break;
      case 4:
        {
          const StackItemType4 *data
            = static_cast<const StackItemType4 *>(item.data());
          const StackItem &parent = data->parent();
          Cat target = data->target();
          int pos = data->pos();
          int len = data->len();

          // skip unification if we know there is nothing further coming to this
          // unification point
          bool present;
          if (branched)
            present = collectedMatches.contains(data);
          else {
            if (priorityQueue.isEmpty()) {
              type_4_skip:
              QList<Match> result;
              {
                StackItem type2(parent, 0);
                foreach (const Match &m, matches) {
                  Cat newCat = m.tree.cat;
                  if (!m.len)
                    qFatal("reduction with unchanged length was deferred");
                  // the length increased, reduce the rule, resetting mark
                  result.append(reduce(newCat, target, pos+m.len, len+m.len,
                                       m.tree, type2, m.scope, m.ruleno,
                                       m.nextTokenConstraints));
                }
              }
              // do another unification pass on the result
              unify(result);

              nextMatches = result;
              nextItem = parent;
              goto tailcall;
            }
            int headDepth = priorityQueue.head().depth();
            int depth = data->depth();
            if (headDepth < depth) goto type_4_skip;
            if (headDepth == depth) {
              present = collectedMatches.contains(data);
              if (!present) goto type_4_skip;
            } else present = collectedMatches.contains(data);
          }

          // unify matches, deferring processing
          if (present) {
            QPair<bool, QList<Match> > &entry = collectedMatches[data];
            entry.first = true;
            entry.second.append(matches);
          } else {
            collectedMatches[data] = qMakePair(false, matches);
            priorityQueue.enqueue(item);
          }
          return QList<Match>();
        }
      case 5:
        {
          const StackItemType5 *data
            = static_cast<const StackItemType5 *>(item.data());
          const StackItem &parent = data->parent();
          Cat cat = data->cat();
          PseudoCatScope scope = data->scope();

          finalizeMatches(nextMatches, cat, scope);

          nextItem = parent;
          goto tailcall;
        }
        break;
      case 6:
        qFatal("type 6 items not supported by processStackItem");
      default:
        qFatal("invalid stack item type");
    }
  }
}


QList<Match> Parser::processStack(const StackItem &stack, CatArg token)
{
  branched = false; // reset branched flag
  switch (stack.type()) {
    // type 0 and 6 are toplevel items
    case 0:
      {
        const StackItemType0 *data
          = static_cast<const StackItemType0 *>(stack.data());
        const QList<StackItem> &parents = data->parents();
        Cat cat = data->cat();
        Cat effCat = data->effCat();
        int pos = data->pos();
        PseudoCatScope scope = data->scope();
        QList<Match> matches;

        // type 0 item: finish processing of match after a shift
        if (isToken(cat)) {
          if (token == cat) matches.append(Match(1, inputSource->parseTree(), 0,
                                                 scope));
        } else {
          // reduce the matched token (and possibly additional tokens, with
          // deferred processing) to the target category
          StackItem type1(parents, cat, effCat, scope);
          // The token carries no next token constraints.
          matches = reduce(token, effCat, pos, 1, inputSource->parseTree(),
                           type1, PseudoCatScope(), 0, NextTokenConstraints());

          if (effCat != cat) // cat is a pseudo-category
            finalizeMatches(matches, cat, scope);
          else
            copyScope(matches, scope);
        }

        if (parents.isEmpty()) // toplevel item
          return matches;
        else {
          QList<Match> result;
          if (parents.count() > 1) branched = true;
          foreach (const StackItem &parent, parents)
            result.append(processStackItem(parent, matches));
          return result;
        }
      }
    case 6:
      {
        const StackItemType6 *data
          = static_cast<const StackItemType6 *>(stack.data());
        const StackItem &parent = data->parent();
        QList<Node> leaves = data->leaves();
        int i = data->i();
        Node tree = data->tree();
        PseudoCatScope scope = data->scope();
        NextTokenConstraints nextTokenConstraints
          = data->nextTokenConstraints();
        QList<Match> matches;

        // type 6 item: finish processing of a P constraint
        // match the i-th leaf against the shifted token
        if (inputSource->matchParseTree(leaves.at(i++))) {
          int l = leaves.size();
          if (i == l) // we're done matching the constraint
            matches.append(Match(l, tree, 0, scope, nextTokenConstraints));
          else { // not done yet, create a new type 6 item
            StackItem type6(parent, leaves, i, tree, scope,
                            nextTokenConstraints);
            nextStacks.append(type6);
          }
        }

        return processStackItem(parent, matches);
      }
    // case 2 and 4 are unification points, so look for matches collected so far
    // and process them
    case 2:
    case 4:
      {
        // We use take (= value + remove) instead of value here to ensure that
        // processStackItem will not send us back here.
        QPair<bool, QList<Match> > entry = collectedMatches.take(stack.data());
        if (entry.first) // need unification
          unify(entry.second);
        return processStackItem(stack, entry.second);
      }
    default:
      qFatal("invalid stack (expected toplevel item or unification point)");
  }
}


bool Parser::shift(int pos)
{
  if (!inputSource->rewindTo(pos, currentLexerState)) {
    qWarning("invalid input position");
    return false;
  }
  Cat token = inputSource->nextToken();
  if (IS_EPSILON(token))
    return false;

  // delete all the stacks which don't satisfy the next token constraints
  {
    int l = nextStacks.size();
    for (int i=0; i<l; ) {
      StackItem &stack = nextStacks[i];
      // type 6 items are already filtered for next token constraints
      if (stack.type()) i++; else {
        const StackItemType0 *data
          = static_cast<const StackItemType0 *>(stack.data());
        QList<StackItem> parents = data->parents();
        // no parents = toplevel item, skip processing to avoid killing this
        if (parents.empty()) i++; else {
          int n = parents.size();
          for (int j=0; j<n; ) {
            const StackItem &parent = parents.at(j);
            const StackItemType3 *parentData
              = static_cast<const StackItemType3 *>(parent.data());
            if (validateNextTokenConstraints(token,
                  parentData->nextTokenConstraints())) j++; else {
              if (j) parents.swap(0, j);
              parents.removeFirst();
              n--;
            }
          }
          // no parents left, kill the type 0 item
          if (parents.isEmpty()) {
            if (i) nextStacks.swap(0, i);
            nextStacks.removeFirst();
            l--;
          } else {
            stack.setParents(parents);
            i++;
          }
        }
      }
    }
  }

  // if no more stacks, set errPos and errToken and return false
  // (this happens if we had a valid complete parse, but no continuations, and
  // now there's extra input)
  if (nextStacks.isEmpty()) {
    errPos = pos;
    errToken = token;
    return false;
  }

  // process stack
  currentMatches.clear();
  QList<StackItem> currentStacks = nextStacks;
  nextStacks.clear();
  priorityQueue = Private::PriorityQueue<StackItem>(currentStacks);
  while (!priorityQueue.isEmpty())
    currentMatches.append(processStack(priorityQueue.dequeue(), token));
  type0Indices.clear();

  // if no more stacks and no current matches, set errPos and errToken, restore
  // the previous nextStacks to allow running prediction on them and return
  // false
  if (nextStacks.isEmpty() && currentMatches.isEmpty()) {
    errPos = pos;
    errToken = token;
    nextStacks = currentStacks;
    return false;
  }

  currentLexerState = inputSource->saveState();
  return true;
}


QList<Match> Parser::parse(int *errorPos, Cat *errorToken, int *incrementalPos,
                           QList<StackItem> *incrementalStacks,
                           QList<Match> *incrementalMatches,
                           LexerState *lexerState)
{
  int pos = 0;

  if (!incrementalPos || *incrementalPos < 0) // start a new parse
    currentMatches = match(startCat, 0, PseudoCatScope(), StackItem(),
                           NextTokenConstraints());
  else { // continue an incremental parse
    pos = *incrementalPos;
    if (incrementalMatches) currentMatches = *incrementalMatches;
    if (incrementalStacks) nextStacks = *incrementalStacks;
  }

  if (lexerState)
    currentLexerState = *lexerState;
  else
    currentLexerState.clear();

  // shift tokens while possible
  errPos = -1;
  while (shift(pos)) pos++;

  // error handling
  if (errPos >= 0) { // parse error
    if (errorPos) *errorPos = errPos;
    if (errorToken) *errorToken = errToken;
    if (incrementalPos) *incrementalPos = errPos;
    if (incrementalStacks) *incrementalStacks = nextStacks;
    if (incrementalMatches) incrementalMatches->clear();
    if (lexerState) *lexerState = currentLexerState;
    errPos = -1;
    errToken = Cat();
    nextStacks.clear();
    currentMatches.clear();
    currentLexerState.clear();
    return QList<Match>();
  }
  if (errorPos) *errorPos = -1;
  if (errorToken) *errorToken = Cat();

  // filter all the matches which have expect-type next token constraints
  {
    int s = currentMatches.size();
    for (int i=0; i<s; ) {
      Match &m = currentMatches[i];
      if (m.nextTokenConstraints.expect.isEmpty()) i++; else {
        if (i) currentMatches.swap(0, i);
        currentMatches.removeFirst();
        s--;
      }
    }
  }

  // incremental parsing
  if (incrementalPos) *incrementalPos = pos;
  if (incrementalMatches) *incrementalMatches = currentMatches;
  if (incrementalStacks) *incrementalStacks = nextStacks;
  if (lexerState) *lexerState = currentLexerState;
  nextStacks.clear();
  currentLexerState.clear();

  // accept current matches
  QList<Match> result = currentMatches;
  currentMatches.clear();
  return result;
}


Predictions Parser::computePredictions(const QList<StackItem> &stacks) const
{
  Predictions predict;
  foreach (const StackItem &stack, stacks) {
    if (stack.type()) { // type 6 item
      const StackItemType6 *data
        = static_cast<const StackItemType6 *>(stack.data());
      predict.insert(data->leaves().at(data->i()).cat);
    } else // type 0 item
      predict.insert(static_cast<const StackItemType0 *>(stack.data())
                       ->effCat());
  }
  return predict;
}

void Parser::expandNonterminalPredictionRecurse(CatArg cat,
                                                QHash<Cat, QSet<Cat> > &result,
                                                QSet<Cat> &mark) const
{
  mark.insert(cat);
  foreach (const Rule &rule, rules.value(cat)) {
    QListIterator<Cat> i(rule);
    /* For each nonempty rule (empty rules are not interesting for prediction),
       we handle at least the first item in the rule as a prediction: if it's a
       token, it is our prediction and the corresponding nonterminal is this
       category; if it's a nonterminal, we need to process the prediction
       recursively, unless it is already marked, indicating direct or indirect
       left recursion (and allowing us to stop) or the repetition of an already
       tried possibility (also allowing us to stop, since we do not care about
       parse trees here, only the last category). Then, as long as the first i
       categories are nullable and the (i+1)th category exists, we repeat the
       process for the (i+1)th category. */
    while (i.hasNext()) {
      Cat cati = effectiveCat(i.next());
      if (isToken(cati)) {
        result[cat].insert(cati); // record nonterminal and token
        break; // tokens are not nullable
      }
      // now cati is a nonterminal
      if (!mark.contains(cati))
        expandNonterminalPredictionRecurse(cati, result, mark);
      if (!nullable.contains(cati)) break;
    }
  }
}


QHash<Cat, QSet<Cat> > Parser::expandNonterminalPrediction(CatArg cat) const
{
  QHash<Cat, QSet<Cat> > result;
  QSet<Cat> mark;
  if (isToken(cat))
    qWarning("trying to expand terminal prediction");
  else
    expandNonterminalPredictionRecurse(cat, result, mark);
  return result;
}

void Parser::expandNonterminalPredictionRecurseC(CatArg cat,
                                                 QHash<Cat, QSet<Cat> > &result,
                                                 QSet<Cat> mark, int ruleno,
                                                 const PseudoCatScope &scope,
                                                 const NextTokenConstraints
                                                   &nextTokenConstraints)
{
  mark.insert(cat);
  QList<Rule> ruleList = rules.value(cat);
  int firstRule = ruleno >= 0 ? ruleno : 0;
  int lastRule = ruleno >= 0 ? ruleno : ruleList.size() - 1;
  for (int currRule = firstRule; currRule <= lastRule; currRule++) {
    const Rule &rule = ruleList.at(currRule);
    QListIterator<Cat> i(rule);
    /* For each nonempty rule (empty rules are not interesting for prediction),
       we handle at least the first item in the rule as a prediction: if it's a
       token, it is our prediction and the corresponding nonterminal is this
       category; if it's a nonterminal, we need to process the prediction
       recursively, unless it is already marked, indicating direct or indirect
       left recursion (and allowing us to stop). Then, as long as the first i
       categories are nullable and the (i+1)th category exists, we repeat the
       process for the (i+1)th category.
       We optimize the common case of no epsilons to skip because we do not have
       to consider context-sensitive constraints in that case. */
    Cat cat1 = Cat();
    if (i.hasNext()) {
      cat1 = i.next();
      Cat effCat1 = effectiveCat(cat1);
      if (isToken(effCat1)) {
        if (validateNextTokenConstraints(effCat1, nextTokenConstraints))
          result[cat].insert(effCat1); // record nonterminal and token
        continue; // tokens are not nullable
      }
      // now effCat1 is a nonterminal
      /* If we have a P-constraint here, that constraint forces the category to
         be epsilon (because it must be identical to something already matched,
         which is epsilon). So don't predict inside it. */
      if (!mark.contains(effCat1)
          && !scope.hasPConstraint(cat1)) {
        int mcfgRuleno = -1;
        PseudoCatScope mcfgScope;
        if (scope.hasMcfgConstraint(cat1)) {
          QPair<int, PseudoCatScope> mcfgConstraint
            = scope.mcfgConstraint(cat1);
          mcfgRuleno = mcfgConstraint.first;
          mcfgScope = mcfgConstraint.second;
        }
        expandNonterminalPredictionRecurseC(effCat1, result, mark, mcfgRuleno,
                                            mcfgScope, nextTokenConstraints);
      }
      if (!nullable.contains(effCat1)) continue;
    }
    {
      QList<Match> currentMatches;
      // match cat(i-1) to epsilon first
      /* FIXME: We discard the parse trees here. Would it be more efficient
                to use a variant of matchToEpsilon which doesn't build them?
                OTOH, this way, we can reuse the matchToEpsilon cache. */
      const QList<Match> componentMatches = matchToEpsilon(cat1, scope);
      if (componentMatches.isEmpty())
        continue; // We didn't match epsilon, so we're done with this rule.
      /* If we have one version without context-sensitive constraints, the
         others are redundant. */
      bool haveUnconstrained = false;
      foreach (const Match &cm, componentMatches) {
        if (cm.scope.isNull() && cm.nextTokenConstraints.expect.isEmpty()
            && cm.nextTokenConstraints.taboo.isEmpty()) {
          haveUnconstrained = true;
          break;
        }
      }
      if (haveUnconstrained)
        currentMatches.append(Match(0, Node(), 0, scope, nextTokenConstraints));
      else {
        foreach (const Match &cm, componentMatches) {
          currentMatches.append(Match(0, Node(), 0, cm.scope,
                                      nextTokenConstraints));
          if (!cm.nextTokenConstraints.expect.isEmpty())
            currentMatches.last().nextTokenConstraints.expect.append(
              cm.nextTokenConstraints.expect);
          if (!cm.nextTokenConstraints.taboo.isEmpty())
            currentMatches.last().nextTokenConstraints.taboo.append(
              cm.nextTokenConstraints.taboo);
        }
      }
      while (i.hasNext()) {
        // now update cati for the new i
        Cat cati = i.next();
        Cat effCati = effectiveCat(cati);
        if (isToken(effCati)) {
          bool nextTokenConstraintsPass = false;
          foreach (const Match &m, currentMatches)
            if (validateNextTokenConstraints(effCati, m.nextTokenConstraints)) {
              nextTokenConstraintsPass = true;
              break;
            }
          if (nextTokenConstraintsPass)
            result[cat].insert(effCati); // record nonterminal and token
          break; // tokens are not nullable
        }
        // now effCati is a nonterminal
        if (!mark.contains(effCati)) {
          foreach (const Match &m, currentMatches)
            /* If we have a P-constraint here, that constraint forces the
               category to be epsilon (because it must be identical to something
               already matched, which is epsilon). So don't predict inside it.
               */
            if (!m.scope.hasPConstraint(cati)) {
              int mcfgRuleno = -1;
              PseudoCatScope mcfgScope;
              if (m.scope.hasMcfgConstraint(cati)) {
                QPair<int, PseudoCatScope> mcfgConstraint
                  = m.scope.mcfgConstraint(cati);
                mcfgRuleno = mcfgConstraint.first;
                mcfgScope = mcfgConstraint.second;
              }
              expandNonterminalPredictionRecurseC(effCati, result, mark,
                                                  mcfgRuleno, mcfgScope,
                                                  m.nextTokenConstraints);
            }
        }
        if (!nullable.contains(effCati)) break;
        int s = currentMatches.size();
        for (int j=0; j<s; ) {
          Match &m = currentMatches[j];
          /* FIXME: We discard the parse trees here. Would it be more efficient
                    to use a variant of matchToEpsilon which doesn't build them?
                    OTOH, this way, we can reuse the matchToEpsilon cache. */
          const QList<Match> componentMatches = matchToEpsilon(effCati,
                                                               m.scope);
          if (componentMatches.isEmpty()) {
            if (j) currentMatches.swap(0, j);
            currentMatches.removeFirst();
            s--;
          } else {
            int cs = componentMatches.size();
            /* If we have one version without context-sensitive constraints, the
               others are redundant. */
            bool haveUnconstrained = false;
            for (int k=0; k<cs; k++) {
              const Match &cm = componentMatches.at(k);
              if (cm.scope.isNull() && cm.nextTokenConstraints.expect.isEmpty()
                  && cm.nextTokenConstraints.taboo.isEmpty()) {
                haveUnconstrained = true;
                break;
              }
            }
            if (!haveUnconstrained) {
              for (int k=1; k<cs; k++) {
                const Match &cm = componentMatches.at(k);
                currentMatches.append(Match(0, Node(), 0, cm.scope,
                                            m.nextTokenConstraints));
                if (!cm.nextTokenConstraints.expect.isEmpty())
                  currentMatches.last().nextTokenConstraints.expect.append(
                    cm.nextTokenConstraints.expect);
                if (!cm.nextTokenConstraints.taboo.isEmpty())
                  currentMatches.last().nextTokenConstraints.taboo.append(
                    cm.nextTokenConstraints.taboo);
              }
              const Match &cm = componentMatches.first();
              m.scope = cm.scope;
              if (!cm.nextTokenConstraints.expect.isEmpty())
                m.nextTokenConstraints.expect.append(
                  cm.nextTokenConstraints.expect);
              if (!cm.nextTokenConstraints.taboo.isEmpty())
                m.nextTokenConstraints.taboo.append(
                  cm.nextTokenConstraints.taboo);
            }
            j++;
          }
        }
        if (currentMatches.isEmpty())
          break; // We didn't match epsilon, so we're done with this rule.
      }
    }
  }
}


QHash<Cat, QSet<Cat> > Parser::expandNonterminalPredictionC(CatArg cat)
{
  QHash<Cat, QSet<Cat> > result;
  if (isToken(cat))
    qWarning("trying to expand terminal prediction");
  else
    expandNonterminalPredictionRecurseC(cat, result, QSet<Cat>(), -1,
                                        PseudoCatScope(),
                                        NextTokenConstraints());
  return result;
}


MultiPredictions Parser::computeMultiPredictions(const QList<StackItem> &stacks)
  const
{
  MultiPredictions predictMulti;
  foreach (const StackItem &stack, stacks) {
    if (stack.type()) { // type 6 item
      /* We will define the literal as the full string of the P constraint here,
         which is very easy to obtain. This might not strictly be a literal in
         the sense of the definition, since it could be obtained from a whole
         tree of nonterminals, but it definitely always contains the literal (in
         the strict sense) containing the predicted category. */
      const StackItemType6 *data
        = static_cast<const StackItemType6 *>(stack.data());
      QList<Node> leaves = data->leaves();
      int i = data->i();
      QList<Cat> prediction, literal;
      int l = leaves.size();
      for (int j=i; j<l; j++)
        prediction.append(leaves.at(j).cat);
      literal = prediction;
      for (int j=i-1; j>=0; j--)
        literal.prepend(leaves.at(j).cat);
      MultiPrediction multiPrediction(literal, data->tree().cat);
      if (!predictMulti.contains(prediction, multiPrediction))
        predictMulti.insert(prediction, multiPrediction);
    } else { // type 0 item
      const StackItemType0 *data
        = static_cast<const StackItemType0 *>(stack.data());
      Cat cat = data->effCat();
      if (isToken(cat)) {
        const QList<StackItem> &parents = data->parents();
        if (parents.isEmpty()) { // huh, start category is a terminal?
          QList<Cat> list;
          list << cat;
          MultiPrediction multiPrediction(list, cat);
          if (!predictMulti.contains(list, multiPrediction))
            predictMulti.insert(list, multiPrediction);
        } else {
          foreach (const StackItem &parent, parents) {
            const StackItemType3 *parentData
              = static_cast<const StackItemType3 *>(parent.data());
            Rule rule = parentData->rule();
            int i = parentData->i();
            int len = 1;
            while (i+len < rule.size() && isToken(rule.at(i+len))) len++;
            QList<Cat> literal = rule.mid(i, len);
            while (i > 0 && isToken(rule.at(i-1))) i--, len++;
            MultiPrediction multiPrediction(rule.mid(i, len),
                                            parentData->tree().cat);
            if (!predictMulti.contains(literal, multiPrediction))
              predictMulti.insert(literal, multiPrediction);
          }
        }
      } else {
        QList<Cat> list;
        list << cat;
        MultiPrediction multiPrediction(list, cat);
        if (!predictMulti.contains(list, multiPrediction))
          predictMulti.insert(list, multiPrediction);
      }
    }
  }
  return predictMulti;
}

void Parser::expandNonterminalPredictionMultiRecurse(CatArg cat,
 QHash<Cat, QSet<QList<Cat> > > &result, QSet<Cat> &mark) const
{
  mark.insert(cat);
  foreach (const Rule &rule, rules.value(cat)) {
    int l = rule.size();
    /* For each nonempty rule (empty rules are not interesting for prediction),
       we handle at least the first item in the rule as a prediction: if it's a
       token, the literal starting with that token is our prediction and the
       corresponding nonterminal is this category; if it's a nonterminal, we
       need to process the prediction recursively, unless it is already marked,
       indicating direct or indirect left recursion (and allowing us to stop) or
       the repetition of an already tried possibility (also allowing us to stop,
       since we do not care about parse trees here, only the last category).
       Then, as long as the first i categories are nullable and the (i+1)th
       category exists, we repeat the process for the (i+1)th category. */
    for (int i = 0; i < l; i++) {
      Cat cati = effectiveCat(rule.at(i));
      if (isToken(cati)) {
        int len = 1;
        while (i+len < l && isToken(rule.at(i+len))) len++;
        result[cat].insert(rule.mid(i, len)); // record nonterminal and literal
        break; // tokens are not nullable
      }
      // now cati is a nonterminal
      if (!mark.contains(cati))
        expandNonterminalPredictionMultiRecurse(cati, result, mark);
      if (!nullable.contains(cati)) break;
    }
  }
}


QHash<Cat, QSet<QList<Cat> > >
  Parser::expandNonterminalPredictionMulti(CatArg cat) const
{
  QHash<Cat, QSet<QList<Cat> > > result;
  QSet<Cat> mark;
  if (isToken(cat))
    qWarning("trying to expand terminal prediction");
  else
    expandNonterminalPredictionMultiRecurse(cat, result, mark);
  return result;
}

void Parser::expandNonterminalPredictionMultiRecurseC(CatArg cat,
  QHash<Cat, QSet<QList<Cat> > > &result, QSet<Cat> mark, int ruleno,
  const PseudoCatScope &scope, const NextTokenConstraints &nextTokenConstraints)
{
  mark.insert(cat);
  QList<Rule> ruleList = rules.value(cat);
  int firstRule = ruleno >= 0 ? ruleno : 0;
  int lastRule = ruleno >= 0 ? ruleno : ruleList.size() - 1;
  for (int currRule = firstRule; currRule <= lastRule; currRule++) {
    const Rule &rule = ruleList.at(currRule);
    int l = rule.size();
    /* For each nonempty rule (empty rules are not interesting for prediction),
       we handle at least the first item in the rule as a prediction: if it's a
       token, the literal starting with that token is our prediction and the
       corresponding nonterminal is this category; if it's a nonterminal, we
       need to process the prediction recursively, unless it is already marked,
       indicating direct or indirect left recursion (and allowing us to stop).
       Then, as long as the first i categories are nullable and the (i+1)th
       category exists, we repeat the process for the (i+1)th category.
       We optimize the common case of no epsilons to skip because we do not have
       to consider context-sensitive constraints in that case. */
    Cat cat1 = Cat();
    if (l) {
      cat1 = rule.first();
      Cat effCat1 = effectiveCat(cat1);
      if (isToken(effCat1)) {
        if (validateNextTokenConstraints(effCat1, nextTokenConstraints)) {
          int len = 1;
          while (len < l && isToken(rule.at(len))) len++;
          // record nonterminal and literal
          result[cat].insert(rule.mid(0, len));
        }
        continue; // tokens are not nullable
      }
      // now effCat1 is a nonterminal
      /* If we have a P-constraint here, that constraint forces the category to
         be epsilon (because it must be identical to something already matched,
         which is epsilon). So don't predict inside it. */
      if (!mark.contains(effCat1)
          && !scope.hasPConstraint(cat1)) {
        int mcfgRuleno = -1;
        PseudoCatScope mcfgScope;
        if (scope.hasMcfgConstraint(cat1)) {
          QPair<int, PseudoCatScope> mcfgConstraint
            = scope.mcfgConstraint(cat1);
          mcfgRuleno = mcfgConstraint.first;
          mcfgScope = mcfgConstraint.second;
        }
        expandNonterminalPredictionMultiRecurseC(effCat1, result, mark,
                                                 mcfgRuleno, mcfgScope,
                                                 nextTokenConstraints);
      }
      if (!nullable.contains(effCat1)) continue;
    }
    {
      QList<Match> currentMatches;
      // match cat(i-1) to epsilon first
      /* FIXME: We discard the parse trees here. Would it be more efficient
                to use a variant of matchToEpsilon which doesn't build them?
                OTOH, this way, we can reuse the matchToEpsilon cache. */
      const QList<Match> componentMatches = matchToEpsilon(cat1, scope);
      if (componentMatches.isEmpty())
        continue; // We didn't match epsilon, so we're done with this rule.
      /* If we have one version without context-sensitive constraints, the
         others are redundant. */
      bool haveUnconstrained = false;
      foreach (const Match &cm, componentMatches) {
        if (cm.scope.isNull() && cm.nextTokenConstraints.expect.isEmpty()
            && cm.nextTokenConstraints.taboo.isEmpty()) {
          haveUnconstrained = true;
          break;
        }
      }
      if (haveUnconstrained)
        currentMatches.append(Match(0, Node(), 0, scope, nextTokenConstraints));
      else {
        foreach (const Match &cm, componentMatches) {
          currentMatches.append(Match(0, Node(), 0, cm.scope,
                                      nextTokenConstraints));
          if (!cm.nextTokenConstraints.expect.isEmpty())
            currentMatches.last().nextTokenConstraints.expect.append(
              cm.nextTokenConstraints.expect);
          if (!cm.nextTokenConstraints.taboo.isEmpty())
            currentMatches.last().nextTokenConstraints.taboo.append(
              cm.nextTokenConstraints.taboo);
        }
      }
      for (int i = 1; i < l; i++) {
        // now update cati for the new i
        Cat cati = rule.at(i);
        Cat effCati = effectiveCat(cati);
        if (isToken(effCati)) {
          bool nextTokenConstraintsPass = false;
          foreach (const Match &m, currentMatches)
            if (validateNextTokenConstraints(effCati, m.nextTokenConstraints)) {
              nextTokenConstraintsPass = true;
              break;
            }
          if (nextTokenConstraintsPass) {
            int len = 1;
            while (i+len < l && isToken(rule.at(i+len))) len++;
            // record nonterminal and literal
            result[cat].insert(rule.mid(i, len));
          }
          break; // tokens are not nullable
        }
        // now effCati is a nonterminal
        if (!mark.contains(effCati)) {
          foreach (const Match &m, currentMatches)
            /* If we have a P-constraint here, that constraint forces the
               category to be epsilon (because it must be identical to something
               already matched, which is epsilon). So don't predict inside it.
               */
            if (!m.scope.hasPConstraint(cati)) {
              int mcfgRuleno = -1;
              PseudoCatScope mcfgScope;
              if (m.scope.hasMcfgConstraint(cati)) {
                QPair<int, PseudoCatScope> mcfgConstraint
                  = m.scope.mcfgConstraint(cati);
                mcfgRuleno = mcfgConstraint.first;
                mcfgScope = mcfgConstraint.second;
              }
              expandNonterminalPredictionMultiRecurseC(effCati, result, mark,
                                                       mcfgRuleno, mcfgScope,
                                                       m.nextTokenConstraints);
            }
        }
        if (!nullable.contains(effCati)) break;
        int s = currentMatches.size();
        for (int j=0; j<s; ) {
          Match &m = currentMatches[j];
          /* FIXME: We discard the parse trees here. Would it be more efficient
                    to use a variant of matchToEpsilon which doesn't build them?
                    OTOH, this way, we can reuse the matchToEpsilon cache. */
          const QList<Match> componentMatches = matchToEpsilon(effCati,
                                                               m.scope);
          if (componentMatches.isEmpty()) {
            if (j) currentMatches.swap(0, j);
            currentMatches.removeFirst();
            s--;
          } else {
            int cs = componentMatches.size();
            /* If we have one version without context-sensitive constraints, the
               others are redundant. */
            bool haveUnconstrained = false;
            for (int k=0; k<cs; k++) {
              const Match &cm = componentMatches.at(k);
              if (cm.scope.isNull() && cm.nextTokenConstraints.expect.isEmpty()
                  && cm.nextTokenConstraints.taboo.isEmpty()) {
                haveUnconstrained = true;
                break;
              }
            }
            if (!haveUnconstrained) {
              for (int k=1; k<cs; k++) {
                const Match &cm = componentMatches.at(k);
                currentMatches.append(Match(0, Node(), 0, cm.scope,
                                            m.nextTokenConstraints));
                if (!cm.nextTokenConstraints.expect.isEmpty())
                  currentMatches.last().nextTokenConstraints.expect.append(
                    cm.nextTokenConstraints.expect);
                if (!cm.nextTokenConstraints.taboo.isEmpty())
                  currentMatches.last().nextTokenConstraints.taboo.append(
                    cm.nextTokenConstraints.taboo);
              }
              const Match &cm = componentMatches.first();
              m.scope = cm.scope;
              if (!cm.nextTokenConstraints.expect.isEmpty())
                m.nextTokenConstraints.expect.append(
                  cm.nextTokenConstraints.expect);
              if (!cm.nextTokenConstraints.taboo.isEmpty())
                m.nextTokenConstraints.taboo.append(
                  cm.nextTokenConstraints.taboo);
            }
            j++;
          }
        }
        if (currentMatches.isEmpty())
          break; // We didn't match epsilon, so we're done with this rule.
      }
    }
  }
}


QHash<Cat, QSet<QList<Cat> > >
  Parser::expandNonterminalPredictionMultiC(CatArg cat)
{
  QHash<Cat, QSet<QList<Cat> > > result;
  if (isToken(cat))
    qWarning("trying to expand terminal prediction");
  else
    expandNonterminalPredictionMultiRecurseC(cat, result, QSet<Cat>(), -1,
                                             PseudoCatScope(),
                                             NextTokenConstraints());
  return result;
}


ConstrainedPredictions Parser::computeConstrainedPredictions(
  const QList<StackItem> &stacks) const
{
  ConstrainedPredictions predict;
  foreach (const StackItem &stack, stacks) {
    if (stack.type()) { // type 6 item
      const StackItemType6 *data
        = static_cast<const StackItemType6 *>(stack.data());
      CatArg cat = data->leaves().at(data->i()).cat;
      NextTokenConstraints nextTokenConstraints;
      if (!predict.contains(cat, nextTokenConstraints))
        predict.insert(cat, nextTokenConstraints);
    } else { // type 0 item
      const StackItemType0 *data
        = static_cast<const StackItemType0 *>(stack.data());
      Cat cat = data->effCat();
      const QList<StackItem> &parents = data->parents();
      if (parents.isEmpty()) { // start category, no constraints
        NextTokenConstraints nextTokenConstraints;
        if (!predict.contains(cat, nextTokenConstraints))
          predict.insert(cat, nextTokenConstraints);
      } else {
        if (isToken(cat)) {
          // validate the next token constraints immediately for tokens
          bool nextTokenConstraintsPass = false;
          foreach (const StackItem &parent, parents) {
            const StackItemType3 *parentData
              = static_cast<const StackItemType3 *>(parent.data());
            NextTokenConstraints nextTokenConstraints
              = parentData->nextTokenConstraints();
            if (validateNextTokenConstraints(cat, nextTokenConstraints)) {
              nextTokenConstraintsPass = true;
              break;
            }
          }
          if (nextTokenConstraintsPass) {
            NextTokenConstraints nextTokenConstraints;
            if (!predict.contains(cat, nextTokenConstraints))
              predict.insert(cat, nextTokenConstraints);
          }
        } else {
          foreach (const StackItem &parent, parents) {
            const StackItemType3 *parentData
              = static_cast<const StackItemType3 *>(parent.data());
            NextTokenConstraints nextTokenConstraints
              = parentData->nextTokenConstraints();
            if (!predict.contains(cat, nextTokenConstraints))
              predict.insert(cat, nextTokenConstraints);
          }
        }
      }
    }
  }
  return predict;
}


QHash<Cat, QSet<Cat> > Parser::expandNonterminalPredictionC(CatArg cat,
  const NextTokenConstraints &nextTokenConstraints)
{
  QHash<Cat, QSet<Cat> > result;
  if (isToken(cat))
    qWarning("trying to expand terminal prediction");
  else
    expandNonterminalPredictionRecurseC(cat, result, QSet<Cat>(), -1,
                                        PseudoCatScope(),
                                        nextTokenConstraints);
  return result;
}


QHash<Cat, QSet<Cat> > Parser::expandNonterminalPredictionC(CatArg cat,
  const QList<NextTokenConstraints> &nextTokenConstraintsList)
{
  switch (nextTokenConstraintsList.size()) {
    case 0: // An empty disjunctive list is false, probably not what you want!
      qWarning("list of next token constraints is empty");
      return QHash<Cat, QSet<Cat> >();
    case 1: // common case, handle the next token constraints directly
      return expandNonterminalPredictionC(cat,
                                          nextTokenConstraintsList.first());
    default: // general case, predict first, filter later
      {
        QHash<Cat, QSet<Cat> > result = expandNonterminalPredictionC(cat);
        QHash<Cat, QSet<Cat> > filteredResult;
        QHashIterator<Cat, QSet<Cat> > it(result);
        while (it.hasNext()) {
          it.next();
          foreach (CatArg cati, it.value()) {
            bool nextTokenConstraintsPass = false;
            foreach (const NextTokenConstraints &nextTokenConstraints,
                     nextTokenConstraintsList) {
              if (validateNextTokenConstraints(cati, nextTokenConstraints)) {
                nextTokenConstraintsPass = true;
                break;
              }
            }
            if (nextTokenConstraintsPass)
              filteredResult[it.key()].insert(cati);
          }
        }
        return filteredResult;
      }
  }
}


ConstrainedMultiPredictions Parser::computeConstrainedMultiPredictions(
  const QList<StackItem> &stacks) const
{
  ConstrainedMultiPredictions predictMulti;
  foreach (const StackItem &stack, stacks) {
    if (stack.type()) { // type 6 item
      /* We will define the literal as the full string of the P constraint here,
         which is very easy to obtain. This might not strictly be a literal in
         the sense of the definition, since it could be obtained from a whole
         tree of nonterminals, but it definitely always contains the literal (in
         the strict sense) containing the predicted category. */
      const StackItemType6 *data
        = static_cast<const StackItemType6 *>(stack.data());
      QList<Node> leaves = data->leaves();
      int i = data->i();
      QList<Cat> prediction, literal;
      int l = leaves.size();
      for (int j=i; j<l; j++)
        prediction.append(leaves.at(j).cat);
      literal = prediction;
      for (int j=i-1; j>=0; j--)
        literal.prepend(leaves.at(j).cat);
      ConstrainedMultiPrediction multiPrediction(literal, data->tree().cat);
      if (!predictMulti.contains(prediction, multiPrediction))
        predictMulti.insert(prediction, multiPrediction);
    } else { // type 0 item
      const StackItemType0 *data
        = static_cast<const StackItemType0 *>(stack.data());
      Cat cat = data->effCat();
      const QList<StackItem> &parents = data->parents();
      if (isToken(cat)) {
        if (parents.isEmpty()) { // huh, start category is a terminal?
          QList<Cat> list;
          list << cat;
          ConstrainedMultiPrediction multiPrediction(list, cat);
          if (!predictMulti.contains(list, multiPrediction))
            predictMulti.insert(list, multiPrediction);
        } else {
          foreach (const StackItem &parent, parents) {
            const StackItemType3 *parentData
              = static_cast<const StackItemType3 *>(parent.data());
            // validate the next token constraints immediately for tokens
            NextTokenConstraints nextTokenConstraints
              = parentData->nextTokenConstraints();
            if (!validateNextTokenConstraints(cat, nextTokenConstraints))
              continue;
            Rule rule = parentData->rule();
            int i = parentData->i();
            int len = 1;
            while (i+len < rule.size() && isToken(rule.at(i+len))) len++;
            QList<Cat> literal = rule.mid(i, len);
            while (i > 0 && isToken(rule.at(i-1))) i--, len++;
            ConstrainedMultiPrediction multiPrediction(rule.mid(i, len),
                                                       parentData->tree().cat);
            if (!predictMulti.contains(literal, multiPrediction))
              predictMulti.insert(literal, multiPrediction);
          }
        }
      } else {
        if (parents.isEmpty()) { // start category, no constraints
          QList<Cat> list;
          list << cat;
          ConstrainedMultiPrediction multiPrediction(list, cat);
          if (!predictMulti.contains(list, multiPrediction))
            predictMulti.insert(list, multiPrediction);
        } else {
          foreach (const StackItem &parent, parents) {
            const StackItemType3 *parentData
              = static_cast<const StackItemType3 *>(parent.data());
            NextTokenConstraints nextTokenConstraints
              = parentData->nextTokenConstraints();
            QList<Cat> list;
            list << cat;
            ConstrainedMultiPrediction multiPrediction(list, cat,
                                                       nextTokenConstraints);
            if (!predictMulti.contains(list, multiPrediction))
              predictMulti.insert(list, multiPrediction);
          }
        }
      }
    }
  }
  return predictMulti;
}


QHash<Cat, QSet<QList<Cat> > >
  Parser::expandNonterminalPredictionMultiC(CatArg cat,
  const NextTokenConstraints &nextTokenConstraints)
{
  QHash<Cat, QSet<QList<Cat> > > result;
  if (isToken(cat))
    qWarning("trying to expand terminal prediction");
  else
    expandNonterminalPredictionMultiRecurseC(cat, result, QSet<Cat>(), -1,
                                             PseudoCatScope(),
                                             nextTokenConstraints);
  return result;
}


QHash<Cat, QSet<QList<Cat> > >
  Parser::expandNonterminalPredictionMultiC(CatArg cat,
  const QList<NextTokenConstraints> &nextTokenConstraintsList)
{
  switch (nextTokenConstraintsList.size()) {
    case 0: // An empty disjunctive list is false, probably not what you want!
      qWarning("list of next token constraints is empty");
      return QHash<Cat, QSet<QList<Cat> > >();
    case 1: // common case, handle the next token constraints directly
      return expandNonterminalPredictionMultiC(cat,
               nextTokenConstraintsList.first());
    default: // general case, predict first, filter later
      {
        QHash<Cat, QSet<QList<Cat> > > result
          = expandNonterminalPredictionMultiC(cat);
        QHash<Cat, QSet<QList<Cat> > > filteredResult;
        QHashIterator<Cat, QSet<QList<Cat> > > it(result);
        while (it.hasNext()) {
          it.next();
          foreach (const QList<Cat> &literal, it.value()) {
            CatArg cati = literal.first();
            bool nextTokenConstraintsPass = false;
            foreach (const NextTokenConstraints &nextTokenConstraints,
                     nextTokenConstraintsList) {
              if (validateNextTokenConstraints(cati, nextTokenConstraints)) {
                nextTokenConstraintsPass = true;
                break;
              }
            }
            if (nextTokenConstraintsPass)
              filteredResult[it.key()].insert(literal);
          }
        }
        return filteredResult;
      }
  }
}

} // end namespace