ИДЗ-2 МЛиТА 2017

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

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


1. Арифметические выражения с радикалами и натуральными числами

Пример: V25+V(230+V25V(230+V7)) - эта запись означает сумму двух величин, первая это корень квадратный  из 25, вторая - корень квадратный из суммы 230 и корня квадратного из корня 25 степени из суммы 230 и корня квадратного из 7.


2. Неприведенные многочлены от двух переменных с целыми коэффициентами

Пример:  -x^234+234xy(-23456x^34y-123400x^54y^7)+178


3. Знаки препинания в предложениях русского языка

Пример: Фффф, ффф: ффффф! Фффф?! Фффф… Ф? Фффф-фффф; ффф.


4*. Исправления в предложениях русского языка (ф - старая буква, ж - зачеркнутый сисмвол, х - зачеркнутый знак препинания, э - новая буква (новые знаки препинания обозначаются так же).

Пример (исправления в примере темы 2): ЖЭффжх. жЭфф: ффжжж! Фффф?х Ффжф… Фх. Ффффхффффхжжж.


5. Сноски в предложениях русского языка с двумя знаками препинания - точкой и тире (# - начало страницы, | - конец текста страницы и начало для комментариев к сноскам, /* - обозначение сноски, все сноски должны размещаться в конце страницы)

Пример: #Котто кококо/*. Кокко токко/* котоко. | /* - кото токо /* - тотто. #Токотот. Кокто кокто. Кто кто. | #Око/* | /* - окоооооооо. |


6. Списки с тремя уровнями вложености (| -перевод строки, _ - пробел):

Пример:

Татам:|_ - там;|_- тама;|__- ма;|__- та;|_- тата;|__- тат;|__-мам;|___- мамат;|___- мамам;|_- мат.


7. Двойные кавычки - 2. Правило русского языка: Если внутри слов, заключенных в кавычки, встречаются другие слова, в свою очередь заключенные в кавычки, рекомендуется (при условии, что для этого есть технические возможности) использовать кавычки разного рисунка: внешние – «елочки» , внутренние – „лапки“ (или – в текстах, набранных на компьютере, – "компьютерные кавычки"), например, ЗАО «Издательский дом „Комсомольская правда“», ООО «Компания „Металлинвест“»

Пример: ЗАО «Заза “Озаза” озаза»

Более сложный пример - произвольная вложенность:

ООО «Заза “Оза «ОАЗА “Оз”» аза «За»” озаза»


8. Двойные кавычки - 1. Правило русского языка: Если внутри слов, заключенных в кавычки, встречаются другие слова, в свою очередь заключенные в кавычки, то закрывающие кавычки ставятся только один раз, например, ЗАО «Издательский дом «Комсомольская правда» , ООО «Компания «Металлинвест».

Пример: ЗАО «Заза  «Озаза»

Более сложный пример - произвольная вложенность:

ЗАО «Заза  «Оза «Аза» а озо  «Озаза»


9о. Целые числа, кратные 10, но не кратные 4

Примеры: 2345430, -2311111111111111110


10о. Чётные суммы двоичных чисел

Примеры: 0+1+1, 1000000000001+1000+1011110+11111111

11. Частные единиц и двоек, дающих целые числа (вычислять частные надо справа налево):

Примеры: 1/1/2, 1/1/2/1/2, 1/1/1/1/1, 2/2, 2/2/2/2/2, 2/2/2/1, 1/1/1/1/2


12*. Нулевая сумма единиц и единиц с минусом

Примеры: 1-1+1-1+1-1+1+1-1-1, 1+1-1+1-1+1-1-1

Одним из решающих эту задачу показано, что LL(1) грамматика может быть построена. Постройте её, если не удастся, тогда упростите, как предложено ниже.

Докажите, что КС-грамматика для такого языка есть, а грамматики LL(1) нет.

Уменьшим множество сумм, ограничив их такими, для которых будут равны все суммы полученные отбрасыванием с начали и с конца одинакового числа слагаемых. Для этого языка LL(1) Грамматика может быть построена. Постройте.


13о. Аддитивная Римская система (нетрадиционная вариация)

Цифры идут в порядке убывания величин. D, L, V можно использовать не более одного раза (M-1000, D-400, C-100, L-50, X-10, V-5, I-1)


Примеры: MMMDCCCLXXXXVIIIIII, MMXVII


14. Неаддитивная Римская система

(M-1000, D-400, C-100, L-50, X-10, V-5, I-1)

Смотри Википедию для уточнения задания:

Меньшая цифра может быть записана и слева от большей, тогда её следует вычесть из большей. При этом вычитаться могут только цифры, обозначающие 1 или степени 10, а в качестве уменьшаемого выступать только ближайшие в числовом ряду к вычитаемой две цифры (то есть вычитаемое, умноженное на 5 или 10). Повторения меньшей цифры не допускаются. Таким образом, существует только шесть вариантов использования «правила вычитания»:

  • IV = 4

  • IX = 9

  • XL = 40

  • XC = 90

  • CD = 400

  • CM = 900

Например, число 94 будет XCIV = 100 − 10 + 5 − 1 = 94 — так называемое «правило вычитания» (появилось в эпоху поздней античности, а до этого римляне писали число 4 как IIII, а число 40 — как XXXX).


15. Римская система в версии Microsoft Excel

Смотри Википедию для уточнения задания:

В наши дни в некоторых случаях используется и упрощенная запись римских чисел: например, в программе Microsoft Excel при преобразовании арабских цифр в римские при помощи функции «РИМСКОЕ()» можно использовать несколько видов представления чисел, от классического до сильно упрощенного (так, число 499 может быть записано как CDXCIX, LDVLIV, XDIX, VDIV или ID). Упрощение состоит в том, что для уменьшения какой-либо цифры слева от неё может писаться любая другая цифра.

Примеры

999. Тысяча (M), вычтем 1 (I), получим 999 (IM) вместо CMXCIX. Следствие: 1999 — MIM вместо MCMXCIX

95. Сто (C), вычтем 5 (V), получим 95 (VC) вместо XCV

1950: Тысяча (M), вычтем 50 (L), получим 950 (LM). Следствие: 1950 — MLM вместо MCML

Одним из решающих обнаружено, что статья в Википедии неправильная, и формат записи чисел в Римской системе счисления такой же, как в задаче 14. Решите вместо этой задачи задачу 25.

16о. Структурированная матрица

Рассмотрим матрицу размера 2nx2n. Разобъем её на четыре одинаковых по размеру матриц и пронумеруем как показано на рисунке. Обозначим полученную структурированную матрицу как (1234). Теперь также можно структурировать любую из четырех подматриц. Например, структура второй матрицы будет (1(1234)34).  

1

2

3

4





1


1

2

3

4



3


4


Другие примеры записей структурированных матриц: ((12(1234)(1(123(1234))34))234)

Пояснение того, как получилась такая структура:

(1234)->((1234)234)->((12(1234)4)234)->((12(1234)(1234))234)->((12(1234)(1(1234)34))234)-> ((12(1234)(1(123(1234))34))234)


17о. Сумма синусов

Пример: sin(2310x+23,05)+sin(-x+1004)+sin(2,34x-0,1023)


18о. Произведение натуральных степеней

Пример: 2345^34^100*(122^10)^2*1001^1002^(12^33)^55


19. Дробно рациональные функции одной переменной c целыми коэффициентами

Примеры: x/(x^2+1),   (-123x^22+x^2-57x^2+234)/(x^23+89)


20о. Добавление единицы в единичной системе

Примеры правильных выражений: I+I=II, III+I=IIII, IIII+I=IIIII …


21. Алгебраические формулы со скобками и знаками операций + и -. При этом сумма операндов никогда не берется в скобки, а разность может браться, а может нет.

Пример: a+b-(c-(d-f))

 

22. Алгебраические формулы со скобками и знаками операций + и -. При этом разность операндов всегда берется в скобки, а сумма может браться, а может нет.

Пример:a+(b-(c+(d-a)))

 

23. Алгебраические формулы со скобками и знаками операций + и -. При этом перед скобкой плюс стоять не может.

Пример:a+b-(c-(d-f))

 

24. Алгебраические формулы со скобками и знаками операций + и . При этом знак умножения может быть опущен.

Пример:(a+b)(c+d)*fa

 

25. Алгебраические бесскобочные формулы, знаками арифметических операций и именами функций одной переменной, под знаком функции стоят бесскобочные выражения.

Пример: f(a+b-c)*c-g(a)+f(g(f(a*d+c)))


Comments