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中。Parseterm 将返回一个带有“blue”的集合。 Parseterm 还将使用 qnext 进一步迭代查询列表。

在解析器中，我们现在有一个正在测试的新词“AND”，它不是 strcmp，因此解析器返回术语。

在 parseand 中它会是 strcmp == 0 所以它会被带入循环。将运行 qnext，然后返回 orterm 集(“blue”)和递归 parseand(index，iter)的交集。

单词 html 也会在 hashmap 中找到，该集合将返回到 parseand。然后 Parseand 将返回“blue”和“html”的 set_intersection。

我真的不知道如何称呼这个解析。我已经阅读了 book up 和 book down，pdf 之后的 pdf 解析，但我不确定。我们从顶部开始，输入单词，但算法的设计会将单词发送到底部，到 parseterm，然后再次向上处理。

对不起，如果这是一篇很长的文章。我尽力解释我的问题。

Answer 1

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