cfgrammars.h

Go to the documentation of this file.

 
#include "elementa/license.inc"
#include "elementa/checks.inc"
 
#ifndef ELEMENTA_PARSING_CFGRAMMARS
#define ELEMENTA_PARSING_CFGRAMMARS
 
#include <vector>
#include <map>
#include <set>
#include <utility>
#include <type_traits>
#include <iterator>
#include "elementa/base/fundamentaltypes.h"
#include "elementa/base/exceptions.h"
#include "elementa/base/serial_channels/serializers.h"
#include "elementa/base/iterators.h"
#include "elementa/base/enums.h"
#include "elementa/patterns/validatable.h"
#include "elementa/parsing/lexer.h"
 
namespace elementa
{
 
namespace parsing
{
 
/* **********************************************************************
 
    Class: CFGrammar
 
*************************************************************************/
 
 
class CFGrammar
{
 public:
 
    struct MultipleEntry: public elementa::base::Exc
    {
        MultipleEntry(const std::string & details):
                        elementa::base::Exc{"Multiple entry in LL(1) table" + 
                                            details} {}
                                            
        ELE_CLASS_EXCOVERRIDE(MultipleEntry)
    };
 
 
    using CodeElement = TokenId;
 
    using SetOfElements = std::set<CodeElement>;
 
    using MapOfElements = std::map<CodeElement,SetOfElements>;
 
    using VectorOfElements = std::vector<CodeElement>;
 
 
    using RHS = VectorOfElements;
 
    using RHSs = std::vector<RHS>; 
 
    using MapOfRules = std::map<CodeElement, RHSs>;
 
    using Rule = std::pair<CodeElement,RHS>;
 
 
    class RuleIterator final: ELE_CLASS_VALIDATABLE
    {
     public:
 
        using Category = std::bidirectional_iterator_tag;
 
        using T = Rule;
 
        using Distance = std::ptrdiff_t;
 
        using Pointer = T*;
 
        using Reference = T&;
 
 
        RuleIterator(void)
            {ELE_CODE_TRACE_OFF;
                ELE_CODE_TRACE({},"RuleIterator::dflt-constr. of " <<
                                  elementa::base::to_number(this)); }
 
 
        RuleIterator(const CFGrammar & gr, bool beginorend = true);
 
        RuleIterator(const RuleIterator & oth):Validatable{oth}
            {ELE_CODE_TRACE_OFF; ELE_CODE_TRACE({},"RuleIterator::copy-const.");
                copyFrom(oth); }
 
        RuleIterator(RuleIterator && oth):Validatable{oth}
            {ELE_CODE_TRACE_OFF; ELE_CODE_TRACE({},"RuleIterator::move-const.");
                copyFrom(oth); }
 
        RuleIterator & operator=(const RuleIterator & oth)
            {ELE_CODE_TRACE_OFF; 
                ELE_CODE_TRACE({},"RuleIterator::assign, oth!=this : " << 
                                  (this != &oth));  
                if (this != &oth) { Validatable::operator=(oth); copyFrom(oth);} 
                return(*this); }
        RuleIterator & operator=(RuleIterator && oth)
            {ELE_CODE_TRACE_OFF; 
                ELE_CODE_TRACE({},"RuleIterator::move-assign, oth!=this : " << 
                                  (this != &oth));  
                if (this != &oth) { Validatable::operator=(oth); copyFrom(oth);}
                return(*this); }
 
        ~RuleIterator(void)
            {ELE_CODE_TRACE_OFF; 
                ELE_CODE_TRACE({},"RuleIterator::destructor of " <<
                                  elementa::base::to_number(this));}
 
        RuleIterator operator++(int);
 
        RuleIterator operator--(int); 
        
        RuleIterator & operator++(void); 
    
        RuleIterator & operator--(void);
 
        Rule operator*(void) const;
 
        bool operator==(const RuleIterator & oth) const;
 
        bool operator!=(const RuleIterator & oth) const
            { return(!this->operator==(oth)); }
 
     private:
    
        std::pair<typename MapOfRules::const_iterator, 
                  typename RHSs::size_type> pos_;
        MapOfRules::const_iterator grbeg_, grend_;
 
        void copyFrom(const RuleIterator & oth);
    };
 
