Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Сравнение лексического распознавателя с каноническим конечным автоматом






Итак, основная идея лексического анализа состоит в том, что распознать последовательность символов (литер), не имеющих произвольной вложенности, можно при помощи устройства, обладающего только памятью текущего состояния. Единственное средство запомнить какое-либо факт или событие во входной последовательности – ввести соответствующее состояние в диаграмму автомата. Тогда каждое состояние автомата несет в себе смысловую нагрузку, связанную с запоминанием – «находимся внутри идентификатора», «обнаружили символ s внутри идентификатора» и т.п.. Проектирование автоматного распознавателя на уровне диаграммы состояний/переходов на самом деле представляет собой одну из вариаций доисторической технологии «исторического программирования» с использованием блок-схем. Далее мы увидим, что есть средства описания лексики более высокого уровня, базирующиеся на формальных грамматиках.

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

· завершение распознавания предыдущей лексемы;

· возврат символов, соответствующих началу текущей лексемы;

· сброс автомата в исходное состояние;

· повторное распознавание начала текущей лексемы.

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






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.