#include <set>
#include <unordered_set>
#include <unordered_map>
#include <utility>

template<
	class T,
	class U
>
struct TypeList
{
	typedef T head;
	typedef U tail;
};

struct NullType {};

#define TYPELIST1(T1) TypeList<T1, NullType>
#define TYPELIST2(T1, T2) TypeList<T1, TYPELIST1(T2) >
#define TYPELIST3(T1, T2, T3) TypeList<T1, TYPELIST2(T2, T3) >

//структуры для хранения значений любого типа в стеке
struct AnyHolder {
	virtual ~AnyHolder() {}
};

template <typename T>
struct AnyHolderT: public AnyHolder
{
	T value;

	AnyHolderT(const T& new_value) :
		value(new_value)
	{
		/* пусто */
	}
};

struct Stack {
	std::vector<AnyHolder*> s;

	public:
		struct StackError : public std::exception
		{
			StackError(const std::string& message) //:std::exception(message)
			{
				/* пусто */
			}
		};

		template <typename Attr>
		void pushBack(Attr item)
		{
			s.push_back(new AnyHolderT<Attr>(item));
		}

		template <typename Attr>
		void popBack(Attr& item)
		{
			if (s.empty())
				throw StackError("Stack is empty");

			AnyHolderT<Attr> *h;
			if ((h = dynamic_cast<AnyHolderT<Attr>*>(s.back())) == 0)
				throw StackError("Bad type");

			item = h->value;
			s.pop_back();
			delete h;
		}
};

//структуры для сохранения правил
struct Action {
	virtual void changeStack(Stack&) = 0;

	virtual ~Action() {}
};

template <typename TokenType>
struct AltInfo;

template <typename TokenType>
struct GeneralizedSymbol
{
	bool isTerm;
	AltInfo<TokenType> *nterm;
	TokenType term;

	bool operator==(const GeneralizedSymbol& other) const
	{
		if (this->isTerm != other.isTerm)
			return false;
		if (this->isTerm)
			return this->term == other.term;
		else
			return this->nterm == other.nterm;
	}


	bool operator!=(const GeneralizedSymbol& other) const
	{
		return !(*this == other);
	}
};

namespace std {
	template<typename TokenType>
	struct hash<GeneralizedSymbol<TokenType>>
	{
		size_t operator()(const GeneralizedSymbol<TokenType>& symbol)
		{
			
			if (symbol.isTerm)
				return (int)symbol.term;
			AltInfo<TokenType>* i = symbol.nterm;
			int jS = (int)symbol.nterm;
			return (int)symbol.nterm;
		}
	};
}



template <typename TokenType>
struct SequenceInfo
{
	std::vector<GeneralizedSymbol<TokenType>> symbols;
	Action *action;

	SequenceInfo() :
		action(0)
	{
		/* пусто */
	}
};

template <typename TokenType>
struct AltInfo
{
	std::vector<SequenceInfo<TokenType>> alt;
	bool visited;

	AltInfo()
	{
		visited = false;
	}
};

//тип Rule для определения e
struct Rule {
};

// Промежуточный тип RuleAux, возвращаемый не последним оператором <<
template <
	typename TokenType,
	class TypeList
>
struct RuleAux
{
	SequenceInfo<TokenType> symbols;

	RuleAux(const SequenceInfo<TokenType>& sequence) :
		symbols(sequence)
	{
		/* пусто */
	}
};

// Промежуточный тип TermAux
template <
	typename TokenType,
	typename AttrType
>
struct TermAux
{
	TokenType terminal;

	TermAux(TokenType terminal) :
		terminal(terminal)
	{
		/* пусто */
	}
};

// Промежуточный тип RuleRes, возвращаемый тип последнего оператора <<
template <
	typename TokenType,
	typename AttrType
>
struct RuleRes
{
	SequenceInfo<TokenType> symbols;

	RuleRes(const SequenceInfo<TokenType >& symb) :
		symbols(symb)
	{
		/* пусто */
	}
};

// промежуточный тип Alt, возвращаемый оператором |
template<
	typename TokenType,
	typename Attr
>
struct Alt
{
	AltInfo<TokenType> alt_info;

	Alt(const AltInfo<TokenType>& alts) :
		alt_info(alts)
	{
		/* пусто */
	}
};

// определение типа Term
template<
	typename AttrType,
	typename TokenType
>
TermAux<TokenType, AttrType>
Term(TokenType tokType)
{
	return TermAux<TokenType, AttrType>(tokType);
};

struct Coord
{
	std::string filename;
	int line;
	int col;
};

