lalr.h - mozsearch

Enable keyboard shortcuts

// Copyright (C) 2016 The Qt Company Ltd.

// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only WITH Qt-GPL-exception-1.0

// Qt-Security score:insignificant reason:build-tool

#pragma once

#include <QtCore/qset.h>

#include <QtCore/qstack.h>

#include <QtCore/qmap.h>

#include <QtCore/qstring.h>

#include <QtCore/qtextstream.h>

#include <algorithm>

#include <functional>

#include <set>

#include <list>

class Rule;

class State;

class Grammar;

class Item;

class State;

class Arrow;

class Automaton;

// names

typedef std::list<QString>::iterator Name;

typedef std::list<Name> NameList;

typedef std::set<Name> NameSet;

// items

typedef std::list<Item> ItemList;

typedef ItemList::iterator ItemPointer;

// rules

typedef std::list<Rule> debug_infot;

typedef debug_infot::iterator RulePointer;

typedef QMultiMap<Name, RulePointer> RuleMap;

// states

typedef std::list<State> StateList;

typedef StateList::iterator StatePointer;

// arrows

typedef QMap<Name, StatePointer> Bundle;

class Rule

public:

  void clear ()

    lhs = Name ();

    rhs.clear ();

    prec = Name ();

public:

  Name lhs;

  NameList rhs;

  Name prec;

};

class Lookback

public:

  Lookback (StatePointer s, Name n):

    state (s), nt (n) {}

  inline bool operator == (const Lookback &other) const

  { return state == other.state && nt == other.nt; }

  inline bool operator != (const Lookback &other) const

  { return state != other.state || nt != other.nt; }

  bool operator < (const Lookback &other) const;

public:

  StatePointer state;

  Name nt;

};

class Item

public:

  inline NameList::iterator begin_rhs () const

  { return rule->rhs.begin (); }

  inline NameList::iterator end_rhs () const

  { return rule->rhs.end (); }

  inline bool operator == (const Item &other) const

  { return rule == other.rule && dot == other.dot; }

  inline bool operator != (const Item &other) const

  { return rule != other.rule || dot != other.dot; }

  inline bool isReduceItem () const

  { return dot == rule->rhs.end (); }

  Item next () const;

public:

  RulePointer rule;

  NameList::iterator dot;

};

class State

public:

  State (Grammar *grammar);

  inline bool operator == (const State &other) const

  { return kernel == other.kernel; }

  inline bool operator != (const State &other) const

  { return kernel != other.kernel; }

  std::pair<ItemPointer, bool> insert(const Item &item);

  std::pair<ItemPointer, bool> insertClosure(const Item &item);

public: // attributes

  ItemList kernel;

  ItemList closure;

  Bundle bundle;

  QMap<Name, NameSet> reads;

  QMap<Name, NameSet> follows;

  RulePointer defaultReduce;

};

/////////////////////////////////////////////////////////////

// digraph

/////////////////////////////////////////////////////////////

template <typename _Tp>

class Node

public:

  typedef std::set<Node<_Tp> > Repository;

  typedef typename Repository::iterator iterator;

  typedef typename std::list<iterator>::iterator edge_iterator;

public:

  static iterator get (_Tp data);

  std::pair<edge_iterator, bool> insertEdge(iterator other) const;

  inline edge_iterator begin () const

  { return outs.begin (); }

  inline edge_iterator end () const

  { return outs.end (); }

  inline bool operator == (const Node<_Tp> &other) const

  { return data == other.data; }

  inline bool operator != (const Node<_Tp> &other) const

  { return data != other.data; }

  inline bool operator < (const Node<_Tp> &other) const

  { return data < other.data; }

  static inline iterator begin_nodes ()

  { return repository ().begin (); }

  static inline iterator end_nodes ()

  { return repository ().end (); }

  static Repository &repository ()

    static Repository r;

    return r;

public: // attributes

  mutable bool root;

  mutable int dfn;

  mutable _Tp data;

  mutable std::list<iterator> outs;

protected:

  inline Node () {}

  inline Node (_Tp d):

    root (true), dfn (0), data (d) {}

};

template <typename _Tp>

typename Node<_Tp>::iterator Node<_Tp>::get (_Tp data)

  Node<_Tp> tmp (data);

  iterator it = repository ().find (tmp);

  if (it != repository ().end ())

    return it;

  return repository ().insert (tmp).first;

template <typename _Tp>

