Семинар 8. Разбор КС-грамматики
Суббота, 13 апреля 2019
НГУ, ауд. 1155, НГУ, новый корпус
(с предыдущего семинара: парсер 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).