Краткие ответы по теории

Краткие ответы на экзаменационные вопросы по курсу“Системы программирования”1. Этапы жизненного цикла программного продукта.· Анализ: определение, формализация, документирование требований к будущемупрограммному продукту· Проектирование: формирование архитектуры системного программного продукта(декомпозиция: алгоритмы + модули, объекты + интерфейс)· Реализация: кодирование (непосредственное написание кода по описанной вспецификации функциональности и интерфейсам) + тестирование (запускпрограммы на некоторых входных данных с целью обнаружить дефект –несоответствие ожидаемого результата и выданного программой) + отладка(обнаружение причины дефекта и её исправление)· Внедрение (перенос продукта на целевую систему с инструментальной)· Сопровождение: эволюция программного продукта при его эксплуатации2.

Состав и схема функционирования классической системы программирования.· Редакторы текстов· Компиляторы, макрогенераторы, ассемблеры· Библиотеки· Редакторы связей· Загрузчики· Средства конфигурации· Отладчики· Средства тестирования· Профилировщики· Справочные системы· Системы планирования и координации работыТранслятор – программа, которая позволяет писать программу на языке высокого уровняи обеспечивает ее выполнение (позволяет писать не в машинных кодах)Компилятор - программа, которая осуществляет перевод исходной программы на ЯП вобъектную программу (одна из разновидностей транслятора)Интерпретатор – так же 1 из разновидностей трансляторов, выход – результат обработкиисходных данныхРедактор связей - программа, получающая на вход отдельные файлы с неразрешённымивнешними ссылками и увязывающая отдельные связиЗагрузчик - программа, обеспечивающая настройку модуля на конкретные адресаоперативной памяти, функции загрузчика в последнее время выполняет не системапрограммирования, а операционная системаСхема:Редактор текстов -> (исходная программа на некотором языке программирования) ->компилятор (+макрогенератор) -> (объектная программа – машинно-ориентированноепредставление программы, где есть информация в машинном коде + инф о внешнихсвязях + таблицы констант…) -> редактор связей –> (исполняемый модуль – программа вмашинных кодах как единое целое, относительно некоторого условного начальногоадреса) –> загрузчик (+отладчик)3.

Типы трансляторов, особенности интерпретаторов и компиляторов.· Компиляторы: выдают результат в виде исполняемого файла (в данном случаесчитаем, что компоновка входит в компиляцию). Этот файл транслируется одинраз (может быть запущен самостоятельно) и не требует для работы наличия намашине создавшего его транслятора· Интерпретаторы: исполняют программу после разбора (в этом случае в ролиобъектногокодавыступаетвнутреннеепредставлениепрограммыинтерпретатором). Исполняется она построчно. В данном случае программатранслируется(интерпретируется) при каждом запуске (если объектный кодкэшируется, возможны варианты) и требует для исполнения наличия на машинеинтерпретатора и исходного кодаСхема работы «чистого» компилятора: (исходная программа) -> компилятор ->(объектный модуль) -> (+ входные данные) -> (результаты работы)Схема работы чистого интерпретатора: (исходная программа + входные данные) ->интерпретатор -> (результаты работы)Смешанная стратегия: (исходная программа) -> компилятор промежуточногопредставления -> (промежуточное представление программы в байт-коде или машинномкоде + вх.

данные) -> интерпретатор промежуточного представления -> (результатыработы)4. Общая схема работы компилятора.Фаза анализа: (исходная программа на ЯП) -> лексический анализатор ->(последовательность лексем) ->синтаксический анализатор -> (промежуточноепредставление) -> семантический анализаторФаза синтеза: подготовка к генерации -> генерация кода -> (объектный модуль)5.