//Token
template<typename TokenType>
class Token
{
	TokenType token;
	Coord coord;

public:
	Token(TokenType token, Coord coord)
	{
		this->token = token;
		this->coord = coord;
	}

	virtual ~Token() {}

	TokenType tokenType() const
	{
		return token;
	}

	Coord coords() const
	{
		return coord;
	}

	virtual void toStack(Stack&)
	{
		/* На стек ничего не кладём */
	}
};

//AttrToken
template<
	typename TokenType,
	typename AttrType
>
class AttrToken : public Token<TokenType>
{
	AttrType attr;

public:
	AttrToken(TokenType token, AttrType attr, Coord coord) :
		Token(token, coord)
	{
		this->attr = attr;
	}

	virtual void toStack(Stack& stack)
	{
		stack.pushBack(attr);
	}
};

//lexer
template<typename TokenType>
class Lexer
{
	virtual Token<TokenType> *next_token() = 0;
};

//NTerm
template <
	typename TokenType,
	typename Attr
>
struct NTerm
{
	NTerm() {}
	NTerm(Alt<TokenType, Attr> alt) {
		rules = alt.alt_info;
	}
	NTerm(RuleRes<TokenType, Attr> ruleRes) {
		rules.alt.push_back(ruleRes.symbols);
	}
	NTerm(RuleAux<TokenType, TYPELIST1(Attr)> ruleAux) {
		rules.alt.push_back(ruleAux.symbols);
	}
	NTerm(RuleAux<TokenType, NullType> ruleAux) {
		rules.alt.push_back(ruleAux.symbols);
	}
	//для правил A->e
	NTerm(Rule rule) {
		SequenceInfo<TokenType> e;
		rules.alt.push_back(e);
	}

	struct Item
	{
		SequenceInfo<TokenType>* seqInfo;
		//GeneralizedSymbol<TokenType> nextTerm;
		std::unordered_set<GeneralizedSymbol<TokenType>> nextTerms;
		int cursor;

		Item(SequenceInfo<TokenType>* item, int cursor, std::vector<GeneralizedSymbol<TokenType>> nextTerms)
		{
			this->seqInfo = item;

			for (int i = 0; i < nextTerms.size(); i++)
			{
				this->nextTerms.insert(nextTerms[i]);
			}
			this->cursor = cursor;
		}

		bool operator==(const Item& other) const
		{
			bool totallyEqual = false;
			if (nextTerms.size() == other.nextTerms.size())
			{
				totallyEqual = true;
				for (std::unordered_set<GeneralizedSymbol<TokenType>>::iterator i = nextTerms.begin(); i != nextTerms.end(); i++)
				{
					if (other.nextTerms.find(*i) == other.nextTerms.end())
					{
						totallyEqual = false;
						break;
					}
				}
			}			

			return (this->seqInfo == other.seqInfo) && (this->cursor == other.cursor) && (totallyEqual);
		}


		bool operator!=(const Item& other) const
		{
			return !(*this == other);
		}
	};

	struct ItemSet
	{
		std::vector<Item>* set;
		bool isReduced;
	};

	bool First(std::vector<SequenceInfo<TokenType>> chain, std::vector<TokenType>& first)
	{
		bool hasEpsilon = false;

		//если первые n нетерминалов в цепочке порождают (возможно, среди непустых) пустую посл-ть, то добавляем first(n+1-го нетерминала)
		// xSeq = Y1Y2...Yk
		for (std::vector<SequenceInfo<TokenType>>::iterator xSeq = chain.begin(); xSeq != chain.end(); xSeq++)
		{
			//если текущее правило не A->e
			if (xSeq->symbols.size() != 0)
			{
				// для каждого Yj
				for (std::vector<GeneralizedSymbol<TokenType>>::iterator yj = xSeq->symbols.begin(); yj != xSeq->symbols.end(); yj++)
				{
					// если Yj терминал
					if (yj->isTerm)
					{
						bool isAlready = false;
						for (std::vector<TokenType>::iterator term = first.begin(); term != first.end(); term++)
						{
							if (*term == yj->term)
								isAlready = true;
						}
						if (!isAlready)
							first.push_back(yj->term);
						break;
					}
					else // если Yj нетерминал
					{
						if (!First(yj->nterm->alt, first)) // если из текущего Yj не выводится эпсилон, то больше ничего не добавляем к First(X)
							break;
					}
				}
			}
			else //если текущее правило A->e
			{
				hasEpsilon = true;
			}
		}

		return hasEpsilon;
	}

	std::vector<Item> Closure(std::vector<Item> &result, std::vector<Item> itemVector)
	{
		std::vector<Item> itemVectorAux;

		//для каждого пункта [A->...*Bb, a] из I
		for (int i = 0; i < itemVector.size(); i++)
		{
			//sequence = ..*Bb
			std::vector<GeneralizedSymbol<TokenType>>* sequence = &(itemVector[i].seqInfo->symbols);
			
			int cursor = itemVector[i].cursor;
			if (cursor < sequence->size() && !(*sequence)[cursor].isTerm)
			{
				SequenceInfo<TokenType> chain;
				for (int j = cursor + 1; j < sequence->size(); j++)
				{
					chain.symbols.push_back((*sequence)[j]);
				}

				//для каждого терминала из Item.nextTerms
				std::vector<TokenType> firstBa;
				for (std::unordered_set<GeneralizedSymbol<TokenType>>::iterator j = itemVector[i].nextTerms.begin(); j != itemVector[i].nextTerms.end(); j++)
				{
					chain.symbols.push_back(*j);
					//chain = b
					std::vector<SequenceInfo<TokenType>> ba;
					ba.push_back(chain);

					// First(ba)
					std::vector<TokenType> firstBaAux;
					First(ba, firstBaAux);
					firstBa.insert(firstBa.end(), firstBaAux.begin(), firstBaAux.end());
					chain.symbols.pop_back();
				}

				//для каждого правила B->y из G'
				//B = sequence[cursor]
				std::vector<SequenceInfo<TokenType>>* bSeq = &((*sequence)[cursor].nterm->alt);
				//for (std::vector<SequenceInfo<TokenType>>::iterator y = bSeq.begin(); y != bSeq.end(); y++)
				for (int k = 0; k < bSeq->size(); k++)
				{
					std::vector<GeneralizedSymbol<TokenType>> nextTerms;
					GeneralizedSymbol<TokenType> term;
					term.isTerm = true;
					//для каждого терминала b из firstBa
					for (std::vector<TokenType>::iterator b = firstBa.begin(); b != firstBa.end(); b++)
					{
						term.term = *b;
						nextTerms.push_back(term);
					}
					Item newItem(&((*bSeq)[k]), 0, nextTerms);

					// проверяем, существует ли уже такой пункт?
					bool hasAlready = false;
					for (std::vector<Item>::iterator item = itemVector.begin(); !hasAlready && item != itemVector.end(); item++)
					{
						if (*item == newItem)
							hasAlready = true;
					}
					//если нет, добавляем B->*y, b 
					if (!hasAlready)
					{
						itemVectorAux.push_back(newItem);
					}
				}
			}
		}
		result.insert(result.end(), itemVectorAux.begin(), itemVectorAux.end());

		//вызвать closure для нерассмотренных, добавленных пунктов
		if (itemVectorAux.size() != 0)
		{
			std::vector<Item> newItems = Closure(result, itemVectorAux);
			
		}
			
		return itemVectorAux;
	}

	std::vector<Item> Goto(std::vector<Item> i, GeneralizedSymbol<TokenType> x)
	{
		std::vector<Item> j;

		for (std::vector<Item>::iterator item = i.begin(); item != i.end() && item->cursor < (*item->seqInfo).symbols.size(); item++)
		{
			if ((*item->seqInfo).symbols[item->cursor] == x)
			{
				item->cursor++;
				j.push_back(*item);
			}
		}
		Closure(j, j);
		return j;
	}

	std::vector<std::vector<Item>> Items(std::vector<std::vector<Item>> &result, std::vector<std::vector<Item>> c, std::unordered_set<GeneralizedSymbol<TokenType>> allSymbols)
	{
		std::vector<std::vector<Item>> itemsVectorAux;

		for (int i = 0; i < c.size(); i++) // для каждого множества пунктов из с
		{
			for (std::unordered_set<GeneralizedSymbol<TokenType>>::iterator x = allSymbols.begin(); x != allSymbols.end(); x++) // для каждого символа грамматики: как терминала, так и нетерминала
			{
				std::vector<Item> newItemSet = Goto(c[i], *x);
				if (newItemSet.size() > 0)
				{
					//проверяем, содержится ли Goto(c[i], x) уже в с и, если нет, добавляем в с
					bool hasAlready = false, totallyEqual;
					for (std::vector<std::vector<Item>>::iterator itemSet = c.begin(); !hasAlready && itemSet != c.end(); itemSet++)
					{
						totallyEqual = true;
						for (int j = 0; j < itemSet->size() && j < newItemSet.size(); j++)
						{
							if ((*itemSet)[j] != newItemSet[j])
								totallyEqual = false;
						}
						if (totallyEqual && itemSet->size() == newItemSet.size())
							hasAlready = true;
					}
					//если нет, добавляем 
					if (!hasAlready)
					{
						itemsVectorAux.push_back(newItemSet);
					}
				}
			}
		}
		result.insert(result.end(), itemsVectorAux.begin(), itemsVectorAux.end());

		if (itemsVectorAux.size() != 0)
		{
			std::vector<std::vector<Item>> newItems = Items(result, itemsVectorAux, allSymbols);
		}

		return itemsVectorAux;
	}

