pgf.cpp

Go to the documentation of this file.

/* DynGenPar: Dynamic Generalized Parser - PGF import
   Copyright (C) 2010-2012 Kevin Kofler <kevin.kofler@chello.at>
   Copyright (C) 2014-2016 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 "pgf.h"

#include <cstdio>
#include <cmath>
#include <cctype>
#include <QIODevice>
#include <QFile>
#include <QBuffer>

namespace DynGenPar {

namespace PgfInternals {

// Convenience macro to avoid copying&pasting namespace boilerplate
#define PGFINTERNALS_DECLARE_TYPEINFO(type, typeclass) \
  } /* end namespace PgfInternals */ \
  DYNGENPAR_DECLARE_TYPEINFO(PgfInternals::type, typeclass); \
  namespace PgfInternals {

class HaskellDataStream {
  public:
    enum Status {Ok, ReadPastEnd, ReadCorruptData, IOError};
    HaskellDataStream(QIODevice *d) : iodevice(d), m_status(Ok), m_version(0),
                                      m_minorVersion(0) {}
    bool atEnd() const {return iodevice->atEnd();}
    QIODevice *device() const {return iodevice;}
    void setStatus (Status status) {m_status = status;}
    Status status() const {return m_status;}

    void readVersion();
    unsigned short version() {return m_version;}
    unsigned short minorVersion() {return m_minorVersion;}

    HaskellDataStream &operator>>(bool &b);
    HaskellDataStream &operator>>(char &c);
    HaskellDataStream &operator>>(int &i);
    HaskellDataStream &operator>>(double &d);
    HaskellDataStream &operator>>(QByteArray &bytes);
    HaskellDataStream &operator>>(QString &s);

  private:
    char nextChar();
    unsigned char nextUChar() {return (unsigned char) nextChar();}

    QIODevice *iodevice;
    Status m_status;

    unsigned short m_version;
    unsigned short m_minorVersion;
};
PGFINTERNALS_DECLARE_TYPEINFO(HaskellDataStream, Q_MOVABLE_TYPE);
PGFINTERNALS_DECLARE_TYPEINFO(HaskellDataStream::Status,
                              Q_PRIMITIVE_TYPE);

char HaskellDataStream::nextChar()
{
  if (m_status != Ok) return 0;
  if (iodevice->atEnd()) {
    m_status = ReadPastEnd;
    return 0;
  }
  char c;
  if (!iodevice->getChar(&c)) {
    m_status = IOError;
    return 0;
  }
  return c;
}

void HaskellDataStream::readVersion()
{
  unsigned char c1 = nextUChar();
  unsigned char c2 = nextUChar();
  m_version = (c1 << 8) + c2;
  if (m_version != 1 && m_version != 2 && m_status == Ok)
    m_status = ReadCorruptData;
  c1 = nextUChar();
  c2 = nextUChar();
  m_minorVersion = (c1 << 8) + c2;
  if (((m_version == 1 && m_minorVersion)
       || (m_version == 2 && m_minorVersion > 1))
      && m_status == Ok) m_status = ReadCorruptData;
}

HaskellDataStream &HaskellDataStream::operator>>(bool &b)
{
  unsigned char c = nextUChar();
  if (c > 1) {
    m_status = ReadCorruptData;
    b = false;
    return *this;
  }

  b = (bool) c;
  return *this;
}

HaskellDataStream &HaskellDataStream::operator>>(char &c)
{
  c = nextChar();
  return *this;
}

HaskellDataStream &HaskellDataStream::operator>>(int &i)
{
  unsigned char c = nextUChar();
  unsigned u = c & 0x7Fu;
  unsigned shift = 0;

  while (c & 0x80u) {
    c = nextUChar();
    u |= (c & 0x7Fu) << (shift += 7u);
  }

  i = (int) u;

  return *this;
}

HaskellDataStream &HaskellDataStream::operator>>(double &d)
{
  // read an IEEE 754 big-endian double-precision floating point number
  unsigned char c1 = nextUChar();
  unsigned char c2 = nextUChar();
  bool negative = (c1 & 0x80);
  int exponent = (((c1 & 0x7f) << 4) + (c2 >> 4));
  unsigned char c3 = nextUChar();
  unsigned char c4 = nextUChar();
  unsigned char c5 = nextUChar();
  unsigned char c6 = nextUChar();
  unsigned char c7 = nextUChar();
  unsigned char c8 = nextUChar();
  if (!exponent) {
    d = 0.;
    return *this;
  }
  exponent -= (1023 + 52);
  unsigned long long mantissa = (1ull << 52)
                                + ((unsigned long long) (c2 & 0xf) << 48)
                                + ((unsigned long long) c3 << 40)
                                + ((unsigned long long) c4 << 32)
                                + ((unsigned long long) c5 << 24)
                                + ((unsigned long long) c6 << 16)
                                + ((unsigned long long) c7 << 8)
                                + (unsigned long long) c8;

  d = std::ldexp((double) mantissa, exponent);
  if (negative) d = -d;

  return *this;
}

HaskellDataStream &HaskellDataStream::operator>>(QByteArray &bytes)
{
  bytes = QByteArray();

  int len;
  operator>>(len);

  if (len < 0) {
    m_status = ReadCorruptData;
    return *this;
  }

  for (int i=0; i<len; i++) {
    bytes.append(nextChar());
  }

  return *this;
}

HaskellDataStream &HaskellDataStream::operator>>(QString &s)
{
  int len;
  operator>>(len);

  if (len < 0) {
    m_status = ReadCorruptData;
    s = QString();
    return *this;
  }

  /* We need to count Unicode codepoints for the UTF-8 bytes read.
     Why don't they put a byte count in the serialization format??? */
  QByteArray bytes;
  for (int i=0; i<len; i++) {
    char c = nextChar();
    bytes.append(c);
    if (c >= 0) continue;
    if (!(c & 0x40)) {
      m_status = ReadCorruptData;
      s = QString();
      return *this;
    }
    int n = 1;
    if (c & 0x20) {
      n++;
      if (c & 0x10) {
        n++;
        if (c & 8) {
          m_status = ReadCorruptData;
          s = QString();
          return *this;
        }
      }
    }
    for (int j=0; j<n; j++) {
      c = nextChar();
      if ((c & 0xc0) != 0x80) {
        m_status = ReadCorruptData;
        s = QString();
        return *this;
      }
      bytes.append(c);
    }
  }

  s = QString::fromUtf8(bytes);

  return *this;
}

HaskellDataStream &operator>>(HaskellDataStream &stream, QVariant &v)
{
  char type;
  stream >> type;

  switch (type) {
    case 0: // string
      {
        QString s;
        stream >> s;
        v = s;
      }
      break;
    case 1: // int
      {
        int i;
        stream >> i;
        v = i;
      }
      break;
    case 2: // double
      {
        double d;
        stream >> d;
        v = d;
      }
      break;
    default:
      stream.setStatus(HaskellDataStream::ReadCorruptData);
      v = QVariant();
      break;
  };

  return stream;
}

template <typename T1, typename T2> HaskellDataStream
  &operator>>(HaskellDataStream &stream, QPair<T1, T2> &p)
{
  return (stream >> p.first >> p.second);
}

template <typename T> HaskellDataStream &operator>>(HaskellDataStream &stream,
                                                    QList<T> &l)
{
  int n;
  stream >> n;

  if (n < 0) {
    stream.setStatus(HaskellDataStream::ReadCorruptData);
    l = QList<T>();
    return stream;
  }

  for (int i=0; i<n; i++) {
    T entry;
    stream >> entry;
    l.append(entry);
  }

  return stream;
}

template <typename T1, typename T2> HaskellDataStream
  &operator>>(HaskellDataStream &stream, QHash<T1, T2> &h)
{
  int n;
  stream >> n;

  if (n < 0) {
    stream.setStatus(HaskellDataStream::ReadCorruptData);
    h = QHash<T1, T2>();
    return stream;
  }

  for (int i=0; i<n; i++) {
    T1 key;
    stream >> key;
    T2 value;
    stream >> value;
    h.insert(key, value);
  }

  return stream;
}

struct Type {
  // dummy structure, we don't need abstract types
};
PGFINTERNALS_DECLARE_TYPEINFO(Type, Q_PRIMITIVE_TYPE);

HaskellDataStream &operator>>(HaskellDataStream &stream, Type &dummy);

struct Hypo {
  // dummy structure, we don't need abstract types
};
PGFINTERNALS_DECLARE_TYPEINFO(Hypo, Q_PRIMITIVE_TYPE);

HaskellDataStream &operator>>(HaskellDataStream &stream, Hypo &dummy);

struct Expr {
  // dummy structure, we don't need abstract types
};
PGFINTERNALS_DECLARE_TYPEINFO(Expr, Q_PRIMITIVE_TYPE);

HaskellDataStream &operator>>(HaskellDataStream &, Expr &)
{
  qFatal("dependent types not supported");
}

HaskellDataStream &operator>>(HaskellDataStream &stream, Type &)
{
  QList<Hypo> hypos;
  QByteArray cat;
  QList<Expr> exps;
  return (stream >> hypos >> cat >> exps);
}

HaskellDataStream &operator>>(HaskellDataStream &stream, Hypo &)
{
  bool bindtype;
  QByteArray cat;
  Type type;
  return (stream >> bindtype >> cat >> type);
}

struct Equation {
  // dummy structure, we don't need abstract types
};
PGFINTERNALS_DECLARE_TYPEINFO(Equation, Q_PRIMITIVE_TYPE);

HaskellDataStream &operator>>(HaskellDataStream &, Equation &)
{
  qFatal("dependent types not supported");
}

struct AbsFun {
  // dummy structure, we don't need abstract types
};
PGFINTERNALS_DECLARE_TYPEINFO(AbsFun, Q_PRIMITIVE_TYPE);

HaskellDataStream &operator>>(HaskellDataStream &stream, AbsFun &)
{
  Type type;
  int arity;
  bool haveEquations;
  stream >> type >> arity >> haveEquations;
  if (haveEquations) {
    QList<Equation> equations;
    stream >> equations;
  }
  double probability;
  return (stream >> probability);
}

struct AbsCat {
  QList<Hypo> context;
  QList<QPair<double, QByteArray> > functions;
};
PGFINTERNALS_DECLARE_TYPEINFO(AbsCat, Q_MOVABLE_TYPE);

HaskellDataStream &operator>>(HaskellDataStream &stream, AbsCat &absCat)
{
  if (stream.version() >= 2) {
    double probability; // ignored
    return (stream >> absCat.context >> absCat.functions >> probability);
  } else return (stream >> absCat.context >> absCat.functions);
}

struct Symbol {
  enum SymType {Cat, Lit, Var, KS, KP, BIND, SOFT_BIND, NE, SOFT_SPACE, CAPIT,
                ALL_CAPIT, Invalid = -1};
  SymType symtype;
  int n, l;
  QStringList tokens;
  QList<QPair<QStringList, QStringList> > alternatives;
};
PGFINTERNALS_DECLARE_TYPEINFO(Symbol, Q_MOVABLE_TYPE);
PGFINTERNALS_DECLARE_TYPEINFO(Symbol::SymType, Q_PRIMITIVE_TYPE);

HaskellDataStream &operator>>(HaskellDataStream &stream, Symbol &symbol)
{
  char symtype;
  stream >> symtype;
  switch (symtype) {
    case (int) Symbol::Cat:
    case (int) Symbol::Lit:
    case (int) Symbol::Var:
      stream >> symbol.n >> symbol.l;
      break;
    case (int) Symbol::KS:
      if (stream.version() >= 2) {
        QString token;
        stream >> token;
        symbol.tokens = QStringList(token);
      } else stream >> symbol.tokens;
      break;
    case (int) Symbol::KP:
      if (stream.version() >= 2) {
        QList<Symbol> symbols;
        typedef QPair<QList<Symbol>, QStringList> SymAlternative;
        QList<SymAlternative> symAlternatives;
        stream >> symbols >> symAlternatives;
        symbol.tokens.clear();
        foreach (const Symbol &sym, symbols) {
          if (sym.symtype == Symbol::KS) {
            symbol.tokens << sym.tokens;
          } else {
            qFatal("non-token symbols in pre prefixes not supported");
          }
        }
        symbol.alternatives.clear();
        foreach (const SymAlternative &symAlternative, symAlternatives) {
          QPair<QStringList, QStringList> alternative;
          foreach (const Symbol & sym, symAlternative.first) {
            switch (sym.symtype) {
              case (int) Symbol::KS:
                alternative.first << sym.tokens;
                break;
              case (int) Symbol::BIND:
                alternative.first << PreludeBind;
                break;
              case (int) Symbol::SOFT_BIND:
              case (int) Symbol::SOFT_SPACE:
              case (int) Symbol::CAPIT:
              case (int) Symbol::ALL_CAPIT:
                // ignore
                break;
              default:
                qFatal("non-token, non-bind symbols in pre not supported");
            }
          }
          alternative.second = symAlternative.second;
          symbol.alternatives << alternative;
        }
      } else stream >> symbol.tokens >> symbol.alternatives;
      break;
    case (int) Symbol::BIND:
    case (int) Symbol::SOFT_BIND:
    case (int) Symbol::NE:
      if (stream.version() >= 2) break; else goto corrupt;
    case (int) Symbol::SOFT_SPACE:
    case (int) Symbol::CAPIT:
    case (int) Symbol::ALL_CAPIT:
      if (stream.version() > 2
          || (stream.version() == 2 && stream.minorVersion() >= 1)) break;
      // else fall through
    default:
    corrupt:
      stream.setStatus(HaskellDataStream::ReadCorruptData);
      symtype = -1;
      break;
  };
  symbol.symtype = (Symbol::SymType) symtype;

  return stream;
}

struct CncFun {
  QByteArray fun;
  QList<int> lins;
};
PGFINTERNALS_DECLARE_TYPEINFO(CncFun, Q_MOVABLE_TYPE);

HaskellDataStream &operator>>(HaskellDataStream &stream, CncFun &cncfun)
{
  return (stream >> cncfun.fun >> cncfun.lins);
}

struct PArg {
  // QList<QPair<int, int> > hypos; // dependent types
  int fid;
};
PGFINTERNALS_DECLARE_TYPEINFO(PArg, Q_PRIMITIVE_TYPE);

HaskellDataStream &operator>>(HaskellDataStream &stream, PArg &parg)
{
  int numHypos;
  stream >> numHypos;
  if (numHypos)
    qFatal("dependent types not supported");

  return (stream >> parg.fid);
}

struct Production {
  bool isCoercion;
  int id; // of the function for an apply, of the category for a coercion
  QList<PArg> args;
};
PGFINTERNALS_DECLARE_TYPEINFO(Production, Q_MOVABLE_TYPE);

HaskellDataStream &operator>>(HaskellDataStream &stream, Production &production)
{
  stream >> production.isCoercion >> production.id;

  if (!production.isCoercion)
    stream >> production.args;

  return stream;
}

struct CncCat {
  int s, e;
  QStringList labels;
};
PGFINTERNALS_DECLARE_TYPEINFO(CncCat, Q_MOVABLE_TYPE);

HaskellDataStream &operator>>(HaskellDataStream &stream, CncCat &cnccat)
{
  return (stream >> cnccat.s >> cnccat.e >> cnccat.labels);
}

struct Concr {
  QHash<QByteArray, QVariant> cflags;
  QHash<QByteArray, QString> printnames;
  QList<QList<Symbol> > sequences;
  QList<CncFun> cncfuns;
  QHash<int, QList<int> > lindefs;
  QHash<int, QList<Production> > productions;
  QHash<QByteArray, CncCat> cnccats;
  int totalCats;
};
PGFINTERNALS_DECLARE_TYPEINFO(Concr, Q_MOVABLE_TYPE);

HaskellDataStream &operator>>(HaskellDataStream &stream, Concr &concrete)
{
  if (stream.version() >= 2) {
    QHash<int, QList<int> > linrefs; // ignored
    return (stream >> concrete.cflags >> concrete.printnames
                   >> concrete.sequences >> concrete.cncfuns >> concrete.lindefs
                   >> linrefs >> concrete.productions >> concrete.cnccats
                   >> concrete.totalCats);
  } else {
    return (stream >> concrete.cflags >> concrete.printnames
                   >> concrete.sequences >> concrete.cncfuns >> concrete.lindefs
                   >> concrete.productions >> concrete.cnccats
                   >> concrete.totalCats);
  }
}

} // end namespace PgfInternals
namespace {} // dummy anonymous namespace to capture Doxygen comments


