Войти
В компьютерном программировании и информатике « максимальное количество еды » или « максимальное совпадение » - это принцип, согласно которому при создании некоторой конструкции необходимо использовать как можно большую часть доступного ввода.
Самое раннее известное использование этого термина принадлежит Р.Г. Кеттеллу в его докторской диссертации по автоматическому созданию генераторов кода для компиляторов.
Например, лексический синтаксис многих языков программирования требует, чтобы токены были построены из максимально возможного количества символов из входного потока. Это сделано для решения проблемы неоднозначности, присущей часто используемым регулярным выражениям, таким как [a-z]+(одна или несколько строчных букв).
Этот термин также используется в компиляторах на этапе выбора инструкций для описания метода «мозаики» - определения того, как структурированное дерево, представляющее программу на промежуточном языке, должно быть преобразовано в линейный машинный код. Целое поддерево может быть преобразовано только в одну машинную команду, и проблема состоит в том, как разбить дерево на неперекрывающиеся «плитки», каждая из которых представляет одну машинную инструкцию. Эффективная стратегия состоит в том, чтобы просто создать плитку из максимально возможного поддерева в любой заданной точке, что называется «максимальным пережевыванием».
В некоторых ситуациях «максимальный перекус» приводит к нежелательным или не интуитивным результатам. Например, в языке программирования C оператор x=y/*z;(без пробелов), вероятно, приведет к синтаксической ошибке, поскольку /*последовательность символов инициирует (непреднамеренный) комментарий, который либо не завершается, либо завершается конечным токеном */некоторого более позднего, не связанного с ним фактического комментарий (комментарии в C не вкладываются). Фактически в заявлении имелось в виду присвоить переменной xрезультат деления значения yна значение, полученное путем разыменования указателя z ; это был бы вполне допустимый (хотя и не очень распространенный) код. Это можно указать, используя пробел или используя x=y/(*z);.
Другой пример, в C ++, использует символы «угловой скобки» lt;и gt;в синтаксисе для специализации шаблона, но два последовательных gt;символа интерпретируются как оператор сдвига вправо gt;gt;. До C ++ 11 следующий код вызывал ошибку синтаксического анализа, потому что вместо двух токенов с правой угловой скобкой встречался токен оператора сдвига вправо:
std::vectorlt;std::vectorlt;intgt;gt; my_mat_11; //Incorrect in C++03, correct in C++11. std::vectorlt;std::vectorlt;intgt; gt; my_mat_03; //Correct in either C++03 or C++11.
Стандарт C ++ 11, принятый в августе 2011 года, внес поправки в грамматику, так что маркер сдвига вправо считается синонимом пары прямых угловых скобок (как в Java ), что усложняет грамматику, но позволяет продолжать использовать максимальное количество еды. принцип.
Исследователи языков программирования также отреагировали, заменив или дополнив принцип максимального пережевывания другими тактиками лексической неоднозначности. Один из подходов заключается в использовании «ограничений следования», которые вместо прямого взятия самого длинного совпадения налагают некоторые ограничения на то, какие символы могут следовать за действительным совпадением. Например, указание, что после сопоставления строк [a-z]+не может следовать алфавитный символ, дает тот же эффект, что и максимальное пережевывание с этим регулярным выражением. (В контексте регулярных выражений принцип максимального пережевывания называется жадностью и противопоставляется лени. ) Другой подход состоит в том, чтобы сохранить принцип максимального пережевывания, но сделать его подчиненным некоторому другому принципу, например контексту ( например, правильному -shift токен в Java не будет соответствовать в контексте выражения обобщения, где он синтаксически недействителен).
