- •Часть 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.2.3. Формальное определение языка
Алфавит – это счетное множество допустимых символов языка. Алфавит не обязательно должен быть конечным множеством, но реально все существующие языки строятся на основе конечных алфавитов.
Для обозначения алфавита воспользуемся прописными буквами. Обозначим некоторый алфавит А.
Цепочка символов (А) является цепочкой над алфавитом А, если в нее входят только символы из алфавита А. Для любого алфавита А пустая цепочка может как являться, так и не являться цепочкой над алфавитом А, т. е. (А) может учитываться или не учитываться. Это условие оговаривается дополнительно.
Если А – некоторый алфавит, то:
А+ – множество всех цепочек над алфавитом А без ;
А* – множество всех цепочек над алфавитом А, включая ;
т. е. А* = А+
Языком L над алфавитом А: L(A) называется некоторое счетное подмножество цепочек конечной длины из множества всех цепочек над алфавитом А. Из этого определения следует три вывода: во-первых множество цепочек языка не обязательно должно быть конечным; во-вторых хотя каждая цепочка, входящая в язык, обязана иметь конечную длину, эта длина может быть сколь угодно большой и формально ничем не ограничена; в-третьих на основе одного алфавита может быть реализовано множество языков.
Все существующие языки естественные и искусственные подпадают под это определение.
Цепочку символов, принадлежащую языку, часто называют предложением.
Для любого языка L(A) справедливо: L(A) А*.
Язык L(A) включает в себя L(A), т. е. L(A) L(A), если
L(A)[ L(A)].
Множество цепочек языка L(A) является подмножеством множества цепочек языка L(A).
Два языка L(A) и L(A) совпадают (эквивалентны), т. е. L(A) = L(A),если L(A) L(A) и L(A) L(A) или иначе:
L(A)[ L(A)] и L(A)[ L(A)].
Два языка L(A) и L(A) почти эквивалентны
L(A) L(A),
если они различаются только на , т. е.
L(A) = L(A) или L(A) = L(A) .
1.2.4. Способы задания языков
Формально каждый язык – это множество цепочек символов над некоторым алфавитом. Кроме алфавита язык предусматривает также правила построения допустимых цепочек, поскольку обычно далеко не все цепочки над заданным алфавитом принадлежат языку. Символы могут объединяться в элементарные конструкции языка – лексемы, а на их основе строятся более сложные конструкции – предложения. И те и другие в общем виде являются цепочками символов, но предусматривают некоторые правила построения. Необходимо указать эти правила, или, строго говоря, задать язык.
В общем случае язык можно определить тремя способами.
1. Перечислением всех допустимых цепочек языка;
2. Указанием способа порождения цепочек языка, т. е. заданием грамматики языка.
3. Определением метода распознавания цепочек языка.
Первый способ – это формальный способ прямого действия, который на практике не применяется из-за бесконечного числа допустимых цепочек. Иногда для чисто формальных языков можно перечислить множество входящих в них цепочек, используя математическое описание множеств.
Например, запись L(0, 1) = {0n 1n, n > 0} задает язык над алфавитом, A = {0, 1},содержащий все цепочки с чередующими символами 0 и 1, начинающиеся с 0 и заканчивающиеся 1. Например, при n = 1 цепочка = 01, при n = 2 = 0011 и т. д. Пустая цепочка в этот язык не входит. Если изменить условия в определении со строгого неравенства n 0 на n 0, то получится почти эквивалентный язык L(0, 1), содержащий пустую цепочку.
Но в таком варианте происходит сдвиг первого способа ко второму.
Второй способ – это способ, использующий порождающую процедуру, которая задается с помощью конечного множества правил, называемых грамматикой и порождающих в точности те цепочки, которые принадлежат языку L.
Третий способ предусматривает построение некоторого логического устройства (распознавателя) – автомата соответствующего языку, который получает на входе цепочку символов, а на выходе выдает ответ: принадлежит или нет эта цепочка заданному языку.
При построении трансляторов используются второй и третий способы: грамматика как средство описания синтаксиса языка программирования, а автомат как модель алгоритма распознавания предложений языка. При этом методически (и технологически) сначала конструируется грамматика, причем такая, по которой, как по источнику, строится алгоритм распознавания.