如何为以下语法制作递归下降 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);
}
最佳答案
问题是你的语法不是 LL(1) —— 事实上它是有歧义的,这使得解析更加困难。尝试使用 LL(1) 语法作为括号,例如
S -> (S)S
S -> ε
关于c++ - 闭括号集的基本递归下降解析器,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22275089/