Pgf::Pgf(const QString &fileName, const QString &concreteName)
{
  using namespace PgfInternals;
  /* negative categories and categories 0 and 1 are reserved, so we add
     CAT_OFFSET to all GF category IDs */
  static const int CAT_OFFSET = 6;

  // deserialize the Haskell byte stream
  QFile file(fileName);
  file.open(QIODevice::ReadOnly);
  HaskellDataStream stream(&file);

#define CHECK_STATUS() if (stream.status() != HaskellDataStream::Ok) \
                         qFatal("invalid PGF file or wrong version of GF")

  stream.readVersion();
  CHECK_STATUS();

  QHash<QByteArray, QVariant> gflags;
  stream >> gflags;
  CHECK_STATUS();

  QByteArray absname;
  stream >> absname;
  CHECK_STATUS();

  QHash<QByteArray, QVariant> aflags;
  stream >> aflags;
  CHECK_STATUS();

  QHash<QByteArray, AbsFun> funs;
  stream >> funs;
  CHECK_STATUS();

  QHash<QByteArray, AbsCat> cats;
  stream >> cats;
  CHECK_STATUS();

  QHash<QByteArray, Concr> concretes;
  stream >> concretes;
  CHECK_STATUS();

  if (!stream.atEnd()) qFatal("invalid PGF file or wrong version of GF");

#undef CHECK_STATUS

  if (concretes.isEmpty())
    qFatal("invalid PGF file or wrong version of GF");

  Concr concrete;
  if (concreteName.isEmpty()) {
    if (concretes.size() > 1)
      qFatal("must specify the name of the concrete grammar");
    QHashIterator<QByteArray, Concr> it(concretes);
    concrete = it.next().value();
  } else {
    QByteArray concreteName8Bit = concreteName.toLocal8Bit();
    if (!concretes.contains(concreteName8Bit))
      qFatal("concrete grammar '%s' not found in PGF file",
             concreteName8Bit.data());
    concrete = concretes.value(concreteName8Bit);
  }

  // find the start category
  if (!aflags.contains("startcat")) qFatal("no start category specified");
  QByteArray startcatName = aflags.value("startcat").toString().toLocal8Bit();
  CncCat startcat = concrete.cnccats.value(startcatName);
  if (startcat.s != startcat.e)
    qFatal("start category '%s' has parameters", startcatName.data());
  pmcfg.startCat = startcat.s + CAT_OFFSET;

  // fetch category and component names
  catNames << "EPSILON" << "LEX_ERROR";
  while (catNames.size() < concrete.totalCats + CAT_OFFSET)
    catNames.append(QString());
  {
    QHashIterator<QByteArray, CncCat> it(concrete.cnccats);
    while (it.hasNext()) {
      CncCat cnccat = it.next().value();
      QString cat = QString::fromLocal8Bit(it.key());
      for (int i=cnccat.s; i<=cnccat.e; i++)
        catNames[i + CAT_OFFSET] = cat;
      componentNames.insert(cat, cnccat.labels);
    }
  }

  // mark the special GF categories as tokens
  for (int i=2; i<CAT_OFFSET; i++) pmcfg.tokens.insert(i);

  // convert the sequences and tokens
  QList<Sequence> sequences;
  typedef QPair<QString, int> PrefixMatch;
  typedef QPair<int, QList<PrefixMatch> > PrefixInfo;
  QList<PrefixInfo> prefixInfo;
  int nonExistCat = 0; // dummy category generated for Prelude.nonExist
  foreach (const QList<Symbol> &gfsequence, concrete.sequences) {
    Sequence sequence;
    bool isSuffix = false;
    foreach (const Symbol &symbol, gfsequence) {
      switch (symbol.symtype) {
        case Symbol::Cat: // category
        case Symbol::Lit: // literal
        case Symbol::Var: // variable
          if (isSuffix) {
            qWarning("ignoring unsupported use of Prelude.Bind (only suffix "
                     "tokens supported)");
            isSuffix = false;
          }
          sequence.append(Term(symbol.n, symbol.l));
          break;
        case Symbol::KS: // string of tokens
          {
            QStringList tokens = symbol.tokens;
            foreach (const QString &token, tokens) {
              if (token == PreludeBind) {
                if (isSuffix)
                  qWarning("ignoring duplicate Prelude.Bind");
                isSuffix = true;
                continue;
              }
              if (isSuffix) {
                typedef QPair<QString, int> Suffix;
                int id = 0;
                foreach (const Suffix &suffix, suffixes) {
                  if (suffix.first == token) {
                    id = suffix.second;
                    break;
                  }
                }
                if (!id) {
                  id = catNames.size();
                  catNames.append(QString(PreludeBind) + ' ' + token);
                  suffixes.append(qMakePair(token, id));
                  pmcfg.tokens.insert(id);
                }
                sequence.append(id);
                isSuffix = false;
              } else {
                /* Some PGF files put '.' at the end of a token, which confuses
                   the lexer. (Those PGF grammars really ought to be fixed!)
                   Work around that. */
                QStringList splitTokens;
                if (token.endsWith('.') && token != ".") {
                  QString choppedToken = token;
                  choppedToken.chop(1);
                  splitTokens.append(choppedToken);
                  splitTokens.append(".");
                } else splitTokens.append(token);
                foreach (const QString &splitToken, splitTokens) {
                  if (tokenHash.contains(splitToken))
                    sequence.append(tokenHash.value(splitToken));
                  else {
                    int id = catNames.size();
                    catNames.append(splitToken);
                    tokenHash.insert(splitToken, id);
                    pmcfg.tokens.insert(id);
                    sequence.append(id);
                  }
                }
              }
            }
          }
          break;
        case Symbol::KP: // pre
          {
            if (isSuffix) {
              qWarning("ignoring unsupported use of Prelude.Bind (only suffix "
                       "tokens supported)");
              isSuffix = false;
            }
            // convert pre to a context-free rule accepting all the alternatives
            // record the information needed to build next token constraints
            QList<QStringList> uniqueAlternatives;
            uniqueAlternatives.append(symbol.tokens);
            QList<PrefixMatch> info;
            typedef QPair<QStringList, QStringList> PreAlternative;
            QList<int> constraintIds;
            foreach (const PreAlternative &alternative, symbol.alternatives) {
              int index = uniqueAlternatives.indexOf(alternative.first);
              if (index > 0) {
                QString &constraintName = catNames[constraintIds[index-1]];
                constraintName.append('|');
                constraintName.append(alternative.second.join("*|"));
                constraintName.append('*');
              } else if (index < 0) {
                index = uniqueAlternatives.size();
                uniqueAlternatives.append(alternative.first);
                constraintIds.append(catNames.size());
                catNames.append(alternative.second.join("*|")+'*');
              }
              foreach (const QString &prefix, alternative.second)
                info.append(qMakePair(prefix, index));
            }
            QStringList uniqueAlternativeNames;
            foreach (const QStringList &uniqueAlternative, uniqueAlternatives)
              uniqueAlternativeNames.append(uniqueAlternative.join(" "));
            QString name = "pre {" + uniqueAlternativeNames.join("; ") + '}';
            int id = catNames.size();
            catNames.append(name);
            QList<Rule> cfRules;
            int index = 0;
            foreach (const QStringList &uniqueAlternative, uniqueAlternatives) {
              Rule rule;
              foreach (const QString &token, uniqueAlternative) {
                if (token == PreludeBind) {
                  qWarning("ignoring unsupported use of Prelude.Bind in pre");
                  continue;
                }
                if (tokenHash.contains(token))
                  rule.append(tokenHash.value(token));
                else {
                  int tokenId = catNames.size();
                  catNames.append(token);
                  tokenHash.insert(token, tokenId);
                  pmcfg.tokens.insert(tokenId);
                  rule.append(tokenId);
                }
              }
              if (index++)
                rule.nextTokenConstraints.expect.append(constraintIds[index-2]);
              cfRules.append(rule);
            }
            pmcfg.cfRules[id] = cfRules;
            sequence.append(id);
            prefixInfo.append(qMakePair(id, info));
          }
          break;
        case Symbol::BIND: // Prelude.BIND (since GF 3.6)
          if (isSuffix)
            qWarning("ignoring duplicate Prelude.Bind");
          isSuffix = true;
          break;
        case Symbol::SOFT_BIND: // Prelude.SOFT_BIND (since GF 3.6)
        case Symbol::SOFT_SPACE: // Prelude.SOFT_SPACE (since GF 3.7)
        case Symbol::CAPIT: // Prelude.CAPIT (since GF 3.7)
        case Symbol::ALL_CAPIT: // Prelude.ALL_CAPIT (since GF 3.7)
          // We have no use for this at the moment. Ignore it.
          break;
        case Symbol::NE: // Prelude.nonExist (since GF 3.6)
          // Generate an unreachable dummy category for non-existing forms.
          // Reuse the same category for all of them.
          if (!nonExistCat) {
            nonExistCat = catNames.size();
            catNames.append("nonExist");
          }
          sequence.append(nonExistCat);
          isSuffix = false;
          break;
        default:
          qFatal("invalid symbol");
      }
    }
    if (isSuffix)
      qWarning("ignoring unsupported use of Prelude.Bind (only suffix tokens "
               "supported)");
    sequences.append(sequence);
  }

  // build next token constraints
  foreach (const PrefixInfo &info, prefixInfo) {
    QList<Rule> &cfRules = pmcfg.cfRules[info.first];
    Rule &defaultRule = cfRules.first();
    int s = cfRules.size();
    QHashIterator<QString, int> it(tokenHash);
    while (it.hasNext()) {
      it.next();
      const QString &token = it.key();
      if (token.startsWith('$') || token.startsWith('`')) {
        // allow any article in front of formulas
        const int &tokenId = it.value();
        for (int i=1; i<s; i++)
          pmcfg.cfRules[cfRules[i].nextTokenConstraints.expect.first()]
            .append(Rule() << tokenId);
      } else {
        int ruleno = 0;
        foreach (const PrefixMatch &prefix, info.second) {
          if (token.startsWith(prefix.first)) {
            ruleno = prefix.second;
            break;
          }
        }
        if (ruleno) {
          const int &tokenId = it.value();
          pmcfg.cfRules[cfRules[ruleno].nextTokenConstraints.expect.first()]
            .append(Rule() << tokenId);
          defaultRule.nextTokenConstraints.taboo.append(tokenId);
        }
      }
    }
  }

  // convert the lindefs to coercion functions
  QHash<QString, int> coercionFunctions;
  {
    QHashIterator<int, QList<int> > it (concrete.lindefs);
    while (it.hasNext()) {
      const QList<int> lindefs = it.next().value();
      if (lindefs.size() != 1) qFatal("expected exactly 1 lindef per category");
      QString cat = catNames.at(it.key() + CAT_OFFSET);
      coercionFunctions.insert(cat, lindefs.first());
    }
  }
  // In format version 1, firstFunction was always concrete.lindefs.size().
  // Format version 2 has one or more corresponding linrefs for every lindef.
  // (Usually one, but in the English resource grammar, verb categories have two
  // linref functions each.) So we have to loop to find the first function.
  int i = 0;
  int numFunctions = concrete.cncfuns.size();
  for (; i<numFunctions; i++) {
    const CncFun &cncfun = concrete.cncfuns.at(i);
    QString name = QString::fromLocal8Bit(cncfun.fun);
    if (!name.startsWith("lindef ")) {
      // We found the first actual function.
      break;
    }
    int dim = cncfun.lins.size();
    Function function;
    for (int j=0; j<dim; j++)
      function.append(Sequence() << Term(0,j));
    pmcfg.functions.append(function);
    functionNames.append(name.replace("lindef ", "coerce "));
  }
  firstFunction = i;

  // convert the functions (actual ones, skip lindefs)
  for (; i<numFunctions; i++) {
    const CncFun &cncfun = concrete.cncfuns.at(i);
    Function function;
    foreach (int lin, cncfun.lins) function.append(sequences.at(lin));
    pmcfg.functions.append(function);
    functionNames.append(QString::fromLocal8Bit(cncfun.fun));
  }

  // convert the productions
  {
    // fill in a map needed for nested coercions
    QHash<int, int> coercions;
    QHashIterator<int, QList<Production> > it (concrete.productions);
    while (it.hasNext()) {
      const QList<Production> productions = it.next().value();
      int lhs = it.key() + CAT_OFFSET;
      foreach (const Production &production, productions)
        if (production.isCoercion) {
          int rhs = production.id + CAT_OFFSET;
          if (!coercions.contains(lhs) || rhs < coercions.value(lhs))
            coercions.insert(lhs, rhs);
        }
    }
    it = concrete.productions;
    while (it.hasNext()) {
      const QList<Production> productions = it.next().value();
      int lhs = it.key() + CAT_OFFSET;
      QList<Rule> &rules = pmcfg.rules[lhs];
      foreach (const Production &production, productions) {
        if (production.isCoercion) {
          int cat = production.id + CAT_OFFSET;
          QString catName = catNames.at(cat);
          // support nested coercions
          while (catName.isEmpty()
                 || catName.endsWith("(coerced)")) {
            if (!coercions.contains(cat))
              qFatal("failed to look up real category for C%d", production.id);
            cat = coercions.value(cat);
            catName = catNames.at(cat);
          }
          QString catNameCoerced = catName + "(coerced)";
          catNames[lhs] = catNameCoerced;
          if (!componentNames.contains(catNameCoerced))
            componentNames.insert(catNameCoerced,
                                  componentNames.value(catName));
          Rule rule(coercionFunctions.value(catName));
          rule.append(cat);
          rules.append(rule);
        } else {
          Rule rule(production.id);
          foreach (PArg parg, production.args)
            rule.append(parg.fid + CAT_OFFSET);
          rules.append(rule);
        }
      }
    }
  }
}

