Семинар 8. Разбор КС-грамматики

(с предыдущего семинара: парсер 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).