Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Принцип наибольшего совпадения при разборе
В компьютерном программировании и информатике принцип "максимального захвата" или "наибольшего совпадения" заключается в том, что при создании какой-либо конструкции следует потреблять как можно большую часть доступного ввода. Первое известное использование этого термина встречается в докторской диссертации Р. Г. Г. Кэттелла, посвященной автоматическому построению генераторов кода для компиляторов.
Longest match principle in parsing
In computer programming and computer science, "maximal munch" or "longest match" is the principle that when creating some construct, as much of the available input as possible should be consumed. The earliest known use of this term is by R. G. G. Cattell in his PhD thesis on automatic derivation of code generators for compilers.
Применение
Например, лексический синтаксис многих языков программирования требует, чтобы токены формировались из максимально возможного числа символов из входного потока. Это делается для разрешения проблемы внутренней неоднозначности в часто используемых регулярных выражениях, таких как [a-z]+ (одна или более строчных букв). Этот термин также используется в компиляторах на этапе выбора инструкций для описания метода "разбиения на блоки" – определения того, как структурированное дерево, представляющее программу на промежуточном языке, должно быть преобразовано в линейный машинный код. Целое поддерево может быть преобразовано всего в одну машинную инструкцию, и задача состоит в том, чтобы разделить дерево на неперекрывающиеся "блоки", каждый из которых представляет одну машинную инструкцию. Эффективная стратегия заключается в создании блока из максимально возможного поддерева в любой данной точке, что называется "жадным разбивлением" (или "максимальным захватом").
For instance, the lexical syntax of many programming languages requires that tokens be built from the maximum possible number of characters from the input stream. This is done to resolve the problem of inherent ambiguity in commonly used regular expressions such as [a z]+ (one or more lower case letters). The term is also used in compilers in the instruction selection stage to describe a method of "tiling" — determining how a structured tree representing a program in an intermediate language should be converted into linear machine code. An entire subtree might be converted into just one machine instruction, and the problem is how to split the tree into non overlapping "tiles", each representing one machine instruction. An effective strategy is simply to make a tile of the largest subtree possible at any given point, which is called "maximal munch".
Недостатки
В некоторых ситуациях принцип "максимального захвата" приводит к нежелательным или неинтуитивным результатам. Например, в языке программирования C, выражение x=y/*z; (без пробелов) скорее всего вызовет синтаксическую ошибку, поскольку последовательность /* (непреднамеренно) инициирует комментарий, который либо не завершается, либо завершается конечным токеном */ некоторого последующего, не связанного комментария (комментарии в C не могут быть вложенными). Фактически, в этом выражении предполагалось присвоить переменной x результат деления значения y на значение, полученное при разыменовании указателя z; это был бы допустимый код. Это можно выразить, используя пробелы или x=y/(*z);. Другой пример, в C++, использует символы угловых скобок < и > в синтаксисе специализации шаблонов, но два последовательных символа > интерпретируются как оператор побитового сдвига вправо >>. До C++11 следующий код приводил бы к ошибке разбора, поскольку вместо двух токенов угловых скобок обнаруживался бы токен оператора сдвига вправо:
In some situations, "maximal munch" leads to undesirable or unintuitive outcomes. For instance, in the C programming language, the statement x=y/*z; (without any whitespace) will probably lead to a syntax error since the /* character sequence (unintentionally) initiates a comment that is either unterminated or terminated by the end token */ of some later, unrelated actual comment (comments in C do not nest). What was actually meant in the statement was to assign to the variable x the result of dividing the value in y by the value obtained by dereferencing pointer z; this would be valid code. It can be stated by making use of whitespace or using x=y/(*z);. Another example, in C++, uses the "angle bracket" characters < and > in the syntax for template specialization, but two consecutive > characters are interpreted as the right shift operator >>. Prior to C++11, the following code would produce a parse error, because the right shift operator token is encountered instead of two right angle bracket tokens:
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), что усложняет грамматику, но позволяет продолжать использовать принцип максимального захвата. Исключение из правила максимального захвата в любом случае пришлось добавить для обработки последовательности <::, которая может встречаться в шаблонах. В этом случае, если за последовательностью не следует : или >, символ < интерпретируется как отдельный токен, а не как часть токена <:.
std::vector<std::vector<int>> my mat 11; //Incorrect in C++03, correct in C++11. std::vector<std::vector<int> > my mat 03; //Correct in either C++03 or C++11. The C++11 standard adopted in August 2011 amended the grammar so that a right shift token is accepted as synonymous with a pair of right angle brackets (as in Java), which complicates the grammar but allows the continued use of the maximal munch principle. An exception to the maximal munch rule had to be added anyway to deal with the sequence <:: which can appear in templates. In that case, unless the sequence is followed by : or > the character < is interpreted as its own token instead of part of the token <:.
Альтернативы
Исследователи языков программирования также отреагировали, заменив или дополнив принцип максимального захвата другими тактиками лексической дезагигиации. Один из подходов — использовать "ограничения следования", которые вместо прямого выбора самого длинного соответствия накладывают ограничения на то, какие символы могут следовать за допустимым соответствием. Например, требование, чтобы строки, соответствующие [a-z]+, не могли быть за которыми следуют алфавитные символы, достигает того же эффекта, что и принцип максимального захвата с этим регулярным выражением. (В контексте регулярных выражений принцип максимального захвата называют жадностью и противопоставляют ему нежадность.) Другой подход заключается в сохранении принципа максимального захвата, но подчинении его другому принципу, например, контексту (например, токен сдвига вправо в Java не будет распознан в контексте обобщенного выражения, где он синтаксически недопустим).
Programming languages researchers have also responded by replacing or supplementing the principle of maximal munch with other lexical disambiguation tactics. One approach is to utilize "follow restrictions", which instead of directly taking the longest match will put some restrictions on what characters can follow a valid match. For example, stipulating that strings matching [a z]+ cannot be followed by an alphabetic character achieves the same effect as maximal munch with that regular expression. (In the context of regular expressions, the maximal munch principle is referred to as greediness and contrasted with laziness.) Another approach is to keep the principle of maximal munch but make it subordinate to some other principle, such as context (e. g., the right shift token in Java would not be matched in the context of a generics expression, where it is syntactically invalid).