class PgfLexerStateData : public AbstractLexerStateData {
  public:
    virtual AbstractLexerStateData *clone() {
      return new PgfLexerStateData(*this);
    }
    qint64 streamPos;
    bool inFormula;
    bool pastFormula;
    QList<int> suffixes;
};
DYNGENPAR_DECLARE_TYPEINFO(PgfLexerStateData, Q_MOVABLE_TYPE);

class PgfTokenSource : public TokenSource {
  public:
    // The PGF is owned by the parser, so we keep only a pointer in this class.
    PgfTokenSource(Pgf *p)
      : TokenSource(), pgf_p(p), stream(new QFile()), inFormula(false),
        pastFormula(false)
      {static_cast<QFile *>(stream)->open(stdin, QIODevice::ReadOnly);}
    virtual ~PgfTokenSource() {delete stream;}
    // We also require the data to match where there is any.
    virtual bool matchParseTree(const Node &treeToMatch) {
      return (treeToMatch.cat == tree.cat) && (treeToMatch.data == tree.data);
    }
    virtual bool rewindTo(int pos,
                          const LexerState &lexerState = LexerState()) {
      /* Sequential streams cannot be rewound at all.
         For other streams, we need a non-null lexer state to rewind to a
         non-zero position. */
      if (stream->isSequential() || (pos && lexerState.isNull()))
        return TokenSource::rewindTo(pos);
      else if (!pos && currPos) { // rewind to position zero = reset
        stream->reset();
        reset();
        return true;
      } else {
        if (pos != currPos) {
          const PgfLexerStateData *data
            = static_cast<const PgfLexerStateData *>(lexerState.data());
          if (!stream->seek(data->streamPos)) {
            tree = Node();
            return false;
          }
          inFormula = data->inFormula;
          pastFormula = data->pastFormula;
          suffixes = data->suffixes;
        }
        return simpleRewind(pos);
      }
    }
    virtual LexerState saveState() {
      /* We cannot rewind if the stream is sequential, so don't bother saving a
         lexer state in that case. */
      if (stream->isSequential()) return LexerState();
      PgfLexerStateData *data = new PgfLexerStateData;
      data->streamPos = stream->pos();
      data->inFormula = inFormula;
      data->pastFormula = pastFormula;
      data->suffixes = suffixes;
      return LexerState(data);
    }
    void setInputStdin() {
      delete stream;
      stream = new QFile();
      static_cast<QFile *>(stream)->open(stdin, QIODevice::ReadOnly);
      reset();
    }
    void setInputFile(const QString &fileName) {
      delete stream;
      stream = new QFile(fileName);
      stream->open(QIODevice::ReadOnly);
      reset();
    }
    void setInputBytes(const QByteArray &bytes) {
      delete stream;
      stream = new QBuffer();
      static_cast<QBuffer *>(stream)->setData(bytes);
      stream->open(QIODevice::ReadOnly);
      reset();
    }
    void setInputString(const QString &string) {
      setInputBytes(string.toLocal8Bit());
    }
    void setInputBuffer(QByteArray *buffer) {
      delete stream;
      stream = new QBuffer(buffer);
      stream->open(QIODevice::ReadOnly);
      reset();
    }
  protected:
    virtual Cat readToken();
  private:
    void reset() {
      tree = Node();
      currPos = 0;
      inFormula = pastFormula = false;
      suffixes.clear();
    }
    Pgf *pgf_p;
    QIODevice *stream;
    bool inFormula;
    bool pastFormula;
    QList<int> suffixes;
};
DYNGENPAR_DECLARE_TYPEINFO(PgfTokenSource, Q_MOVABLE_TYPE);

