Co parsowanie bez skanera ma wspólnego z „Dangling Else Problem”?

Nie rozumiem tego zdania z artykułu w Wikipedii na temat problemu Dangling Else :

[Problem Dangling Else] to problem, który często pojawia się w konstrukcji kompilatora, szczególnie w parsowaniu bez skanera.

Czy ktoś może mi wyjaśnić, w jaki sposób techniki analizy bez skanera mogą zaostrzyć ten problem? Wydaje mi się, że problem dotyczy gramatyki - ponieważ jest niejednoznaczna - a nie wyboru techniki analizy składniowej. czego mi brakuje?

Domyślam się, że zdanie w artykule z Wikipedii wynika z nieporozumienia dotyczącego pracy E. Vissera.

Gramatyki parserów bez skanera (tj. Gramatyki opisujące język jako zbiór sekwencji znaków zamiast zestawu sekwencji tokenów z tokenami opisanymi osobno jako ciągi znaków) zwykle mają wiele dwuznaczności. E. Papier Visser Filtry ujednoznaczniające dla uogólnionych parserów LR bez skanera (*) proponuje kilka mechanizmów rozwiązywania niejednoznaczności, z których jeden jest przydatny do rozwiązania problemu innego, wiszącego. Ale w artykule nie stwierdzono, że dokładna dwuznaczność zwana „problemem zwisającym inaczej” jest związana z parserami bez skanera (ani nawet, że mechanizm jest szczególnie użyteczny w parserach bez skanera).

Fakt, że proponuje mechanizm jego rozwiązania, nie jest niejawnym stwierdzeniem, ponieważ inny mechanizm rozwiązywania niejednoznaczności (priorytet i pierwszeństwo operatora) wydaje się również całkowicie niezwiązany z pozbawioną skanera charakterem rozważanych analizatorów składni (na przykład, że tych dwuznaczności nie można obecne w gramatyce zwykłej, ponieważ wynikają z zagnieżdżania, a te obsługiwane przez regułę najdłuższego dopasowania).

(*) Prawdopodobnie jest to papier służący jako podstawa artykułu z Wikipedii na temat parserów bez skanera, nawet jeśli odnoszą się do innego, również przez E. Vissera, Scannerless Generalized-LR Parsing .

Aby stwierdzić problem, Dangling Else Problem to dwuznaczność w specyfikacji składni kodu, w której może być niejasny, w przypadku następnych ifs i els, do których jeszcze należy.

Najprostszy i klasyczny przykład:

if(conditionA)
if(conditionB)
   doFoo();
else
   doBar();

Jest to niejasne dla tych, którzy nie znają na pamięć specyfiki języka, który ifotrzymuje else(a ten konkretny fragment kodu jest poprawny w pół tuzina języków, ale może działać inaczej w każdym z nich).

Konstrukcja Dangling Else stanowi potencjalny problem dla implementacji analizatora składni bez skanera, ponieważ strategia polega na zarzucaniu strumienia plików po jednym znaku na raz, dopóki analizator składni nie zobaczy, że ma on wystarczająco dużo do tokenizacji (trawienie w asemblerze lub języku pośrednim, który kompiluje) . Umożliwia to parserowi utrzymanie stanu minimalnego; gdy tylko uzna, że ​​ma wystarczającą ilość informacji, aby zapisać tokeny, które jest parsowane do pliku, zrobi to. To jest końcowy cel parsera bez skanera; szybka, prosta, lekka kompilacja.

Zakładając, że znaki nowej linii i białe znaki przed lub po interpunkcji są bez znaczenia (jak w większości języków w stylu C), to stwierdzenie wydaje się kompilatorowi jako:

if(conditionA)if(conditionB)doFoo();else doBar;

Doskonale parsowalny do komputera, więc zobaczmy. Dostaję jedną postać na raz, dopóki nie będę:

if(conditionA)