	void FindAllSymbolsRec(AltInfo<TokenType>& vertex, std::unordered_set<GeneralizedSymbol<TokenType>>& allSymbols)
	{
		//std::unordered_set<GeneralizedSymbol<TokenType>> allSymbols;

		if (!vertex.visited) //если вершину не посещали
		{
			vertex.visited = true;
			//for (std::vector<SequenceInfo<TokenType>>::iterator rule = rules.alt.begin(); rule != rules.alt.end(); rule++)
			for (int i = 0; i < vertex.alt.size(); i++)
			{
				SequenceInfo<TokenType>* rule = &(vertex.alt[i]);
				//for (std::vector<GeneralizedSymbol<TokenType>>::iterator symbol = rule->symbols.begin(); symbol != rule->symbols.end(); symbol++)
				for (int j = 0; j < rule->symbols.size(); j++)
				{
					allSymbols.insert(rule->symbols[j]);
					if (!(rule->symbols[j].isTerm))
					{
						//AltInfo<TokenType>* s = (symbol->nterm);
						FindAllSymbolsRec(*((rule->symbols)[j].nterm), allSymbols);
					}
				}
			}
		}
	}

	std::vector<std::vector<Item>> ReduceItems(std::vector<ItemSet> items)
	{
		std::vector<std::vector<Item>> kernels;

		for (int i = 0; i < items.size() - 1; i++)
		{
			if (!items[i].isReduced)
			{
				std::vector<Item> first = *items[i].set;
				for (int j = i + 1; j < items.size(); j++)
				{
					std::vector<Item> second = *items[j].set;
					//если ядра равны, редуцируем
					if (first.size() == second.size()) // если одинаковое число правил
					{
						bool isTotallyEqual = true;
						std::vector<int> numbers;
						for (int k = 0; k < first.size(); k++)
						{
							bool foundMatch = false;
							for (int g = 0; g < first.size(); g++)
							{
								if (first[k].seqInfo == second[g].seqInfo)
								{
									foundMatch = true;
									numbers.push_back(g);
									break;
								}
							}
							if (foundMatch == false)
								isTotallyEqual = false;
						}

						if (isTotallyEqual)
						{
							items[j].isReduced = true;

							for (int k = 0; k < first.size(); k++)
							{
								for (std::unordered_set<GeneralizedSymbol<TokenType>>::iterator nextTerms = second[numbers[k]].nextTerms.begin(); nextTerms != second[numbers[k]].nextTerms.end(); nextTerms++)
								{
									first[k].nextTerms.insert(*nextTerms);
								}								
							}
						}
					}

				}

				//добавляем first в результирующий вектор
				kernels.push_back(first);
			}
		}

		return kernels;
	}