static bool isTextChar(char c)
{
  return (c >= 'a' && c <= 'z')
         || (c >= 'A' && c <= 'Z')
         || (c < 0) // non-ASCII UTF-8 characters
         || c == '_' || c == '\'' || c == '\\';
}

Cat PgfTokenSource::readToken()
{
  /* Check for saved suffixes before checking anything else, even the end of the
     stream. The suffixes are already matched from previous stream input, thus
     the input only counts as consumed when the suffixes are consumed. */
  if (!suffixes.isEmpty())
    return suffixes.takeFirst();

  if (stream->atEnd()) return PgfTokenEpsilon; // end of input

  char c;
  QByteArray tokenBytes;

  if (inFormula) {
    while (true) {
      if (stream->atEnd()) break; /* allows incremental parsing and predicting
                                     '$' rather than failing on "unexpected
                                     'LEX_ERROR'" */
      if (!stream->getChar(&c)) return PgfTokenLexError;
      if (c == '$') {
        stream->ungetChar(c);
        break;
      }
      tokenBytes.append(c);
      if (c == '\\') {
        if (stream->atEnd()) break; /* allows incremental parsing and predicting
                                     '$' rather than failing on "unexpected
                                     'LEX_ERROR'" */
        if (!stream->getChar(&c)) return PgfTokenLexError;
        tokenBytes.append(c);
      }
    }
    tree = Node(PgfTokenString);
    tree.data = QString::fromLocal8Bit(tokenBytes.data()).trimmed();
    inFormula = false;
    pastFormula = true;
    return PgfTokenString;
  }

  int state = 0;
  bool continueLoop = true;
  bool isNumber = false;
  while (continueLoop) {
    if (!stream->getChar(&c)) return PgfTokenLexError;
    switch (state) {
      default: // no token yet
        if (std::isspace(c)) {
          if (stream->atEnd()) return PgfTokenEpsilon; // end of input
        } else if (isTextChar(c)
                   || (pastFormula && c == '$')) {
          pastFormula = false;
          tokenBytes.append(c);
          state = 1;
          if (stream->atEnd()) continueLoop = false; // end of input
        } else if (c == '$') {
          inFormula = true;
          tokenBytes.append(c);
          continueLoop = false;
        } else if (c == '-') {
          tokenBytes.append(c);
          state = 2;
          if (stream->atEnd()) continueLoop = false; // end of input
        } else if (c >= '0' && c <= '9') {
          tokenBytes.append(c);
          isNumber = true;
          state = 3;
          if (stream->atEnd()) continueLoop = false; // end of input
        } else {
          tokenBytes.append(c);
          continueLoop = false;
        }
        break;
      case 1: // parsing a word
        if (isTextChar(c) || c == '-' || (c >= '0' && c <= '9')) {
          tokenBytes.append(c);
          if (stream->atEnd()) continueLoop = false; // end of input
        } else {
          stream->ungetChar(c);
          continueLoop = false;
        }
        break;
      case 2: // dash
        if (c == '-') {
          tokenBytes.append(c);
          if (stream->atEnd()) continueLoop = false; // end of input
        } else if (isTextChar(c)) {
          tokenBytes.append(c);
          state = 1;
          if (stream->atEnd()) continueLoop = false; // end of input
        } else if (c >= '0' && c <= '9') {
          tokenBytes.append(c);
          isNumber = true;
          state = 3;
          if (stream->atEnd()) continueLoop = false; // end of input
        } else {
          stream->ungetChar(c);
          continueLoop = false;
        }
        break;
      case 3: // parsing a number
        if ((c >= '0' && c <= '9') || c == 'e' || c == '-') {
          tokenBytes.append(c);
          if (stream->atEnd()) continueLoop = false; // end of input
        } else if (c == '.') { // dot, could be integer + period or float
          if (stream->atEnd()) { // period at end of file, number stops here
            stream->ungetChar(c);
            continueLoop = false;
          } else {
            char c2;
            if (stream->peek(&c2, 1) < 1) return PgfTokenLexError;
            if (c2 >= '0' && c2 <= '9') // float, accept the dot
              tokenBytes.append(c);
            else { // period, number stops here
              stream->ungetChar(c);
              continueLoop = false;
            }
          }
        } else {
          stream->ungetChar(c);
          continueLoop = false;
        }
        break;
    }
  }

  QString tokenString = QString::fromLocal8Bit(tokenBytes.data());
  if (isNumber) {
    if (tokenString.contains('.') || tokenString.contains('e')) { // float
      bool ok;
      double d = tokenString.toDouble(&ok);
      if (!ok) return PgfTokenLexError;
      tree = Node(PgfTokenFloat);
      tree.data = d;
      return PgfTokenFloat;
    } else { // integer
      bool ok;
      int i = tokenString.toInt(&ok);
      if (!ok) return PgfTokenLexError;
      tree = Node(PgfTokenInt);
      tree.data = i;
      return PgfTokenInt;
    }
  } else { // word
    /* default = string (will be returned if the word is not known)
       TODO: Do we want to make this configurable? If a String isn't acceptable
             at this place, we will get a parse error anyway, it will just be an
             unexpected token "String" rather than "LEX_ERROR". But we may
             want/need to support more ways of handling String tokens in the
             future. (For example, what about strings which are also other
             tokens? When do we want to return them as String? Do we use
             prediction information?) */
    int token = PgfTokenString;
    if (pgf_p->tokenHash.contains(tokenString))
      token = pgf_p->tokenHash.value(tokenString);
    else {
      // try lowercasing the first character
      QString tokenStringLower = tokenString;
      tokenStringLower[0] = tokenStringLower[0].toLower();
      if (pgf_p->tokenHash.contains(tokenStringLower))
        token = pgf_p->tokenHash.value(tokenStringLower);
      else { // now try suffixes
        QString tokenStringChopped = tokenString;
        do {
          typedef QPair<QString, int> Suffix;
          bool suffixMatched = false;
          foreach (const Suffix &suffix, pgf_p->suffixes) {
            if (tokenStringChopped.endsWith(suffix.first)) {
              suffixMatched = true;
              suffixes.prepend(suffix.second);
              int suffixLen = suffix.first.size();
              tokenStringChopped.chop(suffixLen);
              tokenStringLower.chop(suffixLen);
              break;
            }
          }
          if (!suffixMatched) break;
          if (tokenStringChopped.isEmpty()) /* can happen during incremental
                                               parsing */
            token = suffixes.takeFirst();
          if (pgf_p->tokenHash.contains(tokenStringChopped))
            token = pgf_p->tokenHash.value(tokenStringChopped);
          else if (pgf_p->tokenHash.contains(tokenStringLower))
            token = pgf_p->tokenHash.value(tokenStringLower);
        } while (token == PgfTokenString);
        if (token == PgfTokenString) {
          /* If we don't know the word, we return it as a String (see TODO
             above). */
          suffixes.clear();
          tree = Node(PgfTokenString);
          tree.data = tokenString;
        }
      }
    }
    return token;
  }
}

