Как проверить ввод на основе CFG?

Рассмотрим эту грамматику:

expr ::= LP expr RP
| expr PLUS|MINUS expr
| expr STAR|SLASH expr
| term

term ::= INTEGER|FLOAT

Контекстно-свободная грамматика определяется как G = ( V, Σ, R, S )где (в данном случае):

V = { expr, term }
Σ = { LP, RP, PLUS, MINUS, STAR, SLASH, INTEGER, FLOAT }
R = //was defined above
S = expr

Теперь давайте определим небольшой класс с именем Parser какое определение (примеры кода предоставлены в C ++):

class Parser
{
public:
Parser();
void Parse();
private:
void parseRecursive(vector<string> rules, int ruleIndex, int startingTokenIndex, string prevRule);

bool isTerm(string token);  //returns true if token is in upper case
vector<string> split(...);  //input: string; output: vector of words splitted by delim

map<string, vector<string>> ruleNames; //contains grammar definition
vector<int> tokenList; //our input set of tokens
};

Чтобы упростить переход между правилами, каждое правило грамматики разбито на 2 части: ключ (до ::=) и его правила (после ::=), поэтому для моей грамматики сверху имеет место следующая карта:

std::map<string, vector<string>> ruleNames =
{
{ "expr", {
"LP expr RP",
"expr PLUS|MINUS expr",
"expr STAR|SLASH expr",
"term"}
},
{ "term", { "INTEGER", "FLOAT" } }
};

Для целей тестирования строка (2 + 3) * 4 был размечен на следующий набор

{ TK_LP, TK_INTEGER, TK_PLUS, TK_INTEGER, TK_RP, TK_STAR, TK_INTEGER }

и был использован в качестве входных данных для Parser,

Теперь самое сложное: алгоритм. Из того, что я понимаю, я думал об этом:

1) Извлечение первого правила из начального вектора символов (LP expr RP) и разбить его на слова.

2) Проверьте, является ли первое слово в правиле терминальным.

1. Если слово является терминальным, сравните его с первым токеном.
   • Если они равны, увеличьте индекс токена и перейдите к следующему слову в правиле.
   • Если они не равны, сохраните индекс токена и перейдите к следующему правилу.
2. Если слово не является терминальным и не использовалось в предыдущей рекурсии, увеличьте индекс токена и перейдите к рекурсивному разбору (передавая новые правила и нетерминальное слово)

Хотя я не уверен в этом алгоритме, я все же попытался сделать и реализовать его (конечно, безуспешно):

1) Outter Parse функция, которая инициирует рекурсию:

void Parser::Parse()
{
int startingTokenIndex = 0;
string word = this->startingSymbol;
for (int ruleIndex = 0; ruleIndex < this->ruleNames[word].size(); ruleIndex++)
{
this->parseRecursive(this->ruleNames[word], ruleIndex, startingTokenIndex, "");
}
}

2) Рекурсивная функция:

void Parser::parseRecursive(vector<string> rules, unsigned ruleIndex, unsigned startingTokenIndex, string prevRule)
{
printf("%s - %s\n", rules[ruleIndex].c_str(), this->tokenNames[this->tokenList[startingTokenIndex]].c_str());
vector<string> temp = this->split(rules[ruleIndex], ' ');
vector<vector<string>> ruleWords;
bool breakOutter = false;

for (unsigned wordIndex = 0; wordIndex < temp.size(); wordIndex++)
{
ruleWords.push_back(this->split(temp[wordIndex], '|'));
}

for (unsigned wordIndex = 0; wordIndex < ruleWords.size(); wordIndex++)
{
breakOutter = false;
for (unsigned subWordIndex = 0; subWordIndex < ruleWords[wordIndex].size(); subWordIndex++)
{
string word = ruleWords[wordIndex][subWordIndex];
if (this->isTerm(word))
{
if (this->tokenNames[this->tokenList[startingTokenIndex]] == this->makeToken(word))
{
printf("%s ", word.c_str());
startingTokenIndex++;
} else {
breakOutter = true;
break;
}
} else {
if (prevRule != word)
{
startingTokenIndex++;
this->parseRecursive(this->ruleNames[word], 0, startingTokenIndex, word);
prevRule = word;
}
}
}

if (breakOutter)
break;
}
}

Какие изменения я должен внести в мой алгоритм, чтобы он работал?