#include <set>
#include <unordered_set>
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);
}
};
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;
};
//тип 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);
}
//для правил A->e
NTerm(Rule rule) {
SequenceInfo<TokenType> e;
rules.alt.push_back(e);
}
struct Item
{
SequenceInfo<TokenType>* seqInfo;
GeneralizedSymbol<TokenType> nextTerm;
int cursor;
Item(SequenceInfo<TokenType>* item, int cursor, TokenType nextTerm)
{
this->seqInfo = item;
this->nextTerm.isTerm = true;
this->nextTerm.term = nextTerm;
this->cursor = cursor;
}
bool operator==(const Item& other) const
{
return (this->seqInfo == other.seqInfo) && (this->cursor == other.cursor) && (this->nextTerm == other.nextTerm);
}
bool operator!=(const Item& other) const
{
return !(*this == other);
}
};
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> &itemVector)
{
std::vector<Item> itemVectorAux;
//для каждого пункта [A->...*Bb, a] из I
//for (std::vector<Item>::iterator item = itemVector.begin(); item != itemVector.end(); item++)
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)
{
//chain = b
std::vector<SequenceInfo<TokenType>> ba;
SequenceInfo<TokenType> chain;
for (int j = cursor + 1; j < sequence->size(); j++)
{
chain.symbols.push_back((*sequence)[j]);
}
chain.symbols.push_back(itemVector[i].nextTerm);
ba.push_back(chain);
// First(ba)
std::vector<TokenType> firstBa;
First(ba, firstBa);
//для каждого правила 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++)
{
//для каждого терминала b из firstBa
for (std::vector<TokenType>::iterator b = firstBa.begin(); b != firstBa.end(); b++)
{
Item newItem(&((*bSeq)[k]), 0, *b);
// проверяем, существует ли уже такой пункт?
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);
}
}
}
}
// а если больше?
}
//вызвать closure для нерассмотренных, добавленных пунктов
if (itemVectorAux.size() != 0)
{
std::vector<Item> newItems = Closure(itemVectorAux);
itemVector.insert(itemVector.end(), newItems.begin(), newItems.end());
}
return itemVectorAux;
}
public:
void parse(Lexer<TokenType> &lexer) {
//тут строится таблица для lalr(1) анализатора
//построение мн-ва пунктов: пар (номер правила, положение точки)
//пункты с точкой в начале тела не нужны
std::set<AltInfo<TokenType>*> rulesLalr;
//расширяем грамматику, добавляя правило 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);
//rulesLalr.insert(&startSymbol);
//MakeRules(rulesLalr, &rules);
//инициализируем С мн-вом closure({S'->*S, $})
TokenType term = (TokenType)NULL;
Item firstItem(&seqInfo, 0, term);
std::vector<Item> s;
s.push_back(firstItem);
//SequenceInfo<TokenType> e;
//std::cout << e.symbols.size();
Closure(s);
//из каждого 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);
}