Семинар 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).