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

1. Грамматика лексических единиц

1. Грамматика идентификатора

IcR

RcR

RdR

RrI

c-буква

d-цифра

r-разделитель (‘,’,’ ‘,’<’)

2. Грамматика числа

IdQ

QdQ

QrI

d-цифра

r-разделитель (‘,’,’ ‘,’<’)

3. Грамматика служебного слова

I<P

PcS

ScS

S>H

HI

c-буква

4. Грамматика констант

I’K

KcF

FcF

F’J

JI

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

3. Структуры данных и таблицы

При работе лексический анализатор формирует таблицы идентификаторов, чисел и лексем. Однако он также использует и готовые (зарание известные таблицы). К заранее из-вестным можно отнести такие таблицы как таблица служебных слов, таблица разделителей. Все заранее известные таблицы представим в памяти ЭВМ в виде двумерных массивов, а не-известные таблицы будем формировать в процессе работы лексического анализатора в виде линейных односвязных списков структур. Последовательность лексемм тоже представим в виде линейного односвязного списка.

Структуры данных

Структура Лекскемма.

typedef struct lexemma

{

int type; //тип(1-идентификатор,2-число,3-служ.слово,4-разделит.,5-константа Bool

// 6-константа Char)

int length; //длина

void *ptt; //указатель на таблицу(ТИ,ТЧ и т.д.)

struct lexemma *next; //указатель на следующий элемент списка

}lex;

Структура Идентификатор

typedef struct identificator

{

char *name; //имя

char type; //тип (1-bool,0-char)

int clas; //класс (1-массив,0-переменная)

int dim; //размерность массива (dim-мерный)

int dimc[3]; //количество элементов в n-ом уровне

struct identificator *next; //указатель на следующий элемент списка

}id;

Структура Число

typedef struct number

{

int value; //значение

struct number *next; //указатель на следующий элемент списка

}num;

Структура Ячейка памяти

typedef struct mem

{

int type; //тип (1-bool,0-char)

char *value; //значение

}

Таблицы

Количество таблиц определим по количеству типов лексем. Внашем случае их будет 6 щтук. 4 заранее известных и 2 формируемых в процессе работы лексического анализатора.

Зарание известные таблицы: 1) таблица служебных слов

2) таблица разделителей

3) таблица констант Bool

4) таблица констант Char

Формируемые таблицы: 1) таблица идентификаторов

2) таблица чисел

Пример.

Пример работы лексического анализатора.

Подадим на вход лексического анализатора цепочку:

{<bool>a7</bool>;<char><arr>a 2 2</arr>,dtr6</char>;

<bool><ass>hgf ‘true’</ass></boo>;<ass><marr>a 0 0</marr> <not>’A’</not></ass>;}

В результате работы лексического анализатора получим таблицы:

Таблица служ. Слов

1. bool

2. /bool

3. char

4. /char

5. arr

6. /arr

7. marr

8. /marr

9. iarr

10. /iarr

11. ass

12. /ass

13. and

14. /and

15. or

16. /or

17. not

18. /not

Таблица разделителей

19. ‘ ‘

20. ‘,’

21. ‘;’

22. ‘{‘

23. ‘}’

24. ‘’’

Таблица констант Char

25. ‘a’

26. ‘b’

27. ‘c’

…..

48. ‘x’

49. ‘y’

50. ‘z’

51. ‘A’

52. ‘B’

53. ‘C’

…..

73. ‘X’

74. ‘Y’

75. ‘Z’

Таблица коностант Bool

73. ‘true’

74. ‘false’

Таблица идентификаторов

78 a7

79 a

80 dtr6

81. hgf

Таблица чисел

82 2

83 0

Список лексемм.

Тип 4 Длина 1 Разделитель: { Указатель: 22

Тип 3 Длина 4 Служ.слово: bool Указатель: 1

Тип 1 Длина 2 Идентиф.: a7 Указатель: 78

Тип 3 Длина 5 Служ.слово: /bool Указатель: 2

Тип 4 Длина 1 Разделитель: ; Указатель: 21

Тип 3 Длина 4 Служ.слово: char Указатель: 3

Тип 3 Длина 3 Служ.слово: arr Указатель: 5

Тип 1 Длина 1 Идентиф.: a Указатель: 79

Тип 4 Длина 1 Разделитель: Указатель: 19

Тип 2 Длина 1 Число: 2 Указатель: 82

Тип 4 Длина 1 Разделитель: Указатель: 19

Тип 2 Длина 1 Число: 2 Указатель: 82

Тип 3 Длина 4 Служ.слово: /arr Указатель: 6

Тип 4 Длина 1 Разделитель: , Указатель: 20

Тип 1 Длина 4 Идентиф.: dtr6 Указатель: 80

Тип 3 Длина 5 Служ.слово: /char Указатель: 4

Тип 4 Длина 1 Разделитель: ; Указатель: 21

Тип 3 Длина 4 Служ.слово: bool Указатель: 1

Тип 3 Длина 3 Служ.слово: ass Указатель: 11

Тип 1 Длина 3 Идентиф.: hgf Указатель: 81

Тип 4 Длина 1 Разделитель: ' Указатель: 24

Тип 5 Длина 4 Константа Bool: true Указатель: 76

Тип 4 Длина 1 Разделитель: ' Указатель: 24

Тип 3 Длина 4 Служ.слово: /ass Указатель: 12

Тип 3 Длина 5 Служ.слово: /bool Указатель: 2

Тип 4 Длина 1 Разделитель: ; Указатель: 21

Тип 3 Длина 3 Служ.слово: ass Указатель: 11

Тип 3 Длина 4 Служ.слово: marr Указатель: 7

Тип 1 Длина 1 Идентиф.: a Указатель: 79

Тип 4 Длина 1 Разделитель: Указатель: 19

Тип 2 Длина 1 Число: 0 Указатель: 83

Тип 4 Длина 1 Разделитель: Указатель: 19

Тип 2 Длина 1 Число: 0 Указатель: 83

Тип 3 Длина 5 Служ.слово: /marr Указатель: 8

Тип 4 Длина 1 Разделитель: Указатель: 19

Тип 3 Длина 3 Служ.слово: not Указатель: 17

Тип 4 Длина 1 Разделитель: ' Указатель: 24

Тип 6 Длина 1 Константа Char: A Указатель: 51

Тип 4 Длина 1 Разделитель: ' Указатель: 24

Тип 3 Длина 4 Служ.слово: /not Указатель: 18

Тип 3 Длина 4 Служ.слово: /ass Указатель: 12

Тип 4 Длина 1 Разделитель: ; Указатель: 21

Тип 4 Длина 1 Разделитель: } Указатель: 23