Семинар 8. Разбор КС-грамматики (Алгоритмы и структуры данных, часть 2)

Парсер CYK. Дерево разбора и абстрактное синтаксическое дерево (AST). Задача разбора слова. Однозначность разбора слова, грамматики, языка. Неоднозначный КС-язык {0^n 1^n 2^m 3^m} | {0^n 1^m 2^m 3^n}. Лексический разбор (lexer). Лексемы, интерфейс, пример. Однозначная грамматика для арифметических выражений. Приоритет операций слева направо. Унарный минус. Пример дерева разбора и AST (арифм. дерево). Рекурсивный разбор. Функции для нетерминалов и их поведение. Код разбора арифметического выражения. Время работы O(N). Получение AST вместо значения. Левая рекурсия. Устранение. Теория LL-разбора (кратко). Определение k-префиксов (Fi). Идея LL-разбора и определение LL(k) и SLL(k) грамматик. Класс LL(1) = SLL(1). Семинар №8 в курсе “Алгоритмы и структуры данных, часть 2“, весна 2018 (Новосибирск) Преподаватели курса: Александр Александрович Стененко, Степан Юрьевич Гатилов Страница лекции на сайте CS центра: Все видео курса по порядку: