Pull to refresh

Prolog — грамматический разбор и языковые проблемы

Reading time 10 min
Views 14K
Грамматический разбор — тема, которую должен знать и ориентироваться каждый программист. Именно, потому что применяем ее каждый день. Да мы не пишем новые языки или не правим грамматики каждый день, но мы пользуемся регулярными выражениями, задумываемся о сложности и вычислимости, думаем о количестве строк кода, что имеет непосредственное отношение к грамматикам.

Целью этой статьи является попытка показать связи в различных областях знаний, как программирование и математика, философия и логика, а так же продемонстрировать в действии одну из наиболее удачных областей применения языка Prolog — грамматический разбор.



Иногда создается впечатление, что в различных науках используются различные термины для определения одного и того же объекта. Тогда и возникает это неотвратимое чувство, как-то все объединить, классифицировать, что на практике осуществить достаточно сложно. Ведь разные научные дисциплины имеют разные объекты изучения, различные цели, методологии и, самое неприятное, специфичные терминологии.

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

Экскурс в историю


Философия

Как ни странно, сначала хочется упомянуть философию, а именно одно из ее направлений XX века Аналитическая философия. Думаю многие программисты, математики, не воспринимают ее достаточно серьезно, хотя стоило бы. Многие включают в самообразование изучение новых языков программирования, на мой взгляд, включение философии в некоторой степени необходимо. Не зря же PHD — доктор философских наук.

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

Математическая логика

Вообще необходимость вмешательства философии в математику назрела в конце 19 века. Как известно Эйлер доказал большое количество теорем и утверждений, но в то же время формализмом он отнюдь не страдал. То есть Эйлер вполне мог суммировать расходящиеся ряды, даже не вводя определения, на каком основании это можно делать. Нет, он приводил замечания, рассуждения, даже больше, чем Ферма, оставивший только заметки на полях, но все-таки сейчас такие рассуждения не были бы восприняты доказательством. К концу 19 века в математике назрел кризис: появились такие утверждения, как «континуум-гипотеза», проблема выбора. Эти утверждения не могли разрешиться однозначно, так как у разных людей они вызывали разные ассоциации, проще говоря некоторые верили в верность утверждений, а некоторые — нет. Тогда математика взяла курс на формализм, после чего выявились базовые проблемы (соотнесения реальных объектов к числам и другим математическим объектам, проверки аксиом), но это уже оставили на усмотрение философов. С этого момента математику можно было называть языком наук.

Математическая логика сразу же избрала своим объектом не числа или другие объекты, как другие математические дисциплины, а слова и утверждения некоторого формального языка. По сути дела было дано определение доказательству, были определены стандартные логические умозаключения MP (Modus Ponens) и Gen (Generalization), а также описаны формальные математические теории (чисел, групп). В общем получилась математика, которую мы видим сейчас: с формальными доказательствами и апостериорными проверками (априори остались только аксиомы).

Несомненно для математики это сразу же дало результаты. Многие бы программисты сокрушались, это же теперь все доказательства надо переписывать на новый язык, но ничего математики «рефакторинга» не испугались и все потихоньку переписали, выполняя программу Гильберта. В общем, тут мы подходим совсем близко к программированию и к краху формальной математики. В 30-е годы появился 1-й математик, который начал рассматривать доказательства и теоремы, не с позиции смысла, а с позиции бесмыссленных слов и утверждений, подчиняющихся грамматическим правилам (аксиомам и правилам вывода). Он поставил правила и их свойства важнее самих слов, что было не совсем обычно для математики. И изучив свойства правил, он сгенерировал утверждение, для которого было нельзя получить/вывести доказательство. Это был Гедель.

Здесь важно отметить, что в математической логике понятие выводимость означает то же самое, что и доказуемость. Так как все мы знаем, что доказывать теоремы очень сложно и неподвластно машине, то можно предположить, что и алгоритмическая задача проверки того, что слово может быть выведено из конкретной грамматики, тоже не разрешима. То есть, в общем случае, что выведет программа на консоль, может быть неизвестно :) В простейшем случае неизвестно закончит программа выполнение или нет

