- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Лексер, парсер. Этапы компиляции. (Часть 1) презентация
Содержание
- 1. Лексер, парсер. Этапы компиляции. (Часть 1)
- 2. Фронтэнд Машинно независимые оптимизации Код генерация + машинно зависимые оптимизации Этапы компиляции
- 3. Лексический анализатор (лексер) Синтаксический анализатор (парсер) Семантический анализатор Генерация промежуточного представления Этапы фронтэнда
- 4. Схема работы Исходный код Лексер
- 5. if (a == b) then
- 6. Лексер формирует последовательности входных символов в лексемы,
- 7. Лексема --
- 8. Обрабатываемые лексером и парсером последовательности символов и
- 9. Алфавит – множество символов, используемых в языке
- 10. Тип 0: неограниченные Тип 1: контекстно-зависимые /
- 11. Регулярные грамматики: праволинейные (A → w, A
- 12. Тип 0 (неограниченные): естественные языки: Русский Английский
- 13. Тип 2 контекстно – свободная грамматика: может
- 14. Строгие определения. Регулярные множества.
- 15. Выражению «(a(b|c))*c» удовлетворяют: с ababacc abacabc Не удовлетворяют: ac abbc abacac Пример регулярного выражения
- 16. Строгие определения. Конечные автоматы.
- 17. Схема построения лексера Лексическая спецификация
- 18. Регулярное Выражение -> НКА
- 19. Регулярное Выражение -> НКА
- 20. Рассмотрим регулярное выражение: Построим соответствующий НКА: Пример
- 21. ε-замыкание(S) — множество состояний, которые достижимы из
- 22. НКА -> ДКА Пример
- 23. Пример построенной диаграммы S com1
- 24. Неполная лексема Конец файла между /* …
- 25. Место выполнения лексического анализатора Схема работы лексического
Слайд 2Фронтэнд
Машинно независимые оптимизации
Код генерация + машинно зависимые оптимизации
Этапы компиляции
Слайд 3Лексический анализатор (лексер)
Синтаксический анализатор (парсер)
Семантический анализатор
Генерация промежуточного представления
Этапы фронтэнда
Слайд 6Лексер формирует последовательности входных символов в лексемы, определяет их тип и
отправляет токены парсеру.
Лексема – минимальная единица языка, имеющая самостоятельный смысл.
Токен – тип лексемы + аттрибут
Парсер формирует исходное выражение языка, запрашивая токены.
Лексема – минимальная единица языка, имеющая самостоятельный смысл.
Токен – тип лексемы + аттрибут
Парсер формирует исходное выражение языка, запрашивая токены.
Схема работы
Слайд 7Лексема --
Токен
12345 (число, 12345)
temp_1 (идентификатор, указатель на симтаб)
+= (оператор, plus_assign)
+ (оператор, plus)
const (ключевое слово, const)
Void (ключевое слово, void)
var_name (идентификатор, указатель на симтаб)
* (оператор, star)
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 | ε
Нетерминальный символ – символ не из алфавита
Цепочка — последовательность символов
Терминальная цепочка – цепочка, состоящая из терминальных символов
Язык – множество терминальных цепочек
Пример грамматики:
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)*)
леволинейные (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 регулярная грамматика:
Может быть описана с помощью конечного автомата
Используется для формирования лексемы лексическим анализатором
Используется для анализа последовательности токенов синтаксическим анализатором
Тип 3 регулярная грамматика:
Может быть описана с помощью конечного автомата
Используется для формирования лексемы лексическим анализатором
Способы разбора грамматик
Слайд 15Выражению «(a(b|c))*c» удовлетворяют:
с
ababacc
abacabc
Не удовлетворяют:
ac
abbc
abacac
Пример регулярного выражения
Слайд 17Схема построения лексера
Лексическая спецификация
Регулярное выражение
Недетерминированный автомат
Детерминированный автомат
Диаграмма состояний
Слайд 21ε-замыкание(S) — множество состояний, которые достижимы из S путём переходов по
ε
Начальное состояние ДКА - ε-замыкание начального состояния НКА
While(есть нерассмотренное состояние ДКА: «cur»)
Для каждого состояния "B1" НКА, входящего в “cur”:
Для каждого перехода “P” из "B" в “B2":
Добавить состояние “new” ε-замыкание(B2)
Добавить переход “cur” -> “new” по P
Конечные состояния ДКА – состояния, содержащие конечные состояния НКА
Начальное состояние ДКА - ε-замыкание начального состояния НКА
While(есть нерассмотренное состояние ДКА: «cur»)
Для каждого состояния "B1" НКА, входящего в “cur”:
Для каждого перехода “P” из "B" в “B2":
Добавить состояние “new” ε-замыкание(B2)
Добавить переход “cur” -> “new” по P
Конечные состояния ДКА – состояния, содержащие конечные состояния НКА
НКА -> ДКА
Слайд 23Пример построенной диаграммы
S
com1
/
IDENTIFIER
NUMBER
com2
!
+=
temp
!=
++
+
“STRING”
ERROR
Буква
Цифра
“
“
Буква, цифра
Цифра
Буква
EOF
EOF
*
*/
/
EOL
/
+
!
=
=
+
“ “
Слайд 24Неполная лексема
Конец файла между /* … */
Конец файла внутри строки в
кавычках
Буквенный символ в цифровой константе: 123q
Некорректный символ: @
Буквенный символ в цифровой константе: 123q
Некорректный символ: @
Ошибки находящиеся лексером
Слайд 25Место выполнения лексического анализатора
Схема работы лексического анализатора
Какие ошибки обрабатываются лексическим анализатором
Идейная
схема построения лексического анализатора
Предназначение символьной таблицы для лексера
Предназначение символьной таблицы для лексера
Должны быть ясны вопросы:
