Лекция на тему «Внутреннее проектирование и разработка программных средств». 5.1 Модуль лексического разбора.



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

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

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

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

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

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

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

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

 

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

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

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

1                                             A:\ISX

3                                            ЭКРАН

5                                           ИТОГИ

7                                        ДИСКЕТА

 

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

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

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

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

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

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

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

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

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

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

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

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

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

mesi-8
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.

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

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

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

      Var PAR: 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;

        If Ls = 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}

5.2 Модуль синтаксического анализа

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

В зависимости от поставленной задачи блок синтаксического анализа обеспечивает следующие действия:

во-первых, контролирует соответствие управляющего вектора   графу предметной области;

во-вторых, обеспечивает использование аппарата умолчания;

в-третьих, обеспечивает использование макрокоманд.

Контроль соответствия управляющего вектора графу предметной области позволяет выявить следующие ошибки в программе на входном языке:

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

Во-вторых, управляющий вектор не содержит завершающих этапов обработки информации (незавершенная программа);

В-третьих, в управляющем векторе пропущены промежуточные этапы;

В-четвертых, управляющий вектор содержит дублирующие участки;

В-пятых, в управляющем векторе содержится сочетание различных ошибок.

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

Пример проверки соответствия управляющего вектора графу предметной области:

 

mesi-9Процедура, реализующая модуль синтаксического анализа, имеет следующий вид:

Procedure San ( YV: T_YV; Ksl: Integer;

           Var  Tinf: TypeTinf) ;

 {Блок синтаксического анализа}

 Var

  GPO: Array[1..7,1..2] of Integer; {Граф предметной области}

  N_VER: Integer;{Номер начальной вершины}

  K_VER: Integer;{Номер конечной вершины}

  I: Integer;

 Begin

  With Tinf Do

  Begin

    PB:= 2;

    Kv:= 0;

   {Загрузка ГПО}

   GPO[1,1]:= 1; GPO[1,2]:= 2;

   GPO[2,1]:= 1; GPO[2,2]:= 2;

   GPO[3,1]:= 2; GPO[3,2]:= 3;

   GPO[4,1]:= 2; GPO[4,2]:= 3;

   GPO[5,1]:= 3; GPO[5,2]:= 4;

   GPO[6,1]:= 3; GPO[6,2]:= 4;

   GPO[7,1]:= 4; GPO[7,2]:= 5;

   N_VER:= 1;

   K_VER:= 5;

   I:=1;

   WHILE (I<=KSL) and (KV=0) Do

   Begin

    If GPO[ YV[I], 1] = N_VER

     Then  N_VER:= GPO[ YV[I], 2]

     Else Kv:= 8;

     I:= I+ 1;

    END;

   If (N_VER<>K_VER) AND (KV=0) Then KV:= 16;

 End; {WITH}

 End;

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

Во-первых, вставкой в управляющий вектор одиночного недостающего элемента;

Во-вторых, вставкой в управляющий вектор совокупности недостающих элементов.

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

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

 

mesi-10Недостающий элемент, т.е. код 3, определяющий дугу, соединяющую вторую и третью вершину, вставляется в управляющий вектор.

Для решения задачи может быть использована следующая совокупность команд:

{фрагмент программного кода}

If GPO [ YV [ I ] , 1 ] = N_VER

     Then  N_VER := GPO [ YV [ I ], 2 ]

     Else

     Begin

      {Ошибка в управляющем векторе}

       J:= 1; KeyD:= False;

       While (J <= 7) And (KeyD = False) Do

       Begin

         If (N_Ver = GPO[J,1]) And

         (GPO[YV[I],1] = GPO[J,2]) Then

         {Найдена дуга, которая позволяет

             исправить управляющий вектор}

         Begin

           For K:= Ksl DownTo I Do

            YV[K+1]:=YV[K];

           {Модификация управляющего вектора}

           YV[I]:=J; KeyD :=True;

           N_VER:= GPO[ YV[I], 2 ];

           KSL := KSL +1;

         End

       Else

         J:=J+1;

       End; {While J}

       If KeyD = False Then

       {Управляющий вектор исправить не удалось}

       Kv:= 8;

     End;{If}

     I:= I+ 1 ;

   End; {While I}

   If (N_VER <> K_VER) AND (KV = 0) Then

   Begin

      { Незавершенная программа на входном языке пакета}

       J:= 1; KeyD:= False;

       While (J <= 7) And (KeyD = False) Do

       Begin

       If (N_Ver=GPO[J,1]) And

          (K_Ver = GPO[J,2]) Then

         {Найдена дуга, которая позволяет

             исправить управляющий вектор}

         Begin

              KSL := KSL +1;

              Yv[KSL]:=J;

              KeyD:= True;

         End

       Else

         J:=J+1;

       End; {While J}

       If KeyD = False Then

       {Управляющий вектор исправить не удалось}

       KV:= 16 ;

   End;

 End; {WITH}