Программирование (Computer science)

Неизвестно, почему для оценки сложности алгоритмов по умолчанию были выбраны именно машины Тьюринга. Существует по крайней мере 3 тождественных математических модели: Алгорифмы Маркова, функции Геделя и Частично рекурсивные функции (более применимые в математической логике).

Лингвистика

Конечно же, говоря о языке, невозможно не упомянуть достижений лингвистов в этой области. Как ни странно программисты пользуются классификацией Хомского при описании новых грамматик и понимании сложности. Так регулярные грамматики, описываются недетерминированными автоматами, которые могут быть преобразованы в детерминированные, контекстно-свободные — автомат со стеком, а для контекстно-зависимых может потребоваться полная машина Тьюринга. Полезным результатом в теории алгоритмов, что грамматики типа 0 (самые сложные) необходимы и достаточны для распознавания машиной Тьюринга.

Чтобы подробно и обстоятельно разобраться во всех терминах перечисленных выше несомненно потребуется «книга дракона», а так же неплохие книги по дискретной математике и математической логике, что естественно не может быть раскрыто в одной статье. В статье же предполагается, что читатель имеет представление об этих понятиях.

Описание формальной грамматики в Prolog


Возьмем определение формального языка:
В математической логике и информатике формальный язык — это множество конечных слов (строк, цепочек) над конечным алфавитом [Wikipedia].

Нас прежде всего будет интересовать не сам язык, а способ его задания, точнее грамматика:
Формальная грамматика или просто грамматика в теории формальных языков — способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавита. Различают порождающие и распознающие (или аналитические) грамматики — первые задают правила, с помощью которых можно построить любое слово языка, а вторые позволяют по данному слову определить, входит оно в язык или нет [Wikipedia].

Возьмем стандартное описание грамматики языка палиндромов четной длины:
	  S -> a S a.
	  S.
	

Маленькие буквы описывают терминальные символы, а большие продукции. Удивительно, то как этот синтаксис изначально близок к Prolog:
	  S :- a, S, a.
	  S.
	


Конечно смысловая нагрузка абсолютно другая, но есть абсолютная схожесть в выполнении программы. Это грамматика является контекстно-свободной и если для ее разбора использовать LL-анализатор, то шаги выполнения анализа полностью совпадут с шагами выполнения Пролога. То есть будут просматриваться правила слева-направо, в отличие от LR анализатора. Главным отличием выполнения программ на Прологе является то, что бэктрекинг не ограничен. К одним из плюсов LL -анализаторов (Antlr) перед LR-анализаторами (yacc) относится, простота отладки, так как продукции можно рассматривать как функции и интерпретировать их вызов на стеке, к минусам относится меньшее количество описываемых языков.

Prolog язык домено-ориентированный, то есть позволяет создавать специальные нотации под каждый язык, не исключением является и задача описания грамматик. Синтаксис достаточно простой:

	  s --> [a], s, [a].
	  s --> [].
	


В прямоугольных скобках находятся терминальные символы (их может быть много), вне скобок, литералы являются продукциями. Такой синтаксис позволяет однозначно перевести только КС-грамматики, но при небольшом расширении этого синтаксиса анализатор может решать задачи, требующие полной машины Тьюринга, то есть покрываются языки грамматики типа 0.

Пару примеров КС-грамматик описанных на прологе.

	  s --> [].
	  s --> [a], s, [b].

	  sentence --> noun_phrase, verb_phrase.
	  noun_phrase --> det, noun.
	  verb_phrase --> verb, noun_phrase.
	  det --> [the].
	  det --> [a].
	  noun --> [cat].
	  noun --> [bat].
	  verb --> [eats].  
	


Реализация анализатора и продуктора формальных языков в Prolog



Самым интересным моментом является имплементация анализатора, потому как это одна из тех задач, которые на Prolog реализуется достаточно просто. Ключевым моментом (недостатком), что Пролог не может работать с чтением из файла, используя чистые предикаты, поэтому все содержание нужно загрузить в список (это может быть список лексем или букв).

