ИДЗ-2(МЛиТА-2015)

ИДЗ-2 МЛиТА 2015

Работы должны быть выложены на студенческих сайтах в форме документов, к редактированию которых преподаватель имеет доступ.

В отчёт должны войти:

1. Набор граничных примеров и контрпримеров, демонстрирующих уточнение языка.

2. КС-грамматика языка.

3. Грамматический разбор одного примера.

4. Проверка того, что грамматика удовлетворяет однозначности ветвления по первому символу (принадлежит классу LL0).

5. Модифицированная грамматика (если исходная КС-грамматика не удовлетворяет условию однозначности ветвления).

6. Таблица перевода языка в диаграммы (может быть опущена, если используется алгоритм прямого перевода, который должен быть сформулирован вместо диаграмм). Оптимизация числа диаграмм подстановкой.

7. Таблица перевода синтаксических диаграмм в алгоритм синтаксического анализа.

8. Таблица перевода алгоритма в программу.

9. Исходный код программы.

10. Исполняемый файл программы (при запуске программы должно появляться условие задачи с примерами и инструкция по вводу, после выполнения программа должна предложить ввести другой пример выражения для анализа).



Задания

1. Алгебраические формулы со скобками одного уровня вложенности (максимально):

    (a+b)+(c+d*e)+(d*e); a; (a+b)*c*(d*e); a+(b*c)


2*. Алгебраические формулы со скобками одного уровня вложенности (максимально) без лишних скобок с учетом приоритета операций:

    (a+b)+(c+d*e)+d*e; a; (a+b)*c*(d*e); a+b*c


3*. Алгебраические формулы со скобками одного уровня вложенности (максимально) без лишних скобок с учетом ассоциативности операций:

    a+b+c+d*e+(d*e); a; (a+b)*c*d*e; a+(b*c)


4. Выражения с неассоциативной операцией /:

    (((a/b)/c)/(b/c))/(d/e); a/b/c/(b/c)/(d/e)


5*. Выражения с неассоциативной операцией / без лишних скобок с учетом естественного порядка выполнения операций слева направо:

    (a/b)/c/(b/c)/(d/e); a/b/c/(b/c)/(d/e)


6. Выражения с одной ассоциативной операцией (+) и одной неассоциативной операцией и максимально одним уровнем вложенности скобок

    (a-b)-(c-d)+(b+c); a-b-(c-d)+b+(e-f)


7*. Выражения с одной ассоциативной операцией (+) и одной неассоциативной операцией и максимально одним уровнем вложенности скобок без лишних скобок с учетом ассоциативности операции +:

    a-b-(c-d)+b+c; a-b-(c-d)+b+e-f


8**. Выражения с одной ассоциативной операцией (+) и одной неассоциативной операцией и любым уровнем вложенности скобок без лишних скобок с учетом ассоциативности операции +:

    a-b-((c-d)+b+c); a-((b-(c-d))+b+e-f)


9*. Выражения единичной матрицы различными видами произведений квадратных матриц одного порядка:

    A^(-1)*A; E; A*E*A^(-1); B*A^(-1)*A*B^(-1); A*E*B*C*C^(-1)*B^(-1)*A^(-1)

(или более простой вариант, в котором обратная матрица обозначается одним символом, например для A это A' или ещё более простой вариант, когда матрицей и ей обратной есть разделитель, например, A^(-1)_A; E; A*E_A^(-1); B*A^(-1)_A*B^(-1); A*E*B*C_C^(-1)*B^(-1)*A^(-1))


10. Запись больших вещественных чисел в нормальной форме (мантисса, порядок):

    3.45E-45; -1.4780120E200


6*. Простой XML (постановку задачи уточнить самим):

    <b>text<i>text</i></b>


11. Неравенства < в единичной системе счисления:

    11<111; 1<11111; 1111<11111


12. Выражения значений функции s(x)=x+1 в единичной системе счисления:

    s(1)=11; s(11)=111; s(11111)=111111


13. Выражения значений функции b(x)=x-1 в единичной системе счисления:

    s(11)=1; s(1111)=111; s(11111)=1111


14. Выражения значений функции t(x)=2*x в единичной системе счисления:

    s(1)=11; s(11)=1111; s(111)=111111


15. Выражения значений функции d(x)=[x/2] в единичной системе счисления:

    s(11)=1; s(111)=1; s(1111)=11; s(11111)=11


16. Выражения нестрогого неравенства в суммах единиц:

    1+1>=1; 1+1+1>=1+1+1; 1+1+1+1+1>=1+1


17. Равенства чисел в единичной системе счисления:

11=11; 11111=11111; 1=1


18. Выражения НОД нескольких длинных натуральных чисел:

    23; D(1234520;256712); D(D(325;1);34)); D(D(1234;4321);D(23;2345))


19. Одномерные пазлы (простые). Описать множество различных цепочек, определяющих прямоугольники из пазлов A, B, C, D и E:

ECA; EBCDA; EBBBBCDDA


20*. Одномерные пазлы (с симметрией). Описать множество различных цепочек, определяющих прямоугольники из пазлов A, B, C и их симметричных отражений относительно вертикальной оси A' и B':

A'CA; A'BCB'A; A'BBBBCB'B'A

Пазл

21*. Одномерные пазлы (с поворотом). Описать множество различных цепочек, определяющих полоски с плотно прилегающими сторонами из пазлов A, B, C и пазлов, полученных из C поворотом на 90 градусов R(C) и пазлов, полученных из A и B поворотами на 180 градусов: D(A), D(B):

D(A)CA; D(A)CAR(C)D(A)CA; D(A)CAR(C)R(C)D(A)BCA


Пазл

22**. Одномерные пазлы (с неограниченным числом поворотов). Описать множество различных цепочек, определяющих полоски с плотно прилегающими сторонами из пазлов A, B, C и пазлов, полученных из них любым числом поворотов на 90 градусов (например, R(R(A)); R(R(R(C))):

R(R(A))CA; R)R((A))CAR(R(R(C)))R(R(A))CR(R(R(R(A))))


24*. Простой XML (постановку задачи уточнить самим):

    <b>text<i>text</i></b>

    
ĉ
Sergey Pozdnyakov,
12 нояб. 2015 г., 15:24
Comments