В.Н. Пильщиков - Язык Плэнер (1156455), страница 23
Текст из файла (страница 23)
Переменные, которые использует аналиаатор, имеют следующий смысл. ЬУ вЂ” это список лисп-переменных, к которым разрешено обращаться в анализируемой лисповсной функции; мы будем предполагать, что в теле любой определяемой функции Можно использовать только ее локальные переменные и запрещено использование внепших переменных. ПŠ— это «флажокм 108 который указывает, анализируется ли сейчас тело какой-нибудь определяемой функции (ПЕ=Т) или нет (ПЕ= ()); по этому флажку анализатор узнает, допустимы ли сейчас обращения к еще не описанным функциям (что допускается в теле определяемых функций) или нет. ПИ))ЕР— список обращений как раз к таким неописанным функциям; анализ этих обращений откладывается на Конец, когда станут иавестными все функции, определенные в лисп-программе. ЕВК вЂ” это флажок, который имеет значение (), пока в лисп-программе не обнаружено ошибок, и принимает значение Т при первой же ошибке .
Ниже приводится описание нашего аналиаатора, снабженное краткими пояснениями. [ПЕР1ИЕ АИАЬУБЕВ (ЬАМВПА () [РКО6 ((ЬУ ()) (ПЕ ()) (ПИПЕР ()) (ЕВВ ()) И) [РЫЯТ 1]ПОТЕ (ТУРЕ РЯПВК ИАВ6 1)] [РЫБТ САВ (ТУРЕ ЯПВК ИАВО 1)] [РЫЯТ СОВ (ТУРЕ БНВВ ИАВ6 1)] [Р1 13Т СОНЯ (ТУРЕ 3()ВВ ИАК6 2)] [РЫЯТ АТОМ (ТУРЕ ЯПВВ ИАВ6 1)] [РЫБТ Е1] (ТУРЕ ЯНВВ ИАВ6 2)] [жн)ЬЕ [ИОТ [ЕОР]] [13 [1 РОЕМ] [КЕАП]]] [ЬООР Е Л)ИВЕР [СОИП ([13 ([НАБ ТУРЕ ЯПВВ ИАПО »И] <ЫЯТ .И)) Е]) (Т [РК1ИТ-ЕКВОВ .Е])]] .ЕКВ])] Это основная функция анализатора.
Прежде всего опа заносит в списки свойств названий встроенных лисп-функций информацию об их классе и числе аргументов. Для идентификаторов СОИП в ЯЕХРВ списки свойств не задаются, так как обращения к функциям с этими названиями будут анализироваться по особым правилам, беа использования списков свойств. Затем в 1УН1ЬЕ- цикле осуществляется считывание лисп-выражений и их проверка. В ЬООР-цикле аиалиаируются те обращения к лисп-функциям, которые были аанесепы в список ПИРЕР.
В те момепты,'когда анализатору встречались зти обращения, указанные в них функции еще не были определены, поэтому анализатор мог тогда проверять лишь правильность 'аргументов, заданных в, этих обращениях. Теперь же он проверяет правильность числа аргументов н то, были ли в лисп-программе определекы фУнкцнн, указаНные в утих обращениях, Сообщения о любом неправильном лисп-выражении печатает следующая функция: [ПЕР)ХЕ РВ1ХТ-ЕВВОВ (ЬАМВОА (Е) [ОО [МРВ1ХТ 1ХСОВВЕСТ РОЕМ: .Е] [ЯЕТ ЕВВ Т]])] Все остальные процедуры нашего аналиватора — вто сопоставители, проверяющие правильность ваписи равличпых типов лисповских выражений, / [ОЕР1ХЕ 1 РОЕМ (КАРРА () [БАМЕ (Е) «Е [АСТ [1 СОХЯТ] [1 ЧАВ] [РСХСАЩ [ЬАМВОА-САЩ [ВЕ [РВ1ХТ-ЕВВОВ .Е]Ц ])) Лисп-форма — это илн константа, или переменная, или обращение к функции, или особое обращение с ЬАМВПА-выражением.
Если аналнвнруемое выражение — не форма, то об етом сообщается на печать. [ПЕР)ХЕ 1 СОХЯТ (КАРРА () [АСТ Т Х1Ь () [Х1)М]])] Лисп-константа — вто Т, Х1Ь, () или чйсло. [ОЕР1ХЕ 1 ЧАВ (КАРРА () [ЕТ [1О] [ОХЕ-ОГ .1Ч]]Ц Переменной (согласно нашим предположениям) является иден- тификатор ив текущего списка ЬЧ. [ОЕР1ХЕ Р()ХСАЬЬ (КАРРА () [ЯАМЕ (Х) ([1О] <ЫЯТ «Х)) [)ЧНЕХ ((СОХО < )) [ЫЯТ, [СЕ 2]] ([) <ЯТАВ ([1 РОЕМ] [Ь-РОВМ]) >)) ( (БЕХРВ < ) ) [ХЕИРПХ] ) (([НАБ ТУРЕ ЯСВВ] < )) ([НАБ ХАНС .Х] <БТАВ [1 РОЕМ]))) (([НАЯ ТУРЕ РЯОВВ] < )) ([НАЯ ХАВС Х] < ))) ([ВЕ: ПЕ! в Х ([) <ЯТАВ [1-РОЕМ])) [ВЕ [БЕТ ЮХОЕР (ЬОХОЕР .Х)]]Н]Н Обращение к функции доялшо быть сцискои в круглых скобках„ 110 начинающимсн с идентифниатора.
Обращение к фуннции СОКЕ должно содержать хотя бы один аргумент, и все аргументы обязаны быть описками из двух форм. Обращение к фужщии ЯЕХРВ аналианруется с помощью сопоставителя 1ЧЕ%РУК. Для обрацений к другим функциям, встроенным или уже определенным, проверяется правильность числа заданных аргументов, а для функций класса ЯСВВ проверяется и то, являются ли их аргументы формамн. Если же встретилось обращение к неописанной функции и мы сейчас находимся внутри тела некоторой определяемой функции, т. е. ОЕ = Т, тогда проверяется, являются лл аргументы етого обращения формами, после чего обращение ааносится в список ПЕВЕК Если ОЕ = (), то обращение к неописанной функции недопустимо, и такому обращению сопоставитель РОИСАЫ, не соответствует.
[ОЕР1ХЕ КЕЧЧРУ)Ч (КАРРА () [БАМЕ (Р )Ч) (БЕХРВ [ЕТ [1О] «Р] [ОЕХРВ «Щ) [ВЕ [РЫБТ .Р (ТЧРЕ БОВЕ )ЧАВО,К)]Ц)] Этот сопоставитель проверяет правильность обращений к функции ЯЕХРВ. Проверив, что в аиалиаируемом обращении первый аргумент является идентификатором, а второй — правильным определяющим выражением, сопоставитель заносит в список свойств этого идентификатора — имени определяемой функции — число параметров функции (оно узнается при выполнении сопоставителя ОЕХРВ) н признак того, что функция относится и классу БУЕВ. [ОЕР1ЕЕ ОЕХРВ (КАРРА («Р),[БАМЕ (1Ч (ОЕ Т)) (1АМВОА [ЕТ [ЯТАВ [1О]] «1Ч] [1гРОВМ]) ([] [ЫЯТ [РАТ .Р]] [])])] Проверяя, правильно ли построено определяющее вьтраженне функции, сопоставнтель ОЕХРВ вводит локальные переменные ЕЧ и ПЕ, которые будут использоваться сопоставителем 1 РОЕМ при анализе тела этого определяющего выражения.
ПЕ получает значение Т, а значением 1.Ч становится список параметров ие определяющего выражения. Этим сообщается сопоставителю 1 РОЕМ, что он работает внутри определяющего выражения и что здесь допустимы обращения только к переменным, являющимся параметрами аналнаируемой функции. Если определяющее выражение ааписано цравильно, то образец, заданный каи аргумент сопоставнтеля ОЕХРВ, сопоставляется с числом, равным длине списка параметров. [ОЕГ1ЕЕ ЕАМВПА-САВЕ (КАРРА () [БАМЕ (К) ([ОЕХРВ«К] (ЕТ [ЫБТ .К] [ЯТАВ [ РОЕМ]]>)])], Ш В обращении с ЬАМВРА-выраженном число аргументов должно равняться числу параметров, описанных в ЬАМВВА-выражении, н все этн аргументы должны быть формами. На этом завершается описание анализатора.
Запуск его осуществляется обращением к функции АХАЬт'ЗЕВ; ~АХАЬУЗЕЩ. Значение этого выражения равно (), если в анализируемой лисппрограмме не было обнаружено ошибок, и равно Т, если была най. дена хотя бы одна ошибка, ГЛАВА 3 РЕЖИМ ВОЗВРАТОВ 3.1. Основные понятия Многие аадачн обработки символьной информации и искусственного интеллекта (например, символьное интегрирование, синтаксический анализ, доказательство теорем, планирование действий роботов, игровые задачи) решаются методом перебора.
Этн ' задачи не имеют эффективного алгоритма решения, н единственная возможность решить их — это рассмотреть различные варианты, которые потенциально могут быть решениями, в надежде найти вариант, который действительно решает задачу. Конечно, при этом стремятся с помощью эвристпк совратить число рассматриваемых,вариантов, но в основе такого способа решения лежит все же перебор вариантов. Существует несколько разновидностей метода перебора. Наиболее часто на практике применяется перебор в глубину, когда в каждой точке ветвления выбирается один из вариантов и он исследуезюя до конца. Если выбранный путь не,приводит н успеху, то осуществляется возврат и ближайшей точке ветвления, в кото рой еще остались нерассмотренные альтернативы, здесь выбнра ется новый вариант, и теперь исследуется уже он (см.
рис. 1). Для того чтобы упростить программирование такого метода перебораз в язык плэнер введен специальный способ выполнения программ режим возвратов (Ьас)гггасЫвя). Суть его в следующем. В любой плзиерской программе могут быть развилки — точки, где необходимо сделать выбор из нескольких альтернатив. Программа выбирает в развилке одну нз альтернатив и продолжает свои вычисления. В какой-то момент может быть установлено, что сделанный выбор неудачен, тогда вырабатывается неуспех — специальный сигнал, по которому программа прекращает обработку выбранной альтернативы и возвращается назад к развилка Одновременно уничтожаются следы работы программы на неуспешном пути вычислений: восстанавливаются прежние апачения перемен3 Н.
и. Пвльиаиоа ных, прежние значения опнсков свойств и т. п. Таким образом, прн появлении неуспеха восстанавливается то состояние программы, в котором она находилась, когда делала первый выбор в развилке, как будто бы н не было этого выбора. Теперь в развилке выбирается другая альтернатива, после чего программа возобновляет свои вычисления — анализирует новую альтернативу. Если и она не приводит к успеху, то снова происходит возврат к развилке, где выбирается следующая альтернатива, и т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