	struct State
	{
		std::string action;
		Item* item;
		std::vector<Item> gotoItem;
	};

public:
	void parse(Lexer<TokenType> &lexer) {
		//тут строится таблица для lalr(1) анализатора
		//построение мн-ва пунктов: пар (номер правила, положение точки, символ из follow)

		//расширяем грамматику, добавляя правило S' -> S. Стартовый символ - startSymbol
		AltInfo<TokenType> startSymbol;
		SequenceInfo<TokenType> seqInfo;
		GeneralizedSymbol<TokenType> gs;
		gs.isTerm = false;
		gs.nterm = &rules;
		seqInfo.symbols.push_back(gs);
		startSymbol.alt.push_back(seqInfo);

		//добавить в С первое мн-во пунктов = closure({S'->*S, $}) 
		GeneralizedSymbol<TokenType> term;
		term.term = (TokenType)NULL;
		term.isTerm = true;
		std::vector<GeneralizedSymbol<TokenType>> nextTerms;
		nextTerms.push_back(term);
		Item firstItem(&seqInfo, 0, nextTerms);
		std::vector<Item> s;
		s.push_back(firstItem);
		std::vector<std::vector<Item>> c;
		Closure(s, s);
		c.push_back(s);
		std::unordered_set<GeneralizedSymbol<TokenType>> allSymbols;
		FindAllSymbolsRec(startSymbol, allSymbols);
		Items(c, c, allSymbols);
		//построен набор множеств LR(1) пунктов

		// для каждого ядра из мн-ва LR(1) пунктов находим все множества, имеющие это ядро и заменяем их объединением
		std::vector<ItemSet> itemSetVector;
		ItemSet itemSet;
		itemSet.isReduced = false;
		for (int i = 0; i < c.size(); i++)
		{
			itemSet.set = &(c[i]);
			itemSetVector.push_back(itemSet);
		}

		std::vector<std::vector<Item>> kernels = ReduceItems(itemSetVector);

		//добавляем  символ конца строки в allSymbols
		allSymbols.insert(term);

		//строим Action и Goto для состояний
		std::vector<std::unordered_map<GeneralizedSymbol<TokenType>, State>> action;
		for (int i = 0; i < kernels.size(); i++)
		{
			std::unordered_map<GeneralizedSymbol<TokenType>, State> termsState;
			//для всех символов грамматики
			for (std::unordered_set<GeneralizedSymbol<TokenType>>::iterator symbol = allSymbols.begin(); symbol != allSymbols.end(); symbol++)
			{
				if (symbol->isTerm) 
				{
					//для терминала a строим action					
					bool belongs = false;
					//for (std::vector<Item>::iterator rule = kernels[i].begin(); rule != kernels[i].end(); rule++)
					for (int j = 0; j < kernels[i].size(); j++)
					{
						State state;
						Item rule = kernels[i][j];

						if (rule.cursor < (*rule.seqInfo).symbols.size())
						{
							//случай а) //проверяем, входит ли [A->..*aB, b] в Ii и goto(Ii, a) == Ij
							GeneralizedSymbol<TokenType> s = (*rule.seqInfo).symbols[rule.cursor];
							if (s == *symbol)
							{
								//находим goto(Ii, a) = Ij и устанавливаем action "перенос j"
								std::vector<Item> ij = Goto(kernels[i], *symbol)

								state.action = "s";
								state.item = &kernels[i][j];
								std::pair<GeneralizedSymbol<TokenType>, State> pair(*symbol, state);
								termsState.insert(pair);
								belongs = true;
								break;
							}
						}
						else if (rule.seqInfo != &seqInfo)
						{
							// случай  б)
							// ищем, есть ли a среди nextTerms
							bool hasA = false;
							for (std::unordered_set<GeneralizedSymbol<TokenType>>::iterator nextTerm = rule.nextTerms.begin(); nextTerm != rule.nextTerms.end(); nextTerm++)
							{
								if (*nextTerm == *symbol)
								{
									hasA = true;
									break;
								}
							}

							if (hasA)
							{
								state.action = "r";
								state.item = &kernels[i][j];
								std::pair<GeneralizedSymbol<TokenType>, State> pair(*symbol, state);
								termsState.insert(pair);
								belongs = true;
								break;
							}
						}
						else if (rule.seqInfo == &seqInfo)
						{
							// если [S'->S*,$] входит в Ii, установить action[i, $] = ACCEPT							
							state.action = "accept";
							std::pair<GeneralizedSymbol<TokenType>, State> pair(term, state);
							termsState.insert(pair);
							belongs = true;
							break;
						}
						//ошибка
						if (!belongs)
						{
							//std::cout << "ошибка";
						}
					}						
				}
				else
				{
					//для нетерминала строим goto
				}
			}
			action.push_back(termsState);
		}
		/*GeneralizedSymbol<TokenType> x;
		x.isTerm = true;
		x.term = CE;
		std::vector<Item>  jhgfhjgf = Goto(kernels[4], c[0][1].seqInfo->symbols[0]);*/
		//из каждого Ii-го пункта строится состояние i
		//1) если A->a*xb и Goto(Ii, a)= Ij, то Action(i, a) = "перенос j"
		//

		//считываем входящую посл-ть
		/*for (Token<TokenType> newToken = lexer.next_token(); newToken.token != NULL;){

		}*/

		//алгоритм lalr(1) анализа
	}

	AltInfo<TokenType> rules;
};




//перегрузка оператора <<
// Rule() << терминал без атрибута (Rule() << READ)
template<
	typename TokenType
