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

Сентябрь 7, 2022

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

Содержание

2. Фронтэнд Машинно независимые оптимизации Код генерация + машинно зависимые оптимизации Этапы компиляции
3. Лексический анализатор (лексер) Синтаксический анализатор (парсер) Семантический анализатор Генерация промежуточного представления Этапы фронтэнда
4. Схема работы Исходный код Лексер Парсер Символьная таблица Токен Следующий Семантический анализ
5. if (a == b) then a += 5; else a -= 5; if (a == b)
6. Лексер формирует последовательности входных символов в лексемы, определяет их тип и отправляет токены парсеру. Лексема –
7. Лексема -- Токен 12345 (число, 12345) temp_1 (идентификатор, указатель на симтаб) += (оператор, plus_assign) + (оператор,
8. Обрабатываемые лексером и парсером последовательности символов и токенов напрямую зависят от спецификации языка. Необходим способ описания
9. Алфавит – множество символов, используемых в языке Терминальный символ - символ из алфавита Нетерминальный символ –
10. Тип 0: неограниченные Тип 1: контекстно-зависимые / неукорачивающие Тип 2: контекстно-свободные Тип 3: регулярные: праволинейные/леволинейные Классификация
11. Регулярные грамматики: праволинейные (A → w, A → wB, A,B ∈ N, w ∈ T*) леволинейные
12. Тип 0 (неограниченные): естественные языки: Русский Английский Тип 2 (контекстно-свободные): большинство языков программирования: Java С++ Тип
13. Тип 2 контекстно – свободная грамматика: может быть описана с помощью конечного автомата с магазинной памятью
14. Строгие определения. Регулярные множества.
15. Выражению «(a(b|c))*c» удовлетворяют: с ababacc abacabc Не удовлетворяют: ac abbc abacac Пример регулярного выражения
16. Строгие определения. Конечные автоматы.
17. Схема построения лексера Лексическая спецификация Регулярное выражение Недетерминированный автомат Детерминированный автомат Диаграмма состояний
18. Регулярное Выражение -> НКА
19. Регулярное Выражение -> НКА
20. Рассмотрим регулярное выражение: Построим соответствующий НКА: Пример
21. ε-замыкание(S) — множество состояний, которые достижимы из S путём переходов по ε Начальное состояние ДКА -
22. НКА -> ДКА Пример
23. Пример построенной диаграммы S com1 / IDENTIFIER NUMBER com2 ! += temp != ++ + “STRING”
24. Неполная лексема Конец файла между /* … */ Конец файла внутри строки в кавычках Буквенный символ
26. Скачать презентацию

Слайд 2

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

Слайд 3

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

Слайд 4

Схема работы
Исходный код
Лексер
Парсер
Символьная таблица
Токен
Следующий
Семантический
анализ

Слайд 5

if (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
Конечные состояния ДКА – состояния, содержащие конечные состояния НКА

НКА -> ДКА

Слайд 22

НКА -> ДКА Пример

Слайд 23

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

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

Слайд 24

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

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

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

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

Содержание

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

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

Схема работыИсходный кодЛексерПарсерСимвольная таблицаТокенСледующийСемантическийанализ

if (a == b) then a += 5; else a -=

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

Лексема -- Токен12345 (число, 12345)temp_1 (идентификатор, указатель на симтаб)+= (оператор, plus_assign)+ (оператор,

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

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

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

Регулярные грамматики:праволинейные (A → w, A → wB, A,B ∈ N,

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

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

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

Выражению «(a(b|c))*c» удовлетворяют:сababaccabacabcНе удовлетворяют:acabbcabacacПример регулярного выражения

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

Схема построения лексераЛексическая спецификацияРегулярное выражениеНедетерминированный автоматДетерминированный автоматДиаграмма состояний

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

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

Рассмотрим регулярное выражение:Построим соответствующий НКА:Пример

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

НКА -> ДКА Пример

Пример построенной диаграммы Scom1/IDENTIFIERNUMBERcom2!+=temp!=+++“STRING”ERRORБукваЦифра““Буква, цифраЦифраБукваEOFEOF**//EOL/+!==+“ “

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

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

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

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

Схема работы
Исходный код
Лексер
Парсер
Символьная таблица
Токен
Следующий
Семантический
анализ

if (a == b) then
a += 5;
else
a -=

Лексема -- Токен
12345 (число, 12345)
temp_1 (идентификатор, указатель на симтаб)
+= (оператор, plus_assign)
+ (оператор,

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

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

Регулярные грамматики:
праволинейные (A → w, A → wB, A,B ∈ N,

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

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

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

Схема построения лексера
Лексическая спецификация
Регулярное выражение
Недетерминированный автомат
Детерминированный автомат
Диаграмма состояний

Рассмотрим регулярное выражение:
Построим соответствующий НКА:
Пример

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

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

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