A2_2010 (1119653)

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

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

Вариант 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. Нарисовать схему однопроходного компилятора. Каким образом в таких компиляторах взаимодействуют лексический и синтаксический анализаторы? Какой из анализаторов является ведущим в таком взаимодействии?

Ответ:

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

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

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

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

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

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

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

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

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