ИДЗ-2 МЛиТА-2016

ИДЗ-2 МЛиТА 2016

Работы должны быть выложены на студенческих сайтах в форме документов, к редактированию которых преподаватель имеет доступ. В таблице группы нужно указать дату и время выкладки, разместить непосредственные ссылки на текст и на исполняемый файл программы (который, возможно, не удастся разместить на своем сайте).
В отчёт должны войти:
1. Набор граничных примеров и контрпримеров, демонстрирующих уточнение языка.
2. КС-грамматика языка.
3. Грамматический разбор одного примера.
4. Проверка того, что грамматика удовлетворяет однозначности ветвления по первому символу (принадлежит классу LL(1).
5. Модифицированная грамматика (если исходная КС-грамматика не удовлетворяет условию однозначности ветвления).
6. Таблица перевода языка в диаграммы (может быть опущена, если используется алгоритм прямого перевода, который должен быть сформулирован вместо диаграмм). Оптимизация числа диаграмм подстановкой.
7. Таблица перевода синтаксических диаграмм в алгоритм синтаксического анализа.
8. Таблица перевода алгоритма в программу.
9. Исходный код программы.
10. Исполняемый файл программы (при запуске программы должно появляться условие задачи с примерами и инструкция по вводу, после выполнения программа должна предложить ввести другой пример выражения для анализа).


Старосту прошу сначала раздать трудные темы (со звездочкой) тем, кто готов их сделать, потом темы средней трудности и только потом лёгкие - тем, у кого были затруднения с изучением темы "Языки и грамматики"


Темы ИДЗ-2, МЛиТА-2016

Языки и грамматики: синтаксический анализ

1. Предваренная форма с возможными скобками (правильная связь между именами переменных не требуется
Пример: А х[1] (Е х[231] Ах[12] Ах Р(х[512]; х[12]; х[0]))

2. Логические выражения с кванторами и скобками от трех переменных и одноместных предикатов:
Пример: А х (Е y P(x) =>!Q(z) )\/ Ах (P(x) + Eх Р(х))

3. Неприведённые многочлены Жегалкина
(х_231 +х_12)*(х+1)*(х_512*х_12*(1+х­_0))

4*. Запись многоэтажных формул в «урезанном» ТеХе

5. Арифметические выражения в html с нижними и верхними индексами

6o. «Финский язык»: слово состоит из небольшого числа согласных и гласных, буквы К могут повторяться в середине слова, но не более 2 подряд, буквы А аналогично могут повторяться в конце слова, остальные согласные и гласные должны чередоваться:
МУККОНЕН, РУККОЛА, ВАНТАА

7*. Арифметические выражения со скобками и учётом приоритета
a*(b*c+d), a*b*(c+d) - правильные, (a*b)*c+d, (a*b*c)+d – неправильные

8. Выражения с функциями одной переменной
f(x+y*x)-f(g(x+f(x)))

9. Константные выражения с натуральными числами, корнями и степенями
\/(23+375^58)/1+\/2/30

10o. Конечные непрерывные (цепные) дроби
(23;5,7,10,2), (5,70,2), (0;5,7,100) — правильные;
(3;12, 5, 1), (3; 0, 23, 3), (0,5,7,100) — неправильные

11o. Двоичные деревья с максимально полными промежуточными уровнями, то есть если deg(v)=2 и v не корень, то есть ребро (v;l), где l – лист

Бинарные деревья
((ll)(l)) – правильное    ((ll)(ll)) — правильное   ((ll)((l))) – неправильное

12. Пути шахматного короля по бесконечной доске с возвращением по пройденным клеткам в обратном порядке: ARRUULBRDDLL

Путь
13o. Сложные булевы функции трех переменных
F12(x;F3(y;y;F3(x;x;x));F256(z;y;x))

14. Импликации без лишних скобок, но не обязательно со всеми скобками с учетом чтения слева направо:
x=>(x=>z)=>(y=>(u=>w)) – правильная
x=>(x=>z)=>((y=>u)=>w) – неправильная

15o. Чётные числа как произведение натуральных
2357*33*21*1*172*30

16. Арифметические выражения от натуральных чисел с нечётным результатом (без операции деления)
351-497*25+271

17*. Упрощёный MathML

18*. Упрощённый C

19. Последовательность букв A и B, в которой ни одна комбинация из двух букв не повторяется дважды подряд:
ABBAAABBA – правильная    AAAABAAB – неправильная   ABAABABB – неправильная

20. Язык простой экспертной системы
ЕСЛИ А и В и НЕ С ТО D
ЕСЛИ А => В ТО C=>D ИНАЧЕ D=> C
ЕСЛИ или А или В или НЕ С ТО {ЕСЛИ C=>D ТО {ЕСЛИ НЕ А ТО E ИНАЧЕ F}} ИНАЧЕ G

21. Постфиксные вычисления с целыми числами и стеком глубины 3 (разделители — один или более пробелов):
10 23 234 * 31 * 45 - + правильная
10 23 234 *31 45 * - + неправильная

Comments