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