Максимальный перекус - Maximal munch

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

Самое раннее известное использование этого термина было сделано R.G.G. Кеттелл в своей докторской диссертации[1] об автоматическом выводе генераторы кода за компиляторы.

Заявление

Например, лексический синтаксис из многих языки программирования требует, чтобы жетоны быть построенным из максимально возможного количества символов из входного потока. Это сделано для решения проблемы неоднозначности обычно используемых обычные выражения Такие как [а-я] + (одна или несколько строчных букв).[2]

Этот термин также используется в компиляторы в выбор инструкции этап для описания метода "мозаики" - определения того, как структурированное дерево представляет программу в промежуточный язык следует преобразовать в линейный Машинный код. Целое поддерево может быть преобразовано только в одну машинную инструкцию, и проблема состоит в том, как разбить дерево на неперекрывающиеся «плитки», каждая из которых представляет одну машинную инструкцию. Эффективная стратегия - просто создать плитку из максимально возможного поддерева в любой заданной точке, что называется «максимальным пережевыванием».[3]

Недостатки

В некоторых ситуациях «максимальный перекус» приводит к нежелательным или не интуитивным результатам. Например, в C язык программирования, инструкция х = у / * г; (без пробелов), вероятно, приведет к синтаксической ошибке, поскольку /* последовательность символов инициирует (непреднамеренный) комментарий, который либо не завершается, либо завершается конечным токеном */ некоторых более поздних, не связанных действительный комментарий (комментарии в C не вкладываются). Фактически в заявлении имелось в виду присвоение переменной Икс результат деления значения на у по значению, полученному при разыменовании указатель z; это был бы вполне допустимый (хотя и не очень распространенный) код. Это можно указать, используя пробел или используя х = у / (* г);.

Другой пример, в C ++, использует символы "угловой скобки" < и > в синтаксисе для специализация шаблона, но два подряд > символы интерпретируются как сдвиг вправо оператор >>.[4] До C ++ 11 следующий код вызывал ошибку синтаксического анализа, потому что вместо двух токенов с правой угловой скобкой встречался токен оператора сдвига вправо:

    стандартное::вектор<стандартное::вектор<int>> my_mat_11; // Неправильно в C ++ 03, правильно в C ++ 11.    стандартное::вектор<стандартное::вектор<int> > my_mat_03; // Правильно в C ++ 03 или C ++ 11.

В C ++ 11 стандарт принят в августе 2011 г. внес поправки в грамматику так что лексема сдвига вправо считается синонимом пары прямоугольных скобок (как в Ява ), что усложняет грамматику, но позволяет продолжать использовать принцип максимального жевания.

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

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

Рекомендации

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

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

  • Ахо, Альфред V .; Lam, Monica S .; Сетхи, Рави; Ульман, Джеффри Д. (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.
  • Ван ден Бранд, Марк Дж. Дж .; Шердер, Йерун; Винью, Юрген Дж .; Виссер, Элко (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). Контекстно-зависимое сканирование для анализа расширяемых языков. GPCE '07: Труды 6-й Международной конференции по генеративному программированию и разработке компонентов. Нью-Йорк: ACM. С. 63–72. Дои:10.1145/1289971.1289983. ISBN  9781595938558.