Och, wiem, co to oznacza (w języku C #), oznacza to „ pushwarunekA na stosie ewaluacji, a następnie wywołanie, brfalseaby przejść do instrukcji po następnym średniku, jeśli nie jest to prawda”. W tej chwili nie widzę średnika, więc na razie ustawię przesunięcie skoku do następnej spacji po tej instrukcji i zwiększę to przesunięcie, gdy wstawię więcej instrukcji, aż zobaczę średnik. Kontynuowanie analizy ...

if(conditionB)

OK, to analizuje podobną parę operacji IL i następuje natychmiast po instrukcji, którą właśnie przeanalizowałem. Nie widzę średnika, więc zwiększę przesunięcie skoku mojej poprzedniej instrukcji o długość moich dwóch poleceń (jednego dla push i jeden dla breaka) i nadal szukam.

doFoo();

Ok, to proste. To jest „ calldoFoo”. I czy to jest średnik, który widzę? To wspaniale, to koniec linii. Zwiększę przesunięcia obu bloków o długość tych dwóch poleceń i zapomnę, że kiedykolwiek mnie to obchodziło. OK, kontynuuję ...

else

... O o. To nie jest tak proste, jak się wydawało. OK, zapomniałem, co właśnie robiłem, ale elseoznacza to, że gdzieś już widziałem warunkowe polecenie przerwania, więc pozwól mi spojrzeć wstecz ... tak, brfalseoto jest , zaraz po tym, jak włączyłem „warunek B” stos, cokolwiek to było. OK, teraz potrzebuję bezwarunkowego breakjako następnego oświadczenia. Stwierdzenie, które nastąpi później, jest teraz zdecydowanie celem mojego warunkowego przerwania, więc upewnię się, że mam rację, i zwiększę bezwarunkową przerwę, którą wprowadziłem. Przechodząc ...

doBar();

To łatwe. „ calldoBar”. I jest średnik i nigdy nie widziałem żadnych aparatów ortodontycznych. Zatem bezwarunkowy breakpowinien przejść do następnego stwierdzenia, cokolwiek to jest, i mogę zapomnieć, że kiedykolwiek mnie to obchodziło.

A więc, co mamy ... (uwaga: jest 22:00 i nie mam ochoty konwertować offsetów bitowych na szesnastkowy lub wypełniać pełnej powłoki IL funkcji za pomocą tych poleceń, więc to tylko pseudo-IL przy użyciu numerów linii, w których zwykle byłyby przesunięcia bajtów):

ldarg.1 //conditionA
brfalse <line 6> //jumps to "break"
ldarg.2 //conditionB
brfalse <line 7> //jumps to "call doBar"
call doFoo
break <line 8> //jumps beyond statement in scope
call doBar
<line 8 is here>

Cóż, to faktycznie działa poprawnie, JEŻELI reguła (jak w większości języków w stylu C) jest taka, że elseidzie z najbliższym if. Wciśnięty, aby śledzić zagnieżdżanie wykonania, działałby w ten sposób, w przypadku gdy warunek A jest fałszywy, cała pozostała część fragmentu kodu jest pomijana:

if(conditionA)
    if(conditionB)
       doFoo();
    else
       doBar();

... ale robi to przypadkowo, ponieważ przerwa związana z instrukcją zewnętrzną ifprzeskakuje do breakinstrukcji na końcu instrukcji wewnętrznej if , co powoduje, że wskaźnik wykonania wykracza poza całą instrukcję. Jest to dodatkowy niepotrzebny skok, a jeśli ten przykład byłby bardziej złożony, mógłby przestać działać, jeśli zostałby parsowany i tokenizowany w ten sposób.

A co, jeśli specyfikacja języka mówi, że zwisanie elsenależy do pierwszego if, a jeśli warunek A jest fałszywy, to wykonywany jest doBar, a jeśli warunek A jest prawdziwy, ale nie warunek B, to nic się nie dzieje?

if(conditionA)
    if(conditionB)
       doFoo();
else
   doBar();

Analizator składni zapomniał o istnieniu pierwszego if, a zatem ten prosty algorytm analizatora składni nie wygenerowałby poprawnego kodu, nie mówiąc już o wydajnym kodzie.

Teraz parser może być wystarczająco inteligentny, aby zapamiętać ifs i elses przez dłuższy czas, ale jeśli specyfikacja języka mówi, że pojedynczy elsepo dwóch ifs pasuje do pierwszego if, to powoduje problem z dwoma ifs z dopasowaniem elses:

if(conditionA)
    if(conditionB)
       doFoo();
    else
       doBar();
else
    doBaz();

Parser zobaczy pierwszy else, dopasuje do pierwszego if, a następnie zobaczy drugi i przejdzie w panikę w trybie „co do diabła robiłem ponownie”. W tym momencie parser ma dość dużo kodu w stanie umożliwiającym modyfikację, który wolałby już wypchnąć do wyjściowego strumienia plików.

Istnieją rozwiązania wszystkich tych problemów i co-jeśli. Ale albo kod musi być taki, że smart zwiększa złożoność algorytmu analizatora składni, lub specyfikacja języka pozwalająca analizatorowi na tak niemądry zwiększa szczegółowość kodu źródłowego języka, na przykład poprzez wymaganie zakończenia instrukcji typu end iflub nawiasów wskazujących zagnieżdżenie blokuje, jeśli ifinstrukcja ma else(oba są powszechnie widoczne w innych stylach językowych).

To tylko jeden, prosty przykład kilku ifinstrukcji, i spójrz na wszystkie decyzje, które musiał podjąć kompilator, i gdzie i tak mógł się łatwo pomylić. Taki jest szczegół tego niewinnego oświadczenia Wikipedii w twoim pytaniu.