这种算法是哪种递归解析？自下而上还是自上而下？

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将返回一个"蓝色"的集合.Parseterm还将使用qnext进一步迭代查询列表.

在parseor中,我们现在将有一个正在测试的新单词"AND",它不是strcmp所以因此parseor返回term.

在parseand中它将是strcmp == 0所以它将被带入循环.将运行qnext,然后返回orterm set("blue")和递归parseand(index,iter)的交集.

html这个词也可以在hashmap中找到,该set将返回到parseand.然后Parseand将返回"blue"和"html"的set_intersection.

我真的不知道该怎么称呼这个解析.我已阅读预订并预订,pdf解析后的pdf,但我不确定.我们从顶部开始,输入单词,但算法的设计会将单词发送到底部,然后再进行解析,然后重新开始工作.

对不起,如果这是一篇很长的帖子.我尽力解释我的问题.

Answer 1

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