c-这种算法是哪种递归解析?自下而上还是自上而下

Question

我发现并使用了一种算法来解决我遇到的一个问题。目前的问题是，我不确定这是自下而上还是自上而下。

我有以下语法：

query   ::= andterm 
| andterm "ANDNOT" query
andterm ::= orterm
| orterm "AND" andterm
orterm  ::= term
| term "OR" orterm
term    ::= "(" query ")" 
| <word>

因此，我有以下代码：

struct index {
hashmap *map;
char *qword;
}
void querynext(iter, index) {
if (list_hasnext(iter)) {
index->qword = list_next(iter);
}
else index->qword = "";
}
set_t *parsequery(index, iter) {
set_t *andterm;
andterm = parseand(index, iter);
if(strcmp(index->qword, "ANDNOT") == 0) {
qnext(iter, index);
return set_different(andterm, parsequery(index, iter)):
}
else return andterm;
}
set_t *parseand(index, iter) {
set_t *orterm;
orterm = parseor(index, iter);
if(strcmp(index->qword, "AND") == 0) {
qnext(iter, index);
return set_intersection(orterm, parseand(index, iter));
}
else return orterm;
}
set_t *parseor(index, iter) {
set_t *term;
term = parseterm(index, iter);
if(strcmp(index->qword, "OR") == 0) {
qnext(iter, index);
return set_difference(term, parseor(index, iter));
}
else return term;
}
set_t *parseterm(index, iter) {
if(strcmp(index->qword, "(") == 0) {
qnext(iter, index);
set_t *parseset = parsequery(index, iter);
if(strcmp(index->qword, ")") == 0) {
qnext(iter, index);
return perseset;
}
}
if(map_haskey(index->map, index->qword)) {
set_t *parsekey;
parsekey = map_get(index->map, index->qword);
qnext(iter, index);
return parsekey;
}
else {
set_t emptyset;
emptyset = set_create;
return empty;
}
}

当前算法的流程如下："blue AND html"的示例输入。

当它通过parsequery运行时，它将通过以下过程进行馈送：parsequery->parseand->parseor->parseterm。

在parseterm中，它将被发现在hasmap中。Parsetent将返回一个带有"蓝色"的集合。Parsetent还将使用qnext进一步迭代查询列表。

在parseor中，我们现在将有一个正在测试的新词"AND"，它不是strcmp，因此parseor返回term。

在parseand中，它将是strcmp==0，因此它将被带入循环中。将运行qnext，然后返回orterm集("blue")和递归解析器(index，iter)的交集。

html这个词也会在hashmap中找到，并且集合会返回到parseand。然后，Parsend将返回"blue"one_answers"html"的set_intersection。

我真的不知道该怎么称呼这种解析。我读过一本书，一本书一本书的解析，但我不确定。我们从顶部开始，输入单词，但算法的设计会将单词发送到底部，解析词条，然后再向上

如果这是一篇很长的帖子，我很抱歉。我尽力解释我的问题。

Answer 1

在您的代码中，每个非终端符号都有一个过程，它根据语法规则递归调用解析其他非终端的过程。所以它是一个递归下降解析器。它从上到下(隐式地)构造解析树，这使它成为自上而下的解析器。附加信息如何传播其实并不重要。