• Общая информация
• Новости
• Преподаватели
• Мероприятия
• Контакты
• Полезные ссылки

"Лингвистические основы информатики" Направл.: Математика и компьютерные науки (лекции и практики)

Семестр VII, направление Математика и компьютерные науки, отчетность - ЭКЗАМЕН

Учебные пособия

А.П.Замятин, А.М.Шур. Языки, грамматики, распознаватели

Баллы

Баллы по текущей лекционной аттестации находятся [/ ЗДЕСЬ]

Баллы по текущей аттестации по практике (посещаемость и активность) группы МЕН-410203 находятся ЗДЕСЬ

Баллы по текущей аттестации по практике (посещаемость и активность) группы МЕН-410204 находятся ЗДЕСЬ

Баллы по домашним и контрольным работам по практике группы МЕН-410203 находятся ЗДЕСЬ

Баллы по домашним и контрольным работам по практике группы МЕН-410204 находятся ЗДЕСЬ

Утвержденная рабочая программа дисциплины находится Странице

Online-курс находится на elearn.urfu по ССЫЛКЕ

Это в перспективе:

• Способ реализации: в случае очного формата - лекция в аудитории с использованием проектора, в случае гибридного или дистанционного формата: Собрание с использованием BBB в курсе "Лингвистические основы информатики" на elearn (в Moodle) (демонстрация и комментирование презентации лектором; сопровождение записями лектора и студентов на виртуальной доске Idroo, обязательная запись собрания);
• В течение семестра назначается Домашняя работа, а также проводится Контрольная работа в виде Заданий или тестов в курсе на elearn.
• В конце курса - тест на добор баллов;
• 1 раз за курс - проверка Глоссария через игровые элементы Moodle.

Лекции (34ч)

Лекции-презентации находятся ЗДЕСЬ

Лекция 1-2. LR(0)-автомат. LR(0)-грамматика. Анализатор на основе LR(0)-автомата

Лекция 3. SLR(1)-анализатор. SLR(1)-грамматика

Лекция 4. LR(1)-автомат, LR(1)-анализатор, LR(1)-грамматика

Лекция 5. Гибридный метод построения LR-автомата. LALR(1)-грамма

Лекция 6. Основная теорема LR анализа

Лекция 7. LR(k)-автомат. LR(k)-грамматики. LR-язык

Лекция 8. Семантический анализ. Атрибутная грамматика

Лекция 9. Граф зависимости в атрибутной грамматике. Синтаксическое дерево и даг в операторной грамматике

Лекция 10. Вычисление атрибутов, совмещенное с LR-анализом (восходящий анализ)

Практики (17ч)

• Способ реализации: решение задач по плану из учебного пособия А.П.Замятин, А.М.Шур. Языки, грамматики, распознаватели, предлагаемых преподавателем;
• в случае очного формата: решение задач на виртуальной доске Idroo с использованием проектора или на меловой доске;
• в случае гибридного формата: решение задач на виртуальной доске Idroo с использованием проектора или на меловой доске (для тех студентов, кто присутствует оффлайн) и трансляция доски Idroo через Собрание с использованием BBB в курсе "Лингвистические основы информатики" на elearn (в Moodle) (для тех студентов, кто присутствует онлайн), производится запись собрания;
• в случае дистанционного формата: решение задач на виртуальной доске Idroo и трансляция доски Idroo через Собрание с использованием BBB в курсе "Лингвистические основы информатики" на elearn (в Moodle) (для всех студентов), производится запись собрания;
• В течение семестра назначаются Домашняя работа 1-8, а также проводится Контрольная работа в виде Заданий в курсе на elearn.
• Возможна сдача работ над ошибками с уведомлением преподавателя через чат в курсе на elearn. в течение недели после проверки.
• Общение и консультации с преподавателем вне занятий проводятся при помощи Форумов или Чатов на elearn или Telegram.
• после занятия доска Idroo сохраняется и кладется в курс на elearn.

Дополнительные задачи

Практика 1. Восходящий анализ. Грамматики ПП, СП. Операторные грамматики. 10.09.2024.
Задача №8 стр. 152, написать протокол разбора цепочки [a;a].
Задача: написать таблицу приоритета для грамматики арифметических выражений S->S+S|S*S|(S)|x, написать обработчик ошибок, написать протокол разбора цепочки x+x*x.
Домашнее задание №1: №1(а) стр 151 (+ правосторонний вывод слова cacbacb), №9(в) стр 152 (+правосторонний вывод цепочки x or x and not x+обработчик ошибок+найти и исправить ошибки в любой неправильной цепочке (по выбору студента), доказать, что грамматика неоднозначна.
Дедлайн: 23:00 7/10/2024.

Практика 2. LR – анализ. LR(0)-автомат, LR(0)-грамматика, таблица LR(0)-анализатора.
Задачи №1(a) стр.182, написать управляющую таблицу и разбор цепочки [a;a], №1(в) стр.182. Дополнительно: доказать однозначность грамматики из №1(a) стр.182.
Домашнее задание №2: №9(а) стр 152, написать протокол разбора цепочки (x+x)*.x, написать обработчик ошибок, найти и исправить ошибки в цепочке (x+xx ; №1(б) стр 182, написать таблицу LR(0) анализатора и протокол разбора любой цепочки языка грамматики.
Дедлайн: 23:00 7/10/2024.

Практика 3. SLR(1) грамматика, таблица SLR(1)-анализатора.
Задачи №2(б) стр. 182 + таблица SLR(1)-анализатора, протокол разбора цепочки acdbcb.
Домашнее задание №3: Задача №2(a) стр.182, таблица SLR(1)-анализатора, протокол разбора цепочки из языка, допускаемого грамматикой, по выбору студента.
Дедлайн: 23:00 21/10/2024.

Практика 4. LR(1)-автомат, LALR(1)-автомат, LALR-грамматика.
Задачи: №3 стр.182, №4 стр.182, построить таблицу LR(1)-анализатора и протокол разбора цепочки bdc, доказать неоднозначность грамматики S->SS|[S]|[]. Доказать, что она не LR(0), SLR(1), LR(1)-грамматика. Устранить конфликт при помощи левоассоциативности a;a;a=(a;a);a, написать обработчик ошибок и протокол выявления ошибок в цепочке a[aa]]. Или устранить неоднозначность в грамматике S->not S|(S)|S and S|S or S, при помощи приоритета операций, левоассоциативности and, or и правоассициативности not, написать обработчик ошибок. Написать протокол разбора допуска цепочки x or not x and x и протокол поиска oшибок в цепочке x or not and x )
Домашнее задание №4: Домашняя контрольная.
Дедлайн: 23:00 4/11/2024.

