Конечные автоматы

Задача разбора (постановка задачи)

Классификация распознавателей по типам языков

Как было показано в предыдущей главе, классификация распознавателей (вид входящих в состав распознавателя компонентов) определяет сложность алгорит­ма работы распознавателя. Но сложность распознавателя также напрямую связа­на с типом языка, входные цепочки которого может принимать (допускать) рас­познаватель.

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

Для языков с фразовой структурой (тип 0) необходим распознаватель, равномощный машине Тьюринга — недетерминированный двусторонний автомат, имею­щий неограниченную внешнюю память. Поэтому для языков данного типа нель­зя гарантировать, что за ограниченное время на ограниченных вычислительных ресурсах распознаватель завершит работу и примет решение о том, принадлежит или не принадлежит входная цепочка заданному языку. Отсюда можно заклю­чить, что практического применения языки с фразовой структурой не имеют (и не будут иметь), а потому далее они не рассматриваются.

Для контекстно-зависимых языков (тип 1) распознавателями являются двусто­ронние недетерминированные автоматы с линейно ограниченной внешней памя­тью. Алгоритм работы такого автомата в общем случае имеет экспоненциальную сложность — количество шагов (тактов), необходимых автомату для распознава­ния входной цепочки, экспоненциально зависит от длины этой цепочки. Следо­вательно, и время, необходимое на разбор входной цепочки по заданному алго­ритму, экспоненциально зависит от длины входной цепочки символов.

Такой алгоритм распознавателя уже может быть реализован в программном обес­печении компьютера — зная длину входной цепочки, всегда можно сказать, за какое максимально возможное время будет принято решение о принадлежности цепочки данному языку и какие вычислительные ресурсы для этого потребуют­ся. Однако экспоненциальная зависимость времени разбора от длины цепочки существенно ограничивает применение распознавателей для контекстно-зависи­мых языков. Как правило, такие распознаватели применяются для автоматизи­рованного перевода и анализа текстов на естественных языках, когда временные ограничения на разбор текста несущественны (следует также напомнить, что, по­скольку естественные языки более сложны, чем контекстно-зависимый тип, то после такой обработки часто требуется вмешательство человека). В компилято­рах для анализа текстов на различных языках программирования контекстно-за­висимые распознаватели не применяются, поскольку скорость работы компиля­тора имеет существенное значение, а синтаксический разбор текста программы можно выполнять в рамках более простого, контекстно-свободного типа языков.

Поэтому в рамках этого учебного пособия контекстно-зависимые языки также не рассматриваются.

Для контекстно-свободных языков (тип 2) распознавателями являются односто­ронние недетерминированные автоматы с магазинной (стековой) внешней па­мятью — МП-автоматы. При простейшей реализации алгоритма работы такого автомата он имеет экспоненциальную сложность, однако путем некоторых усо­вершенствований алгоритма можно добиться полиномиальной (кубической) за­висимости времени, необходимого па разбор входной цепочки, от длины этой цепочки. Следовательно, можно говорить о полиномиальной сложности распо­знавателя для КС-языков.

Среди всех КС-языков можно выделить класс детерминированных КС-языков, распознавателями для которых являются детерминированные автоматы с магазинной (стековой) внешней памятью — ДМП-автоматы. Эти языки обладают свойством однозначности — доказано, что для любого детерминированного КС-языка всегда можно построить однозначную грамматику. Кроме того, для таких языков существует алгоритм работы распознавателя с квадратичной сложно­стью. Поскольку эти языки являются однозначными, именно они представляют наибольший интерес для построения компиляторов.

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

