Обработка текстов
Пролог обладает большими возможностями по сопоставлению объектов с образцом, поэтому данный язык программирования хорошо подходит для обработки текстов. На Прологе с успехом можно реализовывать генераторы отчетов, текстовые редакторы и трансляторы с языков.
В данном разделе продемонстрируем две системы грамматического разбора. Система грамматического разбора – это программа, которая распознает синтаксические объекты в потоке лексем, т.е. реализует какую-либо формальную грамматику. Общеизвестны две основные стратегии грамматического разбора: нисходящая (сверху вниз) и восходящая (снизу вверх).
Система нисходящего грамматического разбора базируется на стратегии с обратной цепочкой рассуждений, а система восходящего разбора – с прямой. Следовательно, реализация на Прологе системы нисходящего разбора может быть осуществлена достаточно прямолинейным способом.
Продемонстрируем систему разбора сверху вниз примером простейшего синтаксического анализатора предложений. В описанной системе используется грамматика, которую можно схематически представить так:
предложение --> группа_подлежащего группа_сказуемого
группа_подлежащего --> определение существительное
группа_подлежащего --> существительное
группа_сказуемого --> глагол существительное
Первым аргументом предиката object является входной список лексем, третий аргумент – это название определяемого объекта. Второй аргумент образован частью списка, оставшегося после того, как из оставшегося списка будет взят терминал или нетерминал.
Система нисходящего грамматического разбора начинает работу с принятия некоторой гипотезы, а затем проверяет верность следствий этой гипотезы по данным, содержащимся во входном списке. Первоначальной гипотезой может служить, например, предположение о том, что во входном списке можно обнаружить нетерминал "предложение". В соответствии с грамматическим правилом для нетерминала "предложение" данная гипотеза разбивается на две субгипотезы: на предположения о том, что во входном потоке содержатся группа подлежащего и группа сказуемого. Эти две гипотезы в свою очередь разбиваются на субгипотезы более низкого уровня. Процесс разделения гипотез на субгипотезы продолжается до тех пор, пока система не встретит терминал. В этом случае она пытается установить факт наличия терминала в начальной позиции входного списка.
Несколько сложнее реализуется на Прологе система восходящего грамматического разбора, т.к. она базируется на прямой цепочке рассуждений. Однако такая система имеет то преимущество, что может работать с рекурсивными правилами, которые могли бы вызвать бесконечное зацикливание в системе нисходящего разбора.
Примером для реализации восходящей грамматики с рекурсивными правилами является синтаксический анализатор математических выражений. Такая система начинает работу с данными и переходит к простым синтаксическим объектам, а затем и к более сложным. В то время как система нисходящего разбора управляется в основном гипотезами, система восходящего грамматического разбора управляется данными.
Более важной сферой применения систем грамматического разбора является построение так называемого дерева грамматического разбора в том или ином виде, в котором явно указаны классы объектов и существующие между ними отношения
24. В следующем примере на вход подается алгебраическое выражение в виде строки, которое может содержать имена переменных и знаки плюс и умножить. Результат работы программы – запись выражения в префиксной форме, когда знак операции предшествует операндам.
Предикат run начинает работу программы с создания окна, считывает исходное выражение в переменную STR . Следующий предикат tokl переводит строковую переменную в список токенов (лексем) TOKL, далее предикат s_exp запускает рабочий предикат plusexp, с которого собственно начинается работа анализатора.
Процедура multexp первую лексему (имя переменной) переводит в префиксную форму и проверяет остаток на наличие после нее (лексемы) операции умножения предикатом multexp1. Если знак "*" присутствует, последний предикат переводит сомножители в префиксную форму.
Предикат plusexp1 проверяет остаток после знака "+" на наличие операции умножения предикатом multexp. Если умножения нет, слагаемые также переводятся в префиксную форму.