DynGenPar
Dynamic Generalized Parser
dyngenpar.h
Go to the documentation of this file.
1 /* DynGenPar: Dynamic Generalized Parser
2  Copyright (C) 2010-2012 Kevin Kofler <kevin.kofler@chello.at>
3  Copyright (C) 2015 DAGOPT Optimization Technologies GmbH
4  written by Kevin Kofler <kofler@dagopt.com>
5 
6  Support by the Austrian Science Fund FWF under contract numbers
7  P20631 and P23554 is gratefully acknowledged.
8 
9  This program is free software: you can redistribute it and/or modify
10  it under the terms of the GNU General Public License as published by
11  the Free Software Foundation, either version 2 of the License, or
12  (at your option) any later version.
13 
14  This program is distributed in the hope that it will be useful,
15  but WITHOUT ANY WARRANTY; without even the implied warranty of
16  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17  GNU General Public License for more details.
18 
19  You should have received a copy of the GNU General Public License
20  along with this program. If not, see <http://www.gnu.org/licenses/>. */
21 
22 // Don't use pragma once here, Qt Jambi doesn't support it.
23 #ifndef DYNGENPAR_H
24 #define DYNGENPAR_H
25 
26 #include <QString>
27 #include <QList>
28 #include <QStringList>
29 #include <QHash>
30 #include <QMultiHash>
31 #include <QSet>
32 #include <QPair>
33 #include <QQueue>
34 #include <QSharedData>
35 #include <QVariant>
36 #include <QVector>
37 #include <QDataStream>
38 
39 #include "priorityqueue.h"
40 
41 // Tell GCC that qFatal does not return.
42 #if defined(__GNUC__) && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ > 4))
43 #define qFatal(x...) (qFatal(x), __builtin_unreachable())
44 #endif
45 
46 // Convenience macro to avoid copying&pasting namespace boilerplate
47 #define DYNGENPAR_DECLARE_TYPEINFO(type, typeclass) \
48  } /* end namespace DynGenPar */ \
49  Q_DECLARE_TYPEINFO(DynGenPar::type, typeclass); \
50  namespace DynGenPar {
51 
52 namespace DynGenPar {
53 
54 // --- general data structures (both context-free grammars and PMCFGs) ---
55 
56 #ifdef DYNGENPAR_INTEGER_CATEGORIES
57 typedef int Cat;
58 #define IS_EPSILON(cat) (!(cat))
59 typedef int CatArg;
60 #else
61 
68 typedef QString Cat;
69 #define IS_EPSILON(cat) ((cat).isNull())
70 
80 typedef const Cat &CatArg;
81 #endif
82 
86 
94 
102  bool operator==(const NextTokenConstraints &other) const {
103  return expect == other.expect && taboo == other.taboo;
104  }
106  QDataStream &writeExternal(QDataStream &stream) const {
107  return stream << expect << taboo;
108  }
110  QDataStream &readExternal(QDataStream &stream) {
111  return stream >> expect >> taboo;
112  }
113 };
114 uint qHash(const NextTokenConstraints &nextTokenConstraints);
115 DYNGENPAR_DECLARE_TYPEINFO(NextTokenConstraints, Q_MOVABLE_TYPE);
116 
118 class Action;
119 } // end namespace
120 
121 inline QDataStream &operator<<(QDataStream &stream,
122  const DynGenPar::Action *data);
123 inline QDataStream &operator>>(QDataStream &stream, DynGenPar::Action *&data);
124 
125 namespace DynGenPar {
126 class Rule : public QList<Cat> {
127  public:
128  static bool serializeLabels;
129  static bool serializeActions;
130  Rule() : QList<Cat>(), action(0) {}
131  explicit Rule(const QVariant &label)
132  : QList<Cat>(), action(0), lbl(label) {}
133  explicit Rule(const QList<Cat> &list)
134  : QList<Cat>(list), action(0), lbl() {}
135  Rule(const QList<Cat> &list, const QVariant &label)
136  : QList<Cat>(list), action(0), lbl(label) {}
137  QVariant label() const {return lbl;}
138  void setLabel(const QVariant &label) {lbl = label;}
141  Rule &operator+=(const QList<Cat> &other) {
142  QList<Cat>::operator+=(other);
143  return *this;
144  }
145  Rule &operator+=(const Cat &value) { // QList always wants a const &
146  QList<Cat>::operator+=(value);
147  return *this;
148  }
149  Rule &operator<<(const QList<Cat> &other) {
150  QList<Cat>::operator<<(other);
151  return *this;
152  }
153  Rule &operator<<(const Cat &value) { // QList always wants a const &
154  QList<Cat>::operator<<(value);
155  return *this;
156  }
158  void add(const Cat &value) { // QList always wants a const &
159  append(value);
160  }
162  QList<Cat> &toList() { return (QList<Cat> &) *this; }
164  QDataStream &writeExternal(QDataStream &stream, bool writeLabel = true,
165  bool writeAction = true) const {
166  return nextTokenConstraints.writeExternal(stream
167  << * (const QList<Cat> *) this
168  << (writeLabel ? lbl
169  : QVariant()))
170  << (writeAction ? action : static_cast<Action *>(0));
171  }
173  QDataStream &readExternal(QDataStream &stream) {
174  return nextTokenConstraints.readExternal(stream >> * (QList<Cat> *) this
175  >> lbl) >> action;
176  }
177 
178  private:
179  QVariant lbl;
180 };
181 DYNGENPAR_DECLARE_TYPEINFO(Rule, Q_MOVABLE_TYPE);
182 
183 typedef QHash<Cat, QList<Rule> > RuleSet;
184 typedef QSet<Cat> TokenSet;
185 
187 
190 struct Cfg {
192  Cfg() : rules(), tokens(), startCat() {}
193  Cfg(const RuleSet &r, const TokenSet &t, CatArg sc)
194  : rules(r), tokens(t), startCat(sc) {}
195  RuleSet rules;
196  TokenSet tokens;
198  bool isToken(CatArg cat) const {return tokens.contains(cat);}
199  void addToken(CatArg cat) {tokens.insert(cat);}
201  QDataStream &writeExternal(QDataStream &stream) const {
202  return stream << rules << tokens << startCat;
203  }
205  QDataStream &readExternal(QDataStream &stream) {
206  return stream >> rules >> tokens >> startCat;
207  }
208 };
209 DYNGENPAR_DECLARE_TYPEINFO(Cfg, Q_MOVABLE_TYPE);
210 
211 typedef QSet<Cat> Predictions;
212 
216  MultiPrediction() : fullLiteral(), cat() {}
217  MultiPrediction(const QList<Cat> &fullLit, CatArg c)
218  : fullLiteral(fullLit), cat(c) {}
221 
223  bool operator==(const MultiPrediction &other) const {
224  return fullLiteral == other.fullLiteral && cat == other.cat;
225  }
226 };
227 DYNGENPAR_DECLARE_TYPEINFO(MultiPrediction, Q_MOVABLE_TYPE);
228 
229 typedef QMultiHash<QList<Cat>, MultiPrediction> MultiPredictions;
230 typedef QMultiHash<Cat, NextTokenConstraints> ConstrainedPredictions;
231 
236  : fullLiteral(), cat(), nextTokenConstraints() {}
238  : fullLiteral(fullLit), cat(c), nextTokenConstraints() {}
241  : fullLiteral(fullLit), cat(c), nextTokenConstraints(ntc) {}
245 
247  bool operator==(const ConstrainedMultiPrediction &other) const {
248  return fullLiteral == other.fullLiteral && cat == other.cat
249  && nextTokenConstraints == other.nextTokenConstraints;
250  }
251 };
252 DYNGENPAR_DECLARE_TYPEINFO(ConstrainedMultiPrediction, Q_MOVABLE_TYPE);
253 
254 typedef QMultiHash<QList<Cat>, ConstrainedMultiPrediction>
256 
258 struct FullRule {
260  FullRule() : cat(), rule(), epsilonsSkipped(0), ruleno(0) {}
261  FullRule(CatArg c, const Rule &r, int epsSkipped, int n)
262  : cat(c), rule(r), epsilonsSkipped(epsSkipped), ruleno(n) {}
267 
269  int ruleno;
270 };
271 DYNGENPAR_DECLARE_TYPEINFO(FullRule, Q_MOVABLE_TYPE);
272 
274 struct Node;
275 class Alternative : public QList<Node> {
276  public:
278  explicit Alternative(const QVariant &label)
279  : QList<DynGenPar::Node>(), lbl(label) {}
280  explicit Alternative(const QList<DynGenPar::Node> &list)
281  : QList<DynGenPar::Node>(list), lbl() {}
282  Alternative(const QList<DynGenPar::Node> &list, const QVariant &label)
283  : QList<DynGenPar::Node>(list), lbl(label) {}
284  QVariant label() const {return lbl;}
285  void setLabel(const QVariant &label) {lbl = label;}
288  return *this;
289  }
292  return *this;
293  }
294  Alternative &operator<<(const QList<DynGenPar::Node> &other) {
296  return *this;
297  }
300  return *this;
301  }
303  void add(const DynGenPar::Node &value) {
304  append(value);
305  }
308  return (QList<DynGenPar::Node> &) *this;
309  }
310 
311  private:
312  QVariant lbl;
313 };
314 DYNGENPAR_DECLARE_TYPEINFO(Alternative, Q_MOVABLE_TYPE);
315 
317 struct Node {
318  Node() {}
319  Node(CatArg c) : cat(c) {children.append(Alternative());}
320  Node(CatArg c, const QVariant &d) : cat(c), data(d) {
321  children.append(Alternative());
322  }
324  QVariant data;
327  bool operator==(const Node &other) const {
328  return cat == other.cat && data == other.data && children == other.children;
329  }
330 };
331 DYNGENPAR_DECLARE_TYPEINFO(Node, Q_MOVABLE_TYPE);
332 
334 class PseudoCatScope;
336  public:
338 
343  QHash<Cat, QPair<QPair<Node, NextTokenConstraints>, int> > pConstraints;
345 
348  QHash<Cat, QPair<int, PseudoCatScope> > mcfgConstraints;
349 };
350 DYNGENPAR_DECLARE_TYPEINFO(PseudoCatScopeData, Q_MOVABLE_TYPE);
351 
353  public:
354  PseudoCatScope() : d() {}
355  QHash<Cat, QPair<QPair<Node, NextTokenConstraints>, int> > &pConstraints() {
356  ensureNonNull();
357  return d->pConstraints;
358  };
359  QHash<Cat, QPair<int, PseudoCatScope> > &mcfgConstraints() {
360  ensureNonNull();
361  return d->mcfgConstraints;
362  };
363  bool hasPConstraint(CatArg cat) const {
364  return d ? d->pConstraints.contains(cat) : false;
365  };
366  bool hasMcfgConstraint(CatArg cat) const {
367  return d ? d->mcfgConstraints.contains(cat) : false;
368  };
369  QPair<QPair<Node, NextTokenConstraints>, int> pConstraint(CatArg cat) const
370  {
371  return d ? d->pConstraints.value(cat)
372  : QPair<QPair<Node, NextTokenConstraints>, int>();
373  };
374  QPair<int, PseudoCatScope> mcfgConstraint(CatArg cat) const {
375  return d ? d->mcfgConstraints.value(cat) : QPair<int, PseudoCatScope>();
376  };
377  bool isNull() const { return !d.constData(); }
379  const PseudoCatScopeData *data() const { return d.constData(); }
380  bool operator==(const PseudoCatScope &other) const { return d == other.d; }
381  private:
382  QSharedDataPointer<PseudoCatScopeData> d;
383  void ensureNonNull() {
384  if (!d.constData()) d = new PseudoCatScopeData;
385  }
386 };
387 DYNGENPAR_DECLARE_TYPEINFO(PseudoCatScope, Q_MOVABLE_TYPE);
388 
389 inline uint qHash(const PseudoCatScope &scope) {
390  return qHash(scope.data());
391 }
392 
394 struct Match {
396  Match() : len(0), tree(), ruleno(0), scope(), nextTokenConstraints() {}
397  Match(int l, Node t, int n, PseudoCatScope s)
398  : len(l), tree(t), ruleno(n), scope(s), nextTokenConstraints() {}
399  Match(int l, Node t, int n, PseudoCatScope s, const NextTokenConstraints &nt)
400  : len(l), tree(t), ruleno(n), scope(s), nextTokenConstraints(nt) {}
401  int len;
403  int ruleno;
404 
407 };
408 DYNGENPAR_DECLARE_TYPEINFO(Match, Q_MOVABLE_TYPE);
409 
411 struct ActionInfo {
413  ActionInfo() : tree() {}
414  ActionInfo(const Node &t) : tree(t) {}
416 };
417 DYNGENPAR_DECLARE_TYPEINFO(ActionInfo, Q_MOVABLE_TYPE);
418 
421  public:
422  virtual ~ActionDeserializer() {}
423  virtual Action *readAction(QDataStream &) = 0;
424 };
425 DYNGENPAR_DECLARE_TYPEINFO(ActionDeserializer, Q_MOVABLE_TYPE);
426 
428 class Action {
429  private:
430  static QHash<QString, ActionDeserializer *> deserializers;
431  protected:
432  static void registerDeserializer(const QString &name,
433  ActionDeserializer *deserializer) {
434  deserializers.insert(name, deserializer);
435  }
436  public:
437  virtual ~Action() {}
438  virtual void execute(const ActionInfo &info) = 0;
440  virtual void writeExternal(QDataStream &stream) const {
441  qWarning("action not serializable");
442  stream << QString();
443  }
445  static QDataStream &constructAndRead(QDataStream &stream, Action *&data) {
446  QString type;
447  stream >> type;
448  if (type.isEmpty()) {
449  data = 0;
450  return stream;
451  } else if (deserializers.contains(type)) {
452  data = deserializers.value(type)->readAction(stream);
453  return stream;
454  } else qFatal("action deserializer \"%s\" not found",
455  type.toLocal8Bit().data());
456  }
457 };
458 DYNGENPAR_DECLARE_TYPEINFO(Action, Q_MOVABLE_TYPE);
459 
460 
461 // --- data structures for DAG-structured parse stacks ---
462 
464 class StackItem;
465 class StackItemData : public QSharedData {
466  public:
467  StackItemData(int depth) : m_depth(depth) {}
468  virtual ~StackItemData() {}
469  virtual StackItemData *clone() = 0;
470  virtual int type() const = 0;
471  int depth() const {return m_depth;}
472  virtual void addParent(const StackItem &parent) = 0;
473  virtual void setParents(const QList<StackItem> &parents) = 0;
474  protected:
475  int m_depth;
476 };
477 DYNGENPAR_DECLARE_TYPEINFO(StackItemData, Q_MOVABLE_TYPE);
478 
479 class StackItem {
480  public:
481  StackItem() : d() {}
482  StackItem(const QList<StackItem> &parents, CatArg cat, CatArg effCat,
483  int pos, const PseudoCatScope &scope);
484  StackItem(const QList<StackItem> &parents, CatArg cat, CatArg effCat,
485  const PseudoCatScope &scope);
486  StackItem(const StackItem &parent, int dummy);
487  StackItem(const StackItem &parent, const Rule &rule, int len, int curr,
488  int i, const Node &tree, int ruleno,
489  const NextTokenConstraints &nextTokenConstraints);
490  StackItem(const StackItem &parent, CatArg target, int pos, int len);
492  StackItem(const StackItem &parent, CatArg cat,
493  const PseudoCatScope &scope);
494  StackItem(const StackItem &parent, const QList<Node> &leaves, int i,
495  const Node &tree, const PseudoCatScope &scope,
496  const NextTokenConstraints &nextTokenConstraints);
497  int type() const {return d ? d->type() : -1;}
498  int depth() const {return d ? d->depth() : -1;}
499  void addParent(const StackItem &parent) {d->addParent(parent);}
500  void setParents(const QList<StackItem> &parents) {d->setParents(parents);}
501  const StackItemData *data() const {return d.constData();}
502  bool operator<(const StackItem &other) const {
503  return depth() < other.depth();
504  }
505  private:
506  QSharedDataPointer<StackItemData> d;
507 };
508 DYNGENPAR_DECLARE_TYPEINFO(StackItem, Q_MOVABLE_TYPE);
509 
512  public:
513  StackItemType0(const QList<StackItem> &parents, CatArg cat, CatArg effCat,
514  int pos, const PseudoCatScope &scope)
515  : StackItemData(0), m_parents(parents), m_cat(cat), m_effCat(effCat),
516  m_pos(pos), m_scope(scope) {
517  foreach(const StackItem &parent, parents) {
518  int newDepth = parent.depth() + 1;
519  if (m_depth < newDepth) m_depth = newDepth;
520  }
521  }
522  virtual ~StackItemType0() {}
523  virtual StackItemData *clone() {return new StackItemType0(*this);}
524  virtual int type() const {return 0;}
525  virtual void addParent(const StackItem &parent) {
526  m_parents.append(parent);
527  int newDepth = parent.depth() + 1;
528  if (m_depth < newDepth) m_depth = newDepth;
529  }
530  virtual void setParents(const QList<StackItem> &parents) {
531  m_parents = parents;
532  m_depth = 0;
533  foreach(const StackItem &parent, parents) {
534  int newDepth = parent.depth() + 1;
535  if (m_depth < newDepth) m_depth = newDepth;
536  }
537  }
538  const QList<StackItem> &parents() const {return m_parents;}
539  Cat cat() const {return m_cat;}
540  Cat effCat() const {return m_effCat;}
541  int pos() const {return m_pos;}
542  PseudoCatScope scope() const {return m_scope;}
543  private:
544  QList<StackItem> m_parents;
545  Cat m_cat, m_effCat;
546  int m_pos;
547  PseudoCatScope m_scope;
548 };
549 DYNGENPAR_DECLARE_TYPEINFO(StackItemType0, Q_MOVABLE_TYPE);
550 
553  public:
554  StackItemType1(const QList<StackItem> &parents, CatArg cat, CatArg effCat,
555  const PseudoCatScope &scope) :
556  StackItemData(0), m_parents(parents), m_cat(cat), m_effCat(effCat),
557  m_scope(scope) {
558  foreach(const StackItem &parent, parents) {
559  int newDepth = parent.depth() + 1;
560  if (m_depth < newDepth) m_depth = newDepth;
561  }
562  }
563  virtual ~StackItemType1() {}
564  virtual StackItemData *clone() {return new StackItemType1(*this);}
565  virtual int type() const {return 1;}
566  virtual void addParent(const StackItem &) {
567  // this could be allowed, but is not needed anywhere, so detect misuse
568  qFatal("cannot call addParent on type 1 item");
569  }
570  virtual void setParents(const QList<StackItem> &) {
571  // this could be allowed, but is not needed anywhere, so detect misuse
572  qFatal("cannot call setParents on type 1 item");
573  }
574  const QList<StackItem> &parents() const {return m_parents;}
575  Cat cat() const {return m_cat;}
576  Cat effCat() const {return m_effCat;}
577  PseudoCatScope scope() const {return m_scope;}
578  private:
579  QList<StackItem> m_parents;
580  Cat m_cat, m_effCat;
581  PseudoCatScope m_scope;
582 };
583 DYNGENPAR_DECLARE_TYPEINFO(StackItemType1, Q_MOVABLE_TYPE);
584 
586 
588  public:
589  StackItemType2(const StackItem &parent) : StackItemData(parent.depth() + 1),
590  m_parent(parent) {}
591  virtual ~StackItemType2() {}
592  virtual StackItemData *clone() {return new StackItemType2(*this);}
593  virtual int type() const {return 2;}
594  virtual void addParent(const StackItem &) {
595  qFatal("cannot call addParent on type 2 item");
596  }
597  virtual void setParents(const QList<StackItem> &) {
598  qFatal("cannot call setParents on type 2 item");
599  }
600  const StackItem &parent() const {return m_parent;}
601  private:
602  StackItem m_parent;
603 };
604 DYNGENPAR_DECLARE_TYPEINFO(StackItemType2, Q_MOVABLE_TYPE);
605 
608  public:
609  StackItemType3(const StackItem &parent, const Rule &rule, int len, int curr,
610  int i, const Node &tree, int ruleno,
611  const NextTokenConstraints &nextTokenConstraints)
612  : StackItemData(parent.depth() + 1), m_parent(parent), m_rule(rule),
613  m_len(len), m_curr(curr), m_i(i), m_tree(tree), m_ruleno(ruleno),
614  m_nextTokenConstraints(nextTokenConstraints) {}
615  virtual ~StackItemType3() {}
616  virtual StackItemData *clone() {return new StackItemType3(*this);}
617  virtual int type() const {return 3;}
618  virtual void addParent(const StackItem &) {
619  qFatal("cannot call addParent on type 3 item");
620  }
621  virtual void setParents(const QList<StackItem> &) {
622  qFatal("cannot call setParents on type 3 item");
623  }
624  const StackItem &parent() const {return m_parent;}
625  Rule rule() const {return m_rule;}
626  int len() const {return m_len;}
627  int curr() const {return m_curr;}
628  int i() const {return m_i;}
629  Node tree() const {return m_tree;}
630  int ruleno() const {return m_ruleno;}
632  return m_nextTokenConstraints;
633  }
634  private:
635  StackItem m_parent;
636  Rule m_rule;
637  int m_len, m_curr, m_i;
638  Node m_tree;
639  int m_ruleno;
640  NextTokenConstraints m_nextTokenConstraints;
641 };
642 DYNGENPAR_DECLARE_TYPEINFO(StackItemType3, Q_MOVABLE_TYPE);
643 
645 
647  public:
648  StackItemType4(const StackItem &parent, CatArg target, int pos, int len)
649  : StackItemData(parent.depth() + 1), m_parent(parent), m_target(target),
650  m_pos(pos), m_len(len) {}
651  virtual ~StackItemType4() {}
652  virtual StackItemData *clone() {return new StackItemType4(*this);}
653  virtual int type() const {return 4;}
654  virtual void addParent(const StackItem &) {
655  qFatal("cannot call addParent on type 4 item");
656  }
657  virtual void setParents(const QList<StackItem> &) {
658  qFatal("cannot call setParents on type 4 item");
659  }
660  const StackItem &parent() const {return m_parent;}
661  Cat target() const {return m_target;}
662  int pos() const {return m_pos;}
663  int len() const {return m_len;}
664  private:
665  StackItem m_parent;
666  Cat m_target;
667  int m_pos, m_len;
668 };
669 DYNGENPAR_DECLARE_TYPEINFO(StackItemType4, Q_MOVABLE_TYPE);
670 
674  public:
675  StackItemType5(const StackItem &parent, CatArg cat,
676  const PseudoCatScope &scope)
677  : StackItemData(parent.depth() + 1), m_parent(parent), m_cat(cat),
678  m_scope(scope) {}
679  virtual ~StackItemType5() {}
680  virtual StackItemData *clone() {return new StackItemType5(*this);}
681  virtual int type() const {return 5;}
682  virtual void addParent(const StackItem &) {
683  qFatal("cannot call addParent on type 5 item");
684  }
685  virtual void setParents(const QList<StackItem> &) {
686  qFatal("cannot call setParents on type 5 item");
687  }
688  const StackItem &parent() const {return m_parent;}
689  Cat cat() const {return m_cat;}
690  PseudoCatScope scope() const {return m_scope;}
691  private:
692  StackItem m_parent;
693  Cat m_cat;
694  PseudoCatScope m_scope;
695 };
696 DYNGENPAR_DECLARE_TYPEINFO(StackItemType5, Q_MOVABLE_TYPE);
697 
700  public:
701  StackItemType6(const StackItem &parent, const QList<Node> &leaves, int i,
702  const Node &tree, const PseudoCatScope &scope,
703  const NextTokenConstraints &nextTokenConstraints)
704  : StackItemData(parent.depth() + 1), m_parent(parent), m_leaves(leaves),
705  m_i(i), m_tree(tree), m_scope(scope),
706  m_nextTokenConstraints(nextTokenConstraints) {}
707  virtual ~StackItemType6() {}
708  virtual StackItemData *clone() {return new StackItemType6(*this);}
709  virtual int type() const {return 6;}
710  virtual void addParent(const StackItem &) {
711  qFatal("cannot call addParent on type 6 item");
712  }
713  virtual void setParents(const QList<StackItem> &) {
714  qFatal("cannot call setParents on type 6 item");
715  }
716  const StackItem &parent() const {return m_parent;}
717  QList<Node> leaves() const {return m_leaves;}
718  int i() const {return m_i;}
719  Node tree() const {return m_tree;}
720  PseudoCatScope scope() const {return m_scope;}
722  return m_nextTokenConstraints;
723  }
724  private:
725  StackItem m_parent;
726  QList<Node> m_leaves;
727  int m_i;
728  Node m_tree;
729  PseudoCatScope m_scope;
730  NextTokenConstraints m_nextTokenConstraints;
731 };
732 DYNGENPAR_DECLARE_TYPEINFO(StackItemType6, Q_MOVABLE_TYPE);
733 
734 inline StackItem::StackItem(const QList<StackItem> &parents, CatArg cat,
735  CatArg effCat, int pos,
736  const PseudoCatScope &scope)
737 {
738  d = new StackItemType0(parents, cat, effCat, pos, scope);
739 }
740 
741 inline StackItem::StackItem(const QList<StackItem> &parents, CatArg cat,
742  CatArg effCat, const PseudoCatScope &scope)
743 {
744  d = new StackItemType1(parents, cat, effCat, scope);
745 }
746 
747 inline StackItem::StackItem(const StackItem &parent, int)
748 {
749  d = new StackItemType2(parent);
750 }
751 
752 inline StackItem::StackItem(const StackItem &parent, const Rule &rule, int len,
753  int curr, int i, const Node &tree, int ruleno,
754  const NextTokenConstraints &nextTokenConstraints)
755 {
756  d = new StackItemType3(parent, rule, len, curr, i, tree, ruleno,
757  nextTokenConstraints);
758 }
759 
760 inline StackItem::StackItem(const StackItem &parent, CatArg target, int pos,
761  int len)
762 {
763  d = new StackItemType4(parent, target, pos, len);
764 }
765 
766 inline StackItem::StackItem(const StackItem &parent, CatArg cat,
767  const PseudoCatScope &scope)
768 {
769  d = new StackItemType5(parent, cat, scope);
770 }
771 
772 inline StackItem::StackItem(const StackItem &parent, const QList<Node> &leaves,
773  int i, const Node &tree,
774  const PseudoCatScope &scope,
775  const NextTokenConstraints &nextTokenConstraints)
776 {
777  d = new StackItemType6(parent, leaves, i, tree, scope, nextTokenConstraints);
778 }
779 
780 
781 // --- token source abstraction ---
782 
785  public:
787  virtual AbstractLexerStateData *clone() = 0;
788 };
789 DYNGENPAR_DECLARE_TYPEINFO(AbstractLexerStateData, Q_MOVABLE_TYPE);
790 
791 class LexerState {
792  public:
793  LexerState() : d() {}
794  LexerState(AbstractLexerStateData *data) : d(data) {}
795  void clear() { d = 0; }
796  bool isNull() const { return !d.constData(); }
797  const AbstractLexerStateData *data() const { return d.constData(); }
798  bool operator==(const LexerState &other) const { return d == other.d; }
799  private:
800  QSharedDataPointer<AbstractLexerStateData> d;
801 };
802 DYNGENPAR_DECLARE_TYPEINFO(LexerState, Q_MOVABLE_TYPE);
803 
804 class TokenSource {
805  public:
806  TokenSource() : currPos(0) {}
807  virtual ~TokenSource() {}
810 
814  tree = Node();
815  Cat result = readToken();
816  if (!IS_EPSILON(result)) {
817  // If the implementation of readToken didn't create a parse tree, create
818  // the default one: a leaf node.
819  if (tree.children.isEmpty()) tree = Node(result);
820  currPos++;
821  }
822  return result;
823  }
826  return tree;
827  }
829 
836  virtual bool matchParseTree(const Node &treeToMatch) {
837  return treeToMatch.cat == tree.cat;
838  }
840  int currentPosition() {return currPos;}
842 
853  virtual bool rewindTo(int pos, const LexerState & = LexerState()) {
854  tree = Node();
855  return (pos == currPos);
856  }
858  virtual LexerState saveState() {return LexerState();}
859  protected:
861  virtual Cat readToken() = 0;
863 
864  bool simpleRewind(int pos, bool rewindOnly = false) {
865  tree = Node(); // destroy saved parse tree
866  if (rewindOnly && pos > currPos) // cannot rewind forward
867  return false;
868  currPos = pos;
869  return true;
870  }
871  int currPos;
873 
880 };
881 DYNGENPAR_DECLARE_TYPEINFO(TokenSource, Q_MOVABLE_TYPE);
882 
883 class ListTokenSource : public TokenSource {
884  public:
886  virtual ~ListTokenSource() {}
889  virtual bool rewindTo(int pos, const LexerState & = LexerState()) {
890  return simpleRewind(pos);
891  }
892  protected:
894  virtual Cat readToken() {
895  if (currPos < inputTokens.size())
896  return inputTokens.at(currPos);
897  return Cat();
898  }
899 };
900 DYNGENPAR_DECLARE_TYPEINFO(ListTokenSource, Q_MOVABLE_TYPE);
901 
903 
906 struct TextPosition {
907  TextPosition() : line(0), col(0) {}
908  TextPosition(int l, int c) : line(l), col(c) {}
909 
910  void reset() { line = col = 0; }
911 
913  void countCharacter(unsigned char c) {
914  // ignore CR
915  if (c == '\r') return;
916 
917  if (c == '\n') { // LF
918  line++;
919  col = 0;
920  } else col++; // horizontal character
921  }
922 
923  int line;
924  int col;
925 };
926 DYNGENPAR_DECLARE_TYPEINFO(TextPosition, Q_PRIMITIVE_TYPE);
927 
928 
929 // --- data structures for PMCFGs (in standard representation) ---
930 
932 struct Term {
934  Term() : arg(-1), component(0), token() {}
935  Term(int a, int c) : arg(a), component(c), token() {}
936  Term(CatArg t) : arg(-1), component(0), token(t) {}
937  int arg, component;
942  bool isComponent() const {return arg >= 0;}
943  bool isToken() const {return arg < 0;}
945  bool operator==(const Term &other) const {
946  return arg == other.arg && component == other.component
947  && token == other.token;
948  }
949 };
950 DYNGENPAR_DECLARE_TYPEINFO(Term, Q_MOVABLE_TYPE);
951 
953 class Sequence : public QList<Term> {
954  public:
956 
957  Sequence() : QList<Term>(), nextTokenConstraints() {}
958  explicit Sequence(const NextTokenConstraints &ntc)
959  : QList<Term>(), nextTokenConstraints(ntc) {}
960  explicit Sequence(const QList<Term> &list)
961  : QList<Term>(list), nextTokenConstraints() {}
962  Sequence(const QList<Term> &list, const NextTokenConstraints &ntc)
963  : QList<Term>(list), nextTokenConstraints(ntc) {}
964  Sequence &operator+=(const QList<Term> &other) {
966  return *this;
967  }
968  Sequence &operator+=(const Term &value) {
970  return *this;
971  }
972  Sequence &operator<<(const QList<Term> &other) {
974  return *this;
975  }
976  Sequence &operator<<(const Term &value) {
978  return *this;
979  }
981  void add(const Term &value) {
982  append(value);
983  }
986  return (QList<Term> &) *this;
987  }
988 };
989 DYNGENPAR_DECLARE_TYPEINFO(Sequence, Q_MOVABLE_TYPE);
990 
992 class Function: public QList<Sequence> {
993  public:
995  explicit Function(const QList<Sequence> &list) : QList<Sequence>(list) {}
998  return *this;
999  }
1000  Function &operator+=(const Sequence &value) {
1002  return *this;
1003  }
1004  Function &operator<<(const QList<Sequence> &other) {
1006  return *this;
1007  }
1008  Function &operator<<(const Sequence &value) {
1010  return *this;
1011  }
1013  void add(const Sequence &value) {
1014  append(value);
1015  }
1018  return (QList<Sequence> &) *this;
1019  }
1020 };
1021 DYNGENPAR_DECLARE_TYPEINFO(Function, Q_MOVABLE_TYPE);
1022 
1024 struct Pmcfg {
1026 
1027 
1033 
1050  RuleSet rules;
1052 
1053  TokenSet tokens;
1055 
1058 
1065  RuleSet cfRules;
1067 
1069 
1070  QHash<int, QString> functionNames;
1071  QHash<QString, int> functionIndices;
1072  void addFunction(const QString &name, const Function &function) {
1073  int index = functions.size();
1074  functions.append(function);
1075  functionNames.insert(index, name);
1076  functionIndices.insert(name, index);
1077  }
1078  Function lookupFunction(const QVariant &id) const {
1079  if (id.type() == QVariant::Int) return functions.at(id.toInt());
1080 
1081  QString name = id.toString();
1082  if (!functionIndices.contains(name)) return Function();
1083  return functions.at(functionIndices.value(name));
1084  }
1086 };
1087 DYNGENPAR_DECLARE_TYPEINFO(Pmcfg, Q_MOVABLE_TYPE);
1088 
1093  : pmcfgRule(rule), argPositions(rule.size()) {}
1095  QVector<QVector<int> > argPositions;
1099 };
1100 DYNGENPAR_DECLARE_TYPEINFO(PmcfgComponentInfo, Q_MOVABLE_TYPE);
1101 
1102 Node parseTreeToPmcfgSyntaxTree(const Node &parseTree);
1103 
1104 
1105 // --- parse state struct, for bindings ---
1106 
1108 struct ParseState {
1110  : errorPos(-1), errorToken(), incrementalPos(-1), incrementalStacks(),
1111  incrementalMatches(), lexerState() {}
1112  // explicitly implement the default copy constructor to get it bound
1113  ParseState(const ParseState &other)
1114  : errorPos(other.errorPos), errorToken(other.errorToken),
1115  incrementalPos(other.incrementalPos),
1116  incrementalStacks(other.incrementalStacks),
1117  incrementalMatches(other.incrementalMatches), lexerState(other.lexerState)
1118  {}
1119 
1126 
1127  void reset() { *this = ParseState(); }
1128 };
1129 DYNGENPAR_DECLARE_TYPEINFO(ParseState, Q_MOVABLE_TYPE);
1130 
1131 
1132 // --- main class ---
1133 
1135 class Parser {
1136  public:
1137  // interface methods
1138  Parser(TokenSource *tokenSource)
1139  : inputSource(tokenSource), lastGeneratedCat(0) {}
1140  virtual ~Parser() {}
1141  bool isToken(CatArg cat) const {return tokens.contains(cat);}
1142  void addToken(CatArg cat) {tokens.insert(cat);}
1143  bool isLiteral(const QList<Cat> &list) const;
1144  void initCaches();
1145  void addRule(CatArg cat, const Rule &rule);
1146  void loadCfg(const Cfg &cfg) {
1147  rules = cfg.rules;
1148  tokens = cfg.tokens;
1149  startCat = cfg.startCat;
1150  initCaches();
1151  }
1153  Cfg getCfg() {return Cfg(rules, tokens, startCat);}
1154  bool loadPmcfg(const Pmcfg &pmcfg);
1155  bool addPmcfgRule(Pmcfg &pmcfg, CatArg cat, const Rule &rule);
1156  QList<Match> parse(int *errorPos = 0, Cat *errorToken = 0,
1157  int *incrementalPos = 0,
1158  QList<StackItem> *incrementalStacks = 0,
1159  QList<Match> *incrementalMatches = 0,
1160  LexerState *lexerState = 0);
1163  return parse(&parseState->errorPos, &parseState->errorToken,
1164  &parseState->incrementalPos, &parseState->incrementalStacks,
1165  &parseState->incrementalMatches, &parseState->lexerState);
1166  }
1167  Predictions computePredictions(const QList<StackItem> &stacks) const;
1169  Predictions computePredictions(const ParseState &parseState) const {
1170  return computePredictions(parseState.incrementalStacks);
1171  }
1172  QHash<Cat, QSet<Cat> > expandNonterminalPrediction(CatArg cat) const;
1173  QHash<Cat, QSet<Cat> > expandNonterminalPredictionC(CatArg cat);
1174  MultiPredictions computeMultiPredictions(const QList<StackItem> &stacks)
1175  const;
1177  MultiPredictions computeMultiPredictions(const ParseState &parseState) const
1178  {
1179  return computeMultiPredictions(parseState.incrementalStacks);
1180  }
1181  QHash<Cat, QSet<QList<Cat> > >
1182  expandNonterminalPredictionMulti(CatArg cat) const;
1183  QHash<Cat, QSet<QList<Cat> > >
1184  expandNonterminalPredictionMultiC(CatArg cat);
1185  ConstrainedPredictions computeConstrainedPredictions(
1186  const QList<StackItem> &stacks) const;
1188  ConstrainedPredictions computeConstrainedPredictions(
1189  const ParseState &parseState) const {
1190  return computeConstrainedPredictions(parseState.incrementalStacks);
1191  }
1192  QHash<Cat, QSet<Cat> > expandNonterminalPredictionC(CatArg cat,
1193  const NextTokenConstraints &nextTokenConstraints);
1194  QHash<Cat, QSet<Cat> > expandNonterminalPredictionC(CatArg cat,
1195  const QList<NextTokenConstraints> &nextTokenConstraintsList);
1196  ConstrainedMultiPredictions computeConstrainedMultiPredictions(
1197  const QList<StackItem> &stacks) const;
1200  const ParseState &parseState) const
1201  {
1202  return computeConstrainedMultiPredictions(parseState.incrementalStacks);
1203  }
1204  QHash<Cat, QSet<QList<Cat> > >
1205  expandNonterminalPredictionMultiC(CatArg cat,
1206  const NextTokenConstraints &nextTokenConstraints);
1207  QHash<Cat, QSet<QList<Cat> > >
1208  expandNonterminalPredictionMultiC(CatArg cat,
1209  const QList<NextTokenConstraints> &nextTokenConstraintsList);
1210 
1212 
1213 
1217  RuleSet rules;
1219  TokenSet tokens;
1223 
1225 
1226 
1247  QHash<Cat, QPair<Cat, QList<Cat> > > pseudoCats;
1250 
1253  QHash<Cat, QPair<Cat, int> > componentCats;
1255 
1259  QHash<Cat, QList<Cat> > catComponents;
1261 
1262  protected:
1265 
1266  private:
1267  // helper methods
1268  Cat effectiveCat(CatArg cat) const;
1269  void processRule(CatArg cat, const Rule &rule, int skip, int ruleno,
1270  QQueue<Cat> &nullableQueue, bool &clearEpsilonMatches);
1271  bool computePmcfgDimension(CatArg cat, const Rule &rule,
1272  const Pmcfg &pmcfg);
1273  bool convertPmcfgRule(CatArg cat, const Rule &rule, const Pmcfg &pmcfg,
1274  bool updateCaches);
1275  bool reachable(CatArg cat, CatArg target, QSet<Cat> mark);
1276  QList<FullRule> neighborhood(CatArg cat, CatArg target);
1277  void finalizeMatches(QList<Match> &matches, CatArg cat,
1278  const PseudoCatScope &scope);
1279  void copyScope(QList<Match> &matches, const PseudoCatScope &scope);
1280  QList<Match> matchCFToEpsilon(CatArg cat, QSet<Cat> mark);
1281  QList<Match> matchEffectiveCatToEpsilon(CatArg cat, QSet<Cat> mark);
1282  QList<Match> matchToEpsilonRecurse(CatArg cat, QSet<Cat> mark,
1283  const PseudoCatScope &scope);
1284  QList<Match> matchToEpsilon(CatArg cat, const PseudoCatScope &scope);
1285  bool matchesTokenRecurse(CatArg cat, CatArg token, QSet<Cat> mark) const;
1286  bool matchesToken(CatArg cat, CatArg token) const;
1287  void collectLeaves(const Node &tree, QList<Node> &leaves);
1288  bool validateNextTokenConstraints(CatArg token,
1289  const NextTokenConstraints &nextTokenConstraints) const;
1290  QList<Match> match(CatArg cat, int pos, const PseudoCatScope &scope,
1291  const StackItem &stack,
1292  const NextTokenConstraints &nextTokenConstraints);
1293  QList<Match> matchRemaining(const Rule &rule, int len, int curr, int i,
1294  const Node &tree, const PseudoCatScope &scope,
1295  int ruleno, const StackItem &stack,
1296  const NextTokenConstraints
1297  &nextTokenConstraints);
1298  Cat findFirstToken(const Node &tree);
1299  void unify(QList<Match> &matches);
1300  QList<Match> reduce(CatArg cat, CatArg target, int pos, int len,
1301  const Node &tree, const StackItem &stack,
1302  const PseudoCatScope &scope, int ruleno,
1303  const NextTokenConstraints &nextTokenConstraints,
1304  QSet<Cat> mark = QSet<Cat>());
1305  QList<Match> processStackItem(const StackItem &item,
1306  const QList<Match> &matches);
1307  QList<Match> processStack(const StackItem &stack, CatArg token);
1308  bool shift(int pos);
1309  void expandNonterminalPredictionRecurse(CatArg cat,
1310  QHash<Cat, QSet<Cat> > &result,
1311  QSet<Cat> &mark) const;
1312  void expandNonterminalPredictionRecurseC(CatArg cat,
1313  QHash<Cat, QSet<Cat> > &result,
1314  QSet<Cat> mark, int ruleno,
1315  const PseudoCatScope &scope,
1316  const NextTokenConstraints
1317  &nextTokenConstraints);
1318  void expandNonterminalPredictionMultiRecurse(CatArg cat,
1319  QHash<Cat, QSet<QList<Cat> > > &result, QSet<Cat> &mark) const;
1320  void expandNonterminalPredictionMultiRecurseC(CatArg cat,
1321  QHash<Cat, QSet<QList<Cat> > > &result, QSet<Cat> mark, int ruleno,
1322  const PseudoCatScope &scope,
1323  const NextTokenConstraints &nextTokenConstraints);
1324  int generateCat() { return --lastGeneratedCat; }
1325 
1327  QMultiHash<Cat, FullRule> initialGraph;
1329  QHash<QPair<Cat, Cat>, QList<FullRule> > neighborhoods;
1331  QSet<Cat> nullable;
1333  QHash<Cat, QList<Match> > epsilonMatches;
1334 
1336  QList<StackItem> nextStacks;
1338  QList<Match> currentMatches;
1340  LexerState currentLexerState;
1342  QHash<Cat, int> type0Indices;
1344 
1351  QHash<const StackItemData *, QPair<bool, QList<Match> > > collectedMatches;
1353  Private::PriorityQueue<StackItem> priorityQueue;
1355 
1356  bool branched;
1358  int errPos;
1360  Cat errToken;
1362  int lastGeneratedCat;
1363 };
1364 DYNGENPAR_DECLARE_TYPEINFO(Parser, Q_MOVABLE_TYPE);
1365 
1366 } // end namespace
1367 
1368 
1369 // --- utility functions in the global namespace ---
1370 
1371 Q_DECLARE_METATYPE(DynGenPar::PmcfgComponentInfo)
1372 
1373 uint qHash(const QList<DynGenPar::Cat> &list);
1374 
1375 template<>
1377  *QSharedDataPointer<DynGenPar::StackItemData>::clone()
1378 {
1379  return d->clone();
1380 }
1381 
1382 template<>
1384  *QSharedDataPointer<DynGenPar::AbstractLexerStateData>::clone()
1385 {
1386  return d->clone();
1387 }
1388 
1389 inline QDataStream &operator<<(QDataStream &stream,
1390  const DynGenPar::NextTokenConstraints &data) {
1391  return data.writeExternal(stream);
1392 }
1393 
1394 inline QDataStream &operator>>(QDataStream &stream,
1396  return data.readExternal(stream);
1397 }
1398 
1399 inline QDataStream &operator<<(QDataStream &stream,
1400  const DynGenPar::Rule &data) {
1401  return data.writeExternal(stream, DynGenPar::Rule::serializeLabels,
1403 }
1404 
1405 inline QDataStream &operator>>(QDataStream &stream, DynGenPar::Rule &data) {
1406  return data.readExternal(stream);
1407 }
1408 
1409 inline QDataStream &operator<<(QDataStream &stream,
1410  const DynGenPar::Cfg &data) {
1411  return data.writeExternal(stream);
1412 }
1413 
1414 inline QDataStream &operator>>(QDataStream &stream, DynGenPar::Cfg &data) {
1415  return data.readExternal(stream);
1416 }
1417 
1418 inline QDataStream &operator<<(QDataStream &stream,
1419  const DynGenPar::Action *data) {
1420  if (data) {
1421  data->writeExternal(stream);
1422  return stream;
1423  } else return stream << QString();
1424 }
1425 
1426 inline QDataStream &operator>>(QDataStream &stream, DynGenPar::Action *&data) {
1427  return DynGenPar::Action::constructAndRead(stream, data);
1428 }
1429 
1430 #endif // DYNGENPAR_H
const StackItem & parent() const
Definition: dyngenpar.h:716
ParseState(const ParseState &other)
Definition: dyngenpar.h:1113
const AbstractLexerStateData * data() const
Definition: dyngenpar.h:797
MultiPredictions computeMultiPredictions(const ParseState &parseState) const
overloaded version using ParseState, for bindings
Definition: dyngenpar.h:1177
virtual StackItemData * clone()
Definition: dyngenpar.h:708
PseudoCatScope scope() const
Definition: dyngenpar.h:720
virtual void writeExternal(QDataStream &stream) const
implementation of the QDataStream operator<<
Definition: dyngenpar.h:440
QList< Cat > fullLiteral
the entire literal completed by the prediction
Definition: dyngenpar.h:219
bool operator==(const Term &other) const
needed for QList
Definition: dyngenpar.h:945
void add(const DynGenPar::Node &value)
Java-style + the binding generator doesn&#39;t detect the inherited append.
Definition: dyngenpar.h:303
ConstrainedMultiPrediction(const QList< Cat > &fullLit, CatArg c)
Definition: dyngenpar.h:237
ConstrainedMultiPrediction(const QList< Cat > &fullLit, CatArg c, NextTokenConstraints ntc)
Definition: dyngenpar.h:239
Term()
dummy default constructor for bindings
Definition: dyngenpar.h:934
QList< Term > & toList()
for bindings
Definition: dyngenpar.h:985
QDataStream & operator>>(QDataStream &stream, DynGenPar::Action *&data)
Definition: dyngenpar.h:1426
Function(const QList< Sequence > &list)
Definition: dyngenpar.h:995
QHash< Cat, QPair< Cat, int > > componentCats
maps categories which represent components of a multi-component category to the category and componen...
Definition: dyngenpar.h:1253
Sequence(const QList< Term > &list)
Definition: dyngenpar.h:960
const StackItem & parent() const
Definition: dyngenpar.h:660
static QDataStream & constructAndRead(QDataStream &stream, Action *&data)
implementation of the QDataStream operator>>
Definition: dyngenpar.h:445
QHash< Cat, QList< Rule > > RuleSet
Definition: dyngenpar.h:183
PseudoCatScope scope() const
Definition: dyngenpar.h:542
type 6 item: during match, we&#39;re matching a P constraint
Definition: dyngenpar.h:699
virtual LexerState saveState()
saves the current lexer state, by default a null LexerState
Definition: dyngenpar.h:858
QDataStream & writeExternal(QDataStream &stream, bool writeLabel=true, bool writeAction=true) const
implementation of the QDataStream operator<<
Definition: dyngenpar.h:164
static void registerDeserializer(const QString &name, ActionDeserializer *deserializer)
Definition: dyngenpar.h:432
QPair< QPair< Node, NextTokenConstraints >, int > pConstraint(CatArg cat) const
Definition: dyngenpar.h:369
virtual int type() const
Definition: dyngenpar.h:617
Node(CatArg c)
Definition: dyngenpar.h:319
Sequence(const QList< Term > &list, const NextTokenConstraints &ntc)
Definition: dyngenpar.h:962
Match(int l, Node t, int n, PseudoCatScope s, const NextTokenConstraints &nt)
Definition: dyngenpar.h:399
QHash< Cat, QPair< int, PseudoCatScope > > mcfgConstraints
hash table recording MCFG constraints
Definition: dyngenpar.h:348
virtual Cat readToken()
just fetch the next token from the list
Definition: dyngenpar.h:894
void addParent(const StackItem &parent)
Definition: dyngenpar.h:499
virtual StackItemData * clone()
Definition: dyngenpar.h:523
An object representing a CFG (or a PMCFG in our internal representation)
Definition: dyngenpar.h:190
const QList< StackItem > & parents() const
Definition: dyngenpar.h:574
node in the parse tree
Definition: dyngenpar.h:317
QList< Cat > fullLiteral
the entire literal completed by the prediction
Definition: dyngenpar.h:242
Sequence(const NextTokenConstraints &ntc)
Definition: dyngenpar.h:958
data passed to parser actions
Definition: dyngenpar.h:411
bool operator==(const ConstrainedMultiPrediction &other) const
needed for QList, QMultiHash
Definition: dyngenpar.h:247
Alternative & operator+=(const DynGenPar::Node &value)
Definition: dyngenpar.h:290
virtual void addParent(const StackItem &)
Definition: dyngenpar.h:654
TokenSet tokens
tokens
Definition: dyngenpar.h:1219
TokenSet tokens
Definition: dyngenpar.h:196
bool operator==(const Node &other) const
needed for QList
Definition: dyngenpar.h:327
void add(const Term &value)
Java-style (for consistency, even though append is detected here)
Definition: dyngenpar.h:981
LexerState(AbstractLexerStateData *data)
Definition: dyngenpar.h:794
uint qHash(const NextTokenConstraints &nextTokenConstraints)
simple hash function for next token constraints
Definition: dyngenpar.cpp:452
bool hasPConstraint(CatArg cat) const
Definition: dyngenpar.h:363
virtual int type() const
Definition: dyngenpar.h:653
interface for parser action deserializers
Definition: dyngenpar.h:420
virtual void setParents(const QList< StackItem > &)
Definition: dyngenpar.h:570
NextTokenConstraints nextTokenConstraints
Definition: dyngenpar.h:406
virtual int type() const
Definition: dyngenpar.h:524
QList< Cat > expect
list of context-free categories the next token MUST match
Definition: dyngenpar.h:92
QString Cat
Category type: string or integer depending on DYNGENPAR_INTEGER_CATEGORIES.
Definition: dyngenpar.h:68
QHash< Cat, QPair< QPair< Node, NextTokenConstraints >, int > > & pConstraints()
Definition: dyngenpar.h:355
NextTokenConstraints nextTokenConstraints() const
Definition: dyngenpar.h:721
type 0 item: during match, we&#39;re waiting for a token to shift
Definition: dyngenpar.h:511
NextTokenConstraints nextTokenConstraints
only for nonterminals
Definition: dyngenpar.h:244
term in the expression of a component of a PMCFG function
Definition: dyngenpar.h:932
PseudoCatScope scope
Definition: dyngenpar.h:405
component of a PMCFG function, a sequence of terms
Definition: dyngenpar.h:953
const QList< StackItem > & parents() const
Definition: dyngenpar.h:538
virtual void addParent(const StackItem &parent)
Definition: dyngenpar.h:525
(possibly partial) match
Definition: dyngenpar.h:394
virtual int type() const
Definition: dyngenpar.h:565
void setLabel(const QVariant &label)
Definition: dyngenpar.h:138
StackItemType1(const QList< StackItem > &parents, CatArg cat, CatArg effCat, const PseudoCatScope &scope)
Definition: dyngenpar.h:554
QList< Cat > inputTokens
Definition: dyngenpar.h:887
#define IS_EPSILON(cat)
Definition: dyngenpar.h:69
QHash< int, QString > functionNames
Definition: dyngenpar.h:1070
bool simpleRewind(int pos, bool rewindOnly=false)
basic implementation of rewindTo for subclasses which support it
Definition: dyngenpar.h:864
Cfg()
dummy default constructor for bindings
Definition: dyngenpar.h:192
text position
Definition: dyngenpar.h:906
RuleSet cfRules
optional context-free rules
Definition: dyngenpar.h:1065
Match(int l, Node t, int n, PseudoCatScope s)
Definition: dyngenpar.h:397
QDataStream & operator<<(QDataStream &stream, const DynGenPar::Action *data)
Definition: dyngenpar.h:1418
virtual void addParent(const StackItem &)
Definition: dyngenpar.h:710
Sequence & operator<<(const Term &value)
Definition: dyngenpar.h:976
virtual void addParent(const StackItem &)
Definition: dyngenpar.h:566
Node parseTree()
get the parse tree for the last shifted token
Definition: dyngenpar.h:825
StackItemType5(const StackItem &parent, CatArg cat, const PseudoCatScope &scope)
Definition: dyngenpar.h:675
QList< DynGenPar::Node > & toList()
for bindings
Definition: dyngenpar.h:307
QHash< Cat, QPair< int, PseudoCatScope > > & mcfgConstraints()
Definition: dyngenpar.h:359
QList< Cat > & toList()
for bindings
Definition: dyngenpar.h:162
multi-token predictions
Definition: dyngenpar.h:214
const StackItem & parent() const
Definition: dyngenpar.h:688
TokenSet tokens
set of true tokens
Definition: dyngenpar.h:1053
void countCharacter(unsigned char c)
convenience method to count a character
Definition: dyngenpar.h:913
Alternative(const QList< DynGenPar::Node > &list)
Definition: dyngenpar.h:280
RuleSet rules
Definition: dyngenpar.h:195
MultiPrediction()
dummy default constructor for bindings
Definition: dyngenpar.h:216
QVariant label() const
Definition: dyngenpar.h:137
QHash< Cat, QPair< QPair< Node, NextTokenConstraints >, int > > pConstraints
hash table recording parallel constraints
Definition: dyngenpar.h:343
virtual ~Action()
Definition: dyngenpar.h:437
ConstrainedPredictions computeConstrainedPredictions(const ParseState &parseState) const
overloaded version using ParseState, for bindings
Definition: dyngenpar.h:1188
Rule & operator<<(const Cat &value)
Definition: dyngenpar.h:153
QHash< Cat, QList< Cat > > catComponents
maps multi-component categories to the list of their components
Definition: dyngenpar.h:1259
static bool serializeActions
whether the operator<<(QDataStream &, const Rule &) should serialize actions
Definition: dyngenpar.h:129
Predictions computePredictions(const ParseState &parseState) const
overloaded version using ParseState, for bindings
Definition: dyngenpar.h:1169
Function lookupFunction(const QVariant &id) const
Definition: dyngenpar.h:1078
Sequence & operator+=(const QList< Term > &other)
Definition: dyngenpar.h:964
virtual StackItemData * clone()=0
StackItemType6(const StackItem &parent, const QList< Node > &leaves, int i, const Node &tree, const PseudoCatScope &scope, const NextTokenConstraints &nextTokenConstraints)
Definition: dyngenpar.h:701
Cat startCat
start category
Definition: dyngenpar.h:1056
Rule & operator+=(const QList< Cat > &other)
Definition: dyngenpar.h:141
type 3 item: during matchRemaining, we&#39;re executing a match
Definition: dyngenpar.h:607
virtual int type() const
Definition: dyngenpar.h:709
attached to the parse trees as rule labels to allow obtaining syntax trees
Definition: dyngenpar.h:1090
bool isToken(CatArg cat) const
Definition: dyngenpar.h:1141
void addToken(CatArg cat)
Definition: dyngenpar.h:199
type 1 item: during type 0 item processing, we&#39;re executing a reduce
Definition: dyngenpar.h:552
virtual StackItemData * clone()
Definition: dyngenpar.h:616
ActionInfo(const Node &t)
Definition: dyngenpar.h:414
virtual void setParents(const QList< StackItem > &parents)
Definition: dyngenpar.h:530
QDataStream & readExternal(QDataStream &stream)
implementation of the QDataStream operator>>
Definition: dyngenpar.h:205
virtual void setParents(const QList< StackItem > &)
Definition: dyngenpar.h:713
ConstrainedMultiPredictions computeConstrainedMultiPredictions(const ParseState &parseState) const
overloaded version using ParseState, for bindings
Definition: dyngenpar.h:1199
bool hasMcfgConstraint(CatArg cat) const
Definition: dyngenpar.h:366
QList< Cat > taboo
list of context-free categories the next token MUST NOT match
Definition: dyngenpar.h:100
virtual void setParents(const QList< StackItem > &)
Definition: dyngenpar.h:621
Cfg(const RuleSet &r, const TokenSet &t, CatArg sc)
Definition: dyngenpar.h:193
virtual bool rewindTo(int pos, const LexerState &=LexerState())
rewind to an older position (requires buffering)
Definition: dyngenpar.h:853
PseudoCatScope scope() const
Definition: dyngenpar.h:577
TokenSource * inputSource
input source
Definition: dyngenpar.h:1264
QList< Match > incrementalMatches
Definition: dyngenpar.h:1124
virtual ~TokenSource()
Definition: dyngenpar.h:807
Action * action
Definition: dyngenpar.h:140
virtual AbstractLexerStateData * clone()=0
Rule & operator+=(const Cat &value)
Definition: dyngenpar.h:145
FullRule(CatArg c, const Rule &r, int epsSkipped, int n)
Definition: dyngenpar.h:261
Function & operator+=(const QList< Sequence > &other)
Definition: dyngenpar.h:996
bool operator==(const LexerState &other) const
Definition: dyngenpar.h:798
QSet< Cat > Predictions
Definition: dyngenpar.h:211
StackItemType4(const StackItem &parent, CatArg target, int pos, int len)
Definition: dyngenpar.h:648
API for stateful lexers to save their state for rewinding.
Definition: dyngenpar.h:784
FullRule()
dummy default constructor for bindings
Definition: dyngenpar.h:260
QDataStream & writeExternal(QDataStream &stream) const
implementation of the QDataStream operator<<
Definition: dyngenpar.h:106
Match()
dummy default constructor for bindings
Definition: dyngenpar.h:396
Function & operator<<(const Sequence &value)
Definition: dyngenpar.h:1008
bool operator==(const PseudoCatScope &other) const
Definition: dyngenpar.h:380
Sequence & operator+=(const Term &value)
Definition: dyngenpar.h:968
Node(CatArg c, const QVariant &d)
Definition: dyngenpar.h:320
Rule(const QList< Cat > &list)
Definition: dyngenpar.h:133
ConstrainedMultiPrediction()
dummy default constructor for bindings
Definition: dyngenpar.h:235
StackItem()
invalid type
Definition: dyngenpar.h:481
QMultiHash< QList< Cat >, ConstrainedMultiPrediction > ConstrainedMultiPredictions
Definition: dyngenpar.h:255
Term(int a, int c)
Definition: dyngenpar.h:935
Cat cat
the nonterminal generating the literal
Definition: dyngenpar.h:220
QMultiHash< Cat, NextTokenConstraints > ConstrainedPredictions
Definition: dyngenpar.h:230
MultiPrediction(const QList< Cat > &fullLit, CatArg c)
Definition: dyngenpar.h:217
void add(const Sequence &value)
Java-style (for consistency, even though append is detected here)
Definition: dyngenpar.h:1013
RuleSet rules
set of PMCFG rules
Definition: dyngenpar.h:1050
Node tree
sub-parse-tree for hierarchical parsing
Definition: dyngenpar.h:879
virtual bool rewindTo(int pos, const LexerState &=LexerState())
overridden because lists can be rewound
Definition: dyngenpar.h:889
virtual StackItemData * clone()
Definition: dyngenpar.h:652
LexerState lexerState
Definition: dyngenpar.h:1125
int currentPosition()
get the current input position
Definition: dyngenpar.h:840
Rule(const QVariant &label)
Definition: dyngenpar.h:131
Cat startCat
start category
Definition: dyngenpar.h:1221
int ruleno
used for PMCFGs
Definition: dyngenpar.h:403
bool isNull() const
Definition: dyngenpar.h:796
TextPosition(int l, int c)
Definition: dyngenpar.h:908
StackItemType0(const QList< StackItem > &parents, CatArg cat, CatArg effCat, int pos, const PseudoCatScope &scope)
Definition: dyngenpar.h:513
int type() const
Definition: dyngenpar.h:497
QMultiHash< QList< Cat >, MultiPrediction > MultiPredictions
Definition: dyngenpar.h:229
StackItemType3(const StackItem &parent, const Rule &rule, int len, int curr, int i, const Node &tree, int ruleno, const NextTokenConstraints &nextTokenConstraints)
Definition: dyngenpar.h:609
type 4 item: during reduce, we&#39;re executing a matchRemaining
Definition: dyngenpar.h:646
QList< Function > functions
list of PMCFG functions
Definition: dyngenpar.h:1031
RuleSet rules
grammar rules
Definition: dyngenpar.h:1217
multi-token predictions with next token constraints
Definition: dyngenpar.h:233
virtual StackItemData * clone()
Definition: dyngenpar.h:564
interface for parser actions
Definition: dyngenpar.h:428
type 2 item: during reduce, we&#39;re recursively executing another reduce
Definition: dyngenpar.h:587
Parser(TokenSource *tokenSource)
Definition: dyngenpar.h:1138
virtual ~Parser()
Definition: dyngenpar.h:1140
Cat cat
the nonterminal generating the literal / the nonterminal itself
Definition: dyngenpar.h:243
const StackItem & parent() const
Definition: dyngenpar.h:600
const Cat & CatArg
Category type (string or integer) when passed as an argument.
Definition: dyngenpar.h:80
QList< StackItem > incrementalStacks
Definition: dyngenpar.h:1123
virtual bool matchParseTree(const Node &treeToMatch)
match the parse tree for the last shifted token against the given tree
Definition: dyngenpar.h:836
void addFunction(const QString &name, const Function &function)
Definition: dyngenpar.h:1072
Term(CatArg t)
Definition: dyngenpar.h:936
virtual void setParents(const QList< StackItem > &)
Definition: dyngenpar.h:685
Alternative(const QVariant &label)
Definition: dyngenpar.h:278
bool isComponent() const
Definition: dyngenpar.h:942
bool operator==(const MultiPrediction &other) const
needed for QList, QMultiHash
Definition: dyngenpar.h:223
void add(const Cat &value)
Java-style + the binding generator doesn&#39;t detect the inherited append.
Definition: dyngenpar.h:158
Alternative & operator<<(const DynGenPar::Node &value)
Definition: dyngenpar.h:298
QHash< Cat, QPair< Cat, QList< Cat > > > pseudoCats
pseudo-categories, used to represent PMCFGs internally
Definition: dyngenpar.h:1247
virtual int type() const
Definition: dyngenpar.h:681
void setLabel(const QVariant &label)
Definition: dyngenpar.h:285
QHash< QString, int > functionIndices
Definition: dyngenpar.h:1071
QDataStream & readExternal(QDataStream &stream)
implementation of the QDataStream operator>>
Definition: dyngenpar.h:110
virtual void setParents(const QList< StackItem > &)
Definition: dyngenpar.h:657
PmcfgComponentInfo(const Rule &rule)
Definition: dyngenpar.h:1092
QList< Sequence > & toList()
for bindings
Definition: dyngenpar.h:1017
QList< Node > leaves() const
Definition: dyngenpar.h:717
void setParents(const QList< StackItem > &parents)
Definition: dyngenpar.h:500
int ruleno
needed for PMCFGs (to match components of rules to each other)
Definition: dyngenpar.h:269
QDataStream & readExternal(QDataStream &stream)
implementation of the QDataStream operator>>
Definition: dyngenpar.h:173
PMCFG function.
Definition: dyngenpar.h:992
QVariant label() const
Definition: dyngenpar.h:284
Alternative(const QList< DynGenPar::Node > &list, const QVariant &label)
Definition: dyngenpar.h:282
Cfg getCfg()
get a Cfg object back from the parser, for serialization
Definition: dyngenpar.h:1153
PseudoCatScope scope() const
Definition: dyngenpar.h:690
bool isToken() const
Definition: dyngenpar.h:943
StackItemType2(const StackItem &parent)
Definition: dyngenpar.h:589
QVector< QVector< int > > argPositions
Definition: dyngenpar.h:1095
full rule as found in the initial graph
Definition: dyngenpar.h:258
bool operator==(const NextTokenConstraints &other) const
needed for hash tables
Definition: dyngenpar.h:102
virtual StackItemData * clone()
Definition: dyngenpar.h:680
StackItemData(int depth)
Definition: dyngenpar.h:467
virtual void addParent(const StackItem &)
Definition: dyngenpar.h:682
Rule(const QList< Cat > &list, const QVariant &label)
Definition: dyngenpar.h:135
Function & operator+=(const Sequence &value)
Definition: dyngenpar.h:1000
const StackItemData * data() const
Definition: dyngenpar.h:501
void loadCfg(const Cfg &cfg)
Definition: dyngenpar.h:1146
bool isToken(CatArg cat) const
Definition: dyngenpar.h:198
static bool serializeLabels
whether the operator<<(QDataStream &, const Rule &) should serialize labels
Definition: dyngenpar.h:128
virtual void setParents(const QList< StackItem > &)
Definition: dyngenpar.h:597
QDataStream & writeExternal(QDataStream &stream) const
implementation of the QDataStream operator<<
Definition: dyngenpar.h:201
int col
column, zero-based
Definition: dyngenpar.h:924
QVariant data
Definition: dyngenpar.h:324
virtual void addParent(const StackItem &)
Definition: dyngenpar.h:594
NextTokenConstraints nextTokenConstraints
Definition: dyngenpar.h:139
const PseudoCatScopeData * data() const
needed for hash tables
Definition: dyngenpar.h:379
type 5 item: during match (of an MCFG constraint), we&#39;re executing a matchRemaining ...
Definition: dyngenpar.h:673
rule constraints affecting the next token, for scannerless parsing
Definition: dyngenpar.h:84
Node()
error node
Definition: dyngenpar.h:318
QList< Alternative > children
Definition: dyngenpar.h:325
int line
line, zero-based
Definition: dyngenpar.h:923
QList< Match > parse(ParseState *parseState)
overloaded version using ParseState, for bindings
Definition: dyngenpar.h:1162
QSet< Cat > TokenSet
Definition: dyngenpar.h:184
void addToken(CatArg cat)
Definition: dyngenpar.h:1142
virtual StackItemData * clone()
Definition: dyngenpar.h:592
Node parseTreeToPmcfgSyntaxTree(const Node &parseTree)
converts a parse tree obtained from a PMCFG to a PMCFG syntax tree
Definition: dyngenpar.cpp:539
QPair< int, PseudoCatScope > mcfgConstraint(CatArg cat) const
Definition: dyngenpar.h:374
Cat nextToken()
get the next token from the input, increment current position, save parse tree
Definition: dyngenpar.h:813
main class
Definition: dyngenpar.h:1135
bool operator<(const StackItem &other) const
Definition: dyngenpar.h:502
const StackItem & parent() const
Definition: dyngenpar.h:624
NextTokenConstraints nextTokenConstraints
Definition: dyngenpar.h:955
virtual void addParent(const StackItem &)
Definition: dyngenpar.h:618
Alternative & operator+=(const QList< DynGenPar::Node > &other)
Definition: dyngenpar.h:286
parse state struct, for bindings
Definition: dyngenpar.h:1108
int depth() const
Definition: dyngenpar.h:498
ActionInfo()
dummy default constructor for bindings
Definition: dyngenpar.h:413
virtual int type() const
Definition: dyngenpar.h:593
NextTokenConstraints nextTokenConstraints() const
Definition: dyngenpar.h:631