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?
if a then if b then s1 else s2
, to gramatyka jest niejednoznaczna.Odpowiedzi:
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 .
źródło
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:
Jest to niejasne dla tych, którzy nie znają na pamięć specyfiki języka, który
if
otrzymujeelse
(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:
Doskonale parsowalny do komputera, więc zobaczmy. Dostaję jedną postać na raz, dopóki nie będę:
Och, wiem, co to oznacza (w języku C #), oznacza to „
push
warunekA na stosie ewaluacji, a następnie wywołanie,brfalse
aby 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 ...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.
Ok, to proste. To jest „
call
doFoo”. 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ę ...... O o. To nie jest tak proste, jak się wydawało. OK, zapomniałem, co właśnie robiłem, ale
else
oznacza to, że gdzieś już widziałem warunkowe polecenie przerwania, więc pozwól mi spojrzeć wstecz ... tak,brfalse
oto jest , zaraz po tym, jak włączyłem „warunek B” stos, cokolwiek to było. OK, teraz potrzebuję bezwarunkowegobreak
jako 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 ...To łatwe. „
call
doBar”. I jest średnik i nigdy nie widziałem żadnych aparatów ortodontycznych. Zatem bezwarunkowybreak
powinien 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):
Cóż, to faktycznie działa poprawnie, JEŻELI reguła (jak w większości języków w stylu C) jest taka, że
else
idzie z najbliższymif
. 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:... ale robi to przypadkowo, ponieważ przerwa związana z instrukcją zewnętrzną
if
przeskakuje dobreak
instrukcji na końcu instrukcji wewnętrznejif
, 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
else
należy do pierwszegoif
, 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?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ć
if
s ielse
s przez dłuższy czas, ale jeśli specyfikacja języka mówi, że pojedynczyelse
po dwóchif
s pasuje do pierwszegoif
, to powoduje problem z dwomaif
s z dopasowaniemelse
s:Parser zobaczy pierwszy
else
, dopasuje do pierwszegoif
, 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 if
lub nawiasów wskazujących zagnieżdżenie blokuje, jeśliif
instrukcja maelse
(oba są powszechnie widoczne w innych stylach językowych).To tylko jeden, prosty przykład kilku
if
instrukcji, 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.źródło