Для реализации используются «разностные списки» — X \ [], левая часть — непросмотренные элементы, правая часть — просмотренные. Теперь представим, что каждое правило, перемещает лексему из левой части разностного списка в правую. При бэктрекенге лексема перемещается обратно: из правого в левый. Запишем это в виде простейших правил Пролога:

	  s(L, L).
	  s(L, L3) :- L=[a|L1], s(L1, L2), L3=[b|L2].
	


Для того, чтобы определить принадлежит ли слово aabb языку, необходимо запустить предикат :-s([a,a,b,b], []). И ответ будет — yes. Как и любая чистая программа на прологе, она не имеет одного входа и выхода, поэтому эта же грамматика может быть использована как порождающая!
На запрос :-s(X, []) мы будем получать: [], [a,b], [a,a,b,b],…. Можно даже задавать запросы с потерянными данными (задача восстановления данных): :-s([a,X,Y, b], []). -> X = a, Y = b. В общем, все это мы получаем абсолютно бесплатно :)

Очевидно, что процесс генерации предикатов из правил грамматики может быть автоматизирован и большинство интерпретаторов/компиляторов, так и делают. Хотя для тех реализаций Пролога, которые не поддерживают DCG (Definite Clause Grammar) — это можно сделать самостоятельно. Тем более, что это является отличной задачей для тех, кто изучает Пролог.
	:- op(1200, xfx, '-->').
	:- op(200, xfx, '\\'). 
	dcg_nonterminal(X) :- list(X), !, fail.
	dcg_nonterminal(_).
	dcg_terminals(Xs) :- list(Xs).

	dcg_parse(A, Tokens) :- dcg_nonterminal(A), (A --> B), dcg_parse(B, Tokens). 
	dcg_parse((A, B), Tokens \\ Xs) :- dcg_parse(A, Tokens \\ Tokens1), dcg_parse(B, Tokens1 \\ Xs).
	dcg_parse(A, Tokens) :- dcg_terminals(A), dcg_connect(A, Tokens). 
	dcg_parse({A}, Xs \\ Xs) :- call(A).

	dcg_connect([], Xs \\ Xs). 
	dcg_connect([W | Ws], [W | Xs] \\ Ys) :- dcg_connect(Ws, Xs \\ Ys).
	% Example :- dcg_parse(s, [a,b] \\ []).

	


Мне кажется этот код настолько полон, что комментарии ему не нужны, причем первые 3 правила всего лишь проверки.

Описание сложных грамматик и дерево результатов в Prolog


Понятно, что ни один анализатор не работает только с КС-грамматиками, все анализаторы вносят изменения, чтобы покрыть наибольшее количество языков. Наиболее просто это сделать в DCG правилах в Прологе. Все, что нужно, это добавить контекст, а именно параметры в правила ( не понимаю почему всем LL анализаторам так не сделать). Возьмем КЗ-грамматику (a..ab..bc..c — 3 буквы с одинаковым числом повторений).

        rule(a:X, b : Y, c : Z) --> [a],  rule(a:X+1, b : Y, c : Z).
        rule(a:X, b : Y, c : Z) --> [b],  rule(a:X, b : Y+1, c : Z).
        rule(a:X, b : Y, c : Z) --> [c],  rule(a:X, b : Y, c : Z+1).
        rule(a:N, b : N, c : N) --> [].
        


Крайне понятно и наглядно. Для тех, кого мучает вопрос эффективности данная грамматика будет анализироваться Прологом с той же эффективностью, что и LA(1)-анализатором. Если поставить отсечение после [a] (терминалов), то и затраты памяти будут такими же. Из-за того, что предикат плюс, использованный в правилах, не является декларативным (в прошлой статье приводился пример деклатаривного плюса) данная грамматика не является порождающей. То есть нельзя написать запрос :-rule(a:5,b:_, c:_,Res,[]).