Тем не менее, следует помнить, что только синтаксические конструкции языков программирования допускают разбор с помощью распознавателей КС-языков. Сами языки программирования, как уже было сказано, не могут быть полностью отнесены к типу КС-языков, поскольку предполагают некоторую контекстную зависимость в тексте исходной программы (например, такую, как необходимость предварительного описания переменных). Поэтому кроме синтаксического раз­бора практически все компиляторы предполагают дополнительный семантиче­ский анализ текста исходной программы. Этого можно было бы избежать, если построить компилятор на основе контекстно-зависимого распознавателя, но ско­рость работы такого компилятора была бы недопустима низка, поскольку время разбора в таком варианте будет экспоненциально зависеть от длины исходной программы. Комбинация из распознавателя КС-языка и дополнительного семан­тического анализатора является более эффективной с точки зрения скорости разбора исходной программы.

Для регулярных языков (тип 3) распознавателями являются односторонние неде­терминированные автоматы без внешней памяти — конечные автоматы (КА). Это очень простой тип распознавателя, который всегда предполагает линейную зависимость времени на разбор входной цепочки от ее длины. Кроме того, конеч­ные автоматы имеют важную особенность: любой недетерминированный КА всегда может быть преобразован в детерминированный. Это обстоятельство су­щественно упрощает разработку программного обеспечения, обеспечивающего функционирование распознавателя.

Простота и высокая скорость работы распознавателей определяют широкую об­ласть применения регулярных языков.

В компиляторах распознаватели на основе регулярных языков используются для лексического анализа текста исходной программы — выделения в нем про­стейших конструкций языка, таких как идентификаторы, строки, константы и т. п. Это позволяет существенно сократить объем исходной информации и упрощает синтаксический разбор программы. Более подробно взаимодействие лексическо­го и синтаксического анализаторов текста программы рассмотрено дальше, в гла­ве, посвященной структуре компилятора. На основе распознавателей регулярных языков функционируют ассемблеры — компиляторы с языков ассемблера (мне­мокода) в язык машинных команд.

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

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

Разработчики компилятора всегда имеют дело с уже определенным языком программирования. Грамматика для синтаксических конструкций этого языка из­вестна. Она, как правило, четко описана в стандарте языка, и хотя форма опи­сания может быть произвольной, ее всегда можно преобразовать к требуемому виду (например, к форме Бэкуса—Наура или к форме описания с использованием метасимволов). Задача разработчиков заключается в том, чтобы построить рас­познаватель для заданного языка, который затем будет основой синтаксического анализатора в компиляторе.

Таким образом, задача разбора в общем виде заключается в следующем: на осно­ве имеющейся грамматики некоторого языка построить распознаватель для это­го языка. Заданная грамматика и распознаватель должны быть эквивалентны, то есть определять один и тот же язык (часто допускается, чтобы они были почти эквивалентны, поскольку пустая цепочка во внимание обычно не принимается).

Задача разбора в общем виде может быть решена не для всех типов языков. Но как было сказано выше, разработчиков компиляторов интересуют, прежде всего, контекстно-свободные и регулярные языки. Для данных типов языков доказано, что задача разбора для них разрешима. Более того, для них найдены формальные методы ее решения. Описанию и обоснованию именно методов решения задачи разбора и будет посвящена большая часть материала последующих глав.

Поскольку языки программирования не являются чисто формальными языками и несут в себе некоторый смысл (семантику), то задача разбора для создания ре­альных компиляторов понимается несколько шире, чем она формулируется для чисто формальных языков. Компилятор должен не просто дать ответ, принадле­жит или нет входная цепочка символов заданному языку, но и определить ее смысловую нагрузку. Для этого необходимо выявить те правила грамматики, на основании которых цепочка была построена. Фактически работа распознавате­лей в составе компиляторов сводится к построению в том или ином виде дерева разбора входной цепочки. Затем уже это дерево разбора используется компиля­тором для синтеза результирующего кода.

Кроме того, если входная цепочка символов не принадлежит заданному языку — исходная программа содержит ошибку, — разработчику программы не интересно просто узнать сам факт наличия ошибки. В данном случае задача разбора также расширяется: распознаватель в составе компилятора должен не только устано­вить факт присутствия ошибки во входной программе, но и по возможности оп­ределить тип ошибки и то место в цепочке символов, где она встречается.

Дата добавления: 2014-01-20