Семинар 8. Разбор КС-грамматики
Понедельник, 04 апреля 2022
НГУ, ауд. 1156, НГУ, новый корпус
Дерево разбора и абстрактное синтаксическое дерево (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(1) = SLL(1).