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

Poniższa gramatyka bezkontekstowa przedstawia dwuznaczność typu „wiszące inne” (wyobraź to sobie $a$oznacza if expr theni$b$oznacza elsei$c$ oznacza inny rodzaj instrukcji lub bloku):

$$\begin{aligned} S &\rightarrow aSbS \;|\; aS \;|\; c\\ \end{aligned}$$ 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:

$$\begin{aligned} S &\rightarrow aTbS \;|\; aS \;|\; c\\ T &\rightarrow aTbT \;|\; c\\ \end{aligned}$$ 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 analizuje$aacbc$ tak jak $(a(ac)bc)$.

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

$$\begin{aligned} S &\rightarrow aSbS \;|\; aU \;|\; c\\ U &\rightarrow aU \;|\; c\\ \end{aligned}$$ 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)$.

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” (lub$a$ w gramatyce reprezentatywnej) jest otwartym nawiasiem i „innym” ($b$) to ścisły nawias. (Z sekwencji$a$s i $b$możesz wstawić mechanicznie $c$s, 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:

$$\begin{aligned} S&\to U \;|\; M \\ U&\to T \;|\; a U b T \;|\; a U b c \;|\; a M b U \\ M&\to a M b M \;|\; c \\ T&\to a T \;|\; a c \\ \end{aligned}$$

$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 $a$s. 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 $U$oraz $U$ może następować tylko $T$.

Niezręczność wynika z zapobiegania $U$z 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. Gdyby$U$jest dozwolone zerowanie, będzie również wyprowadzać całkowicie zrównoważony ciąg. Od$S$ jest w efekcie $M^* U$, prowadzi to do dwuznaczności, w której można uznać za całkowicie zrównoważoną $S$ być serią $M$ następnie pusty $U$lub 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.

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