End;

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

If N_Ver = GPO [7,1] Then

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

Вставка совокупности элементов, как правило, предусматривает использование специальных алгоритмов поиска пути между различными узлами сети.

Использование макрокоманд позволяет сократить запись программы на входном языке, благодаря замене одной команды (макрокоманды) несколькими командами (макрорасширением).

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

Например, дана следующая таблица

Макрокоманда

Макрорасширение первая составляющая

Макрорасширение вторая составляющая

          50

              1        40

          40

             30

       7

          30               3

       5

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

mesi-7

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

Procedure San ( Var YV: T_YV; Var Ksl: Integer;

                                                    Var  Tinf: TypeTinf) ;

 {Вариант модуля синтаксического анализа

  с использованием макрокоманд}

 Var

  GPO: Array[1..7,1..2] of Integer; {Граф предметной области}

  N_VER: Integer;{Номер начальной вершины}

  K_VER: Integer;{Номер конечной вершины}

  I: Integer;

 {Описание таблицы макрокоманд}

  Macro_C: Array [1..30,1..3] Of Integer;

  Nmac: Integer; {Количество строк в таблице макрокоманд}

  KeyD: Boolean;

 Begin

  With Tinf Do

  Begin

    PB:= 2;

    Kv:= 0;

   Nmac:=3;

   Macro_C[1,1]:= 50; Macro_C[1,2]:=1; Macro_C[1,3]:=40;

   Macro_C[2,1]:= 40; Macro_C[2,2]:=30; Macro_C[2,3]:=7;

   Macro_C[3,1]:= 30; Macro_C[3,2]:=3; Macro_C[3,3]:=5;

   KeyD:=True;

  While KeyD Do

  Begin

   KeyD:= False;

   For I:= 1 To Ksl Do

     For J:= 1 To Nmac Do

     If Yv[I] = Macro_C[J,1] Then

     Begin

        KeyD:= True;

        Im:= I;

        Jm:= J;

     End;

    If KeyD Then

   Begin

      For K := Ksl DownTo Im Do

        Yv[K+1]:= Yv[K];

     Yv[Im]:= Macro_C[Jm,2];

     Yv[Im+1]:= Macro_C[Jm,3];

     Ksl:= Ksl+1;

   End;

End;

   {Загрузка ГПО и остальной программный код

блока синтаксического анализа}

                   …

End;

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

5.3 Модуль управления

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

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

