- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Лексер. Парсер. (Часть 2) презентация
Содержание
- 1. Лексер. Парсер. (Часть 2)
- 2. Фронтэнд Машинно независимые оптимизации Код генерация + машинно зависимые оптимизации Этапы компиляции
- 3. Лексический анализатор (лексер) Синтаксический анализатор (парсер) Семантический анализатор Генерация промежуточного представления Этапы фронтэнда
- 4. Схема работы Исходный код Лексер
- 5. Лексер формирует последовательности входных символов в лексемы
- 6. Обрабатываемые лексером и парсером последовательности символов и
- 7. Алфавит – множество символов, используемых в языке
- 8. Тип 0: неограниченные Тип 1: контекстно-зависимые /
- 9. Регулярные грамматики: праволинейные (A → w, A
- 10. Тип 0 (неограниченные): естественные языки: Русский Английский
- 11. Тип 2 контекстно – свободная грамматика: может
- 12. Недетерминированный Детерминированный Строгие определения. Конечные автоматы с магазинной памятью.
- 13. Нисходящий анализ Метод рекурсивного спуска (парсер с
- 14. id + id * id Дерево разбора
- 15. Дерево разбора строится сверху вниз, слева направо
- 16. Каждому нетерминалу соответствует процедура, в которую жёстко
- 17. Пример применения метода рекурсивного спуска
- 18. Грамматика жёстко зашита в алгоритм. В последующих
- 19. Идея – убрать откатывание. По каждому символу
- 20. Удаление левой рекурсии Левая факторизация Предиктивный анализатор
- 21. Пример преобразования грамматики: Предиктивный анализатор
- 22. Определение множества FIRST FIRST(a), a∈(N⋃T)* - множество
- 23. Определение множества FOLLOW FOLLOW(A), A∈N – множества
- 24. Пример построения FIRST, FOLLOW Предиктивный анализ
- 25. Построение таблицы Предиктивный анализ
- 26. Пример построения таблицы Предиктивный анализ
- 27. Предиктивный анализ, разбор
- 28. Предиктивный анализ, пример
- 29. Строим дерево разбора начиная с листьев Для
- 30. Построение LR(1) анализатора 1. Пополнение грамматики 2.
- 31. Пополнение грамматики Добавим новое правило S' →
- 32. Каноническая система множеств Вначале имеется множество I0 с
- 33. Пример
- 34. Построение Goto Eсли в канонической системе множеств
- 35. Построение action Если есть переход по терминалу
- 36. Пример
- 37. Восходящий анализ, разбор
- 38. Восходящий анализ, пример
- 39. Баланс скобок {…{…(…)…(((…))…)…}…(…}…} Верность выражений “+” между expr Обрабатываемые ошибки
- 40. Место выполнения синтаксического анализатора Нисходящий анализ Метод
Фронтэнд Машинно независимые оптимизации Код генерация + машинно зависимые оптимизации Этапы компиляции
Слайд 2Фронтэнд
Машинно независимые оптимизации
Код генерация + машинно зависимые оптимизации
Этапы компиляции
Слайд 3Лексический анализатор (лексер)
Синтаксический анализатор (парсер)
Семантический анализатор
Генерация промежуточного представления
Этапы фронтэнда
Слайд 5Лексер формирует последовательности входных символов в лексемы и отправляет токены парсеру.
Лексема
– минимальная единица языка, имеющая самостоятельный смысл.
Токен – тип лексемы + аттрибут
Парсер формирует исходное выражение языка, запрашивая токены.
Токен – тип лексемы + аттрибут
Парсер формирует исходное выражение языка, запрашивая токены.
Схема работы
Слайд 6Обрабатываемые лексером и парсером последовательности символов и лексем напрямую зависят от
спецификации языка.
Необходим способ описания
«что в языке может быть»
«что в языке не может быть»
Необходим способ описания
«что в языке может быть»
«что в языке не может быть»
Схема работы
Слайд 7Алфавит – множество символов, используемых в языке
Терминальный символ - символ из
алфавита
Нетерминальный символ – символ не из алфавита
Цепочка — последовательность символов
Терминальная цепочка – цепочка, состоящая из терминальных символов
Язык – множество терминальных цепочек
Пример грамматики:
S->aQbZ
Q->ab | cc | Qd
Z -> aQa | c | ε
Нетерминальный символ – символ не из алфавита
Цепочка — последовательность символов
Терминальная цепочка – цепочка, состоящая из терминальных символов
Язык – множество терминальных цепочек
Пример грамматики:
S->aQbZ
Q->ab | cc | Qd
Z -> aQa | c | ε
Строгие определения. Грамматики.
Слайд 8Тип 0: неограниченные
Тип 1: контекстно-зависимые / неукорачивающие
Тип 2: контекстно-свободные
Тип 3: регулярные:
праволинейные/леволинейные
Классификация грамматик по Хомскому
Слайд 9Регулярные грамматики:
праволинейные (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)*)
леволинейные (A → w, A → Bw, A,B ∈ N, w ∈ T*)
Контекстно-свободные грамматики:
(A → w, A ∈ N, w ∈ (T U N)*)
Строгие определения. Типы грамматик.
Слайд 10Тип 0 (неограниченные): естественные языки:
Русский
Английский
Тип 2 (контекстно-свободные): большинство языков программирования:
Java
С++
Тип 3:
(регулярные): описание отдельных лексем в языках программирования:
Идентификатор
Числовая константа
Идентификатор
Числовая константа
Соответствие языков и грамматик
Слайд 11Тип 2 контекстно – свободная грамматика:
может быть описана с помощью конечного
автомата с магазинной памятью
Используется для анализа последовательности токенов синтаксическим анализатором
Тип 3 регулярная грамматика:
Может быть описана с помощью конечного автомата
Используется для формирования лексемы лексическим анализатором
Используется для анализа последовательности токенов синтаксическим анализатором
Тип 3 регулярная грамматика:
Может быть описана с помощью конечного автомата
Используется для формирования лексемы лексическим анализатором
Способы разбора грамматик
Слайд 12 Недетерминированный
Детерминированный
Строгие определения. Конечные автоматы с магазинной памятью.
Слайд 13Нисходящий анализ
Метод рекурсивного спуска (парсер с возвратом)
Предиктивный анализатор (предсказывающий анализатор) (LL
анализатор)
Восходящий анализ (LR анализатор)
Восходящий анализ (LR анализатор)
Варианты синтаксического анализа
Слайд 15Дерево разбора строится сверху вниз, слева направо
Токены от лексера рассматриваются в
порядке поступления
Метод рекурсивного спуска
Слайд 16Каждому нетерминалу соответствует процедура, в которую жёстко зашиты продукции данного нетерминала
Процедура
последовательно сравнивает пришедшие токены с терминалами продукций
Если ни одна продукция не подходит – ошибка
Если встречается нетерминал управление переходит в процедуру нетерминала
Если ни одна продукция не подходит – ошибка
Если встречается нетерминал управление переходит в процедуру нетерминала
Метод рекурсивного спуска
Слайд 18Грамматика жёстко зашита в алгоритм. В последующих алгоритмах на основании грамматики
строятся таблицы
Алгоритм выполняется за экспоненциальное время
Алгоритм может зацикливаться
Использование неявного стека
Алгоритм выполняется за экспоненциальное время
Алгоритм может зацикливаться
Использование неявного стека
Рекурсивный спуск, минусы
Слайд 19Идея – убрать откатывание. По каждому символу должно быть изначально ясно
куда переходим.
Преобразование грамматики
Удаление левой рекурсии
Левая факторизация
Вычисление множеств
FIRST
FOLLOW
Составление таблицы
Преобразование грамматики
Удаление левой рекурсии
Левая факторизация
Вычисление множеств
FIRST
FOLLOW
Составление таблицы
Предиктивный анализатор
Слайд 22Определение множества FIRST
FIRST(a), a∈(N⋃T)* - множество терминалов или ℇ, с которых
может начинаться а.
Построение множества FIRST
Построение множества FIRST
Предиктивный анализатор
Слайд 23Определение множества FOLLOW
FOLLOW(A), A∈N – множества терминалов, которые могут появиться сразу
за А, включая концевой маркер $
Построение множества FOLLOW
Построение множества FOLLOW
Предиктивный анализатор
Слайд 29Строим дерево разбора начиная с листьев
Для большинства языков программирования можно построить
LR грамматику
Наиболее общий метод анализа без отката
Существуют генераторы LR анализаторов
Наиболее общий метод анализа без отката
Существуют генераторы LR анализаторов
Восходящий анализатор
Слайд 30Построение LR(1) анализатора
1. Пополнение грамматики
2. Построение канонической системы множеств допустимых LR(1)-ситуаций
3.
Построение таблицы анализатора
3.1 Построение таблицы Goto
3.2 Построение таблицы Actions
4. Разбор цепочки
3.1 Построение таблицы Goto
3.2 Построение таблицы Actions
4. Разбор цепочки
Слайд 31Пополнение грамматики
Добавим новое правило S' → S, и сделаем S' аксиомой
грамматики.
Допуск имеет место ⬄ когда возможно осуществить свёртку по правилу S → S'.
Допуск имеет место ⬄ когда возможно осуществить свёртку по правилу S → S'.
Слайд 32Каноническая система множеств
Вначале имеется множество I0 с конфигурацией анализатора S' → .S,
$
К этой конфигурации применяется операция закрытия до тех пор, пока в результате её применения не перестанут добавляться новые конфигурации.
Строятся переходы в новые множества путём сдвига точки на один символ вправо
К этой конфигурации применяется операция закрытия до тех пор, пока в результате её применения не перестанут добавляться новые конфигурации.
Строятся переходы в новые множества путём сдвига точки на один символ вправо
Слайд 34Построение Goto
Eсли в канонической системе множеств есть переход из Ii в Ij по символу A,
то в Goto(Ii, A) мы ставим состояние Ij. После заполнения таблицы полагаем, что во всех пустых ячейках Goto(Ii, A) = Error
После заполнения таблицы полагаем, что во всех пустых ячейках Goto(Ii, A) = Error
После заполнения таблицы полагаем, что во всех пустых ячейках Goto(Ii, A) = Error
Слайд 35Построение 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
Если A ≠ S' и есть конфигруация A → α., a, то Action(Ii, a) = Reduce(A → α)
Для состояния Ii, в котором есть конфигурация S' → S., $, Action(Ii, $) = Accept
Для всех пустых ячеек Action(Ii, a) = Error
Слайд 39Баланс скобок {…{…(…)…(((…))…)…}…(…}…}
Верность выражений “+” между expr
Обрабатываемые ошибки
Слайд 40Место выполнения синтаксического анализатора
Нисходящий анализ
Метод рекурсивного спуска
Предиктивный анализатор
Восходящий анализ
Должны быть ясны
вопросы:
