Ответы_экзамен_2009 (1115077), страница 4
Текст из файла (страница 4)
Библиотеки классов включаются в программу на этапе компиляции и компилируются со всей программой вместе.
Библиотеки компонент - это библиотека готовых откомпилированных программных модулей, предназначенных для использования в качестве составной части программы, и которыми можно манипулировать во время разработки программы. Компоненты бывают локальные (находящиеся на той же ЭВМ, где создается ПП) и распределенные (расположенные на сервере и доступные по сети ЭВМ).
Примеры технологий, использующих библ. компонент: CORBA, COM, DCOM, ActiveX, Java Beans
КРИТЕРИИ: - есть только перечисление типов библиотек: 1 балл;
- за каждую отсутствующую (неверную) характеристику: –3.
Замечание. За отсутствие упоминаний о распределенных объектах и компонентах не наказывать.
9. Записать результат перевода в ПОЛИЗ (постфиксную запись) фрагмента программы на языке Си:
for( i = 0; i < n; i++ ){ a = b - c - d; ++b; }
Ответ:
| ПОЛИЗ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
| &i | 0 | = | i | n | < | 26 | !F | 15 | ! | &i | ++ | 4 | ! | &a | b | c |
| 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | |
| - | d | - | = | &b | ## | 11 | ! |
|
Соглашения: 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. Оптимизация линейных участков программы.
а) Удаление бесполезных присваиваний.
б) Исключение избыточных вычислений.
в) Свертка объектного кода (выполнение во время компиляции тех операций исходной программы, для которых значения операндов уже известны).
г) Перестановка операций (для дальнейшей свертки или оптимизации вычислений).
д) Арифметические преобразования (на основе алгебраических и логических тождеств).
e) Оптимизация вычисления логических выражений.
3. Подстановка кода функции вместо ее вызова в объектный код.
4. Оптимизация циклов.
а) Вынесение инвариантных вычислений из циклов.
б) Замена операций с индуктивными (образующими арифметическую прогрессию) переменными (как правило, умножения на сложение).
в) Слияние и развертывание циклов.
Машинно-независимые преобразования исходной программы производятся в форме ее внутреннего представления.
КРИТЕРИИ: - только ответ на последний вопрос: 1 балл;
- отсутствие каждого типа (арабская цифра): –3;
- за каждую неточность внутри: –1 (не больше -3 для одной арабской цифры);
- неверный (отсутствует) ответ на последний вопрос: –3.
За каждую задачу — максимум 10 баллов.
| 1. Дана грамматика G: S Bc | Sa| ε B Ad A d A bB | (a) Классификация: найти такое целое k, что G является грамматикой типа k и не является грамматикой типа k+1. Ответ: k 2 (C bB не удовлетвор. определению леволинейной грамматики, B Cd не удовл. опре-делению праволинейной ) | (б) Каким из перечисленных классов Ответ:
|
(в) Описать язык L(G) в виде теоретико-множественной формулы или исчерпывающего словесного описания (не более 300 печатных знаков включая пробелы).
| Ответ L(G) { bn d n+2 сak | n0, k0} { ak | k0} КРИТЕРИИ: (а) нет ответа; неверный ответ : –3 (обоснование не обязательно) (б) за каждый неверный или отсутствующий ответ: –1 (т.е. всего до –4 за этот пункт) (обоснование не обязательно) (в) описание отсутствует или с ошибками: –3 | |||
| 2. (а) Дать определение приведенной КС-грамматики. (б) Эквивалентны ли данные КС-грамматики G1 и G2 ? Ответ обосновать. G1 : S BA A bAa | a | B b | | G2 : S E | BA D dDd | c | E ED | Ed A bAa | ADE | a | B DbE | b | ||
Ответ: (а) КС-грамматика G называется приведенной, если в ней нет недостижимых и бесплодных символов.
(б) Нет. Грамматика G2 после приведения:
S BA
A bAa | a |
B b
Следовательно, L(G1)L(G2), т.к. L(G2), L(G1).
КРИТЕРИИ: (а) нет ответа; определение с ошибками: –5
(б) нет ответа; неверный ответ; нет обоснования; неверное обоснование: –5
Замечание. Для обоснования неэквивалентности достаточно привести одну различающую цепочку.
| 3. По леволинейной грамматике G была построена диаграмма состояний A:
| ( (б) Детерминирован ли разбор по данной диаграмме ? Объясните ответ. | |
| (в) Если разбор по диаграмме состояний A недетерминированный (т.е. конечный автомат A — недетерминированный), то с помощью соответствующего алгоритма построить эквивалентный детерминированный автомат AD , иначе — написать для A программу-анализатор на языке C++. | ||
a) Восстановить по диаграмме A грамматику G:Ответ: (a) G: S Bс
B Bc| Ab | c
A Aa | Sa | a
(б) Разбор недетерминирован, т.к. автомат A не является детерминированным: из состояния B возможен переход в более чем одно состояние по символу c.
(в)
Построим таблицу переходов для AD :
a b c { H } { A } { B } { A } { A } { B } { B } {B, S } {B, S } { A } {B, S }
Начальное состояние: { H }. Заключительное состояние: { B, S }.
AD :
Допускаются другие способы построения, дающие в итоге такой же автомат AD с точностью до обозначений вершин.
КРИТЕРИИ: (а) нет ответа; грамматика построена, но неэквивалентная или не соответствующая
диаграмме : –3
(б) нет ответа; неверный ответ; ошибочное объяснение : –3
(в) нет ответа или программа на C++ приведена;
неэквивалентный или недетерм. автомат построен : –4
| 4. | И | |
| d — переместить перо по диагонали на одну клетку вправо-вверх. Например, по последовательности eeeeedddddeeeee интерпретатор построит букву «и» размера 55, изображенную на рисунке. Построить грамматику с терминальным алфавитом {e, d}, описывающую буквы «и» любого размера nn, n 1. В грамматике должно быть не более 7 правил вывода (считая альтернативы). | ||
меется клетчатый лист бумаги, бесконечный вправо и вниз. В левом верхнем углу расположено перо, оставляющее на бумаге след при перемещении. Перо управляется интерпретатором-графопостроителем. На вход интерпретатору подается последовательность символов-команд из алфавита { e , d }: e — переместить перо на одну клетку вниз;Ответ: Описание буквы «и» размера nn — это цепочка end nen. Следовательно, требуется построить грамматику, порождающую язык { end nen | n 1}: S EDSe | Ede
DE ED
Dd dd
Ed ed
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
