Maksymalne chrupanie

W programowaniu komputerowym i informatyce „ maksymalne chrupanie ” lub „ najdłuższe dopasowanie ” to zasada, zgodnie z którą przy tworzeniu jakiegoś konstruktu należy wykorzystać jak najwięcej dostępnych danych wejściowych.

Najwcześniejsze znane użycie tego terminu zostało użyte przez RGG Cattella w jego rozprawie doktorskiej na temat automatycznego wyprowadzania generatorów kodu dla kompilatorów .

Aplikacja

Na przykład składnia leksykalna wielu języków programowania wymaga, aby tokeny były budowane z maksymalnej możliwej liczby znaków ze strumienia wejściowego. Ma to na celu rozwiązanie problemu nieodłącznej dwuznaczności w powszechnie używanych wyrażeniach regularnych, takich jak [az]+ (jedna lub więcej małych liter).

Termin ten jest również używany w kompilatorach na etapie wyboru instrukcji do opisania metody „kafelkowania” - określania, w jaki sposób ustrukturyzowane drzewo reprezentujące program w języku pośrednim powinno zostać przekształcone w liniowy kod maszynowy . Całe poddrzewo można przekształcić w tylko jedną instrukcję maszynową, a problem polega na tym, jak podzielić drzewo na nienakładające się „kafelki”, z których każdy reprezentuje jedną instrukcję maszynową. Skuteczną strategią jest po prostu utworzenie kafelka największego możliwego poddrzewa w dowolnym punkcie, co nazywa się „maksymalnym chrupaniem”.

Wady

W niektórych sytuacjach „maksymalne chrupanie” prowadzi do niepożądanych lub nieintuicyjnych rezultatów. Na przykład w C instrukcja x=y/*z; (bez spacji) prawdopodobnie doprowadzi do błędu składniowego, ponieważ sekwencja znaków /* inicjuje (niezamierzony) komentarz, który jest albo niezakończony, albo zakończony tokenem końcowym */ jakiegoś późniejszego, niepowiązanego rzeczywistego komentarza (komentarze w C nie gniazdo). W stwierdzeniu chodziło właściwie o przypisanie zmiennej x wyniku dzielenia wartości przez y przez wartość uzyskaną przez wyłuskanie wskaźnika z ; byłby to prawidłowy kod. Można to stwierdzić, używając białych znaków lub używając x=y/(*z); .

Inny przykład, w C++ , wykorzystuje znaki „nawiasów kątowych” < i > w składni specjalizacji szablonu , ale dwa kolejne znaki > są interpretowane jako operator przesunięcia w prawo >> . W wersjach wcześniejszych niż C++11 poniższy kod powodowałby błąd analizy, ponieważ zamiast dwóch tokenów w nawiasach prostokątnych napotykano token operatora przesunięcia w prawo:

      
        std  ::  wektor  <  std  ::  wektor  <  int  >>  my_mat_11  ;  //Niepoprawnie w C++03, poprawnie w C++11.  std  ::  wektor  <  std  ::  wektor  <  int  >  >  my_mat_03  ;  //Poprawnie w C++03 lub C++11. 

Standard C++ 11 przyjęty w sierpniu 2011 r. zmienił gramatykę w taki sposób, że token przesunięty w prawo jest akceptowany jako synonim pary nawiasów prostokątnych (jak w Javie ), co komplikuje gramatykę, ale pozwala na dalsze używanie maksymalnego chrupania zasada. I tak trzeba było dodać wyjątek od reguły maksymalnego mlaskania, aby poradzić sobie z sekwencją <:: która może pojawić się w szablonach. W takim przypadku, chyba że po sekwencji występuje : lub > znak < jest interpretowany jako własny token zamiast części tokena <: .

Alternatywy

Badacze języków programowania również zareagowali, zastępując lub uzupełniając zasadę maksymalnego chrupania innymi taktykami ujednoznaczniania leksykalnego. Jednym ze sposobów jest zastosowanie „przestrzegania ograniczeń”, które zamiast bezpośredniego wybierania najdłuższego dopasowania, nałoży pewne ograniczenia na to, jakie postacie mogą podążać za prawidłowym dopasowaniem. Na przykład zastrzeżenie, że po ciągach pasujących do [az]+ nie może następować znak alfabetu, osiąga ten sam efekt, co maksymalne chrupanie z tym wyrażeniem regularnym. (W kontekście wyrażeń regularnych zasada maksymalnego chrupania jest określana jako chciwość i skontrastowane z lenistwem .) Innym podejściem jest zachowanie zasady maksymalnego chrupania, ale podporządkowanie jej innej zasadzie, takiej jak kontekst (np. token przesunięcia w prawo w Javie nie zostałby dopasowany w kontekście wyrażenia generycznego , gdzie jest składniowo niepoprawny).

Bibliografia

•   Aho, Alfred V.; Lam, Monika S.; Sethi, Ravi; Ullman, Jeffrey D. (2007). Kompilatory: zasady, techniki i narzędzia (wyd. 2). Boston: Addison-Wesley. ISBN 978-0-321-48681-3 .
•   Strona, Daniel (2009). „Kompilatory”. Praktyczne wprowadzenie do architektury komputerów . Teksty z informatyki . Londyn: Springer. s. 451–493. doi : 10.1007/978-1-84882-256-6_11 . ISBN 978-1-84882-255-9 .
•    Van den Brand, Mark GJ; Scheerder, Jeroen; Vinju, Jurgen J.; Visser, Eelco (2002). Filtry ujednoznaczniające dla uogólnionych parserów LR bez skanera . Notatki z wykładów z informatyki . Tom. 2304/2002. Berlin/Heidelberg: Springer. s. 21–44. doi : 10.1007/3-540-45937-5_12 . ISBN 978-3-540-43369-9 . ISSN 0302-9743 .
• Vandevoorde, Daveed (14 stycznia 2005). „Nawiasy kątowe” . Źródło 31 marca 2010 r .
•   Van Wyk, Eric; Schwerdfeger, sierpień (2007). Skanowanie zależne od kontekstu w celu analizowania języków rozszerzalnych . GPCE '07: Materiały z 6. Międzynarodowej Konferencji na temat programowania generatywnego i inżynierii komponentów . Nowy Jork: ACM. s. 63–72. doi : 10.1145/1289971.1289983 . ISBN 9781595938558 .