2009 вариант 1, 2, 3 ответы (1119755), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

КРИТЕРИИ: - неверное определение СП: –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. Адреса ПОЛИЗа можно обозначать подчеркиванием ( а = &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 баллов.

(в) Описать язык L(G) в виде теоретико-множественной формулы или исчерпывающего словесного описания (не более 300 печатных знаков включая пробелы).

Ответ: (а) символ A  N называется бесплодным в грамматике
G   T, N, P, S , если множество {  T ^* | A  } пусто.

(б) Нет. Грамматика G₁ после применения алгоритма приведения не будет содержать ни одного правила (S — бесплодный символ), поэтому L(G₁). Результатом применения алгоритма приведения к грамматике G₂ будет грамматика : S  AA

A  .

Следовательно, L(G₂){ }. Таким образом, L(G₁)L(G₂), т.к.   L(G₂),   L(G₁).

КРИТЕРИИ: (а) нет ответа; определение с ошибками: –5

(б) нет ответа; неверный ответ; нет обоснования; неверное обоснование: –5

Замечание. Для обоснования неэквивалентности достаточно привести одну различающую цепочку.

Ответ почти эквивалентны считать верным.

Ответ: (a) G: S  c | Sc | Ac

A  Bb| Aa

B  Aa | Bb | b

(б) Разбор недетерминирован, т.к. автомат A не является детерминированным: из состояния A возможен переход в более чем одно состояние (по символу а). [или: т.к. из состояния B возможен переход в более чем одно состояние (по символу b)]

(в)

Характеристики

Список файлов ответов (шпаргалок)