Условная схема распознавателя
Основные компоненты:
лента, содержащая исходную цепочку входных символов, и считывающая головка, обозревающая очередной символ в этой цепочке;
устройство управления (УУ), координирующее работу распознавателя (имеет некоторый набор состояний и конечную память (ограниченного объема – для хранения своего состояния и некоторой промежуточной информации));
внешняя (рабочая) память, которая может хранить некоторую информацию в процессе работы распознавателя (неограниченного объема).
доступ к рабочей памяти для чтения или записи информации;
преобразование информации в памяти;
изменение состояния УУ.
Распознаватель работает по шагам (тактам).
В начале такта, как правило, считывается очередной символ из входной цепочки, и в зависимости от этого символа УУ определяет, какие действия необходимо выполнить.
Вся работа распознавателя состоит из последовательности тактов.
В начале каждого такта состояние распознавателя определяется его конфигурацией.
В процессе работы конфигурация распознавателя меняется.
одна начальная конфигурация:
- считывающая головка обозревает первый символ входной цепочки,
- УУ находится в заданном начальном состоянии,
- внешняя память либо пуста, либо содержит строго определенную информацию;
одна или несколько конечных конфигураций:
- считывающая головка, как правило, находится за концом исходной цепочки (часто для распознавателей вводят специальный символ, обозначающий конец входной цепочки).
Распознаватель допускает входную цепочку символов α, если, находясь в начальной конфигурации и получив на вход эту цепочку, он может проделать последовательность шагов, заканчивающуюся одной из его конечных конфигураций.
Задача разбора в общем виде может быть
решена не для всех типов языков.
Разработчиков компиляторов интересуют
прежде всего контекстно-свободные и регулярные языки.
Для данных типов языков доказано, что задача разбора
для них разрешима и для них найдены
формальные методы ее решения.
При разработке компилятора для некоторого языка программирования возникает задача, которая требует связать между собой два независимых метода задания языков – грамматику и распознаватель языка.
Так как языки программирования не являются чисто формальными, то для них задача разбора включает также:
определение смысловой нагрузки входной цепочки символов (необходимо выявить те правила грамматики, на основании которых цепочка была построена);
не только установление факта присутствия ошибки во входной программе, но и по возможности определение типа ошибки и того места в цепочке символов, где она встречается.
Если не удалось найти и скачать доклад-презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:
Email: Нажмите что бы посмотреть