Quale tipo di parsing ricorsivo è questo algoritmo? Bottom-up o top-down?

Question

Ho trovato e utilizzato un algoritmo per risolvere un problema che avevo. Il problema attuale è che non sono sicuro se questo è bottom-up o top-down.

Ho la seguente grammatica:

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

E così ho il seguente codice:

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; 
} 
} 

Il flusso dell'algoritmo corrente sarà così: ingresso del campione di "blu E html ".

Quando viene eseguito il parsequery, verrà alimentato attraverso questo processo: parsequery-> parseand-> parseor-> parseterm.

In parseterm si troverà nella hasmap. Parseterm restituirà un set con "blue". Parseterm eseguirà inoltre l'elenco delle query un ulteriore passaggio utilizzando qnext.

In parseor ora avremo una nuova parola che è in fase di test, "AND", non è strcmp quindi quindi parseor restituisce il termine.

In parseand sarà strcmp == 0 quindi verrà inserito nel ciclo. qnext verrà eseguito, quindi restituirà l'intersezione di orterm set ("blue") e la parseand ricorsiva (index, iter).

La parola html si troverà anche nell'hashmap e l'insieme verrà restituito a parseand. Parseand restituirà quindi il set_intersection di "blue" e "html".

Non so come chiamare questo parsing, davvero. Ho letto libro e libro giù, pdf dopo pdf sull'analisi, ma non ne sono sicuro. Iniziamo in alto, inseriamo la parola, ma il disegno dell'algoritmo invierà la parola in basso, in parseterm e poi funzionerà nuovamente.

Scusate se questo era un post lungo. Ho cercato di spiegare il mio problema nel miglior modo possibile.

Answer 1

Nel codice, esiste una procedura per ciascun simbolo non terminale che richiama ricorsivamente le procedure per analizzare altri non-terminali in base alle regole della grammatica. Quindi è un recursive descent parser. Costruisce l'albero di analisi (implicitamente) dall'alto al basso, il che lo rende un parser dall'alto verso il basso. Non importa come vengono propagate le informazioni aggiuntive.