Parser rekurencyjnego zniżania z nawracaniem gramatyki

10

Czy ktoś może mi dlaczego parser rekurencyjnego zejścia z produkcje i (w tej kolejności) nie rozpoznaje języka utworzonego przez gramatykę .S.zaS.zaS.zazaS.zaS.za | zaza

Wygląda na to, że analizuje tylko słowa z języka .{za2)n | n1}

Wygenerowałem taki analizator składni za pomocą tego generatora analizatora składni ABNF z regułą produkcyjną, S = "a" S "a" / "aa"a analizator składni aaaaaana przykład nie rozpoznaje tego słowa .

Spodziewałbym się, że użyje produkcyjnego dopóki konkatenacja węzłów końcowych parsowania drzewa od lewej strony nie zacznie się od 7 , a następnie pójdzie w górę drzewa parsowania, wybierając zamiast tego produkcyjne dopóki drzewo nie będzie wyglądać jak to:S.zaS.zaaS.zaza

   S 
 / | \
a  S  a
 / | \
a  S  a
  / \
 a   a
meribold
źródło
2
Jak myślisz, dlaczego nie może przetworzyć tego słowa?
Yuval Filmus
@Yuval, myślę, że powinien to przeanalizować, więc muszę coś przeoczyć.
meribold
Ach, teraz pytanie ma więcej sensu; dzięki za edycję! Jeśli to, co piszesz, jest prawdą (nie sprawdziłem), generator wydaje się mieć błąd. (Lub nie jest to określone dla twojej gramatyki; Myślę, że jest to mało prawdopodobne, ponieważ gramatyka jest elementarna i jednoznaczna.
Raphael
@ Rafael, ponownie zredagowałem pytanie (mam nadzieję, że nie zmieniłem znaczenia). Właściwie mam za zadanie wyjaśnić, dlaczego taki parser nie rozpoznaje tego słowa aaaaaa.
meribold
Skąd masz to drzewo? Nie otrzymuję wiele z tego generatora analizatora składni ABNF. Drzewo, które dajesz, nie ma większego sensu. Ale ciąg aaaaaapowinien parsować i nie. Ale aaaaparsuje. Najwyraźniej masz rację, jeśli chodzi o potęgi 2. To musi być błąd. parsuje tylko aaz S = "aa" / "a" [S] "a". Czy potrafisz prześledzić, co robi parser?
babou

Odpowiedzi:

6

To nie jest duża odpowiedź, ale parsowania drzew nie pasują do normalnych komentarzy.

Twoja gramatyka należy analizować ciąg .S.zaS.za | zazazazazazazaza

Ale parsowanie ma następującą postać:

      S 
     /|\
    / S \
   / /|\ \
  / / S \ \
 / / / \ \ \
a a a   a a a

lub jeśli wolisz tę prezentację, z terminalami na różnych liniach

     S 
   / | \
  a  S  a
   / | \
  a  S  a
    / \
   a   a

Sprawdziłem, czy generator analizatora składni ABNF nie działa, ale nie wiem, jak prześledzić, co robi.

Rzeczywiście wydaje się, że rozpoznaje zbiór nie jest tym, co określa gramatyka.{za2)n | n1}

Trochę zaskakujące jest posiadanie tak skomplikowanej strony wokół błędnego parsera, który ponadto używa całkowicie nieciekawej techniki parsowania.


Po dalszym spojrzeniu na to:

Myślę, że znalazłem jedno źródło problemu. Nawiasy kwadratowe oznaczają opcjonalne .

Więc gramatyka powinny być pisane S = "a" S "a" / "aa" lub S = "a" [S] "a". Wtedy wydaje się działać poprawnie.

Ale system jest najwyraźniej stracony, gdy ma dwukrotnie tę samą regułę w różnych formach. Nie jestem pewien dlaczego.

Nie znalazłem strony wyjaśniającej te problemy składniowe przy określaniu gramatyki.

Nadal uważam ten buggy.

