Лексический анализ. Классификация языков по Хомскому (Н

Классификация языков по Хомскому (Н. Хомский 1959 г.).

Лекция 14

Тип языка по Хомскому	Класс языка	Класс распознающих устройств
0 - без ограничений	Рекурсивно-перечислимые множества	Машины Тьюринга
1 - непосредственно составляющие (контекстные)	НС - языки	Линейно ограниченные автоматы
2 - контекстно-свободные	КС - языки	Автоматы с магазинной памятью
3 - автоматные	Регулярные языки	Конечные автоматы

Лексический анализ - предварительная обработка исходной программы, на которой распознаются лексемы и заменяются их образами - дескрипторами.

Дескриптор =(<тип лексемы>, <указатель>).

Тип лексемы - числовой код класса лексемы (идентификатор, служебное слово, метка, константа, разделитель и др.)

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

Пример: 10 - ключевое слово, 20 - разделитель, 30 - идентификатор, 40 - константа.

Program primer;		Таблица ключевых слов		Таблица разделителей		Таблица идентификаторов
var X,Y,Z:real;		№	Ключевое слово		№	Разделитель		¹	Идентификатор
begin			Program			;			Primer
X:=5;			Begin			,			X
Y:=5;			End			+			Y
Z:=X+Y;			For			-			Z
end.			Real			/
			Var			*		Таблица констант
						:		№	Константа
						=
						.

Дескрипторный текст:

(10,1)(30,1)(20,1)

(10,6)(30,2)(20,2)(30,3)(20,2)(30,4)(20,7)(10,5)(20,1)

(10,2)

(30,2)(20,7)(20,8)(40,1)(20,1)

(30,3)(20,7)(20,8)(40,1)(20,1)

(30,4)(20,7)(20,8)(30,2)(20,3)(30,3)(20,1)

(10,3)(20,9)

Дата добавления: 2013-12-13