Pytania otagowane jako parsers

Pytania o algorytmy decydujące o tym, czy dany ciąg należy do ustalonego języka formalnego.

1
Czy istnieje jakiś nieogólny algorytm analizowania CFG, który rozpoznaje EPAL?
EPAL, język parzystych palindromów, jest definiowany jako język generowany przez następującą jednoznaczną, bezkontekstową gramatykę: S→aaS→aaS \rightarrow a a S→bbS→bbS \rightarrow b b S→aSaS→aSaS \rightarrow a S a S→bSbS→bSbS \rightarrow b S b EPAL jest „zmorą” wielu algorytmów parsowania: jeszcze nie spotkałem się z żadnym algorytmem parsowania dla jednoznacznych CFG, które …
2
Czy dla każdego wyrażenia „zła” istnieje nie-zła alternatywa, czy też diabeł w gramatyce?
Najwyraźniej ataki ReDos wykorzystują właściwości niektórych (poza tym użytecznych) wyrażeń regularnych ... zasadniczo powodując eksplozję możliwych ścieżek przez wykres zdefiniowany przez NFA. Czy można uniknąć takich problemów, pisząc równoważne wyrażenie „non-evil”? Jeśli nie (w związku z tym gramatyka nie może być obsługiwana przez NFA w praktycznej czasoprzestrzeni), jakie metody analizy …
1
Po co rozdzielać leksowanie i parsowanie?
Możliwe jest parsowanie dokumentu za pomocą pojedynczego przejścia z automatu stanów. Jaka jest korzyść z dwóch przejść, tj. posiadanie leksera do konwersji tekstu na tokeny i parsera do testowania reguł produkcyjnych dla tych tokenów? Dlaczego nie mieć pojedynczego przejścia, które stosuje reguły produkcji bezpośrednio do tekstu?
2
Co to jest parser IELR (1)?
Próbuję nauczyć się używania żubra. Bizon manpage (1) mówi o bizonie: Wygeneruj deterministyczny analizator składni LR lub uogólniony analizator składni LR (GLR), korzystając z tabel analizatora składni LALR (1), IELR (1) lub kanonicznej LR (1). Co to jest parser IELR? Wszystkie istotne artykuły, które znalazłem w sieci WWW, są płatne.
1
Kiedy
Zgodnie z artykułem Wikipedii , L w oznacza „skanowanie od lewej do prawej”, a „R” oznacza „pochodzenie od prawej”. Jednak w oryginalnym artykule Knutha na temat gramatyki definiuje (na stronie 610) jako język, który jest „możliwy do przetłumaczenia z lewej na prawą za pomocą związanego ”.L R ( k )L.R(k)LR(k)L …
5
Czym różni się brak jednoznaczności od determinizmu?
Próbuję zrozumieć, co należy rozumieć przez „deterministyczny” w wyrażeniach takich jak „deterministyczna gramatyka bezkontekstowa”. (W tej dziedzinie są bardziej deterministyczne „rzeczy”). Byłbym wdzięczny za przykład bardziej niż najbardziej wyszukane wyjaśnienie! Jeśli to możliwe. Moje główne źródło zamieszania polega na tym, że nie jestem w stanie powiedzieć, w jaki sposób ta …
2
Czy język wyrażeń regularnych wymaga automatycznych mechanizmów wypychania w celu jego parsowania?
Chcę przekonwertować wprowadzone przez użytkownika wyrażenie regularne na NFA, aby móc następnie uruchomić NFA dla łańcucha w celu dopasowania. Jakiej minimalnej maszyny można użyć do parsowania wyrażeń regularnych? Zakładam, że musi to być automat push, ponieważ obecność nawiasów oznacza konieczność liczenia, a DFA / NFA nie może wykonać dowolnego liczenia. …
3
Jaka jest ta gramatyka LL (1)?
To pytanie z Dragon Book. Oto gramatyka: S→AaAb∣BbBaS→AaAb∣BbBaS \to AaAb \mid BbBa A→εA→εA \to \varepsilon B→εB→εB \to \varepsilon Pytanie dotyczy tego, jak pokazać, że jest to LL (1), ale nie SLR (1). Aby udowodnić, że jest to LL (1), próbowałem zbudować jego tabelę analizującą, ale otrzymuję wiele produkcji w komórce, …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.