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.$\{ A_1, \dots, A_n \}$$n$$A_1$$A_n$

Na przykład:

S <- X { A, B, C } Y

jest równa:

S <- X  A B C  Y
S <- X  A C B  Y
S <- X  B A C  Y
S <- X  B C A  Y
S <- X  C A B  Y
S <- X  C B A  Y

Wydaje się, że koncepcja została wprowadzona w „Rozszerzaniu gramatyki bezkontekstowej o frazy permutacyjne” . W tym dokumencie opisano również, jak parsować te frazy w czasie liniowym za pomocą parsera LL (1).

Artykuł „Przetwarzanie wyrażeń permutacyjnych” opisuje metodę analizowania wyrażeń permutacyjnych przy użyciu kombinacji parserów. To jedyne dwa artykuły, które znalazłem, które mówią o frazach permutacyjnych i jak je parsować.

Widząc, że możemy łatwo parsować tego rodzaju frazy permutacji za pomocą parserów opartych na LL (1), domyślam się, że możemy zrobić to samo z parserami w stylu LR (1). Moje pytanie brzmi zatem:

Czy gramatykę zawierającą wyrażenia permutacyjne można analizować liniowo w czasie w rozmiarze łańcucha wejściowego za pomocą maszyny LR (1), zachowując przy tym tabelę o rozsądnych rozmiarach?

$O(|G|!)$

$O(2^{|G|})$

Chociaż jest to lepsze, to oczywiście nie jest wystarczająco dobre - użycie wyrażenia permutacji złożonego z 30 elementów sprawiłoby, że gramatyka byłaby bezużyteczna. Jest jeszcze jedna część parsowania LR, której jeszcze nie dotknęliśmy, i jest to rzeczywista procedura oparta na stosie używana do parsowania. Wyobrażam sobie, że przechowywanie liczników na stosie może rozwiązać problem, ale nie jestem pewien, jak to zrobić.

Obecnie wdrażam generator parsera, a problematyczne wyrażenia permutacyjne byłyby darem z nieba. Kiedy używam maszyn LR (1), nastąpiło powyższe pytanie.

Czy zastanawiałeś się nad przekształceniem tego w problem semantyczny? Zamiast reguł gramatycznych dla wszystkich permutacji nieterminali {A, B, C}, wystarczy jedna reguła do rozpoznawania (A | B | C) ^ 3 wraz ze specjalnym kodem wewnętrznym, który upewnia się, że tylko jeden z nich jest rozpoznawany, w przeciwnym razie deklaruje błąd. Wstawiłbym pustą produkcję przed powyższą klauzulą, której redukcja uruchamia inicjalizację tego, czego używasz do zliczania A, B i C, a następnie, której redukcja uruchamia kontrole i (jeśli to konieczne) potwierdza błąd. (oczywiście może to być nieco trudne, jeśli gramatyka jest rekurencyjna przez A, B i / lub C)

Nie sądzę, żeby ktoś potrzebował licznika. Zasadniczo po prostu sprawdzasz wszystkie permutacje, ale się psujesz

pseudo kod:

perm-match(input, pattern)
     if pattern = nil return true

     foreach(rule in pattern)
         if (match(input, rule))
             perm-match(input - matchedpart, pattern - rule)
             break
         end
     end
     return false
end

Oto bardziej konkretny przykład

Załóżmy, że próbujemy dopasować dowolną permutację abcd, a naszym ciągiem jest bcda

• Krok 1: Znajdź pierwszy pasujący symbol. W tym przypadku jest to b
• Krok 2: Usuń ten symbol z naszego wzorca i zmniejsz ciąg: np. Acd i cda są pozostawione
• Krok 3: Powtórz krok 1 dla nowych ciągów
  • c pasuje do cda, co pozostawia nam reklamy i da
  • mecze w da, które pozostawiają nam d i d
  • d pasuje do d, co pozostawia nam zero w obu ciągach

Widzisz więc, że ten prosty algorytm może dość łatwo sprawdzić permutację, porównując po prostu „ciągi” niedziałające. Zauważ, że złożoność funkcji to O (n!) Najgorszy przypadek i O (1) najlepszy przypadek. W pewnym sensie liczymy, przechowując symbole w celu dopasowania w tablicy. Sądzę, że byłby to ogólnie „szybki”, ponieważ w większości przypadków nie poradziłby sobie bardzo duży n.