Основные понятия теории формальных грамматик и языков.Алфавит - это конечное множество символов.Цепочкой символов в алфавите V называется любая конечная последовательностьсимволов этого алфавита.Цепочка, которая не содержит ни одного символа, называется пустой цепочкой(обозначается ε)Если a и b - цепочки, то цепочка ab называется конкатенацией (или сцеплением) цепочекaиbОбращением (или реверсом) цепочки a называется цепочка, символы которой записаны вобратном порядке (обозначается aR).n-ой степенью цепочки a (будем обозначать an) называется конкатенация n цепочек aДлина цепочки a - это число составляющих ее символов (обозначается |a|)Язык в алфавите V - это подмножество цепочек конечной длины в этом алфавите.V* - множество, содержащее все цепочки конечной длины в алфавите V, включая пустуюцепочку ε.V+ - множество, содержащее все цепочки конечной длины в алфавите V, исключаяпустую цепочку ε.Порождающая грамматика – это четверка (VT, VN, P, S), гдеVT – алфавит терминальных символов (терминалов)VN – алфавит нетерминальных символов (нетерминалов), не пересекающийся с VTP – конечное подмножество множества (VN È VN)+ ´ (VT È VN)*; элемент (a, b)называется правилом вывода и записывается в виде a -> b; в a есть хотя бы одиннетерминалS – начальный символ (цель) грамматики, S из VNЦепочка bÎ(VT È VN)* выводима из цепочки bÎ(VT È VN)+ в грамматике G = (VT, VN,P, S) (обозначим aÞb), если существуют цепочки γ0, γ1, ¼ , γn, (n³0), такие, что a = γ0 ->γ1 -> ¼ -> γn = bПоследовательность γ0, γ1, ¼ , γn называется выводом длины n.Языком, порождаемым грамматикой G = (VT, VN, P, S), называется множество L(G) ={aÎVT* | SÞa}.Цепочка aÎ(VT È VN)*, для которой SÞa, называется сентенциальной формой вграмматике G = (VT, VN, P, S).6.

Эквивалентные грамматики.Грамматики G1 и G2 называются эквивалентными, если L(G1) = L(G2).Грамматики G1 и G2 почти эквивалентны, если языки, ими порождаемые, отличаютсяболее, чем на ε.7. Классификация формальных грамматик и языков по Хомскому.Тип 0: грамматики типа 0: на правила вывода не накладывается никаких ограничений,кроме ограничений по определению (в a есть хотя бы 1 нетерминал)Тип 1:а) неукорачивающие грамматики: a->b, |a| £ |b|, aÎ(VN È VN)+, bÎ(VN È+VN)b) контекстно-зависимые (КЗ): a->b, a = ξ1 Aξ2 ; b = ξ1γξ2 ; AÎVN, γÎ(VN È VN)+;ξ1, ξ2Î(VN È VN)*Тип 2: a) контекстно-свободные (КС): A->b, AÎVN, bÎ(VN È VN)+b) укорачивающие контекстно-свободные (УКС): A->b, AÎVN, bÎ(VN È VN)*Тип 3: a) праволинейные: A -> tB || A -> t; A, BÎVN, tÎVTb) леволинейные: A -> Bt|| A -> t; A, BÎVN, tÎVT8.

Соотношения между типами грамматик.· Любая регулярная грамматика – КС и УКС· Любая КС – УКС, КЗ, неукорачивающая· Любая КЗ – типа 0· Любая неукорачивающая – типа 0· Любая УКС – типа 0· УКС, содержащая правила вида A->ε, не является КЗ и не являетсяукорачивающей.9. Соотношения между типами языков.Язык L(G) является языком типа К, если его можно описать грамматикой типа К и нельзяграмматикой типа К + 1· Любой регулярный язык – КС-язык, но не все КС-языки являются регулярными(L={anbn|n>0})· Любой КС-язык – КЗ-язык, но не все КЗ-языки являются КС-языками(L={anbncn|n>0})· Любой КЗ-язык - язык типа 0· УКС-язык, содержащий ε, не является КЗ-языком10. Задача разбора.

Дерево вывода.Вывод цепочки bÎVT* из SÎVN в КС-грамматике G = (VT, VN, P, S), называется левым(левосторонним), если в этом выводе каждая очередная сентенциальная формаполучается из предыдущей заменой самого левого нетерминалаВывод цепочки bÎVT* из SÎVN в КС-грамматике G = (VT, VN, P, S), называется правым(правосторонним), если в этом выводе каждая очередная сентенциальная формаполучается из предыдущей заменой самого правого нетерминалаДерево является деревом вывода(деревом разбора) в грамматике G = (VT, VN, P, S),если:···каждая вершина дерева помечена символом из множества (VN È VT È ε), приэтом корень дерева помечен символом S; листья - символами из (VT È ε)если вершина дерева помечена символом AÎVN, а ее непосредственные потомки символами a1, a2, ... , an, где каждое aiÎ(VT È VN), то A->a1a2...an - правило выводав этой грамматике;если вершина дерева помечена символом AÎVN, а ее единственныйнепосредственный потомок помечен символом ε, то A->ε - правило вывода в этойграмматике.11.

Неоднозначность грамматик и языков.Грамматика G является неоднозначной, если существует aÎL(G), для которойсуществует более одного дерева вывода. В противном случае грамматика называетсяоднозначной.Проблема определения однозначности грамматики алгоритмически неразрешима.Язык, порождаемый грамматикой, называется неоднозначным, если он не может бытьпорождён никакой однозначной грамматикой.12. Недостижимые и бесполезные (бесплодные) символы грамматики.