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

1. ГЛАВА 3

Лексический анализ
3.1 Назначение и необходимость фазы лексического анализа
3.2 Транслитератор
3.3 Регулярные языки и грамматики
3.4 Конечные автоматы
3.4.1 Определение КА.
3.4.2 Диаграмма переходов (состояний)
3.5 Матрица переходов КА
3.6 Детерминированный и недерминированный автомат
3.7 Лексический анализатор
3.8 Связь регулярных грамматик КА
3.8.1 Построение КА на основе леволинейной грамматики
3.8.2 Построение леволинейной грамматики на основе КА

2. 3.1 Назначение и необходимость фазы лексического анализа

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

3. 3.1 Назначение и необходимость фазы лексического анализа

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

4. 3.2 Транслитератор

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

5. 3.3 Регулярные языки и грамматики

Пример. Классы лексем:
• идентификаторы;
• служебные слова (множество
идентификаторов);
• целые числа, вещественные, строки
(литералы);
• однолитерные разделители ('+', '-', '(', ')'...);
• двухлитерные разделители ('//', '/*', '*/', ':=')
• комментарии.
5

6. 3.3 Регулярные языки и грамматики

<идентификатор> ::= буква | <идентификатор> буква |
<идентификатор> цифра
<целое> ::= цифра | <целое> цифра
<разделитель> ::= +| - | / | ( | ) …
<разделитель> ::= <slash> / | <slash> * | <ast>/ | <colon>=
<ast> ::= *
<colon> ::= :
Регулярные грамматики
A ->B | , где A, B VN, VT*
A -> B | , где A, B VN, VT*
Автоматные грамматики
A -> Bt | t, где A, B VN, t VT
A -> tB | t, где A, B VN, t VT
6

7. 3.3 Регулярные языки и грамматики

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

8. 3.4 Конечные автоматы

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

9. 3.4.1 Определение КА

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

10. 3.4.1 Определение КА

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

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}
S
δ(0,A) = {B}
δ(1,B)={A,Z}
1
0
A
1
B
Z
1
E
11

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

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

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

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

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

Состояние\Следующий <знак>
элемент
<десятичная <цифра>
точка>
<прочие>
1 Start
2, F1, М0
6, F0, M1
3, F2, M0
6, F0, M1
2 <знак>
6, F0, М2
6, F0, M3
3, F2, M0
6, F0, M4
3 <целое>
6, F0, М5
4, F4, М0
3, F2, M0
6, F0, M4
4 <число с точкой>
6, F0, М6
6, F0, M1
5, F3, M0
6, F0, M6
5 <дес. число с фикс. т.>
6, F0, М8
6, F0, M1
5, F3, M0
Exit
6 Error
Exit
Exit
Exit
Exit
Матрица переходов состояний для распознавания десятичных чисел с
фиксированной точкой
14

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

Подпрограмма
Действие
Инициализация
num=0; sign = "+"; count = 1.0
F0
Exit
F1
sign = insign
F2
num = 10 * num + innum
F3
count = count / 10; num = num + innum * count
F4
innum – значение следующей введенной цифры;
insign – значение знака во входной строке;
sign – значение знака распознаного числа;
num – значение распознаного числа;
count – количество цифр после точки.
15

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

Номер
сообщения
М0
M1
М2
M3
М4
М5
М6
М7
M8
Exit
Сообщение
Ошибка. Строка не число: нет ни цифры ни знака
Ошибка. Два последовательных знака
Ошибка. Перед точкой нет ни одной цифры
Ошибка. За знаком не следует цифра
Ошибка. Отсутствует точка
Ошибка. За точкой нет ни одной цифры
Ошибка. Две десятичные точки в числе
Ошибка. Знак в середине числа
All OK
16

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.
• Доказано, что для любого КА можно построить ДКА.
Домашнее задание: Алгоритм преобразования
произвольного КА к детерминированному виду.
17

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

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

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

<рrоg> ::= PROGRAM <prog_name> VAR <dec_list> BEGIN <stmt_ list> END.
<prog_name> ::= id
<dec_list> ::= <dec>; | <dec_list>; <dec>
<dec> ::= <id_list>:<type>
<type> ::= INTEGER
<id_list> ::= <id> | <id_list>, <id>
<stmt_list> ::= <stmt> | <stmt_list>; <stmt>
<stmt> ::= <assign> | <read> | <write> | <for>
<assign> ::= <id>:=<exp>
<exp> <term> | <exp>+<term> | <exp>-<term>
<term> ::= <factor> | <term>*<factor> | <term> DIV <factor>
<factor> ::= <id> | <int> | (<exp>)
<read> ::= READ(<id_list>)
<write>::= WRITE(<id_ list>)
<for> ::= FOR <index_ exp> DO <body>
<index_exp> ::= <id>:=<exp> TO <exp>
<body> ::= <stmt> | BEGIN <stmt_list> END
<id> ::= <id_name>
<id name> ::= <letter> | <id_name> <letter> | <id_name><digit>
<int> ::= <digit> | <int><digit>
<letter> ::= A | В | С|... | Z
<digit>::= 0 | 1 | 2 |...| 9
19

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.
20

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

Таблица разделителей
TD
2
Таблица служебных слов
TW 1
N
1
2
3
4
5
6
7
8
Терминальный
символ
PROGRAM
BEGIN
VAR
INTEGER
END
FOR
TO
DO
Признак
разделителя
-
N
Терминальный
Признак
символ
разделителя
1 ;
+
2 :
+
3 :=
21

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

Таблица литералов (констант)
TNUM 3
N Лите- Ад- Тип
рал рес
1
2
3
4
0
0
1
100
I
I
I
I
Другая
информация
Значение
во
внутреннем
представлении
Таблица идентификаторов
TID
4
N
1
2
3
4
Символи- Ад- Tип Другая
ческое имя рес
информация
STATS
I
SUM
I
SUMSQ
I
I
I
22

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

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

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) – чтение из входного потока очередного
символа и занесение его в с
24

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

25

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 ...
26

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; }
27

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

буква цифра ‘ ‘,’\n’
‘{‘
‘}‘
‘:’
‘=’
┴
Прочее
3,F0
7
4, F1
6
5
6
0
S
1, F0
2, F1
1
ID
1, F4
7
1, F3 0, F4 0, F4 0, F4
0, F4
0, F4
0, F4
2 NUM 0, F5
2, F3
0, F5 0, F5 0, F5 0, F5
0, F5
0, F5
0, F5
3
COM 3, F0
3, F0
3, F0 3, F0 0, F0 3, F0
3, F0
7
3, F0
4
ASS
0, F7
0, F7
0, F7 0, F7 0, F7 0, F7
0, F8
0, F7
0, F7
5
FIN
—
—
—
—
—
6
DLM
0, F9
0, F9
0, F9
0, F9
0, F9
7
ERR
—
—
—
—
—
3, F1
—
—
—
—
0, F9 0, F9 0, F9 0, F9
—
—
—
—
28

29. 3.8 Связь регулярных грамматик КА

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

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

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

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}
31

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
32

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
0
1
H
A
B
0
S
33

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

Шаг
1
2
3
4
5
6
7
Состояние
H
A
S
A
S
B
S
Остаток входной
цепочки
101001
01001
1001
001
01
1
-
34

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

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

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

3) Просматриваем функции переходов автомата M для всех
возможных состояний из Q для всех входных символов из V.
Если δ(A,t)={B1,B2, … Bn}, A,B є Q, t є V, 1<i<=n,
то для всех состояний 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}
36

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

37

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

0
1
S
A
H
0
1
+
_
B
V= {0,1,+,-, }
Q = {S, A, B, H}
q0 = H
F= {S}
Шаг 1. VT = V= {0,1,+,-, }
Шаг 2. VN = {S, A, B}
Шаг 3.
P:
S -> A
A -> A0 | A1 | B0 | B1 | 0 | 1
B -> A+ | AШаг 4. S = S
δ(B,1) = {A}
δ(B,0) = {A}
δ(A,+) = {B}
δ(A,-) = {B}
δ(A,0) = {A}
δ(A,1) = {A}
δ(H,0) = {A}
δ(H,1) = {A}
δ(A, ) = {S}
38