3.8. Обработка текстов

Пролог обладает большими возможностями по сопоставлению объектов с образцом, поэтому данный язык программирования хорошо подходит для обработки текстов. На Прологе с успехом можно реализовывать генераторы отчетов, текстовые редакторы и трансляторы с языков.

В данном разделе продемонстрируем две системы грамматического разбора. Система грамматического разбора – это программа, которая распознает синтаксические объекты в потоке лексем, т.е. реализует какую-либо формальную грамматику. Общеизвестны две основные стратегии грамматического разбора: нисходящая (сверху вниз) и восходящая (снизу вверх).

Система нисходящего грамматического разбора базируется на стратегии с обратной цепочкой рассуждений, а система восходящего разбора – с прямой. Следовательно, реализация на Прологе системы нисходящего разбора может быть осуществлена достаточно прямолинейным способом.

Продемонстрируем систему разбора сверху вниз примером простейшего синтаксического анализатора предложений. В описанной системе используется грамматика, которую можно схематически представить так:

предложение --> группа_подлежащего группа_сказуемого

группа_подлежащего --> определение существительное

группа_подлежащего --> существительное

группа_сказуемого --> глагол существительное

Первым аргументом предиката object является входной список лексем, третий аргумент – это название определяемого объекта. Второй аргумент образован частью списка, оставшегося после того, как из оставшегося списка будет взят терминал или нетерминал.

Система нисходящего грамматического разбора начинает работу с принятия некоторой гипотезы, а затем проверяет верность следствий этой гипотезы по данным, содержащимся во входном списке. Первоначальной гипотезой может служить, например, предположение о том, что во входном списке можно обнаружить нетерминал "предложение". В соответствии с грамматическим правилом для нетерминала "предложение" данная гипотеза разбивается на две субгипотезы: на предположения о том, что во входном потоке содержатся группа подлежащего и группа сказуемого. Эти две гипотезы в свою очередь разбиваются на субгипотезы более низкого уровня. Процесс разделения гипотез на субгипотезы продолжается до тех пор, пока система не встретит терминал. В этом случае она пытается установить факт наличия терминала в начальной позиции входного списка.

Несколько сложнее реализуется на Прологе система восходящего грамматического разбора, т.к. она базируется на прямой цепочке рассуждений. Однако такая система имеет то преимущество, что может работать с рекурсивными правилами, которые могли бы вызвать бесконечное зацикливание в системе нисходящего разбора.

Примером для реализации восходящей грамматики с рекурсивными правилами является синтаксический анализатор математических выражений. Такая система начинает работу с данными и переходит к простым синтаксическим объектам, а затем и к более сложным. В то время как система нисходящего разбора управляется в основном гипотезами, система восходящего грамматического разбора управляется данными.

Более важной сферой применения систем грамматического разбора является построение так называемого дерева грамматического разбора в том или ином виде, в котором явно указаны классы объектов и существующие между ними отношения

24. В следующем примере на вход подается алгебраическое выражение в виде строки, которое может содержать имена переменных и знаки плюс и умножить. Результат работы программы – запись выражения в префиксной форме, когда знак операции предшествует операндам.

Предикат runначинает работу программы с создания окна, считывает исходное выражение в переменнуюSTR. Следующий предикатtoklпереводит строковую переменную в список токенов (лексем)TOKL, далее предикатs_expзапускает рабочий предикатplusexp, с которого собственно начинается работа анализатора.

Процедура multexpпервую лексему (имя переменной) переводит в префиксную форму и проверяет остаток на наличие после нее (лексемы) операции умножения предикатомmultexp1. Если знак "*" присутствует, последний предикат переводит сомножители в префиксную форму.

Предикат plusexp1проверяет остаток после знака "+" на наличие операции умножения предикатомmultexp. Если умножения нет, слагаемые также переводятся в префиксную форму.

domains

TOKL = STRING*

EXP=var(STRING);

plus(EXP,EXP);

mult(EXP,EXP)

PREDICATES

run

tokl(STRING,TOKL)

s_exp(TOKL,TOKL,EXP)

multexp(TOKL,TOKL,EXP)

multexp1(TOKL,TOKL,EXP,EXP)

plusexp(TOKL,TOKL,EXP)

plusexp1(TOKL,TOKL,EXP,EXP)

elmexp(TOKL,TOKL,EXP)

GOAL

run.

CLAUSES

run:– makewindow(1,2,7,"",0,0,25,80),

readln(STR),tokl(STR,TOKL),

s_exp(TOKL,_,EXP), write(EXP),nl.

tokl(STR,[TOK|TOKL]):–

fronttoken(STR,TOK,STR1),

tokl(STR1,TOKL).

tokl(_,[]).

s_exp(IL,OL,EXP):–plusexp(IL,OL,EXP).

plusexp(IL,OL,EXP2):–

multexp(IL,OL1,EXP1),

plusexp1(OL1,OL,EXP1,EXP2).

plusexp1(["+"|IL],OL,EXP1,EXP3):–

multexp(IL,OL1,EXP2),

plusexp1(OL1,OL, plus(EXP1,EXP2),EXP3).

plusexp1(IL,IL,EXP,EXP).

multexp(IL,OL,EXP2):–

elmexp(IL,OL1,EXP1),

multexp1(OL1,OL,EXP1,EXP2).

multexp1(["*"|IL],OL,EXP1,EXP3):–

elmexp(IL,OL1,EXP2),

multexp1(OL1,OL, mult(EXP1,EXP2),EXP3).

multexp1(IL,IL,EXP,EXP).

elmexp([NAME|IL],IL, var(NAME)).

25. Еще один пример анализатора, строящего дерево синтаксического разбора для простого английского выражения. Предложение, подлежащее разбору, должно соответствовать следующей грамматике:

<SENTENCE> ::= <NOUN PHRASE> <VERB PHRASE>

<NOUN PHRASE> ::=<DETERMINER> <noun> <RELATIONAL CLAUSE>

<DETERMINER> ::= < > | <determiner>

<RELATIONAL CLAUSE> ::= < > | <relative> <VERB PHRASE>

<VERB PHRASE> ::= <verb> | <NOUN PHRASE>

Программа на Прологе:

DATABASE %Слова , которые должны быть распознаны

det( STRING ) % Определитель

noun( STRING ) % Существительное

rel( STRING ) % Предлог