СП - Краткие ответы на экзаменационные вопросы

17

Краткие ответы на экзаменационные вопросы по курсу “Системы программирования”

1. Этапы жизненного цикла программного продукта.

• Анализ: определение, формализация, документирование требований к будущему программному продукту

• Проектирование: формирование архитектуры системного программного продукта (декомпозиция: алгоритмы + модули, объекты + интерфейс)

• Реализация: кодирование (непосредственное написание кода по описанной в спецификации функциональности и интерфейсам) + тестирование (запуск программы на некоторых входных данных с целью обнаружить дефект – несоответствие ожидаемого результата и выданного программой) + отладка (обнаружение причины дефекта и её исправление)

• Внедрение (перенос продукта на целевую систему с инструментальной)

• Сопровождение: эволюция программного продукта при его эксплуатации

1. Состав и схема функционирования классической системы программирования.

• Редакторы текстов

• Компиляторы, макрогенераторы, ассемблеры

• Библиотеки

• Редакторы связей

• Загрузчики

• Средства конфигурации

• Отладчики

• Средства тестирования

• Профилировщики

• Справочные системы

• Системы планирования и координации работы

Транслятор – программа, которая позволяет писать программу на языке высокого уровня и обеспечивает ее выполнение (позволяет писать не в машинных кодах)

Компилятор - программа, которая осуществляет перевод исходной программы на ЯП в объектную программу (одна из разновидностей транслятора)

Интерпретатор – так же 1 из разновидностей трансляторов, выход – результат обработки исходных данных

Редактор связей - программа, получающая на вход отдельные файлы с неразрешёнными внешними ссылками и увязывающая отдельные связи

Загрузчик - программа, обеспечивающая настройку модуля на конкретные адреса оперативной памяти, функции загрузчика в последнее время выполняет не система программирования, а операционная система

Схема:

Редактор текстов -> (исходная программа на некотором языке программирования) -> компилятор (+макрогенератор) -> (объектная программа – машинно-ориентированное представление программы, где есть информация в машинном коде + инф о внешних связях + таблицы констант…) -> редактор связей –> (исполняемый модуль – программа в машинных кодах как единое целое, относительно некоторого условного начального адреса) –> загрузчик (+отладчик)

1. Типы трансляторов, особенности интерпретаторов и компиляторов.

• Компиляторы: выдают результат в виде исполняемого файла (в данном случае считаем, что компоновка входит в компиляцию). Этот файл транслируется один раз (может быть запущен самостоятельно) и не требует для работы наличия на машине создавшего его транслятора

• Интерпретаторы: исполняют программу после разбора (в этом случае в роли объектного кода выступает внутреннее представление программы интерпретатором). Исполняется она построчно. В данном случае программа транслируется(интерпретируется) при каждом запуске (если объектный код кэшируется, возможны варианты) и требует для исполнения наличия на машине интерпретатора и исходного кода

Схема работы «чистого» компилятора: (исходная программа) -> компилятор -> (объектный модуль) -> (+ входные данные) -> (результаты работы)

Схема работы чистого интерпретатора: (исходная программа + входные данные) -> интерпретатор -> (результаты работы)

Смешанная стратегия: (исходная программа) -> компилятор промежуточного представления -> (промежуточное представление программы в байт-коде или машинном коде + вх. данные) -> интерпретатор промежуточного представления -> (результаты работы)

1. Общая схема работы компилятора.

Фаза анализа: (исходная программа на ЯП) -> лексический анализатор -> (последовательность лексем) -> синтаксический анализатор -> (промежуточное представление) -> семантический анализатор

Фаза синтеза: подготовка к генерации -> генерация кода -> (объектный модуль)

1. Основные понятия теории формальных грамматик и языков.

Алфавит - это конечное множество символов.

Цепочкой символов в алфавите V называется любая конечная последовательность символов этого алфавита.

Цепочка, которая не содержит ни одного символа, называется пустой цепочкой (обозначается ε)

Если и - цепочки, то цепочка называется конкатенацией (или сцеплением) цепочек и 

Обращением (или реверсом) цепочки называется цепочка, символы которой записаны в обратном порядке (обозначается ^R).

n-ой степенью цепочки (будем обозначать ⁿ) называется конкатенация n цепочек 

Длина цепочки  - это число составляющих ее символов (обозначается ||)

Язык в алфавите V - это подмножество цепочек конечной длины в этом алфавите.

V* - множество, содержащее все цепочки конечной длины в алфавите V, включая пустую цепочку ε.

V⁺ - множество, содержащее все цепочки конечной длины в алфавите V, исключая пустую цепочку ε.

Порождающая грамматика – это четверка (VT, VN, P, S), где

VT – алфавит терминальных символов (терминалов)

VN – алфавит нетерминальных символов (нетерминалов), не пересекающийся с VT

P – конечное подмножество множества (VT  VN)⁺  (VT  VN)*; элемент (, ) называется правилом вывода и записывается в виде  -> ; в  есть хотя бы один нетерминал

S – начальный символ (цель) грамматики, S из VN

Цепочка (VT VN)* выводима из цепочки (VT VN)⁺ в грамматике G = (VT, VN, P, S) (обозначим ), если существуют цепочки γ₀, γ₁,  , γ_n, (n0), такие, что = γ₀ -> γ₁ ->  -> γ_n = 

Последовательность γ₀, γ₁,  , γ_n называется выводом длины n.

Языком, порождаемым грамматикой G = (VT, VN, P, S), называется множество L(G) = {VT* | S}.

