В компьютерном программировании и информатике « максимальное потребление » или « самое длинное совпадение » — это принцип, согласно которому при создании некоторой конструкции должно быть использовано как можно больше доступных входных данных.
Самое раннее известное использование этого термина принадлежит Р. Г. Г. Кеттеллу в его докторской диссертации [1] об автоматическом выводе генераторов кода для компиляторов .
Например, лексический синтаксис многих языков программирования требует, чтобы токены строились из максимально возможного количества символов из входного потока. Это делается для решения проблемы внутренней неоднозначности в часто используемых регулярных выражениях, таких как [a-z]+(одна или несколько строчных букв). [2]
Этот термин также используется в компиляторах на этапе выбора инструкций для описания метода «плиточного» — определения того, как структурированное дерево, представляющее программу на промежуточном языке , должно быть преобразовано в линейный машинный код . Целое поддерево может быть преобразовано всего в одну машинную инструкцию, и проблема заключается в том, как разбить дерево на неперекрывающиеся «плитки», каждая из которых представляет одну машинную инструкцию. Эффективная стратегия — просто сделать плитку из наибольшего поддерева, возможного в любой заданной точке, что называется «максимальным пережевыванием». [3]
В некоторых ситуациях "максимальный мунч" приводит к нежелательным или неинтуитивным результатам. Например, в языке программирования C оператор x=y/*z;(без пробелов) вероятно приведет к синтаксической ошибке, поскольку /*последовательность символов (непреднамеренно) инициирует комментарий, который либо не завершен, либо завершен конечным маркером */некоторого более позднего, не связанного фактического комментария (комментарии в C не вкладывают друг в друга). На самом деле в операторе подразумевалось присвоение переменной xрезультата деления значения на yзначение, полученное путем разыменования указателя z ; это будет допустимый код. Его можно указать, используя пробелы или используя x=y/(*z);.
Другой пример, в C++ , использует символы «угловых скобок» <и >в синтаксисе для специализации шаблона , но два последовательных >символа интерпретируются как оператор сдвига вправо>> . [4] До C++11 следующий код вызывал ошибку синтаксического анализа, поскольку вместо двух токенов правых угловых скобок встречается токен оператора сдвига вправо:
std :: vector < std :: vector < int >> my_mat_11 ; //Неверно в C++03, верно в C++11. std :: vector < std :: vector < int > > my_mat_03 ; //Верно либо в C++03, либо в C++11. Стандарт C++11 , принятый в августе 2011 года, внес поправки в грамматику таким образом, что токен сдвига вправо принимается как синоним пары правых угловых скобок (как в Java ), что усложняет грамматику, но позволяет продолжать использовать принцип максимального пережевывания. Исключение из правила максимального пережевывания должно было быть добавлено в любом случае, чтобы иметь дело с последовательностью <::, которая может появляться в шаблонах. В этом случае, если только за последовательностью не следует :или >символ <не интерпретируется как его собственный токен, а не часть токена <:.
Исследователи языков программирования также отреагировали, заменив или дополнив принцип максимального пережевывания другими тактиками устранения лексической неоднозначности. Один из подходов заключается в использовании «ограничений следования», которые вместо прямого взятия самого длинного совпадения накладывают некоторые ограничения на то, какие символы могут следовать за допустимым совпадением. Например, условие, что за сопоставлением строк [a-z]+не может следовать алфавитный символ, достигает того же эффекта, что и максимальное пережевывание с этим регулярным выражением. [5] (В контексте регулярных выражений принцип максимального пережевывания называется жадностью и противопоставляется лени .) Другой подход заключается в том, чтобы сохранить принцип максимального пережевывания, но подчинить его некоторому другому принципу, такому как контекст ( например , токен сдвига вправо в Java не будет сопоставлен в контексте выражения generics , где он синтаксически недопустим). [6]