Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3)

Сентябрь 7, 2022

Главная
Алгебра
Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3)

Содержание

2. 3.1 Назначение и необходимость фазы лексического анализа Лексический анализ – первая фаза процесса трансляции, предназначенная для
3. 3.1 Назначение и необходимость фазы лексического анализа Задачи, решаемые сканером (преимущества сканера): представление элементарных конструкций языка
4. 3.2 Транслитератор Устройство, осуществляющее сопоставление класс с каждым отдельным символом, называется транслитератором. Наиболее типичными классами символов
5. 3.3 Регулярные языки и грамматики Пример. Классы лексем: идентификаторы; служебные слова (множество идентификаторов); целые числа, вещественные,
6. 3.3 Регулярные языки и грамматики Автоматные грамматики A -> Bt | t, где A, B ∈
7. 3.3 Регулярные языки и грамматики Доказано, что класс регулярной и автоматной грамматики почти эквиваленты. Любую регулярную
8. 3.4 КОНЕЧНЫЕ АВТОМАТЫ ГЛАВА 3. Лексический анализ
9. 3.4.1 Определение КА Конечный автомат (КА) – это пятерка (Q, V, δ, q0, F), где: Q
10. 3.4.1 Определение КА Конечный автомат называется полностью определенным, если в каждом его состоянии определена функция перехода
11. 3.4.2 Диаграмма переходов (состояний) Граф переходов (дерево, диаграмма) – направленный помеченный граф с символами состояний конечного
12. 3.5 Матрица переходов КА Каждая строка этой матрицы представляет состояние автомата, а каждый столбец соответствует возможному
13. 3.5 Матрица переходов КА ::= | фиксированной точкой > ::= ::= | | ::= . ::=
14. 3.5 Матрица переходов КА Матрица переходов состояний для распознавания десятичных чисел с фиксированной точкой
15. 3.5 Матрица переходов КА innum – значение следующей введенной цифры; insign – значение знака во входной
16. 3.5 Матрица переходов КА
17. 3.6 Детерминированный и недерминированный автомат Конечный автомат (Q, V, δ, q0, F) называется детерминированным конечным автоматом
18. 3.7 Лексический анализатор Лексический анализатор – программа, которая используя набор сканеров, преобразует исходный текст программы во
19. 3.7 Лексический анализатор ::= PROGRAM VAR BEGIN END. ::= id ::= ; | ; ::= :
20. 3.7 Лексический анализатор PROGRAM STATS VAR SUM, SUMSQ, I, VALUE, MEAN, VARIANCE: INTEGER; BEGIN SUM :=
21. 3.7 Лексический анализатор Таблица служебных слов TW 1 Таблица разделителей TD 2
22. 3.7 Лексический анализатор Таблица литералов (констант) TNUM 3 Таблица идентификаторов TID 4
23. 3.7 Лексический анализатор Переменные: buf – буфер для накопления символов лексем; с – очередной входной символ;
24. 3.7 Лексический анализатор Функции: void clear (void) – очистить буффер buf, void add (void) – добавление
25. 3.7 Лексический анализатор
26. 3.7 Лексический анализатор КА пользуясь набором сканера формирует набор лексем. PROGRAM STATS VAR SUM ... :
27. 3.7 Лексический анализатор F0={ gc() } F1={ clear(); add(); gc()} F3={ add(); gc() } F4={ j==look(TW)
28. 3.7 Лексический анализатор
29. 3.8 Связь регулярных грамматик КА На основании имеющейся регулярной грамматики можно построить эквивалентный ей КА, и
30. 3.8.1 Построение КА на основе леволинейной грамматики Необходимо построить КА M(Q, V, δ, q0, F), по
31. 3.8.1 Построение КА на основе леволинейной грамматики 3) Просматриваем все множество правил грамматики G. Если встречается
32. 3.8.1 Построение КА на основе леволинейной грамматики Построить автомат M(Q, V, δ, q0, F) на основе
33. 3.8.1 Построение КА на основе леволинейной грамматики Шаг 1. V = {0, 1} Шаг 2. Q
34. 3.8.1 Построение КА на основе леволинейной грамматики
35. 3.8.2 Построение леволинейной грамматики на основе КА 1) Множество терминальных символов строится на основании входных символов
36. 3.8.2 Построение леволинейной грамматики на основе КА 3) Просматриваем функции переходов автомата M для всех возможных
37. 3.8.2 Построение леволинейной грамматики на основе КА
39. Скачать презентацию