Как многие уже заметили, в синтаксисе отсутствуют привычные нам по БНФ символы + и *, которыми часто пользуется в описании грамматик. Но это несложно исправить имея в руках мощный инструмент метаправил.

          '*'(Rule) --> [].
          '*'(Rule) --> Rule, '*'(Rule).
          '+'(Rule) --> Rule, '*'(Rule).

          tree -> '+'(branch).
          forest -> '*'(tree).
        


Выглядит, конечно, не привычно, поэтому этот синтаксис и не прижился в DCG. А придать выражениям более-менее естественный вид мешают ограничения парсера Пролога, которые поддерживает только унарные префиксные и бинарные операторы.

Дерево результатов в Prolog


Распознать принадлежит слово языку или нет — довольно редко встречающаяся задача в программировании. Гораздо чаще нас интересует грамматическое дерево разбора для последующей интерпретации/валидации/анализа. Вот пример типичного грамматического разбора в Prolog (прямо как на уроке английского языка):
          sentence(s(NP,VP)) --> noun_phrase(NP), verb_phrase(VP).
          noun_phrase(np(D,N)) --> det(D), noun(N).
          verb_phrase(vp(V,NP)) --> verb(V), noun_phrase(NP).
          det(d(the)) --> [the].
          det(d(a)) --> [a].
          noun(n(bat)) --> [bat].
          noun(n(cat)) --> [cat].
          verb(v(eats)) --> [eats].

         | ?- sentence(Parse_tree, [the,bat,eats,a,cat], []).
         Parse_tree = s(np(d(the),n(bat)),vp(v(eats),np(d(a),n(cat)))) ? ;
     


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

          expr(Res) --> expr(X), ['+'], summand(Y), {Res is X + Y}. 
          expr(Res) --> expr(X), ['-'], summand(Y), {Res is X + Y}. 
          summand(Res) --> summand(X), ['*'], multiplicator(Y), {Res is X / Y}. 
          summand(Res) --> summand(X), ['/'], multiplicator(Y), {Res is X / Y}. 
          summand(Res) --> multiplicator(Res). 
          multiplicator(X) --> number(X). 
          multiplicator(X) --> ['('], number(X), [')'].       
       


В принципе, используя метапредикаты и {} для вызова встроенных предикатов Пролога, мы получаем полную машину Тьюринга. В методах интерпретации программ на Прологе можно провести параллель с детерменированной Машиной Тьюринга и недетерминированной. Детерминированная Машина Тьюринга будет интерпретировать программы Пролога в классическом варианте, то есть подбирая правила сверху вниз, в строгом порядке. Недетерминированный аналог интерпретации будет искать наилучшее совпадение правила и следовать по этой ветке (как НМТ выбирает черезвычайно удачную следующую команду, чтобы достигнуть конечной цели завершения программы).

Специфика анализатора Prolog


Подводя итоги анализа DCG-парсера на Прологе, приведем + и — его использования:
1. + Выразимость большого количества языков (вплоть до типа 0).
2. + Удобство записи контекстно-зависимых языков, построения дерева вывода, метаправила.
3. + Механизмы трассировки, вывода на консоль доступны как стандартные Прологовские предикаты и все инструменты Пролога могут быть использованы.
4. — Простая перестановка правил может привести к зацикливанию программы. Пример:
expr(Res) --> expr(X), ['+'], expr(Y).
Правило такого вида будет корректно воспринято анализатором и иногда выдавать ожидаемый результат, но чаще всего будет зацикливать программу или использовать огромное количество ресурсов при бэктрекинге.
5. — Использование отсечения в качестве ограничения бэктрекинга может неожиданно влиять на логику программы.
6. — Достаточно сложно ограничить использование бэктрекинга и Look Ahead символов.
7. — Необходим все содержимое анализируемого текста в памяти (массив лексем или букв).

Библиография


1. Ахо. Компиляторы: принципы, технологии и инструменты
2. Чень и Ли. Автоматическое доказательство теорем.
3. Мендельсон. Математическая логика.

P.S. (Последнее слово): Кто нибудь знает сколько статей надо про Пролог написать, чтобы на хабре появился блог «Пролог» :)
Tags:
Hubs:
+18
Comments 23
Comments Comments 23

Articles