Лексер. Парсер. (Часть 2) - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Лексер. Парсер. (Часть 2). Доклад-сообщение содержит 40 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

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

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

Схема работы

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

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

Слайд 7

Описание слайда:

Строгие определения. Грамматики. Алфавит – множество символов, используемых в языке Терминальный символ - символ из алфавита Нетерминальный символ – символ не из алфавита Цепочка — последовательность символов Терминальная цепочка – цепочка, состоящая из терминальных символов Язык – множество терминальных цепочек Пример грамматики: 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)*)

Слайд 10

Описание слайда:

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

Слайд 11

Описание слайда:

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

Слайд 12

Описание слайда:

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

Слайд 13

Описание слайда:

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

Слайд 14

Описание слайда:

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

Слайд 15

Описание слайда:

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

Слайд 16

Описание слайда:

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

Слайд 17

Описание слайда:

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

Слайд 18

Описание слайда:

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

Слайд 19

Описание слайда:

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

Слайд 20

Описание слайда:

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

Слайд 21

Описание слайда:

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

Слайд 22

Описание слайда:

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

Слайд 23

Описание слайда:

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

Слайд 24

Описание слайда:

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

Слайд 25

Описание слайда:

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

Слайд 26

Описание слайда:

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

Слайд 27

Описание слайда:

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

Слайд 28

Описание слайда:

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

Слайд 29

Описание слайда:

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

Слайд 30

Описание слайда:

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

Слайд 31

Описание слайда:

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

Слайд 32

Описание слайда:

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

Слайд 33

Описание слайда:

Пример

Слайд 34

Описание слайда:

Построение Goto Eсли в канонической системе множеств есть переход из Ii в Ij по символу A, то в Goto(Ii, A) мы ставим состояние Ij. После заполнения таблицы полагаем, что во всех пустых ячейках 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

Слайд 36

Описание слайда:

Пример

Слайд 37

Описание слайда:

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

Слайд 38

Описание слайда:

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

Слайд 39

Описание слайда:

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

Слайд 40

Описание слайда:

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