"Лингвистические основы информатики" Направл.: Математика и компьютерные науки (лекции и практики)
Последнее изменение: 16/09/2025 15:26:05Семестр VII, направление Математика и компьютерные науки, отчетность - ЭКЗАМЕН
Учебные пособия
А.П.Замятин, А.М.Шур. Языки, грамматики, распознаватели
Утвержденная рабочая программа дисциплины находится Странице
- Способ реализации: в случае очного формата - лекция в аудитории с использованием проектора, в случае гибридного или дистанционного формата: Собрание с использованием BBB в курсе "Лингвистические основы информатики" на elearn (в Moodle) (демонстрация и комментирование презентации лектором; сопровождение записями лектора и студентов на виртуальной доске, обязательная запись собрания);
- В течение семестра на лекциях назначается Домашняя работа, а также проводится Контрольная работа в виде тестов и Заданий в курсе на elearn, на практиках - назначается Домашняя работа и Контрольная работы на elearn.
- Собираются и оцениваются конспекты лекций и практик
Лекции (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-анализом (восходящий анализ)
Лекция 11. Восходящий анализ с маркером
Лекция 12. Проверка семантической корректности программы, общие сведения. Выражения типа
Лекция 13. Атрибутная грамматика проверки типов данных в программе.
Лекция 14. Полиморфизм.
Практики (17ч)
- Способ реализации: решение задач по плану из учебного пособия А.П.Замятин, А.М.Шур. Языки, грамматики, распознаватели, предлагаемых преподавателем;
- в случае очного формата: решение задач на меловой доске;
- в случае гибридного формата: решение задач на виртуальной доске с использованием проектора или на меловой доске (для тех студентов, кто присутствует оффлайн) и трансляция доски через Собрание с использованием BBB в курсе "Лингвистические основы информатики" на elearn (в Moodle) (для тех студентов, кто присутствует онлайн), производится запись собрания;
- в случае дистанционного формата: решение задач на виртуальной доске и трансляция доски через Собрание с использованием BBB в курсе "Лингвистические основы информатики" на elearn (в Moodle) (для всех студентов), производится запись собрания;
- В течение семестра назначаются Домашняя работа 1-8, а также проводится Контрольная работа в виде Заданий в курсе на elearn.
- Возможна сдача работ над ошибками с уведомлением преподавателя через чат в курсе на elearn в течение недели после проверки.
- Общение и консультации с преподавателем вне занятий гибридного или дистанционного форматов проводятся при помощи Форумов или Чатов на elearn.
Дополнительные задачи
Практика 1. Восходящий анализ. Грамматики ПП, СП. Операторные грамматики. 2.09.2025. Задача №8 стр. 152, написать протокол разбора цепочки [a;a].
Задача: написать таблицу приоритета для грамматики выражений логики высказываний, написать обработчик ошибок, написать протокол разбора правильной цепочки, и разбор неправильной цепочки, доказать, что грамматика неоднозначна.
Домашнее задание №1: №1(а) стр 151 (+ правосторонний вывод слова cacbacb), №9(в) стр 152 ((+ правосторонний вывод слова cacbacb), №9(г) стр 152 (можно Cи), таблицу приоритетов многочленов Жегалкина (+правосторонний вывод правильной цепочки + обработчик ошибок + найти и исправить ошибки в любой неправильной цепочке (по выбору студента), доказать, что грамматика неоднозначна. Дедлайн: 23:00 15/09/2025.
Практика 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. Семантический анализ. Атрибутные грамматики.
Задача 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.
Домашнее задание №5:
Задача LOI1, задача №3 стр. 198, построить аннотированное дерево и топографически отсортированный граф зависимости для цепочки w=1011, задача 2* стр. 198, построить аннотированное дерево вывода для регулярного выражения a.(a+b.b)*
Дедлайн: 23:00 18/11/2024.
Практика 6.
Устранение левой рекурсии. Совмещение нисходящего и восходящего анализа, синтаксического и семантического анализа.
Дано: G – КС-грамматика для чисел в двоичной форме без знака с целой и дробной частью.
P = {S ->A,B | 0,B | A | 0; 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,4*Текущ.практич.атт.+0,6*(0,4*Текущ.лекц.атт.+0,6*Промеж.лекц.атт.(экзамен))
Текущ.лекц.аттестация
1) Работа на лекции (30 баллов)
- Активность (10 баллов)
- Тесты на лекции (10 баллов)
- Проверка конспектов лекций (10 баллов с учетом тестов на лекции) (10 баллов)
2) Домашняя работа (тест №1) (35б)
3) Контрольная работа (тест №2)(35б.)
Текущ.практ.аттестация
1) Активность (10 баллов)
2) Проверка конспектов практик (10 баллов, с учетом посещаемости)
3) Домашняя работа (40 баллов)
4) Контрольная работа (40 баллов)
Предварительная дата экзамена:
См. также