Практика 5. Семантический анализ. Атрибутные грамматики.
Задача LOI1, задача №3 стр. 198, построить аннотированное дерево и топографически отсортированный граф зависимости для цепочки w=1011, задача 2* стр. 198, построить аннотированное дерево вывода для регулярного выражения a.(a+b.b)*
Домашнее задание №5:
Задача 1: №1 стр. 198.
Задача 2: Построить атрибутную грамматику, вычисляющую max вложимость скобок в однозначной грамматике арифметических выражений:
E->E+T, T->T*F, E->T, T->F, F->(E), F->x.
(A.rec - max вложимость скобок выражение, выводимое из A). Построить аннотируемое дерево вывода цепочки (x)*((x)) и топографически отсортированный граф зависимости.
Задача 3: Построить атрибутную грамматику, вычисляющую десятичное значение двоичного числа А.B (A, B - двоичные числа) с плавающей точкой (без знака). Подсказка: использовать атрибут A.val - десятичное значение целого двоичного числа A и атрибут B.val - десятичное значение дробной части 0.B. построить аннотированное дерево и топографически отсортированный граф зависимости для цепочки w=10.0111.
Дедлайн: 23:00 18/11/2024.

Практика 6.
Устранение левой рекурсии. Совмещение нисходящего и восходящего анализа, синтаксического и семантического анализа.
Дано: G – КС-грамматика для чисел в двоичной форме без знака с целой и дробной частью.
P = {S ->A,B | ,B | A; A -> A1 | A0 | 1; B -> 1B | 0B |1 }.
1) Составить таблицу соответствия атрибутной грамматики с двумя атрибутами:
.por “порядок двоичной дроби”;
.val “десятичное значение двоичной дроби”.
2) Построить аннотированное дерево вывода для слова w = 10,101.
3) Преобразовать грамматику, левофакторизовав ее устранив левую рекурсию
4). Записать новую атрибутную грамматику в виде схемы трансляции.
5). В новой грамматике построить аннотированное дерево нисходящего вывода для слова w = 10,101.
6). Построить рекурсивные функции для нетерминалов схемы трансляции в новой грамматике.
7). Написать протокол с использованием этих рекурсивных функций для разбора цепочки w = 10,101.
Указание:
A.por - номер позиции самого левого символа, который выводится из A.
S.por - номер позиции самого левого символа, который выводится из целой части.
B.por - номер позиции самого правого символа, который выводится из 0,B
Например, если A =>* 1001, то A.por=3, если S =>* 1001,101, то S.por=3, если B =>* 0,101, то S.por=-3
Домашнее задание:
Дано: G – КС-грамматика формул логики высказываний в ДНФ без отрицаний.
P = {S -> C |S V C, C -> x | C & L, L -> x}.
1) Составить таблицу соответствия атрибутной грамматики с одним атрибутом:
.val “логическое выражение от переменной x”.
2) Построить аннотированное дерево вывода для произвольной цепочки w данного языка (по выбору студента).
3) Преобразовать грамматику, левофакторизовав ее (если это необходимо) и устранив левую рекурсию 4). Записать новую атрибутную грамматику в виде схемы трансляции.
5). В новой грамматике построить аннотированное дерево нисходящего вывода для слова w', полученного из слова w заменой различные вхождения x на булевы переменные, например, если x=xVx&x, то в качестве w' можно взять 0V0&1.
6). Построить рекурсивные функции для нетерминалов схемы трансляции в новой грамматике.
7). Написать протокол с использованием этих рекурсивных функций для разбора цепочки w'.
Дедлайн: 23:00 20/12/2024.

Практика 7.
Задачи
Дедлайн: 23:00 16/12/2024.

Практика 8.
Задачи

В перспективе

Техкарта БРС: 0,3*Текущ.лекц.атт.+0,7*(0,4*Текущ.практ.атт.+0,6*Промеж.практ.атт.(зачет))

Текущ.лекций=Работа на занятии (посещ. и активн.) (20б.)+Домашняя работа (40б)(тесты)+Контрольная работа(тесты)(40б.)

Текущ.практ.=Посещ.и активн.(20б.)+Домашняя работа 1 (20б.)+Домашняя работа 2(20б)+Контрольная работа (40б.).

Предварительная дата экзамена:

См. также

Нагребецкая Ю.В.