- •Часть 1
- •Лекция №1 Предисловие п.1. Место системного программного обеспечения в компьютерной системе
- •П.2. Структура спо
- •П.3. Хакеры как движущая сила развития спо
- •Лекция №2
- •1. Формальные языки и грамматики в системе программирования
- •1.1. Структура систем программирования
- •1.2. Языки и цепочки символов. Способы задания языков
- •1.2.1. Общие представления о языках
- •1.2.2. Цепочки символов. Операции над цепочками символов
- •1.2.3. Формальное определение языка
- •1.2.4. Способы задания языков
- •Лекция №3
- •1.3. Грамматики и распознаватели
- •1.3.1. Порождающая грамматика
- •1.3.2. Запись правил грамматики с использованием метасимволов
- •Лекция №4
- •1.3.3. Распознаватели
- •1.3.4. Классификация распознавателей
- •1.3.4.1. Классификация распознавателей по компонентам
- •1.3.4.2. Классификация распознавателей по типу языков
- •Лекция №4
- •Лекция №5
- •1.3.5. Примеры классификации языков и грамматик
- •Лекция № 6
- •1.4. Технология формирования предложений языка
- •1.4.1. Выводимость цепочек
- •1.4.2. Сентенциальная форма грамматики
- •1.4.3. Левосторонний и правосторонний выводы
- •1.4.4. Дерево вывода и методы его построения
- •1.4.5. Проблема однозначности грамматик
- •2.1.2. Формальное определение компилятора
- •2.1.3. Интерпретаторы
- •2.2. Общая схема работы компилятора
- •2.3. Варианты построения компиляторов
- •2.3.1. Общие подходы в построении компиляторов
- •2.3.2. Понятие прохода
- •2.3.3. Однопроходные и многопроходные компиляторы
- •2.4. Особенности построения интерпретаторов и их взаимодействие с компиляторами
- •3.1.2. Принципы построения сканеров
- •Лекция 9
- •3.1.3. Сканер как конечный автомат
- •Лекция 10
- •3.2. Взаимодействие сканера с таблицей идентификаторов
- •3.2.1.Назначение и особенности построения таблиц идентификаторов
- •3.2.2. Простейшие методы построения таблиц идентификаторов
- •3.2.3. Построение таблиц идентификаторов по методу бинарного дерева
- •Список литературы
1.3.4. Классификация распознавателей
Классификация распознавателей с одной стороны может быть сделана в зависимости от вида составляющих их компонентов, а с другой стороны по типам распознаваемых языков, которые в свою очередь классифицируются в соответствии с типами грамматик, их порождающих.
1.3.4.1. Классификация распознавателей по компонентам
Основными классификационными компонентами являются: считывающее устройство, устройство управления и внешняя память.
По видам считывающего устройства распознаватели могут быть двусторонние и односторонние.
Односторонние распознаватели допускают перемещение считывающей головки по ленте входных символов только в одном направлении. Это значит, что на каждом шаге работы распознавателя считывающая головка может либо переместиться по ленте на некоторое число позиций в заданном направлении, либо остаться на месте. Поскольку все языки программирования подразумевают нотацию чтения исходной программы «слева направо», то также работают и все распознаватели. Поэтому односторонние распознаватели можно назвать левосторонними, которые читают входную цепочку слева направо и не возвращаются назад к уже прочитанной части цепочки.
Двусторонние распознаватели допускают возможность обращения к уже прочитанной части цепочки, которую они тоже начинают читать слева направо, т. е. считывающая головка может перемещаться относительно ленты в обоих направлениях, но читает слева направо.
По видам УУ распознаватели бывают детерминированные и недетерминированные.
Распознаватель называется детерминированным, если для каждой допустимой конфигурации распознавателя, которая возникла на некотором шаге его работы, существует единственно возможная конфигурация, в которую распознаватель перейдет на следующем шаге работы.
Если имеется в ходе работы распознавателя хотя бы одна такая конфигурация, для которой существует некоторое конечное множество альтернативных конфигураций, возможных на следующем шаге работы, то такой распознаватель называется недетерминированным.
По видам внешней памяти распознаватели бывают следующих типов:
– без внешней памяти;
– с ограниченной внешней памятью;
– с неограниченной внешней памятью.
У распознавателей без внешней памяти в процессе их работы используется только конечная память УУ.
У распознавателей с ограниченной внешней памятью объем внешней памяти зависит от длины входной цепочки символов. Эта зависимость может быть линейной, полиномиальной, экспоненциальной и т. д. Кроме того, для таких распознавателей может быть указан способ организации внешней памяти: стек, очередь, список и т. п.
В распознавателях с неограниченной внешней памятью предполагается, что для их работы может потребоваться внешняя память любого объема вне зависимости от длины входной цепочки. При этом метод доступа к памяти может быть произвольным.
На основании трех рассмотренных составляющих можно организовать общую классификацию распознавателей по компонентам. Например, в этой классификации может оказаться такой тип распознавателя: «двусторонний недетерминированный распознаватель с линейно ограниченной стековой памятью».
Чем выше в классификации стоит распознаватель, тем сложнее создавать алгоритм, обеспечивающий его работу, тем сложнее программное обеспечение компилятора, ибо в отношении исходной программы компилятор выступает как распознаватель, а человек, создавший программу на некотором языке программирования выступает в роли генератора цепочек этого языка.
Разработать двусторонние распознаватели сложнее, чем односторонние. Недетерминированные распознаватели по сложности выше детерминированных. Затраты на создание алгоритма в зависимости от типа внешней памяти также очевидны.