Курсовая работа1 / ПРEIОП~1
.DOCПриложение1.
Построение диаграммы лексического анализатора.
1. ВЫДЕЛЕНИЕ ЛЕКСЕМ.
Выделим в языке лексемы:
<лексема>::=<ключевое_слово>|<идентификатор>|<целое_без_знака>|
<однолитерный_разделитель>|<двулитерный_разделитель>||
<строка>|<комментарии>
При этом будем полагать тип лексемы равным 1, если это ключевое_слово; 2, если это идентификатор; 3, если это целое_без_знака; 4, если это однолитерный разделитель; 5, если это двулитерный разделитель; 6, если это строка. При этом заметим, что для комментариев не нужно устанавливать тип лексемы, т.к. комментарии будут удалены из входного файла.
-
ПОСТРОЕНИЕ КОНЕЧНЫХ АВТОМАТОВ.
Для выделенных лексем запишем правила вывода и построим конечные автоматы:
-
идентификатор:
S -> l I
I -> l I
I -> d I
I -> e1
Здесь S - начальное состояние, I - конец_идентификатора, l - буква, d - цифра, e1 - любой символ, кроме буквы и цифры.
Конечный автомат:
Заметим, что лексема “ключевое_слово” обрабатывается аналогичным образом.
-
целое_без_знака:
S -> d C
C -> d C
C -> e2
Здесь S - начальное состояние, C - конец_целого_без_знака, d - цифра, e2 - любой символ, кроме цифры.
Конечный автомат:
-
однолитерный_разделитель:
S -> r
S -> *
S -> /
S -> :
S -> =
S -> <
S -> >
S -> ‘
Здесь S - начальное состояние, r - любой символ ,принадлежащий к
множеству {‘,’ ‘.’ ‘+’ ‘-‘ ‘(‘ ‘)’ ‘*’ ‘/’ ‘[‘ ‘]’ ‘=’ }
Конечный автомат для любого из этих правил вывода:
-
двулитерный_разделитель (рассмотрим на примере разделителя “:=”):
S -> : E
E -> =
Здесь S - начальное состояние, E - остаток двулитерного_разделителя (разделителя “:=”).
Конечный автомат:
-
комментарии:
S -> / S1
S1 -> * S2
S2 -> @ S2
S2 -> * S3
S3 -> /
Здесь S - начальное состояние, S1 - остаток двулитерного_разделителя (разделителя “/*”), S2 - остаток_комментария, @ - любой символ, S3 - остаток_ двулитерного_разделителя (разделителя “*/”).
Конечный автомат:
3. ВЫДЕЛЕНИЕ СЕМАНТИЧЕСКИХ ПРОЦЕДУР.
Выделим семантические процедуры, необходимые для осуществления лексического анализа:
-
Процедура ПОДГ - переходит к следующему входному символу, определяет его класс и устанавливает накапливаемую лексему в пустое состояние; в случае, если после обработки предыдущей лексемы последний обрабатываемый символ оказался началом новой лексемы, перехода к следующему входному символу не происходит.
-
Процедура ВКЛ - добавляет прочитанный символ к накапливаемой лексеме.
-
Процедура СЛЛ - переходит к следующему входному символу и определяет его класс.
-
Процедура ПОИСКТКС - вызывается для лексем типа 1 и 2; ищет накопленную лексему в таблице ключевых слов - в случае успеха устанавливает тип лексемы равным 1, иначе устанавливает тип лексемы равным 2 и записывает лексему в таблицу идентификаторов.
-
Процедура ПОИСКТТС1 - вызывается для лексем типа 4; ищет накопленную лексему в таблице однолитерных разделителей и устанавливает тип лексемы равным 4.
-
Процедура ПОИСКТТС2 - вызывается для лексем типа 5; ищет накопленную лексему в таблице двулитерных разделителей и устанавливает тип лексемы равным 5.
-
Процедура ЗАПТЧК - вызывается для лексем типа 3; записывает накопленную лексему в таблицу числовых констант.
-
Процедура ЗАПТТК - вызывается для лексем типа 6; записывает накопленную лексему в таблицу текстовых констант.
-
Процедура ФОРМВЫХ - формирует выход для очередной накопленной лексемы.
4. ПОСТРОЕНИЕ ДИАГРАММЫ ЛЕКСИЧЕСКОГО АНАЛИЗАТОРА.
По грамматикам, полученным в п.2 настоящего раздела, построим объединенный граф конечного автомата, объединяя начальные и заключительные состояния и нагружая ребра полученного автомата именами семантических процедур, описанных в п.3 настоящего раздела: