Czy istnieje inna rozdzielczość problemu „zwisające inaczej” niż „najbliższy odpowiednik”?

9

Poniższa gramatyka bezkontekstowa przedstawia dwuznaczność typu „wiszące inne” (wyobraź to sobie aoznacza if expr theniboznacza elseic oznacza inny rodzaj instrukcji lub bloku):

SaSbS|aS|c
Na przykład, aacbc może być analizowany jako (a(acbc)) lub jako (a(ac)bc) (jest to najprostsze / najkrótsze niejednoznaczne słowo dla tej gramatyki).

„Standardowy” sposób rozwiązania tej dwuznaczności „zwisające inaczej” wymusza „inne” (b), aby sparować z najbliższym / najbardziej wewnętrznym „if-then” (a). Można to zrobić w następujący sposób:

SaTbS|aS|cTaTbT|c
Ta gramatyka jest jednoznaczna. W powyższym przykładzie wymusza(a(acbc)) rozbiór gramatyczny zdania.

Pytanie: Czy istnieje inny naturalny sposób rozwiązania dwuznaczności, która wymusiłaby(a(ac)bc) parsowanie aacbc? Innymi słowy, szukam gramatyki, która generuje ten sam język co dwa powyższe, która jest jednoznaczna i która analizujeaacbc tak jak (a(ac)bc).

Uwaga: Moja pierwsza próba była następująca:

SaSbS|aU|cUaU|c
co rozwiązuje niejednoznaczność aacbc zgodnie z wymaganiami - ale ta gramatyka jest nadal niejednoznaczna: aacbacbc może być analizowany jako (a(ac)b(acbc)) lub jako (a(acb(ac))bc).
Gro-Tsen
źródło
1
A w twoim ostatnim przykładzie, które z dwóch możliwych parów uważasz za „naturalne” lub prawidłowe i dlaczego?
rici
@rici Tak, to podchwytliwe pytanie !, i nie wiem. Będę szczęśliwy z jednoznaczną gramatyką, która powoduje parsowanieaacbacbc. Najbardziej zależy mi na tymaaaaaacbcbcbc (z więcej ajest niż b's) pasuje do k- ostatni b z k-ty a (i opuszcza wnętrze anie ma sobie równych).
Gro-Tsen

Odpowiedzi:

7

Ten problem jest dokładnym odpowiednikiem problemu dopasowywania nawiasów w wyrażeniu, w którym pominięto niektóre z bliskich nawiasów. Tutaj „if” (luba w gramatyce reprezentatywnej) jest otwartym nawiasiem i „innym” (b) to ścisły nawias. (Z sekwencjias i bmożesz wstawić mechanicznie cs, umieszczając po jednym przed każdym b i jeden na samym końcu.) Ponieważ lepiej pasuje do mojego nawiasowego mózgu, piszę tak, jakby to był problem.

Tradycyjna rozdzielczość „dopasuj najbliżej”, wisząca w innym przypadku, dopasowuje każde zamknięcie z najnowszą, jak dotąd niedopasowaną otwartą. Oznacza to, że nigdy nie ma niedopasowanego otwarcia (lub zamknięcia, jeśli o to chodzi) między dopasowanym otworem a pasującym zamknięciem.

Jedną z możliwych alternatyw byłoby dopasowanie każdego zamknięcia do najwcześniejszego możliwego niedopasowanego otwarcia. „Wykonalne” oznacza tutaj, że otwartą można dopasować bez naruszania zagnieżdżenia rodzicielskiego (np. Pierwszego( w ()() nie może realnie pasować do ostatniego )).

To dopasowanie musi być wykonane na zewnątrz, aby dopasowanie do zamknięcia nie było podejmowane, dopóki wszystkie otaczające pary nie zostaną dopasowane. Fakt ten uniemożliwia utworzenie analizy z użyciem algorytmu z ograniczonym spojrzeniem, ponieważ analiza musi działać do wewnątrz z obu końców po podzieleniu łańcucha na całkowicie dopasowane segmenty (ponieważ te skutecznie ograniczają zakres potencjalnych dopasowań).

Jednak fakt, że internetowy parser od lewej do prawej nie istnieje, nie oznacza, że ​​nie ma jednoznacznego CFG. (Oczywiście: język palindromiczny musi zostać przeanalizowany z obu końców w kierunku środka, ale łatwo jest napisać jednoznaczną gramatykę).

Aby stworzyć gramatykę dla problemu nawiasów „najdalej dopasowanego”, polegałem na tym, że po niedopasowanym otwarciu nie może nastąpić dopasowany otwór. Gdyby tak było, właściwość najodleglejszego dopasowania nie miałaby zastosowania, ponieważ niedopasowane otwarcie mogłoby pasować do zamknięcia dopasowanego otwarcia, więc fakt, że jest ona niedopasowana, narusza właściwość najdalszego dopasowania.

Oto nieco niezgrabna gramatyka:

SU|MUT|aUbT|aUbc|aMbUMaMbM|cTaT|ac

S jest symbolem początkowym; M są w pełni dopasowanymi instrukcjami; U są zdecydowanie niedopasowanymi instrukcjami (co oznacza, że ​​zawierają co najmniej jedną niedopasowaną instrukcję) a, więc nie mogą być puste) i T jest „ogonem” składającym się tylko z niedopasowanych as. Powyższy fakt o niedopasowanych otwarciach można odczytać bezpośrednio z gramatyki: wszystkie niedopasowane otwarcia są pochodnąT, a T może pojawić się tylko na końcu litery Uoraz U może następować tylko T.

