Синтаксический анализатор позволяет проверять программы, составленные на языке с определенной грамматикой. Грамматика—это совокупность определений, которые регламентируют, какие комбинации базовых структур языка, называемых лексемами, являются допустимыми. В данном случае лексемой считается любая отделенная пробелами цепочка символов. Мы можем рассматривать правила, вопросы-подсказки и переводы как предложения на некотором языке правил.
Таблица 4. Грамматика правил, подсказок и переводов для экспертной системы, представленная в форме Бекуса — Наура
* Иногда вместо слова ЯВЛЯЕТСЯ используется тире
Первый шаг процесса составления программы синтаксического анализа состоит в создании исчерпывающего описания языка, на проверку фраз которого и ориентирован анализатор. Грамматика этого языка представлена в табл. 4 в форме Бекуса—Наура (БНФ), дающей компактное описание синтаксиса языка. В ней используются два специальных оператора, а именно «::» («по определению, ранво») и «|» («или»). К примеру, первую строку в табл.4
предложение ::= правило | подсказка | перевод
следует читать как «предложение — это по определению правило, подсказка или перевод». Символы и слова, заключенные в одиночные кавычки, должны записываться в языке именно так, как показано в БНФ. Прочие знаки представляют собой синтаксические категории и определяются грамматикой. Фраза
правило ::= номер__правила 'ЕСЛИ' условие 'ТО' вывод '.'
означает, что правило состоит из номера правила, а также следующих за ним ключевого слова «ЕСЛИ», условия (которое определяется где-то в другой части грамматики), слона «ТО» и вывода. Правило завершается знаком «.». Из определения условия
условие ::= выражение 'И' условие
следует, что условие содержит либо одно выражение, либо несколько выражений, связанных словами «И». Такого рода запись называется определением с правой рекурсией, поскольку описываемый объект находится в правой части этого определения. Количество рекурсий (т. е. операций, в каждой из которых используется результат, полученный во время предыдущей операции) в подобном определении не обязательно ограничено. Вполне допустима ситуация, когда условие содержит бесконечное число выражений. Очевидно, что при работе с любой программой, в которой будет предприниматься попытка синтаксического анализа такого объекта, возникли бы сложности, связанные с ограниченностью времени, которое отводится на решение задачи, и конечным объемом памяти ЭВМ. Пользуясь БНФ, можно получить достаточно эффективное теоретическое определение конкретной грамматики, однако такая форма записи не всегда содержит информацию об ограничениях, связанных с практической реализацией грамматики на конкретной вычислительной машине.
Использование определения, записываемого в соответствии с БНФ, дает то преимущество, что при наличии заданной таким образом грамматики написание программы синтаксического анализатора не составляет особого труда. Подобное определение служит своего рода руководством по «нисходящему» проектированию программы. Будем предполагать, что в вашем распоряжении уже есть стандартная программа (она называется scanf—программа просмотра файлов) для считывания лексем из файла входных данных.
Для составления программы синтаксического анализатора вначале рассмотрим первую строку грамматики и напишем процедуру, которая способна выполнять следующие действия: воспринимать ту или иную лексему из файла и решать, что она собой представляет—начальную лексему правила, вопрос-подсказку или перевод; считывать следующую лексему; вызывать программу, необходимую для анализа оставшейся части предложения. Этим занимается процедура предложение, доступная упомянутой программе BYTEnet. Пред полагается, что процедура правило, предусмотренная в этой программе, вызывается посредством лексемы со значением «ЕСЛИ». При поступлении указанной лексемы происходит вызов условия; в противном случае процедура правило вызывает стандартную программу обработки ошибок и инициирует выход из основной программы. Такой процесс продолжается в соответствии с БНФ-определениями, пока мы не доберемся до процедур атрибут, предикат и значение, которые обеспечивают сохранение идентифицированных ими структурных компонентов для последующего использования.
В нашей реализации при определении значения завершающей лексемой служит слово «И», поэтому попытка воспользоваться значениями типа «твердый и древесный» ггриведет к тому, что в синтаксическом анализаторе произойдет останов по ошибке. Разрешить эту проблему можно, изменив определение правила в грамматике таким образом, чтобы в качестве ключевого применялось слово, отличное от «И», или введя в структуру синтаксического анализатора процедуру возврата. Последняя позволяла бы синтаксическому анализатору возвращаться к тому элементу предложения, который обусловил появление ошибки, и выполнять затем другой возможный вариант анализа.
Все процедуры, которые осуществляет синтаксический анализатор, должны взаимодействовать между собой в соответствии с определенным «соглашением». Оно предусматривает, что при повторном использовании таких процедур последние должны будут просматривать все идентифицируемые с их помощью лексемы, помещая первую лексему каждой следующей фразы в глобальную переменную, которая также называется лексемой.
Многие процедурные элементы, входящие в состав синтаксического анализатора, например условия и признаки, имеют рекурсивный характер, поскольку рекурсии содержатся в их определениях. Такой вид нисходящего Грамматического разбора называется синтаксическим анализом по методу рекурсивного спуска.
Рассмотренная здесь грамматика позволяет объединить правила» вопросы-подсказки и переводы в общий файл. Правила, содержащиеся в табл. 1, можно вводить в программу именно в том виде, в каком они представлены в таблице. Подсказки и переводы (табл. 2) необходимо изменять в соответствии с требованиями грамматики. Например:
@ trans стебель
Стебель растения
@
@подсказка стебель
Является ли стебель растения древесным или зеленым?
@
Для изменения типа правил, распознаваемых программой, следует модифицировать грамматику, а затем, руководствуясь новой грамматикой, переписать стандартные программы, предназначенные для се обработки.
Программу перекрестных ссылок, в которой применяются процедуры синтаксического анализа, описанные в настоящей статье, можно перенести в экспертную систему из пакета, работающего в сети BYTEnel. Имеются варианты исходного кода этой программы, записанные на языке Паскаль в версиях Apple и УКСД (разработанной Калифорнийским университетом в Сан-Диего), а также в версии Паскаля Turbo. Рассматриваемая здесь совокупность правил реализована в настоящее время в виде текстового файла, как наиболее полная база знаний, предназначенная для идентификации видов хвойных, произрастающих в северо-восточных районах США. Указанная программа перекрестных ссылок считывает информацию о знаниях из базы, содержащейся в текстовом файле, составляя упорядоченный по алфавиту список признаков вместе с соответствующими переводами, вопросами-подсказками и значениями. На экране дисплея воспроизводятся также номера всех правил, в которых представлено значение признака.
Хотя исходный код программы перекрестных ссылок занимает в памяти ЭВМ 16K байт, это лишь одна из частей экспертной системы. Далее мы рассмотрим спецификации законченной программы на языке Паскаль, с помощью которой реализуется картотечно-поисковая дедуктивная машина. В основу этих спецификаций положен написанный авторами данной статьи пакет, получивший название «Микро-Эксперт». Издательство «Макгроу-Хилл» предлагает его (в записи на диске) пользователям вычислительных машин фирм IBM и Apple. В состав указанного пакета, который по существу представляет собой несложную реализацию картотечно-поисковой дедуктивной машины, входят исчерпывающая документация и собственно исходный код. («МикроЭксперт» — торговая марка фирмы «МикроЭксперт системз».) Программу перекрестных ссылок из состава пакета BYTEnet можно без каких бы то ни было модификаций использовать совместно с системой «МикроЭксперт».
