ИДЗ-2 МЛиТА 2012

Языки для описания посредством LL(1) грамматик и конструирование синтаксических анализаторов

МЛиТА, ИДЗ-2, 2012-2013

В каждой группе староста распределяет варианты так, чтобы студенты брали задачи по силам (o - легкие задачи, *-трудные, **-очень трудные). Отчеты о работе размещаются на сайтах студентов. В отчет входят: набор примеров и контрпримеров языка, грамматика, грамматический разбор типичного примера, проверка на однозначность ветвления, модифицированная грамматика (если нужно), синтаксические диаграммы ( в таблице из трех столбиков: правило-диаграмма-замечания), алгоритм синтаксического анализа (в таблице из трех столбиков: правило или диаграмма-оператор на псевдокоде-замечания), код синтаксического анализатора (в таблице из трех столбиков: оператор на псевдокоде-оператор в используемом АЯ-замечания), файлы с исходным кодом и исполняемый файл.

Тема 1. Язык сравнения длинных чисел: первое число пишется слева направо до черты, второе - справа налево до черты. Если первое число больше второго, то запись является правильным словом языка.

Примеры правильных слов языка: 1234|3321, 234|21

Примеры неправильных слов языка: 12|3321, 222|322


Тема 2. Язык правильных скобочных записей: между скобками одной направленности не более двух пробелов, между разными скобками – не менее двух пробелов.