Слайд 2

3.1 Назначение и необходимость фазы лексического анализа
Лексический анализ – первая фаза

процесса трансляции, предназначенная для группировки символов входной цепочки в более крупные конструкции, называемые лексемами.
Лексемы – минимальные несущие смысл объединения символов. С каждой лексемой связано два понятия:
класс лексемы, определяющий общее название для категории элементов, обладающих общими свойствами
значение лексемы, определяющее подстроку символов входной цепочки, соответствующих распознанному классу лексемы. В зависимости от класса, значение лексемы может быть преобразовано во внутреннее представление уже на этапе лексического анализа.

Слайд 3

3.1 Назначение и необходимость фазы лексического анализа
Задачи, решаемые сканером (преимущества сканера):
представление

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

Слайд 4

3.2 Транслитератор
Устройство, осуществляющее сопоставление класс с каждым отдельным символом, называется транслитератором.

Наиболее типичными классами символов являются:
буква;
цифра;
разделитель;
игнорируемый;
запрещенный;
прочие.

Слайд 5

3.3 Регулярные языки и грамматики
Пример. Классы лексем:
идентификаторы;
служебные слова (множество идентификаторов);
целые

числа, вещественные, строки (литералы);
однолитерные разделители ('+', '-', '(', ')'...);
двухлитерные разделители ('//', '/*', '*/', ':=')
комментарии.

Слайд 6

3.3 Регулярные языки и грамматики
Автоматные грамматики
A -> Bt | t, где

A, B ∈ VN, t ∈ VT
A -> tB | t, где A, B ∈ VN, t ∈ VT

Регулярные грамматики
A ->Bγ | γ, где A, B ∈ VN, γ ∈ VT*
A -> γB | γ, где A, B ∈ VN, γ ∈ VT*

<идентификатор> ::= буква | <идентификатор> буква | <идентификатор> цифра
<целое> ::= цифра | <целое> цифра
<разделитель> ::= +| - | / | ( | ) …
<разделитель> ::= / | * | / | =
::= *
::= :

Слайд 7

3.3 Регулярные языки и грамматики
Доказано, что класс регулярной и автоматной грамматики

почти эквиваленты. Любую регулярную грамматику можно привести к автоматному виду.
Домашнее задание:
Алгоритм преобразования регулярной грамматики к автоматному виду

Слайд 8

3.4 КОНЕЧНЫЕ АВТОМАТЫ
ГЛАВА 3. Лексический анализ

Слайд 9

3.4.1 Определение КА
Конечный автомат (КА) – это пятерка (Q, V, δ,

q0, F), где:
Q – конечное множество состояний;
V – конечное множество допустимых входных символов (алфавит);
δ – отображение множества Q × VT -> Q, определяющее поведение автомата; отображение δ часто называют функцией переходов;
q0 ∈ Q – начальное состояние;
F ∈ Q – непустое множество конечных состояний.

Слайд 10

3.4.1 Определение КА
Конечный автомат называется полностью определенным, если в каждом его

состоянии определена функция перехода для каждого входного символа.
Для a є V и q ∈ Q определена δ (a, q)= R, R <= Q
Множество цепочек, допускаемых конечным автоматом, составляет определяемый им язык.
Два конечных автомата называются эквивалентными, если они определяют один и тот же язык.

Слайд 11

3.4.2 Диаграмма переходов (состояний)
Граф переходов (дерево, диаграмма) – направленный помеченный граф

с символами состояний конечного автомата в вершинах, в котором есть дуга (p,q) , помеченная символом a є V (p,q ∈ Q), если в КА определена функция δ (a,p) и q ∈ δ (a,p).

