Ответы_экзамен_2009 (1115077), страница 2
Текст из файла (страница 2)
Порождает Lвх и формально генерирует соответствующие цепочки из Lц ,
но метод рек. спуска неприменим: -5
7. Дайте определение системы программирования. Перечислите основные компоненты классической системы программирования на базе ОС UNIX (ЯП Си). Кратко опишите назначение каждого из основных компонент.
Ответ:
Система программирования — это комплекс программных инструментов и библиотек, который поддерживает весь технологический цикл создания программного продукта (ПП).
[Как вариант: Система программирования — это комплекс программных средств (инструментов, библиотек), предназначенных для поддержки программного продукта на протяжении всего жизненного цикла этого программного продукта.]
Основные компоненты системы программирования: 1. Транслятор (проверяет синтаксическую правильность программ и переводит их с языка программирования на машинный язык, что и позволяет выполнить их на ЭВМ). 2. Макрогенератор или макропроцессор (работает непосредственно перед транслятором, используется для получения макрорасширения исходной программы). 3. Редактор связей или компоновщик (предназначен для связывания между собой (по внешним данным) объектных файлов, порождаемых компилятором, а также файлов библиотек, входящих в состав СП). 4. Редактор текстов (используется для составления и редактирования программ на языке программирования).
5. Отладчик (используется для проверочных запусков программ, локализации и исправления ошибок). 6. Библиотеки (облегчают работу программиста, предоставляя готовые фрагменты решения тех или иных подзадач программы, используются на этапе трансляции и исполнения).
КРИТЕРИИ: - неверное определение СП: –5;
- есть только определение СП: 1 балл;
- отсутствие каждого компонента (кроме макрогенератора): –3;
- за каждое неверное (отсутствующее) описание: –2;
- каждая мелкая погрешность: –1.
Замечание. Макрогенератор может рассматриваться как часть транслятора или пакетного редактора текстов, поэтому допустимо его отсутствие в перечне компонентов . Вместо трансляторов могут упоминаться компиляторы и ассемблеры.
8. Каковы два основных способа подключения библиотек функций? Чем они отличаются? Назовите основные достоинства этих способов.
Ответ: Библиотеки функций могут подключаться статически и динамически. ДБ в отличие от СтБ подключаются к программе не во время компиляции программы с помощью редактора связей, а непосредственно в ходе её выполнения. На этапе компоновки программы редактор связей, встречая вызовы функций ДБ, вместо выполнения процедуры связывания формирует таблицу точек вызова функций ДБ для последующей операции динамического связывания (то есть компоновщик не помещает в целевую программу тела функций ДБ). Таким образом, отложенный процесс полной компоновки завершится уже на этапе выполнения целевой программы. Преимущества ДБ:
-
не требуется включать в программу объектный код часто используемых функций, что существенно сокращает объем кода;
-
различные программы, выполняемые в некоторой ОС, могут пользоваться кодом одной и той же библиотеки, содержащейся в ОП;
-
изменения и улучшения функций библиотек сводится к обновлению только содержимого динамически подключаемых библиотек, а уже существующие тексты программ не требуют перекомпиляции (правда, этот же факт может оказаться недостатком, если при модификации функций каким-то образом меняется логика их работы, поэтому использование динамических библиотек накладывает определенные обязательства как на разработчика программы, так и на создателя библиотеки).
КРИТЕРИИ: - есть только ответ на первый вопрос: 1 балл;
- ответ не на вопрос: 0 баллов;
- неверный (или отсутствует) ответ на второй вопрос: –5;
- за каждое не упомянутое преимущество: –2;
- отсутствие преимуществ статических библиотек — не снижать (можно отметить относительную простоту реализации; устойчивость к модификациям — все равно все перекомпилируется и какие-то несоответствия со старым вариантом могут обнаружиться на этапе трансляции).
9. Записать результат перевода в ПОЛИЗ (постфиксную запись) фрагмента программы на языке Си:
b = i = 0; do {S =(a < i*(a + b) ? b++ : ++i);} while (i < 100);
Ответ:
| ПОЛИЗ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
| &b | &i | 0 | = | = | &S | a | i | a | b | + | * | < | 20 | !F | &b | ++ |
| 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | |
| 22 | ! | &i | ## | = | i | 100 | < | 30 | !F | 6 | ! |
|
Соглашения: 1. Адреса ПОЛИЗа можно обозначать подчеркиванием ( а = &a).
2. Префиксный ++ обозначен в ПОЛИЗе как ## .
3. Различение префиксных и постфиксных ++ разрешается на уровне интерпретации.
4. "Мусор" в стеке после выполнения присваивания игнорируется.
КРИТЕРИИ: - пропуск адреса в первом операнде операции(ий) присваивания: –3;
- пропуск адреса в операнде операции(ий) ++ : –3;
- неверный ПОЛИЗ первого оператора: –6;
- неверный ПОЛИЗ цикла (любые, не указанные выше ошибки): 0 баллов.
Замечание. Допустимы следующие вариации ПОЛИЗа в ответах:
(1) разрешается разворачивать унарные операции ++ и -- :
префиксные — ++х ==> &x, x, 1, +, = ;
постфиксные — х++ ==> &y, x, =, &x, x, 1, +, = ,y , где y — новый операнд;
(2) может использоваться операция «;» для выбрасывания «мусора» из стека, при трактовке присваивания как операции, оставляющей результат присваивания на вершине стека.
Соответственно изменяются адреса переходов в связи с (1) и/или (2).
10. Чем характерны машинно-зависимые оптимизирующие преобразования? Перечислите их основные типы, дав краткое пояснение. На каком этапе трансляции производится большая часть этих преобразований?
Ответ: При выполнении машинно-зависимой оптимизации компилятор принимает во внимание те или иные составляющие архитектуры вычислительной системы (особенности аппаратных и программных средств), на которой результирующая программа будет выполняться.
Основные типы м-з пр.: 1. Оптимальное распределение регистров процессора.
2. Оптимизация передачи параметров в процедуры и функции (через регистры).
3. Оптимизация кода для процессоров, допускающих распараллеливание вычислений.
Пример: a+b+c+d+e+f;
для одного потока обработки данных: ((((a+b)+c)+d)+e)+f;
для двух потоков обработки данных: ((a+b)+c)+((d+e)+f);
для трех потоков обработки данных: (a+b)+(c+d)+(e+f);
Машинно-зависимые преобразования производятся в основном над результирующей объектной программой.
КРИТЕРИИ: - нет ответа на первый вопрос: –3;
- только ответ на 1-й вопрос или только на последний: 1 балл;
- отсутствие каждого типа: –2;
- неверный (отсутствует) ответ на последний вопрос: –3;
За каждую задачу — максимум 10 баллов.
| 1. Дана грамматика G:
S A | ε A cdAa | cB cdcBa cdсDa Da Daa D a | найти такое целое k, что G является грамматикой типа k и не является грамматикой типа k+1. Ответ: k 1 (третье и четвертое правила не удовл. типу 2) | (б) Каким из перечисленных классов принадлежит язык L(G) ? Ответ:
|
(в) Описать язык L(G) в виде теоретико-множественной формулы или исчерпывающего словесного описания (не более 300 печатных знаков включая пробелы).
| Ответ: L(G) {(cd)n с an+k | n1, k1} {ε} КРИТЕРИИ: (а) нет ответа; неверный ответ : –3 (обоснование не обязательно) (б) за каждый неверный или отсутствующий ответ: –1 (т.е. всего до –4 за этот пункт) (обоснование не обязательно) (в) описание отсутствует или с ошибками: –3 | |||
| 2. (а) Дать определение бесплодного символа. (б) Эквивалентны ли данные КС-грамматики G1 и G2 ? Ответ обосновать. G1 : S BAaС | BC A Aa | a | B b | G2 : S E | BAa | AA D bDc | a E EaD | Ed A AaE | ADE | B DbE | bE | ||
Ответ: (а) символ A N называется бесплодным в грамматике
G T, N, P, S , если множество { T * | A } пусто.
(б) Нет. Грамматика G1 после применения алгоритма приведения не будет содержать ни одного правила (S — бесплодный символ), поэтому L(G1). Результатом применения алгоритма приведения к грамматике G2 будет грамматика : S AA
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