PgfParser::PgfParser(const Pgf &p) : Parser(new PgfTokenSource(&pgf)), pgf(p)
{
  init();
}

PgfParser::PgfParser(const QString &fileName, const QString &concreteName)
      : Parser(new PgfTokenSource(&pgf)), pgf(fileName, concreteName)
{
  init();
}

void PgfParser::setInputStdin()
{
  static_cast<PgfTokenSource *>(inputSource)->setInputStdin();
}

void PgfParser::setInputFile(const QString &fileName)
{
  static_cast<PgfTokenSource *>(inputSource)->setInputFile(fileName);
}

void PgfParser::setInputBytes(const QByteArray &bytes)
{
  static_cast<PgfTokenSource *>(inputSource)->setInputBytes(bytes);
}

void PgfParser::setInputString(const QString &string)
{
  static_cast<PgfTokenSource *>(inputSource)->setInputString(string);
}

void PgfParser::setInputBuffer(QByteArray *buffer)
{
  static_cast<PgfTokenSource *>(inputSource)->setInputBuffer(buffer);
}

QString PgfParser::catName(int cat) const
{
  if (cat < 0) { // generated category
    if (pseudoCats.contains(cat)) {
      // pseudo-category, get the effective one
      cat = pseudoCats.value(cat).first;
      if (cat >= 0) return pgf.catNames.at(cat);
    }
    if (componentCats.contains(cat)) {
      QPair<Cat, int> component = componentCats.value(cat);
      QString name = pgf.catNames.at(component.first);
      if (pgf.componentNames.contains(name))
        return QString("%1[%2]").arg(name).arg(pgf.componentNames.value(name)
                                               .at(component.second));
      else
        return QString("%1[%2]").arg(name).arg(component.second);
    } else return QString::number(cat); // unknown generated category
  } else return pgf.catNames.at(cat);
}

void PgfParser::filterCoercionsFromSyntaxTree(Node &tree) const
{
  for (int i=0; i<tree.children.size(); ) {
    const Alternative &child = tree.children.at(i);
    QVariant label = child.label();
    if (label.type() == QVariant::Int && label.toInt() < pgf.firstFunction) {
      tree.children.append(child.first().children);
      tree.children.removeAt(i);
    } else i++;
  }
  int s = tree.children.size();
  for (int i=0; i<s; i++) {
    Alternative &child = tree.children[i];
    int l = child.size();
    for (int j=0; j<l; j++)
      filterCoercionsFromSyntaxTree(child[j]);
  }
}

} // end namespace