M ( {S,A,B,Z}, {0,1}, δ, S, {Z} )
δ(1,S) = {A}
δ(0,A) = {B}
δ(1,B)={A,Z}

Слайд 12

3.5 Матрица переходов КА
Каждая строка этой матрицы представляет состояние автомата, а

каждый столбец соответствует возможному входному элементу.
В ячейках матрицы указывается структура из трех полей:
состояние
функция которая выполняется при переходе из одного состояния в другое
сообщение об ошибке

Слайд 13

3.5 Матрица переходов КА
<десятичное целое с фиксированной точкой> ::=
<число с

точкой> <цифра> |
< десятичное целое с
фиксированной точкой > <цифра>
<число с точкой> ::= <целое>
<десятичная точка>
<целое> ::= <знак> <целое> |
<цифра> | <целое> <цифра>
<десятичная точка> ::= .
<знак> ::= + | -
<цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Слайд 14

3.5 Матрица переходов КА
Матрица переходов состояний для распознавания десятичных чисел с

фиксированной точкой

Слайд 15

3.5 Матрица переходов КА
innum – значение следующей введенной цифры;
insign – значение

знака во входной строке;
sign – значение знака распознаного числа;
num – значение распознаного числа;
count – количество цифр после точки.

Слайд 16

3.5 Матрица переходов КА

Слайд 17

3.6 Детерминированный и недерминированный автомат
Конечный автомат (Q, V, δ, q0, F)

называется детерминированным конечным автоматом (ДКА), если в каждом из его состояний для любого входного символа функция переходов содержит не более одного состояний.
Для a є V, q ∈ Q, r ∈ Q, определена δ (a, q)= {r}
В недетерминированном КА δ (a,q) = {r1,r2,...,rn} – означает, что из состояния q по входному символу a можно осуществить переход в любое из состояний ri, i = 1, 2, ... ,n.
Доказано, что для любого КА можно построить ДКА.
Домашнее задание: Алгоритм преобразования произвольного КА к детерминированному виду.

Слайд 18

3.7 Лексический анализатор
Лексический анализатор – программа, которая используя набор сканеров, преобразует

исходный текст программы во внутреннее представление и помещает определённую информацию в специальные таблицы.
Типы лексем (сканеров): идентификаторы, служебные слова, литералы (или константы) и разделители.
Каждой лексеме сопоставляется пара:
(тип лексемы, указатель на инф. о ней)

Слайд 19

3.7 Лексический анализатор
<рrоg> ::= PROGRAM VAR BEGIN

END.
::= id
::= ; | ;
::= :
::= INTEGER
::= | ,
::= | ;
::= | | |
::= :=
| + | -
::= | * | DIV
::= | | ()
::= READ()
::= WRITE()
::= FOR DO
::= := TO
::= | BEGIN END
::=
::= | |
::= |
::= A | В | С|... | Z
::= 0 | 1 | 2 |...| 9

Слайд 20

3.7 Лексический анализатор
PROGRAM STATS
VAR
SUM, SUMSQ, I, VALUE, MEAN, VARIANCE: INTEGER;
BEGIN
SUM :=

0;
SUMSQ := 0;
FOR I 1 TO 100 DO
BEGIN
READ( VALUE );
SUM := SUM + VALUE;
SUMSQ := SUMSQ + VALUE * VALUE;
END;
MEAN := SUM DIV 100;
VARIANCE := SUMSQ DIV 100 - MEAN * MEAN;
WRITE( MEAN, VARIANCE);
END.

Слайд 21

3.7 Лексический анализатор
Таблица служебных слов TW 1
Таблица разделителей
TD 2

Слайд 22

3.7 Лексический анализатор
Таблица литералов (констант) TNUM 3
Таблица идентификаторов TID 4

Слайд 23

3.7 Лексический анализатор
Переменные:
buf – буфер для накопления символов лексем;
с –

очередной входной символ;
d – переменная для формирования числового значения константы;
TW – таблица служебных слов ;
TD – таблица ограничителей;
TID – таблица идентификаторов;
TNUM – таблица констант;
tabl – имя типа таблиц;
ptable – указатель на tabl.