>
RuleAux<TokenType, NullType>
operator<<(Rule, TokenType terminal)
{
	GeneralizedSymbol<TokenType> tok;
	tok.isTerm = true;
	tok.term = terminal;
	SequenceInfo<TokenType> sequence;
	sequence.symbols.push_back(tok);

	return RuleAux<TokenType, NullType>(sequence);
}

// Rule() << терминал с атрибутом
template<
	typename TokenType,
	typename AttrType
>
RuleAux<TokenType, TYPELIST1(AttrType)>
operator<<(Rule, TermAux<TokenType, AttrType> term)
{
	GeneralizedSymbol<TokenType> tok;
	tok.isTerm = true;
	tok.term = term.terminal;
	SequenceInfo<TokenType> sequence;
	sequence.symbols.push_back(tok);

	return RuleAux<TokenType, TYPELIST1(AttrType)>(sequence);
}

// Rule() << нетерминал без атрибута
template<
	typename TokenType
>
RuleAux<TokenType, NullType>
operator << (Rule, NTerm<TokenType, void> &next_nterm)
{
	GeneralizedSymbol<TokenType> tok;
	tok.isTerm = false;
	tok.nterm = &next_nterm.rules;
	SequenceInfo<TokenType> sequence;
	sequence.symbols.push_back(tok);

	return RuleAux<TokenType, NullType>(sequence);
}

// Rule() << нетерминал с атрибутом
template<
	typename TokenType,
	typename NewAttr
>
RuleAux<TokenType, TYPELIST1(NewAttr)>
operator << (Rule, NTerm<TokenType, NewAttr> &next_nterm)
{
	GeneralizedSymbol<TokenType> tok;
	tok.isTerm = false;
	tok.nterm = &next_nterm.rules;
	SequenceInfo<TokenType> sequence;
	sequence.symbols.push_back(tok);

	return RuleAux<TokenType, TYPELIST1(NewAttr)>(sequence);
}

// RuleAux << терминал без атрибута (Rule() << Program << ';')
template<
	typename TokenType,
	class Types,
	typename TokenTypeValue
>
RuleAux<TokenType, Types>
operator<<(RuleAux<TokenType, Types> rule, TokenTypeValue v)
{
	TokenType t = TokenType(v);
	GeneralizedSymbol<TokenType> tok;
	tok.isTerm = true;
	tok.term = t;
	SequenceInfo<TokenType> sequence = rule.symbols;
	sequence.symbols.push_back(tok);

	return RuleAux<TokenType, Types>(sequence);
}

// RuleAux << терминал с атрибутом
template<
	typename TokenType,
	class Types,
	typename AttrType
>
RuleAux<TokenType, TypeList<AttrType,Types>>
operator<<(RuleAux<TokenType, Types> rule, TermAux<TokenType, AttrType> term)
{
	GeneralizedSymbol<TokenType> tok;
	tok.isTerm = true;
	tok.term = term.terminal;
	SequenceInfo<TokenType> sequence = rule.symbols;
	sequence.symbols.push_back(tok);

	return RuleAux<TokenType, TypeList<AttrType, Types>>(sequence);
}

// RuleAux << нетерминал без атрибута
template<
	typename TokenType,
	class Types
>
RuleAux<TokenType, Types>
operator<<(RuleAux<TokenType, Types> rule, NTerm<TokenType, void> &next_nterm)
{
	GeneralizedSymbol<TokenType> tok;
	tok.isTerm = false;
	tok.nterm = &next_nterm.rules;
	SequenceInfo<TokenType> sequence = rule.symbols;
	sequence.symbols.push_back(tok);

	return RuleAux<TokenType, Types>(sequence);
}


// RuleAux << нетерминал с атрибутом
template<
	typename TokenType,
	class Types,
	typename NewAttr
>
RuleAux<TokenType, TypeList<NewAttr, Types>>
operator << (RuleAux<TokenType, Types> rule, NTerm<TokenType, NewAttr> &next_nterm)
{
	GeneralizedSymbol<TokenType> tok;
	tok.isTerm = false;
	tok.nterm = &next_nterm.rules;
	SequenceInfo<TokenType> sequence = rule.symbols;
	sequence.symbols.push_back(tok);

	return RuleAux<TokenType, TypeList<NewAttr, Types>>(sequence);
}

// RuleAux пустой << функция (без параметров, так как RuleAux пустой), возвращающая void
template <
	typename TokenType,
	typename AttrRes
