Средствами языка функционального программирования ЛИСП необходимо написать функцию , имитирующую действия, производимые директивой ассемблера DB.
Элементы могут разделяться как одним пробелом так и несколькими. Перед открывающейся скобкой пробел может отсутствовать. Хвостовые пробелы отсутствуют.
В связи с необходимостью анализировать входную строку на предмет наличия управляющих цепочек (DUP), предлагается разработать конечный автомат, описываемый множеством входных символов, множеством состояний, таблицей переходов.
Входные символы представляется удобным разбить на классы символов. В таблице 2.1 приводятся все возможные классы символов, необходимые для решения поставленной задачи.
Класс | Символы | Описание |
---|---|---|
1 | пробел | пробел |
2 | ' (апостроф) | ограничители строки |
3 | 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 | цифра |
4 | , (запятая) | разделитель элементов |
5 | D, d | символ D цепочки DUP |
6 | U, u | символ U цепочки DUP |
7 | P, p | символ P цепочки DUP |
8 | ( (лев.скобка) | начало операнда для DUP |
9 | ) (пр.скобка) | конец операнда для DUP |
0 | остальные символы, не вошедшие в дан- ный столбец этой таблицы | другие символы |
В таблице 2.2 представлены состояния конечного автомата.
Состояние | Описание |
---|---|
0 | состояние ошибки |
1 | пропуск пробелов |
2 | считывание строки |
3 | поиск следующего элемента |
4 | считывание числа (счетчика) |
5 | поиск D или d |
6 | поиск U или u |
7 | поиск P или p |
8 | поиск левой скобки ( |
Псевдосостояния | |
-1 | выход из процедуры обработки строки |
-2 | рекурсивный вызов процедуры обработки строки (обработка операнда DUP) |
Псевдосостояния не переводят конечный автомат в какое-либо конкретное состояние, переход в псевдосостояние вызывает выполнение каких-либо действий: либо возврат из процедуры обработки строки, либо рекурсивный вызов процедуры обработки строки.
В таблицу 2.1 (таблица классов символов) не включен псевдосимвол - конец строки. Обозначим его как $, такое же обозначение примем и для класса, к которому относится этот символ.
Таблица 2.3 представляет таблицу переходов конечного автомата. Строка определяет некоторое текущее состояние конечного автомата, столбцы - классы входных символов. Каждый элемент таблицы переодов конечного автомата определяет следующее состояние, в которое должен перйти конечный автомат из некоторого состояния при поступлении символа, относяшегося к некоторому классу.
Состояние конечного автомата | Класс входного символа | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | $ | |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 2 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2 | 2 | 2 | 3 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 0 |
3 | 0 | 3 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | -1 | -1 |
4 | 0 | 5 | 0 | 4 | 0 | 6 | 0 | 0 | 0 | 0 | 0 |
5 | 0 | 0 | 0 | 0 | 0 | 6 | 0 | 0 | 0 | 0 | 0 |
6 | 0 | 0 | 0 | 0 | 0 | 0 | 7 | 0 | 0 | 0 | 0 |
7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 8 | 0 | 0 | 0 |
8 | 0 | 8 | 0 | 0 | 0 | 0 | 0 | 0 | -2 | 0 | 0 |
Из таблицы переходов можно определить множество классов символов, допустимых конечным автоматом, находящимся в том или ином состоянии. В таблице 2.4 представлены множества возможных классов входных символов для каждого состояния конечного автомата. В данной таблице отсутствуют данные для состояния ошибки и псевдосостояний по понятным причинам (не допустим ни один класс символов).
Состояние | Множество допустимых классов входных символов |
---|---|
1 | 1, 2, 3 |
2 | 1, 3, 4, 5, 6, 7, 8, 9, 0 |
3 | 1, 4, 9 |
4 | 1, 3, 5 |
5 | 1, 5 |
6 | 6 |
7 | 7 |
8 | 1, 8 |
При поступлении того или иного входного символа, конечный автомат, находясь в некотором состоянии, должен совершать определенные действия, например:
Автомат должен проверять класс входного символа на допустимость в данном состоянии до каких-либо действий. Если класс входного символа допустим в данном состоянии, то автомат должен выполнить надлежащие действия, в противном случае автомат должен перейти в состояние ошибки.
Особым случаем являются псевдосостояния конечного автомата: действия должны совершаться при переходе в псевдосостояние без каких-либо проверок входного символа.
При переходе в псевдосостояние -1 должен произойти выход из процедуры обработки входной последовательности символов с возвратом результата.
При переходе в псевдосостояние -2 автомат должен произвести следующие действия:
На основании всех приведенных выше утверждении необходимо
реализовать конечный автомат средствами языка ЛИСП.
Язык ЛИСП достаточно эффективен для реализации конечного автомата, т.е. применим для разбора входной последовательности символов.
Средства рекурсии языка позволяют эффективно реализовывать сложные алгоритмы.
Удобно возвращать функциями не одно значение, а целый список различных по типу значений.
Современный язык ЛИСП не должен считаться диковинным
языком и должен применяться там, где средства этого языка
приведут к упрощению написания сложных алгоритмов.
;; Пример входной строки: ;; ;; (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) ) )