Системное программное обеспечение: Основы трансляции. Карпушин А.Н - 17 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

19
Однако можно указать некоторые виды правил вывода, которые приводят
к неоднозначности:
1. A → AA | α;
2. A → AαA | β;
3. A → αA | Aβ | γ;
4. A → αA | αAβA | γ.
Общая схема распознавателя
Важнейшей задачей любого транслятора является определение принад-
лежности имеющегося текста программы к данному языку (т.е. не содержит ли
текст ошибок). В отношении исходной программы транслятор выступает как
распознаватель, а человек, создавший программу на некотором языке, высту-
пает в роли генератора цепочек этого языка.
Распознаватель – это специальный алгоритм, который позволяет опреде-
лить принадлежность цепочки символов некоторому языку. Распознаватели
представляют собой один из способов определения языка.
В общем виде распознаватель можно отобразить в виде условной схемы,
состоящей из следующих основных компонентов:
1. Элемента, содержащего исходную цепочку входных символов, и считы-
вающего устройства, обозревающего очередной символ в этой цепочке;
2. Устройства управления, которое координирует работу распознавателя,
имеет некоторый набор состояний и конечную память (для хранения сво-
его состояния и некоторой промежуточной информации);
3. Внешней (рабочей) памяти, которая может хранить некоторую информа-
цию в процессе работы распознавателя и в отличие от памяти устройства
управления может иметь неограниченный объем.
Распознаватель работает с символами своего алфавита – алфавита распо-
знавателя. Алфавит распознавателя конечен и включает в себя все допустимые
символы входных цепочек, а также некоторый дополнительный алфавит сим-
волов, которые могут обрабатываться устройством управления и храниться в
рабочей памяти распознавателя.
Виды распознавателей
Распознаватели можно классифицировать в зависимости от вида состав-
ляющих их компонентов: считывающего устройства, устройства управления и
внешней памяти.
По видам считывающего устройства распознаватели могут быть
двусторонние и односторонние.
Односторонние распознаватели допускают чтение входных символов
только в одном направлении. Поскольку все языки программирования подразу-
мевают нотацию чтения исходной программы «слева направо», то так же рабо-
тают и все распознаватели. Поэтому, когда говорят об односторонних распо-
знавателях, то прежде всего имеют в виду левосторонние, которые читают ис-
ходную цепочку слева направо и не возвращаются назад к уже прочитанной
части цепочки.

Страницы