Общая схема распознавателя

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

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

В общем виде распознаватель можно отобразить в виде условной схемы, пред­ставленной на рис. 1.5.

Рис. 1.5. Условная схема распознавателя

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

Как видно из рисунка, распознаватель состоит из следующих основных компо­нентов:

 ленты, содержащей исходную цепочку входных символов, и считывающей го­ловки, обозревающей очередной символ в этой цепочке;

 устройства управления (УУ), которое координирует работу распознавателя, имеет некоторый набор состояний и конечную память (для хранения своего состояния и некоторой промежуточной информации);

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

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

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

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

Конфигурация распознавателя определяется следующими параметрами:

 содержимое входной цепочки символов и положение считывающей головки в ней;

 состояние УУ;

 содержимое внешней памяти.

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

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

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

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

Язык, определяемый распознавателем, – это множество всех цепочек, которые допускает распознаватель.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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