Классическая теория компиляторов
 Скачать 1.25 Mb.
|
|
$BMZ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 K K I J - A $SUBS 6 * + := 41 $BR 16 17 18 19 20 21 22 23 24 25 26 27 28 I I 1 + := I I 1 + := L $BRL $BLOCKEND 29 30 31 32 33 34 35 36 37 38 39 40 41 В заключение хотелось бы сделать добавить одно замечание. Хранение оператора, ключевого слова и т.п. в массиве польской формы трудностей не вызывает – мы содержим там лишь числовой код (например, в виде отрицательного числа). Операнды тоже представлены числами – индексами таблицы имен, где хранятся и переменные, и константы. Сложнее обстоит дело со стеком аргументов, необходимым для вычисления польской формы, и в котором хранятся значения рабочих, промежуточных переменных. Это могут быть и целые, и действительные числа, строки, символы, адреса и т.п. Следовательно, необходимо предусмотреть хранение, помимо собственно значения, и типа аргумента, и размера и, возможно, многого другого. На это следует обращать особое внимание при разработке компиляторов. 63 Одним из возможных вариантов организации рабочего стека является использование т.н. тегового стека. В теговом стеке каждый хранимый элемент предваряется неким описателем его типа, называемым тегом. Тег может содержать самую разнообразную информацию, описывающую данные – тип, размер, права доступа и т.д. Для простейшего интерпретатора можно различать такие типы данных, как числовые, строковые и адресные. В качестве адреса в простейшем случае может использоваться целое число – номер записи в таблице имен. ТЕТРАДЫ Добавление тетрад с другими операторами также не вызывает трудностей и происходит аналогично. Тот же фрагмент программы, представленный в форме тетрад, выглядит так: (1) $BLOCK (10) + K, T4, T5 (2) - I, J, T1 (11) := T5,, K (3) $BOUNDS 1, T1 (12) $BR 18 (4) $ADEC A (13) + I, 1, T6 (5) := 0,, K (14) := T6,, I (6) - I, J, T2 (15) + I, 1, T7 (7) $BMZ 13, T2 (16) := T7,, I (8) - I, J, T3 (17) $BRL L (9) * A[T3], 6, T4 (18) $BLOCKEND Здесь используются следующие операторы: Оператор Операнды Описание $BR i переход на i-ю тетраду $BZ (BP,BM) i, P переход на i-ю тетраду, если P=0 (P>0,P<0) $BG (BL,BE) i, P1, P2 переход на i-ю тетраду, если P1>P2 (P1 $BRL P переход на тетраду, номер которой задан в P- м элементе таблицы символов $BOUNDS P1, P2 P1 и P2 описывают граничную пару массива $ADEC P Массив описан в P. Если размерность массива равна n, то этой тетраде должны предшествовать n операторов $BOUNDS, задающих n граничных пар С тетрадой номер 9 могут возникнуть определенные проблемы. Трудности связаны с использованием аргумента в виде переменной с индексом. Решение может заключаться в использовании той же методики, что и в случае описания массивов. 64 Введем пару операторов типа $AINDX I $AGET A, R Здесь $AINDX заносит аргумент I (индекс массива) в специальный стек – стек индексов. Это необходимо для того, чтобы команда $AGET смогла вычислить адрес элемента массива A, используя содержимое стека индексов, и занести значение этого элемента в R. В этот же момент может происходить и очистка стека (по мере извлечения необходимого количества аргументов) Например, выражение "A[1,2]+B[J]" будет представлено в виде $AINDX 1 $AINDX 2 $AGET A, T1 $AINDX J $AGET B, T2 + T1, T2, T3 По такому же принципу может быть организован и вызов подпрограмм. Кстати, здесь особенно явно проявляется роль стека при обращении к подпрограммам. Иллюстрацией этому могут служить наверняка знакомые большинству программистов неприятности со стеком, когда неверно указывается количество или тип аргументов при вызове подпрограмм (особенно в языке С). ОБ ОПЕРАТОРАХ И ВЫРАЖЕНИЯХ Теперь, когда определены основные методы и лексического, и синтаксического анализа, когда ясно, как представимы во внутренних формах основные языковые конструкции, хотелось бы обратить внимание на общий синтаксис языка. Надо быть предельно внимательным при определении таких основных синтаксических категорий, как программа, оператор и выражение. Этот вопрос может оказаться не таким простым и естественным. Например, в языке Си выражения считаются операторами. Отсюда, скажем, вполне работоспособной, хотя и бессмысленной, будет программа, представленная ниже: 65 void main(void) { int a,b; 3-4*b; 1+2; for(2+a;1;) b+1; } Не менее важными являются вопросы вида: что такое пустой оператор? как сделать так, чтоб была возможность ставить или не ставить разделитель операторов (‘;’) перед закрывающей операторной скобкой? и т.д. ОПТИМИЗАЦИЯ ПРОГРАММ Оптимизация программ – это очень объемная тема, на которую написаны (и пишутся до сих пор) многочисленные труды. Здесь мы лишь вкратце затронем этот вопрос. Различают два основных вида оптимизации – машинно-зависимую (МЗО) и машинно-независимую (МНЗО): Оптимизация Машинно-зависимая Машинно-независимая (МЗО) (МНЗО) МЗО связана с типом генерируемых команд и включается в фазу генерации кода (т.е. оптимизации подлежат машинные коды). МЗО напрямую зависит от архитектуры вычислительной машины и потому рассматриваться нами не будет. В отличие от МЗО, МНЗО – отдельная фаза компилятора, предшествующая генерации кода. Она включается на этапе генерации промежуточного кода – внутренней формы представления программы. Оптимизации подлежат: - время выполнения; - емкостные ресурсы (память). Существуют 4 основных типа машинно-независимой оптимизации МНЗО. 66 I. Исключение общих подвыражений (оптимизация линейных участков) Оптимизация линейных участков – это процедура, позволяющая не рассчитывать одно и то же выражение несколько раз, исключая общие подвыражения. Эта процедура разделяется на следующие шаги: - представить выражение в форме, пригодной для обнаружения общих подвыражений; - определить эквивалентность двух и более подвыражений; - исключить повторяющиеся; - изменить команды так, чтобы учесть это исключение. Например, пусть выражение A = c*d*(d*c+b) записано в виде тетрад: (1) * c d T1 (2) * d c T2 (3) + T2 b T3 (4) * T1 T3 T4 (5) = A T4 Упорядочим операнды в алфавитном порядке (там, где это возможно): (1) * c d T1 (2) * c d T2 (3) + T2 b T3 (4) * T1 T3 T4 (5) = A T4 Далее определим границы операторов и найдем общие подвыражения (это (1) и (2)) и затем исключим подвыражение (2). После чего заменим далее везде T2 на T1: (1) * c d T1 (2) + T1 b T3 (3) * T1 T3 T4 (4) = A T4 Этот прием неудобен тем, что возможны варианты, когда либо не представляется возможным отыскать сразу общие выражения, либо в тех случаях, когда b, c, d – функции, имеющие побочный эффект; в этом случае мы можем поломать всю логику вычислений. II. Вычисления на этапе компиляции Если в программе есть участки, в которых присутствуют подвыражения, состоящие из констант, то эти подвыражения можно просчитать на этапе компиляции. Например, вполне возможно заранее вычислить правую часть выражения вида A := 1.5 * 2/3 67 III. Оптимизация булевых выражений Метод основан на использовании свойств булевых выражений. Например, вместо if (a and b and c) then <операторы> endif надо сгенерировать команды таким образом, чтобы исключались лишние проверки. Суть метода состоит в том, что мы строим разветвление условия оператора if. Таким образом, вместо "if (a and b and c) then <операторы> endif" получим: if not a then goto Label if not b then goto Label if not c then goto Label <операторы> Label: //метка перехода Проблемы, связанные с использованием этого метода, заключаются в том, что, во-первых, могут проявиться побочные эффекты в тех случаях, когда аргументами являются функции, а во-вторых, "оптимизированный" код может получиться более громоздким по сравнению с оригиналом. IV. Вынесение инвариантных вычислений за пределы цикла Это – один из наиболее эффективных методов оптимизации, дающий весьма ощутимые результаты. for i:=1 to 10 do begin ………. a:=b+c; // инвариант ………. end Для реализации метода необходимо: - распознать инвариант; - определить место переноса; - перенести инвариант. Неудобства метода: - отследить инвариант нелегко, т.к. аргументы могут косвенно зависеть от переменной цикла; - не учитываются побочные эффекты, если аргументы инварианта являются функциями (или зависимыми от них). 68 Проблемы, связанные с оптимизацией Итак, очевидно, что необходимо сопоставлять ожидаемый выигрыш от повышения эффективности объектной программы с дополнительными накладными расходами, связанными с увеличением времени компиляции, надежности и сложности самого компилятора. Во-вторых, с оптимизаций зачастую связаны такие "неприятности", как даже ухудшение кода, сложность трассировки оптимизированных программ. Кроме того, бывает очень сложно выявить и/или устранить возникающие "побочные" эффекты. Например, пусть мы работаем со стеком, используя функции push() для записи числа в стек и pop() для извлечения числа. Если нам надо извлечь пару чисел из стека и поместить обратно в стек их логическую сумму, то мы можем написать что-то вроде A := pop(); B := pop(); C := A || B; push(C); Причем этот вариант является обычно более предпочтительным перед компактным вида push(pop() || pop()), ибо скорее всего оптимизирующий компилятор превратит это выражение в push(pop()), сочтя второй pop() лишним (он честно будет использовать логическую парадигму A || A A). Это типичный пример побочных эффектов оптимизации. Выводы 1. Необходимо сопоставлять затраты на оптимизацию с ожидаемым эффектом. 2. Оптимизация не всегда приводит к улучшению кода – могут появиться побочные эффекты. Либо после оптимизации получается более громоздкий код. 3. Чем больше вычислительной работы перекладывается на этап компиляции, тем эффективнее будет выполняться программа. 4. Более предпочтительной для МНЗО является внутренняя форма представления программы в виде тетрад. 5. Лучший метод оптимизации – писать хорошие (грамотные) программы. 69 ИНТЕРПРЕТАТОРЫ По большому счету все то, что изучалось выше, предназначалось для того, чтобы дать необходимый теоретический базис и практические навыки и приемы, необходимые для построения интерпретатора – простейшего в ряду транслятор-компилятор-интерпретатор. Итак, мы уже знаем, что интерпретатор – это программа, которая - транслирует исходную программу на языке высокого уровня во внутреннее представление; - выполняет (интерпретирует) программу, представленную на этом внутреннем языке. Интерпретатор прост. Его логическая структура напоминает урезанный компилятор. Интерпретаторы хороши для обучения (когда большая часть времени уходит на отладку) и для тех языков, в которых много времени уходит на работу системных программ (работа с матрицами, базами данных и т.п.). Достоинства интерпретаторов - простота (не надо реализовывать генерацию объектного кода); - удобство и простота отладки программ – все внутренние структуры нам доступны (прежде всего – это доступ к таблице символов в любой момент времени), легки трассировка, отслеживание обращений к меткам и переменным (например, при установке флага проверки обращения в той же таблице символов) и т.п.; - возможность включения интерпретируемых выражений в процессе выполнения программы (самомодификация программы). Именно поэтому интерпретаторы наиболее часто применяются при разработке новых (не случайно сначала был создан именно интерпретатор языка С) и сложных языков – скажем, Пролог и Смолток в классическом варианте являются интерпретируемыми языками. Недостатки интерпретаторов Основным недостатком интерпретатора является малая, "по определению", скорость выполнения программы, т.к. при запуске нам необходимо выполнить все фазы анализа. Для устранения этого недостатка приходится платить упрощением синтаксиса языка, т.е. его грамматики. (Львиная доля времени работы интерпретатора приходится на анализ – лексический и синтаксический). В связи с этим наиболее простыми для реализации являются языки командного типа. В таких языках каждое предложение – это команда (императив) вида "<команда> [<аргументы>]". 70 Наиболее эффективной формой внутреннего представления программы для интерпретатора является польская форма записи. Тогда основной частью интерпретатора является переключатель CASE: while TRUE do begin case gettype(P[n]) of operand: Push(S,P[n]); operator: arg1 := Pop(); arg2 := Pop(); Push(arg1 @ arg2); else: error(); endcase n := n+1 end Выше уже говорилось о том, что при реализации интерпретатора возникает проблема представления в стеке аргументов различных типов данных. На практике существуют 4 типа аргументов: - константы, - имена, - адреса переменных (адрес значения, номер элемента таблицы), - указатели (поле "Значение" содержит номер (адрес) элемента в таблице символов). Зачастую между этими понятиями существует некоторая путаница. Обычно это касается понятий адреса и указателя. Для наглядности их можно изобразить на следующем рисунке: Адрес Значение addr value addr * Указатель P @ Адрес A Существуют два основных способа хранения типа операнда (напомним, что в массиве польской формы записи операнды представляют собой положительные числа – адреса элементов в таблице имен). Во-первых, различать типы данных можно, используя аналогию с байт-кодом. Либо можно хранить аргумент, предваряя его элементом, указывающим тип (о теговом стеке говорилось выше). Во-вторых, тип элемента можно держать в таблице имен, и тогда в польской форме мы будем хранить лишь адреса. Если первый метод обеспечивает максимальное быстродействие (можно сразу определить тип аргумента, не обращаясь к таблице имен), то второй способ 71 хранения более компактен. Как всегда, за все надо платить. Тем не менее, второй способ является более предпочтительным – он "красивее" и естественней. Кроме того, очевидна необходимость наличия механизма проверки типов и соответствующих функций конвертирования. Вроде следующих: cvPV (pointer to value) – конвертация указателя в значение; cvPA (pointer to address) – конвертация указателя в адрес; cvAV (address to value) – конвертация адреса в значение. Для увеличения эффективности выполнения программы можно заранее вставлять в польскую форму записи процедуры конверсии типов (напомним основной принцип – не оставлять на время выполнения программы то, что можно сделать на этапе компиляции). И последние замечания по поводу возможной реализации интерпретатора. Трассировка. Можно легко и просто включить режим трассировки значений переменных. Например, установить флаг в таблице переменных и в соответствии с ним выводить значение переменной при обращении к ней по чтению и/или записи. Аналогично можно поступать и с метками, и с подпрограммами. Для диагностики ошибок можно вставлять в польскую форму записи нумерацию строк исходной программы – некоторые фиктивные операторы, нужные только для отладки. При реализации языка, в котором существуют подпрограммы, необходимо четко представлять себе механизм их вызова. Хороший сканер поместит в таблицу имен не только имя самой подпрограммы, но и ее тип, и количество и типы аргументов. Эта информация нужна будет для того, чтобы, выполняя оператор передачи управления $CALL, система взяла бы из стека необходимое количество операндов и могла бы поместить обратно значение, возвращаемое функцией. Кроме того, следует помнить и о локальных переменных, определенных внутри подпрограммы. Наиболее приемлемым способом избавиться от "засорения" таблицы имен локальными переменными является помещение их в стек. Тогда естественным образом будет решена и проблема их видимости. Обычно интерпретатор – это самостоятельная программа, что зачастую создает некоторые проблемы, связанные с мобильностью программного обеспечения (в том смысле, что один исполняемый файл удобнее пары – исходный текст программы плюс интерпретатор). Однако существуют т.н. "скрытые" или "неявные" интерпретаторы. Реализация неявного 72 интерпретатора заключается в том, что формируется исполняемый файл, содержащий в себе как непосредственно интерпретатор, так и исходный текст программы (почти в явном виде). Это приводит к тому, что внешне мы имеем исполняемый модуль, который, однако, занимается не чем иным, как интерпретацией со всеми вытекающими отсюда последствиями – достоинствами и недостатками. Типичным примером подобных систем является старая система программирования Clipper. Пишутся интерпретаторы обычно на языках высокого уровня. И особенно полезными являются здесь принципы объектно-ориентированного программирования. Однако зачастую эффективнее бывает технология, при которой сначала создается макетный интерпретатор, реализованный, скажем, на Прологе. Макетный интерпретатор является полигоном для отладки структуры языка, он, естественно, прост, но малоэффективен с точки зрения скорости интерпретации. Тем не менее, Пролог для отладки структуры языка – незаменимое средство. Интерпретатор языка, среднего между Бейсиком и Паскалем, можно написать за 2-3 дня, и занимать он будет 400-500 строк (личный рекорд автора – это интерпретатор языка, в котором есть циклы, условные операторы, операторные скобки и полная арифметика с набором математических функций, который был написан за два вечера и занимал чуть более 400 строк). После отладки структуры языка можно браться за реализацию интерпретатора и на более эффективных с вычислительной точки зрения языках. КОМПИЛЯТОРЫ КОМПИЛЯТОРОВ Выше мы уже упоминали о компиляторах компиляторов (КК) – системах, позволяющих создавать компиляторы. На самом деле КК – это некий инструментарий программиста, помогающий создавать компиляторы (или интерпретаторы). Создавая множество компиляторов или постоянно модифицируя грамматику разрабатываемого языка (к сожалению, далеко не всегда можно заранее ясно определить структуру и синтаксис), разработчик, естественно, желает некоторым образом автоматизировать некие рутинные процедуры. Не случайно все рассмотренные нами методы анализа по возможности представлялись в формальном виде. Все они могли быть автоматизированы. Имея регулярную грамматику лексической структуры можно, автоматически сгенерировать сканер в виде конечного автомата. Имея грамматику синтаксической структуры, можно написать универсальную процедуру синтаксически управляемого перевода (или создать универсальный МП-автомат). 73 Следовательно, по крайней мере эти две наименее творческие и наиболее сложные и рутинные составляющие компилятора можно сгенерировать автоматически. Для этого потребуется некоторое описание двух наших грамматик – грамматики для сканера и грамматики для реализации синтаксического анализатора. Это описание вполне можно хранить в некотором файле. И тогда мы получим своего рода специальный входной язык – язык описания компилятора. Разумеется, получить на выходе готовый компилятор мы не сможем. В лучшем случае на выходе будут некоторые фрагменты компилятора: Описание компилятора Описание лексики //Ключевые слова begin, end, program, … //Однолитерные лексемы + - * / …. //Двухлитерные лексемы ++ -- := // … Описание синтаксиса … КК Сканер Синтак- сический анализатор А дальше разработчику все равно необходимо будет самостоятельно добавлять семантические процедуры. С семантикой без него все равно ни один КК не справится. И еще пара замечаний. Во-первых, при описании синтаксиса желательно правила грамматики записывать как можно в более естественной форме, при этом отделяя синтаксические категории от терминальных символов (скажем, заключая синтаксические категории в угловые скобки). С одной стороны, это сделает описание более удобочитаемым, а с другой – позволит КК легко разделять символы обоих словарей (терминального и нетерминального). Во-вторых, нельзя забывать про наличие в схеме СУ-перевода (если КК реализует именно этот метод) еще двух составляющих – условия применимости правила грамматики и семантической процедуры. Все это тоже должно быть описано. Если описать семантическую процедуру достаточно просто, то с условием применения все гораздо сложнее. Ведь 74 условие, в общем случае, может быть представлено произвольным логическим выражением. Дабы не заниматься его анализом с последующим вычислением, можно посоветовать сразу записывать это выражение в польской форме. Получится хоть не совсем красиво, зато удобно и очень просто. И последнее. Познакомиться с описанием одного из наиболее почтенных КК можно в замечательной книге Кернигана и Пайка (см. библиографию). Описанный там КК YACC (Yet Another C Compiler – еще один компилятор С или Yet Another Compiler Compiler – еще один компилятор компиляторов) представляет весьма мощный инструмент, хотя использование его – занятие весьма утомительное. На самом же деле пользоваться надо своим собственным инструментарием. КК – это один из немногих продуктов, ценность которого определяется его "эксклюзивностью". Ведь не случайно создание по-настоящему эффективных компиляторов определяется квалификацией разработчиков, их опытом и, вообще говоря, уровнем их «школы». Потому до сих пор велика конкуренция на рынке компиляторов и трансляторов, эффективность которых у одних производителей заметно отличается от того, что делают другие. Кстати, зачастую бывает и так, что у одного и того же производителя компиляторы для разных языков получаются совсем разного качества. 75 ПРИЛОЖЕНИЕ. ВВЕДЕНИЕ В ПРОЛОГ Одна из наиболее сложных задач изучаемого курса – познакомиться с совершенно новым и необычным языком программирования – языком Пролог. Этот язык интересует нас с точки зрения его применимости для построения важнейшей части любого компилятора – синтаксического анализатора. Как мы убедимся далее, Пролог для этой цели подходит более всех других языков. Пролог – это достаточно "древний" язык. Он был создан в 1973 Алэном Колмеро во Франции, в Марсельском университете. Особенно популярен Пролог в Европе и в Японии. В 1981 г., анонсируя проект создания ЭВМ пятого поколения, японцы выбрали именно Пролог в качестве базового языка программирования. Пролог считается одним из языков искусственного интеллекта. Его название происходит от аббревиатуры PROgramming in LOGic (ПРОграммирование ЛОГики) – ПРОЛОГ. Действительно, основа языка Пролог – математическая логика. Пролог знаменует собой важный этап в эволюции языков программирования: движение от языков низкого уровня, пользуясь которыми программисты описывают, как что-либо следует делать (традиционные процедурно-ориентированные), к языкам высокого уровня, в которых указывается, что необходимо делать (декларативные языки). Пролог – язык программирования, предназначенный для обработки символьной (нечисловой) информации. Особенно хорошо он приспособлен для решения задач, в которых фигурируют объекты и отношения между ними. Язык этот весьма прост. Его реализация содержит ограниченный набор механизмов: сопоставление образцов, древовидное представление структур данных и автоматический поиск с возвратом. Классический Пролог относится к интерпретируемым языкам. Первый интерпретатор Пролога был написан на Фортране. Впоследствии было создано множество версий языка для разнообразнейших программно- аппаратных платформ, были даже созданы компиляторы Пролога, однако, несмотря даже на отсутствие стандартов Пролога (де факто таковым считается "марсельская" версия), его идеология, внутренние механизмы остаются неизменными. ОПИСАНИЕ ВЗАИМООТНОШЕНИЙ МЕЖДУ ОБЪЕКТАМИ Как уже говорилось, Пролог создан для того, чтобы описывать взаимоотношения между объектами. В этом смысле Пролог можно назвать реляционным языком. "Реляционность" Пролога является значительно более мощной и развитой по сравнению с реляционными языками, используемыми 76 для работы с базами данных. Именно поэтому зачастую Пролог используется для создания СУБД, в которых применяются сверхсложные запросы и процедуры поиска. Пусть у нас есть несколько объектов. Обозначим их именами a, b, c, d, e и f. Рассмотрим отношение типа "родитель" между этими объектами: (a) (b) (c) (d) (e) (f) (g) родитель родитель родитель родитель родитель родитель Отношения в Прологе определяются в общем случае заданием имени отношения и n-ки объектов, для которых это отношение выполняется. На Прологе эта схема будет представлена следующей программой из 6 предложений (фактов): родитель(a, c). родитель(b, c). родитель(b, d). родитель(c, e). родитель(c, f). родитель(f, g). Аргументы отношения могут быть атомами (конкретными объектами или константами) или переменными – абстрактными объектами. Здесь объекты a, b, c, d, e, f – это атомы (константы). Обратите внимание на то, что они записываются строчными буквами. Константы на Прологе бывают символьного типа, строкового типа, а также константы – числа. В данном случае мы имеем дело именно с символьными константами. Как обычно, константа – это то, что имеет неизменное значение. родитель – это бинарное отношение (отношение второго порядка). С тем же успехом можно было бы дополнить нашу схему, добавив отношения первого порядка. Например: женщина (a). мужчина (b). мужчина (c). 77 и т.д. Классический Пролог является интерактивной средой: он позволяет пользователю задавать системе вопросы и, естественно, получать на них ответы. После ввода рассмотренной выше программы Пролог-системе можно будет задавать различные вопросы. Синтаксис постановки вопроса на языке Пролог выглядит так: ? утверждение Для ответа на тот или иной вопрос система ищет в базе данных имеющиеся факты и правила, подтверждающие утверждение и при нахождении таковых отвечает утвердительно, в противном случае – отрицательно. С этой точки зрения можно считать, что Пролог пытается доказать введенное в качестве вопроса утверждение. Например: ? – родитель (a, c) Да ? – родитель (a,e) Нет и т.п. Можно задавать и вопросы вида: ?- родитель(a, X) X = c Да ?- родитель(X, c) X = a X = b Да ?- родитель(X, Y) X=a Y=c X=b Y=c X=b Y=d X=c Y=e X=c Y=f X=f Y=g Да 78 Таким образом, система отыщет всевозможные варианты значений переменной X. О переменных мы поговорим несколько позже, а здесь отметим лишь, что переменная – это то, что может принимать некоторые значения и обозначается именем, начинающимся с заглавной буквы. СОСТАВНЫЕ ВОПРОСЫ Пролог умеет отвечать не только на такие примитивные вопросы, какие были приведены выше. Вопросы могут быть сложными, образующими логические выражения. Примером составного вопроса является вопрос вида "кто является родителем родителя?". Для того чтобы задать такой вопрос, определим понятие "родитель родителя" следующим образом. Некто X является родителем родителя Z, если этот X – родитель некоторого Y, а этот Y является родителем для Z. Это утверждение может быть записано в виде логического выражения, представляющего коньюнкцию. В Прологе операция И обозначается ключевым словом and либо запятой: родитель(X,Y) and родитель (Y,Z) Найдем родителя и "деда" объекта g: (X) (Y) (g) родитель родитель Родитель родителя Тогда наш вопрос может выглядеть так: ?- родитель(X,Y), родитель(Y, g) Реакция системы на этот вопрос будет заключаться в выдаче значений переменных X и Y: X = c Y = f Обратите внимание на то, что наш вопрос мог быть записан и в таком виде: ?- родитель(Y, g), родитель(X,Y) Результат будет тем же самым, однако, как это будет видно далее, эффективность поиска в этом случае будет выше. 79 ПРАВИЛА Введем отношение "отпрыск". Можно изобразить аналогичную вышеприведенной схему отношений и ввести еще 6 предложений-фактов. Однако значительно элегантнее определить отношение "отпрыск" (отношение, противоположное отношению "родитель") следующим образом: С точки зрения формальной логики понятие "отпрыск" можно определить так: Для любых X и Y Y является отпрыском X, если X – родитель Y. На Прологе это будет записано в виде следующего предложения: отпрыск(Y,X) :- родитель(X,Y). Подобные предложения называются правилами. Правило имеет условную часть (посылку – антецедент) и часть вывода (заключение – консеквент). Если в привычном виде правило записывается как Если (антецедент) То (консеквент), то в Прологе правило выглядит иначе – сначала записывается заключение, а затем посылка: Заключение if Посылка Посылка в Прологе называется телом правила, а заключение – головой правила. (Голова) if (Тело) Например, отношение родитель_родителя может быть представлено в виде правила родитель_родителя(X,Z) :- родитель(X,Y), родитель(Y,Z). А отношение "сестра" может быть определено так: (X) (Z) (Y) родитель родитель Сестра сестра(X,Y) :- родитель(Z,X), родитель(Z,Y), женщина(X). 80 ПРОЛОГ С МАТЕМАТИЧЕСКОЙ ТОЧКИ ЗРЕНИЯ Пролог рассматривает факты и правила в качестве множества аксиом, а вопрос пользователя – как теорему. Пролог пытается доказать эту теорему, т.е. показать, что ее можно логически вывести из аксиом. Для примера рассмотрим известный силлогизм Аристотеля: Все люди смертны. Сократ-человек. Следовательно, Сократ смертен Более формально: (Все люди смертны = Для любого X: X – человек => X смертен) Х: Х – человек Х – смертен Сократ – человек Сократ смертен На Прологе это будет выглядеть так: смертен(X) :- человек(X). человек(сократ). ?- смертен(сократ) Да ФОРМАЛИЗМ ЯЗЫКА ПРОЛОГ Итак, подытожим вышеизложенное. С формальной точки зрения Пролог-программа состоит из предложений. Каждое предложение заканчивается точкой. Предложения Пролога состоят из головы и тела. Тело – список целей, разделенных запятыми. Запятые обозначают операцию конъюнкции. Предложения Пролога бывают трех типов: факты, правила и вопросы. - Факты содержат утверждения, которые всегда истинны. Факт – это предложение, у которого тело пустое. - Правила содержат утверждения, истинность которых зависит от некоторых условий. Имеют голову и непустое тело. - С помощью вопросов пользователь спрашивает систему о том, какие утверждения являются истинными. Вопрос – это предложение, состоящее только из тела. Вопросы к системе состоят из одного или более целевых утверждений (целей). ПЕРЕМЕННЫЕ Переменные обозначаются идентификаторами, начинающимися с заглавной буквы. В Прологе переменная представляет собой объект, способный принимать различные значения. Однако на этом сходство прологовской переменной с переменными в процедурных языках программирования 81 заканчивается. Переменная в Прологе может быть либо свободной (или неконкретизированной), либо несвободной (конкретизированной). Конкретизация переменной происходит тогда, когда по ходу вычислений вместо переменной подставляется другой объект (переменная получает конкретное значение и становится несвободной). С этого момента переменная не может принять другое значение. Переменная определяется только внутри предиката (никаких "глобальных" переменных в Прологе не существует). Строго говоря, предполагается, что на переменные действует квантор всеобщности ("для всех"). И именно в этом состоит смысл понятия переменной. МЕХАНИЗМ ПОИСКА РЕШЕНИЯ Разберемся с тем, каким образом работает поисковая система Пролога. Когда задается вопрос, интерпретатор Пролога начинает последовательно проверять (доказывать) истинность всех составляющих его коньюнктов. Проверяя очередной коньюнкт, система начинает просмотр имеющейся базы данных и правил. С каждым из выбираемых фактов и правил Пролог сначала пытается сопоставить доказываемое утверждение. Сопоставление термов. Все объекты данных в Прологе синтаксически представляют собой термы. Термы сопоставимы, если: - они идентичны; - можно конкретизировать переменные терма таким образом, чтобы они стали идентичными. Если термы сопоставимы, то система продолжает доказывать истинность входящих в сопоставленный терм утверждений и т.д. При этом, однако, в системном стеке запоминается точка возврата – местоположение этого сопоставленного терма. Иными словами, система Пролог реализует некоторое дерево поиска, причем поиск этот осуществляется в глубину, вплоть до исчерпывания всего пути поиска. Если на очередном шаге поиска могут быть сопоставлены несколько термов, то система запоминает в стеке номера этих термов с тем, чтобы можно было в дальнейшем попытаться использовать и эти альтернативы. Именно так и осуществляется механизм поиска с возвратом. РЕКУРСИВНЫЕ ПРАВИЛА В Прологе нет циклов. Все итерационные процедуры осуществляются с помощью рекурсии. Кроме того, рекурсия играет, естественно, и самостоятельную роль. Например, можно определить отношение "предок" (предок в самом общем смысле) следующим образом: 82 предок(X,Z) :- родитель(X,Z). предок(X,Z) :- родитель(X,Y), предок(Y,Z). Повторение. Организовать циклические вычисления можно с помощью простого предиката repeat: repeat. repeat :- repeat. Первое правило всегда истинно. Оно необходимо для создания точки возврата, когда сработает рекурсивный repeat. Следовательно, нам достаточно заставить систему перейти к альтернативному варианту, и мы тогда получим бесконечный цикл. Например, предикат echo будет запрашивать пользователя ввод строки, выводить ее на экран. И продолжаться это будет до тех пор, пока пользователь не введет строку "quit": echo:- repeat, write("Введите строку (quit-выход)"), readln(S), S="quit". Дело в том, что в последней строке происходит сравнение введенной строки со строкой "quit". Если строки не совпадают, то система вернется к предыдущей альтернативной точке. Таковой является предикат repeat (недаром их у нас два варианта). Система пробует очередной вариант его выполнения и тем самым попадает в бесконечную рекурсию – в бесконечный цикл. А вот если строки совпадут, то тогда выполнение предиката echo будет считаться успешным. Приведем еще один пример применения рекурсивного правила. Следующий предикат вычисляет сумму ряда: sum(1,1). sum(N,Summ) :- N>0, Next = N-1, sum(Next,Sum2), Summ = N+Sum2. СПИСКИ Очень важной структурой в Прологе является список – некий аналог массива. Все списки однородные, т.е. состоят из элементов одного типа – только чисел, только строк и т.п. Очень характерно, как определяет списки сам Пролог. В Прологе список – это структура, состоящая из головы и хвоста. Голова – это один 83 элемент. Хвост – это список. Список может и не содержать элементов. Тогда он называется пустым списком. Правила определения списка могут выглядеть так: Список [] Список Голова, Хвост Голова элемент Хвост Список Список задается перечислением его элементов, заключенным в квадратные скобки. Разделение списка на голову и хвост происходит указанием специального разделителя – символа '|'. Примеры списков: [1,3,8,1,6], [a, b, ec ], ["абв", "где", "жз"] При этом в списке [1,3,8,1,6] голова – это элемент 1, а хвост – это список [3,8,1,6]: [ 1 | 3 , 8 , 1 , 6 ] голова хвост Знание того, как определяется список в Прологе, позволяет понять, как пишутся предикаты для работы с ними. Например, предикат, распечатывающий список, может выглядеть так: print_list([]) :- !. print_list([H|Tail]) :- write(H), print_list (Tail). Другим примером может служить замечательный предикат append. Это – удивительный предикат. Он столь же прост, сколько и универсален. Если разобраться, как он работает, то можно считать, что вы как минимум наполовину знаете устройство Пролога. Выглядит он весьма просто: append([],L,L). append([H|A],B,[H|C]) :- append(A,B,C). Этот предикат может конкатенировать (сцеплять) два списка, он может проверять, составляет ли конкатенация пары списков третий, он может даже разделять список на все возможные пары его составляющих. Именно это и делается в приведенной ниже программе, которая выводит на экран все возможные разбиения списка: 84 goal s([1,2,3,4]). clauses append([],L,L). append([H|A],B,[H|C]) :- append(A,B,C). print_list([]) :- !. print_list([H|Tail]) :- write(H), print_list (Tail). s(S) :- append(L1,L2,S), print_list(L1), print_list(L2), fail. s(_) :- !. О том, что такое ! и fail, будет сказано ниже. УПРАВЛЕНИЕ ПОИСКОМ Откат после неудачи. Предикат fail всегда заканчивается неудачей. Вместо него можно было бы использовать какое-нибудь априорно ложное утверждение (например, 1=2), однако с ним программа выглядит элегантнее. Следующий предикат выводит на экран все имеющиеся имена. show_all :- name(X), fail. name("Петров"). name("Иванов"). name("Сидоров"). Если бы не fail, то выполнение предиката закончилось бы выводом одного-единственного имени. Правило выдачи на экран “эха”, использующее уже знакомый repeat, но уже в бесконечном цикле, выглядит так: echo:- repeat, readln(S), write(S), fail. Здесь fail служит для того, чтобы реализовать откат после неудачи. Еще раз отметим, что откат происходит к repeat, т.к. в нем существует как 85 минимум две возможности реализации repeat. Это правило порождает бесконечное число точек возврата. Отсечение. Иногда бывает необходимо ограничить круг поиска, т.е. заставить систему "забыть" о существовании альтернативных вариантов – точек возврата. Фактически речь идет о задаче отсечения ненужных результатов. Этой цели служит предикат cut или '!' (в Прологе вообще любят все сокращать – вместо and – запятая, вместо cut – восклицательный знак, вместо or – точка с запятой ';'). Пользоваться этим предикатом нужно очень осторожно. А лучше стараться не пользоваться вовсе (во всяком случае без крайней необходимости). Этот предикат всегда истинен. Он отсекает все точки возврата, находящиеся до него (иными словами, этот предикат очищает стек точек возвратов). Примеры использования предиката cut: show_somebody :- name(X), make_cut(X), !. make_cut(X) :- X="anonymous". echo :- repeat, readln(S), write(S), check(X), !. check(S) :- S="stop". check(_) :- fail. ПРИМЕРЫ ПРОГРАММ Изучение и понимание языков немыслимо без практики и уж тем белее без примеров. Несмотря на ограниченность объема и чрезмерную «лаконичность» изложения основ Пролога, тем не менее будет весьма полезно ознакомиться с решением двух классических Прологовских задач. Кроме того, в конце будет приведен ряд некоторых полезных предикатов, иллюстрирующих логику решения задач. 86 Программа поиска всех циклов в графе Эта программа позволяет находить все простые циклы в графе. Очевидно, что поиск циклов построен на основе предиката way2 , который ищет пути из заданных начальной и конечной вершин. Его задача заключается в том, чтоб сформировать найденный путь в виде списка, при этом в пути не должно быть повторяющихся вершин. % Программа поиска всех циклов в графе domains ilist = integer * predicates % Ребро графа a(integer,integer) % Поиск пути из FROM в TO. RES - результат, % OLDWAY - уже пройденный путь. way2(integer,integer,ilist,ilist) % (FROM, TO, RES, OLDWAY) % Печать списка print_list(ilist) % Проверка принадлежности элемента списку isin(integer,ilist) % Поиск всех циклов findallcirc goal findallcirc, write("\nDone."). clauses findallcirc :- way2(FROM,FROM,W,[]), write(FROM,": "), print_list(W), fail. findallcirc :- !. isin(E,[E|_]). isin(E,[_|Tail]) :- isin(E,Tail). print_list([]) :- nl. print_list([H|Tail]) :- write(H," "), print_list(Tail). way2(X,Y,[Y],OLDWAY) :- 87 a(X,Y), not(isin(Y,OLDWAY)). way2(X,Y,[Z|W2],OLDWAY) :- a(X,Z), not(isin(Z,OLDWAY)), way2(Z,Y,W2,[Z|OLDWAY]). % Описание ребер графа a(1,2). a(1,5). a(2,3). a(3,4). a(2,5). a(4,1). a(5,4). a(3,6). a(6,2). Анализатор арифметических выражений Этот пример должен продемонстрировать, насколько легко решаются с использованием Пролога задачи синтаксического анализа. На входе – анализируемая строка символов, на выходе – польская форма. Здесь реализван даже примитивный сканер, хотя лексический анализ – это сугубо процедурная часть и лучше реализовавать ее именно на процедурных языках. Тем не менее, использование встроенного предиката fronttoken позволяет решить хоть в каком-то виде и эту задачу. Предикат fronttoken выделяет лексему из строки. % Очень простой анализатор арифметических выражений. % Занимается сканированием строки символов и формированием % польской формы записи исходного выражения. DOMAINS strlist = string* PREDICATES % Сканер. На входе - строка, на выходе - поток лексем scanstr(string,strlist) % Синтаксический анализатор. На входе - поток лексем (список), % на выходе - польская форма записи recognize(strlist,strlist) % Служебные и вспомогательные предикаты printlist(strlist) a2(strlist,strlist,strlist) a3(strlist,strlist,strlist,strlist) % Грамматика. Второй аргумент - это фрагмент сформированной %с помощью правила польской формы E(strlist,strlist) 88 T(strlist,strlist) F(strlist,strlist) % Проверка того, является ли список именем. Проверяется именно % список, а не элемент. Это нужно для большей общности. isitname(strlist) GOAL %%% Входная строка INPUTSTR="b+ c/(d -e)", %%% Сканирование scanstr(INPUTSTR,STRLEXEMS), write("\nПоток лексем:\n"), printlist(STRLEXEMS), nl, %%% Распознавание и формирование польской формы recognize(STRLEXEMS,POLAND), write("\nПольская форма:\n"), printlist(POLAND), write("\nГотово.\n"). CLAUSES %%% ------------------- Сканер scanstr("",[]). scanstr(S,[Token|TLrest]) :- fronttoken(S,Token,Rest), scanstr(Rest,TLrest). %%% ------------------- Вспомогательные предикаты a2([],L,L). a2([H|A],B,[H|C]) :- a2(A,B,C). a3(L1,L2,L3,L) :- a2(L1,LX,L), a2(L2,L3,LX). printlist([]). printlist([H|Tail]) :- write(H," "), printlist(Tail). isitname([N|[]]) :- isname(N). %%% ------------------- Основной предикат recognize(L,PF) :- E(L,PF). %%% ------------------- Синтаксические правила % E->E+T 89 E(L,A) :- a3(L1,["+"],L3,L), E(L1,A1), T(L3,A2), a3(A1,A2,["+"],A). % E->E-T E(L,A) :- a3(L1,["-"],L3,L), E(L1,A1), T(L3,A2), a3(A1,A2,["-"],A). % E->T E(L,A) :- T(L,A). % T->T*F T(L,A) :- a3(L1,["*"],L3,L), T(L1,A1), F(L3,A2), a3(A1,A2,["*"],A). % T->T/F T(L,A) :- a3(L1,["/"],L3,L), T(L1,A1), F(L3,A2), a3(A1,A2,["/"],A). % T->F T(L,A) :- F(L,A). % F->name F(L,L) :- isitname(L). % F->(E) F(L,A) :- a3(["("],L1,[")"],L), E(L1,A). Некоторые полезные предикаты Приведенные ниже предикаты иллюстрируют принципы решения типовых прологовских задач. Определение минимума и максимума двух чисел Обратите внимание на использование предиката отсечения. Он необходим для ликвидации возможной точки возврата. min2(A,B,A) :- A < B, !. min2(_,B,B). max2(A,B,A) :- A > B, !. max2(_,B,B). Определение принадлежности элемента списку member(X,[X|_]) :- !. member(X,[_|T]) :- member(X,T). 90 Выборка элемента списка по его индексу index([X|_],1,X) :- !. index([_|L],N,X) :- N>1, N1=N-1, index(L,N1,X). Вычисление длины списка list_len([], 0). list_len ([_|T], N) :- list_len (T, N2), N = N2+1. Вычисление суммы элементов списка (а заодно и его длины) sum_list([], 0, 0). sum_list([H|T], SUM, NUMBER) :- sum_list(T, SUM1, NUMBER1), SUM = H+SUM1, NUMBER = NUMBER1+1. Инверсия списка reverse(X,Y) :- reverse1([],X,Y). reverse1(Y,[],Y). reverse1(X1,[U|X2],Y) :- reverse1([U|X1],X2,Y). Вычисление максимального элемента списка max_in([X],X):- !. max_in([H|T],H):- max_in(T,R), R max_in2([A],A). max_in2 ([H|T],M) :- max_in2 (T,M1), max2(H,M1,M). Удаление элемента из списка delete(_,[],[]). delete(X,[X|Y],Y):- !. delete(X,[A|Y],[A|Z]):- delete(X,Y,Z). 91 БИБЛИОГРАФИЧЕСКИЙ СПИСОК 1. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. В 2-х томах. Том 1. М.: Мир, 1978. –616с. 2. Ахо А., Моника С. Лам М., Рави Сети Р., Ульман Дж. Компиляторы. Принципы, технологии и инструментарий. – Вильямс, 2003. – 768 с. 3. Грис Д. Конструирование компиляторов для цифровых вычислительных машин /Пер.с англ. –М.: Мир, 1975. 4. Донован Дж. Системное программирование /Пер.с англ. –М.: Мир, 1975. – 540с. 5. Ин Ц., Соломон Д. Использование Турбо-пролога. –М.: Мир, 1993. 6. Керниган Б.В., Пайк Р. UNIX – универсальная среда программирования /Пер.с англ. Березко, Иващенко. Под ред. М.И.Белякова –М.: Финансы и статистика, 1992. –304 с. 7. Марселлус Д. Программирование экспертных систем на Турбо-прологе. – М.: Финансы и статистика, 1994, –254с. 8. Хантер Р. Проектирование и конструирование компиляторов. –М.: Финансы и статистика, 1984. |