🗊Презентация Лексер. Парсер. (Часть 2)

Лексер + Парсер. Часть 2. Илья Филиппов 05.10.2015

Этапы компиляции Фронтэнд Машинно независимые оптимизации Код генерация + машинно зависимые оптимизации

Этапы фронтэнда Лексический анализатор (лексер) Синтаксический анализатор (парсер) Семантический анализатор Генерация промежуточного представления

Схема работы

Схема работы Лексер формирует последовательности входных символов в лексемы и отправляет токены парсеру. Лексема – минимальная единица языка, имеющая самостоятельный смысл. Токен – тип лексемы + аттрибут Парсер формирует исходное выражение языка, запрашивая токены.

Схема работы Обрабатываемые лексером и парсером последовательности символов и лексем напрямую зависят от спецификации языка. Необходим способ описания «что в языке может быть» «что в языке не может быть»

Строгие определения. Грамматики. Алфавит – множество символов, используемых в языке Терминальный символ - символ из алфавита Нетерминальный символ – символ не из алфавита Цепочка — последовательность символов Терминальная цепочка – цепочка, состоящая из терминальных символов Язык – множество терминальных цепочек Пример грамматики: S->aQbZ Q->ab | cc | Qd Z -> aQa | c | ε

Классификация грамматик по Хомскому Тип 0: неограниченные Тип 1: контекстно-зависимые / неукорачивающие Тип 2: контекстно-свободные Тип 3: регулярные: праволинейные/леволинейные

Строгие определения. Типы грамматик. Регулярные грамматики: праволинейные (A → w, A → wB, A,B ∈ N, w ∈ T*) леволинейные (A → w, A → Bw, A,B ∈ N, w ∈ T*) Контекстно-свободные грамматики: (A → w, A ∈ N, w ∈ (T U N)*)

Соответствие языков и грамматик Тип 0 (неограниченные): естественные языки: Русский Английский Тип 2 (контекстно-свободные): большинство языков программирования: Java С++ Тип 3: (регулярные): описание отдельных лексем в языках программирования: Идентификатор Числовая константа

Способы разбора грамматик Тип 2 контекстно – свободная грамматика: может быть описана с помощью конечного автомата с магазинной памятью Используется для анализа последовательности токенов синтаксическим анализатором Тип 3 регулярная грамматика: Может быть описана с помощью конечного автомата Используется для формирования лексемы лексическим анализатором

Строгие определения. Конечные автоматы с магазинной памятью. Недетерминированный Детерминированный

Варианты синтаксического анализа Нисходящий анализ Метод рекурсивного спуска (парсер с возвратом) Предиктивный анализатор (предсказывающий анализатор) (LL анализатор) Восходящий анализ (LR анализатор)

Дерево разбора id + id * id

Метод рекурсивного спуска Дерево разбора строится сверху вниз, слева направо Токены от лексера рассматриваются в порядке поступления

Метод рекурсивного спуска Каждому нетерминалу соответствует процедура, в которую жёстко зашиты продукции данного нетерминала Процедура последовательно сравнивает пришедшие токены с терминалами продукций Если ни одна продукция не подходит – ошибка Если встречается нетерминал управление переходит в процедуру нетерминала

Пример применения метода рекурсивного спуска

Рекурсивный спуск, минусы Грамматика жёстко зашита в алгоритм. В последующих алгоритмах на основании грамматики строятся таблицы Алгоритм выполняется за экспоненциальное время Алгоритм может зацикливаться Использование неявного стека

Предиктивный анализатор Идея – убрать откатывание. По каждому символу должно быть изначально ясно куда переходим. Преобразование грамматики Удаление левой рекурсии Левая факторизация Вычисление множеств FIRST FOLLOW Составление таблицы

Предиктивный анализатор Удаление левой рекурсии Левая факторизация

Предиктивный анализатор Пример преобразования грамматики:

Предиктивный анализатор Определение множества FIRST FIRST(a), a∈(N⋃T)* - множество терминалов или ℇ, с которых может начинаться а. Построение множества FIRST

Предиктивный анализатор Определение множества FOLLOW FOLLOW(A), A∈N – множества терминалов, которые могут появиться сразу за А, включая концевой маркер $ Построение множества FOLLOW

Предиктивный анализ Пример построения FIRST, FOLLOW

Предиктивный анализ Построение таблицы

Предиктивный анализ Пример построения таблицы

Предиктивный анализ, разбор

Предиктивный анализ, пример

Восходящий анализатор Строим дерево разбора начиная с листьев Для большинства языков программирования можно построить LR грамматику Наиболее общий метод анализа без отката Существуют генераторы LR анализаторов

Построение LR(1) анализатора 1. Пополнение грамматики 2. Построение канонической системы множеств допустимых LR(1)-ситуаций 3. Построение таблицы анализатора 3.1 Построение таблицы Goto 3.2 Построение таблицы Actions 4. Разбор цепочки

Пополнение грамматики Добавим новое правило S' → S, и сделаем S' аксиомой грамматики. Допуск имеет место  когда возможно осуществить свёртку по правилу S → S'.

Каноническая система множеств Вначале имеется множество I0 с конфигурацией анализатора S' → .S, $ К этой конфигурации применяется операция закрытия до тех пор, пока в результате её применения не перестанут добавляться новые конфигурации. Строятся переходы в новые множества путём сдвига точки на один символ вправо

Пример

Построение Goto Eсли в канонической системе множеств есть переход из Ii в Ij по символу A, то в Goto(Ii, A) мы ставим состояние Ij. После заполнения таблицы полагаем, что во всех пустых ячейках Goto(Ii, A) = Error После заполнения таблицы полагаем, что во всех пустых ячейках Goto(Ii, A) = Error

Построение action Если есть переход по терминалу a из состояния Ii в состояние Ij, то Action(Ii, a) = Shift(Ij) Если A ≠ S' и есть конфигруация A → α., a, то Action(Ii, a) = Reduce(A → α) Для состояния Ii, в котором есть конфигурация S' → S., $, Action(Ii, $) = Accept Для всех пустых ячеек Action(Ii, a) = Error

Пример

Восходящий анализ, разбор

Восходящий анализ, пример

Обрабатываемые ошибки Баланс скобок {…{…(…)…(((…))…)…}…(…}…} Верность выражений “+” между expr

Должны быть ясны вопросы: Место выполнения синтаксического анализатора Нисходящий анализ Метод рекурсивного спуска Предиктивный анализатор Восходящий анализ