2.2.2. Определение синтаксиса лексем
Лексический анализ удобно выполнять на основе детерминированного конечного преобразователя, поэтому синтаксис лексем должен быть описан с помощью автоматных грамматик.
Определение автоматных грамматик, описывающих синтаксис лексем рекомендуется выполнять в следующем порядке:
Разбить литеры, с помощью которых записываются программы на входном языке, на классы. В один класс помещаются литеры, которые одинаковым образом используются для образования лексем. Примерами классов литер являются: латинская буква, двоичная цифра, десятичная цифра, символ «=».
Составить автоматные грамматики, описывающие синтаксис лексем, при условии, что терминальными символами грамматики являются классы литер, а начальным символом грамматики – символ S.
Следующие правила автоматной грамматики, в которой буква – класс «латинская буква», цифра – класс «цифра», - класс, включающий все литеры, за исключением латинских букв и цифр, описывают синтаксис идентификатора:
|
S |
|
буква Id |
|
Id |
|
буква Id |
|
Id |
|
цифра Id |
|
Id |
|
, |
2.2.3. Построение диаграммы лексического анализатора
Построение диаграммы лексического анализатора выполняется в следующей последовательности:
Для каждой лексемы построить граф конечного автомата, в котором начальное состояние отмечено символом S, а конечное состояние, соответствующее концу разбора лексемы – символом F. На рис. 2.1 приведены графы конечных автоматов для распознавания лексем «идентификатор» и «целое число без знака».
Объединить начальные и конечные состояния отдельных конечных автоматов (рис. 2.2). Если построенный таким образом конечный автомат является недетерминированным, преобразовать его в детерминированный конечный автомат (ДКА). Граф полученного ДКА называется диаграммой лексического анализатора.
3. Разработать структуры данных (формат таблиц) для хранения лексем различных типов и структуру данных для представления токенов. Заметим, что разработанные на этапе лексического анализа структуры данных будут уточняться на этапе синтаксического анализа.
Рис. 2.1 Рис. 2.2
4. Определить внешние спецификации процедур (функций), описывающих семантику перевода исходного текста программы, представленного в виде строки литер, в строку токенов. К таким процедурам относятся процедуры чтения литеры из входного потока и определения ее класса, формирования очередной лексемы и определения ее типа, поиска (записи) лексемы в соответствующей таблице, формирования токена и записи его в выходной поток.
Включить описание семантики лексического анализа в диаграмму лексического анализатора, нагрузив ребра графа ДКА именами процедур (функций), которые должны выполняться при переходах между состояниями.