c++ - 如何编写递归下降解析器？

Question

<分区>

Answer 1

鉴于您已经编写的内容，它主要是从 EBNF 到 C++ 源代码的机械翻译，因此(例如)这样的规则:

<Scheme>              ->  <Identifier> ( <Identifier List> ) 
<Identifier List>     ->  <Identifier> <Identifier List Tail>
<Identifier List Tail>->  , <Identifier List> | ε

转换成这个一般顺序的东西(但要小心——我只是在脑海中打字，所以它根本没有经过测试；更多地把它想象成类似 C 的伪代码比按原样编译的任何东西)。

bool scheme() { 
    return identifier()        &&
           check_input('(')    &&
           identifier_list()   &&
           check_input(')');
}

bool identifier_list() { 
    if (identifier()) {
        if (check_input(','))
            return identifier_list();
        else
            return true;
    }
    return false;
}

bool identifier() { 
    // you haven't said what's a legal identifier, so for the moment I'm assuming
    // rules roughly like C's.
    int ch;
    std::string id;

    if (!((ch=getinput()) == '_' || isalapha(ch))
        return false;

    do { 
        id += ch;
        ch = getinput();
    } while (isalpha(ch) || isdigit(ch) || ch == '_');
    putback(ch);
    return true;
}

一旦你让它正确识别输入(并构建标识符等，正如我上面所做的，即使我没有对它做任何事情)你就可以开始构建一个解析树(或其他)添加东西在你认出它们的那棵树上。如果你在 C 中这样做，你通常使用 union 。在 C++ 中，您可能想改用类层次结构(尽管它会是一个非常短、浓密的层次结构——事实上，很容易是所有其他直接从基类派生的层次结构)。