/////////////////////////////////////////////////////////////////////////////// // This file is generated automatically using Prop (version 2.3.0), // last updated on Feb 5, 1997. // The original source file is "exp.pC". /////////////////////////////////////////////////////////////////////////////// #define PROP_REWRITING_USED #define PROP_PRINTER_USED #define PROP_REGEXP_MATCHING_USED #define PROP_EQUALITY_USED #define PROP_PARSER_USED #define PROP_QUARK_USED #include ////////////////////////////////////////////////////////////////////////////// // // This example program performs idiom matching on a simple expression // language. We'll also define a parser to parses an expression // from the input. // /////////////////////////////////////////////////////////////////////////////// #include #include #include #include /////////////////////////////////////////////////////////////////////////////// // // First, we define the type Exp to represent // our expressions. Identifiers (type Id) are represented as // atomic strings so that equality testing can be done quickly. // // We also use pretty printing annotations to // indicate to Prop to generate a simple print routine. // /////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////// // Forward class definition for Exp /////////////////////////////////////////////////////////////////////////////// #ifndef datatype_Exp_defined #define datatype_Exp_defined typedef class a_Exp * Exp; #endif /////////////////////////////////////////////////////////////////////////////// // Class hierarchy for datatype Exp /////////////////////////////////////////////////////////////////////////////// class a_Exp; // base class for datatype Exp class Exp_Int; // subclass for 'Int int' class Exp_Id; // subclass for 'Id Quark const &' class Exp_Add; // subclass for 'Add (Exp, Exp)' class Exp_Sub; // subclass for 'Sub (Exp, Exp)' class Exp_Mul; // subclass for 'Mul (Exp, Exp)' class Exp_Div; // subclass for 'Div (Exp, Exp)' class Exp_Sqr; // subclass for 'Sqr Exp' class Exp_MulAdd; // subclass for 'MulAdd (Exp, Exp, Exp)' class Exp_Neg; // subclass for 'Neg Exp' /////////////////////////////////////////////////////////////////////////////// // Base class for datatype 'Exp' /////////////////////////////////////////////////////////////////////////////// class a_Exp : public TermObj { public: enum Tag_Exp { tag_Int = 0, tag_Id = 1, tag_Add = 2, tag_Sub = 3, tag_Mul = 4, tag_Div = 5, tag_Sqr = 6, tag_MulAdd = 7, tag_Neg = 8 }; protected: const Tag_Exp _tag_; inline a_Exp(Tag_Exp _t_) : _tag_(_t_) {} public: inline int untag() const { return _tag_; } inline friend int boxed(const a_Exp * x) { return 1; } inline friend int untag(const a_Exp * x) { return x->_tag_; } //////////////////////////////////////////////////////////////////////////// // Downcasting functions for Exp //////////////////////////////////////////////////////////////////////////// inline friend Exp_Int * _Int(Exp _x_) { return (Exp_Int *)_x_; } inline friend Exp_Id * _Id(Exp _x_) { return (Exp_Id *)_x_; } inline friend Exp_Add * _Add(Exp _x_) { return (Exp_Add *)_x_; } inline friend Exp_Sub * _Sub(Exp _x_) { return (Exp_Sub *)_x_; } inline friend Exp_Mul * _Mul(Exp _x_) { return (Exp_Mul *)_x_; } inline friend Exp_Div * _Div(Exp _x_) { return (Exp_Div *)_x_; } inline friend Exp_Sqr * _Sqr(Exp _x_) { return (Exp_Sqr *)_x_; } inline friend Exp_MulAdd * _MulAdd(Exp _x_) { return (Exp_MulAdd *)_x_; } inline friend Exp_Neg * _Neg(Exp _x_) { return (Exp_Neg *)_x_; } }; /////////////////////////////////////////////////////////////////////////////// // class for constructor 'Exp::Int int' /////////////////////////////////////////////////////////////////////////////// class Exp_Int : public a_Exp { public: int Int; inline Exp_Int (int _xInt) : a_Exp(a_Exp::tag_Int), Int(_xInt) {} inline friend a_Exp * Int (int _xInt) { return new Exp_Int (_xInt); } }; /////////////////////////////////////////////////////////////////////////////// // class for constructor 'Exp::Id Quark const &' /////////////////////////////////////////////////////////////////////////////// class Exp_Id : public a_Exp { public: Quark Id; inline Exp_Id (Quark const & _xId) : a_Exp(a_Exp::tag_Id), Id(_xId) {} inline friend a_Exp * Id (Quark const & _xId) { return new Exp_Id (_xId); } }; /////////////////////////////////////////////////////////////////////////////// // class for constructor 'Exp::Add (Exp, Exp)' /////////////////////////////////////////////////////////////////////////////// class Exp_Add : public a_Exp { public: Exp _1; Exp _2; inline Exp_Add (Exp _x1, Exp _x2) : a_Exp(a_Exp::tag_Add), _1(_x1), _2(_x2) {} inline friend a_Exp * Add (Exp _x1, Exp _x2) { return new Exp_Add (_x1, _x2); } }; /////////////////////////////////////////////////////////////////////////////// // class for constructor 'Exp::Sub (Exp, Exp)' /////////////////////////////////////////////////////////////////////////////// class Exp_Sub : public a_Exp { public: Exp _1; Exp _2; inline Exp_Sub (Exp _x1, Exp _x2) : a_Exp(a_Exp::tag_Sub), _1(_x1), _2(_x2) {} inline friend a_Exp * Sub (Exp _x1, Exp _x2) { return new Exp_Sub (_x1, _x2); } }; /////////////////////////////////////////////////////////////////////////////// // class for constructor 'Exp::Mul (Exp, Exp)' /////////////////////////////////////////////////////////////////////////////// class Exp_Mul : public a_Exp { public: Exp _1; Exp _2; inline Exp_Mul (Exp _x1, Exp _x2) : a_Exp(a_Exp::tag_Mul), _1(_x1), _2(_x2) {} inline friend a_Exp * Mul (Exp _x1, Exp _x2) { return new Exp_Mul (_x1, _x2); } }; /////////////////////////////////////////////////////////////////////////////// // class for constructor 'Exp::Div (Exp, Exp)' /////////////////////////////////////////////////////////////////////////////// class Exp_Div : public a_Exp { public: Exp _1; Exp _2; inline Exp_Div (Exp _x1, Exp _x2) : a_Exp(a_Exp::tag_Div), _1(_x1), _2(_x2) {} inline friend a_Exp * Div (Exp _x1, Exp _x2) { return new Exp_Div (_x1, _x2); } }; /////////////////////////////////////////////////////////////////////////////// // class for constructor 'Exp::Sqr Exp' /////////////////////////////////////////////////////////////////////////////// class Exp_Sqr : public a_Exp { public: Exp Sqr; inline Exp_Sqr (Exp _xSqr) : a_Exp(a_Exp::tag_Sqr), Sqr(_xSqr) {} inline friend a_Exp * Sqr (Exp _xSqr) { return new Exp_Sqr (_xSqr); } }; /////////////////////////////////////////////////////////////////////////////// // class for constructor 'Exp::MulAdd (Exp, Exp, Exp)' /////////////////////////////////////////////////////////////////////////////// class Exp_MulAdd : public a_Exp { public: Exp _1; Exp _2; Exp _3; inline Exp_MulAdd (Exp _x1, Exp _x2, Exp _x3) : a_Exp(a_Exp::tag_MulAdd), _1(_x1), _2(_x2), _3(_x3) {} inline friend a_Exp * MulAdd (Exp _x1, Exp _x2, Exp _x3) { return new Exp_MulAdd (_x1, _x2, _x3); } }; /////////////////////////////////////////////////////////////////////////////// // class for constructor 'Exp::Neg Exp' /////////////////////////////////////////////////////////////////////////////// class Exp_Neg : public a_Exp { public: Exp Neg; inline Exp_Neg (Exp _xNeg) : a_Exp(a_Exp::tag_Neg), Neg(_xNeg) {} inline friend a_Exp * Neg (Exp _xNeg) { return new Exp_Neg (_xNeg); } }; ostream& operator << (ostream&,Exp); ostream& pretty_print(ostream&,Exp,int = 0,int = 0); /////////////////////////////////////////////////////////////////////////////// // Pretty printer for type Exp /////////////////////////////////////////////////////////////////////////////// ostream& pretty_print(ostream& _f_, Exp _x_, int _tab_, int _prec_) { switch (untag(_x_)) { case a_Exp::tag_Int: _f_ << _Int(_x_)->Int; break; case a_Exp::tag_Id: _f_ << _Id(_x_)->Id; break; case a_Exp::tag_Add: _f_ << "("; pretty_print(_f_, _Add(_x_)->_1, _tab_, _prec_); _f_ << " + "; pretty_print(_f_, _Add(_x_)->_2, _tab_, _prec_); _f_ << ")"; break; case a_Exp::tag_Sub: _f_ << "("; pretty_print(_f_, _Sub(_x_)->_1, _tab_, _prec_); _f_ << " - "; pretty_print(_f_, _Sub(_x_)->_2, _tab_, _prec_); _f_ << ")"; break; case a_Exp::tag_Mul: _f_ << "("; pretty_print(_f_, _Mul(_x_)->_1, _tab_, _prec_); _f_ << " * "; pretty_print(_f_, _Mul(_x_)->_2, _tab_, _prec_); _f_ << ")"; break; case a_Exp::tag_Div: _f_ << "("; pretty_print(_f_, _Div(_x_)->_1, _tab_, _prec_); _f_ << " / "; pretty_print(_f_, _Div(_x_)->_2, _tab_, _prec_); _f_ << ")"; break; case a_Exp::tag_Sqr: _f_ << "sqr("; pretty_print(_f_, _Sqr(_x_)->Sqr, _tab_, _prec_); _f_ << ")"; break; case a_Exp::tag_MulAdd: _f_ << "muladd("; pretty_print(_f_, _MulAdd(_x_)->_1, _tab_, _prec_); _f_ << ", "; pretty_print(_f_, _MulAdd(_x_)->_2, _tab_, _prec_); _f_ << ", "; pretty_print(_f_, _MulAdd(_x_)->_3, _tab_, _prec_); _f_ << ")"; break; case a_Exp::tag_Neg: _f_ << "neg("; pretty_print(_f_, _Neg(_x_)->Neg, _tab_, _prec_); _f_ << ")"; break; } return _f_; } ostream& operator << (ostream& _f_, Exp _x_) { return pretty_print(_f_,_x_); } /////////////////////////////////////////////////////////////////////////////// // // Next, we define the set of symbols used for our Exp parser. // /////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////// // Definition of datatype 'ExpToken' /////////////////////////////////////////////////////////////////////////////// enum ExpToken { XXflXX = 256, XXfnXX = 257, XXciXX = 258, XXcjXX = 259, XXckXX = 260, XXclXX = 261, XXcnXX = 262, XXcpXX = 263, XXdlXX = 264, ID = 265, INT = 266 }; ostream& operator << (ostream&,ExpToken); ostream& pretty_print(ostream&,ExpToken,int = 0,int = 0); /////////////////////////////////////////////////////////////////////////////// // // Next, we declare the interface of the parser. // /////////////////////////////////////////////////////////////////////////////// class ExpParser : public LR1Parser { public: //////////////////////////////////////////////////////////////////////////// // Parser table type definitions //////////////////////////////////////////////////////////////////////////// typedef LR1Parser Super; typedef Super::Offset Offset; typedef Super::State State; typedef Super::Rule Rule; typedef Super::Symbol Symbol; typedef Super::ProductionLength ProductionLength; typedef Super::ShortSymbol ShortSymbol; typedef Super::EquivMap EquivMap; enum { INITIAL_STACK_SIZE_ = 256, MAX_STACK_SIZE_ = 8192 }; protected: //////////////////////////////////////////////////////////////////////////// // Semantic value stack //////////////////////////////////////////////////////////////////////////// union ExpParser_semantic_stack_type * t__, * bot__; int stack_size__; int heap_allocated__; public: //////////////////////////////////////////////////////////////////////////// // Constructor and parsing method //////////////////////////////////////////////////////////////////////////// ExpParser(); virtual void parse(); void action_driver(const Rule); private: void adjust_stack(int); void grow_semantic_stack(); IOLexerBuffer lexbuf; public: int get_token(); // retrieve a token void process (Exp); // process a Exp }; /////////////////////////////////////////////////////////////////////////////// // // The lexer simply returns the tokens one by one; it also skip over the // spaces and newlines. If any unrecognized tokens are encountered, // the program will terminate. // /////////////////////////////////////////////////////////////////////////////// int ExpParser::get_token() { { for (;;) { { static const DFATables::Offset _X1_base [ 15 ] = { 0, 0, 0, 1, 0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 0 }; static const DFATables::State _X1_check [ 31 ] = { 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 3, 1, 1, 1, 3, 7, 0, 0, 0, 0, 0, 0, 0, 0 }; static const DFATables::State _X1_next [ 31 ] = { 0, 0, 14, 0, 14, 0, 14, 13, 12, 11, 10, 9, 8, 7, 3, 6, 3, 3, 5, 4, 3, 3, 7, 0, 0, 0, 0, 0, 0, 0, 0 }; static const DFATables::State _X1_def [ 15 ] = { 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; static const unsigned char _X1_equiv_classes [ 256 ] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 6, 5, 5, 5, 5, 5, 5, 5, 7, 8, 9, 10, 5, 11, 5, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 15, 14, 14, 14, 14, 14, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 18, 17, 19, 17, 17, 17, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21 }; static const DFATables::Rule _X1_accept_rule [ 15 ] = { -1, 0, 0, 10, -3, -2, -10, 11, -9, -8, -7, -6, -5, -4, -13 }; static const RegexMatch _X1 ( _X1_base, _X1_check, _X1_def, _X1_next, _X1_accept_rule, _X1_equiv_classes ); int rule__; const char * next; switch(rule__ = _X1.MatchText(RegexMatch::start_state,lexbuf,next)) { case 1: { L2:; return ((ExpToken)(rule__ + 255)); } break; case 2: { goto L2; } break; case 3: { goto L2; } break; case 4: { goto L2; } break; case 5: { goto L2; } break; case 6: { goto L2; } break; case 7: { goto L2; } break; case 8: { goto L2; } break; case 9: { goto L2; } break; case 10: { goto L2; } break; case 11: { goto L2; } break; case 12: {} break; default: { goto L1; } } } } L1:; } return EOF; } /////////////////////////////////////////////////////////////////////////////// // // The parser is defined below. Notice that the exps are separated // by semi-colons. We call process() to simplify each one. // /////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////// // Encoded parser tables for syntax class ExpParser /////////////////////////////////////////////////////////////////////////////// static const DFATables::Offset ExpParser_base [ 27 ] = { 0, 0, 37, 2, 4, 0, 0, 23, 20, 19, 0, 4, 0, 13, 20, 25, 27, 29, 0, 0, 0, 13, 27, 0, 0, 0, 0 }; static const DFATables::State ExpParser_check [ 74 ] = { 0, 10, 1, 0, 3, 11, 4, 1, 10, 1, 0, 1, 1, 0, 11, 1, 1, 3, 3, 4, 4, 8, 14, 8, 8, 8, 8, 15, 21, 16, 13, 17, 22, 22, 9, 14, 14, 7, 2, 0, 15, 15, 16, 16, 17, 17, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; static const DFATables::State ExpParser_next [ 74 ] = { 0, 0, 2, 0, 0, 0, 0, 3, 16403, 4, 0, 16389, 16390, 0, 16404, 7, 8, 0, 10, 0, 11, 16397, 0, 14, 15, 16, 17, 0, 16410, 0, 21, 0, 16, 17, 16402, 0, 22, 12, 9, 0, 0, 23, 0, 16408, 0, 16409, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5520 }; static const DFATables::State ExpParser_def [ 27 ] = { 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 8, 8, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 22, 0, 0, 0 }; static const DFATables::State ExpParser_defact [ 27 ] = { 0, 32768, 0, 0, 0, 32777, 32778, 0, 0, 32768, 0, 0, 32780, 32779, 0, 0, 0, 0, 32770, 32775, 32776, 32768, 32771, 32772, 32773, 32774, 32769 }; static const DFATables::ProductionLength ExpParser_len [ 13 ] = { 0, 4, 3, 3, 3, 3, 3, 3, 3, 1, 1, 0, 2 }; static const DFATables::ProductionLength ExpParser_ncount [ 13 ] = { 0, 3, 1, 2, 2, 2, 2, 1, 1, 0, 0, 0, 1 }; static const DFATables::ShortSymbol ExpParser_lhs [ 13 ] = { 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 17, 18 }; static const DFATables::EquivMap ExpParser_equiv [ 274 ] = { 14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 10, 7, 8, 5, 3, 4, 6, 1, 11, 12, 2, 0, 15, 16, 17, 18 }; /////////////////////////////////////////////////////////////////////////////// // Debugging tables for syntax class ExpParser /////////////////////////////////////////////////////////////////////////////// #ifdef DEBUG_ExpParser static const int ExpParser_line[] = { 0, 0, 0, 98, 99, 100, 101, 102, 103, 104, 105, 94, 0 }; static const char * const ExpParser_symbolname[] = { "???", "\";\"", "?", "\"+\"", "\"-\"", "\"*\"", "\"/\"", "\"(\"", "\")\"", "\"[\"", "\"]\"", "ID", "INT", "???", "???", "command", "exp", "???", "???" }; static const DFATables::ShortSymbol ExpParser_rhs_0[] = { -1 }; static const DFATables::ShortSymbol ExpParser_rhs_1[] = { 16, 1, 17, 15, -1 }; static const DFATables::ShortSymbol ExpParser_rhs_2[] = { 2, 1, 15, -1 }; static const DFATables::ShortSymbol ExpParser_rhs_3[] = { 16, 3, 16, -1 }; static const DFATables::ShortSymbol ExpParser_rhs_4[] = { 16, 4, 16, -1 }; static const DFATables::ShortSymbol ExpParser_rhs_5[] = { 16, 5, 16, -1 }; static const DFATables::ShortSymbol ExpParser_rhs_6[] = { 16, 6, 16, -1 }; static const DFATables::ShortSymbol ExpParser_rhs_7[] = { 7, 16, 8, -1 }; static const DFATables::ShortSymbol ExpParser_rhs_8[] = { 9, 16, 10, -1 }; static const DFATables::ShortSymbol ExpParser_rhs_9[] = { 11, -1 }; static const DFATables::ShortSymbol ExpParser_rhs_10[] = { 12, -1 }; static const DFATables::ShortSymbol ExpParser_rhs_11[] = { -1 }; static const DFATables::ShortSymbol ExpParser_rhs_12[] = { 15, 14, -1 }; static const DFATables::ShortSymbol * ExpParser_rhs[] = { ExpParser_rhs_0, ExpParser_rhs_1, ExpParser_rhs_2, ExpParser_rhs_3, ExpParser_rhs_4, ExpParser_rhs_5, ExpParser_rhs_6, ExpParser_rhs_7, ExpParser_rhs_8, ExpParser_rhs_9, ExpParser_rhs_10, ExpParser_rhs_11, ExpParser_rhs_12 }; #endif /////////////////////////////////////////////////////////////////////////////// // Semantic value stack for syntax class ExpParser /////////////////////////////////////////////////////////////////////////////// union ExpParser_semantic_stack_type { int dummy; typedef Exp ATTRIBUTE_0; ATTRIBUTE_0 _44, _41, _38, _36, _33, _31, _29, _27, _26, _24, _22, _21, _19, _17, _16, _14, _12, _11, _3; }; /////////////////////////////////////////////////////////////////////////////// // Parser driver for syntax class ExpParser /////////////////////////////////////////////////////////////////////////////// inline void ExpParser::action_driver(const Rule _r_) { ExpParser_semantic_stack_type syn_; //////////////////////////////////////////////////////////////////////////// // Tracing code for syntax class ExpParser //////////////////////////////////////////////////////////////////////////// #ifdef DEBUG_ExpParser { cerr << "Reducing via rule " << _r_ << " at line " << ExpParser_line[_r_] << ", " << ExpParser_symbolname[ExpParser_lhs[_r_]] << " <- "; for (const DFATables::ShortSymbol * _p_ = ExpParser_rhs[_r_]; *_p_ >= 0; _p_++) cerr << ExpParser_symbolname[*_p_] << ' '; cerr << '\n'; } #endif //////////////////////////////////////////////////////////////////////////// // Actions for syntax class ExpParser //////////////////////////////////////////////////////////////////////////// t__ -= ExpParser_ncount[_r_]; switch (_r_) { #undef to__ #define to__ 0 #undef to__ #define to__ -1 case 11: { process(t__[1+to__]._3); } break; #undef to__ #define to__ 0 case 3: { syn_._11 = Add(t__[1+to__]._12,t__[2+to__]._14); } break; case 4: { syn_._16 = Sub(t__[1+to__]._17,t__[2+to__]._19); } break; case 5: { syn_._21 = Mul(t__[1+to__]._22,t__[2+to__]._24); } break; case 6: { syn_._26 = Div(t__[1+to__]._27,t__[2+to__]._29); } break; case 7: { syn_._31 = t__[1+to__]._33; } break; case 8: { syn_._36 = t__[1+to__]._38; } break; case 9: { syn_._41 = Id(lexbuf.text()); } break; case 10: { syn_._44 = Int(atol(lexbuf.text())); } break; } if (t__ >= bot__ + stack_size__) grow_semantic_stack(); *++t__ = syn_; } /////////////////////////////////////////////////////////////////////////////// // Parsing method for parser class ExpParser /////////////////////////////////////////////////////////////////////////////// void ExpParser::parse() { ExpParser_semantic_stack_type stack__[INITIAL_STACK_SIZE_]; t__ = bot__ = stack__; stack_size__ = sizeof(stack__)/sizeof(stack__[0]) - 1; heap_allocated__ = 0; parser_prefix(); LR1ParserDriver drv; drv.driver(*this); parser_suffix(); if (bot__ != stack__) delete [] bot__; } void ExpParser::adjust_stack(int offset) { t__ += offset; } void ExpParser::grow_semantic_stack() { int N = (stack_size__ + 1) * 2; ExpParser_semantic_stack_type * S = new ExpParser_semantic_stack_type [N]; if (N >= LR1Parser::SEMANTIC_STACK_SIZE) error_report("Warning: semantic stack overflow"); memcpy(S, bot__, sizeof(ExpParser_semantic_stack_type) * (stack_size__ + 1)); if (heap_allocated__) delete [] bot__; t__ = S + (t__ - bot__); bot__ = S; stack_size__ = N - 1; heap_allocated__ = 1; } /////////////////////////////////////////////////////////////////////////////// // Constructor for parser class ExpParser /////////////////////////////////////////////////////////////////////////////// ExpParser::ExpParser() : Super(ExpParser_base,ExpParser_check,ExpParser_def,ExpParser_defact,ExpParser_next, ExpParser_len,ExpParser_ncount,ExpParser_lhs,ExpParser_equiv,267,267,270) {} /////////////////////////////////////////////////////////////////////////////// // // For processing, we'll define a rewrite class IdiomMatcher // in treeparser mode. It'll take an expression and transform it into // another expression. // /////////////////////////////////////////////////////////////////////////////// class IdiomMatcher : public BURS { private: IdiomMatcher(const IdiomMatcher&); // no copy constructor void operator = (const IdiomMatcher&); // no assignment public: struct IdiomMatcher_StateRec * stack__, * stack_top__; void labeler(Exp redex); inline virtual void operator () (Exp redex) { labeler(redex); } Exp reduce(Exp redex,int lhs = 1); private: public: IdiomMatcher() {} }; /////////////////////////////////////////////////////////////////////////////// // // Within the IdiomMatcher we'll define the tree grammar of the input. // The input only contains integers, identifiers, and the operators // +, -, *, and /. Since this is a simple grammar, we only have one // non-terminal `exp'. // // The idioms that we'll recognize are simply: // // (i) a * (b + c) ==> muladd(a,b,c) // (ii) 0 - a ==> neg(a) // // Notice that the tree grammar is ambiguious; to resolve the ambiguity, // we annotate each production with a cost. The tree parser will // try to locate a derivation with minimal cost. The cost of a // production is the cost of the current rule plus the cost of all // its subderivations. Since the base cost of the production MulAdd is 2 // while the costs of Mul and Add together is 3, the idiom MulAdd // will be choosen whenever possible. // // For example, if the user inputs // // 0 - (a * (b + (0 - c))) // // Then will be transformed into // // neg(muladd(a, b, neg(c)) // // During transformation, the synthesized attributes are written // using the '#' prefix. For example #a refers the synthesized // attribute of the parse associated with the subderivation starting // from 'a'. Note that this is different that just 'a', which refers // to the a-component of the original pattern. The current synthesized // attribute is written as '##'. If the synthesized attribute // and the type of the current redex is the same, then by default // the current redex will be returned as the synthesized attribute. // /////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////// // State record for rewrite class IdiomMatcher /////////////////////////////////////////////////////////////////////////////// struct IdiomMatcher_StateRec { TreeTables::Cost cost[2]; // cost for each non-terminal struct { // accept rule number unsigned int _exp : 4; } rule; }; /////////////////////////////////////////////////////////////////////////////// // Accept rules tables for rewrite class IdiomMatcher /////////////////////////////////////////////////////////////////////////////// const char IdiomMatcher_exp_accept[] = { -1, 7, 6, 5, 4, 3, 2, 1, 0 }; /////////////////////////////////////////////////////////////////////////////// // Closure methods for rewrite class IdiomMatcher /////////////////////////////////////////////////////////////////////////////// void IdiomMatcher::labeler (Exp redex) { int cost__; IdiomMatcher_StateRec * _state_rec = (IdiomMatcher_StateRec *)mem[sizeof(IdiomMatcher_StateRec)]; redex->set_state_rec(_state_rec); _state_rec->cost[0] = 0; _state_rec->cost[1] = 32767; { switch (redex->untag()) { case a_Exp::tag_Int: { // exp -> Int i \ 1: ... cost__ = 1 + 1; if (cost__ < _state_rec->cost[1]) { _state_rec->cost[1] = cost__; _state_rec->rule._exp = 8; }} break; case a_Exp::tag_Id: { // exp -> Id id \ 1: ... cost__ = 1 + 1; if (cost__ < _state_rec->cost[1]) { _state_rec->cost[1] = cost__; _state_rec->rule._exp = 7; }} break; case a_Exp::tag_Add: { labeler(_Add(redex)->_1); labeler(_Add(redex)->_2); // exp -> Add (a as exp, b as exp) \ 1: ... cost__ = 1 + (((IdiomMatcher_StateRec *)_Add(redex)->_1->get_state_rec())->cost[1] + (((IdiomMatcher_StateRec *)_Add(redex)->_2->get_state_rec())->cost[1] + 1)); if (cost__ < _state_rec->cost[1]) { _state_rec->cost[1] = cost__; _state_rec->rule._exp = 6; }} break; case a_Exp::tag_Sub: { labeler(_Sub(redex)->_1); labeler(_Sub(redex)->_2); switch (_Sub(redex)->_1->untag()) { case a_Exp::tag_Int: { if ((_Int(_Sub(redex)->_1)->Int == 0)) { // exp -> Sub (Int _, a as exp) | (_Int(_Sub(redex)->_1)->Int == 0) \ 1: ... cost__ = 1 + (((IdiomMatcher_StateRec *)_Sub(redex)->_2->get_state_rec())->cost[1] + 1); if (cost__ < _state_rec->cost[1]) { _state_rec->cost[1] = cost__; _state_rec->rule._exp = 1; }} else { } } break; default: {} break; } // exp -> Sub (a as exp, b as exp) \ 1: ... cost__ = 1 + (((IdiomMatcher_StateRec *)_Sub(redex)->_1->get_state_rec())->cost[1] + (((IdiomMatcher_StateRec *)_Sub(redex)->_2->get_state_rec())->cost[1] + 1)); if (cost__ < _state_rec->cost[1]) { _state_rec->cost[1] = cost__; _state_rec->rule._exp = 5; }} break; case a_Exp::tag_Mul: { labeler(_Mul(redex)->_1); labeler(_Mul(redex)->_2); switch (_Mul(redex)->_2->untag()) { case a_Exp::tag_Add: { // exp -> Mul (a as exp, Add (b as exp, c as exp)) \ 2: ... cost__ = 2 + (((IdiomMatcher_StateRec *)_Mul(redex)->_1->get_state_rec())->cost[1] + (((IdiomMatcher_StateRec *)_Add(_Mul(redex)->_2)->_1->get_state_rec())->cost[1] + (((IdiomMatcher_StateRec *)_Add(_Mul(redex)->_2)->_2->get_state_rec())->cost[1] + 1))); if (cost__ < _state_rec->cost[1]) { _state_rec->cost[1] = cost__; _state_rec->rule._exp = 2; }} break; default: {} break; } // exp -> Mul (a as exp, b as exp) \ 2: ... cost__ = 2 + (((IdiomMatcher_StateRec *)_Mul(redex)->_1->get_state_rec())->cost[1] + (((IdiomMatcher_StateRec *)_Mul(redex)->_2->get_state_rec())->cost[1] + 1)); if (cost__ < _state_rec->cost[1]) { _state_rec->cost[1] = cost__; _state_rec->rule._exp = 4; }} break; case a_Exp::tag_Div: { labeler(_Div(redex)->_1); labeler(_Div(redex)->_2); // exp -> Div (a as exp, b as exp) \ 2: ... cost__ = 2 + (((IdiomMatcher_StateRec *)_Div(redex)->_1->get_state_rec())->cost[1] + (((IdiomMatcher_StateRec *)_Div(redex)->_2->get_state_rec())->cost[1] + 1)); if (cost__ < _state_rec->cost[1]) { _state_rec->cost[1] = cost__; _state_rec->rule._exp = 3; }} break; case a_Exp::tag_Sqr: { labeler(_Sqr(redex)->Sqr);} break; case a_Exp::tag_MulAdd: { labeler(_MulAdd(redex)->_1); labeler(_MulAdd(redex)->_2); labeler(_MulAdd(redex)->_3);} break; default: { labeler(_Neg(redex)->Neg);} break; } } } Exp IdiomMatcher::reduce(Exp redex,int lhs) { Exp __ = redex; const IdiomMatcher_StateRec * _state_rec = (const IdiomMatcher_StateRec *)(redex->get_state_rec()); int r__; switch (lhs) { case 1: r__ = IdiomMatcher_exp_accept[_state_rec->rule._exp]; break; default: r__ = -1; break; } switch (r__) { case 7: { // Sub (Int _, a as exp) Exp _0__ = reduce(_Sub(redex)->_2,1); // exp cout << "negation idiom found\n"; __ = Neg(_0__); } break; case 6: { // Mul (a as exp, Add (b as exp, c as exp)) Exp _0__ = reduce(_Mul(redex)->_1,1); // exp Exp _1__ = reduce(_Add(_Mul(redex)->_2)->_1,1); // exp Exp _2__ = reduce(_Add(_Mul(redex)->_2)->_2,1); // exp cout << "multiply/add idiom found\n"; __ = MulAdd(_0__,_1__,_2__); } break; case 5: { // Div (a as exp, b as exp) Exp _0__ = reduce(_Div(redex)->_1,1); // exp Exp _1__ = reduce(_Div(redex)->_2,1); // exp __ = Div(_0__,_1__); } break; case 4: { // Mul (a as exp, b as exp) Exp _0__ = reduce(_Mul(redex)->_1,1); // exp Exp _1__ = reduce(_Mul(redex)->_2,1); // exp __ = Mul(_0__,_1__); } break; case 3: { // Sub (a as exp, b as exp) Exp _0__ = reduce(_Sub(redex)->_1,1); // exp Exp _1__ = reduce(_Sub(redex)->_2,1); // exp __ = Sub(_0__,_1__); } break; case 2: { // Add (a as exp, b as exp) Exp _0__ = reduce(_Add(redex)->_1,1); // exp Exp _1__ = reduce(_Add(redex)->_2,1); // exp __ = Add(_0__,_1__); } break; case 1: { // Id id } break; case 0: { // Int i } break; } return __; } /////////////////////////////////////////////////////////////////////////////// // // For processing, we just transform the input formula a bit, // then prints it out. The rules are by no means exhaustive. // /////////////////////////////////////////////////////////////////////////////// void ExpParser::process(Exp exp) { cout << "input = " << exp << '\n'; IdiomMatcher M; M(exp); // construct a tree parse Exp e = M.reduce(exp); // reduces it according to the found derivation. cout << "output = " << e << '\n'; } /////////////////////////////////////////////////////////////////////////////// // // Finally, the main program simply instantiates a copy of the parser, // and invoke the parse method. By default, the input is from // the standard input. // /////////////////////////////////////////////////////////////////////////////// int main() { ExpParser P; P.parse(); exit(0); } /* ------------------------------- Statistics ------------------------------- Merge matching rules = yes Number of DFA nodes merged = 30 Number of ifs generated = 1 Number of switches generated = 4 Number of labels = 1 Number of gotos = 10 Adaptive matching = disabled Fast string matching = disabled Inline downcasts = disabled -------------------------------------------------------------------------- */