    class LL1TableIndex: public std::pair<CodeElement,CodeElement>,
                         ELE_CLASS_VALIDATABLE
    {
      public:
 
        using BaseClass = std::pair<CodeElement,CodeElement>;
 
        LL1TableIndex(void) = default;
 
        LL1TableIndex(const LL1TableIndex & oth):Validatable{oth},
                                                        BaseClass{oth}  {}
 
        LL1TableIndex(LL1TableIndex && oth):Validatable{std::move(oth)},
                                                   BaseClass{std::move(oth)} {}
 
        LL1TableIndex & operator=(const LL1TableIndex & oth)
            { if (this != &oth) { Validatable::operator=(oth); 
                                  if (valid()) BaseClass::operator=(oth); }
              return(*this); }
 
        LL1TableIndex & operator=(LL1TableIndex && oth) 
            { if (this != &oth) { Validatable::operator=(std::move(oth)); 
                                  if (valid()) 
                                    BaseClass::operator=(std::move(oth)); }
              return(*this); }
 
        LL1TableIndex(CodeElement nt, CodeElement t):BaseClass{nt,t}
            { if (!isNonTerminal(nt))
                ELE_CODE_INVARG(
                    std::string{"First part of a LL1 table index is not a "} +
                    "non-terminal (code " + std::to_string(nt) +")");
              if ((!isTerminal(t))&&(t != kCodeEnd)) // endofsentence is allowed
                ELE_CODE_INVARG(
                    std::string{"Second part of a LL1 table index is not a "} +
                    "terminal or endofsentence (code " +std::to_string(t) +")"); 
              setValid(); }
              
        bool operator==(const LL1TableIndex & o) const
            { return(valid() && o.valid() &&
                     (this->first == o.first) && (this->second == o.second)); }
            
        bool operator!=(const LL1TableIndex & o) const
            { return(!operator==(o)); }
 
        bool operator<(const LL1TableIndex & oth) const
            { return(valid() && oth.valid() && 
                     ( (first < oth.first) ||
                       ( (first == oth.first) && (second < oth.second) ))); }
    };
 
 
    class CatId: public std::pair<int,int>
    {
     public:
 
        using Base = std::pair<int,int>;
        using Base::Base;
    };
 
    using LL1Table = std::map<LL1TableIndex,RuleIterator>;
 
    static const CodeElement kCodeEmpty; 
 
    static const CodeElement kCodeEnd; 
 
    static const std::string kEmptyName; 
 
    static const std::string kEndName; 
 
    static bool isNonTerminal(CodeElement c) noexcept 
        { return(c > kCodeEmpty);}
 
 
    static bool isTerminal(CodeElement c, bool extended = false) noexcept 
        { return(extended ? (c <= kCodeEmpty) : (c < kCodeEnd)); }
 
 
    static void checkRule(const Rule & r);
 
 
    static bool isRuleHeader(const Rule & r, 
                             CodeElement left, CodeElement firstright);
                             
 
    static bool hasRuleFirstRight(const Rule & r,
                                  CodeElement firstright);                           
 
    CFGrammar(void) { clear(); }
 
    CFGrammar(const CFGrammar &) = delete;
    CFGrammar(CFGrammar &&) = delete;
    CFGrammar & operator=(const CFGrammar &) = delete;
    CFGrammar & operator=(CFGrammar &&) = delete;
 
    virtual ~CFGrammar(void) = default;
 
    size_t sizeTerminals(void) const noexcept
        { return(static_cast<size_t>(kCodeEnd - lastterm_)); }
 
    size_t sizeNonTerminals(void) const noexcept
        { return(static_cast<size_t>(lastnonterm_ - kCodeEmpty)); }
 
 
    bool existsTerminal(CodeElement c) const
        { if (!isTerminal(c)) return(false); return(lastterm_ <= c); }
 
 
    bool existsNonTerminal(CodeElement c) const
        { if (!isNonTerminal(c)) return(false); return(lastnonterm_ >= c); }
 
    size_t sizeTerminals(int cat) const
        { if (!existsTerminalCategory(cat))
            ELE_CODE_INVARG("Invalid category number");
          return(catsterms_[cat].size()); }
 