Babou
źródło
1
Auć. Tak. Nie wiem, o czym myślałem, kiedy napisałem to parsowanie. Zmodyfikuję moje pytanie i wkleję twoje.
meribold
Znalazłem inny zejście rekurencyjne, wycofywania z parsera generator online demo tutaj i to widać takie samo zachowanie tej zasady:S ::= 'a'<S>'a' | 'a''a'
meribold
aaaaaaPodczas używania nadal się nie analizuje S = "a" S "a" / "aa", ale wydaje się, że masz rację co do nawiasów.
meribold
Nie widzę sensu odkrywania rekurencyjnego opadania, parsera cofania.
babou
masz rację S = "a" S "a" / "aa"... Testowałem zbyt szybko i kliknąłem generuj zamiast parsować.
babou
3

s1()S.zaS.zatrues()s2()S.zaza

Rozważ aaaaaaponowne przeanalizowanie tego słowa . W pewnym momencie parsowanie będzie wyglądać następująco:

   S 
 / | \
a  S  a
 / | \
a  S  a    <--
 / | \
a  S  a
  / \
 a   a

s()trueSS.zaza

   S 
 / | \
a  S  a
  / \
 a   a

Zazwyczaj uważam to za problem w mojej implementacji, a nie w ogóle w przypadku parserów rekurencyjnego wycofywania.

#include <iostream>

char* next;    
bool term(char token) {
    if (*next != '\0')
        return *next++ == token;
    else
        return false;
}

bool s();    
bool s1() {
    return term('a') && s() && term('a');
}    
bool s2() {
    return term('a') && term('a');
}    
bool s() {
    auto save = next;
    return s1() or (next = save, s2());
}    

int main(int argc, char* argv[]) {
    next = "aaaaaa";
    if (s() && *next == '\0') {
        std::cout << "match";
    }
    else
        std::cout << "no match";
}
meribold
źródło
2

Jest to funkcja, a nie błąd

Przyjrzyj się, kiedy i gdzie występuje cofanie się:

     1.           2.          3.          4.          5.          6.          7.          8.          9.          10.         11.         12.

     S            S           S           S           S           S           S           S           S           S           S           S      
   / | \        / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \
  a  S  a      a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a
                / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       /   \
               a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a     a
                            / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \
                           a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a
                                        / | \       / | \       / | \       / | \       / | \       / | \       / | \       /   \
                                       a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a     a
                                                    / | \       / | \       / | \       / | \       / | \       /   \
                                                   a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a     a
                                                                / | \       / | \       / | \       /   \   
                                                               a  S  a     a  S  a     a  S  a     a     a
                                                                            / | \       /   \
                                                                           a  S  a     a     a



w[] = 'aaaaaa'  //input
l[] = ''        //current tree leafs


 1. tree:   The parser starts with the start symbol S and tries first alternative S->aSa:       Result: w[0]  = l[0]     w = aaaaaa    l = aSa
 |          -- S->aSa works                                                                         | |     | | 
 6. tree:   The parser matches a after a:                                                       Result: w[6]  = l[6]     w = aaaaaa    l = aaaaaaSaaaaaa
 7. tree:   The parser tries S->aSa again but there is no match!                                Result: w[7] != l[7]     w = aaaaaa    l = aaaaaaaSaaaaaaa 
 8. tree:   The parser tries S->aa but there is still no match!                                 Result: w[7] != l[7]     w = aaaaaa    l = aaaaaaaaaaaaaa
 9. tree:   Backtracking after the last symbol that matched => Backtracking at l[7]             Result: w[7] != l[7]     w = aaaaaa    l = aaaaaaaaaaaa
10. tree:   Backtracking after the last symbol that matched => Backtracking at l[7]             Result: w[7] != l[7]     w = aaaaaa    l = aaaaaaaaaa
11. tree:   Backtracking after the last symbol that matched => Backtracking at l[7]             Result: w[7] != l[7]     w = aaaaaa    l = aaaaaaaa
12. tree:   Backtracking after the last symbol that matched => Backtracking at l[7]             Result: w[7] != l[7]     w = aaaaaa    l = aaaa

Kluczową kwestią jest to, że parser cofa się po pozycji, w której znaleziono ostatnią pasującą postać. Właśnie dlatego „skacze” z drzewa 11 przy l = aaaaaaaa do 12. drzewa przy l = aaaa przy użyciu S -> aa przy l [7].

Sebbas
źródło
Nareszcie mam czas na edycję! ;)
Sebbas