В дальнейшем будем исходить из предположения, что все лексемы могут быть однозначно выделены сканером на этапе лексического анализа. Для всех современных языков программирования это действительно так, поскольку их синтаксис разрабатывался с учетом возможностей компиляторов.
Таблица лексем и содержащаяся в ней информация
Результатом работы лексического анализатора является перечень всех найденных в тексте исходной программы лексем с учетом характеристик каждой лексемы. Этот перечень лексем можно представить в виде таблицы, называемой таблицей лексем. Каждой лексеме в таблице лексем соответствует некий уникальный условный код, зависящий от типа лексемы, и дополнительная служебная информация. Таблица лексем в каждой строке должна содержать информацию о виде лексемы, ее типе и, возможно, значении. Обычно структуры данных, служащие для организации такой таблицы, имеют два поля: первое – тип лексемы, второе – указатель на информацию о лексеме.
Кроме того, информация о некоторых типах лексем, найденных в исходной программе, должна помещаться в таблицу идентификаторов (или в одну из таблиц идентификаторов, если компилятор предусматривает различные таблицы идентификаторов для различных типов лексем).
Внимание!
Не следует путать таблицу лексем и таблицу идентификаторов – это две принципиально разные таблицы, обрабатываемые лексическим анализатором.
Таблица лексем фактически содержит весь текст исходной программы, обработанный лексическим анализатором. В нее входят все возможные типы лексем, кроме того, любая лексема может встречаться в ней любое количество раз. Таблица идентификаторов содержит только определенные типы лексем – идентификаторы и константы. В нее не попадают такие лексемы, как ключевые (служебные) слова входного языка, знаки операций и разделители. Кроме того, каждая лексема (идентификатор или константа) может встречаться в таблице идентификаторов только один раз. Также можно отметить, что лексемы в таблице лексем обязательно располагаются в том же порядке, что и в исходной программе (порядок лексем в ней не меняется), а в таблице идентификаторов лексемы располагаются в любом порядке так, чтобы обеспечить удобство поиска.
В качестве примера можно рассмотреть некоторый фрагмент исходного кода на языке Object Pascal и соответствующую ему таблицу лексем, представленную в табл. 2.1:
…
begin
for i:=1 to N do
fg:= fg * 0.5
…
Поле «значение» в табл. 2.1 подразумевает некое кодовое значение, которое будет помещено в итоговую таблицу лексем в результате работы лексического анализатора. Конечно, значения, которые записаны в примере, являются условными. Конкретные коды выбираются разработчиками при реализации компилятора. Важно отметить также, что устанавливается связь таблицы лексем с таблицей идентификаторов (в примере это отражено некоторым индексом, следующим после идентификатора за знаком «:», а в реальном компиляторе определяется его реализацией).
Построение лексических анализаторов (сканеров)
Лексический анализатор имеет дело с такими объектами, как различного рода константы и идентификаторы (к последним относятся и ключевые слова). Язык описания констант и идентификаторов в большинстве случаев является регулярным, то есть может быть описан с помощью регулярных грамматик [1–4, 7]. Распознавателями для регулярных языков являются конечные автоматы (КА). Существуют правила, с помощью которых для любой регулярной грамматики может быть построен КА, распознающий цепочки языка, заданного этой грамматикой.
Более подробно о построении КА на основе грамматик для регулярных языков можно узнать в [3, 7, 26].
Любой КА может быть задан с помощью пяти параметров: M(Q,Σ,δ,q0,F),
где:
Q – конечное множество состояний автомата;
Σ – конечное множество допустимых входных символов (входной алфавит КА);
δ – заданное отображение множества Q·Σ во множество подмножеств P(Q)δ: Q·Σ → P(Q) (иногда δ называют функцией переходов автомата);
– начальное состояние автомата;
– множество заключительных состояний автомата.
Другим способом описания КА является граф переходов – графическое представление множества состояний и функции переходов КА. Граф переходов КА – это нагруженный однонаправленный граф, в котором вершины представляют состояния КА, дуги отображают переходы из одного состояния в другое, а символы нагрузки (пометки) дуг соответствуют функции перехода КА. Если функция перехода КА предусматривает переход из состояния q в q' по нескольким символам, то между ними строится одна дуга, которая помечается всеми символами, по которым происходит переход из q в q'.