How to validate input based on CFG?
<p>Consider this grammar:</p>

<pre><code>expr ::= LP expr RP
         | expr PLUS|MINUS expr
         | expr STAR|SLASH expr
         | term

term ::= INTEGER|FLOAT
</code></pre>

<p>Context-free grammar is defined as <code>G = ( V, Σ, R, S )</code>, where (in this case):</p>

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

<p>Now let's define a small class called <code>Parser</code> which definition is (code samples are provided in C++):</p>

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

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

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

<p>To make it easier to go between rules, every grammar rule is split into 2 parts: a key (before <code>::=</code>) and its rules (after <code>::=</code>), so for my grammar from above the following map takes place:</p>

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

<p>For testing purposes, string <code>(2 + 3) * 4</code> has been tokenized to the following set</p>

<pre><code>{ TK_LP, TK_INTEGER, TK_PLUS, TK_INTEGER, TK_RP, TK_STAR, TK_INTEGER }
</code></pre>

<p>and been used as an input data for <code>Parser</code>.</p>

<p>Now for the hardest part: the algorithm. From what I understand, I was thinking about this:</p>

<p>1) Taking first rule from starting symbol vector (<code>LP expr RP</code>) and split it into words.</p>

<p>2) Check if first word in rule is terminal.</p>

<ol>
<li>If the word is terminal, compare it with first token.

<ul>
<li>If they are equal, increase token index and move to next word in rule</li>
<li>If they are not equal, keep token index and move to next rule</li>
</ul></li>
<li>If the word is not terminal and it was not used in previous recursion, increase token index and go into recursive parsing (passing new rules and non-terminal word)</li>
</ol>

<p>While I am not sure in this algorithm, I still tried to make and implementation of it (of course, unsuccessful):</p>

<p>1) Outter <code>Parse</code> function that initiates recursion:</p>

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

<p>2) Recursive function:</p>

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

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

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

        if (breakOutter)
            break;
    }
}
</code></pre>

<p>What changes should I perform to my algorithm to make it work?</p>