Декларативное программирование

[ Содержание | 1 | 2 | 3 | 4 | 5 | 5.1 | 5.2 | 5.3 | 5.4 | 5.5 | 5.6 | 5.7 | 5.8 | 5.9 | 6 | 6.1 | 6.2 | 6.3 | 6.4 | 6.5 | 7 | 7.1 | Литература ]

© 2003 И.А. Дехтяренко

6.3. Синтаксический анализ

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

Арифметические выражения

Рассмотрим следующий свод правил для синтаксиса арифметических выражений.

выражение = слагаемое.
выражение = слагаемое "+" выражение.
выражение = слагаемое "-" выражение.

слагаемое = множитель.
слагаемое = множитель "*" слагаемое.
слагаемое = множитель "/" слагаемое.

множитель = "(" выражение ")".
множитель = число.

число = цифра.
число = цифра число.

цифра = "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9".

Основная задача синтаксического анализатора - определить, соответствует ли данная строка правилам синтаксиса. Мы напишем предикат expr такой, что expr(S) истинно тогда и только тогда, когда строка (список символов) S является правильным выражением.

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

Одна разновидность выражений - просто слагаемые и мы можем записать предложение

expr(E) :- term(E).

Кроме того выражение может быть слагаемым, за которым следует знак "+", а затем другое выражение. Мы можем выразить это, используя отношение append.

expr(E) :- append(A,B,E), term(A), append("+",C,B), expr(C).

Чтобы быть правильным выражением этого вида, строка должна состоять из двух частей A и B, где A - слагаемое, а B состоит из знака "+", и другого выражения. Используя этот принцип, мы можем перевести весь свод правил грамматики, в логическую программу.

expr(E) :- term(E).
expr(E) :- append(A,B,E), term(A), append("+",C,B), expr(C).
expr(E) :- append(A,B,E), term(A), append("-",C,B), expr(C).

term(T) :- factor(T).
term(T) :- append(A,B,T), factor(A), append("*",C,B), term(С).
term(T) :- append(A,B,T), factor(A), append("/",C,B), term(С).

factor(F) :- append("(",A,F),append(E,")",A), expr(E).
factor(F) :- numeral(F).

numeral(N) :- digit(N).
numeral(N) :- append(D,M,N),digit(D), numeral(M).

digit("0"). digit("1").
digit("2"). digit("3").
digit("4"). digit("5").
digit("6"). digit("7").
digit("8"). digit("9").

Хотя эта программа правильна в логическом смысле, она очень неэффективна. Например, чтобы проанализировать строку "2*5+10", мы должны разбить строку на части "2*5" и "+10", проверить что "2*5" - правильное слагаемое и применить второе предложение для expr. Прежде чем достичь этого, входная строка будет разбиваться во всех возможных местах. Это означает проверку каждой из строк "", "2","2*" на предмет соответствия правилу для слагаемого, что в свою очередь приводит к разнообразным разбиениям этих строк и т.д., так что весь процесс занимает чрезвычайно много времени.

Большое количество обращений к append наводит на мысль использовать разностные списки. Например, правила для "выражения" можно записать как

