Лексический анализ

Описание типов лексем

Рассматриваемые лексическим анализатором лексемы могут относиться к одному из следующих типов:

- Идентификаторы – пользовательские имена объектов программы.

- Константы – числовые или логические значения, указанные явно.

- Знаки операций – символы, обозначающие унарные и бинарные операции.

- Специальные символы – квадратные и круглые скобки, запятые и т.д.

- Разделители – пробелы и символы новой строки. Если в тексте программы, в каком- либо месте, может стоять хотя бы один разделитель, то в этом месте может стоять сколько угодно разделителей.

- Ключевые слова – зарезервированные идентификаторы, имеющие строго определённый смысл.

Токен	Лексема	Языковая конструкция
WH	while	Ключевые слова
IF	if
EL	else
GT	goto
RD	read
WR	write
T	true
F	false
INT	int
DB	double
STR	String
CH	char
PKG	package
IMP	import
CLS	class
VD	void
NW	new
NL	null
MN	main
LNG	length
CONC	concat
SUBST	substring
REP	replace
FND	find

ID	<идентификатор>	Идентификаторы
Cconst	1, 1000,-20	Целочисленная константа
Rconst	1.15	Вещественная константа
Chconst	‘f’	Символьная константа
Stconst	“test”	Строковая константа
IncDec	++, --	Унарные арифметические операции
PlusMin	+, -	Аддитивные арифметические операции
Multi	*, /	Мультипликативные арифметические операции
Not	!	Отрицание (логическая операция)
LOR	||	ИЛИ (логическая операция)
LAND	&&	И (логическая операция)
Comp	>, <, < =, > =	Отношения (логические операции)
Ecvi	= =, ! =	Эквивалентность (логические операции)
Assign	=	Операторы присваивания
(	(	Открывающая круглая скобка
(	)	Закрывающая круглая скобка
[	[	Открывающая квадратная скобка
]	]	Закрывающая квадратная скобка
{	{	Открывающая фигурная скобка
}	}	Закрывающая фигурная скобка
;	;	Точка с запятой
?	?	Вопросительный знак
:	:	Двоеточие
.	.	Точка
,	,	Запятая

Определение синтаксиса лексем

Определение автоматных грамматик, описывающих синтаксис лексем.

3. 2. 1. Классы литер, с помощью которых записываются программы на входном языке:

• класс «буква»: a A … z Z _ $

• класс «ноль»: 0

• класс «цифра без нуля»: 1 2 3 4 5 6 7 8 9

• класс «однолитерные разделители»: ; , + - * / ( ) [ ] ? : . ^

• класс «литеры однолитерных и двулитерных разделителей»: < > = ! & |

3. 2. 2. Составление автоматных грамматик, описывающих синтаксис лексем:

Терминальными символами грамматики являются классы литер, а начальным символом грамматики – символ S.

1. Автоматная грамматика, описывающая синтаксис лексем «идентификатор» и «ключевое слово». Здесь “Буква” – класс «буква», “Цифра” – класс «цифра», “₁” – класс, включающий все литеры, за исключением букв и цифр.

Правила грамматики:

S		Буква Id
Id		Буква Id
Id		Цифра Id
Id		1

2. Автоматная грамматика, описывающая синтаксис лексемы «целая константа без знака». Здесь “Цифра” – класс «цифра без нуля» , “₂” – класс, включающий все литеры, за исключением цифр , “Ноль” – класс «ноль»

Правила грамматики:

S		Sign Ноль
S		Sign Цифра C
Sign		+
Sign		-
Sign		2
C		Цифра C
C		Ноль C
C		2

3. Автоматная грамматика, описывающая синтаксис лексемы «вещественная константа без знака». Здесь “₂” – класс, включающий все литеры, за исключением цифр.

Правила грамматики:

S		Sign Ноль
S		Sign Ноль . T
S		Sign Цифра C
Sign		+
Sign		-
Sign		2
C		Цифра C
C		. T
T		Цифра T
T		Ноль T
T		2

4. Автоматные грамматики, описывающие синтаксис лексем «однолитерный разделитель» и «двулитерный разделитель». Здесь “Знак” – классы «однолитерные разделители» и «литеры однолитерных и двулитерных разделителей», “₃” – класс, включающий все литеры.

Правила грамматики:

однолитерные разделители:	S		Знак L
	L		3

лексема «<=»			S						< Next
			Next						= E
			E						3

лексема «>=»	S		> Next
	Next		= E
	E		3

лексема «! =»	S		Next =
	Next		! E
	E		3

лексема «&&»	S		& Next
	Next		& E
	E		3

лексема «||»	S		| Next
	Next		| E
	E		3

Структуры данных Статические таблицы: Составная таблица ключевых слов

1 WH

0

while

2 IF

0

if

3 EL

0

else

4 GT

0

goto

5 RD

0

read

6 WR

0

write

7 T

0

true

8 F

0

false

9 INT

0

int

10 DB

0

double

11 STR

0

String

12 CH

0

char

13 PKG

0

package

14 IMP

0	import

15 CLS

0

class

16 VD

0

void

17 NW

0

new

18 NL

0

null

19 MN

0

main

20 LNG

0

length

21 CON

0

concat

22 SUBS

0

substring

23 REP

0

replace

24 FND

0

find

25 таблица базовых типов

0	int
1	double
2	char
3	String

26 таблица унарных операторов

0	++
1	--

27 таблица аддитивных операторов)

0	+
1	-

28 таблица мультипликативных операторов

0	*
1	/

29 таблица операторов отрицания

0

!

30 таблица операторов ИЛИ

0

||

31 таблица операторов И

0

&&

32 таблица операторов отношения

0	>
1	<
2	>=
3	<=

33 таблица операторов эквивалентности

0	= =
1	! =

34 таблица операторов присваивания

0

=

Составная таблица разделителей

35 (

0

(

36 )

0

)

37 [

0

[

38 ]

0

]

39 {

0

{

40 }

0

}

41 ;

0

;

42 ?

0

?

43 :

0

:

44 .

0

.

45 ,

0

,

Кроме того есть 46 таблица атомарных символов.

Динамические таблицы

47 таблтца типов

Тип	Базовый тип	размер в байтах
Int	0	4
double	1	8
char	2	2
String	3	…

В таблицу типов изначально занесены базовые типы…. все типы пользователя добавляются в эту таблицу на этапе синтаксического анализатора. Каждому типу сопоставлен номер базового типа, которому он соответсвует. 48 таблица идентификаторов (ID)

	идентификатор	тип	значение
0
…..
N

если идентификатор – не относится к типам, то тип 4 (последний тип + 1) , а в значении может быть ссылка на базовый тип последовательность идентификаторов

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

последовательность операторов

оператор	номер в таблице операторов

(таблица операторов формируется из совокупности таблиц операторов по приоритетам)