>
RuleRes<TokenType, void>
operator<<(RuleAux<TokenType, NullType> rule, AttrRes(*func)())
{
	struct TheAction : public Action
	{
		void changeStack(Stack& stack)
		{
			// 1. Вызываем функцию func
			// 2. Кладём её результат на стек
			stack.pushBack(func());
		}

		AttrRes (*func)();
	};

	TheAction *action = new TheAction;
	action->func = func;
	rule.symbols.action = action;
	return RuleRes<TokenType, AttrRes>(rule.symbols);
}

// RuleAux непустой << функция (принимающая один параметр, так как RuleAux непустой), возвращающая void
template <
	typename TokenType,
	typename Attr1
>
RuleRes<TokenType, void>
operator<<(RuleAux<TokenType, TYPELIST1(Attr1)> rule, void(*func)(Attr1))
{
	struct TheAction : public Action
	{
		void changeStack(Stack& stack)
		{
			// 1. Снимаем со стека элемент.
			// 2. Проверяем его тип - Attr1
			Attr1 attr1;
			stack.popBack(attr1);
			// 3. Вызываем функцию, передавая ей этот элемент
			func(attr1);
		}

		void(*func)(Attr1);
	};

	TheAction *action = new TheAction;
	action->func = func;
	rule.symbols.action = action;
	return RuleRes<TokenType, void>(rule.symbols);
}

// RuleAux(один параметр) << функция, возвращающая AttrRes, принимающая один параметр
template <
	typename TokenType,
	typename Attr1,
	typename AttrRes
>
RuleRes<TokenType, AttrRes>
operator<<(RuleAux <TokenType, TYPELIST1(Attr1) > rule, AttrRes(*func)(Attr1))
{
	struct TheAction : public Action
	{
		void changeStack(Stack& stack)
		{
			// 1. Снимаем со стека элемент.
			// 2. Проверяем его тип - Attr1
			Attr1 attr1;
			stack.popBack(attr1);
			// 3. Вызываем функцию, передавая ей этот элемент
			// 4. Кладём на стек результат вызова
			stack.pushBack(func(attr1));
		}

		AttrRes(*func)(Attr1);
	};

	TheAction *action = new TheAction;
	action->func = func;
	rule.symbols.action = action;
	return RuleRes<TokenType, AttrRes>(rule.symbols);
}

// RuleAux(список параметров) << функция, возвращающая AttrRes, принимающая список из двух параметров
template <
	typename TokenType,
	typename Attr1,
	typename Attr2
>
RuleRes<TokenType, void>
operator<<(RuleAux<TokenType, TYPELIST2(Attr2, Attr1)> rule, void(*func)(Attr1, Attr2))
{
	struct TheAction : public Action
	{
		void changeStack(Stack& stack)
		{
			// 1. Снимаем со стека 2 элемента.
			// 2. Проверяем их типы - Attr1, Attr2
			Attr1 attr1;
			Attr2 attr2;
			stack.popBack(attr2);
			stack.popBack(attr1);
			// 3. Вызываем функцию, передавая ей эти элементы
			func(attr1, attr2);
		}

		void(*func)(Attr1, Attr2);
	};

	TheAction *action = new TheAction;
	action->func = func;
	rule.symbols.action = action;
	return RuleRes<TokenType, void>(rule.symbols);
}

// RuleAux(список параметров) << функция, возвращающая AttrRes, принимающая список из двух параметров
template <
	typename TokenType,
	typename Attr1,
	typename Attr2,
	typename AttrRes
>
RuleRes<TokenType, AttrRes>
operator<<(RuleAux<TokenType, TYPELIST2(Attr2, Attr1)> rule, AttrRes(*func)(Attr1, Attr2))
{
	struct TheAction : public Action
	{
		void changeStack(Stack& stack)
		{
			// 1. Снимаем со стека 2 элемента.
			// 2. Проверяем их типы - Attr1, Attr2
			Attr1 attr1;
			Attr2 attr2;
			stack.popBack(attr2);
			stack.popBack(attr1);
			// 3. Вызываем функцию, передавая ей эти элементы
			// 4. Кладём на стек результат вызова
			stack.pushBack(func(attr1, attr2));
		}

		AttrRes(*func)(Attr1, Attr2);
	};

	TheAction *action = new TheAction;
	action->func = func;
	rule.symbols.action = action;
	return RuleRes<TokenType, AttrRes>(rule.symbols);
}

//перегрузка оператора |

// случаи с e
// RuleRes void | Rule 
template<
	typename TokenType
>
Alt<TokenType, void>
operator | (RuleRes<TokenType, void>  ruleRes1, Rule)
{
	AltInfo<TokenType> altInfo;
	altInfo.alt.push_back(ruleRes1);

	SequenceInfo<TokenType> e;
	altInfo.alt.push_back(e);

	return Alt<TokenType, void>(altInfo);
}

