Лексер, парсер. Этапы компиляции. (Часть 1) презентация

Содержание

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

Слайд 1Лексер + Парсер. Часть 1.

Илья Филиппов
21.09.2015

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

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

Слайд 4
Схема работы
Исходный код
Лексер
Парсер
Символьная таблица

Токен
Следующий

Семантический
анализ

Слайд 5if (a == b) then
a += 5;

else
a -= 5;

if (a == b) then\n\ta += 5;\nelse\n\ta-=5;

Исходный код

Слайд 6Лексер формирует последовательности входных символов в лексемы, определяет их тип и

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

Схема работы

Слайд 7Лексема --

Токен
12345 (число, 12345)
temp_1 (идентификатор, указатель на симтаб)
+= (оператор, plus_assign)
+ (оператор, plus)
const (ключевое слово, const)
Void (ключевое слово, void)
var_name (идентификатор, указатель на симтаб)
* (оператор, star)

Примеры лексем и токенов

Слайд 8Обрабатываемые лексером и парсером последовательности символов и токенов напрямую зависят от

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

Схема работы

Слайд 9Алфавит – множество символов, используемых в языке
Терминальный символ - символ из

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

Строгие определения. Грамматики.

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

праволинейные/леволинейные

Классификация грамматик по Хомскому

Слайд 11Регулярные грамматики:
праволинейные (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)*)

Строгие определения. Типы грамматик.

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

(регулярные): описание отдельных лексем в языках программирования:
Идентификатор
Числовая константа

Соответствие языков и грамматик

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

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

Способы разбора грамматик

Слайд 14Строгие определения. Регулярные множества.

Слайд 15Выражению «(a(b|c))*c» удовлетворяют:
с
ababacc
abacabc
Не удовлетворяют:
ac
abbc
abacac
Пример регулярного выражения

Слайд 16
Строгие определения. Конечные автоматы.

Слайд 17Схема построения лексера
Лексическая спецификация


Регулярное выражение


Недетерминированный автомат


Детерминированный автомат


Диаграмма состояний

Слайд 18
Регулярное Выражение -> НКА

Слайд 19
Регулярное Выражение -> НКА

Слайд 20Рассмотрим регулярное выражение:


Построим соответствующий НКА:
Пример

Слайд 21ε-замыкание(S) — множество состояний, которые достижимы из S путём переходов по

ε

Начальное состояние ДКА - ε-замыкание начального состояния НКА

While(есть нерассмотренное состояние ДКА: «cur»)
Для каждого состояния "B1" НКА, входящего в “cur”:
Для каждого перехода “P” из "B" в “B2":
Добавить состояние “new” ε-замыкание(B2)
Добавить переход “cur” -> “new” по P

Конечные состояния ДКА – состояния, содержащие конечные состояния НКА

НКА -> ДКА

“new” по PКонечные состояния ДКА – состояния, содержащие конечные состояния НКАНКА -> ДКА">

Слайд 22
НКА -> ДКА Пример

Слайд 23Пример построенной диаграммы

S
com1
/
IDENTIFIER
NUMBER
com2
!
+=
temp
!=
++
+
“STRING”
ERROR
Буква
Цифра
“
“
Буква, цифра
Цифра
Буква
EOF
EOF
*
*/
/
EOL
/
+
!
=
=
+
“ “

Слайд 24Неполная лексема
Конец файла между /* … */
Конец файла внутри строки в

кавычках
Буквенный символ в цифровой константе: 123q
Некорректный символ: @

Ошибки находящиеся лексером

Слайд 25Место выполнения лексического анализатора
Схема работы лексического анализатора
Какие ошибки обрабатываются лексическим анализатором
Идейная

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

Должны быть ясны вопросы:

Похожие презентации

Кодирование информации 280
Классификация моделей 217
Введение в проектирование. Основные понятия проектирования. (Лекция 1) 834
Формирование и реализация моделей сетевого взаимодействия образовательных организаций 331
Основы веб-программирования. Лекция 2 289
OOP with C#. Introduction C#. Data Types. Variables, expressions, statements. C# decision and iteration constructs 303

Обратная связь

Если не удалось найти и скачать презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.

Для правообладателей

Яндекс.Метрика