Слайд 24

3.7 Лексический анализатор
Функции:
void clear (void) – очистить буффер buf,
void add (void)

– добавление символа с в конец буфера buf;
int look (ptabl T) – поиск в таблице Т лексемы из буфера buf; результат – номер строки таблицы с информацией о лексеме либо 0, если лексемы нет в таблице;
int putl (ptabl Т) – запись в таблицу Т лексемы из buf; результат – номер строки с информацией о лексеме;
int puntnum(void) – запись в TNUM константы из d если ее там не было; результат – номер строки в таблице TNUM с информацией о константе-лексеме;
void makelex (int k, int i) – формирование и вывод внутреннего представления лексемы; к – номер класса, i – номер в классе;
void gc (void) – чтение из входного потока очередного символа и занесение его в с

Слайд 25

3.7 Лексический анализатор

Слайд 26

3.7 Лексический анализатор
КА пользуясь набором сканера формирует набор лексем.
<1,1> <4,1> <1,3>

<4,2>
PROGRAM STATS VAR SUM

<2,2> <1,4> <2,1> <1,2> ...
: INTEGER ; BEGIN ...

Слайд 27

3.7 Лексический анализатор
F0={ gc() }
F1={ clear(); add(); gc()}
F3={ add(); gc() }
F4={

j==look(TW) – ?
Да: makelex(1,j);
Нет: j=put(TID);
makelex(4,j); }

F5={ makelex(3, putnum()) }
F7={ makelex(2, look(TD)) }
F8={ add(),gc(), makelex(2,look(TD)) }
F9={ clear(), add()
j==look(TD) – ?
Да: gc(); makelex(2,j);
Нет: c==’\n’ -?
Да:gc();
Нет:State=7; }

Слайд 28

3.7 Лексический анализатор

Слайд 29

3.8 Связь регулярных грамматик КА
На основании имеющейся регулярной грамматики можно построить

эквивалентный ей КА, и наоборот на основе КА можно построить эквивалентную ему грамматику.
Поскольку КА являются распознавателями регулярных языков, таким образом, построив по регулярной грамматике КА, решаем задачу разбора.

Слайд 30

3.8.1 Построение КА на основе леволинейной грамматики
Необходимо построить КА M(Q, V,

δ, q0, F), по леволинейной грамматике G(VT, VN, P, S).
1) Множество входных символов строится на основании терминальных символов V=VT
2) Множество состояний автомата строится на основании множества нетерминальных символов. Каждому нетерминалу ставится в соответствие состояние автомата и добавляется еще одно начальное состояние.
Q = VN U {H}

Слайд 31

3.8.1 Построение КА на основе леволинейной грамматики
3) Просматриваем все множество правил

грамматики G.
Если встречается правило вида A -> t, A єVN, t є VT, то функцию перехода добавляем состояние A. A є δ(H,t).
Если A -> Bt, A,B є VN, t є VT, то A є δ(B,t).
4) Начальное состояние автомата q0=H.
5) Множество конечных состояний включает одно состояние, соответствующее начальному символу грамматики S.
F={S}

Слайд 32

3.8.1 Построение КА на основе леволинейной грамматики
Построить автомат M(Q, V, δ,

q0, F) на основе имеющейся автоматной грамматики:
G = ( {0,1}, {S,A,B}, P, S)
P: S -> A0 | B1
A -> S1|1
B -> S0|0
L(G) = { (10 | 01)n, n>0}
S => A0 => 10
S => A0 => S10 => B110 => 0110
S => B1 => 01
S => B1 => S01 =>A001 => 1001

Слайд 33

3.8.1 Построение КА на основе леволинейной грамматики
Шаг 1. V = {0,

1}
Шаг 2. Q = {S, A, B, H}
Шаг 3. δ(A,0) = {S}
δ(B,1) = {S}
δ(S,1) = {A}
δ(H,1) = {A}
δ(S,0) = {B}
δ(H,0) = {B}
Шаг 4. q0 = H
Шаг 5. F= {S}

