2010 вариант 1 (Экзамен. Варианты заданий и ответы)

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

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

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

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

G: H  bA | bB | aC

A  bC

B  aC

C  aA | bB | 

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 ();

}

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

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

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

9. Дать определение приведённых грамматик. Преобразовать контекстно-свободную грамматику G к приведённому виду, выписывая результаты применения каждого шага используемого алгоритма.

G: S  ACb | Aa

A  Aa | Ca | a

B  Aa | CDb | Bb

C  Ab | b

D  Aa | Cb | a

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