    size_t sizeNonTerminals(int cat) const
        { if (!existsTerminalCategory(cat))
            ELE_CODE_INVARG("Invalid category number");
          return(catsnonterms_[cat].size()); }
 
 
    bool existsTerminalCategory(int cat) const
        { return(static_cast<VectorOfCats::size_type>(cat) <
                 catsterms_.size()); }
 
 
    bool existsNonTerminalCategory(int cat) const
        { return(static_cast<VectorOfCats::size_type>(cat) <
                 catsnonterms_.size()); }
 
 
    bool existsTerminalCatID(const CatId & catid) const
        { return(existsTerminalCategory(catid.first) &&
                 (static_cast<VectorOfCatIDs::size_type>(catid.second) <
                    catsterms_[catid.first].size())); }
 
 
    bool existsNonTerminalCatID(const CatId & catid) const
        { return(existsTerminalCategory(catid.first) &&
                 (static_cast<VectorOfCatIDs::size_type>(catid.second) <
                    catsnonterms_[catid.first].size())); }
 
 
    CodeElement codeOfTerminal(const CatId & catid) const
        { if (!existsTerminalCatID(catid))
            throw(elementa::base::notfound{""}.asEXC(ELE_CODE_PLACE));
          return(catsterms_[catid.first][catid.second]); }
 
 
    CodeElement codeOfNonTerminal(const CatId & catid) const
        { if (!existsNonTerminalCatID(catid))
            throw(elementa::base::notfound{""}.asEXC(ELE_CODE_PLACE));
          return(catsnonterms_[catid.first][catid.second]); }
 
 
    CatId catidOfTerminal(CodeElement c) const
        { if (!existsTerminal(c))   
            throw(elementa::base::notfound{""}.asEXC(ELE_CODE_PLACE));
         return(CatId{linkstotermcats_[-c].first,linkstotermcats_[-c].second});}
 
 
    CatId catidOfNonTerminal(CodeElement c) const
        { if (!existsNonTerminal(c)) 
            throw(elementa::base::notfound{""}.asEXC(ELE_CODE_PLACE));
          return(CatId{linkstonontermcats_[c].first,
                       linkstonontermcats_[c].second});}
 
 
    int catOfTerminal(CodeElement c) const
        { if (!existsTerminal(c))   
            throw(elementa::base::notfound{""}.asEXC(ELE_CODE_PLACE));
         return(linkstotermcats_[-c].first); }
 
 
    int catOfNonTerminal(CodeElement c) const
        { if (!existsNonTerminal(c)) 
            throw(elementa::base::notfound{""}.asEXC(ELE_CODE_PLACE));
          return(linkstonontermcats_[c].first); }
 
 
    const RHSs & rightsOf(CodeElement n) const;
 
 
    CodeElement starting(void) const;
 
 
    std::string nameOfTerminal(CodeElement c) const;
 
 
    std::string nameOfNonTerminal(CodeElement c) const;
 
    RuleIterator begin(void) const { return(RuleIterator{*this,true}); }
 
    RuleIterator end(void) const { return(RuleIterator{*this,false}); }
 
 
    elementa::base::IotaView<CodeElement> terminalRange(void) const noexcept
        { return(sizeNonTerminals() == 0 ? 
                    elementa::base::IotaView<CodeElement>{}:
                    elementa::base::IotaView<CodeElement>{lastterm_,kCodeEnd});}
 
 
    elementa::base::IotaView<CodeElement> nonTerminalRange(void) const noexcept
        { return(sizeTerminals() == 0 ? 
                    elementa::base::IotaView<CodeElement>{}:
                    elementa::base::IotaView<CodeElement>{kCodeEmpty+1, 
                                                          lastnonterm_+1}); }
 
 
    elementa::base::IotaView<int> terminalCatRange(void) const noexcept
        { return(elementa::base::IotaView<int>{0,
                                   static_cast<int>(catsterms_.size())}); }
 
 
    elementa::base::IotaView<int> nonTerminalCatRange(void) const noexcept
        { return(elementa::base::IotaView<int>{0,
                                   static_cast<int>(catsnonterms_.size())}); }
 
 
    elementa::base::IotaView<int> terminalCatIDRange(int cat) const 
        { if (!existsTerminalCategory(cat))
            throw(elementa::base::notfound{""}.asEXC(ELE_CODE_PLACE));
          return(elementa::base::IotaView<int>{0,
                               static_cast<int>(catsterms_[cat].size())}); }
 
 
    elementa::base::IotaView<int> nonTerminalCatIDRange(int cat) const 
        { if (!existsNonTerminalCategory(cat))
            throw(elementa::base::notfound{""}.asEXC(ELE_CODE_PLACE));
          return(elementa::base::IotaView<int>{0,
                               static_cast<int>(catsnonterms_[cat].size())}); }
 
 
    CodeElement findNonTerminal(const std::string & name) const;
 
 
    CodeElement findTerminal(const std::string & name) const;
 
    std::string to_string(const SetOfElements & soe) const;
 
    std::string to_string(const MapOfElements & moe) const;
 
    std::string to_string(const RHS & rhs) const;
 
    std::string to_string(const Rule & r) const;
 
    std::string to_string(const LL1Table t) const;
 
    void clear(void);
 
 
    CodeElement addTerminal();
 
 
    CodeElement addNonTerminal();
 
 
    void addRule(const Rule & r);
 
 
    void assignName(CodeElement c, const std::string & name);
 
 
    int newTerminalCategory(void);
 
 
    int newNonTerminalCategory(void);
 
 
    void checkIntegrity(bool withnames = true) const;
 
 
    bool directlyLeftRecursive(Rule & r) const;
 
 
    bool leftRecursive(CodeElement & rec) const;
 
 
    void calculateFirsts(MapOfElements & firsts) const; 
 
 
    void firstOfRHS(const RHS & rhs, const MapOfElements & firsts,
                    SetOfElements & f) const;
 
 
    void calculateFollows(const MapOfElements & firsts,
                          MapOfElements & follows,
                          std::string * trace = nullptr) const;
 
 
    void firstFirstConflicts(const MapOfElements & firsts,
                             SetOfElements & nts) const;
 
 
    void firstFollowConflicts(const MapOfElements & firsts,
                              const MapOfElements & follows,
                              MapOfElements & nts) const;       
 
 
    bool isLL1(const MapOfElements & firsts, 
               const MapOfElements & follows,
               SetOfElements & fifi, MapOfElements & fifo) const;
 
 
    void fillLL1Table(const MapOfElements & firsts, 
                      const MapOfElements & follows,
                      LL1Table & table) const;
 
