parsing.h

Go to the documentation of this file.

 
#include "elementa/license.inc"
#include "elementa/checks.inc"
 
#ifndef ELEMENTA_PARSING_PARSING_H
#define ELEMENTA_PARSING_PARSING_H
 
 
#include <utility>
#include <tuple>
#include <memory>
#include <functional>
#include <type_traits>
#include "elementa/base/fundamentaltypes.h"
#include "elementa/base/strings.h"
#include "elementa/base/exceptions.h"
#include "elementa/base/enums.h"
#include "elementa/base/iterators.h"
#include "elementa/base/serial_channels.h"
#include "elementa/patterns/validatable.h"
#include "elementa/adts/trees.h"
#include "elementa/parsing/lexer.h"
#include "elementa/parsing/cfgrammars.h"
 
namespace elementa
{
 
namespace parsing
{
 
/* **********************************************************************
 
    Base error for parsers
 
*************************************************************************/
 
class ParsingError: public elementa::base::Exc
{
 public:
 
    ParsingError(const std::string & explanation):
                    elementa::base::Exc{std::string{"SYNTACTICAL ERROR. "} + 
                                        explanation} {}
                                        
    ELE_CLASS_EXCOVERRIDE(ParsingError)                                 
};
 
class UnexpParsedSymbol: public ParsingError
{
 public:
 
    UnexpParsedSymbol(const std::string & details):
                    ParsingError{elementa::base::concatWithMiddle(
                                            "Unexpected parsed element",
                                            details)} {}
                                            
    ELE_CLASS_EXCOVERRIDE(UnexpParsedSymbol)
};
 
 
class ExpParsedSymbol: public ParsingError
{
 public:
 
    ExpParsedSymbol(const std::string & details):
                                ParsingError{
                                    elementa::base::concatWithMiddle(
                                        "Expected some parsed element",
                                        details)} {}
                                        
    ELE_CLASS_EXCOVERRIDE(ExpParsedSymbol)                                      
};
 
 
class InvParsedElem: public ParsingError
{
 public:
 
    InvParsedElem(const std::string & details):
                                ParsingError{
                                    elementa::base::concatWithMiddle(
                                        "Invalid parsed element",details)} {}
                                        
    ELE_CLASS_EXCOVERRIDE(InvParsedElem)
};
 
 
class RedefinedParsedElem: public ParsingError
{
 public:
 
    RedefinedParsedElem(const std::string & details):
                                ParsingError{
                                    elementa::base::concatWithMiddle(
                                        "Redefined parsed element",details)} {}
                                        
    ELE_CLASS_EXCOVERRIDE(RedefinedParsedElem)
};
 
 
class UndefinedParsedElem: public ParsingError
{
 public:
 
    UndefinedParsedElem(const std::string & details):
                                ParsingError{
                                    elementa::base::concatWithMiddle(
                                        "Undefined parsed element",details)} {}
                                        
    ELE_CLASS_EXCOVERRIDE(UndefinedParsedElem)
};
 
 
/* **********************************************************************
 
    Class: StepInfo
 
*************************************************************************/
 
 
class StepInfo final
{
 public:
 
    ELE_CLASS_ENUM(Kind,
                    kMatch, 
                    kRule   
                   );
 
 
    Kind kind; 
    elementa::base::SerChLoc::Ptr loc; 
 
 
    struct Info
    {
        Token::Ptr vt;
 
        CFGrammar::RuleIterator rit;
 
        Info(const Token::Ptr & v): vt{v} {}
 
        Info(const CFGrammar::RuleIterator & ri): rit{ri} {}
 
        Info(const Info & oth) = default;
        Info(Info && oth) = default;
        Info & operator=(const Info & oth) = default;
        Info & operator=(Info && oth) = default;        
        ~Info(void) = default;
 
    } info; // info content
 
    StepInfo(const Token::Ptr & vt, 
             const elementa::base::SerChLoc::Ptr & l): kind{Kind::kMatch}, 
                                                       loc{l},
                                                       info{vt} 
        {ELE_CODE_TRACE_OFF; 
            ELE_CODE_TRACE({},"StepInfo::(ma)constr.Creating match SI this =" <<
                              elementa::base::to_number(this)); }
 
