Рассмотрим эту грамматику:
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) 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;
}
}
Какие изменения я должен внести в мой алгоритм, чтобы он работал?
Задача ещё не решена.
Других решений пока нет …