Czy ktoś może mi dlaczego parser rekurencyjnego zejścia z produkcje i (w tej kolejności) nie rozpoznaje języka utworzonego przez gramatykę .
Wygląda na to, że analizuje tylko słowa z języka .
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 aaaaaa
na 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:a
S
/ | \
a S a
/ | \
a S a
/ \
a a
context-free
formal-grammars
compilers
parsers
meribold
źródło
źródło
aaaaaa
.aaaaaa
powinien parsować i nie. Aleaaaa
parsuje. Najwyraźniej masz rację, jeśli chodzi o potęgi 2. To musi być błąd. parsuje tylkoaa
zS = "aa" / "a" [S] "a"
. Czy potrafisz prześledzić, co robi parser?Odpowiedzi:
To nie jest duża odpowiedź, ale parsowania drzew nie pasują do normalnych komentarzy.
Twoja gramatyka należy analizować ciąg .S.→ a S.a | zaaaaaa
Ale parsowanie ma następującą postać:
lub jeśli wolisz tę prezentację, z terminalami na różnych liniach
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.{ a2)n | n≥1 }
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"
lubS = "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.
źródło
S ::= 'a'<S>'a' | 'a''a'
aaaaaa
Podczas używania nadal się nie analizujeS = "a" S "a" / "aa"
, ale wydaje się, że masz rację co do nawiasów.S = "a" S "a" / "aa"
... Testowałem zbyt szybko i kliknąłem generuj zamiast parsować.s1()
true
s()
s2()
Rozważ
aaaaaa
ponowne przeanalizowanie tego słowa . W pewnym momencie parsowanie będzie wyglądać następująco:s()
true
S
Zazwyczaj uważam to za problem w mojej implementacji, a nie w ogóle w przypadku parserów rekurencyjnego wycofywania.
źródło
Jest to funkcja, a nie błąd
Przyjrzyj się, kiedy i gdzie występuje cofanie się:
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].
źródło