тесты 0 прошли

#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
{
	public:	
		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;
		AltInfo<TokenType>* altInfo;
		int seqInfoID;
		//GeneralizedSymbol<TokenType> nextTerm;
		std::unordered_set<GeneralizedSymbol<TokenType>> nextTerms;
		int cursor;

		Item(AltInfo<TokenType>* altInfo, int seqInfoID, int cursor, std::vector<GeneralizedSymbol<TokenType>> nextTerms)
		{
			this->altInfo = altInfo;
			 


			this->seqInfoID = seqInfoID;
			this->seqInfo = &(altInfo->alt[seqInfoID]); //тут что-то не то

			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);
			//return (this->seqInfo == other.seqInfo) && (this->cursor == other.cursor);
		}


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

		bool includes(Item other)
		{
			return (this->seqInfo == other.seqInfo) && (this->cursor == other.cursor);
		}
	};

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

	struct StateStack {
		std::vector<int> s;

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

			void pushBack(int item)
			{
				s.push_back(item);
			}

			void popBack(/*int& item*/)
			{
				//if (s.empty())
					//throw StackError("Stack is empty");

				//item = s.back();
				s.pop_back();
			}

			int back()
			{
				return s.back();
			}
	};

	//bool hasEpsilon(GeneralizedSymbol<TokenType> y)
	//{
	//	bool has = false;
	//	std::vector<SequenceInfo<TokenType>> alt = y.nterm->alt;

	//	for (int i = 0; i < alt.size(); i++)
	//	{
	//		if (alt[i].size() == 0) //если есть эпсилон
	//		{
	//			has = true;
	//			break;
	//		}
	//	}

	//	return has;
	//}

	struct FirstBool
	{
		std::unordered_set<GeneralizedSymbol<TokenType>> first;
		bool xHasEps = false;
	};

	FirstBool FirstForSymbol(GeneralizedSymbol<TokenType> x, std::unordered_set<GeneralizedSymbol<TokenType>> visitedNTerms)
	{
		std::unordered_set<GeneralizedSymbol<TokenType>> first; //или всё же [GS]? или [TokenType]
		bool xHasEps = false;
		
		if (x.isTerm)
			first.insert(x);
		else
		{
			if (visitedNTerms.find(x) == visitedNTerms.end()) // чтобы не зациклиться, идём только в те вершины, которые не посещали
			{
				visitedNTerms.insert(x);
				std::vector<SequenceInfo<TokenType>> alt = x.nterm->alt;

				for (int i = 0; i < alt.size(); i++)
				{
					std::vector<GeneralizedSymbol<TokenType>> y1yk = alt[i].symbols;
					//если из x выводится эпсилон, добавить эпсилон. Но мб я идентиф-ю это неправильно, ведь всегда будет конец ввода?
					if (y1yk.size() == 0)
						xHasEps = true;

					//bool sthWasAdded = true;
					//до конца цепочки, пока идут подряд нетерминалы и выводится эпсилон
					for (int j = 0; j < y1yk.size(); j++) //цикл по yi, пока из yi выводится эпсилон
					{
						FirstBool yiFirstBool = FirstForSymbol(y1yk[j], visitedNTerms);
						first.insert(yiFirstBool.first.begin(), yiFirstBool.first.end());
						if (!yiFirstBool.xHasEps || y1yk[j].isTerm)
							break;
						//sthWasAdded = false;
					}
					//добавить в x эпсилон, если всем игрекам от 1 до k принадлежит эпсилон!!!
				}
			}
		}	
		
		FirstBool fb;
		fb.first = first;
		fb.xHasEps = xHasEps;
		return fb;
	}

	std::unordered_set<GeneralizedSymbol<TokenType>> First(std::vector<GeneralizedSymbol<TokenType>> chain)
	{
		std::unordered_set<GeneralizedSymbol<TokenType>> first;
		FirstBool fb;
		int i;

		//если первые n нетерминалов в цепочке порождают (возможно, среди непустых) пустую посл-ть, то добавляем first(n+1-го нетерминала)
		for (i = 0; i < chain.size(); i++)
		{
			GeneralizedSymbol<TokenType> xi = chain[i];
			std::unordered_set<GeneralizedSymbol<TokenType>> visitedNTerms;
			visitedNTerms.insert(xi);
			fb = FirstForSymbol(xi, visitedNTerms);
			first.insert(fb.first.begin(), fb.first.end());
			if ((xi).isTerm || !fb.xHasEps) //если терминал или нет эпсилон - давай, до свидания
			{
				break;
			}
		}
		//добавить в x эпсилон, если всем xi от 1 до k принадлежит эпсилон!!!
		//if (fb.xHasEps && i == chain.size())

		return first;
	}

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

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

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

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

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

		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++) // изменила
		{
			if (item->cursor < (*item->seqInfo).symbols.size() && (*item->seqInfo).symbols[item->cursor] == x)
			{
				item->cursor++;
				j.push_back(*item);
			}
		}
		Closure(j, j);
		return j;
	}

	struct Kernel{
		std::vector<Item> lr1UnionItems;
		std::vector<int> unionNumbrs;
	};

	int GotoKernel(std::vector<Item> item, GeneralizedSymbol<TokenType> x, std::vector<std::vector<Item>> c, std::vector<Kernel> kernels)
	{
		std::vector<Item> gt = Goto(item, x);

		if (gt.size() == 0)
			return -1;

		for (int i = 0; i < kernels.size(); i++)
		{
			bool foundMatch = true;
			for (int j = 0; j < gt.size(); j++)
			{
				bool hasItem = false;
				std::vector<Item> it = kernels[i].lr1UnionItems;

				for (int k = 0; k < it.size(); k++)
				{
					if (it[k].seqInfo == gt[j].seqInfo && it[k].cursor == gt[j].cursor)
					{
						hasItem = true;
						break;
					}
				}
				if (!hasItem)
				{
					foundMatch = false;
					break;
				}
			}
			if (foundMatch == true)
				return i;
		}

		return -1;
	}

	int GotoStates(std::vector<Item> i, GeneralizedSymbol<TokenType> x, std::vector<Kernel> c)
	{
		std::vector<Item> j = Goto(i, x);
		// для каждого мн-ва итемов из с, для каждого итема из j, если размер j =< размера с[..], проверить, что каждый итем лежит внутри с[..]. Если, лежит каждый, то ретурн g

		bool equal, totallyEqual;
		for (int g = 0; g < c.size(); g++)
		{
			std::vector<Item> itemSet = c[g].lr1UnionItems;

			if (itemSet.size() == j.size())
			{
				totallyEqual = true;
				for (int k = 0; k < j.size(); k++)
				{
					equal = false;
					for (int l = 0; l < itemSet.size(); l++)
					{
						// число
						if (itemSet[l].includes(j[k]))
						{
							equal = true;
							break;
						}
					}

					if (!equal)
					{
						totallyEqual = false; // не подошло c[g]
						break;
					}
				}
			}
			else
			{
				totallyEqual = false;
			}

			if (totallyEqual)
			{
				return g;
			}
		}

		return -1;
	}

	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) уже в result и, если нет, добавляем в itemsVectorAux
					bool hasAlready = false, totallyEqual;
					for (std::vector<std::vector<Item>>::iterator itemSet = result.begin(); !hasAlready && itemSet != result.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<Kernel> ReduceItems(std::vector<ItemSet> items)
	{
		std::vector<Kernel> kernels;

		for (int i = 0; i < items.size(); i++) //было до items.size() - 1
		{
			if (!items[i].isReduced)
			{
				Kernel krnl;
				krnl.unionNumbrs.push_back(i);
				krnl.lr1UnionItems = *items[i].set;

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

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

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

				}

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

		return kernels;
	}

	struct State
	{
		std::string action;
		int state;
		GeneralizedSymbol<TokenType> A;
		int b;
	};

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);

		SequenceInfo<TokenType>* firstSeqInfo = &(startSymbol.alt[0]);
		

		//добавить в С первое мн-во пунктов = 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);
		Item firstItem(&startSymbol, 0, 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<Kernel> kernels = ReduceItems(itemSetVector);

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

		//строим Action и Goto для состояний
		std::vector<std::unordered_map<GeneralizedSymbol<TokenType>, State>>	action;
		std::vector<std::unordered_map<GeneralizedSymbol<TokenType>, int>> gotoTable;
		for (int i = 0; i < kernels.size(); i++)
		{
			std::unordered_map<GeneralizedSymbol<TokenType>, State> actionColumn;
			std::unordered_map<GeneralizedSymbol<TokenType>, int> gotoColumn;
			int gotoKernelWithNumber;
			//для всех символов грамматики
			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].lr1UnionItems.size(); j++)
					{
						State state;
						Item rule = kernels[i].lr1UnionItems[j];

						if (rule.seqInfo == firstSeqInfo && rule.cursor == firstSeqInfo->symbols.size())
						{
							//случай в)
							// если [S'->S*,$] входит в Ii, установить action[i, $] = ACCEPT							
							state.action = "accept";
							std::pair<GeneralizedSymbol<TokenType>, State> pair(term, state);
							actionColumn.insert(pair);
							belongs = true;
							break;
						}
						else 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"
								state.action = "s";
								state.state = GotoStates(kernels[i].lr1UnionItems, *symbol, kernels);
								std::pair<GeneralizedSymbol<TokenType>, State> pair(*symbol, state);
								actionColumn.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";
								//проверить, не равно ли A S'

								// пихаем номер правила, по которому будет осуществляться свёртка
								//state.item = &kernels[i][j]; 
								GeneralizedSymbol<TokenType> A;
								A.isTerm = false;
								A.nterm = rule.altInfo;
								state.A = A;
								state.b = rule.seqInfoID;
								
								std::pair<GeneralizedSymbol<TokenType>, State> pair(*symbol, state);
								actionColumn.insert(pair);
								belongs = true;
								break;
							}
						}


						//если ни один, то нет никакого перехода, а если несколько, то ошибка
						/*if (!belongs)
						{
							std::cout << "ошибка";
						}*/
					}						
				}
				else
				{
					//для нетерминала строим goto
					// ядро kernel[i] - объединение I1, ..., Ik. Тогда goto(I1+...+Ik, X), где X - нетерминал, есть goto(I1, X), которое есть closure [A->aX*b] таких, что [A->a*Xb] находится в I 
					gotoKernelWithNumber = GotoKernel(kernels[i].lr1UnionItems, *symbol, c, kernels);	
					std::pair<GeneralizedSymbol<TokenType>, int> pair(*symbol, gotoKernelWithNumber);
					gotoColumn.insert(pair);
				}
			}
			action.push_back(actionColumn);
			gotoTable.push_back(gotoColumn);
		}

		//std::vector<Token<TokenType>*> buffer;
		//считываем входящую посл-ть
		//for (Token<TokenType>* newToken = lexer.next_token(); newToken->tokenType() != 0;){
			//buffer.push_back(newToken);
		//}
		//int cursor = 0;

		StateStack stateStack;
		stateStack.pushBack(0);
		Stack attrStack;

		//алгоритм lalr(1) анализа
		Token<TokenType>* currentTerm = lexer.next_token();
		//GeneralizedSymbol<TokenType> a = buffer[cursor];
		int stateOnStTop;
		for (;;)
		{
			//s = номер ядра на вершине стека
			stateOnStTop = stateStack.back();
			GeneralizedSymbol<TokenType> a;
			a.isTerm = true;
			a.term = currentTerm->tokenType();
			State currentState = action[stateOnStTop][a];
			

			if (currentState.action == "s")
			{
				//если перенос t, вносим t в стек 
				stateStack.pushBack(currentState.state);
				//если у токена есть атрибут, выполняем семантические действия (просто вызываем toStack?)
				(*currentTerm).toStack(attrStack);

				//присваиваем a очередной символ
				currentTerm = lexer.next_token();
			}
			else if (currentState.action == "r")
			{
				//если св-ка A->b, снять |b| символов со стека состояний,  
				GeneralizedSymbol<TokenType> A = currentState.A;
				int b = currentState.b;
				SequenceInfo<TokenType> seq = A.nterm->alt[b];
				for (int i = 0; i < seq.symbols.size(); i++)
					stateStack.popBack();
				// теперь на вершине стека состояние t. Вносим в стек Goto(t, A). 
				int gotoTA = gotoTable[stateStack.back()][A]; // значение должно быть неотрицательным. Иначе, перехода не существует
				stateStack.pushBack(gotoTA);
				//выполняем семантические действия (seqInfo action?) 

			}
			else if (currentState.action == "accept")
			{
				break;// синтаксический анализ завершен
			}
			else
			{
				//восстановление после ошибки
				throw "This sequence doesn't belong to grammar";
			}
		}
	}

	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 | 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);
}