Грамматический разбор списков
Программа CH08EX10.PRO иллюстрирует грамматический разбор списков.
Процесс грамматического разбора работает, снижая проблему; в этом примере
мы преобразуем каждую строку в прологовую структуру, которую можно ис-
пользовать или оценить позднее.
Грамматический разбор в этом примере предназначен для очень прими-
тивного компьютерного языка. Хотя этот пример очень преждевременен для
данной стадии обучения, мы решили его все же привести именно здесь пото-
му, что грамматический разбор - одна из областей, где Турбо Пролог осо-
бенно силен. Если вы не чувствуете себя готовыми для этой темы, можно
пропустить этот пример и продолжить изучение без какой-либо потери целос-
тности.
/* Программа CH08EX10.PRO */
domains
toklist = string*
predicates
tokl(string,toklist)
clauses
tokl(Str,[H|T]):-
fronttoken(Str,H,Str1),!,
tokl(Strl,T).
tokl(_,[]).
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* Это вторая часть программы в грамматичкском разборе *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * */
domains
programm = programm(statementlist)
statementlist = statement*
/* * * * * * * * * * * * * * * * * * * * * *
* Определение из чего состоит утверждение *
* * * * * * * * * * * * * * * * * * * * * */
statement = if_Then_Else(exp, statement,statement);
if_Then(exp,statement);
while(exp,statement);
assing(id,exp)
/* * * * * * * * * * * * *
* Определение выражений *
* * * * * * * * * * * * */
exp = plus(exp,exp);
minus(exp,exp);
var(id);
int(integer)
id = string
predicates
s_program(toklist,program)
s_statement(toklist,toklist,statementlist)
s_exp(toklist,toklist,exp)
s_exp1(toklist,toklist,exp,exp)
s_exp2(toklist,toklist,exp)
clauses
s_program(List1,program(StatementList)):-
s_statementlist(List1,List2,StatementList),
List2=[].
s_statementlist([],[],[]):-!.
s_statementlist(List1,List4,[Statement|Program]):-
s_statement(List1,List2,Statement),
List2=[";"|List3],
s_ (List3,List4,Prgram).
s_statement["if"|List1],List7,if_then_else(Exp,
Snatement1,Statament2)):-
s_exp(List1,List2,Exp),
List2=["then"|List3],
s_statementList3,List4,Statement1),
List4=["else"|List5],!,
s_statementList5,List6,Statement2),
List6=["fi"|List7].
s_statement["if"|List1],List5,if_then(Exp,Statement)):-!,
s_exp(List1,List2,Exp),
List2=["then"|List3],
s_statementList3,List4,Statement),
List4=["fi"|List5].
s_statement["do"|List1],List4,while(Exp,Statement)):-!,
s_statementList1,List2,Statement),
List2=["while"|List3],
s_exp(List3,List4,Exp).
s_statement[Id|List1],List3,assing(Id,Exp)):-
isname(Id),
List1=["="|List2],
s_exp(List2,List3,Exp).
s_exp(LIST1,List3,Exp):-
s_exp2(List1,List2,Exp1),
s_exp1(List2,List3,Exp1,Exp).
s_exp1(["+"|List1],List3,Exp1,Exp):-!,
s_exp2(List1,List2,Exp2),
s_exp1(List2,List3,plus(Exp1,Exp2),Exp).
s_exp1(["-"|List1],List3,Exp1,Exp):-!,
s_exp2(List1,List2,Exp2),
s_exp1(List2,List3,minus(Exp1,Exp2),Exp).
s_exp1(List,List,Exp,Exp).
s_exp2([Int|Rest],Rest,int(I)):-str_int(Int,I),!.
s_exp2([Id|Rest],Rest,var(Id):-isname(Id).
Загрузите и запустите эту программу (нажав Alt-R), затем введите
следующее целевое утверждение:
Goal: tokl("b=2;if b then a=1 else a=2 fi; do a=a-1 while a;Ans),
s_program(Ans,Res).
Турбо Пролог вернет программную структуру:
Ans=["b","=","2",";","if","b","then","a","=","1",
"else","a","=","2","fi",";","do","a","="."a",
"-","1","while","a",";"
],
Res=program([assing("b",ins(2)),
if_then_else(var("b"),assing("a",int(1)),
assing("a",int(2))),
while(var("a"),assing("a",minus(var("a"),int(1))))
])
1 Solutions
Преобразование в этом примере разделяется на два этапа: просмотр и
грамматический разбор. Предикат tokl при просмотре принимает строку и
преобразует ее в список названий. Все предикаты с именем на s - это пре-
дикаты грамматического разбора. В этом примере входной текст - это паска-
леподобная программа, составленная из паскалеподобных утверждений. Язык
программирования понимает только некоторые утверждения : IF THEN ELSE, IF
THEN, DO WHILE и ASSIGMENT. Утверждения составляются из выражений и дру-
гих утверждений. Выражение: сложение, вычитание, переменные, целые.
Вот как работает эта программа:
1. Первое предложение просмотра s_program исследует список названий
и проверяет, можно ли их преобразовать в список утверждений.
2. Предикат s_statementlist проверяет, могут ли названия в списке
названий быть разделены на отдельные утвержденния, каждое заканчива-
ющееся точкой с запятой.
3. Предикат s_statement проверяет является ли первое название списка
названий правильным утверждением. Если да, то утверждение возвраща-
ется в структуру и оставшиеся названия возвращаются к предикату
s_statement.
a. Четыре s_statement предложения относятся к четырем типам ут-
верждений, которые понятны грамматическому разбору. Если первое
s_ statement предложение не может перевести список названий в IF
THEN ELSE утверждение, то работает следующее предложение, которое
пытается преобразовать список названий в утверждение IF THEN. Ес-
ли и это не удается, то следующее предложение преобразует список
названий в DO WHILE утверждение.
b. Если первые три s_statement предложения неудались, то послед-
нее предложение для этого предиката проверяет не является ли ут-
верждение assigment. Для этого предложение проверяет, является ли
первый терм - идентификатором, является ли второй терм - "=", яв-
ляются ли следующие термы - выражениями.
4. Предикаты s_exp, s_exp1 и s_exp2 работают также, проверяя являют-
ся ли первые термы выражениями, и если - да, то возвращают остаток
термов к s_statement.
Для более детального рассмотрения примера грамматического разбора
смотрите приложение "Анализатор предложений" (в книге Турбо Пролог. Спра-
вочное Руководство) и программу SEN_AN.PRO на вашем диске.
- Руководство пользователя турбо пролог 2.0.
- Часть 1: Введение в Турбо Пролог 2.0 18
- Часть 2. Изучение турбо пролога 2.0 44
- Глава 3. Основы пролога 44
- Глава 4. Программы турбо пролога 65
- Глава 5. Унификация и поиск с возвратом. 84
- Глава 6. Простые и составные объекты 116
- Глава 7. Повтор и рекурсия 132
- Глава 8. Списки и рекурсия 160
- Глава 9. Внутренняя база данных турбо пролога 180
- Глава 10. Трассировка и отладка 189
- Часть 3. Описание турбо пролога 2.0 203
- Глава 11. Арифметические вычисления и сравнения 203
- Глава 12. Запись, чтение и файлы 215
- Глава 13. Обработка строк в турбо прологе 240
- Глава 14. Окна в ваших программах 249
- Глава 15. Система внешних баз данных 269
- Глава 16. Программирование на системном уровне 298
- Глава 17. Графический интерфейс borland 309
- Глава 18. Примеры программ 347
- Глава 19. Сложные приемы программирования 365
- Введение
- О Прологе
- Для чего может быть использован Турбо Пролог?
- Чем Турбо Пролог отличается от других языков?
- Минимальные требования к системе
- Поддерживаемое оборудование
- О руководствах по Турбо Пролог 2.0
- Том I: Руководство пользователя
- Рекомендуемая литература
- Используемые шрифты
- Торговые марки.
- Как связаться с фирмой Borland.
- Часть 1 введение в турбо пролог 2.0 глава 1. Установка турбо пролога 2.0
- Что хранится на ваших дисках
- Теперь сделаем резервные копии
- Установка Турбо Пролога на вашу систему
- Установка на систему с гибкими магнитными дисками
- Установка на жесткий диск
- Использование данного руководства
- Глава 2. Начало
- Загрузка Турбо Пролога
- Краткое руководство по меню и "горячим" клавишам.
- Главное меню
- Спускающиеся меню
- "Горячие" клавиши и командные клавиши
- "Горячие" клавиши главного меню
- Командные клавиши редактора
- Командные клавиши компиляции
- Стирание текста
- Манипулирование текстовыми блоками
- Ваша первая программа на Турбо Прологе
- Ввод вашей программы в редактор
- Корректирование ввода
- Просмотр в редакторе
- Запуск вашей программы
- Что происходит, когда вы делаете синтаксическую ошибку
- Сохранение вашей программы на диске
- Просмотр файлов на диске
- Трассирование вашей программы
- Пользователям с гибкими магнитными дисками: создание автономных программ.
- Контроль установки системы
- Часть 2. Изучение турбо пролога 2.0 глава 3. Основы пролога
- ПрОграммирование в лоГике
- Предложения: Факты и Правила.
- Факты: То что известно
- Правила: То что вы можете получить из заданных фактов
- Запросы
- Совместное задание фактов, правил и запросов
- Переменные: основные положения
- Упражнения
- Из естественного языка в программы на Прологе
- Упражнения
- Предикаты (связи)
- Переменные (обобщенные предложения)
- Как переменные получают свои значения
- Анонимные переменные
- Цели (запросы)
- Составные цели: Конъюнкция и Дизъюнкция
- Комментарии
- Что такое Сопоставление?
- Глава 4. Программы турбо пролога
- Основные секции программы на Турбо Прологе
- Секция предложений
- Секция предикатов
- Как объявить предикат пользователя
- Имена предикатов
- Аргументы предикатов
- Секция доменов
- Примеры.
- Секция цели
- Подробнее о декларациях и правилах
- Задание типов аргументов при декларации предикатов
- Упражнения
- Арность (размерность)
- Синтаксис правил
- Ключевое слово Пролога "if" и "if" в других языках
- Автоматическое преобразование типов
- Другие секции программы
- Секция базы данных
- Секция констант
- Глобальные секции
- Директивы компилятора
- Директива include
- Директивы trace и shorttrace
- Глава 10 подробно объясняет трассирование, однако еще до того, как
- Глава 5. Унификация и поиск с возвратом.
- Сопоставление и унификация
- Поиск с возвратом.
- Поиск всех решений
- Упражнение на поиск с возвратом.
- Детальный обзор поиска с возвратом.
- Четыре основных принципа поиска с возвратом.
- Поиск с возвратом для внутреннего целевого утверждения
- Управление поиском решений.
- Использование предиката fail.
- Упражнения.
- Прерывание поиска с возвратом: отсечение.
- Как использовать отсечение.
- Предотвращение поиска с возвратом к предыдущей подцели в правиле.
- Предотвращение поиска с возвратом к следующему предложению.
- Детерминизм и отсечение.
- Пример, использующий отсечение
- Предикат not.
- Упражнения.
- Пролог с процедурной точки зрения.
- Как представлять факты и правила в качестве процедур
- Использование правил для условного ветвления (case).
- Представление проверки в правиле.
- Отсечение как goto.
- Возврат вычисленного значения.
- Глава 6. Простые и составные объекты
- Простые объекты данных.
- Переменные как объекты данных.
- Константы как объекты данных.
- Литеры.
- Составные объекты данных и функторы
- Унификация составных объектов.
- Использование знака равенства для унификации составных объектов.
- Рассмотрение нескольких значений как единое целое.
- Примеры использования функторов.
- Пример использования составных объектов.
- Упражнение.
- Объявление доменов составных объектов.
- Запись определений доменов: Обзор.
- Многоуровневые составные объекты.
- Пример, иллюстрирующий структуру предложения.
- Упражнения.
- Определения составных смешанных доменов.
- Аргументы множественных типов.
- Сравнение составных объектов.
- Глава 7. Повтор и рекурсия
- Процесс повторения
- Снова поиск с возвратом
- Упражнение
- Предварительные и последующие операции
- Упражнение
- Использование поиска с возвратом в замкнутых системах
- Упражнения
- Рекурсивные процедуры
- Что же все-таки делает компьютер?
- Преимущества рекурсии
- Оптимизация хвостовой рекурсии
- Как задать хвостовую рекурсию
- Упражение
- Как избежать хвостовой рекурсии
- На помощь приходит команда "cut"
- Использование аргументов в качестве переменных цикла
- Упражнения
- Рекурсивные структуры данных
- Деревья - как типы данных
- Обход дерева
- Создание дерева
- Бинарные поисковые деревья
- Сортировка на основе дерева
- Упражнения
- Глава 8. Списки и рекурсия
- Что такое списки?
- Объявление списков
- Голова и хвост списка
- Работа со списками
- Использование списков
- Печать списков
- Упражнение
- Подсчет элементов списка
- Упражнение
- Хвостовая рекурсия
- Упражнение
- Другой пример - изменения в списках
- Снова о хвостовой рекурсии
- Еще об изменении списков
- Принадлежность к списку
- Упражнение
- Объединение одного списка с другим: декларативное и процедурное программирование
- Рекурсии с процедурной точки зрения
- Упражнение
- Один предикат может иметь несколько вариантов использования
- Упражнение
- Немедленный поиск всех решений
- Составные списки
- Упражнение
- Грамматический разбор списков
- Заключение
- Глава 9. Внутренняя база данных турбо пролога
- Использование внутренней базы данных
- Объявление внутренней базы данных
- Обновление внутренней базы данных
- Занесение фактов во время исполнения
- Удаление фактов во время выполнения программы
- Удаление нескольких фактов сразу
- Считывание новых фактов из файла во время выполнения программы
- Сохранение базы данных с фактами во время работы программы
- Примеры
- Глава 10. Трассировка и отладка
- Синтаксическая проверка
- Трассировка
- Директива трассировки
- Пример использования директивы trace
- Трассировка в режиме оптимизации: shorttrace
- Трассировка указанных предикатов
- Пример использования директивы shorttrace
- Сохранение результатов трассировки
- Предикат trace
- Пример использования предиката trace
- Диалоговое управление трассировкой
- Состояние ( Status )
- Окно Трассировки ( Trace Window )
- Окно Редактора ( Edit Window )
- Предикаты, с особым значением в режиме трассировки
- Упражнение по трассировке
- Директивы компилятора, используемые для отладки
- Директивы check_determ и nondeterm
- Упражнение
- Директива diagnostics
- Директива nowarnings
- Собщения об ошибках во время выполнения программы
- Опции компилятора из меню
- Integer Overflow Check (Проверка целого)
- Stack Check (Проверка стека)
- Часть 3. Описание турбо пролога 2.0 глава 11. Арифметические вычисления и сравнения
- Арифметические выражения
- Операции
- Порядок вычислений
- Функции и предикаты
- Генератор случайных чисел
- Предикат random/1
- Предикат random/2
- Целочисленная и вещественная арифметика
- Равенство и предикат равенства
- Упражнения
- Сравнение символов, строк и идентификаторов
- Символы
- Идентификаторы
- Примеры, демонстрирующие предикат write
- Упражнение
- Предикат writef/*
- Турбо Пролог распознает следующие спецификаторы формата поля f:
- Примеры форматного вывода
- Предикат readln/1
- Предикаты readint/1, readreal/1 и readchar/1
- Предикат readterm/2
- Предикат file_str/2
- Предикат inkey/1
- Предикат keypressed/0
- Предикат unreadchar/1
- Примеры
- Упражнение
- Открытие и закрытие файлов
- Предикат openread/2
- Предикат readdevice/1
- Предикат writedevice/1
- Примеры
- Работа с файлами
- Примеры
- Предикат eof/1
- Предикат flush/1
- Предикат existfile/1
- Предикат deletefile/1
- Предикат renamefile/2
- Предикат disk/1
- Расширение базы данных с помощью файлов
- Работа с фактами, как с термами
- Примеры
- Глава 13. Обработка строк в турбо прологе
- Обработка строк
- Основные предикаты управления строкой
- Frontchar/3
- Fronttoken/3
- Frontstr/4
- Concat/3
- Str_lеn/2
- Str_char/2
- Str_int/2
- Str_real/2
- Upper_lower/2
- Примеры.
- Глава 14. Окна в ваших программах
- Основные операторы управления окном.
- Задание атрибутов экрана дисплея.
- Черно-белый дисплей.
- Цветной дисплей.
- Makewindow/8
- Пример.
- Shiftwindow/1
- Clearwindow/0
- Removewindow/0
- Cursor/2
- Пример.
- Игра в угадывание слов с использованием окон.
- Усовершенствованные предикаты обработки окон.
- Textmode/2
- Makewindow/11
- Existwindow/1
- Gotowindow/1
- Removewindow/2
- Resizewindow/0
- Resizewindow/4
- Пример.
- Framewindow/1
- Framewindow/4
- Colorsetup/1
- Scr_char/3
- Scr_attr/3
- Field_str/4
- Field_attr/4
- Window_str/1
- Window_attr/1
- Простая игра.
- Использование редактора и dir из программы.
- Editmsg/8
- Edit/2 и edit/13
- Аргументы предиката edit.
- Display/1
- Пример доступа к редактору и каталогу.
- Заключение.
- Глава 15. Система внешних баз данных
- Внешние базы данных в Турбо Прологе.
- Обзор: что такое внешние базы данных?
- Соглашения об именовании.
- Селекторы внешних баз данных.
- Домены, связанные с внешними базами данных.
- Указатели базы данных.
- Домен ref.
- Обработка целых баз.
- Db_create/3
- Db_open/3
- Db_copy/3
- Db_openinvalid/3
- Db_flush/1
- Db_close/1
- Db_delete/1
- Db_garbagecollect/1
- Db_btrees/2
- Db_chains/2
- Db_statistics/5
- Обработка цепочек.
- Chain_inserta/5 и chain_insertz/5
- Chain_insertafter/5
- Term_replace/4
- Term_delete/3
- Ref_term/4
- Пример полной программы.
- B-деревья.
- Страницы, порядок и длина ключа.
- Двойные ключи.
- Множественный просмотр.
- Стандартные предикаты для b-деревьев
- Bt_create/5
- Bt_open/3
- Bt_clost/2 и bt_delete/2
- Bt_statistics/8
- Key_insert/4 и key_delete/4
- Key_first/3, key_last/3 и key_search/4
- Key_next/3 и key_prev/3
- Key_current/4
- Пример: Доступ к базе данных через b-деревья
- Программирование внешних баз данных
- Просмотр базы данных
- Вывод содержания базы данных
- Создание защищенной базы данных
- Обновление базы данных
- Использование внутреннего указателя b-дерева.
- Использование key-search с дублируемыми ключами
- Изменение структуры базы данных.
- Глава 16. Программирование на системном уровне
- Доступ к операционной системе
- System/1
- System/3
- Пример:
- Envsymbol/2
- Date/3 и time/4
- Пример.
- Comline/1
- Операции на уровне бит
- Bitnot/2
- Bitand/3
- Bitor/3
- Bitxor/3
- Bitleft/3
- Bitright/3
- Упражнение:
- Доступ к аппаратуре: поддержка низкого уровня.
- Bios/3 и bios/4
- Ptr_dword/3
- Membyte/3 и memword/3
- Port_byte/2
- Примеры:
- Глава 17. Графический интерфейс borland
- Что такое bgi?
- Несколько слов о видео режимах.
- Несколько слов о полях вывода (графических окнах).
- Файл grapdecl.Pro
- Как начинать
- Инициализация и выключение системы bgi
- Предикаты
- Initgraph/5
- Detectgraph/2
- Getgraphmode/1
- Getmaxmode/1
- Graphdefaults/0
- Closegraph/0
- Restorecrtmode/0
- Текущая позиция (тп)
- Getlinesettings/3
- Окружности
- Circle/3
- Getarccoords/6
- Прямоугольники, многоугольники и полосы.
- Rectangle/4
- Bar3d/6
- Drawpoly/1
- Fillpoly/1
- Setfillpattern/2
- Getfillpattern
- Floodfill/3
- Пример заполнения области.
- Управление цветом.
- Палитра
- Цвет фона и цвет рисования.
- Управление цветом в cga.
- Низкое разрешение cga.
- Высокое разрешение cga.
- Предикаты палитры cga.
- Управление цветом в ega.
- Управление цветом в дисплеях системы rgb.
- Предикаты
- Шрифты: загружать или компоновать
- Предикаты
- Settstyle/3
- Setusercharsize/4
- Пример использования различных видов текста
- Экраны и поля вывода.
- Предикаты.
- Setviewport/5
- Getviesettings/5
- Управление пикселами и образами
- Предикаты
- Ограничения на использование драйвера 8514.
- Использование bgi
- Графические драйверы и символьные шрифты.
- Программа, загружающая драйверы
- Построение и запуск загружаемых .Exe файлов
- Сообщения bgi об ошибках
- Новые драйверы bgi
- Задача выбора кратчайшего пути
- Приключения в опасной пещере
- Моделирование элементов аппаратуры
- Ханойские башни.
- Деление слов на слоги
- Проблема расстановки n ферзей
- Использование клавиатуры.
- Чтение и распознавание клавиш
- Простой редактор полей
- Применение предиката inkey
- Глава 19. Сложные приемы программирования
- Ошибки, исключительные ситуации и прерывания
- Обработка исключительных ситуаций, связанных с ошибками
- Exit/o и exit/1
- Errorsg/4
- Обработка ошибок при чтении термов
- Consulterror/3
- Readtermerror/2
- Управление режимом break
- Break/1
- Breakpressed/0
- Углубленный контроль ошибок в .Exe файлах
- Criticalerror/4
- Fileerror/2
- Анализ потока параметров
- Контроль потока параметров
- Ссылочные типы
- Объявление ссылочных типов
- Ссылочные типы и массив trail
- Применение ссылочного типа
- Динамическое отсечение
- Примеры
- Применение ссылочных типов при реализации бинарных деревьев
- Сортировка с помощью ссылочных типов
- Стиль программирования
- Определение1
- Определение 2
- Определение 3.
- Использование предиката fail
- Детерминизм и отсечение