c++ - 闭括号集的基本递归下降解析器

Question

如何为以下语法制作递归下降 LL(1) 解析器(我正在使用 C++):

S -> SS  
S -> (S)  
S -> epsilon

我尝试过使用递归函数，但我认为这是完全错误的。我知道规则需要按顺序执行，但是如何在不进入无限循环的情况下获取第一条规则来检查第一条规则的其他实例？在我的代码中，我只检查后续规则。

我的代码:

bool rule1(tokenizer * tp){ // S -> SS
    return rule2(tp) && rule2(tp);
}

bool rule2(tokenizer * tp){ // S -> (S)
    bool returnVal = false;

    if(tp-> lookahead. front( ). type == tkn_LPAR){
        tokenizer tmpTknzr = &tp;       
        tp-> lookahead. pop_front( );
        if(tp-> lookahead. front( ). type == tkn_RPAR){ // S -> epsilon
            tp-> lookahead. pop_front( );
            returnVal = true;
        } else {
            if(evalS(tp) && tp-> lookahead. front( ). type == tkn_RPAR){
                tp-> lookahead. pop_front( );
                returnVal = true;
            }
        }
    }
    return returnVal;
}

bool evalS(tokenizer * tp){ // evaluate S
    return rule1(tp) || rule2(tp);
}

Answer 1

问题是你的语法不是 LL(1) —— 事实上它是有歧义的，这使得解析更加困难。尝试使用 LL(1) 语法作为括号，例如

S -> (S)S
S -> ε