103 lines
No EOL
3 KiB
C++
103 lines
No EOL
3 KiB
C++
namespace tp {
|
|
template <typename tAlphabetType, typename tStateType>
|
|
auto DetPushDownAutomata<tAlphabetType, tStateType>::accept(const tAlphabetType* stream, ualni size) -> AcceptResult {
|
|
mItems.removeAll();
|
|
mStateStack.clear();
|
|
mValueStack.clear();
|
|
|
|
auto newItem = [&](tAlphabetType symbol) -> StackItem* {
|
|
auto node = mItems.newNode();
|
|
node->data.symbol = symbol;
|
|
node->data.rule = -1;
|
|
node->data.leafs.clear();
|
|
mItems.pushBack(node);
|
|
return &node->data;
|
|
};
|
|
|
|
mStateStack.append(ualni(0));
|
|
|
|
ualni advancedIdx = 0;
|
|
|
|
while (true) {
|
|
ualni state = mStateStack.last();
|
|
ualni look = (advancedIdx < size) ? (ualni(stream[advancedIdx].id) - mNonTerminalCount) : mTerminalCount;
|
|
|
|
const ContextFreeCompiler::Action& action = mActionTable.get({ state, look });
|
|
|
|
if (action.type == ContextFreeCompiler::Action::SHIFT) {
|
|
mStateStack.append(action.num);
|
|
mValueStack.append(newItem(stream[advancedIdx]));
|
|
advancedIdx++;
|
|
|
|
} else if (action.type == ContextFreeCompiler::Action::REDUCE) {
|
|
ualni rule = action.num;
|
|
ualni pop = mRulePopCount[rule];
|
|
alni lhs = mRuleLhs[rule];
|
|
|
|
StackItem* parent = newItem(mNonTerminalSymbols[(ualni) lhs]);
|
|
parent->rule = (alni) rule;
|
|
|
|
for (ualni i = 0; i < pop; i++) {
|
|
parent->leafs.append(mValueStack.last());
|
|
mValueStack.pop();
|
|
mStateStack.pop();
|
|
}
|
|
|
|
for (ualni i = 0; i < parent->leafs.size() / 2; i++) {
|
|
auto tmp = parent->leafs[i];
|
|
parent->leafs[i] = parent->leafs[parent->leafs.size() - 1 - i];
|
|
parent->leafs[parent->leafs.size() - 1 - i] = tmp;
|
|
}
|
|
|
|
ualni gotoState = (ualni) mGotoTable.get({ mStateStack.last(), (ualni) lhs });
|
|
mStateStack.append(gotoState);
|
|
mValueStack.append(parent);
|
|
|
|
} else if (action.type == ContextFreeCompiler::Action::ACCEPT) {
|
|
return { true, advancedIdx, mValueStack.size() ? mValueStack.last() : nullptr };
|
|
} else {
|
|
return { false, advancedIdx, nullptr };
|
|
}
|
|
}
|
|
}
|
|
|
|
template <typename tAlphabetType, typename tStateType>
|
|
void DetPushDownAutomata<tAlphabetType, tStateType>::construct(const ContextFreeCompiler& compiler) {
|
|
mNonTerminalCount = compiler.getNonTerminals()->size();
|
|
mTerminalCount = compiler.getTerminals()->size();
|
|
mStartSymbol = compiler.getStartSymbol();
|
|
|
|
mNonTerminalSymbols.clear();
|
|
for (auto sym : *compiler.getNonTerminals()) {
|
|
mNonTerminalSymbols.append(sym.data());
|
|
}
|
|
|
|
mRuleLhs.clear();
|
|
for (auto lhs : *compiler.getRuleLhs()) {
|
|
mRuleLhs.append(lhs.data());
|
|
}
|
|
|
|
mRulePopCount.clear();
|
|
for (auto pop : *compiler.getRulePopCount()) {
|
|
mRulePopCount.append(pop.data());
|
|
}
|
|
|
|
ualni S = compiler.getActionTable()->size().x;
|
|
ualni N = mNonTerminalCount;
|
|
ualni T = mTerminalCount;
|
|
|
|
mActionTable.reserve({ S, T + 1 });
|
|
for (ualni s = 0; s < S; s++) {
|
|
for (ualni t = 0; t <= T; t++) {
|
|
mActionTable.set({ s, t }, compiler.getActionTable()->get({ s, t }));
|
|
}
|
|
}
|
|
|
|
mGotoTable.reserve({ S, N });
|
|
for (ualni s = 0; s < S; s++) {
|
|
for (ualni n = 0; n < N; n++) {
|
|
mGotoTable.set({ s, n }, compiler.getGotoTable()->get({ s, n }));
|
|
}
|
|
}
|
|
}
|
|
} |