Сканеры (лексические анализаторы)
Классификация языков
Классификацию языков ввел Хомский. В терминах формальных грамматик определяется 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), идентификаторы (которые не могут быть служебными словами), и целые числа. По крайней мере, один пробел должен отделять смежные идентификаторы, целые числа и/или служебные слова. Ни одного пробела не должно появляться между литерами в слове.
|
|
Идентификаторы и целые числа имеют вид
буква {буква | цифра} и цифра {цифра}.
В добавление ко всему сканер должен распознавать и исключать комментарий. Комментарий начинается с двулитерного символа /* и заканчивается при первом появлении двулитерного символа */. Следующая строка является примером одного комментария:
/* Это * / / один комментарий */.
Сканер строит внутреннее представление для каждого символа. В большинстве случаев это целое число фиксированной длины (байт, полуслово, слово и т.д.). В других частях компилятора гораздо эффективнее обрабатываются эти целые числа, чем цепочки переменной длины, которыми фактически представляются символы.