S -> A0 | B1
A -> S1|1
B -> S0|0

Слайд 34

3.8.1 Построение КА на основе леволинейной грамматики

Слайд 35

3.8.2 Построение леволинейной грамматики на основе КА
1) Множество терминальных символов строится

на основании входных символов
VT=V
2) Множество нетерминалов грамматики G строится на основании множества состояний Q автомата за исключением начального состояния автомата
VN = Q / {q0}

Слайд 36

3.8.2 Построение леволинейной грамматики на основе КА
3) Просматриваем функции переходов автомата

M для всех возможных состояний из Q для всех входных символов из V.
Если δ(A,t)={B1,B2, … Bn}, A,B є Q, t є V, 1то для всех состояний Bi выполняем следующее:
Если A= q0, то множество Bi -> t
Если A≠ q0, то множество Bi ->A t
4)
Если множество конечных состояний F автомата M содержит только одно состояние F={f0}, то начальным символом грамматики принимается нетерминал, соответствующий этому состоянию.
Если множество заключительных состояний F={f1,f2,…,fn},
то S -> F1 | F2 | … | Fn
VN = VN U {S}

Слайд 37

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3)

Содержание

3.1 Назначение и необходимость фазы лексического анализаЛексический анализ – первая фаза

3.1 Назначение и необходимость фазы лексического анализаЗадачи, решаемые сканером (преимущества сканера):представление

3.2 ТранслитераторУстройство, осуществляющее сопоставление класс с каждым отдельным символом, называется транслитератором.

3.3 Регулярные языки и грамматикиПример. Классы лексем:идентификаторы;служебные слова (множество идентификаторов); целые

3.3 Регулярные языки и грамматикиАвтоматные грамматикиA -> Bt | t, где

3.3 Регулярные языки и грамматикиДоказано, что класс регулярной и автоматной грамматики

3.4 КОНЕЧНЫЕ АВТОМАТЫ ГЛАВА 3. Лексический анализ