std::pair<typename std::list<typename Node<_Tp>::iterator>::iterator, bool> Node<_Tp>::insertEdge(typename Node<_Tp>::iterator other) const

  edge_iterator it = std::find (outs.begin (), outs.end (), other);

  if (it != outs.end ())

    return {it, false};

  other->root = false;

  return {outs.insert (outs.end (), other), true};

/////////////////////////////////////////////////////////////

// Grammar

/////////////////////////////////////////////////////////////

class Grammar

public:

  Grammar ();

  Name intern (const QString &id);

  Name intern (const char *id) { return intern(QString::fromUtf8(id)); }

  inline bool isTerminal (Name name) const

  { return terminals.find (name) != terminals.end (); }

  inline bool isNonTerminal (Name name) const

  { return non_terminals.find (name) != non_terminals.end (); }

  void buildRuleMap ();

  void buildExtendedGrammar ();

public:

  QString merged_output;

  QString table_name;

  QString decl_file_name;

  QString impl_file_name;

  QString token_prefix;

  std::list<QString> names;

  Name start;

  NameSet terminals;

  NameSet non_terminals;

  QMap<Name, QString> spells;

  debug_infot rules;

  RuleMap rule_map;

  RulePointer goal;

  Name tk_end;

  Name accept_symbol;

  NameSet declared_lhs;

  int expected_shift_reduce;

  int expected_reduce_reduce;

  QString inputCopyright;

  enum Assoc {

    NonAssoc,

    Left,

    Right

};

  struct TokenInfo {

    Assoc assoc;

    int prec;

};

  QMap<Name, TokenInfo> token_info;

  Assoc current_assoc;

  int current_prec;

};

class Read

public:

  inline Read () {}

  inline Read (StatePointer s, Name n):

    state (s), nt (n) {}

  inline bool operator == (const Read &other) const

  { return state == other.state && nt == other.nt; }

  inline bool operator != (const Read &other) const

  { return state != other.state || nt != other.nt; }

  bool operator < (const Read &other) const;

public:

  StatePointer state;

  Name nt;

};

class Include

public:

  inline Include () {}

  inline Include (StatePointer s, Name n):

    state (s), nt (n) {}

  inline bool operator == (const Include &other) const

  { return state == other.state && nt == other.nt; }

  inline bool operator != (const Include &other) const

  { return state != other.state || nt != other.nt; }

  bool operator < (const Include &other) const;

public:

  StatePointer state;

  Name nt;

};

class Automaton

public:

  Automaton (Grammar *g);

  std::pair<StatePointer, bool> internState (const State &state);

  typedef Node<Read> ReadsGraph;

  typedef ReadsGraph::iterator ReadNode;

  typedef Node<Include> IncludesGraph;

  typedef IncludesGraph::iterator IncludeNode;

  void build ();

  void buildNullables ();

  void buildLookbackSets ();

  void buildDirectReads ();

  void buildReadsDigraph ();

  void buildReads ();

  void visitReadNode (ReadNode node);

  void buildIncludesAndFollows ();

  void buildIncludesDigraph ();

  void visitIncludeNode (IncludeNode node);

  void buildLookaheads ();

  void buildDefaultReduceActions ();

  void closure (StatePointer state);

  int id (RulePointer rule);

  int id (StatePointer state);

  int id (Name name);

  void dump (QTextStream &out, IncludeNode incl);

  void dump (QTextStream &out, ReadNode rd);

  void dump (QTextStream &out, const Lookback &lp);

public: // ### private

  Grammar *_M_grammar;

  StateList states;

  StatePointer start;

  NameSet nullables;

  QMultiMap<ItemPointer, Lookback> lookbacks;

  QMap<ItemPointer, NameSet> lookaheads;

private:

  QStack<ReadsGraph::iterator> _M_reads_stack;

  int _M_reads_dfn;

  QStack<IncludesGraph::iterator> _M_includes_stack;

  int _M_includes_dfn;

};

namespace std {

bool operator < (Name a, Name b);

bool operator < (StatePointer a, StatePointer b);

bool operator < (ItemPointer a, ItemPointer b);

QTextStream &operator << (QTextStream &out, const Name &n);

QTextStream &operator << (QTextStream &out, const Rule &r);

QTextStream &operator << (QTextStream &out, const Item &item);

QTextStream &operator << (QTextStream &out, const NameSet &ns);

QT_BEGIN_NAMESPACE

QTextStream &qerr();

QTextStream &qout();

QT_END_NAMESPACE