V2_2010 (Варианты языков от Волковой)

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

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

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

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

a

a

a

a



b

b



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

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

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

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

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

G: S  Ab | Ba

A  Ca

B  Bb | Da

C  Aa | Bb | a | b

D  Db | Ba

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