expr(A-B) :- term(A-B).
expr(A-B) :- term(A-[0'+ |D]), expr(D-B).
expr(A-B) :- term(A-[0'- |D]), expr(D-B).

На практике разностные списки часто не записывают в виде одной структуры, а представляют парой переменных. Тогда вся программа принимает вид

expr(A,B) :- term(A,B).
expr(A,B) :- term(A,[0'+ |D]), expr(D,B).
expr(A,B) :- term(A,[0'- |D]), expr(D,B).

term(A,B) :- factor(A,B).
term(A,B) :- factor(A,[0'* |C]), term(C,B).
term(A,B) :- factor(A,[0'/ |C]), term(C,B).

factor([0'( |A],B) :-  expr(A,[0') |B]).
factor(A,B) :- numeral(A,B).

numeral(A,B) :- digit(A,B).
numeral(A,B) :- digit(A,C), numeral(C,B).

digit([0'0 |A],A). digit([0'1 |A],A). 
digit([0'2 |A],A). digit([0'3 |A],A).
digit([0'4 |A],A). digit([0'5 |A],A).
digit([0'6 |A],A). digit([0'7 |A],A).
digit([0'8 |A],A). digit([0'9 |A],A).

Определение "цифры" выглядит несколько громоздко, но мы можем его упростить.

digit([C|A],A) :- C >= 0'0, C =< 0'9.

Новое отношение expr(A,B) истинно, если разность строк A и В является правильным выражением. Другими словами, если строку A можно разбить на две части: выражение и остаток строки B. Именно так оно и выполняется. Запрос expr(S,R) принимает список S, находит правильное выражение в начале S и возвращает результат R, содержащий оставшуюся часть строки.

?- expr("2+3-1",L).

L = [43, 51, 45, 49] ;

L = [45, 49] ;

L = [] 

Yes

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

?- expr("2+3-1",[]).
Yes

?- expr("2+3*-1",[]).
No

Синтаксическая структура выражения.

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

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

expr(E, A,B) :- term(E, A,B).
expr(T+E, A,B) :- term(T, A,[0'+ |D]), expr(E, D,B).
expr(T+E, A,B) :- term(T, A,[0'- |D]), expr(E, D,B).

term(T, A,B) :- factor(T, A,B).
term(F*T, A,B) :- factor(F, [0'* |C]), term(T, C,B).
term(F/T, A,B) :- factor(F, [0'/ |C]), term(T, C,B).

factor(E, [0'( |A],B) :-  expr(E, A,[0') |B]).
factor(E, A,B) :- numeral(E, A,B).

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

numeral(E, A,B)  :- numeral(0,E, A,B).

numeral(M,N,A,B) :- digit(D,A,B), N is M*10+ D. 
numeral(M,N,A,B) :- digit(D,A,C), K is M*10+ D-0'0, numeral(K,N,C,B).

digit(D,[C|A],A) :- C >= 0'0, C =< 0'9 , D is C-0'0.

К сожалению, наш анализатор имеет существенный дефект .

?- expr(E,"5-3-2",[]).

E = 5-(3-2)

Yes

Выражение "5-3-2" действительно синтаксически правильно, но распознается оно как "5-(3-2)", в то время как общепринято трактовать его как "(5-3)-2". Проблема вызвана тем, что синтаксические правила не точно отражают внутреннюю структуру выражений.

Можно попытаться исправить правила синтаксиса, например

выражение = слагаемое.
выражение = выражение "+" слагаемое.
выражение = выражение "-" слагаемое.

Но это привело бы к следующей программе.

expr(E, A,B) :- term(E, A,B).
expr(T+E, A,B) :- expr(T, A,[0'+ |D]), term(E, D,B).
expr(T-E, A,B) :- expr(T, A,[0'- |D]), term(E, D,B).

При выполнении второго правила процедура expr немедленно вызовет саму себя и так до бесконечности. Ситуация когда тело правила начинается с рекурсивного обращения к определяемому предикату называется левосторонней рекурсией. В отличие от правосторонней или хвостовой рекурсии, обладающей приятными свойствами, левосторонняя рекурсия часто вызывает проблемы (вспомните хотя бы леворекурсивное определение chief).

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

выражение = слагаемое слагаемые.

слагаемые = .
слагаемые = "+" слагаемое слагаемые.
слагаемые = "-" слагаемое слагаемые.

слагаемое = множитель множители.
множители = .
множители = множитель "*" множители.
множители = множитель "/" множители.

множитель = "(" выражение ")".
множитель = число.

число = цифра цифры.

цифры = .
цифры = цифра число.

цифра = "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9".

Трюк состоит в том, что мы вводим новые синтаксические категории: "слагаемые" - последовательность (возможно пустая) слагаемых, каждому из которых предшествует знак "+" или "-", и "множители" -  аналогичная последовательность множителей. Это не только "исправляет" грамматику, но и делает ее более детерминированной, что значительно повышает эффективность программы. Именно поэтому аналогичной трансформации подвергнуто правило для чисел.

Новый анализатор

expr(E, A,B) :- term(T, A,C), terms(T,E,C,B).

terms(E, E, A, A).
terms(E, F, [0'+|A],B) :- term(T, A, C), terms(E+T, F, C,B).
terms(E, F, [0'-|A],B) :- term(T, A, C), terms(E-T, F, C,B).

term(E, A,B) :- factor(T, A,C), factors(T,E,C,B).

factors(E, E, A, A).
factors(E, F, [0'*|A],B) :- term(T, A, C), factors(E*T, F, C,B).
factors(E, F, [0'/|A],B) :- term(T, A, C), factors(E/T, F, C,B).

factor(E, [0'( |A],B) :-  expr(E, A,[0') |B]).
factor(E, A,B) :- numeral(E, A,B).

numeral(N, A,B) :- digit(D, A,C), digits(D, N, C,B).

digits(N,N, A,A).
digits(M, N, A, B) :-
    digit(D, A, C),
    K is M * 10 + D,
    digits(K,N, C,B).

digit(D,[C|A],A) :- C >= 0'0, C =< 0'9 , D is C-0'0.

работает как ему и положено

?- expr(E,"5-3-2",[]).

E = 5 - 3 - 2

Yes

?- expr(E,"123-345/67*8+90",[]).

E = 123-345/67*8+90 

Yes

Упражнение.

Измените программу так, чтобы она возвращая арифметическое значения выражения.

Грамматики определительных предложений

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

exp(E) --> term(T),terms(T,E).

terms(E,E) --> [].
terms(E,F) --> "+",term(T), terms(E+T,F).
terms(E,F) --> "-",term(T), terms(E-T,F).


term(T)   --> factor(F),factors(F,T).

factors(ET,T) --> [].
factors(T,E) --> "*",factor(F), factors(T*F,E).
factors(T,E) --> "/",factor(F), factors(T/F,E).

factor(E) --> "(",exp(E),")".
factor(E) --> numeral(E).

numeral(N) --> digit(D), digits(D,N).

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

digits(N,N) --> [].
digits(M,N) --> digit(D),{K is M*10+D, digits(K,N)}.

digit(D) --> [C],{C >= 0'0, C =< 0'9 , D is C-0'0}.

Эта нотация называется грамматикой определительных предложений или DC-грамматикой (Definite Clause Grammar, DCG). Она может оказаться полезной не только для задач синтаксического анализа. Ее можно рассматривать как сокращенную запись процедур, использующих списки-накопители или разностные списки. Например процедуру, возвращающую список узлов двоичного дерева можно записать как

nodes(empty) --> [].
nodes(bt(X,Lt,Rt)) --> [X], nodes(Lt), nodes(Rt).

?- nodes( bt(a, 
|      bt(b, bt(d, empty, empty), bt(e, empty, empty)), 
|      bt(c, bt(f, empty, empty), bt(g, empty, empty))),L,[]).

L = [a, b, d, e, c, f, g] 
Yes

Это, кстати, позволяет взглянуть на задачу с необычной точки зрения - как на задачу порождения цепочки символов по дереву разбора. Интересно попробовать запустить процедуру в обратную сторону и получить все возможные деревья, соответствующие данному списку.

?- nodes(X,[a,b,c],[]).

X = bt(a, empty, bt(b, empty, bt(c, empty, empty))) ;

X = bt(a, empty, bt(b, bt(c, empty, empty), empty)) ;

X = bt(a, bt(b, empty, empty), bt(c, empty, empty)) ;

X = bt(a, bt(b, empty, bt(c, empty, empty)), empty) ;

X = bt(a, bt(b, bt(c, empty, empty), empty), empty) ;

No

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

Рассмотрим грамматику, порождающую язык {aⁿbⁿcⁿ | n>=0}

(1)	S	->	A(N)B(N)C(N)
(2)	A(0)	->
(3)	A(N+1)	->	aA(N)
(4)	B(0)	->
(5)	B(N+1)	->	bB(N)
(6)	C(0)	->
(7)	C(N+1)	->	cC(N)

и возможный вывод цепочки aabbcc в этой грамматике:

S
A(N)B(N)C(N)	(1)
aA(N1)B(N1+1)C(N1+1)	(3), подстановка {N=N1+1}
aaA(N2)B(N2+1+1)C(N2+1+1)	(3), подстановка {N1=N2+1}
aaB(0+1+1)C(0+1+1)	(2), подстановка {N2=0}
aabB(0+1)C(0+1+1)	(5)
aabbB(0)C(0+1+1)	(5)
aabbC(0+1+1)	(4)
aabbcC(0+1)	(7)
aabbcсC(0)	(7)
aabbcc	(6)

Язык {aⁿbⁿcⁿ | n>=0} - классический пример языка, не являющегося контекстно-свободным. Отсюда следует, что DC-грамматики позволяют описывать более широкий класс языков, чем КС-грамматики. В действительности, они могут задавать все языки, описываемые порождающими грамматиками общего вида, то есть все рекурсивно перечислимые языки.

[ Содержание | 1 | 2 | 3 | 4 | 5 | 5.1 | 5.2 | 5.3 | 5.4 | 5.5 | 5.6 | 5.7 | 5.8 | 5.9 | 6 | 6.1 | 6.2 | 6.3 | 6.4 | 6.5 | 7 | 7.1 | Литература ]