Niezręczność wynika z zapobiegania Uz dopasowania pustego ciągu. Zapobiega to wielu tym, co uważam za fałszywe dwuznaczności: są one fałszywe w tym sensie, że dopasowanie otwarcia i zamknięcia jest takie samo we wszystkich alternatywnych parsach. GdybyUjest dozwolone zerowanie, będzie również wyprowadzać całkowicie zrównoważony ciąg. OdS jest w efekcie MU, prowadzi to do dwuznaczności, w której można uznać za całkowicie zrównoważoną S być serią M następnie pusty Ulub jeden mniej M a następnie całkowicie zrównoważony U.

Prawdopodobnie istnieje lepsze obejście niż to, które wybrałem. Ale ten wydaje się działać i dobrze współpracuje z parserem GLR Bison, którego testowałem; ten parser narzeka na niejednoznaczne analizy, chyba że napiszesz dodatkowy kod, aby poradzić sobie z niejednoznacznością, a ja byłem zbyt leniwy, aby to zrobić. Testowałem go z ciągami do 20 otwartych i zamkniętych i wydaje się, że wytworzył jednoznaczną analizę dla każdej poprawnie zagnieżdżonej sekwencji, bez tworzenia analiz dla nieprawidłowo zagnieżdżonych sekwencji.

rici
źródło
Gratulacje osiągnięcia tego, co doszedłem, było prawdopodobnie niemożliwe! Sprawdziłem eksperymentalnie, że dla słów o długości ≤16 gramatyka ta jest rzeczywiście jednoznaczna i generuje te same słowa, co te w moim pytaniu. Teraz muszę szczegółowo zrozumieć, jak to działa!
Gro-Tsen
@ Gro-Tsen: Mam nadzieję, że drugi akapit pomoże to wyjaśnić. Gramatyka jest znacznie prostsza, a pozorne niejasności pozostały w:SaSbT|aMbS (M jak w moim rozwiązaniu TaT|c) i tak wpadłem na pomysł, gdy myślałem o problemie. Trochę czasu zajęło mi przekonanie siebie, że trzeba to zrobićUbyć niedopuszczalnym, aby uniknąć dwuznacznych analiz (chociaż, jak powiedziałem, dwuznaczność jest względna), i chwilę dłużej omijać mój niechęć do sposobu, w jaki zdecydowałem się to wymusić. Założę się, że jest bardziej elegancka prezentacja.
rici
0

Weź + b + c + d + e i abcde. Są dwa oczywiste sposoby, w jaki gramatyka może je przeanalizować, ale jest jeden sposób, którego używamy.

W przypadku „wiszącego innego”, tak naprawdę ludzie na to nie patrzą. Zamiast tego składnia jest interpretowana jako „if”, po której następuje zero, jeden lub więcej „else if”, po których następuje opcjonalny „else”.

gnasher729
źródło
Zauważ, że „jeśli… to… inaczej… jeśli… to… jeszcze… jeśli… to… jeszcze…” odpowiada acbacbacbcw mojej notacji: jest to parsowane jednoznacznie przez moją początkową gramatykę (i warianty, które zgadzam się zgodzić), więc nie pytam o alternatywną analizę tego.
Gro-Tsen