Модуль лексического разбора.

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

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

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

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

ПРОГРАММА НА ВСТРОЕННОМ ЯЗЫКЕ

( строковая переменная PVJA)

ВВОДД= A:\ISX; TECT= ЭКРАН; ВЕДОМ= ИТОГИ; СОХР= ДИСКЕТА;

Управляющий Вектор

вектор параметров

(массив YV) (массив PAR)

1 A:\ISX

3 ЭКРАН

5 ИТОГИ

7 ДИСКЕТА

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

Детерминированным конечным автоматом называется упорядоченная система из пяти символов

А = ( X, S, So, B, F), где

Х - множество входных символов;

S - множество внутренних состояний;

So - начальное состояние;

B - функция, отображающая переход в новое состояние;

F - заключительное состояние.

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

В клетках таблицы определяется следующая информация:

Во-первых, новое состояние, в которое переходит конечный автомат;

Во-вторых, функция, отображающая переход в новое состояние.

Например, для разбора ранее приведенной программы на входном языке таблица конечного автомата будет иметь вид:

Внутренние состояния Входные символы
ВВОДД ВВОДК ТЕСТ ПРОСМ ВЕДОМ РАСП СОХР   = Пробел     ; Конец стpоки Неопоз. символ
Sost=0 1/F1 1/F1 1/F1 - - Kv=0 Kv=4
Sost=1 - - - 2/F2 - Kv=5 Kv=6
Sost=2 - - - - 0/F4 Kv=7 2/F3

Функции, представленные в таблице имеют значение:

F1 - формирование управляющего вектора;

F2 - поиск начала параметра;

F3 - формирование параметра;

F4 - завершение формирования параметра.

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

X = {ВВОДД,ВВОДК,ТЕСТ,ПРОСМ,ВЕДОМ,РАСП,СОХР, =, , ;}

S = {SOST = 0, SOST = 1, SOST = 2}

So = {SOST = 0}

B = {F1, F2, F3}

F = {SOST = 0}

Разберем работу представленной модели конечного автомата.

Представленная программа на встроенном языке разбивается на совокупность входных символов. Входные символы поступают на вход системы и в зависимости от состояния системы вызывают определенные действия.

В рассматриваемом примере первоначально на вход системы поступает входной символ "ВВОДД". Начальное внутреннее состояние системы SOST = 0. Поступление входного символа "ВВОДД", при внутреннем состоянии SOST=0 вызовет переход в состояние 1 и выполнение функции F1.

Следующий входной символ "=" поступает на вход системы, когда внутреннее состояние системы SOST = 1. Поступление символа "=" вызовет переход системы в состояние 2. В то время, когда внутреннее состояние системы будет равно «2» на вход системы поступит символ ";". При поступлении данного входного символа будет выполнена функция формирования вектора параметров и система перейдет во внутреннее состояние SOST = 0.

Программная реализация модели конечного автомата может быть обеспечена с помощью операторов типа CASE.

Реализация блока лексического разбора на основе модели конечного автомата может иметь вид:

ProcedureLan (PVJA: String; {Программанавстроенномязыке}

VarYV: T_YV; {Управляющийвектор}

VarPAR: T_PAR; {Векторпараметров}

Var Ksl: Integer; {Количество

расшифрованныхсловПВЯ}

Var Tinf: TypeTinf {Таблицаинформатора});

{ Блоклексическогоразбора}

Var

Slov: Array[1..7] of String;{Терминальный

словарь}

Kts: Integer; {Количество элементов в

терминальном словаре}

Sost: Integer; {Состояние системы}

Stroka: String; {Рабочие переменные}

J,L,Nom,Ls,Ln: Integer;

Begin

With Tinf Do

Begin

PB:=1;

Kv:=0;

Ksl:=0;

Kts:=7;

Sost:=0;

Slov[1]:= 'ВВОДД';

Slov[2]:= 'ВВОДК';

Slov[3]:= 'ТЕСТ';

Slov[4]:= 'ПРОСМ';

Slov[5]:= 'ВЕДОМ';

Slov[6]:= 'РАСП';

Slov[7]:= 'СОХР';

J:=1;

Ln:= Length (PVJA);

While (J<=Ln) And (Kv=0) Do

Begin

Stroka:= Copy(PVJA, J, Ln-J+1);

If Copy(Stroka, 1, 1) = ' ' Then

J:=J+1

Else

Begin

Case Sost of

0: Begin {Поископератора}

Ls:= 0;

For L:= 1 to Kts Do

Begin

Nom:= Pos(Slov[L], Stroka);

If Nom = 1 Then

Begin

Ksl:= Ksl + 1;

YV[Ksl]:= L ;

PAR[Ksl]:= ' ';

Ls:= Length(Slov[L]);

J:= J + Ls;

Sost:= 1;

End;

End;

IfLs = 0 Then {Операторненайден}

Kv:= 4;

End;

1: Begin {Поиск разделителя}

If Copy(Stroka, 1, 1) = '=' Then

Begin

Sost:= 2;

J:= J + 1;

End

Else Kv:= 6;

End;

2: Begin {Засылкапараметра}

If Copy(Stroka, 1, 1) = ';' Then

Begin

Sost:= 0;

J:= J + 1;

End

Else

Begin

Par[Ksl]:= Par[Ksl]+ Copy(Stroka,1,1);

J:= J +1 ;

End;

End;

End;{Case}

End; {Else}

End; {While }

If (Sost = 1) And (Kv = 0) Then KV:= 5;

If (Sost = 2) And (Kv = 0) Then Kv:= 7;

End; {With}

End; {Procedure}

Наши рекомендации