    StepInfo(const CFGrammar::RuleIterator & ri,
             const elementa::base::SerChLoc::Ptr & l): kind{Kind::kRule}, 
                                                       loc{l},
                                                       info{ri}
        {ELE_CODE_TRACE_OFF; 
            ELE_CODE_TRACE({},"StepInfo::(ri)constr. Creating rule SI this =" <<
                              elementa::base::to_number(this)); }
 
    StepInfo(const StepInfo & oth): kind{oth.kind}, loc{oth.loc}, info{oth.info}
        {ELE_CODE_TRACE_OFF; ELE_CODE_TRACE({},"StepInfo::copy-constr."); }
 
    StepInfo & operator=(const StepInfo & oth)
        {ELE_CODE_TRACE_OFF;
            ELE_CODE_TRACE({},"StepInfo::assign, oth!=this = " << 
                              (this != &oth));  
            if (this != &oth) 
            { kind = oth.kind; loc = oth.loc; 
              info = oth.info; } return(*this); }
 
    StepInfo(StepInfo && oth):  kind{oth.kind},
                                loc{std::move(oth.loc)},
                                info{std::move(oth.info)}
        {ELE_CODE_TRACE_OFF; ELE_CODE_TRACE({},"StepInfo::move-constr."); }
 
    StepInfo & operator=(StepInfo && oth)
        {ELE_CODE_TRACE_OFF; 
            ELE_CODE_TRACE({},"StepInfo::move-assign, oth!=this = " << 
                              (this != &oth));  
            if (this != &oth) 
            { kind = oth.kind; loc = std::move(oth.loc); 
              info = std::move(oth.info); } return(*this); }
 
    ~StepInfo(void)
        {ELE_CODE_TRACE_OFF; ELE_CODE_TRACE({},"StepInfo::destructor of " <<
                              elementa::base::to_number(this)); }
 
    bool operator==(const StepInfo & o) const
        { return((kind == o.kind)&&(*loc == *(o.loc))&&
                 (kind == Kind::kMatch ? (*info.vt) == (*(o.info.vt)) :
                                         (*info.rit) == (*(o.info.rit)))); }
 
    bool operator!=(const StepInfo & o) const { return(!operator==(o)); }
 
    std::string to_string(const CFGrammar & gr) const;
 
};
 
 
/* **********************************************************************
 
    Class: ErrorInfo
 
*************************************************************************/
 
 
class ErrorInfo final
{
 public:
 
    ELE_CLASS_ENUM(Kind,
                    kUnexpTerminal,     
                    kEmptyTable         
                  );
 
    using UnexpectedTerminal = std::pair< CFGrammar::CodeElement, Token::Ptr >;
 
 
    Kind kind; 
    elementa::base::SerChLoc::Ptr loc; 
 
 
    struct Info
    {
        UnexpectedTerminal unexppair;
 
        CFGrammar::LL1TableIndex emptytableindex;
 
        Info(const CFGrammar::LL1TableIndex & ti): emptytableindex{ti}
            {}
 
        Info(const UnexpectedTerminal & ut): unexppair{ut} 
            {}
    
        Info(const Info & oth) = default;
        Info(Info && oth) = default;
        Info & operator=(const Info & oth) = default;
        Info & operator=(Info && oth) = default;        
        ~Info(void) = default;
 
    } info; // error content
 
    ErrorInfo(const CFGrammar::LL1TableIndex & ti,
              const elementa::base::SerChLoc::Ptr & l):
                kind{Kind::kEmptyTable},
                loc{l},
                info{ti} {}
 
    ErrorInfo(const UnexpectedTerminal & ut,
              const elementa::base::SerChLoc::Ptr & l):
                kind{Kind::kUnexpTerminal},
                loc{l},
                info{ut} {}
 
    ErrorInfo(const ErrorInfo & oth):
                kind{oth.kind},
                loc{oth.loc},
                info{oth.info}
        {}
 
    ErrorInfo & operator=(const ErrorInfo & oth)
        { if (this!=&oth) 
          { kind = oth.kind; loc = oth.loc; info = oth.info; } return(*this); }
 
    ErrorInfo(ErrorInfo && oth):
                kind{oth.kind},
                loc{std::move(oth.loc)},
                info{std::move(oth.info)}
        {}
 
    ErrorInfo & operator=(ErrorInfo && oth)
        { if (this!=&oth)
          { kind = oth.kind; loc = std::move(oth.loc); 
            info = std::move(oth.info); } return(*this); }
 
