Максимальный жевать

В компьютерном программировании и информатике « максимальный прием » или « самое длинное совпадение » — это принцип, согласно которому при создании некоторой конструкции должно быть использовано как можно больше доступных входных данных.

Самое раннее известное использование этого термина принадлежит Р.Г. Кеттеллу в его докторской диссертации. ^[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; //Incorrect in C++03, correct in C++11.
    std::vector<std::vector<int> > my_mat_03; //Correct in either C++03 or C++11.

Стандарт C++11 , принятый в августе 2011 года, внес поправки в грамматику , так что токен сдвига вправо принимается как синоним пары прямых угловых скобок (как в Java ), что усложняет грамматику, но позволяет продолжать использовать максимальную функцию Munch. принцип. В любом случае пришлось добавить исключение из правила максимального жевания, чтобы справиться с последовательностью <:: которые могут появляться в шаблонах. В этом случае, если последовательность не соблюдается : или > персонаж < интерпретируется как собственный токен, а не как часть токена <:.

Альтернативы

Исследователи языков программирования также отреагировали на это, заменив или дополнив принцип максимального пережевывания другими тактиками устранения лексической неоднозначности. Один из подходов заключается в использовании «ограничений на отслеживание», которые вместо прямого выбора самого длинного совпадения налагают некоторые ограничения на то, какие символы могут следовать за действительным совпадением. Например, оговорив, что строки, соответствующие [a-z]+ за которым не может следовать буквенный символ, достигается тот же эффект, что и при максимальном куске с этим регулярным выражением. ^[5] (В контексте регулярных выражений принцип максимального жевания называется жадностью и противопоставляется лени .) Другой подход состоит в том, чтобы сохранить принцип максимального жевания, но сделать его подчиненным какому-либо другому принципу, например контексту ( например , правильному Токен -shift в Java не будет сопоставляться в контексте обобщенного выражения, где он синтаксически недействителен). ^[6]

Ссылки

^ Кеттелл, RGG «Формализация и автоматический вывод генераторов кода». Докторская диссертация, 1978. Университет Карнеги-Меллона, Питтсбург, Пенсильвания, США.
^ Ахо и др. , 168.
^ Страница, 470.
^ Вандеворде.
^ Ван ден Бранд и др. , 26.
^ Ван Вик и др. , 63.

Библиография

Ахо, Альфред В.; Лам, Моника С.; Сетхи, Рави; Уллман, Джеффри Д. (2007). Составители: принципы, методы и инструменты (2-е изд.). Бостон: Аддисон-Уэсли. ISBN 978-0-321-48681-3 .
Пейдж, Дэниел (2009). «Компиляторы». Практическое введение в архитектуру компьютера . Тексты по информатике. Лондон: Спрингер. стр. 451–493. дои : 10.1007/978-1-84882-256-6_11 . ISBN 978-1-84882-255-9 .
Ван ден Бранд, Марк Дж.Дж.; Ширдер, Йерун; Винью, Юрген Дж.; Виссер, Eelco (2002). «Фильтры устранения неоднозначности для обобщенных анализаторов LR без сканирования». Конструкция компилятора . Конспекты лекций по информатике. Полный. 2304/2002. Берлин/Гейдельберг: Springer. стр. 21–44. дои : 10.1007/3-540-45937-5_12 . ISBN 978-3-540-43369-9 . ISSN 0302-9743 .
Вандевурде, Давид (14 января 2005 г.). «Прямоугольные скобки» . Проверено 31 марта 2010 г.
Ван Вик, Эрик; Швердфегер, август (2007 г.). «Контекстно-зависимое сканирование для анализа расширяемых языков». Материалы 6-й международной конференции по генеративному программированию и компонентной инженерии . Нью-Йорк: ACM. стр. 63–72. дои : 10.1145/1289971.1289983 . ISBN 9781595938558 . S2CID 9145863 .

[1] Кеттелл, RGG «Формализация и автоматический вывод генераторов кода». Докторская диссертация, 1978. Университет Карнеги-Меллона, Питтсбург, Пенсильвания, США.

[2] Ахо и др. , 168.

[3] Страница, 470.

[4] Вандеворде.

[5] Ван ден Бранд и др. , 26.

[6] Ван Вик и др. , 63.

[1]

[2]

[3]

[4]

[5]

[6]