Ответы 2010 вариант 2 (1119775)

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

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

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

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

(в) Тип языка: найти такое целое k, что язык L(G) является языком типа k и не является языком k+1.

Ответ: k  3 (для заданного языка существует порождающая его регулярная грамматика)

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

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

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

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

2. Дать определение порождающей грамматики. Какие ограничения на использование терминальных и нетерминальных символов в правилах грамматики наложены этим определением? Предложите какую-либо грамматику для языка L = {(a,b)⁺} и укажите на этом примере все компоненты, упоминаемые в определении грамматики.

Ответ: (а) Порождающая грамматика G – это четверка (T, N, P, S), где

T – алфавит терминальных символов (терминалов),

N – алфавит нетерминальных символов (нетерминалов), множества N и T не пересекаются друг с другом, то есть N  T = ,

P – конечное множество правил – подмножество множества (T  N)⁺  (T  N)^*;

S – начальный символ (цель) грамматики, S  N.

(б) Этим определением требуется, чтобы в левой части любого правила грамматики присутствовал хотя бы один нетерминальный символ. Других формальных ограничений нет.

(в) Например, в грамматике G = ({a,b}, {A,S}, {S  AS | A; A  a | b}, S):

Множество терминальных символов T – {a,b}

Множество нетерминальных символов N – {A,S}

Множество правил P – {S  AS | A; A  a | b}

Начальный символ (цель) грамматики S

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

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

(в) нет примера грамматики или неправильный пример: –4

за каждый неверный или отсутствующий компонент определения: –1 (до –4)

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

b

Ответ: Gл: S  A | B

A  Aa | Bb | a

a

a

a

a



B  Ab | Ba | a

Автомат недетерминирован

b



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

Gлев: S  C Gправ: H  aC

C  Ca | Cb | a C  aC | bC | 

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

(б) построен неэквивалентный или недетерминированный автомат: –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a

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

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

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

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

void S () { if (c == ‘1’) { c = GetL (); A();

if (c != ‘0’) Error ();

c = GetL (); C(); D();

if (c != ‘1’) Error ();

c = GetL ();

}

else Error ();

}

void A () { if (c == ‘0’) { c = GetL (); A(); }

else if (c == ‘1’) { c = GetL (); B(); } else Error (); }

void B () { if (c == ‘0’) { c = GetL (); C(); }

else if (c == ‘1’) { c = GetL (); B(); } else Error (); }

void C () { if (c == ‘0’) { c = GetL (); C(); }

else if (c == ‘1’) { c = GetL (); D(); } else Error (); }

void D () { if (c == ‘1’) { c = GetL (); D(); } }

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

G = ({0, 1}, {A, B, C, D, S}, P, S) P: S  1A0CD1

A  0A | 1B

B  0C | 1B

C  0C | 1D

D  1D | ε

Анализатор некорректен: любая правильная цепочка должна заканчиваться символом ‘1’, а этот символ может быть зря прочитан процедурой “D()”, что приведёт к неправильной трактовке всех правильных цепочек, например, анализатор выдаёт ошибку на правильной цепочке “10101011”.

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

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

2. либо X ® a₁α₁ |... | a_nα_n где a_i  T для i = 1, ..., n; a_i ¹ a_j для i ¹ j; α_i  (T  N)^*;

3. либо X ® a₁α₁ |... | a_nα_n | ε где a_i  T для i = 1, ..., n; a_i ¹ a_j для i ¹ j; α_i  (T  N)^*,

и first (X) Ç follow (X) = .

Грамматика G показанным условиям не соответствует: first (D) Ç follow (D) = {1}¹ .

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

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

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

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

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

Нет обоснования корректности (нет рассуждений о конечных символах цепочек, не найден пример неправильно трактуемой цепочки и т. д.): -2.

6. Описать основные задачи ассемблеров, компиляторов и интерпретаторов. В чём сходство и различие этих компонентов систем программирования?

Ответ: Ассемблер – для трансляции программ, написанных на языках типа 1:1, компилятор – для трансляции программ, написанных на языках высокого уровня, интерпретатор – не для трансляции программ, а для получения результата с помощью алгоритма, закодированного в программе.

КРИТЕРИИ: За отсутствие комментариев к какому-либо виду трансляторов: -4.

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

Ответ:

Синтаксический анализатор

Завершение формирования программы

Обращение за лексемой

Текст

Лексема

Синтаксическая конструкция

Возврат управления

Лексический анализатор

Семантический анализатор, распределитель памяти, генератор команд

Объектный модуль

Лексический и синтаксический анализаторы взаимодействуют как сопрограммы: ЛА формирует лексемы по исходной программе по запросам СА. Работа ведется под управлением СА.

КРИТЕРИИ: (a) За отсутствие схемы или ошибки в ней: -5.

(б) За отсутствие описания способа взаимодействия: -3.

(в) Нет ответа или ошибка: -3.

8. Описать основные подходы, использующие поведенческие и структурные тесты программ. В чем их основные различия?

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

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

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

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

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

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

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