3.4.1 Определение КАКонечный автомат (КА) – это пятерка (Q, V, δ,

3.4.1 Определение КАКонечный автомат называется полностью определенным, если в каждом его

3.4.2 Диаграмма переходов (состояний)Граф переходов (дерево, диаграмма) – направленный помеченный граф

3.5 Матрица переходов КАКаждая строка этой матрицы представляет состояние автомата, а

3.5 Матрица переходов КА<десятичное целое с фиксированной точкой> ::= <число с

3.5 Матрица переходов КАМатрица переходов состояний для распознавания десятичных чисел с

3.5 Матрица переходов КАinnum – значение следующей введенной цифры;insign – значение

3.5 Матрица переходов КА

3.6 Детерминированный и недерминированный автоматКонечный автомат (Q, V, δ, q0, F)

3.7 Лексический анализаторЛексический анализатор – программа, которая используя набор сканеров, преобразует

3.7 Лексический анализатор<рrоg> ::= PROGRAM VAR BEGIN

3.7 Лексический анализаторPROGRAM STATSVAR SUM, SUMSQ, I, VALUE, MEAN, VARIANCE: INTEGER;BEGIN SUM :=

3.7 Лексический анализаторТаблица служебных слов TW 1Таблица разделителей TD 2

3.7 Лексический анализаторТаблица литералов (констант) TNUM 3Таблица идентификаторов TID 4

3.7 Лексический анализаторПеременные: buf – буфер для накопления символов лексем;с –

3.7 Лексический анализаторФункции:void clear (void) – очистить буффер buf,void add (void)

3.7 Лексический анализатор

3.7 Лексический анализаторКА пользуясь набором сканера формирует набор лексем.<1,1> <4,1> <1,3>

3.7 Лексический анализаторF0={ gc() }F1={ clear(); add(); gc()}F3={ add(); gc() }F4={

3.7 Лексический анализатор

3.8 Связь регулярных грамматик КАНа основании имеющейся регулярной грамматики можно построить

3.8.1 Построение КА на основе леволинейной грамматикиНеобходимо построить КА M(Q, V,

3.8.1 Построение КА на основе леволинейной грамматики3) Просматриваем все множество правил

3.8.1 Построение КА на основе леволинейной грамматикиПостроить автомат M(Q, V, δ,

3.8.1 Построение КА на основе леволинейной грамматикиШаг 1. V = {0,

3.8.1 Построение КА на основе леволинейной грамматики

3.8.2 Построение леволинейной грамматики на основе КА1) Множество терминальных символов строится

3.8.2 Построение леволинейной грамматики на основе КА3) Просматриваем функции переходов автомата

3.8.2 Построение леволинейной грамматики на основе КА

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

3.1 Назначение и необходимость фазы лексического анализа
Лексический анализ – первая фаза

3.1 Назначение и необходимость фазы лексического анализа
Задачи, решаемые сканером (преимущества сканера):
представление

3.2 Транслитератор
Устройство, осуществляющее сопоставление класс с каждым отдельным символом, называется транслитератором.

3.3 Регулярные языки и грамматики
Пример. Классы лексем:
идентификаторы;
служебные слова (множество идентификаторов);
целые

3.3 Регулярные языки и грамматики
Автоматные грамматики
A -> Bt | t, где

3.3 Регулярные языки и грамматики
Доказано, что класс регулярной и автоматной грамматики

3.4 КОНЕЧНЫЕ АВТОМАТЫ
ГЛАВА 3. Лексический анализ

3.4.1 Определение КА
Конечный автомат (КА) – это пятерка (Q, V, δ,

3.4.1 Определение КА
Конечный автомат называется полностью определенным, если в каждом его

3.4.2 Диаграмма переходов (состояний)
Граф переходов (дерево, диаграмма) – направленный помеченный граф

3.5 Матрица переходов КА
Каждая строка этой матрицы представляет состояние автомата, а

3.5 Матрица переходов КА
<десятичное целое с фиксированной точкой> ::=
<число с

3.5 Матрица переходов КА
Матрица переходов состояний для распознавания десятичных чисел с

3.5 Матрица переходов КА
innum – значение следующей введенной цифры;
insign – значение

3.6 Детерминированный и недерминированный автомат
Конечный автомат (Q, V, δ, q0, F)

3.7 Лексический анализатор
Лексический анализатор – программа, которая используя набор сканеров, преобразует

3.7 Лексический анализатор
<рrоg> ::= PROGRAM VAR BEGIN

3.7 Лексический анализатор
PROGRAM STATS
VAR
SUM, SUMSQ, I, VALUE, MEAN, VARIANCE: INTEGER;
BEGIN
SUM :=

3.7 Лексический анализатор
Таблица служебных слов TW 1
Таблица разделителей
TD 2

3.7 Лексический анализатор
Таблица литералов (констант) TNUM 3
Таблица идентификаторов TID 4

3.7 Лексический анализатор
Переменные:
buf – буфер для накопления символов лексем;
с –

3.7 Лексический анализатор
Функции:
void clear (void) – очистить буффер buf,
void add (void)

3.7 Лексический анализатор
КА пользуясь набором сканера формирует набор лексем.
<1,1> <4,1> <1,3>

3.7 Лексический анализатор
F0={ gc() }
F1={ clear(); add(); gc()}
F3={ add(); gc() }
F4={

3.8 Связь регулярных грамматик КА
На основании имеющейся регулярной грамматики можно построить

3.8.1 Построение КА на основе леволинейной грамматики
Необходимо построить КА M(Q, V,

3.8.1 Построение КА на основе леволинейной грамматики
3) Просматриваем все множество правил

3.8.1 Построение КА на основе леволинейной грамматики
Построить автомат M(Q, V, δ,

3.8.1 Построение КА на основе леволинейной грамматики
Шаг 1. V = {0,

3.8.2 Построение леволинейной грамматики на основе КА
1) Множество терминальных символов строится

3.8.2 Построение леволинейной грамматики на основе КА
3) Просматриваем функции переходов автомата