parser.h

Full support for extended regular expressions (those with intersection and complement); Support for

		{
			int number() const { return 19; }
			
			TerminalComma *a10;
		};
		struct IteratorI : PairIterator<NonterminalOptionStatement::BodyIa, NonterminalOptionStatement::BodyIb>
		{
			int number() const { return 20; }
		};
		
		int number() const { return 5; }
		
		TerminalId *left;
		TerminalAssign *a2;
		std::vector<Terminal *> right;
		std::vector<TerminalComma *> a10;
		TerminalSemicolon *a11;
	};
	struct NonterminalInvalidStatement : Nonterminal
	{
		int number() const { return 6; }
		
		TerminalError *a1;
		TerminalSemicolon *a2;
	};
	struct NonterminalExpression : Nonterminal
	{
		int number() const { return 7; }
		virtual int alternative_number() const =0;
		
	enum ExpansionStatus
	{
		NOT_EXPANDED, EXPANDED, CANNOT_BE_EXPANDED, TRIVIALLY_EXPANDED
	};
	ExpansionStatus expansion_status;
	UnionOfIntervals<int> *expanded; // !=NULL <==> expansion_status==EXPANDED
	NonterminalExpression()
	{
		expansion_status=NOT_EXPANDED;
		expanded=NULL;
	}

	};
	struct NonterminalExpressionDisjunction : NonterminalExpression
	{
		int alternative_number() const { return 0; }
		
		NonterminalExpression *expr1;
		NonterminalExpression *expr2;
	};
	struct NonterminalExpressionConjunction : NonterminalExpression
	{
		int alternative_number() const { return 1; }
		
		NonterminalExpression *expr1;
		NonterminalExpression *expr2;
	};
	struct NonterminalExpressionConcatenation : NonterminalExpression
	{
		int alternative_number() const { return 2; }
		
		NonterminalExpression *expr1;
		NonterminalExpression *expr2;
	};
	struct NonterminalExpressionComplement : NonterminalExpression
	{
		int alternative_number() const { return 3; }
		
		NonterminalExpression *expr;
	};
	struct NonterminalExpressionOmittable : NonterminalExpression
	{
		int alternative_number() const { return 4; }
		
		NonterminalExpression *expr;
	};
	struct NonterminalExpressionInParentheses : NonterminalExpression
	{
		int alternative_number() const { return 5; }
		
		NonterminalExpression *expr;
	};
	struct NonterminalExpressionIteration : NonterminalExpression
	{
		int alternative_number() const { return 6; }
		
		NonterminalExpression *expr;
		Terminal *sign;
		 bool reflexive; 
	};
	struct NonterminalExpressionCondition : NonterminalExpression
	{
		int alternative_number() const { return 7; }
		
		NonterminalExpressionC *condition;
	};
	struct NonterminalExpressionRange : NonterminalExpression
	{
		int alternative_number() const { return 8; }
		
		Terminal *range_kw;
		NonterminalExpressionS *first_expr;
		NonterminalExpressionS *last_expr;
		 int first, last; 
	};
	struct NonterminalExpressionContains : NonterminalExpression
	{
		int alternative_number() const { return 9; }
		
		TerminalKwContains *a1;
		NonterminalExpression *expr;
	};
	struct NonterminalExpressionEpsilon : NonterminalExpression
	{
		int alternative_number() const { return 10; }
	};
	struct NonterminalExpressionSymbol : NonterminalExpression
	{
		int alternative_number() const { return 11; }
		
		NonterminalExpressionS *expr;
	};
	struct NonterminalExpressionSharpSign : NonterminalExpression
	{
		int alternative_number() const { return 12; }
		
		TerminalSharpSign *op;
	};
	struct NonterminalExpressionS : Nonterminal
	{
		int number() const { return 8; }
		
		Terminal *symbol;
		
	bool is_nts; // true if it is a nonterminal symbol
	int nn; // nonterminal number, if it is a nonterminal
	std::vector<int> s; // a string of terminals, if it isn't a nonterminal
	NonterminalExpressionS()
	{
		is_nts=false;
		nn=-1;
	}

	};
	struct NonterminalExpressionC : Nonterminal
	{
		int number() const { return 9; }
		virtual int alternative_number() const =0;
	};
	struct NonterminalExpressionC_Disjunction : NonterminalExpressionC
	{
		int alternative_number() const { return 0; }
		
		NonterminalExpressionC *expr1;
		NonterminalExpressionC *expr2;
	};
	struct NonterminalExpressionC_Conjunction : NonterminalExpressionC
	{
		int alternative_number() const { return 1; }
		
		NonterminalExpressionC *expr1;
		NonterminalExpressionC *expr2;
	};
	struct NonterminalExpressionC_Complement : NonterminalExpressionC
	{
		int alternative_number() const { return 2; }
		
		NonterminalExpressionC *expr;
	};
	struct NonterminalExpressionC_InParentheses : NonterminalExpressionC
	{
		int alternative_number() const { return 3; }
		
		NonterminalExpressionC *expr;
	};
	struct NonterminalExpressionC_Comparison : NonterminalExpressionC
	{
		int alternative_number() const { return 4; }
		
		NonterminalExpressionS *left;
		Terminal *comparison_operator;
		NonterminalExpressionS *right;
		
	enum Operation { EQ, NE, LT, LE, GT, GE };
	static Operation swap_operands(Operation op)
	{
		if(op==EQ) return EQ;
		else if(op==NE) return NE;
		else if(op==LT) return GT;
		else if(op==LE) return GE;
		else if(op==GT) return LT;
		else if(op==GE) return LE;
		else throw op;
	}
	static const char *operation_to_s(Operation op)
	{
		if(op==EQ) return "==";
		else if(op==NE) return "!=";
		else if(op==LT) return "<";
		else if(op==LE) return "<=";
		else if(op==GT) return ">";
		else if(op==GE) return ">=";
		else throw op;
	}
	// it means the expression can be rewritten as
	// 'c actual_operation symbol'
 	int symbol;
 	Operation actual_operation;

	};
	struct NonterminalExpressionC_In : NonterminalExpressionC
	{
		int alternative_number() const { return 5; }
		
		NonterminalExpressionS *c;
		TerminalId *symbol;
		 int nn; 
	};
	struct NonterminalExpressionC_Constant : NonterminalExpressionC
	{
		int alternative_number() const { return 6; }
		
		Terminal *true_or_false;
		 bool value; 
	};
	struct NonterminalPairOfExpressions : Nonterminal
	{
		int number() const { return 10; }
		
		NonterminalExpression *expr;
		NonterminalExpression *lookahead;
		TerminalNot *not_eof;
		TerminalKwEof *eof;
	};
	struct NonterminalStartConditionsExpression : Nonterminal
	{
		struct BodyIa : Nonterminal
		{
			int number() const { return 21; }
			
			TerminalId *names;
		};
		struct BodyIb : Nonterminal
		{
			int number() const { return 22; }
		};
		struct IteratorI : PairIterator<NonterminalStartConditionsExpression::BodyIa, NonterminalStartConditionsExpression::BodyIb>
		{
			int number() const { return 23; }
		};
		
		int number() const { return 11; }
		virtual int alternative_number() const =0;
	};
	struct NonterminalStartConditionsExpressionList : NonterminalStartConditionsExpression
	{
		int alternative_number() const { return 0; }
		
		std::vector<TerminalId *> names;
	};
	struct NonterminalStartConditionsExpressionAsterisk : NonterminalStartConditionsExpression
	{
		int alternative_number() const { return 1; }
		
		TerminalLoneAsterisk *a1;
	};
	struct NonterminalAction : Nonterminal
	{
		int number() const { return 12; }
		virtual int alternative_number() const =0;
	};
	struct NonterminalActionReturn : NonterminalAction
	{
		int alternative_number() const { return 0; }
		
		TerminalKwReturn *kw;
		Terminal *return_value;
		TerminalSemicolon *a6;
	};
	struct NonterminalActionSkip : NonterminalAction
	{
		int alternative_number() const { return 1; }
		
		TerminalKwSkip *kw;
		TerminalSemicolon *a2;
	};
	struct NonterminalActionCodeII : NonterminalAction
	{
		int alternative_number() const { return 2; }
		
		TerminalCode *code;
		TerminalSemicolon *semicolon;
		 std::string s; 
	};
	
	class Parser
	{
		static const char *whale_copyright_notice;
		
	public:
		static const int assumed_number_of_bits_in_int=32;
		static const int number_of_terminals=46;
		static const int number_of_nonterminals=24;
		static const int number_of_lr_states=163;
		static const int number_of_rules=88;
		static const int compressed_action_table_size=1015;
		static const int compressed_action_error_map_size=64;
		static const int compressed_goto_table_size=120;
		static const int eof_terminal_number=0;
		static const int error_terminal_number=1;
		
	protected:
		class LRAction
		{
			int n;
			
		public:
			LRAction(int supplied_n=0) { n=supplied_n; }
			
			bool is_error() const { return !n; }
			bool is_accept() const { return n==1; }
			bool is_shift() const { return n<0; }
			bool is_reduce() const { return n>=2; }
			int shift_state() const { return -n-1; }
			int reduce_rule() const { return n-1; }
			int get_n() const { return n; }
			static LRAction error() { return LRAction(0); }
			static LRAction accept() { return LRAction(1); }
			static LRAction shift(int state) { return LRAction(-state-1); }
			static LRAction reduce(int rule) { return LRAction(rule+1); }
		};
		struct StateData
		{
			bool sole_action;
			union { int index_in_action_table, action_value; };
			int index_in_action_error_map;
			int index_in_goto_table;
		};
		struct RuleData
		{
			int nn;
			int length;
		};
		
		static const StateData states[number_of_lr_states];
		static const RuleData rules[number_of_rules];
		static const int compressed_action_table[compressed_action_table_size];
		static const unsigned int compressed_action_error_map[compressed_action_error_map_size];
		static const int compressed_goto_table[compressed_goto_table_size];
		
	public:
		Parser(DolphinLexicalAnalyzer &lexical_analyzer_supplied) : lexical_analyzer(lexical_analyzer_supplied), m_debug(false)
		{
		}
		bool debug() const { return m_debug; }
		void debug(bool b) { m_debug = b; }
		~Parser();
		void initialize();
		NonterminalS *parse();
		void report_error(std::ostream &os, const Terminal *t) const;
		bool recover_from_error();
		void print_stack(std::ostream &os) const;
		
	protected:
		DolphinLexicalAnalyzer &lexical_analyzer;
		Terminal *input_symbol;
		std::vector<int> state_stack;
		std::vector<Symbol *> symbol_stack;
		std::vector<Symbol *> garbage;
		bool m_debug;
		
		LRAction access_action_table(int state, int tn) const
		{
			if(!access_error_map(compressed_action_error_map + states[state].index_in_action_error_map, tn))
				return LRAction::error();
			if(states[state].sole_action)
				return states[state].action_value;
			return LRAction(compressed_action_table[states[state].index_in_action_table+tn]);
		}
		bool access_error_map(const unsigned int *map, int n) const
		{
			return map[n/assumed_number_of_bits_in_int] & (1 << (n%assumed_number_of_bits_in_int));
		}
		int access_goto_table(int state, int nn) const
		{
			return compressed_goto_table[states[state].index_in_goto_table + nn];
		}
		int find_nonterminal_in_stack(int nn) const
		{
			for(int i=symbol_stack.size()-1; i>=0; i--)
				if(symbol_stack[i]->is_nonterminal())
				{
					Nonterminal *n=(Nonterminal *)symbol_stack[i];
					if(n->number()==nn)
						return i;
				}
			return -1;
		}
	};
	
	template<class T> std::vector<T> deepen(const T &x)
	{
		return std::vector<T>(1, x);
	}
	
	std::ostream &print_terminal_location(std::ostream &os, const Terminal *t);
	
} // namespace Whale

typedef Whale::Parser WhaleParser;

#endif