Który rodzaj rekursywnego parsowania to ten algorytm? Od dołu do góry lub z góry na dół?

Question

Znalazłem i użyłem algorytmu do rozwiązania problemu, który miałem. Obecny problem polega na tym, że nie jestem pewien, czy jest to odgórne, czy odgórne.

Mam następujący Gramatyka:

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

A więc mam następujący kod:

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

Przepływ obecnego algorytmu będzie tak: wejście próbka „niebieski AND html ".

Po przejściu przez parsekcję będzie on przesyłany przez ten proces: parsequery-> parseand-> parseor-> parseterm.

W parsetermie okaże się, że znajduje się w hasmapie. Parseterm zwróci zestaw z "niebieskim". Parseterm będzie również iterować listę zapytań o krok dalej za pomocą qnext.

W parserze mamy teraz nowe słowo, które jest testowane, "AND", nie jest to polecenie strcmp, dlatego parseor zwraca termin.

W parsiedzie będzie to strcmp == 0, więc zostanie przeniesione do pętli. qnext zostanie uruchomiony, a następnie zwróci przecięcie zbioru orterm ("niebieski") i rekursywny parseand (index, iter).

Słowo html zostanie również znalezione w mapie mieszającej, a zestaw zostanie zwrócony do parseand. Parseand następnie zwróci set_intersection "blue" i "html".

Nie wiem, jak nazwać to przetwarzanie, naprawdę. Czytałem książki i książki, pdf po pdf na parsowanie, ale nie jestem pewien. Zaczynamy od góry, wprowadzamy słowo, ale projekt algorytmu wyśle ​​słowo na dół, do parsetermu, a następnie do pracy na nowo.

Przepraszam, jeśli to był długi wpis. Starałem się wyjaśnić mój problem najlepiej, jak potrafiłem.

Answer 1

W twoim kodzie jest procedura dla każdego nieterminalnego symbolu, który rekurencyjnie wywołuje procedury do analizowania innych nie-terminali zgodnie z zasadami gramatyki. Jest to więc recursive descent parser. Konstruuje drzewo składniowe (niejawnie) od góry do dołu, co czyni go parserem zstępującym. Nie ma znaczenia, w jaki sposób propagowane są dodatkowe informacje.