Контекстно-свободные языки и магазинные автоматы

Контекстно-свободные грамматики порождают языки с вложенной, рекурсивной структурой, а магазинные автоматы распознают именно эти языки, дополняя конечное управление неограниченным стеком.

Definition

Контекстно-свободный язык порождается грамматикой, правила которой переписывают один нетерминальный символ независимо от контекста, и распознается магазинным автоматом — конечным автоматом, оснащенным стеком, который обеспечивает память типа «последний пришел — первый ушел» неограниченной глубины.

Scope

Эта тема охватывает контекстно-свободные грамматики и выводы, деревья разбора и неоднозначность, эквивалентность контекстно-свободных грамматик с магазинными автоматами, нормальные формы, такие как нормальная форма Хомского, лемму о накачке для контекстно-свободных языков, а также свойства замыкания и разрешимости, которые отличают этот класс от регулярных языков.

Core questions

• Какие виды вложенных или рекурсивных шаблонов требуют стека, а не конечной памяти?
• Почему контекстно-свободные грамматики и магазинные автоматы эквивалентны по мощности?
• Когда грамматика является неоднозначной и почему неоднозначность важна для синтаксического анализа?
• Какие проблемы разрешимости для контекстно-свободных языков разрешимы, а какие нет?

Key theories

Эквивалентность грамматики и автомата

Язык является контекстно-свободным тогда и только тогда, когда он принимается некоторым магазинным автоматом, поэтому представление порождающей грамматики и представление стековой машины описывают один и тот же класс языков.

Нормальная форма Хомского

Каждая контекстно-свободная грамматика может быть переписана так, чтобы каждое правило порождало либо два нетерминала, либо один терминал — нормальная форма, лежащая в основе алгоритмов синтаксического анализа и индуктивных доказательств для этого класса.

Лемма о накачке для контекстно-свободных языков

Каждая достаточно длинная строка в контекстно-свободном языке может быть разделена так, что две ее части накачиваются вместе — свойство, которое не выполняется для языков, требующих больше, чем стековая память, и, таким образом, доказывает их неконтекстно-свободность.

Clinical relevance

Контекстно-свободные грамматики определяют синтаксис почти каждого языка программирования и многих форматов данных, а алгоритмы синтаксического анализа магазинного типа превращают эти грамматики в синтаксические анализаторы, лежащие в основе компиляторов и интерпретаторов, что делает эту тему теоретической основой обработки языков программирования.

History

Хомский ввел контекстно-свободные грамматики в конце 1950-х годов как часть своей иерархии, и они независимо использовались Бэкусом и Науром для определения синтаксиса языка программирования ALGOL. Эквивалентность с магазинными автоматами и структурная теория этого класса были разработаны в течение 1960-х годов.

Key figures

• Noam Chomsky
• John Backus
• Seymour Ginsburg
• Sheila Greibach

Seminal works

• sipser2013
• hopcroft2006

Frequently asked questions

Почему для синтаксического анализа языка программирования нужен стек?

Программы содержат вложенные конструкции, такие как скобки, блоки и вызовы функций, глубина соответствия которых неограничена. Стек записывает каждую незавершенную конструкцию и извлекает ее при закрытии, что является именно той дисциплиной памяти, которую предоставляет магазинный автомат и которой не хватает конечному автомату.

Что означает неоднозначность грамматики?

Грамматика является неоднозначной, когда некоторая строка имеет более одного дерева разбора, что означает, что она может быть выведена с действительно разными структурами. Неоднозначность нежелательна для языков программирования, потому что она делает смысл кода неясным, поэтому разработчики языков ищут однозначные грамматики или добавляют правила разрешения неоднозначности.