c++ - 如何基于CFG验证输入？

Question

考虑这个语法:

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
};

为了更容易在规则之间切换，每个语法规则都分为两部分:一个键(在 ::= 之前)和它的规则(在 ::= 之后) >)，所以对于我上面的语法，发生了以下映射:

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 }

并用作解析器的输入数据。

现在是最难的部分:算法。据我了解，我在考虑这个问题:

1) 从起始符号 vector (LP expr RP) 中提取第一条规则并将其拆分为单词。

2) 检查规则中的第一个词是否是终结符。

1. 如果这个词是终结词，将它与第一个标记进行比较。
   • 如果它们相等，则增加标记索引并移动到规则中的下一个单词
   • 如果不相等，则保留标记索引并转到下一条规则
2. 如果这个词不是终结词并且在之前的递归中没有使用过，增加标记索引并进入递归解析(传递新规则和非终结词)

虽然我对这个算法不太确定，但我还是尝试着制作并实现了它(当然没有成功):

1) 启动递归的外部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;
    }
}

我应该对我的算法进行哪些更改才能使其正常工作？

Answer 1

根据你想实现一次性解析器或编译器编译器的不同，使用不同的方法。 For compiler编译器主要使用LR，用于手动执行LL。基本上，对于 LL，手动实现使用递归下降(对于每个非终端，创建一个实现它的函数)。例如，对于语法:

S -> S + A | A
A -> a | b

让我们取消左递归和左分解(LL 文法不适用于左递归):

S -> As
s -> + As | epsilon
A -> a | b

这样的实现是可能的:

void S (void)
{
    A ();
    s ();
}
void s (void)
{
    if (get_next_token (). value! = '+')
        return;
    A ();
    s ();
}
void A (void)
{
    token * tok = get_next_token ();
    if (tok.value! = 'a' && tok.value! = 'b')
            syntax_error ();
}

如果要添加SDD，则继承属性通过参数传递，合成属性作为输出值。

评论:不要一次收集所有 token ，根据需要获取它们:get_next_token()。