    ~ErrorInfo(void)
        {ELE_CODE_TRACE_OFF; ELE_CODE_TRACE({},"ErrorInfo::destructor"); }
 
    bool operator==(const ErrorInfo & o) const
        { return((kind == o.kind)&&(*loc == *(o.loc))&&
                 (kind == Kind::kUnexpTerminal ? 
                    (
                        (info.unexppair.first == o.info.unexppair.first) &&
                        (*info.unexppair.second == *o.info.unexppair.second)
                    ):
                    (info.emptytableindex == o.info.emptytableindex))); }
 
    bool operator!=(const ErrorInfo & o) const { return(!operator==(o)); }
 
 
    std::string to_string(const CFGrammar & gr) const;
 
};
 
 
/* **********************************************************************
 
    Abstract Base Class: Parser
 
*************************************************************************/
 
 
class Parser
{
 public:
 
    ELE_CLASS_ENUM(Result,
                    kFinished,  
                    kMoreSteps, 
                    kNotInTable,
                    kMismatch   
                  );
 
 
    class Observer
    {
     public:
 
 
        virtual void okStep(const StepInfo & i, Parser & p) = 0;
 
 
        virtual void errorStep(const ErrorInfo & e, Parser & p) = 0;
    };
 
 
    using TransfTokenId = std::function< void(Token &) >;
 
 
    Parser(const CFGrammar & gr, Lexer & lex, 
           const TransfTokenId & transftid = [](Token &)->void{} ):
                                    gr_{gr},lexer_{lex},transftid_{transftid} {}
 
    Parser(const Parser &) = delete;
    Parser & operator=(const Parser &) = delete;    
    Parser(Parser &&) = delete;
    Parser & operator=(Parser &&) = delete;
 
    Parser(void) = default; 
 
    const CFGrammar & grammar(void) const noexcept { return(gr_); }
 
    Lexer & lexer(void) const noexcept { return(lexer_); }
 
    virtual void reset(void) = 0;
 
 
    void parse(Observer & obs);
 
 
    virtual Result parseStep(Observer & obs) = 0;
 
    virtual void printStatus(elementa::base::OutSerCh & chout) const = 0;
 
 protected:
 
    const CFGrammar & gr_;
    Lexer & lexer_;
    TransfTokenId transftid_;
};
 
 
/* **********************************************************************
 
    Class: AST
 
*************************************************************************/
 
 
class AST: public elementa::adts::Tree<StepInfo,char>
{
 public:
 
    using VertexData = StepInfo;
 
    using EdgeData = char;
 
    using BaseGraph = elementa::adts::graphs::Graph<VertexData,EdgeData>;
 
    using BaseTree = typename elementa::adts::Tree<VertexData,EdgeData>;
 
 
    template <template <class,class> class Gr>
    using GraphImpl = Gr<VertexData,EdgeData>;
 
 
    static BaseGraph::VRange_Pred::Pred kPredTerminal; 
 
    using BaseTree::BaseTree;
 
 
    const StepInfo & edgeEnd(const BaseGraph::eiterator & eit) const;
 
 
    const std::string & edgeEndMatch(const BaseGraph::eiterator & eit,
                                     CFGrammar::CodeElement c) const;
 
 
    const CFGrammar::Rule & edgeEndRule(const BaseGraph::eiterator & eit,
                                        CFGrammar::CodeElement c) const;
 
 
    void moveToNextMatch(BaseGraph::eiterator & eit) const;
 
 
    void moveToNextRule(BaseGraph::eiterator & eit) const;
 
};
 
 
/* **********************************************************************
 
    Class: ASTObserver
 
*************************************************************************/
 
 
class ASTObserver: public Parser::Observer
{
 public:
 
 
    ASTObserver(const AST::BaseTree::BGraph & exemplar):ast_{exemplar} {}
 
    void okStep(const StepInfo & i, Parser & p);
 
    void errorStep(const ErrorInfo & e, Parser & p)
        { ELE_CODE_UNIMPLEMENTED; }
 
 
    AST & ast(void) { return(ast_); }
 
 
    typename AST::Ptr lastSubtree(void) 
    { return(pendingtrees_.empty() ? typename AST::Ptr{} :
                                     pendingtrees_.back()); }
 
 private:
 
    typename AST::Forest pendingtrees_; // pointers to trees, actually
    AST ast_;
};
 
 // Parsing
 
} // End parsing namespace
 
} // End elementa namespace 
 
 
#endif