 private:
 
    using MapOfNames = std::map<std::string,CodeElement>;
    using MapOfNamesSearchRes = std::pair< MapOfNames::iterator,bool >;
    using MapOfNamesItem = std::pair<std::string,CodeElement>;
 
    using VectorOfCatIDs = std::vector<int>;
    using VectorOfCats = std::vector< VectorOfCatIDs >;
    using CatAndID = std::pair<int,int>;
    using VectorOfCatAndIDs = std::vector<CatAndID>;
 
    CodeElement lastnonterm_, lastterm_;
    MapOfRules rules_;
 
    std::vector<const std::string *> linkstotermnames_, linkstonontermnames_;
    // pointers without ownership, just to link inside "names_"
    MapOfNames namesterms_,namesnonterms_; 
    // we use map instead of unordered_map for better efficiency in typical 
    // sizes of grammars (see https://stackoverflow.com/a/51961807 )
 
    VectorOfCats catsterms_,catsnonterms_;
    VectorOfCatAndIDs linkstotermcats_, linkstonontermcats_;
 
    RHSs * findRules(CodeElement n);
    bool exploreLeftRecursive(CodeElement n, SetOfElements & hist,
                              CodeElement & res, size_t depth) const;
 
 
    // Static asserts at the end because a bug in doxygen that stops generating
    // code when this is found.
 
    static_assert(std::is_same<TokenId,CFGrammar::CodeElement>::value,
                  "CFGrammar::CodeElement must equal TokenId");
};
 
 
/* **********************************************************************
 
    Class: Szer_CFGrammarSpec
 
*************************************************************************/
 
 
class Szer_CFGrammarSpec: public elementa::base::Serializer<CFGrammar>
{
 public:
 
    struct InvElement: public elementa::base::SzerError
    {
        InvElement(const std::string & details):
                                SzerError{"Invalid element" + details} {}
                                
        ELE_CLASS_EXCOVERRIDE(InvElement)
    };
 
    struct InvCatList: public elementa::base::SzerError
    {
        InvCatList(const std::string & details):
                                SzerError{"Invalid list of categorized elements" 
                                          + details} {}
                                          
        ELE_CLASS_EXCOVERRIDE(InvCatList)
    };
 
    struct Repeated: public elementa::base::SzerError
    {
        Repeated(const std::string & details):
                                SzerError{"Repeated in the specification" 
                                          + details} {}
                                          
        ELE_CLASS_EXCOVERRIDE(Repeated)                                       
    };
 
    struct Unused: public elementa::base::SzerError
    {
        Unused(const std::string & details):
                                SzerError{"Unused in the specification" 
                                          + details} {}
                                          
        ELE_CLASS_EXCOVERRIDE(Unused)                                         
    };
 
    struct Unexpected: public elementa::base::SzerError
    {
        Unexpected(const std::string & details):
                                SzerError{"Unexpected element" + details} {}
                                
        ELE_CLASS_EXCOVERRIDE(Unexpected)                               
    };
 
    static const std::string kTermsSect;
 
    static const std::string kNonTermsSect;
 
    static const std::string kRulesSect;
 
    static const std::string kOpenSect;
 
    static const std::string kCloseSect;
 
    static const std::string kOpenCat;
 
    static const std::string kCloseCat;
 
    static const std::string kSideSep; 
 
    static const std::string kRHSSep; 
 
    static const std::string kRuleEndMark;
 
 
    void ser(elementa::base::OutSerCh & chout, const CFGrammar & cfg);
 
    void deser(elementa::base::InSerCh & chin, CFGrammar & cfg);
 
 private:
 
    ELE_CLASS_ENUM(Section,
                    kTerms,     // begin in 0 according to the standard
                    kNonterms,
                    kRules);
 
    Section whichSection(const std::string & token) const noexcept;
    std::string concatLoc(const std::string & str) const;
    void throwUnexpected(const std::string & whatexp, 
                         const std::string & whatfound,
                         const std::string & place = "") const;
 
    std::string locstr_;
 
};
 
 
  // CFGrammars
 
} // End parsing namespace
 
} // End elementa namespace 
 
 
#endif