Распознаватели. Общая схема распознавателя
Распознаватель (или разборщик) — это специальный автомат, который позволяет определить принадлежность цепочки символов некоторому языку. Задача распознавателя заключается в том, чтобы на основании исходной цепочки дать ответ на вопрос, принадлежит ли она заданному языку или нет. Распознаватели, как было сказано выше, представляют собой один из способов определения языка.
В общем виде распознаватель можно отобразить в виде условной схемы, представленной на рис. 1.2.
Рис. 1.1. Графическое представление грамматики целых десятичных чисел со знаком
Рис. 1.2. Условная схема распознавателя
Как видно из рисунка, распознаватель состоит из следующих основных компонентов:
· ленты, содержащей входную цепочку символов, и считывающей головки, обозревающей очередной символ в этой цепочке;
· устройства управления (УУ), которое координирует работу распознавателя, имеет некоторый набор состояний и конечную память (для хранения своего состояния и некоторой промежуточной информации);
· внешней (рабочей) памяти, которая может хранить некоторую информацию в процессе работы распознавателя и, в отличие от памяти УУ, имеет неограниченный объем.
Распознаватель работает с символами своего алфавита — алфавита распознавателя. Алфавит распознавателя конечен. Он включает в себя все допустимые символы входных цепочек, а также некоторый дополнительный алфавит символов, которые могут обрабатываться УУ и храниться в рабочей памяти распознавателя.
В процессе своей работы распознаватель может выполнять некоторые элементарные операции:
· чтение очередного символа из входной цепочки;
· сдвиг входной цепочки на заданное количество символов (вправо или влево);
· доступ к рабочей памяти для чтения или записи информации;
· преобразование информации в памяти УУ, изменение состояния УУ. То, какие конкретно операции должны выполняться в процессе работы распознавателя, определяется в УУ.
Распознаватель работает по шагам, или тактам. В начале такта, как правило, считывается очередной символ из входной цепочки, и в зависимости от этого символа УУ определяет, какие действия необходимо выполнить. Вся работа распознавателя состоит из последовательности тактов. В начале каждого такта состояние распознавателя определяется его конфигурацией. В процессе работы конфигурация распознавателя меняется.
Конфигурация распознавателя определяется следующими параметрами:
· содержимым входной цепочки символов и положением считывающей головки в ней;
· состоянием УУ;
· содержимым внешней памяти. Для распознавателя всегда задается определенная конфигурация, которая считается начальной конфигурацией. В начальной конфигурации считывающая головка обозревает первый символ входной цепочки, УУ находится в заданном начальном состоянии, а внешняя память либо пуста, либо содержит строго определенную информацию.
Кроме начального состояния для распознавателя задается одна или несколько конечных конфигураций. В конечной конфигурации считывающая головка, как правило, находится за концом исходной цепочки (часто для распознавателей вводят специальный символ, обозначающий конец входной цепочки). Распознаватель допускает входную цепочку символов a, если, находясь в начальной конфигурации и получив на вход эту цепочку, он может проделать последовательность шагов, заканчивающуюся одной из его конечных конфигураций.
Язык, определяемый распознавателем, — это множество всех цепочек, которые допускает распознаватель.