Процедура, реализующая модуль управления, имеет следующий вид:

 Procedure Yprava (YV: T_YV;

                   Par: T_PAR;

                   Ksl: Integer;

               Var Tinf: TypeTinf);

 {Модуль управления}

 Var

   Parm: String;

   J,Kvo: Integer;

   Procedure Vvodd (PARM:String;

                  Var KVO:Integer);

  { Заглушка (STUB) обрабатывающей процедуры,

   предназначенной для ввода информации с внешнего

                                                                       носителя}

   Begin

      Kvo:=0 ;

   End;

    Procedure Vvodk (PARM:String;

                  Var KVO:Integer);

  { Заглушка (STUB) обрабатывающей процедуры,

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

   Begin

      Kvo:=0 ;

   End;

   Procedure TEST (PARM:String;

                  Var KVO:Integer);

  { Заглушка (STUB) обрабатывающей процедуры,

   предназначенной для тестирования информации}

   Begin

      Kvo:=0 ;

   End;

   Procedure PROSM (PARM:String;

                  Var KVO:Integer);

  { Заглушка (STUB) обрабатывающей процедуры,

   предназначенной для просмотра информации}

   Begin

      Kvo:=0 ;

   End;

   Procedure Vedom (PARM:String;

                  Var KVO:Integer);

  { Заглушка (STUB) обрабатывающей процедуры,

   предназначенной для получения ведомости}

   Begin

      Kvo:=0 ;

   End;

   Procedure RASP (PARM:String;

                  Var KVO:Integer);

  { Заглушка (STUB) обрабатывающей процедуры,

   предназначенной для распечатки информации}

   Begin

      Kvo:=0 ;

   End;

   Procedure Soxr (PARM:String;

                  Var KVO:Integer);

  { Заглушка (STUB) обрабатывающей процедуры,

   предназначенной для сохранения информации}

   Begin

      Kvo:=0 ;

   End;

 Begin

   With Tinf Do

   Begin

    PB:= 3; Kv:= 0;

    Kvo:= 0 ;

    For J:=1 to Ksl Do

    Begin

     Parm:= Par[J];

     CASE YV [J] OF

      1: Vvodd ( Parm,kvo);

      2: Vvodk ( Parm,kvo);

      3: Test ( Parm,kvo);

      4: Prosm ( Parm,kvo);

      5: Vedom ( Parm,kvo);

      6: Rasp ( Parm,kvo);

      7: Soxr ( Parm,kvo);

     End; {Case}

  if  Kv < Kvo then Kv:= Kvo;

  End; {For}

 End; {With}

 End; {Procedure}

5.4 Информатор

Информатор предназначен для выдачи сообщений о ходе решения задачи. Процедура, реализующая информатор, имеет следующий вид:

Procedure Inform (Tinf: TypeTinf);

 { Блок информатора}

 Begin

  With Tinf Do Begin

   Case PB Of

     1: Begin

        MESINF.LINES.ADD (‘Выполнен лексический разбор’);

        Case Kv Of

         0: MESINF.LINES.ADD (‘Нормальное завершение’);

         4: MESINF.LINES.ADD (‘Оператор задан неверно’);

5: MESINF.LINES.ADD(‘Отсутствует ПВЯ

                       после имени оператора’);

         6: MESINF.LINES.ADD(‘Разделитель задан неверно’);

         7:MESINF.LINES.ADD(‘Отсутствует символ конца оператора’);

        End;

        End;

     2: Begin

          MESINF.LINES.ADD(‘Выполнен синтаксический анализ’);

        Case Kv Of

         0: MESINF.LINES.ADD(‘Нормальное завершение’);

         8: MESINF.LINES.ADD(‘Неверный порядок операторов’);

        16: MESINF.LINES.ADD(‘Программа не завершена’);

        End;

        End;

3: MESINF.LINES.ADD(‘Выполнились

                                      обрабатывающие процедуры’);

    End; { Case }

    End; { With }

 End;

  5.5 Модуль помощи (HELP)

Организация помощи пользователю является непременным условием эффективного функционирования прикладного программного обеспечения.

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

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

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

В период освоения системы недостаточно подготовленный пользователь нуждается в постоянной поддержке (помощи) со стороны используемого программного обеспечения. Это значит, что на экране должна высвечиваться вспомогательная информация.

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

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

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

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

В простейшем случае модуль помощи может иметь вид.

Procedure TForm_VED.CMDHELPClick (Sender:  TObject);

{ Метод, обеспечивающий помощь пользователю}

Begin

LbHelp1.Caption:= ‘СТРУКТУРА ОПЕРАТОРА’;

LbHelp2.Caption:= ‘<ИМЯ ОПЕРАТОРА>=<ПАРАМЕТР>;’;

LbHelp1.Autosize:=True;

LbHelp2.Autosize:=True;

LbHelp1.Visible:= True;

LbHelp2.Visible:= True;

CMDPROCESS.SetFocus;

End;