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

Типы лексем, выделяемых лексическим анализатором из программы на входном языке, определяются входным языком. Обычно лексические анализаторы исключают из текста исходной программы комментарии, незначащие пробелы, символы табуляции и перевода строки и выделяют лексемы следующих типов:

· идентификаторы;

· константы (числовые, строковые, символьные);

· ключевые слова входного языка,

· знаки операций (арифметические, логические, отношения),

· разделители.

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

k = i+++++j;.

Существует только одна правильная трактовка этого оператора:

k = (i++) + (++j);,

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

k = i ++ ++ + j;.

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

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

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

1. Разбить литеры, с помощью которых записываются программы на входном языке, на классы. В один класс помещаются литеры, которые одинаковым образом используются для образования лексем. Примерами классов литер являются: латинская буква, двоичная цифра, десятичная цифра, символ «=».

2. Составить автоматные грамматики, описывающие синтаксис лексем, при условии, что терминальными символами грамматики являются классы литер, а начальным символом грамматики – символ S.

Следующие правила автоматной грамматики, в которой буква – класс«латинская буква», цифра – класс«цифра», e-класс, включающий все литеры, за исключением латинских букв и цифр, описывают синтаксис идентификатора:

Построение диаграммы лексического анализатора

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

1. Для каждой лексемы построить граф конечного автомата, в котором начальное состояние отмечено символом S, а конечное состояние, соответствующее концу разбора лексемы – символом F. На рис.2.1 приведены графы конечных автоматов для распознавания лексем «идентификатор» и «целое число без знака».

2. Объединить начальные и конечные состояния отдельных конечных автоматов (рис. 2.2). Если построенный таким образом конечный автомат является недетерминированным, преобразовать его в детерминированный конечный автомат (ДКА). Граф полученного ДКА называется диаграммой лексического анализатора.

3. Разработать структуры данных (формат таблиц) для хранения лексем различных типов и структуру данных для представления токенов. Заметим, что разработанные на этапе лексического анализа структуры данных будут уточняться на этапе синтаксического анализа.

Рис. 2.1 Рис. 2.2

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

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