//  Rule | RuleRes void
template<
	typename TokenType
>
Alt<TokenType, void>
operator | (Rule, RuleRes<TokenType, void>  ruleRes1)
{
	AltInfo<TokenType> altInfo;
	SequenceInfo<TokenType> e;
	altInfo.alt.push_back(e);
	altInfo.alt.push_back(ruleRes1);	

	return Alt<TokenType, void>(altInfo);
}

// RuleRes | Rule 
template<
	typename TokenType,
	typename Attr
>
Alt<TokenType, Attr>
operator | (RuleRes<TokenType, Attr> ruleRes1, Rule)
{
	AltInfo<TokenType> altInfo;
	altInfo.alt.push_back(ruleRes1);

	SequenceInfo<TokenType> e;
	altInfo.alt.push_back(e);

	return Alt<TokenType, Attr>(altInfo);
}

//  Rule | RuleRes
template<
	typename TokenType,
	typename Attr
>
Alt<TokenType, Attr>
operator | (Rule, RuleRes<TokenType, Attr> ruleRes1)
{
	AltInfo<TokenType> altInfo;
	SequenceInfo<TokenType> e;
	altInfo.alt.push_back(e);
	altInfo.alt.push_back(ruleRes1);

	return Alt<TokenType, Attr>(altInfo);
}

// RuleRes | RuleRes
template<
	typename TokenType,
	typename Attr
>
Alt<TokenType, Attr>
operator | (RuleRes<TokenType, Attr> ruleRes1, RuleRes<TokenType, Attr> ruleRes2)
{
	AltInfo<TokenType> altInfo;
	altInfo.alt.push_back(ruleRes1.symbols);
	altInfo.alt.push_back(ruleRes2.symbols);

	return Alt<TokenType, Attr>(altInfo);
}



// Alt| RuleRes
template<
	typename TokenType,
	typename Attr
>
Alt<TokenType, Attr>
operator | (Alt<TokenType, Attr> alt, RuleRes<TokenType, Attr> ruleRes)
{
	alt.alt_info.alt.push_back(ruleRes.symbols);

	return alt;
}

// RuleRes | RuleAux
template<
	typename TokenType,
	typename Attr
>
Alt<TokenType, Attr>
operator | (RuleRes<TokenType, Attr> ruleRes, RuleAux<TokenType, TYPELIST1(Attr) > ruleAux)
{
	AltInfo<TokenType> altInfo;
	altInfo.alt.push_back(ruleRes);
	altInfo.alt.push_back(ruleAux);

	return Alt<TokenType, Attr>(altInfo);
}

// RuleAux | RuleRes
template<
	typename TokenType,
	typename Attr
>
Alt<TokenType, Attr>
operator | (RuleAux<TokenType, TYPELIST1(Attr)> ruleAux, RuleRes<TokenType, Attr> ruleRes)
{
	AltInfo<TokenType> altInfo;
	altInfo.alt.push_back(ruleAux.symbols);
	altInfo.alt.push_back(ruleRes.symbols);

	return Alt<TokenType, Attr>(altInfo);
}

// RuleAux пустой | RuleAux пустой
template<
	typename TokenType
>
Alt<TokenType, void>
operator | (RuleAux<TokenType, NullType > ruleAux1, RuleAux<TokenType, NullType > ruleAux2)
{
	AltInfo<TokenType> altInfo;
	altInfo.alt.push_back(ruleAux1.symbols);
	altInfo.alt.push_back(ruleAux2.symbols);

	return Alt<TokenType, void>(altInfo);
}

// RuleAux | RuleAux 
template<
	typename TokenType,
	class Types,
	typename Attr
>
Alt<TokenType, Attr>
operator | (RuleAux<TokenType, Types> ruleAux1, RuleAux<TokenType, Types> ruleAux2)
{
	AltInfo<TokenType> altInfo;
	altInfo.alt.push_back(ruleAux1.symbols);
	altInfo.alt.push_back(ruleAux2.symbols);

	return Alt<TokenType, Attr>(altInfo);
}

// Alt | RuleAux
template<
	typename TokenType,
	class Types,
	typename Attr
>
Alt<TokenType, Attr>
operator | (Alt<TokenType, Attr> alt, RuleAux<TokenType, Types> ruleAux)
{
	alt.alt_info.alt.push_back(ruleAux.symbols);

	return Alt<TokenType, Attr>(alt.alt_info);
}