Pytania otagowane jako parsing

5
Odzyskiwanie parsowanego lasu z parsera Earley?
Niedawno czytałem parser Earley i uważam, że jest to jeden z najbardziej eleganckich algorytmów, jakie do tej pory widziałem. Jednak algorytm w tradycyjnym znaczeniu jest rozpoznawaczem, a nie analizatorem składni, co oznacza, że ​​może wykryć, czy łańcuch pasuje do określonego CFG, ale nie wygenerować dla niego drzewa analizy. Moje pytanie …
1
Czy wszystkie jednoznaczne gramatyki można analizować w czasie liniowym?
Podczas majstrowania przy niekanonicznym analizowaniu LR wymyśliłem metodę analizy (z tabelami o nieskończonych rozmiarach, co czyni ją nieco niepraktyczną ), która jest w stanie przeanalizować dokładnie jednoznaczne gramatyki w czasie , i zastanawiałem się, czy można to zrobić lepiej :O(n2)O(n2)O(n^2) Czy wszystkie jednoznaczne gramatyki można analizować w czasie liniowym? Jestem …
3
Analiza CFG przy użyciu spacji
Istnieje wiele algorytmów, które mogą analizować gramatykę bezkontekstową w czasie . Używając mnożenia macierzy, można nawet iść asymptotycznie szybciej.O(n3)O(n3)O(n^3) Jednak wszystkie algorytmy do analizy dowolnych CFG, które znam, mają najgorsze wykorzystanie przestrzeni (chociaż, co prawda, nie mam pojęcia, jakie jest użycie przestrzeni przez ten algorytm mnożenia macierzy). Zastanawiałem się, czy …
3
Uogólnienia metody Brzozowskiego pochodnych wyrażeń regularnych do gramatyki?
Metoda pochodnych Brzozowskiego jest bardzo ładną techniką do budowania deterministycznych automatów z wyrażeń regularnych w ładnie algebraiczny sposób. Opracowałem kilka uroczych uogólnień tej techniki do obsługi niektórych większych klas gramatycznych, ale algorytmy są na tyle proste, że wydaje się całkiem możliwe, że zostały wcześniej odkryte. Ale wydaje się, że odniesienia …
2
Zwroty permutacyjne z analizą LR
Wyrażenie permutacji jest rozszerzeniem standardu (E) BNF wolne definicji kontekstu gramatyczne: frazę permutacji zawiera n produkcji (lub równoważnie nieterminale) A 1 przez A n . W miejscu wyrażenia permutacyjnego chcielibyśmy zobaczyć każdą z tych produkcji dokładnie raz, ale nie jesteśmy zainteresowani kolejnością tych nieterminali.{ A1, … , An}{ZA1,…,ZAn}\{ A_1, \dots, …
2
Wydajny algorytm do aktualizowania drzewa analizy
Powiedzmy, że mam duży blok kodu, który już sprawdziłem i przeanalizowałem. Załóżmy, że zmienia się tylko jedna postać; Chciałbym zaktualizować parsowanie, ale ponieważ modyfikacja jest bardzo niewielka w porównaniu do całości, chciałbym wiedzieć, czy nie można ponownie przeanalizować całości, ale czy istnieją algorytmy określające zakres do ponownej analizy i odpowiednio …
1
Zależność między analizą składniową redukującą przesunięcie a ograniczonymi kontynuacjami?
Czy ktoś sformalizował związek między technikami analizy składniowej redukującej przesunięcie a ograniczonymi kontynuacjami? Podczas konstruowania analizatora składniowego typu oddolnego (np. Parserów LR) bierzemy gramatykę, a następnie reprezentujemy stany analizy jako zestawy elementów : rozszerzone produkcje od postaci , gdzie i są sekwencje terminali i nieterminali. Marker reprezentuje, jak daleko parser …
1
Dlaczego Tomita stworzył GLR i nie używał Earleya?
Kiedy patrzę na parsowanie Earleya, wygląda to bardzo elegancko i zastanawiam się, dlaczego techniki GLR stały się popularne? Czy ktoś wie, co było nie tak z analizowaniem Earleya przez to, że Tomita stworzyła GLR? Wydajność? Wszelkie publikacje dotyczące tych dyskusji są bardzo mile widziane.
11 parsing 
4
Dobre książki na temat teorii parserów?
Jeden z moich projektów Java jest rozwidleniem parboiled i, w przeciwieństwie do powiedzmy Antlr lub JavaCC, parsery są generowane w czasie wykonywania. Generowane gramatyki to gramatyka wyrażeń parsujących lub PEG (słyszę, że innym terminem jest „packrat”). Podczas gdy generowanie środowiska wykonawczego zwiększa złożoność (generowanie kodu bajtowego), inny aspekt dotyczy samej …
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.