Виды распознавателей

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

По видам считывающего устройства распознаватели могут быть двусторонние и односторонние.

Односторонние распознаватели допускают перемещение считывающей головки по ленте входных символов только в одном направлении. Это значит, что на каж-

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

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

По видам устройства управления распознаватели бывают детерминированные и недетерминированные.

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

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

По видам внешней памяти распознаватели бывают следующих типов:

□ распознаватели без внешней памяти;

□ распознаватели с ограниченной внешней памятью;

□ распознаватели с неограниченной внешней памятью.

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

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

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

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

380 Глава 9. Формальные языки и грамматики

Тип распознавателя в классификации определяет сложность создания такого распознавателя, а следовательно, сложность разработки соответствующего про­граммного обеспечения для компилятора. Чем выше в классификации стоит рас­познаватель, тем сложнее создавать алгоритм, обеспечивающий его работу. Раз­рабатывать двусторонние распознаватели сложнее, чем односторонние. Можно заметить, что недетерминированные распознаватели по сложности выше детер­минированных. Зависимость затрат на создание алгоритма от типа внешней па­мяти также очевидна.

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

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

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

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

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

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

распознаватели, задача разбора

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

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

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

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

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

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

382 Глава 9. Формальные языки и грамматики

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

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

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

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

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

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

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

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

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

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

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

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

Дата добавления: 2015-06-27