Ответы 2010 вариант 1 (1119774)

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

Текст из файла

Вариант 1_2010 Ф.И.О.___________________________________№ группы________

За каждую задачу — максимум 10 баллов

(в) Классификация: найти такое целое k, что G является грамматикой типа k и не является грамматикой типа k+1.

Ответ: k  0 (есть укорачивающее правило A  ε и не КС-правило EE  EEE)

КРИТЕРИИ: (а) описание отсутствует или с ошибками: –4

(б) снимаемые баллы за каждый неверный или отсутствующий ответ в таблице

(обоснование не обязательно)

(в) нет ответа; неверный ответ: –4 (обоснование не обязательно)

2. Дать определение эквивалентных грамматик. Приведите примеры эквивалентных и почти эквивалентных грамматик. Могут ли неэквивалентные грамматики порождать один и тот же язык?

Ответ:

(а) Грамматики G₁ и G₂ называются эквивалентными, если их языки совпадают, L(G₁) = L(G₂). (б) Например, из трёх разных грамматик:

G₁ = ({0,1}, {A,S}, P₁, S) и G₂ = ({0,1}, {S}, {S  0S1 | 01}, S)

P₁: S  0A1 G₃ = ({0,1}, {S}, {S  0S1 | }, S)

0A  00A1

A   G₁ и G₂ эквивалентны, L(G₁) = L(G₂) = {0ⁿ1ⁿ | n > 0}.

G₁ (G₂) и G₃ почти эквивалентны, L(G₃) = {0ⁿ1ⁿ | n  0}

(в) Нет, это невозможно по приведённому определению.

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

(б) за каждый из двух отсутствующих примеров: –3

(в) нет ответа; неверный ответ: –5

3. Построить по заданной грамматике G конечный автомат (в виде ДС). Если автомат оказался детерминированным, построить анализатор на Си, иначе – преобразовать автомат в соответствии с алгоритмом преобразования НКА в эквивалентный ДКА, и по полученному ДКА построить леволинейную грамматику.

G: H  bA | bB | aC

A  bC

B  aC

C  aA | bB | 

Ответ: Автомат недетерминирован G’: S  C

A  Ca

B  Cb

C  Ab | Ba | Da | Db | a

D  b

Функция переходов исходного автомата

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

(б) леволинейная грамматика построена, но неэквивалентная или не соответствующая новой диаграмме: –5

(в) нет ответа или приведена программа анализатора: 0

Ответ: Описание буквы «Г» размера nm — это цепочка cⁿa^m. Следовательно, требуется построить грамматику, порождающую язык {cⁿa^m | n,m 1}: S  сS | cA

A  aA | a

Соглашение запись a является сокращением cout << “a”;

Грамматика с действиями: S  ссSe | ccAe

A  aaA | aa

КРИТЕРИИ: порождается пустая цепочка: –5

имеется лишняя (непустая) или недостающая цепочка: –10

за каждое лишнее правило: –3

5. Восстановить грамматику по заданному анализатору на С++. Сформулировать достаточное условие применимости метода рекурсивного спуска для грамматик без эпсилон-правил. Соответствует ли полученная грамматика данному условию? Обосновать свой ответ. Корректен ли данный анализатор? Обосновать свой ответ (доказать корректность или найти примеры некорректного поведения анализатора).

void S () { if (c == ‘b’) { c = GetS (); A ();

if (c == ‘a’) { c = GetS (); C (); D (); } else Error ();

if (c == ‘’) return;

}

Error ();

}

void A () { if (c == ‘a’) { c = GetS (); A (); } else B (); }

void B () { if (c == ‘b’) { c = GetS (); B (); } else C (); }

void C () { if (c == ‘a’) { c = GetS (); C (); } else D (); }

void D () { if (c == ‘b’) { c = GetS (); D (); } else A (); }

Ответ: Восстановленная грамматика имеет вид:

G = ({a, b, }, {A, B, C, D, S}, P, S) P: S  bAaCD

A  aA | B B  bB | C

C  aC | D D  bD | A

Анализатор некорректен: он, например, зацикливается на цепочке “b”.

Достаточное условие применимости метода рекурсивного спуска для грамматик без эпсилон-правил:

1. либо A  , где   (T  N)^* и это единственное правило вывода для A;

2. либо A  a₁₁ | a₂₂ | ... | a_n_n, где a_i  T для i = 1,2,...,n; a_i  a_j для i  j; _i  (T  N)^*.

Грамматика G достаточным условиям не соответствует: не все правила для нетерминальных символов A, B, C и D начинаются с терминальных символов.

КРИТЕРИИ: Неправильно восстановлена грамматика: -5.

Неверная формулировка достаточного условия применимости: -4.

Неверный ответ на вопрос о соответствии грамматики сформулированному условию: -2.

Нет обоснования соответствия/несоответствия грамматики: -1.

Неверный ответ на вопрос о корректности анализатора: -2.

Нет обоснования корректности (не найден пример “плохой” цепочки): -1.

6. Дать определение системы программирования. Перечислить основные компоненты систем программирования и их основное назначение.

Ответ: cистемой программирования называется комплекс программных средств, предназначенных для поддержки программного продукта на протяжении всего жизненного цикла этого продукта. Основные компоненты современных развитых систем программирования:

• средства интеграции компонентов системы программирования (-1)

• редакторы текстов (-2)

• трансляторы: интерпретаторы, компиляторы и ассемблеры, вместе с макрогенераторами (-2)

• библиотеки (-2)

• редакторы связей (-2)

• средства конфигурирования (-1)

• отладчики (-2)

• средства тестирования (-1)

• профилировщики (-1)

• справочные системы (-1)

КРИТЕРИИ: За пропуск компонентов снижать на 1-2 балла.

7. Выпишите не менее 5 различных видов внутреннего представления программ, используемых при компиляции.

Ответ:

• Связные списочные структуры, представляющие синтаксическое дерево

• Многоадресный код с явно именуемыми результатами (тетрады)

• Многоадресный код с неявно именуемыми результатами (триады)

• Инфиксная запись

• Префиксная запись

• Постфиксная запись

• Язык ассемблера

КРИТЕРИИ: За каждый пропущенный из необходимых 5 видов: -2.

8. С какими компонентами интегрированных систем программирования взаимодействуют входящие в них символьные отладчики? Какую помощь и для чего оказывают отладчикам эти компоненты?

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

КРИТЕРИИ: За пропуск какого-либо компонента: -3 (за каждый пропуск).

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

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

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