Pytania oznaczone «parsers»

Ludzie często mówią, że parsery LR (k) są silniejsze niż parsery LL (k) . Te stwierdzenia są przez większość czasu niejasne; w szczególności, czy powinniśmy porównać klasy dla ustalonego kkk lub unii dla całego kkk ? Jak więc naprawdę wygląda sytuacja? W szczególności jestem zainteresowany tym, jak...

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...

Chcę przeanalizować zdefiniowane przez użytkownika języki specyficzne dla domeny. Te języki są zazwyczaj zbliżone do notacji matematycznych (nie analizuję języka naturalnego). Użytkownicy definiują swoje DSL w notacji BNF, w następujący sposób: expr ::= LiteralInteger | ( expr ) | expr + expr |...

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...

Jeśli mam gramatykę typu 3, można ją przedstawić na automacie wypychania (bez wykonywania żadnych operacji na stosie), dzięki czemu mogę reprezentować wyrażenia regularne przy użyciu języków bezkontekstowych. Ale czy mogę wiedzieć, czy gramatyka typu 3 to , , itd. Bez konstruowania jakichkolwiek...

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...

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...

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...

Myślałem o gramatyce dla języków wrażliwych na indukcje i wygląda na to, że gramatyki CF zrobiłyby to samo, gdyby były połączone z parametrami. Jako przykład rozważ ten fragment uproszczonej gramatyki języka Python w formacie podobnym do ANTLR: // on top-level the statements have empty...

Mam problem z tym ćwiczeniem: Niech G będzie następującą dwuznaczną gramatyką dla rachunku λ: E → v | λv.E | EE | (E) gdzie E jest pojedynczym nieterminalnym symbolem, λv.E oznacza abstrakcję względem zmiennej v w E, a EE oznacza aplikację. Zdefiniuj gramatykę LL (1) G ′, tak aby L...

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...

Często pracuję z lexer / parserami , w przeciwieństwie do kombinatora parserów i widzę osoby, które nigdy nie brały udziału w analizie składniowej, pytają o przetwarzanie danych binarnych. Zazwyczaj dane są nie tylko binarne, ale także kontekstowe. Zasadniczo prowadzi to do posiadania tylko jednego...

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...

Ostatnio studiuję na temat projektowania kompilatorów. Dowiedziałem się o dwóch rodzajach gramatyki: jedna to gramatyka LL, a druga to gramatyka LR. Znamy również fakty, że każda gramatyka LL jest LR, czyli gramatyka LL jest właściwym podzbiorem gramatyki LR. Pierwszy jest używany podczas analizy...

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...

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.→ a S.zaS.→zaS.zaS \rightarrow aSaS.→ a aS.→zazaS \rightarrow aaS.→ a S.a |   S.→zaS.za | zazaS \rightarrow aSa\ |\ aa Wygląda na to, że analizuje tylko...

W parserze LR (0) każdy stan składa się z kolekcji elementów LR (0), które są produkcjami opatrzonymi adnotacją pozycją. W parserze LR (1) każdy stan składa się z kolekcji elementów LR (1), które są produkcjami opatrzonymi adnotacją pozycją i znakiem z wyprzedzeniem. Wiadomo, że biorąc pod uwagę...

Istnieje sposób wykonywania rozmytego parsowania (akceptuje ciągi nawet w literówkach do określonej odległości edycji), z DFA i skonstruowanymi w czasie wykonywania automatami Levenshtein słowa wejściowego. Czy coś podobnego można zrobić z parserem Earley? Trudno mi zrozumieć algorytm, a co dopiero...

Na studiach poznawaliśmy ogólnie teorię obliczeń, a dokładniej maszyny Turinga. Jednym z wielkich wyników teoretycznych jest to, że kosztem potencjalnie dużego alfabetu (symboli) można zmniejszyć liczbę stanów do zaledwie 2. Szukałem przykładów różnych maszyn Turinga, a częstym przedstawionym...

Użycie wektora Earleya jako rozpoznającego jest dość proste: po osiągnięciu końca struny wystarczy sprawdzić, czy produkcja aksjomatyczna została rozpoczęta w pozycji 0. Jeśli masz przynajmniej jeden ciąg, łańcuch jest akceptowany. Użycie wektora Earleya do odtworzenia drzewa przetwarzania jest...