Этапы жизненного цикла программного продукта
· Анализ: цель – определение требований к будущему программному продукту
· Проектирование: результат – архитектура системного программного продукта (алгоритмы + декомпозиция, функции + интерфейс)
· Реализация: кодирование + тестирование + отладка
· Сопровождение: эволюция программного продукта при его эксплуатации
Состав и схема функционирования классической системы программирования
Транслятор – программа, кот позволяет писать программу на языке высокого уровня и обеспечивает ее выполнение (позволяет писать не в машинных кодах)
Компилятор - программа, которая осуществляет перевод исходной программы на ЯП в объектную программу (одна из разновидностей транслятора)
Интерпретатор – так же 1 из разновидностей трансляторов, выход – результат обработки исходных данных
Схема:
Редактор текстов -> (исходная программа на некотором языке программирования) -> компилятор (+макрогенератор) -> (объектная программа – машинно-ориентированное представление программы, где есть информация в машинном коде + инф о внешних связях + таблицы констант…) -> редактор связей –> (исполняемый модуль – программа в машинных кодах как единое целое, относительно некоторого условного начального адреса)
Типы трансляторов, особенности интерпретаторов и компиляторов
Схема работы «чистого» компилятора: (исходная программа на ЯП) -> ЛА + СА + КУ + генерация кода -> (объектный модуль)
Схема работы чистого интерпретатора: (исх. программа на ЯП + входные данные) -> интерпретатор -> (результат работы исх. программы на водных данных)
Смешанная стратегия: (исх. программа на ЯП) -> ЛА + СА + КУ -> (промежуточное представление программы + вх. данные) -> интерпретатор промежуточного представления -> результат работы исх. программы на входных данных
Общая схема работы компилятора
Фаза анализа: (исходная программа на ЯП) -> лексический анализатор -> (последовательность лексем) -> синтаксический анализатор -> (промежуточное представление) -> семантический анализатор
Фаза синтеза: подготовка к генерации -> генерация кода -> (объектный модуль)
Определение порождающей грамматики
Порождающая грамматика – это четверка (VT, VN, P, S), где
VT – алфавит терминальных символов (терминалов)
VN – алфавит нетерминальных символов (нетерминалов, не пересекающийся с VT)
P – конечное подмножество множества (VN U VN)+ X (VT U VN)*; элемент (a, b) называется правилом вывода и записывается в виде a -> b; в а есть хотя бы один нетерминал
S – начальный символ (цель) грамматики, S из VN
Определение языка, порождаемого грамматикой
Язык, порождаемый грамматикой G = (VT. VN, P, S), L(G) – это множество цепочек {a} из VT: каждая a выводима из S.
7. Определение эквивалентности грамматик
Грамматики G1 и G2 называются эквивалентными, если L(G1) = L(G2).
Грамматики G1 и G2 почти эквивалентны, если языки, ими порождаемые, отличаются на более чем на эпсилон.
Определение типов грамматики и языков по Хомскому
Тип 0: на правила 0 не накладывается никаких ограничений, кроме огр. по определению(в а есть хотя бы 1 нетерминал)
Тип 1: а) неукорачивающие грамматики: |a| <= |b|; a из +, b из *
b) КЗ a -> b: a = w1 A w2; b = w1 B w2; w1, w2 из *
Тип 2: a) КС a -> b: a – отдельный нетерминал, b – непустая цепочка
b) УКС: a -> b: a – нетерминал, b – любая цепочка
Тип 3: a) праволинейные: A -> tB || A -> t, A, B из VN, t из VT
b) леволинейные: A -> Bt|| A -> t, …
Соотношения между типами грамматик
· Любая регулярная грамматика = КС
· Любая КС = КЗ, неукорачивающая
· Любая КЗ, любая неукорачивающая = типа 0
· Любая регулярная = УКС
· Любая КС = УКС
· УКС с эпсилон не явл. типа 1.
Соотношения между типами языков
Язык типа К, если его можно описать грамматикой типа К и нельзя грамматикой типа К + 1
· Любой регулярный язык = КС язык, но КС-языки не явл. регулярными
· Любой КС = язык типа 1, но есть типа 1 не КС
· Любой язык типа 1 = язык типа 0
Определение неоднозначности грамматики и языка
Дерево вывода: помеченное упорядоченное дерево, явл. деревом разбора в грамматике G = (VT, VN, P, S), если:
· Корень дерева помечен S, листья – символы из VT, либо эпсилон (для укорачивающих грамматик), все вершины – VN
· Если вершины помечены A из VN и пометки при непосредственных потомках, выписанные слева направо, образуют цепочку a1, …, an, где ai из (VT U VN), то A -> a1…an из P – правило вывода грамматики
· Если вершины помечены A из VN и при непосредственных потомках, помеченных эпсилон, то этот потомок единственный.
Грамматика G является неоднозначной, если существует w из L(G), для которой существует более одного дерева вывода.
