Отчет по лабораторной работе
"Эмуляция директивы DB макроассемблера"

по курсу "Функциональное программирование"



Выполнил: ст-т группы 6-19-2 Сибгатуллин Н.Р.






Содержание:


  1. ПОСТАНОВКА ЗАДАЧИ
  2. ПРОЕКТИРОВАНИЕ РЕШЕНИЯ
  3. АЛГОРИТМЫ ФУНКЦИЙ
    1. Алгоритм функции Handle
    2. Алгоритм функции DB
    3. Алгоритм функции New_State
    4. Алгоритм функции Get_Available_Class
    5. Алгоритм функции Class_Of_Char
    6. Алгоритм функции Class_Of_Char_
    7. Алгоритм функции Get_Number
    8. КРАТКОЕ ОПИСАНИЕ НЕКОТОРЫХ ИСПОЛЬЗУЕМЫХ ФУНКЦИЙ
    9. ВЫВОДЫ
    10. ТЕКСТЫ ФУНКЦИЙ ПРИМЕРЫ РЕЗУЛЬТАТОВ






    1.ПОСТАНОВКА ЗАДАЧИ

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

    Синтаксис директивы DB:

    Директива_DB ::= DB операнд

    операнд ::= строка | выражение

    операнд ::= операнд | операнд , операнд

    строка ::= ' <символы> '

    выражение ::= счетчик DUP ( операнд )

    счетчик ::= <цифра> | <цифра>счетчик

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

    Пример:

    входная строка-операнд:

    "3DUP('def', 2DUP('ab'),'l'),'ttt'"

    выходная строка-результат:

    "defababldefababldefabablttt"


    2.ПРОЕКТИРОВАНИЕ РЕШЕНИЯ


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

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

    Таблица 2.1.Таблица классов символов

    КлассСимволыОписание
    1пробелпробел
    2' (апостроф)ограничители строки
    30, 1, 2, 3, 4,
    5, 6, 7, 8, 9
    цифра
    4, (запятая)разделитель элементов
    5D, dсимвол D цепочки DUP
    6U, uсимвол U цепочки DUP
    7P, pсимвол P цепочки DUP
    8( (лев.скобка)начало операнда для DUP
    9) (пр.скобка)конец операнда для DUP
    0остальные символы,
    не вошедшие в дан-
    ный столбец этой
    таблицы
    другие символы

    В таблице 2.2 представлены состояния конечного автомата.


    Таблица 2.2.Таблица состояний конечного автомата

    СостояниеОписание
    0состояние ошибки
    1пропуск пробелов
    2считывание строки
    3поиск следующего элемента
    4считывание числа (счетчика)
    5поиск D или d
    6поиск U или u
    7поиск P или p
    8поиск левой скобки (
    Псевдосостояния
    -1выход из процедуры обработки строки
    -2рекурсивный вызов процедуры обработки
    строки (обработка операнда DUP)

    Псевдосостояния не переводят конечный автомат в какое-либо конкретное состояние, переход в псевдосостояние вызывает выполнение каких-либо действий: либо возврат из процедуры обработки строки, либо рекурсивный вызов процедуры обработки строки.

    В таблицу 2.1 (таблица классов символов) не включен псевдосимвол - конец строки. Обозначим его как $, такое же обозначение примем и для класса, к которому относится этот символ.

    Таблица 2.3 представляет таблицу переходов конечного автомата. Строка определяет некоторое текущее состояние конечного автомата, столбцы - классы входных символов. Каждый элемент таблицы переодов конечного автомата определяет следующее состояние, в которое должен перйти конечный автомат из некоторого состояния при поступлении символа, относяшегося к некоторому классу.


    Таблица 2.3.Таблица переходов конечного автомата

    Состояние
    конечного
    автомата
    Класс входного символа
    0123456789$
    000000000000
    101240000000
    222322222220
    3030010000-1-1
    405040600000
    500000600000
    600000070000
    700000008000
    808000000-200

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


    Таблица 2.4.Таблица допустимых классов входных символов для состояний конечного автомата

    СостояниеМножество допустимых классов входных символов
    11, 2, 3
    21, 3, 4, 5, 6, 7, 8, 9, 0
    31, 4, 9
    41, 3, 5
    51, 5
    66
    77
    81, 8

    При поступлении того или иного входного символа, конечный автомат, находясь в некотором состоянии, должен совершать определенные действия, например:

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

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

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

    При переходе в псевдосостояние -1 должен произойти выход из процедуры обработки входной последовательности символов с возвратом результата.

    При переходе в псевдосостояние -2 автомат должен произвести следующие действия:

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

    На основании всех приведенных выше утверждении необходимо реализовать конечный автомат средствами языка ЛИСП.



    3.АЛГОРИТМЫ ФУНКЦИЙ


    3.1.Алгоритм функции Hande


    Обозначения:

    а) входные данные:
    String - последовательность входных символов;
    Index - индекс символа во входной строке, с которого необходимо начать обработку;
    б) другие:
    State - состояние конечного автомата;
    Class - класс входного символа;
    NumList- список цифр, составляющих число-счетчик;
    ResString- результирующая строка символов;
    C - входной символ;
    AvailClass- список допустимых классов символа для текущего состояния конечного автомата;
    N - счетчик;
    NewI - новое значение индекса обрабатываемого символа во входной строке, возвращаемое при рекурсивном вызове функции Handle.
    1.Начало функции HANDLE(String,Index);
    2.State=1; I=Index; Numist=NIL; ResString='';
    3.Если State=0 или I>=Length(String), то переход к пункту 21, иначе пункт 4;
    4.Если State=-1, то переход к пункту 21;
    5.Если State=-2, то переход к пункту 6, иначе пункт 11;
    6.N=Get_Number(Numist);
    7.(NewI,S)=Handle(String,I);
    8.Если N>0, то переход к пункту 9, иначе пункт 10;
    9.ResString=ResString+S; N::=N-1; переход к пункту 8;
    10.State=2; Class=1; I::=NewI-1; переход к пункту 20;
    11.C=Char(String,I);
    12.AvailClass=Get_Available_Class(State);
    13.Если С принадлежит AvailClass, то переход к пункту 14, иначе пункт 20;
    14.Если State=1 и Class=3, то переход к пункту 15, иначе пункт 16;
    15.Numist::=Char-Code(C)-#x30; переход к пункту 20;
    16.Если State=2, то переход к пункту 17, иначе пункт 18;
    17.ResString::=ResString+C; переход к пункту 20;
    18.Если State=4 и Class=3, то переход к пункту 19, иначе пункт 20;
    19.NumList::=NumList+(Char-Code(C)-#x30));
    20.I::=I+1; State::=New_State(State,Class); переход к пункту 3;
    21.Возвращаемое значение список (I-1,ResString);
    22.Конец функции Handle.

    3.2.Алгоритм функции DB


    Обозначения:

    а) входные данные:
    String - входная последовательность символов
    б) другие:
    Index - индексный номер символа, на котором закончилась обработка входной строки;
    Result - результирующая строка, полученная в результате обработки входной последовательности символов.
    1.Начало функции DB(String);
    2.(Index,Result)=Handle(String,0);
    3.Index::=Index+1;
    4.Если Index<Length(String), то переход к пункту 5, иначе пункт 6
    5.Вывод строки "Syntax error"; переход к пункту 7;
    6.Вывод строки Result;
    7.Возвращаемое значение NIL;
    8.Конец функции DB.

    3.3.Алгоритм функции New_State


    Обозначения:

    а) входные данные:
    Old_State - текущее состояние конечного автомата;
    Class - класс входного символа, поступившего на вход конечного автомата;
    б) другие:
    ST - таблица состояний конечного автомата;
    Row - строка таблицы состояний конечного автомата, соответствующей состоянию Old_State;
    New - новое состояние конечного автомата, соответствующего элементу строки Row для класса входного символа Class.
    1.Начало функции New_State(Old_State,Class);
    2.Row=Nth(Old_State,ST);
    3.New=Nth(Class,Row);
    4.Возвращаемое значение New;

    3.4.Алгоритм функции Get_Avaiable_Class


    Обозначения:

    а) входные данные:
    State - состояние конечного автомата;
    б) другие:
    ASCT - таблица допустимых классов символов для состояний конечного автомата;
    Class - список номеров классов символов, которые допустимы для данного состояния конечного автомата State.
    1.Начало функции Get_Available_Class(State);
    2.Class=Nth(State-1,ASCT);
    3.Возвращаемое значение Class;
    4.Конец функции Get_Available_Class.

    3.5.Алгоритм функции Cass_Of_Char


    Обозначения:

    а) входные данные:
    Char - символ, класс которого необходимо определить;
    б) другие:
    SCT - таблица классов символов;
    Class - класс символа Char.
    1.Начало функции Class_Of_Char(Char);
    2.Class=Class_Of_Char_(SCT,Char,1);
    3.Возвращаемое значение Class;
    4.Конец функции Class_Of_Char.

    3.6.Алгоритм функции Cass_Of_Char_


    Обозначения:

    а) входные данные:
    Table - таблица классов символов;
    Char - символ, класс которого необходимо определить;
    Class - предполагаемый класс символа;
    б) другие:
    Row - первая строка таблицы классов символов;
    Tail - часть таблицы классов символов без первой строки.
    1.Начало функции Class_Of_Char_(Table,Char,Class);
    2.Если таблица Table пуста, то переход к пункту 3, иначе пункт 4;
    3.Class=0; переход к пункту 8;
    4.Row=CAR(Table);
    5.Если Char принадлежит к Row, то переход к пункту8, иначе пункт 6;
    6.Tail=CDR(Table);
    7.Class::=Class_Of_Char_(Tail,Char,Class+1);
    8.Возвращаемое значение Class;
    9.Конец функции Class_Of_Char.

    3.7.Алгоритм функции Get_Number


    Обозначения:

    а) входные данные:
    List_Of_Digits- список цифр, составляющих число (в обратном порядке);
    б) другие:
    Digits- первая цифра списка цифр числа;
    Tail - часть списка цифр числа без первой цифры;
    X - результирующее число.
    1.Начало функции Get_Number(List_Of_Digits);
    2.Если список List_Of_Digits пуст, то переход к пункту 3, иначе пункт 4;
    3.X=0; переход к пункту 7;
    4.Digit=CAR(List_Of_Digits);
    5.Tail=CDR(List_Of_Digits);
    6.X=Digit+10*Get_Number(Tail);
    7.Возвращаемое значение X;
    8.Конец функции Get_Number.






    4.КРАТКОЕ ОПИСАНИЕ НЕКОТОРЫХ ИСПОЛЬЗУЕМЫХ ФУНКЦИЙ


    Char-Code - возвращает код символа;
    Char - возвращает символ из строки по индексу;
    Do - организация цикла;
    DoTimes - организация цикла;
    ength - возвращает длину выражения (строки или списка);
    Nth - выделение N-ого элемента из списка;






    5.ВЫВОДЫ



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

    Средства рекурсии языка позволяют эффективно реализовывать сложные алгоритмы.

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

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




    6.ТЕКСТЫ ФУНКЦИЙ



    ;;  Пример входной строки:
    ;;
    ;;    (DB " 'abc','bcd',3dup('cde',3 dup ('def' ) ), 'zxy' ")
    ;;
    ;;  Результат:
    ;;
    ;;    'abcbcdcdedefdefdefcdedefdefdefcdedefdefdefzxy'
    ;;              +-------+   +-------+   +-------+
    ;;           +----------++----------++----------+
    
    
    (DeFun DB (String)
    ;; Лабораторная работа N1. Функциональное программирование
    ;;  Эмуляция директивы DB макро-ассемблера
      (SetQ Res (Handle String 0))
      (If (< (1+ (CAR Res)) (Length String))
        (PrintString "Syntax error")
        (PrintString (CADR Res))
      )
    )
    
    (DeFun PrintStringToStream (String Stream)
    ;; Вывод строки символов String в поток вывода Stream
      (DoTimes (I (ength String))
        (PrinC (Char String I) Stream)
      )
    )
    
    (DeFun PrintString (String)
    ;; Вывод строки символов String на экран
      (DoTimes (I (Length String))
        (PrinC (Char String I))
      )
    )
    
    (SetQ SCT '(;; Таблица классов символов
      (#\Space) ;;   1 - пробел
      (#\')     ;;   2 - апостроф (кавычка)
      (#\0 #\1 #\2 #\3 #\4 #\5 #\6 #\7 #\8 #\9)  ;; 3 - цифра
      (#\,)     ;;   4 - запятая
      (#\D #\d) ;;   5 - символ D
      (#\U #\u) ;;   6 - символ U
      (#\P #\p) ;;   7 - символ P
      (#\( )    ;;   8 - левая (открывающая) скобка
      (#\) )    ;;   9 - правая (закрывающая) скобка
      )         ;;   0 - другой символ
    )
    
    (SetQ ASCT '(  ;; Таблица допустимых классов символов
                   ;;  в некотором состоянии конечного автомата
      (1 2 3)      ;;   1 - пропуск пробелов
      (1 3 4 5 6 7 8 9 0) ;; 2 - считывание символов, ограниченных апострофами
      (1 4 9)      ;;   3 - поиск следующего элемента
      (3 1 5)      ;;   4 - считывание числа
      (1 5)        ;;   5 - поиск D/d
      (6)          ;;   6 - поиск U/u
      (7)          ;;   7 - поиск P/p
      (1 8)        ;;   8 - поиск, открывающей скобки (
      )
    )
    
    (SetQ ST '(              ;; Таблица состояний конечного автомата
    ;; 0 1 2 3 4 5 6 7 8 9   -  класс символа
    ;; -------------------
      (0 0 0 0 0 0 0 0 0 0)  ;;  0 - состояние ошибки
      (0 1 2 4 0 0 0 0 0 0)  ;;  1 - пропуск пробелов
      (2 2 3 2 2 2 2 2 2 2)  ;;  2 - считывание строки
      (0 3 0 0 1 0 0 0 0 -1) ;;  3 - поиск следующего символа
      (0 5 0 4 0 6 0 0 0 0)  ;;  4 - считывание числа
      (0 0 0 0 0 6 0 0 0 0)  ;;  5 - поиск D/d
      (0 0 0 0 0 0 7 0 0 0)  ;;  6 - поиск U/u
      (0 0 0 0 0 0 0 8 0 0)  ;;  7 - поиск P/p
      (0 8 0 0 0 0 0 0 -2 0) ;;  8 - поиск открывающей левой скобки (
      )                      ;; -1 - выход из процедуры
                             ;; -2 - рекурсивный вызов процедуры
    )
    
    (DeFun New_State (Old_State Class)
    ;; Определение нового состояния конечного автомата
    ;; исходя из предыдущего состояния Old_State,
    ;; класса входного символа Class и таблицы
    ;; состояний конечного автомата ST.
    ;; Возвращает целое число.
      (Nth Class (Nth Old_State ST))
    )
    
    (DeFun Get_Available_Class (State)
    ;; Определение множества классов входных символов,
    ;; допустимых для некоторого состояния State конечного
    ;; автомата по таблице допустимых классов символов ASCT.
    ;; Возвращает список целых чисел.
      (Nth (1- State) ASCT)
    )
    
    (DeFun Class_Of_Char (Char)
    ;; Определение класса символа Char по таблице
    ;; классов символов SCT.
    ;; Возвращает целое число.
      (Class_Of_Char_ SCT Char 1)
    )
    
    (DeFun Class_Of_Char_ (Table Char Class)
    ;; Определение класса символа Char по таблице
    ;; классов символов SCT.
    ;; Возвращает целое число.
      (Cond ((Null Table) 0)
            ((Member Char (CAR Tabe)) Class)
            (T (Class_Of_char_ (CDR Table) Char (1+ Class)))
      )
    )
    
    (DeFun Get_Number (List_Of_Digits)
    ;; Вычисление значения числа, представленного
    ;; списком цифр его составляющих List_Of_Digits.
    ;; Цифры в списке должны располагаться в обратном порядке,
    ;; относительно того порядка, в котором они располагаются в числе.
    ;; Возвращает целое число.
      (Cond ((Null List_Of_Digits) 0)
            (T (+ (CAR List_Of_Digits)
                  (* 10 (Get_Number (CDR List_Of_Digits))))
            )
      )
    )
    
    (DeFun Handle (String Index)
    ;; Обработка входной строки String, начиная с символа,
    ;; имеющего порядковый номер Index.
    ;; Возвращает список, состоящий из двух элементов:
    ;;    первый элемент - индекс символа, на котором закончилась
    ;;                     обработка строки
    ;;    второй элемент - результирующая строка символов
      (Prog ((Class 0) (Numist NIL) (FS (Make-String-Output-Stream)))
        ;; Обработка строки
        (Return (List
          (Do ((State 1 (New_State State Class)) (I Index (1+ I)))
            ((Or (= State 0) (>= I (Length String))) (1- I))
            (Cond
               ((= State -1) (SetQ State 0))
               ((= State -2) (Prog ()
                               (SetQ Res (Handle String I))
                               (DoTimes (N (Get_Number NumList))
                                 (PrintStringToStream (CADR Res) FS))
                               (SetQ I (1- (CAR Res)))
                               (SetQ State 3)
                               (SetQ Class 1)
                               (SetQ NumList NIL)
                             )
               )
               (T (Prog ((C (Char String I)))
                    (SetQ Class (Class_Of_Char C))
                    (If (Member Class (Get_Available_Class State))
                      (Cond
                        ((= State 1) (If (= Class 3)(SetQ I (1- I))))
                        ((= State 2) (PrinC C FS))
                        ((= State 3) NIL)
                        ((= State 4)
                          (If (= Class 3)
                            (SetQ NumList (Cons (- (Char-Code C) #x30) NumList))
                           )
                        )
                        ((= State 5) NIL)
                        ((= State 6) NIL)
                        ((= State 7) NIL)
                        ((= State 8) NIL)
                        (T (SetQ State 0))
                      )
                    )
                  )
               )
            )
          ) #| Do |#
             (Get-Output-Stream-String FS))
        ) #| Return |#
        (Close FS)
      )
    )
    





    Сибгатуллин Н.Р. , студент ИжГТУ , 1997.
    E-mai : nail@ivt