Примеры правильных слов языка: ( ((   )(   )  ), (  )

Примеры неправильных слов языка: ( (  (   )), ((()))

 

Тема 3*. Язык выражений Excel

Примеры правильных слов языка:  =A1*B1     =SUM(A1:C1)   =IF(A1;B1-C1; SUM(B1:C1))

 

Тема 4. Язык логических выражений с отношениями и одной арифметической операцией.

Примеры правильных слов языка: a>b=>c-d     a-(b-c)=d <=> c<d      (a=b)=>(a<c=>c>d)

 

Тема 5o. Язык ударений.

Примеры правильных слов языка: КАРАБА’С-БАРАБА’C   КАА’СА    БА’РАК   БАР А’К

 

Тема 6. Язык дробных выражений без лишних скобок.

Примеры правильных слов языка: -23/(12/(-231)/23/17)

 

Тема 7. Язык нормальных скулемовских форм.

Примеры правильных слов языка: (P(f(x;y);z;g(x;z;g(x)))|Q(x;y))*R(x)*(T(h(u);z)|S(x;y;z))

 

Тема 8. Язык палиндромов-предложений – «перевертышей», читающихся одинаково с разных сторон, как «А роза упала на лапу Азора». Пробелы и знаки препинания игнорируются. Середина палиндрома обозначается чертой, если число букв нечётное, черта стоит справа от буквы.

Примеры правильных слов языка Я НЕ РЕВУ -| УВЕРЕН Я, Я НЕ РЕВУ |- УВЕРЕН Я, А РОЗА УПАЛА Н|А ЛАПУ АЗОРА

 

Тема 8. Язык пунктуации в русской грамматике.

Примеры правильных слов языка: Ааа аааа, аааа. А ааа-ааа аааа: ааа, аааа! 

Примеры неправильных слов языка: АА.   аА. А ааа: ааа: ааа.  Аааа,ааа. Ааааа аааа,

 

Тема 9o. Из кубиков A, B, C, D строится последовательность. Язык состоит из всех записей, которые соответствуют множеству однозвенных и двухзвенных ломаных.

Примеры правильных слов языка: ABABAB     ADDAAB 

Примеры неправильных слов языка: ADBDA   AAABCC

 

Тема 10. Язык формул комбинаторики без лишних скобок и с пропущенным умножением там, где это не создаёт неоднозначности.

Примеры правильных слов языка: (C(20,5)+P(8))/2+5A(7,18) +3*25!/10!!

Примеры неправильных слов языка: C(20)+P(8)   (A(17,8)) +25!   3*С(5;3)

 

Тема 11. Язык числовых выражения с квадратными корнями с одной арифметической операцией сложения и без лишних скобок. Корни обозначаются большой латинской буквой V

Примеры правильных слов языка: VVV37    V(3+V523)  37+15   V(V3+VV5)   V(3+5)

Примеры неправильных слов языка: (3+5)    3+(5+V5)   V  V(3)    34V5

 

Тема 12. Язык алгебраических выражений с логарифмами, одной арифметической операцией умножения и без лишних скобок. Знак операции умножения не пишется между переменными и заменяется пробелом, если один из множителей – выражение с логарифмами.

Примеры правильных слов языка: LOGaBC    LOGabC   LOGaLOGbCD  

LOGa(LOGbCD LOGnF)  LOGa(LOGb(CD LOGnF))

Примеры неправильных слов языка: LOG LOGaB    LOGAB   (LOGaB LOGbC)

 

Тема 13o. Из кубиков A, B, C, D строится последовательность. Язык состоит из всех записей, которые соответствуют множеству монотонных ломаных, каждый из непрерывных кусков которой является монотонным.

Примеры правильных слов языка: BBBCAA    DBBBBBB   AAADADAAD 

Примеры неправильных слов языка: CD    AAAAAAADBBBC

 

Тема 14o. Из кубиков A, B, C, D строится последовательность. Язык состоит из всех записей, описывающих набор «подков».

Примеры правильных слов языка: ABBC    CCCD   CCDBC 

Примеры неправильных слов языка: BA  C    CDA

 

Тема 15o. Из кубиков A, B, C, D строится последовательность. Язык состоит из всех записей, описывающих правильные скобочные выражения, причём скобки не должны соприкасаться.

Примеры правильных слов языка: BBCAA   BCCDCA 

Примеры неправильных слов языка: AB   BA  C  BC   D 

 

Тема 16. Итальянский язык. В фильме «Формула любви» Семён Фарада и Александр Абдулов поют (псевдо)неаполитанскую песню, в которой слова не имеют смысла, но производят ощущение пения на итальянском. Нужно придумать такие правила, которые будут создавать бессмысленные слова, производящие ощущение итальянской речи.

Примеры правильных слов языка:

Mare bella donna,
Che un bel canzone,
Sai, che ti amo, sempre amo.
Donna bella mare,
Credere, cantare,
Dammi il momento,
Che mi piace piu' !
Uno, uno, uno, un momento,
Uno, uno, uno sentimento,
Uno, uno, uno complimento

Sacramento, sacramento, sacramento...

 

Тема 17. Чешский язык. Известно, что в чешском языке могут идти подряд несколько согласных. Также в языке много шипящих. Нужно придумать такие правила, которые будут создавать бессмысленные слова, производящие ощущение чешской речи.

Примеры правильных слов языка: Hráč   Zdravý   přeloženy do českého  plzeňská vstupenka

 

Тема 18. Вьетнамский язык. Известно, что в восточных языках главными образующими слов являются гласные, а не согласные, к чему мы привыкли в европейских языках. Нужно придумать такие правила, которые будут создавать бессмысленные слова, производящие ощущение вьетнамской речи.

Примеры правильных слов языка: Thì hiện tại hoàn thành tiếp diễn và hiện tại hoàn thành.

 

Тема 19. Язык записи квадратных уравнений в каноническом виде.

Примеры правильных слов языка: x^2-512=0     234x^2+x=0   -x^2-23x+2=0

Примеры неправильных слов языка: -1 x^2-23=0    x^2+-23x+5=0    x^2+0x-33=0

 

Тема 20*. Язык SVG (от англ. Scalable Vector Graphics – язык масштабируемой векторной графики) – язык разметки масштабируемой векторной графики, созданный Консорциумом Всемирной паутины (W3C) и входящий в подмножество расширяемого языка разметки XML, предназначен для описания двумерной векторной и смешанной векторно/растровой графики в формате XML.

 

Тема 21**. Язык запросов SQL SELECT

Примеры правильных слов языка:

SELECT ‘Максимальный личный шифр ‘||eid||’ имеет сотрудник ‘||sname||’ ‘||SUBSTR(fname, 0, 1)||’. ‘||SUBSTR(otch, 0, 1)||’.’ As Максимальный_личный_шифр FROM employees WHERE eid = (SELECT MAX(eid) from employees);

SELECT CONCAT(CONCAT(CONCAT(‘Сотрудник ‘, sname), CONCAT(SUBSTR(fname, 0, 1), SUBSTR(otch, 0, 1))), CONCAT(‘принят на работу ‘, acceptdate)) FROM employees WHERE acceptdate > to_date(’01.01.80′,’dd.mm.yyyy’);

Comments