Цепочка (VT VN)*, для которой S, называется сентенциальной формой в грамматике G = (VT, VN, P, S).

1. Эквивалентные грамматики.
   Грамматики G1 и G2 называются эквивалентными, если L(G1) = L(G2).

Грамматики G1 и G2 почти эквивалентны, если языки, ими порождаемые, отличаются не более чем на ε.

1. Классификация формальных грамматик и языков по Хомскому.

Тип 0: грамматики типа 0: на правила вывода не накладывается никаких ограничений, кроме ограничений по определению (в  есть хотя бы 1 нетерминал)

Тип 1: а) неукорачивающие грамматики: ->, ||  ||, (VT  VN)⁺, (VT  VN)^*

b) контекстно-зависимые (КЗ): ->,  = ξ¹Aξ²;  = ξ¹γξ²; AVN, γ(VT  VN)⁺; ξ¹, ξ²(VT  VN)^*

Тип 2: a) контекстно-свободные (КС): A->, AVN, (VT  VN)⁺

b) укорачивающие контекстно-свободные (УКС): A->, AVN, (VT  VN)^*

Тип 3: a) праволинейные: A -> tB || A -> t; A, BVN, tVT

b) леволинейные: A -> Bt|| A -> t; A, BVN, tVT

1. Соотношения между типами грамматик.

• Любая регулярная грамматика – КС и УКС

• Любая КС – УКС, КЗ, неукорачивающая

• Любая КЗ – типа 0

• Любая неукорачивающая – типа 0

• Любая УКС – типа 0

• УКС, содержащая правила вида A->ε, не является КЗ и не является укорачивающей.

1. Соотношения между типами языков.

Язык L(G) является языком типа К, если его можно описать грамматикой типа К.

• Любой регулярный язык – КС-язык, но не все КС-языки являются регулярными (L={aⁿbⁿ|n>0})

• Любой КС-язык – КЗ-язык, но не все КЗ-языки являются КС-языками (L={aⁿbⁿcⁿ|n>0})

• Любой КЗ-язык - язык типа 0

• УКС-язык, содержащий ε, не является КЗ-языком

Поэтому (так как у языка может быть сразу несколько типов) под типом языка обычно понимают максимальный возможный тип грамматики, которой можно описать этот язык.

1. Задача разбора. Дерево вывода.

Вывод цепочки VT* из SVN в КС-грамматике G = (VT, VN, P, S), называется левым (левосторонним), если в этом выводе каждая очередная сентенциальная форма получается из предыдущей заменой самого левого нетерминала.

Вывод цепочки VT* из SVN в КС-грамматике G = (VT, VN, P, S), называется правым (правосторонним), если в этом выводе каждая очередная сентенциальная форма получается из предыдущей заменой самого правого нетерминала.

Дерево является деревом вывода(деревом разбора) в грамматике G = (VT, VN, P, S), если:

• каждая вершина дерева помечена символом из множества (VN VT ε), при этом корень дерева помечен символом S; листья - символами из (VT ε)

• если вершина дерева помечена символом AVN, а ее непосредственные потомки - символами a₁, a₂, ... , a_n, где каждое a_i(VT VN), то A->a₁a₂...a_n - правило вывода в этой грамматике;

• если вершина дерева помечена символом AVN, а ее единственный непосредственный потомок помечен символом ε, то A->ε- правило вывода в этой грамматике.

1. Неоднозначность грамматик и языков.

Грамматика G является неоднозначной, если существует L(G), для которой существует более одного дерева вывода. В противном случае грамматика называется однозначной.

Проблема определения однозначности грамматики алгоритмически неразрешима.

Язык, порождаемый грамматикой, называется неоднозначным, если он не может быть порождён никакой однозначной грамматикой.

1. Недостижимые и бесполезные (бесплодные) символы грамматики. Алгоритмы удаления недостижимых и бесполезных (бесплодных) символов. Приведенная грамматика.

Символ x(VT  VN) называется недостижимым в грамматике G = (VT, VN, P, S), если он не появляется ни в одной сентенциальной форме этой грамматики.

Алгоритм удаления недостижимых символов:

1. V₀ = {S}; i = 1

2. V_i = {x | x(VT  VN), в Р есть A -> x и AV_i-1, a, b(VT U VN)*}  V_i-1

3. Если V_i  V_i-1, то i=i+1 и переходим к шагу 2, иначе VN’ = V_i VN; VT’ = V_i VT; P’ состоит из правил множества P, содержащих только символы V_i; G’ = (VT’, VN’, P’, S).

Символ А из VN называется бесплодным в грамматике G = (VT, VN, P, S), если множество {aVT* | A -> a} пусто

Алгоритм удаления бесплодных символов:

Рекурсивно строим множества N₀, N₁, …

1. N₀ = 0, i = 1

2. N_i = {A | (A -> )P и (N_i-1  VT)*}  N_i-1

3. Если N_i  N_i-1, то i=i+1 и переходим к шагу 2, иначе VN’ = N_i, P’ состоит из правил множества P, содержащих только символы из VN’  VT; G’ = (VT, VN’, P’, S)

Грамматика называется приведенной, если в ней нет недостижимых и бесплодных символов.

Алгоритм приведения грамматики:

1. Обнаруживаются и удаляются все бесплодные символы

2. Обнаруживаются и удаляются все недостижимые символы

1. Определение недетерминированного конечного автомата (НКА).

Недетерминированный конечный автомат (НКА) - это пятерка (K, VT, F, H, S), где:

K – конечное множество состояний