Символы исходного языка

Сканеры (лексические анализаторы)

Классификация языков

Классификацию языков ввел Хомский. В терминах формальных грамматик определяется 4 основных класса:

1) грамматика типа 0 порождает язык с фразовой структурой (естественные языки).

U⁺: = V^*, где UÎ V È S, U⁺Î{ V È S }⁺.

2) грамматика типа 1 – контекстно-зависимая или контекстно-чувствительная.

xUy: = xuy, где UÎV, uÎ{ V È S }⁺.

3) грамматика типа 2 – контекстно-свободная.

U: = u, где UÎV, uÎ{ V È S }^*.

4) грамматика типа 3 – регулярная (автоматная).

Q: = RT|T, где Q,RÎV, TÎS.

Языки, порождаемые автоматной грамматикой, получили название регулярных множеств.

Сканер представляет собой ту часть транслятора, которая читает литеры исходной программы и строит из них слова (лексемы).

Подмножества формальных языков (синтаксический класс):

1. Служебные слова.

2. Целые числа.

3. Разделители.

4. Идентификаторы.

5. Оператор.

Сущности языка можно разделить на пять подмножеств.

Этапы работы транслятора

лексический

синтаксический

генерация кода

ИП

определение языка

проверка правильности структуры

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

Составленная таблица передается синтаксическому анализатору.

Строчка исходной программы А=В+С+10 будет разобрана

Служебные слова	Идентифи-каторы	Целые числа	Оператор	Разделитель
	i i i		= +

Исходя из этой таблицы, предложение превратится в: i=i+i+10. Это задача сканера – проанализировав предложение, построить цепочку.

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

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

В принципе построение языка программирования может быть построено (освоено) с помощью языка регулярной грамматики.

Символами в языке являются разделители и операторы (/, +, –, *, (,), и //), служебные слова (BEGIN, ABS и END), идентификаторы (которые не могут быть служебными словами), и целые числа. По крайней мере, один пробел должен отделять смежные идентификаторы, целые числа и/или служебные слова. Ни одного пробела не должно появляться между литерами в слове.

Идентификаторы и целые числа имеют вид

буква {буква | цифра} и цифра {цифра}.

В добавление ко всему сканер должен распознавать и исключать комментарий. Комментарий начинается с двулитерного символа /* и заканчивается при первом появлении двулитерного символа */. Следующая строка является примером одного комментария:

/* Это * / / один комментарий */.

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