Факультет вычислительной математики и кибернетики КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Факультет вычислительной математики и кибернетики А.И. ЕНИКЕЕВ ЯЗЫКИ ПРОГРАММИРОВАНИЯ И МЕТОДЫ ТРАНСЛЯЦИИ КАЗАНЬ 2005 год. СОДЕРЖАНИЕ ПРЕДИСЛОВИЕ……………………………………………………….. 4 1.ВВЕДЕНИЕ ……………………………………………………………5 2.Системы программирования. Классификация и методы программирования……………………………………………………….. 2.1.Основные понятия и определения.………………………………. 2.2. Классификация языков программирования.…………………... 2.3.Функциональные языки программирования .…………………... 2.3.1.Простейшие приемы программирования. 2.3.2.Обработка списков. 2.3.2.1. Операции над списками. 2.3.2.2. Примеры программ. 2.3.2.3. Дополнительные средства функционального программирования. 2.4. Спецификация , верификация и синтез программ.Основные понятия 2.5. Системы параллельного программирования.Теория взаимодействующих процессов и ее использование для спецификации и анализа параллельных процессов . 2.5.1. Следы процессов. 2.5.1.1. Конкатенация. 2.5.1.2. Префикс. 2.5.1.3. Операция "после". 2.5.1.4. Проекция . 2.5.1.5. Последовательная композиция . 2.5.1.6. Переименование . 2.5.2.Теория процессов. 2.5.2.1 . Операция присоединения символа . 2.5.2.2 . Альтернативная операция . 2.5.2.3. Начальное состояние процесса . 2.5.2.4. Операция "после". 2.5.2.5. Последовательная композиция . 2.5.2.6. Параллельная композиция. 2.5.2.7. Взаимодействие параллельных процессов. 2.5.3. Язык параллельного программирования OCCAM. 2.6. Объектно-ориентированное программирование. 2.6.1.Основные определения и принципы. 2.6.2. Visual FoxPro - пример объектно-ориентированной СУБД. 3.Теория и методы трансляции. 3.1. Определение языка. 3.1.1.Синтаксис . 3.1.2.Семантика . 3.2. Основные этапы компиляции. 3.3. Лексический анализ. 3.4. Синтаксический анализ. 3.4.1. Цель синтаксического анализа. 3.4.2. Нисходящий синтаксический анализ . 3.4.3. Восходящий синтаксический анализ . 3.4.4. Префиксная и постфиксная записи выражений. 3.5. Семантический анализ. 3.6.Этап синтеза . 3.6.1. Распределение памяти. 3.6.2. Генерация кода. 3.6.3. Оптимизация кода. Л И Т Е Р АТ У Р А……………………………………………………….. ПРЕДИСЛОВИЕ . Пособие предназначено для студентов и преподавателей , специализирующихся в области разработки и реализации систем программирования . Может также представлять интерес для специалистов в области разработки системного программного обеспечения .Цель пособия - дать концептуальное понимание систем программирования , принципов их разработки и реализации на основе гибкого сочетания математического базиса теории программирования с практическими подходами . Особое внимание уделяется методам компиляции . Пособие представляет сокращенный вариант лекционного курса "ЯЗЫКИ ПРОГРАММИРОВАНИЯ И МЕТОДЫ ТРАНСЛЯЦИИ" , читаемого для студентов факультета вычислительной математики и кибернетики Казанского государственного университета в настоящее время автором пособия. 1.ВВЕДЕНИЕ . В начале 70-х годов идеологи применения математических моделей в программировании Скотт и Стрэйчи (авторы целого ряда работ по l-исчислению и денотационной семантике) , работавшие в то время в Оксфордском университе Великобритании ,охарактеризовали в одной из своих публикаций текущее состояние разработок и исследований по программному обеспечению следующим высказыванием. … В настоящее время состояние , сложившееся в программировании, определяется достаточно большим разрывом между теорией и практикой . С одной стороны мы имеем достаточно изощренные средства математического моделирования , которые тем не менее являются стерильными и совершенно непригодны для анализа и исследования практических разработок в области программирования . С другой стороны имеется большое количество прагматически - - ориентированных серых, громоздких и неуклюжих программных разработок , в которых отсутствует концептуальная целостность и логическая взаимосвязь между составляющими частями . Поэтому главной задачей в этой связи является создание промежуточных теорий , которые сохраняя математическую строгость и лаконичность , позволили бы их использовать для предварительного анализа и исследования разрабатываемого программного продукта с целью получения эффективного и качественного результата . Несмотря на то , что с тех пор прошло более 30 лет , ситуация в этом плане кардинально не изменилась. Революционные изменения в компьютерных технологиях и новых способах программирования , происшедшие за это время , наоборот еще более рельефнее высветили упомянутую выше проблему, правда на более высоком уровне развития. Сложность и многообразие разрабатываемых программных средств , увеличившиеся с тех пор на порядки , обусловили еще большую актуальность этапа предварительных исследований на основе адекватного математического моделирования разрабатываемого программного продукта . Следует признать , что в последнее время появилось достаточно много результатов в области теории программирования и многие теоретические результаты нашли свое применение в практике программирования ( это касается например разработки автоматизированных средств перевода с одних естественных языков в другие , создания эффективных генераторов компиляторов , практического использования теоретических результатов по синтезу программ для создания интеллектуальных генераторов программ в объектно-ориентированных средах программирования и т.п.). Однако , с другой стороны , появившиеся в последнее десятиление объектно-ориентированные системы программирования представляли из себя продукт , основаный скорее на интуитивных аспектах программирования , нежели на теоретических . Несмотря на появление языков моделирования для объектно -ориентированного подхода ( например UML - унифицированного языка моделирования ) , в настоящее время не существует теории , которая могла бы претендовать на адекватное описание и анализ объектно-ориентированной среды программирования . Поэтому методика изложения материала данного пособия основывается, насколько это возможно , на гибком сочетании теоретических аспектов программирования с прагматическими задачами.Кроме этого в пределах данного пособия ставится цель систематизировать полученные теоретические и практические результаты по системам программирования и методам реализации этих систем . Поэтому представляемый материал состоит из двух основных разделов . Первый посвящен классификации систем программирования с описанием различных методов программирования в разных системах . Во втором разделе предлагается материал по средствам реализации систем программирования , представленный теоретическими и практическими результатами по разработке компиляторов. 2.Системы программирования. Классификация и методы программирования. 2.1.Основные понятия и определения. Системы программирования представляют одну из важнейших составляющих программного обеспечения компьютерных технологий. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ Системы про- граммирования Операци-онные системы Проблемно-ориентированное ПО Системное ПО Место систем программирования в общей классификации программного обеспечения показано на рис. 2.1-1. Рис.2.1-1.Классификация программного обеспечения. Система программирования определяется следующими составными частями : язык программирования ,транслятор и интегрированная среда разработки. Язык программирования - это формальный язык , предназначенный для описания (кодирования) алгоритмов решения различных задач. Транслятор - это программа, которая переводит текст исходной программы в эквивалентную объектную программу. Если объектный язык представляет собой ассемблер или некоторый машинный язык, то транслятор называется компилятором. Интегрированная среда разработки -это библиотека сервисных программ , предназначенных для автоматизации процессов разработки , программирования и отладки ( понятие интегрированной среды разработки возникло с появлением объектно-ориентированного программирования , однако в том или ином виде это понятие присутствует также в процедурно-ориентированных системах программирования ) . 2.2. Классификация языков программирования. Существует много разных способов классификации языков программирования. Традиционно все это сводится к следующему. Универсальные и проблемно-ориентированные языки программирования . Язык программирования относится к универсальным языкам , если он обеспечивает возможность программирования широкого спектра задач. В случае ориентации на решение специализированного класса задач , мы имеем дело с проблемно-ориентированными языками программирования . Языки высокого и низкого уровня. К языкам низкого уровня относятся машинные языки и ассемблеры. Все остальные языки принято относить к языкам высокого уровня . Однако необходимо иметь в виду наличие языков высокого уровня , в которые для удобства включены средства программирования низкого уровня . Примером является язык программирования C . Машинно- ориентированные и машинно - независимые языки программирования . Языки программирования , зависящие от специфики определенного типа компьютеров , называются машинно- - ориентированными. Все остальные относятся к машинно- независимым языкам .К машинно- ориентированным языкам традиционно принято относить машинные языки и ассемблеры . Однако из этого вовсе не следует , что все остальные языки программирования автоматически можно отнести к машинно-независимым языкам . Имеются языки программирования ,в которых содержатся машинно-ориентированная и машинно- независимые части. Операторные и функциональные языки программирования . К операторным языкам программирования относится большинство традиционных языков ( PASCAL , C и т.п.) , в которых имеются понятия операторов и функций . В отличие от операторных , в функциональных языках программирования отсутствует понятие оператора , а программа строится в виде суперпозиции функций. Классическим примером является функциональный язык программирования LISP . Процедурно- ориентированные и объектно-ориентированные языки программирования . Процедурно- ориентированные языки программирования основаны на традиционном подходе к созданию программного обеспечения , при котором основным строительным блоком является процедура или функция . При объектно-ориентированном подходе в качестве основного строительного блока в процессе программирования выступает объект , принадлежащий определенному классу (являющийся экземпляром определенного класса ) . Содержательно класс можно рассматривать как некий абстрактный объект, наделяемый свойствами , характерными для некоторого множества объектов . Языки компилируемого и интерпретируемого типов .Язык программирования относится к языкам компилируемого типа , если в результате трансляции текста исходной программы получается объектная программа на ассемблере или на некотором машинном языке. Языки интерпретируемого типа предусматривают получение в результате трансляции так называемого промежуточного кода, выполнение которого осуществляется специальной программой , называемой интерпретатором. Иными словами , для языков интерпретируемого типа происходит частичная компиляция , завершаемая генерацией промежуточного кода. Например , язык LISP относится к языкам интерпретируемого типа , а язык PASCAL -к языкам компилируемого типа . Замечания к разделу . Приведенная классификация никоим образом не претендует на полноту , так как кроме приведенных выше типов языков , существуют языки логического программирования , языки параллельного программирования , языки управления базами данных , языки искусственного интелекта и т.п. 2.3.Функциональные языки программирования . Функциональное программирование -это способ составления программ , в котором единственным действием является вызов функции, единственным способом расчленения на части -введение имени для функции и задание для этого имени выражения , вычисляющего значение функции , единственным правилом композиции - суперпозиция функций . В этом разделе предлагаются элементы функционального программирования на основе языка программирования LISP. Раздел никоим образом не претендует на руководство по программированию на языке LISP , его цель - знакомство с основными принципами функционального стиля программирования . В предлагаемом ниже изложении функционального стиля программирования в целях более прозрачного описания материала автор намеренно отходит в ряде случаев от классической LISP- нотации , что по мнению автора не затрагивает принципы функционального программирования. Наиболее удачное изложение принципов функционального программирования можно найти в книге [ 1 ] . 2.3.1.Простейшие приемы программирования. В основе функционального программирования лежит определение функции в виде так называемого выражения l - выражения . Функция F определяется следующим образом : F(x,y.z)=df lx,y,z . PF , где x,y,z - аргументы , а PF -выражение , определяющее способ вычисления функции F. Замечание. Для определенности мы рассматриваем здесь функцию от трех переменных . В общем случае функция может содержать любое количество аргументов. Примеры: 1) (n-факториал) fact(n) )=df ln. IF(n=0,1,n*fact(n-1)) 2) (наибольший общий делитель) gcd(m,n) )=df lm,n.IF(mod(m,n)=0,n,gcd(n, mod(m,n))) , где mod(m,n) - остаток от деления m на n . Замечания. 1) Функция IF(b,P,Q) определяется следующим образом : ì P , если логическое выражение b истинно IF(b,P,Q)= í îQ , в противном случае . 2) В классической LISP-нотации функция записывается в виде (F,x,y,z,…) , где F - имя функции (операции) , x,y,z,…- аргументы , например (IF,b,P,Q) ,(MOD,m,n) , (EQ, n ,0 ) вместо n=0 , (EQ,(MOD,m,n),0) вместо mod(m,n)=0, и т.п. Однако в целях удобства изложения будем использовать привычную математическую нотацию. 3) Основным признаком функционального стиля программирования является рекурсивное определение функций , характеризуемое "обращением самой к себе " . Умение "адекватно" программировать рекурсивно определяемые алгоритмы требует хорошего представления о специфике реализации рекурсии. В отличие от итерационного способа программирования выполнение рекурсивно определяемой программы происходит в два этапа . На первом этапе осуществляется построение рекурсивных соотношений и частичное вычисление с задержкой выполнения действий , которые не могут быть выполнены на данном этапе.Задержка вычислений обусловливается тем , что в описании рекурсивно определяемой функции всегда присутствует явное или косвенное обращение к той же самой функции . Первый этап завершается после выполнения так называемого условия завершения рекурсии. На втором этапе осуществляется полное завершение всех задержанных действий путем последовательного "сворачивания" рекурсивных соотношений.Например , при реализации функции вычисления факториала , если n=4, результатом первого этапа является следующая последовательность : fact(4)=4*fact(3) fact(3)=3*fact(2) fact(2)=2*fact(1) fact(1)=1*fact(0) fact(0)=1 . Условием завершения рекурсии здесь является n=0 . Сворачивание рекурсивных соотношений на втором этапе происходит путем выполнения соответствующих подстановок , в результате чего получается соотношение : fact(4)=4*3*2*1 . 4) В отличие от многих языков программирования в функциональных языках программирования отсутствует строгое описание типов переменных , предполагая , что тип переменной определяется в момент присваивания ей значения . Упражнения к разделу.Запрограммировать следующие функции : 1) max(m,n) - максимальное из чисел m,n ; 2) sum(n)=1+2+…+n ; 3) exp(n,k)=nk -возвести в степень , используя умножение (k-целое); 4) sumexp(n)=11 + 22 + …+ nn ; 2.3.2.Обработка списков. Списком называется последовательность элементов , являющихся атомами (т.е. неразложимыми данными) или , в свою очередь , списками. Атомы представляются константами , именами переменных и функций. Для обозначения пустого списка используется nil . Примеры списков: 1) ("ДЖОН" , "СМИТ" ,33,"ГОДА") ; 2) (x,(y,15),("A","B","C")) 5) () - пустой список (или nil ) ; 6) (F,x,y) 2.3.2.1.Операции над списками. Над списками определены следующие операции: 1) head(s) -первый (головной) элемент списка s (s ¹ nil ) ; 2) tail(s) -список , получающийся из списка s удалением первого элемента ( tail(nil)= nil ) ; 3) cons(a,s) -список , получающийся в результате добавления элемента a в начало списка s ; 4) ìtrue , если a - атом atom(a)= í îfalse , в противном случае . Из перечисленных выше определений очевидным образом следует соотношение t= cons(a,s) - head(t)= a & tail(t)=s . Примеры. 1) Пусть s=(a,b,c) , тогда а) head(s)=a ; б) tail(s)= (b,c) ; в) cons("d",s)=("d", a,b,c) ; г) tail(tail(tail(s)))=nil; д) atom(s)=false; е) atom(head(s))=true . 2) Пусть s= ((a,b,c),d,(x,y)) , тогда а) head(s)= (a,b,c) ; б) tail(s)= (d,(x,y)) ; в) cons((m,n),s) = ((m,n),(a,b,c),d,(x,y)) ; г) atom(head(head(s)))=true . 2.3.2.2.Примеры программ. 1) Нахождение максимального элемента числового списка s. Сначала определим функцию max2(x,y) , значением которой является максимальное из чисел x,y : max2(x,y) )=df lx,y. IF( x>y ,x ,y ).Теперь функция нахождения максимального элемента списка может быть определена так : max(s) )=df ls.IF(tail(s)=nil , head(s) , max2(head(s),max(tail(s))) ) . 2) Вычисление суммы всех элементов числового списка s . sum(s) )=df ls. IF(tail(s)=nil , head(s) ,head(s) + sum(tail(s)) ) . 3) Удаление последнего элемента из списка s. del(s) =df ls. IF(tail(s)=nil , nil , cons(head(s),del(tail(s)) ) . 4) Определение семантики оператора while b do P . while(b,P) =df ls. IF( b, cons(P, while(b,P)) , nil ) . Замечание. В отличие от операторных языков программирования в функциональных языках программирования отсутствует понятие оператора и процедуры. Поэтому программистам , привыкшим к операторному стилю, приходится сталкиваться с определенными трудностями при программировании посредством функциональных средств. Например , рекурсивное определение оператора while b do P с точки зрения операторного стиля могло бы иметь следующий вид : while b do P=df IF b then (P; while b do P) . Однако отсутствие оператора последовательной композиции в функциональном программировании вынуждает нас заменить конструкцию (P; while b do P) на cons(P, while(b,P)) , где функция cons имеет чисто вспомогательную роль и используется для соединения последовательно выполняемых функций. С таким же успехом вместо функции cons мы могли бы использовать любую 2-х местную функцию при условии корректного согласования типов аргументов. Что же касается отсутствия процедур , то известно , что любую процедуру можно определить посредством соответствующей эквивалентной функции . Упражнения к разделу. Запрограммировать следующие функции : 1) инвертирование списка ( например , (a,b,c,d, e ) => (e,d,c,b,a) ); 2) преобразование структурного списка в линейный, т.е. удаление из списка всех внутренних скобок ( например , ( (a,b) ,c, (d, e) ) => =>(a,b,c,d, e ) ) ; 3) удаление из списка первых n-элементов (если n ³ числа элементов списка , результат - nil ) ; 4) удаление из списка последних n-элементов (если n ³ числа элементов списка , результат - nil ) ; 5) ìtrue , если s=t Iseq(s,t)= í îfalse , в противном случае , где s и t - списки . 2.3.2.3.Дополнительные средства функционального программирования. Кроме перечисленных в предыдущих разделах средств , при составлении функциональных программ нам необходимы средства ввода -вывода , присваивания и т.п.. Эти средства представлены следующими функциями : 1) input(s) - ввод переменной , получаемой в результате вычисления выражения s (s¹ nil) ; 2) output(s) - вывод результата вычисления выражения s ; 3) setq(s1 ,s2 ) - присвоение результата вычисления выражения s2 переменной , которая получается в результате вычисления выражения s1 ( s1 ¹ nil ) ; 4) apply(f,s) - применение функции с именем , получаемым в результате вычисления выражения f , к списку аргументов , который является результатом вычисления выражения s ; 5) quote(s) - значением этой функции является само выражение s (содержательно эта функция задерживает вычисление выражения s , которое в данном случае рассматривается как константа ) ; 6) eval(s) - значением этой функции является результат вычисления выражения s ( в частности , если вычисление выражения было задержано функцией quote , функция eval позволяет отменить задержку и вычислить значение соответствующего выражения ) ; 7) list(s,t) - значением этой функции является список (s,t) . При использовании средств функционального программирования следует учитывать , что функциональные программы , в свою очередь , представляются в виде списков. Как уже было отмечено в р. 2.3.1 , функциональная программа вида F( x,y,…) , где F - имя функции , x,y,… -аргументы функции , представляется в виде списка (F , x,y,…) . Поэтому в необходимых случаях функциональные программы можно рассматривать как данные , являющиеся объектом преобразования и обработки.Это свойство , сводящееся по сути к возможности динамического изменения программы в процессе ее выполнения , является весьма привлекательным с точки зрения создания интеллектуальных программ . Однако , с точки зрения технологии программирования использование этой возможности является "правилом дурного тона " , посколько может привести к серьезным затруднениям при тестировании и отладке программ . Примеры. 1) Пусть s=(x,y) , тогда : а) input(head(s))=input(x) - ввод переменной x ; б) output(head(tail(s)))=output(y) -вывод переменной y ; в) setq(head(s), head(tail(s)))= setq(x,y) - переменной x присваивается значение переменной y ; г) list(input(head(s)), setq(x,y)) = list(input(x) , setq(y,x)) - сначала вводится значение переменной x , затем переменной y присваивается значение переменной x ( функция list играет в этом примере лишь вспомогательную роль , обеспечивая соответствующую последовательность действий ) . 2) Пусть s=(cons, x, y ) и t= ("b","c") , тогда : а) apply(quote(head(s)),("a",t)) =apply(quote(cons) , ("a",t))=cons("a",t)= =cons("a",("b","c")) = ("a","b","c") ; б) cons("a",(t)) = cons("a",(("b","c")))= ("a",("b","c")) ; в) list("a",quote(t)) = ("a" , t) ; г) list("a",t) = ("a" , ("b","c")) . Упражнения к разделу.Запрограммировать следующие операции над полиномами : 1) умножение полинома на одночлен ; 2) умножение полинома на полином ; 3) приведение подобных членов . Указание: полином С1 x1 + С2 x2 +…+Cn xn представляется в виде списка : ((С1 ,1),( С2 ,x2 ),…,( Cn ,xn )) . 2.4. Спецификация , верификация и синтез программ. Основные понятия. Процессу разработки любой программы всегда предшествует этап постановки задачи на программирование.Успех разработки и последующего внедрения программы во многом зависит от того , насколько точно и хорошо было сделано описание соответствующей задачи . Такое описание называют спецификацией задачи . Так как саму программу также можно рассматривать в качестве описания задачи , для решения которой она создана , возникает вопрос , чем же спецификация отличается от алгоритма решения задачи . Многие авторы полагают , что спецификация в отличие от программы (алгоритма) должна описывать , что надо сделать , а не как это делать , подчеркивая тем самым непроцедурный характер спецификации. Однако задача может быть процедурной по своей природе и , кроме того, процедурность может быть высокого уровня , свободная от деталей реализации , которые должны обязательно присутствовать в любой работающей программе. В связи с этим представляется более целесообразным говорить о процедурных и непроцедурных спецификациях , имея в виду , что непроцедурные спецификации , как правило , описывают постановку задачи ,а процедурные - способ ее решения. Часто процедурные спецификации называют программными спецификациями , но в отличие от самих программ в программных спецификациях отсутствуют, как правило , детали реализации. Примеры спецификаций. 1) Максимум от чисел a и b : ì a, если a>b max(a,b) = í î b , если a £ b . 2) Наибольший общий делитель натуральных чисел m и n : ì n, если m mod n=0 gcd(m, n) = í î gcd(n, m mod n) , если m mod n¹ 0 . 3) Максимальный элемент множества чисел M : z=max(M) - zÎ M & (" x.xÎM => z ³ x) С понятием спецификации тесно связано понятие надежности программы . Программа является надежной , если она разработана в полном соответствии со своей спецификацией . Отсюда следует , что не всякая надежная программа обязательно является правильной , так как сама спецификация может содержать ошибки .Соответствие программы ее спецификации проверяется тестированием. Однако , позволяя выявить допущенные в программе ошибки , процесс тестирования не позволяет как правило обосновать их отсутствие. В связи с этим в программировании возникло понятие верификации программ . Под верификацией программы понимается процесс формального доказательства ее корректности (надежности) . Предоставляя возможность доказательства отсутствия ошибок в программе , методы верификации тем не менее не нашли применения в практическом программировании из-за их чрезмерной громоздкости и сложности. Однако , знание методов верификации является полезным для разработчиков программ , так как эти методы позволяют более точно и концептуально оценивать суть программирования и стимулируют строгую и скрупулезную проверку всех промежуточных этапов процесса разработки программ . Альтернативой верификациии является синтез программ , заключающийся в автоматическом построении программы по ее спецификации .Синтез является более привлекательным , нежели верификация , поскольку в результате синтеза должны получаться готовые корректные программы при условии корректной работы "синтезатора" . Разработка универсальных средств синтеза программ относится к классу алгоритмически неразрешимых проблем , однако из этого вовсе не следует , что использование синтеза программ на практике обречено на неудачу. При определенном ограничении классов решаемых задач идея синтеза программ находит свое применение при создании генераторов программ. Об этом свидетельствуют работы по созданию интегрированной среды разработки современных объектно-ориентированных систем [2,3]. Реализация интегрированной среды разработки основывается на интеллектуальных генераторах программ , которые по сути можно отнести к средствам синтеза программ. При использовании спецификаций в разработке программ , а также реализации интеллектуальных генераторов программ одной из основных задач является выбор формализованного языка спецификаций и установление соответствия между конструкциями языков спецификаций и программирования. Это соответствие может устанавливаться путем описания семантики базисных средств языка программирования средствами языка спецификаций или наоборот. Рассмотрим один из способов спецификации операторов языка программирования , основанный на языке исчисления предикатов [4]. Введем понятие состояния программы через состояние переменных программы , в свою очередь определяемого через таблицу значений переменных программы. Состояние программы представляет из себя динамически изменяемый объект в процессе выполнения программы , которое может меняться в результате выполнения отдельной программной конструкции (функции , оператора,модуля ). Пусть s={x,y,… } -состояние программы (состояние переменных) до выполнения некоторой программной конструкции P , а s'={x',y',…}- состояние программы после выполнения конструкции P . Тогда для спецификации конструкции P мы можем использовать предикат YP (s,s') , показывающий , как изменились значения переменных x,y,… в результате выполнения конструкции P. В дальнейшем ,для простоты изложения материала, ограничимся рассмотрением только двух переменных x,y , полагая , что все последующие рассуждения и выводы легко обобщаются на случай любого числа переменных ) . Тождественный оператор. Спецификация тождественного оператора IDENT определяется как : IDENT=df (x'=x) & (y'=y) . Из спецификации следует , что тождественный оператор оставляет неизменными все значения переменных . Оператор присваивания. Пусть P- спецификация , x - программная переменная и e- выражение , не содержащее штрихованных переменных (т.е. переменных x',y'). Тогда выражение x:=e;P является спецификацией программной конструкции , которая сначала присваивает переменной x значение выражения e , затем выполняется в соответствии со спецификацией P . Пусть (ex -> P) обозначает выражение , получаемое из P путем замены всех свободных вхождений переменной x на e и De -область определения выражения e . Тогда : x:=e;P =df ù ( De )Ú (ex -> P) Примеры: 1) x:=x+y;IDENT = (x'=x+1&y'=y) ; 2) (y:=y/x; (x:=x+y;IDENT)) = (x=0) Ú ( x'=x+y/x & y'=y/x ) Условный оператор. Пусть P и Q -спецификации и b - логическое выражение , не содержащее штрихованных переменных . Тогда выражение if b then P else Q является спецификацией программной конструкции , которая выполняется как P , если b -истинно , и как Q - в противном случае . Пусть Db -область определения выражения b . Тогда : if b then P else Q=df ù ( Db )Ú (b&P) Ú (ù b&Q) Последовательная композиция. Пусть P - спецификация , содержащая переменную p , значением которой может быть любая допустимая спецификация . Тогда , если Q - некоторая спецификация , определим выражение (Qp ->>P) как соотношение , получаемое заменой всех вхождений переменной p на Q в выражении P. Содержательно точки вхождения переменной p в этом случае можно рассматривать как вызов процедуры или функции со спецификацией Q . Важно отметить , что данная операция подстановки (Qp ->>P) имеет более высокий приоритет, нежели операция подстановки (ex -> P) , то есть в любом случае : Qp ->>( ex -> P)= (ex ->( Qp ->> P)) . Выделим специальную переменную SKIP для обозначения успешного завершения программной конструкции . Пусть P и Q - некоторые специФикации, тогда последовательную композицию можно определить следующим образом : P;Q =df QSKIP ->>P . Содержательно , выражение P;Q определяет программную конструкцию, которая выполняется в соответствии со спецификацией P , и после успешного завершения конструкции P выполняется в соответствии со спецификацией Q . Например , в конструкции y:=y/x ; Q переход на выполнение Q может осуществиться только при x¹ 0 . Примеры: 1) if b then P = if b then P else SKIP 2) SKIP;P=P;SKIP=P . Оператор цикла "while" . Спецификацию циклического оператора определим рекурсивным образом : while b do P=df if b then(P; while b do P) else SKIP , где b -логическое выражение , а P - спецификация тела цикла . Использование аппарата спецификаций оказывается более эффективным , если , кроме описания семантики программ , имеется возможностьисследования их свойств . Исследование свойств программ может быть сделано на основе алгебраических соотношений , использование которых обеспечивает возможность эффективного и обоснованного перехода от спецификаций к соответствующим программным конструкциям. В исследовании свойств программ одним из важных аспектов является семантическая эквивалентность программных конструкций. Программные конструкции являются эквивалентными , тогда и только тогда , когда их соответствующие спецификации - эквивалентны. В данном случае мы рассматриваем логические спецификации , а для логических выражений понятие эквивалентности определено. С содержательной точки зрения программы являются эквивалентными , если они предназначены для решения одной и той же задачи. Примеры соотношений: 1) Db => (if b then P else P) = P ; 2) if b then P else Q = if ù b then Q else P ; 3) x:=e ; if b then P else Q = IF ( ex -> b) then ( x:=e ; P) else ( x:=e ; Q) ; 4) SKIP;P=P;SKIP=P ; 5) P; (Q ; R) = (P; Q) ; R Доказательства перечисленных выше свойств могут быть проделаны на основе свойств исчисления предикатов (правил вывода ) и вышеприведенных определений спецификаций программных конструкций . Ниже приводится перечень классических соотношений из математической логики , являющихся полезными с точки зрения доказательства свойств : 1) P & P - P ; 2) ( P Ú Q ) - ù (ù P & ù Q) ; 3) ( P & Q ) - ù (ù P Ú ù Q) ; 4) (P & Q) - (Q & P) ; 5) (P Ú Q) - (Q Ú P) ; 6) ù (ù P ) - P ; 7) (P Ú ( Q &R ) ) - (P Ú Q ) & (P Ú R) ; 8) (P & ( Q Ú R ) ) - (P & Q ) Ú (P & R) ; 9) ( P - Q ) - ( P => Q ) & ( Q=>P ) ; 10) P Ú TRUE - TRUE ; 11) P & TRUE - P ; 12) P Ú FALSE - P ; 13) P & FALSE - FALSE ; 14) ù ( TRUE ) - FALSE ; 15) ù ( FALSE ) - TRUE ; Пример доказательства . Доказать : if b then P else Q = if ù b then Q else P . Доказательство : if b then P else Q = =ù ( Db )Ú (b&P) Ú (ù b&Q)= (по определению) =ù ( Db )Ú (ù b&Q ) Ú (b&P))= ( коммутативность) = if ù b then Q else P (по определению) 2.5. Системы параллельного программирования.Теория взаимодействующих процессов и ее использование для спецификации и анализа параллельных процессов . Появление систем параллельных вычислений было вызвано необходимостью существенного увеличения скорости компьютерного решения задач . Появление многопроцессорных вычислительных комплексов , компьютерных сетей и многозадачных операционных систем , основанных на концепции мультипрограммирования , обеспечили реальную базу для практической реализации параллельных вычислений .Содержательно , идея параллельного программирования сводится к декомпозиции проблемы на несколько подзадач, которые выполняются одновременно. Средства связи между параллельно решаемыми задачами , предусматривающие взаимодействие между соответствующими процессами , обеспечивают кооперативное решение проблемы. Существуют разные модели параллелизма , но наиболее распостраненными являются так называемая конвейерная модель и модели параллелизма данных, основанные на одновременном применение одних и тех же операций к различным частям структуры данных . В настоящее время средства параллельного программирования практически встроены в большинство объектно- ориентированных систем управления базами данных. Задача разработки программных средств , обеспечивающих параллельное выполнение процессов , представляется достаточно сложной и поэтому требует построения адекватных математических моделей , позволяющих всесторонне исследовать природу параллельных процессов с целью принятия правильных решений по разработке и реализации алгоримов параллельных вычислений . К настоящему времени сформировалось множество разных подходов к выбору математического аппарата для исследования параллельных процессов. Один из наиболее интересных подходов , сочетающий математическую строгость и адекватность практической реализации , представляет теория взаимодействующих процессов CSP ( Communicating Sequential Processes ) [5]. Теория базируется на следующих ниже понятиях . Событие - спецификация существенного факта , имеющего положение в пространстве и во времени. С точки зрения теории автоматов событие- - это возникновение стимула , который может активизировать переход из одного состояния в другое . Событие является атомарным (неразложимым понятием) теории CSP. Примерами событий могут быть возникновение какой либо ошибки в процессе выполнении программ , выполнение определенного запланированного условия , выбор элемента меню , активация командной кнопки , нажатие функциональной клавиши и т.п. . Каждое событие кодируется определенным символом. Множество символов , определяющее все события , в которых некоторый процесс может участвовать , определяет алфавит процесса . След (трасса) - последовательность событий , определяющая один из возможных путей поведения некоторого процесса , начиная с начала выполнения процесса до определенного фиксированного момента времени. Процесс определяется множеством следов в некотором фиксированном алфавите . Теория CSP позволяет создавать модели параллельно выполняемых взаимодействующих процессов с целью исследования свойств процессов . Результаты этих исследований могут оказаться полезными для принятия обоснованных решений на последующих стадиях разработки и реализации соответствующего программного продукта. В данном пособии рассматривается усеченный вариант теории CSP , включающий теоретико - множественную и процедурную модели. 2.5.1. Следы процессов. Многие свойства процессов можно доказать , рассматривая соответ-ствующие свойства следов - последовательностей событий из заданного алфавита A . Пусть A * означает множество всевозможных следов в алфавите A . Пустой след обозначается как <> , а выражение ( c->s ) означает результат приписывания символа ( события ) c к следу s . Базисные свойства следов определяются следующими : Ax1. <> Î A * Ax2. ( c Î A ) & ( s Î A * ) - ( c->s ) Î A * Ax3. ( c->s )= ( d-> t ) - c = d & s = t Ax4. ( c->s ) ¹ <> Ax5.( (<> Î S ) & (" cÎ A ." sÎ S . (c -> s) Î S)) => S Í A * В дальнейшем будем буквами a, b, c, d обозначать события , буквами s, t ,u, v - следы , буквами P ,Q, R, S ,T - процессы . Например , s=< a,b,c,d > - обозначает след s , состоящий из событий a,b,c,d ; ( c-> <>)= < c > ; ( a ->< b,c,d > ) = < a,b,c,d > . Аксиома Ax5 обосновывает корректность применения метода структурной индукции при доказательстве свойств следов . Ниже приводится суть этого метода. Пусть требуется доказать утверждение Y ( s, t ,u ,…) для любых s Î A * . Доказательство строится из следующих шагов (индукция по длине cледа s) . B(базис индукции) . Доказываем Y ( <>, t , u ,…) для всех t , u ,… . I ( индукционная гипотеза ) . Предполагаем , что Y ( s, t ,u ,…) истинно для некоторого s Î A * и для всех t , u ,… . S (шаг индукции) . Доказываем Y ( c->s, t , u ,…) для всех сÎ A . В результате заключаем , что утверждение Y ( s, t ,u ,…) истинно для всех s Î A * . Аналогично проводится процесс доказательства для всех остальных переменных t ,u ,… . Пример доказательства. Докажем свойство Ax6. ( c-> s ) ¹ <> методом структурной индукции по s . B(базис индукции) . Согласно Ax4 имеем ( c-> <> ) ¹ <> для всех сÎ A . I ( индукционная гипотеза ) . ( c-> s ) ¹ <> для всех сÎ A . S (шаг индукции) . Согласно Ax3 и индукционной гипотезе имеем ( c-> ( c-> s ) ) ¹ ( c-> s ) ; кроме того , для всех d , где d ¹ c , по Ax3 имеем ( d-> ( c-> s ) ) ¹ ( c-> s ) . Таким образом , последнее соотношение имеет место независимо от того ,c=d или c ¹ d , и свойство Ax6 доказано. Если s ¹ <> , то будем обозначать через s0 первый символ , а через s' - результат удаления первого символа из следа s . Формально это определяется так : Ax7. ( c-> s )0 =c Ax8. ( c-> s )' =s . Отсюда можно вывести свойство : Ax9. ( c-> s ) = t - ( t ¹ <> ) & ( t0 = c & t' = s) В LISP - нотации следы можно представлять списками . Например : <> - nil (пустой список) ; ( c-> s ) - cons( "c" , s ) ; s0 - head( s ) ; s' - tail( s ) . 2.5.1.1. Конкатенация. Через st обозначается результат конкатенации следов s и t . Формально это определяется следующим образом : c1. <> t = t , c2. ( c-> s) t = c-> ( st ) Операция конкатенации в LISP - нотации описывается функцией append( s, t ) , определяемой как append( s, t )= df ls,t . IF( s=<> , t ,cons ( s0 ,append(s',t) ) ) Для этой операции справедливы следующие свойства : c3. s = s<> ; c4. ( st )u = s( tu ) ; c5 st = su - t = u ; c6. st = <> - s = <> & t = <> ; c7. stÎ A * - s Î A * & t Î A * . Перечисленные свойства доказываются методом структурной индукции. В качестве примера докажем свойство c4 : B(базис индукции) . ( <> t )u = <>( tu ) ( согласно c1 ) . I ( индукционная гипотеза ) . Пусть ( st )u = s( tu ) для некоторого s . S (шаг индукции) . ( (c->s)t )u = (c->(st))u (согласно c2) = c-> ((st)u) u (согласно c2) = c-> (s(tu)) (по индукционной гипотезе) = (c -> s )( tu ) (согласно c2) Для полного завершения доказательства следует провести аналогичное доказательство по переменной t . Упражнения к разделу . Доказать свойства c3 , c5-c7 . 2.5.1.2. Префикс. След s является префиксом следа t (обозначается , как s £ t ), если t начинается с копии s . Формально это определяется так : p1 . s £ t = df $ u (su=t ) . Cправедливы следующие свойства префикса : p2 . <> £ t , для любого следа t ; p3. ù (( c->s ) £ <> ) ; p4. ( c->s ) £ ( d-> t ) - c = d & s £ t Упражнения к разделу . Сформулировать какие-нибудь другие свойства префикса и доказать их . 2.5.1.3. Операция "после". Пусть s £ t . Тогда операция t/s ( читается t после s) определяется следующими аксиомами : a1. t/<> = t ; a2. ( c-> t )/ (c->s) =t/s Пример . < a,b,c,d >/< a,b > = < c,d > . Cправедливы следующие свойства операции "после" : a3. (st)/s=t ; a4. s £ t => s( t/s )= t ; a5. ((s £ t)& (s£ u)&(t/s=u/s))=> t=u ; a6. (su) £ t => t/(su)= (t/s)/u . Данную операцию можно определить с помощью LISP -нотации следующим образом : t/s = df after( t, s ) , где after( t, s )= df lt,s . IF( s=<> , t ,after( t' , s' )) Упражнения к разделу . Доказать свойства a3 - a5 . 2.5.1.4. Проекция . Пусть B -множество символов , а s -след . Тогда проекция следа s на множество B ( обозначение s é B) получается удалением из следа s всех символов , не принадлежащих множеству B . Формально эта операция определяется следующими аксиомами : r1. <> é B = <> ; r2. c Î B => (c-s) é B =c->(s é B) ; r3. c Ï B => (c-s) é B =c->(s é B) ; Cправедливы следующие свойства проекции : r4. s é { } =<> ; r5. (st) é B = (s é B)(t é B) ; r6. (s é C) é B=s é (CÇ B) ; r7. s é B = s - sÎ B* ; Примеры . < a,b > é { a,c } = <a> < a ,c > é { a,c } = <a,c> < a,b,c,d > é { e } = <> Упражнения к разделу . Доказать свойства r4 - r7 . 2.5.1.5. Последовательная композиция . Будем использовать специальный символ Ö для обозначения успешного завершения следа . Тогда через ( s ; t ) обозначается след , получившийся в результате подстановки следа t вместо первого вхождения символа Ö в s и удаления остатка следа s (то есть той части следа s , которая следует после символа Ö ) . Если s не содержит Ö , то s ; t = s . Формально эту операцию можно определить так : s1. <> ; t=<> ; s2. (<Ö >s ) ;t = t ; s3. ( c->s );t = c-> (s;t) , c¹Ö . Поскольку символ Ö является признаком успешного завершения следа , то будем исключать из рассмотрения случаи , когда Ö появляется внутри следа ( например , <a,b,Ö ,c > ) , то есть в любом случае имеет место соотношение s < Ö > t = s . Cправедливы следующие свойства последовательной композиции : s4. (s;t);u = s ;(t;u) ; s5. (< Ö > ; s) = s ; s6. (s;t)0 = s0 , s0 ¹Ö ; Упражнения к разделу . Доказать свойства s4 -s6 . 2.5.1.6. Переименование . Пусть f - функция , отображающая один алфавит в другой . Если s - след , построенный из символов , входящих в область определения функции f , то определим функцию f * (s) как след , получающийся из следа s путем применения функции f к каждому из его символов . Формально : f1. f * (<>) = <> ; f2. f * (c-> s) = f(c) -> f * (s) . Аналогично , если B - множество символов из области определения Функции f , то f * (B) = df { f* (B) | bÎ B } . Условимся , что : f3. f* (c) = Ö - c=Ö . Пример. Пусть f(a)=x , f(b)=y , f(c)=z , f* (Ö ) = Ö , тогда : f * ( < a , b ,c > = < x,y,z > , f * ( { a , b ,c } ) = { x,y,z } Cправедливы следующие свойства операции переименования : f4. f * (st) = f * ( s ) f * ( t ) ; f5. f * (s / t) = f * ( s ) / f * ( t ) ; f6. f * (s é B) = f * ( s ) é f * ( B ) ; f7. f * (s; t) = f * ( s ) ; f * ( t ) Упражнения к разделу . Доказать свойства f4 -f7 . 2.5.2. Теория процессов. Процесс с заданным алфавитом определяется множеством следов , символы которых принадлежат этому алфавиту . Каждый след описывает возможную последовательность событий , в которых процесс может участвовать в определенный момент времени . Формально процесс P - это любое множество следов в алфавите A , для которого выполняются следующие аксиомы : P0. PÍ A * ; P1. <> Î P ; P2. st Î P => s Î P ; Каждый процесс будет определяться парой (A,P) , где A- алфавит процесса , а P - множество следов в алфавите A . Выделим следующие процессы - примитивы : FAILA = df ( A , { <> } ) - пустой процесс в алфавите A , который никогда " ничего не делает " ; (A , A * )- универсальный процесс в алфавите A , который " все делает". В дальнейшем для удобства процесс P будем рассматривать просто как множество следов , выделяя его алфавит лишь в тех случаях , когда это необходимо , обозначая через aP алфавит процесса P . Примеры процессов в алфавите { a, b } : { <> } , { <>,< b > } , { <>,< a >,< a, b > } , { <>,< a >,< a, b > ,< b > , < b, a > } . Для процессов-примитивов справедливы следующие ниже свойства . P3. FAILA является процессом в алфавите A . P4. A * является процессом в алфавите A . P5. aP= A => FAILA Í P . Доказательство свойств P3 , P4 . Для доказательства свойств достаточно показать выполнение аксиом P0 - P2 . Доказательство (P3) : P0 . { <> } Í A * ( согласно аксиоме Ax1 ) ; P1. <> Î { <> } ( согласно теории множеств ) ; P2. ( st Î { <> } ) = > (st = <>) => (s=<>) => ( s Î { <> } ) ( согласно c6 ) . Доказательство (P4) : P0 . A * Í A * ( очевидно ) ; P1. <> Î A * ( согласно аксиоме Ax1 ) ; P2. ( st Î A * ) = > ( s Î A * ) ( согласно c7 ) . 2.5.2.1 . Операция присоединения символа . Если P - процесс , а cÎ aP , то (c->P) определяется как процесс , который начинается с события c , а затем выполняется как процесс P . Формально это определяется так : (c->P) = df {<>} È { (c -> s) | cÎ aP & sÎ P } . Справедливо следующее утверждение. Pr1. Если P -процесс , а cÎ aP , то (c->P) является процессом в алфавите aP . Для доказательства Pr1 достаточно показать выполнение аксиом P0 - P2 аналогично доказательству свойств P3 , P4 . 2.5.2.2 . Альтернативная операция . Если P и Q -процессы , то операция P | Q определяется как P или Q . Формально эта операция определяется следующим образом : P | Q= df P È Q , где a (P | Q ) = aP È aQ . Cправедливы следующие свойства : U1. если P и Q -процессы , то P | Q также является процессом ; U2. операция P | Q коммутативна и ассоциативна ; U3. P | (aP) * = (aP) * ; U4. P | FAIL = P . Примеры. А) ( a->(b-> FAIL)) | ( b-> FAIL ) ={ <>,< a > ,< a,b > , < b > } . Б) Оператор if b then P else Q можно представить в виде (b->P)| (ù b->Q) , где ù b рассматривается как событие отрицания b . B) Операцию (a->P | b-> Q) можно интерпретировать как меню-диалог, где { a,b } - меню из двух элементов a,b ,где выбор элемента a активизирует процесс P , выбор элемента b активизирует процесс Q . Упражнения к разделу . Доказать свойства U1 -U4 . 2.5.2.3. Начальное состояние процесса . Если P - процесс , то определим P0 как множество символов ,опреде-ляющих стартовое состояние процесса : P0 = df { c | < c > Î P } Cправедливы следующие свойства : O1. ( FAIL ) 0 = { } ; O2. (A * )0 = A ; O3. ( c-> P ) 0 = { c } ; O4. ( P |Q ) 0 = P0 È Q0 Пример. (( a-> P) | ( b-> Q )) 0 = ( a-> P) 0 È ( b-> Q ) 0 . Упражнения к разделу . Доказать свойства O1 -O4 . 2.5.2.4. Операция "после". Если s - след процесса P , определим P/s (P после s) как множество следов , определяющее поведение процесса P после следа s : P/s = df { t | st Î P } . Cправедливы следующие свойства : A1. если P - процесс и sÎ P , то P/s - процесс ; A2. P/<> = P ; A3. stÎ P => P/(st) = ( P/s )( P/t ) ; A4. s Î A * => A * /s = A * ; A5. s Î P => (c-> P ) / (c-> s ) = P/s ; A6. c Î P0 - Q0 => ( P | Q ) / ( c-> s ) = (P/< c >) / s ; A7. c Î P0 Ç Q0 => ( P | Q ) / ( c-> s ) = ( (P/< c >) |(Q/< c >) )/ s ; A8. s Î P - ( s=<> )Ú ( s0 Î P0 & s' Î P/< s0 > ) . Замечание . Свойство A8 означает , что если известно P0 и для любого c Î P0 определен процесс P/< c> , то процесс определен полностью . Отсюда следует , что можно ввести другой способ определения процесса , который предусматривает определение процесса парой ( I , F ),где множество I -начальное состояние процесса , а функция F отображает каждый элемент c Î I в процесс P/< c > (по аналогии с определением автомата - функция переходов ) . Отсюда , в дополнение к теоретико-множественному способу определения , вводится так называемое процедурное определение процесса . Процедурное определение процесса является более адекватным с точки зрения реализации процесса в отличие от теоретико - - множественного определения . С другой стороны для исследования свойств процессов более удобным является теоретико- множественная модель , представляющая достаточ-но эффективную математическую базу для формулировки и доказа-тельства свойств процессов . Существуют также и другие модели представления процессов в теории CSP , которые не рассматриваются в рамках данного пособия . Примеры процедурного определения. А) Для процесса R = ( c-> P ) : R0 = { c } & R /< c > = P . Б) Для процесса R = ( a-> P ) | ( b-> Q ) : R0 = { a, b } & ì P , если x=a R /< x > = í î Q , если x=b . B) Для процесса R = P | Q : R0 = P0 È Q0 & ì P , если x Î P0 - Q0 R /< x > = í Q , если x Î Q0 - P0 î P/<x> | Q/<x> , если x Î P0 Ç Q0 . Упражнения к разделу . Доказать свойства A1 -A8 . 2.5.2.5. Последовательная композиция . Если P и Q -процессы , то последовательная композиция (P; Q) выполняется как процесс P до успешного завершения P , затем выполняется как процесс Q . Если процесс P не завершается успешно , то переход на выполнение процесса Q не может быть осуществлен . Признаком успешного завершения процесса (следа ) является событие успешного завершения , обозначаемое символомÖ . Формально последовательная композиция определяется следуюшим образом : (P; Q) = df { s; t | sÎ P & tÎ Q } . Определим процесс SKIP = df { <> , < Ö > } , который понадобится нам в дальнейших рассуждениях . Также , как процесс FAIL , процесс SKIP " ничего не делает ", но в отличие от процесса FAIL завершается всегда успешно . Cправедливы следующие свойства : S1. SKIP , (P; Q) являются процессами ; S2 (P;Q ) ; R = P;(Q;R) ( свойство ассоциативности ) ; S3. FAIL ; P = FAIL ; S4. SKIP ; P = P;SKIP = P ; S5. (c-> P ) ; Q =c-> (P ; Q) , если с ¹ Ö ; S6. ( P | Q ) ; R = ( P ; R ) | ( Q ; R ) ; S7. ( P ; Q ) 0 = P 0 , если Ö Ï P 0 ; S7'. ( P ; Q ) 0 = ( P 0 - { < Ö > } ) È Q 0 , если Ö Î P0 ; Примеры . А) if b then P = (b->P) | (ù b -> SKIP ) ; Б) (b->P) | (ù b -> SKIP ); Q = ( b-> ( P;Q )) | (ù b -> Q ) Упражнения к разделу . Доказать свойства S1 -S7' . 2.5.2.6. Параллельная композиция. Пусть P - процесс в алфавите A , а Q - процесс в алфавите B . Тогда через PA || B Q обозначается операция параллельной композиции процессов P и Q в алфавите (A È B) . Каждое событие , принадлежащее пересечению алфавитов (A Ç B) и соответственно являющееся общим событием , определяет точку взаимодействия параллельно выполняемых процессов P и Q . Событие из множества A-B предполагает участие только процесса P , а событие из множества B-A предполагает участие только процесса Q . Отсюда следует , что любой след процесса PA || B Q после удаления из него событий из множества B-A превращается в след процесса P , а после удаления из него событий из A-B превращается в след процесса Q . Приведенные выше рассуждения обосновывает следующее определение параллелизма : PA || B Q = df { s | sÎ (AÈ B) * & s é A Î P & s é A Î Q } Cправедливы следующие свойства : C1. Операция || коммутативна и ассоциативна ; C2. P ||P = P ; _____ C3. (P ||P) 0 = majority( A Ç B , P0 , Q0 ) , где majority( X , Y , Z ) =( XÇ Y ) È ( YÇ Z ) È ( ZÇ X ) ; C4. sÎ P || Q => ( P || Q )/s = ( P/( s éaP) ) || ( Q/( s éaQ) ; Пусть aÎ A-B , bÎ B-A , c,c0,c1Î A Ç B , c0 ¹c1 . Тогда : C5. ( c->P ) || ( c->Q ) = c -> (P || Q) ; C6. ( c0-> P) || ( c1-> Q )= FAIL ; C7. ( a-> P ) || ( c->Q ) = a-> ( P || ( c->Q )) ; C7'. ( c-> P ) || ( b->Q ) = b-> ( (c->P) || Q ) ; C8. ( a->P ) || ( b->Q ) = ( a-> ( P || ( b->Q ))) | ( b-> (( a-> P) ||Q )) 2.5.2.7. Взаимодействие параллельных процессов. Пусть P и Q - параллельно выполняемые процессы . Если aP Ç aQ = Æ , то это означает , что процессы P и Q не взаимодействуют друг с другом. Однако этот случай не представляет особого интереса в исследовании свойств параллельных процессов , поскольку с точки зрения математической модели при отсутствии взаимодействия безразлично , параллельно выполняются процессы или выполняются последовательно друг за другом. Поэтому будем рассматривать случай , когда aP Ç aQ ¹ Æ . Взаимодействие параллельно выполняемых процессов осуществляется путем обмена сообщениями , то есть один из процессов передает сообщение , а другой принимает его. Для передачи данных от одного процесса к другому в теории CSP используются каналы передачи данных . Вводятся две операции : c ! m -операция передачи сообщения m через канал c , c ? x -операция приема сообщения из канала с в переменную x . В теории CSP рассматривается случай синхронного взаимодействия процессов , который предусматривает одновременное выполнение операций c ! m и c ? x . Таким образом одновременное выполнение этих операций позволяет трактовать его как единое неделимое событие взаимодействия процессов . Последнее определяется следующим соотношением : ( c!m-> P ) || ( c?x-> F(x) ) = c-> ( P || F(m) ) . Упражнения к разделу 2.5.2 . Определить следующие процессы : 1) abstar - процесс , принимающий любое количество букв a , после которого следует любое количество букв b ; 2) anbn - процесс , принимающий любое количество букв a , после которого следует точно такое же количество букв b ; 3) сопрограмма cor( P, Q ) - процесс , поведение которого определяется следующей схемой : P --- off --- off -- ¬ ¬¯ ­ ¬¯ ¯ ­ ¯ Q-------on ------ , где { on , off } Ç ( aP È a Q ) = Æ , a cor( P, Q ) = { on , off } È ( aP È a Q ) ; выполнение сопрограммы начинается с процесса P , который выполняется до активизации события off , после которого запускается процесс Q , который в свою очередь отрабатывает до активизации события on , после которого продолжает выполняться процесс P , и т.п. ) ; 4) stoppable(P) - процесс , который выполняется как P до активизации события stop , после которого процесс stoppable(P) завершает успешно свою работу ; stopÏ aP , a stoppable(P) = aP È { stop } ; 5) resetable(P) - процесс , который выполняется как P до активизации события reset , после которого resetable(P) стартует с начала ; resetÏ aP , a resetable (P) = aP È { reset } . 6) backtrackable(P) - процесс , который выполняется как P до активизации события back , после которого backtrackable (P) стартует с начала ; backÏ aP , a backtrackable (P) = aP È { back } . Пример процедурного определения процесса (stoppable(P) ). stoppable(P) 0 = P0 È { stop } & ì SKIP , если x = stop stoppable(P)/<x> = í î stoppable( P/<x> ) , если x ¹ stop (x) ( xÎ P0 ) . 2.5.3. Язык параллельного программирования OCCAM. OCCAM - язык высокого уровня, предназначенный для выполнения параллельного программирования и создания транспьютеров . Является результатом совместной разработки корпорации INMOS и Оксфордского университета . Концепция OCCAM базируется на теории взаимодействующих процессов, Свое название получил в честь английского философа XIV в. Уильяма Оккама, поскольку в основе разработки языка был использован провозглашенный им принцип: «Сущность не должна превышать необходимость» («бритва Оккама»). В соответствии с упомянутым принципом из двух одинаково эффективных вариантов решений принимается наиболее простое. Язык OCCAM используется в транспьютерах первых и всех последующих выпусков. Полное описание языка OCCAM можно найти в книге [9] . Здесь же ограничимся рассмотрением ряда примеров , с помощью которых проиллюстрируем основные особенности программирования на языке OCCAM . Взаимодействие параллельно выполняемых процессов осуществляется путем обмена сообщениями . Для передачи данных от одного процесса к другому используются каналы передачи данных и следующие операторы : channel ? variable - ввод сообщения из канала channel в переменную variable , channel ! expression - вывод значения выражения expression в канал channel . Рассмотрим следующий пример . Пусть требуется ввести из канала chan1 некоторое числовое значение в переменную x , затем вывести в канал chan2 результат возведения этого же числа в квадрат . Схематически это это можно представить так : chan1 -> |x x*x | -> chan2 . Соответствующая программа на языке OCCAM выглядит следующим образом : VAR x: SEQ chan1 ? x chan2 ! x*x Здесь оператор SEQ P Q определяет последовательную композицию конструкций P и Q ( P;Q ) . Теперь потребуем , чтобы этот процесс выполнялся в цикле пока x>0 . В этом случае мы имеем : VAR x: WHILE x>0 SEQ chan1 ? x chan2 ! x*x Рассмотрим теперь следующую конструкцию : PAR VAR x: WHILE x>0 SEQ chan1 ? x chan2 ! x*x VAR y: WHILE y>0 SEQ chan3 ? y chan4 ! y*y Здесь оператор PAR P Q определяет параллельную композицию конструкций P и Q ( P ||Q ) . В этом случае мы имеем два независимых параллельных процесса : chan1 -> |x x* x | -> chan2 chan3 -> |y y* y | -> chan4 Теперь преобразуем приведенную выше следующим образом : chan1 -> |x x * x | comms -------------------> |y y * y | -> chan2 Программа , адекватная приведенной выше схеме , будет иметь вид : CHAN comms PAR VAR x: WHILE x>0 SEQ chan1 ? x comms ! x*x VAR y: WHILE y>0 SEQ comms ?y chan2 ! y*y Данная программная конструкция определяет два взаимодействующих параллельных процесса с результатом вычисления x4 , который выводится в канал chan2 . Взаимодействие параллельных процессов осуществляется через общий канал comms . Содержательная сущность представленного выше параллельного выполнения процессов сводится к тому , что вычисление y2 = ( x2 ) 2 может выполняться одновременно с вычислением квадрата последующего введенного значения переменной x . Приведенную выше программу можно написать короче , если определим следующую процедуру : PROC square (CHAN source, sink) = VAR x: WHILE x>0 SEQ source ? x sink ! x*x Таким образом , на основе определенной выше процедуры , перепишем программу следующим образом : CHAN comms PAR square (chan1 , comms) square (comms , chan2) Приведем другой пример , иллюстрирующий операцию альтернативной композиции процессов . В качестве примера рассмотрим программу моделирования работы цифрового радиоприемника , точнее часть программы , управляющей громкостью звучания. Для управления звуком мы имеем две клавиши louder и softer , нажимая которые мы либо увеличиваем громкость звучания (louder) , либо уменьшаем (softer) .При программировании будем представлять эти клавиши в виде каналов. Кроме каналов louder и softer введем канал amplifier , который будет определять усилитель. Наконец , введем переменную volume , целочисленное значение которой будет определять громкость звучания . Передача значения переменной volume на усилитель amplifier будет выполняться оператором amplifier ! volume . Таким образом процесс SEQ volume:=volume +1 amplifier ! volume моделирует увеличение громкости , а процесс SEQ volume:=volume -1 amplifier ! volume моделирует уменьшение громкости . Далее , нажатие клавиши louder будет активизировать выполнение оператора louder ? ANY , а нажатие клавиши softer будет активизировать выполнение оператора softer ? ANY. Значение переменной ANY здесь не играет никакой роли , для нас является важным только сам факт выполнения события ввода ( louder ? ANY или softer ? ANY ) . Таким образом мы получаем следующую альтернативную операцию : (louder ? ANY -> LPROC) | (softer ? ANY ->SPROC ) , где процесс LPROC моделирует увеличение громкости , а процесс SPROC моделирует уменьшение громкости . То есть при выполнении события louder ? ANY запускается процесс LPROC , а при выполнении события softer ? ANY запускается процесс SPROC . На языке OCCAM имеем : ALT louder ? ANY LPROC softer ? ANY SPROC На основе вышеперечисленного представим следующую программу на языке OCCAM : VAR volume: SEQ volume:=0 WHILE true ALT louder ? ANY SEQ volume:=volume +1 amplifier ! volume softer ? ANY SEQ volume:=volume -1 amplifier ! volume Конструкция WHILE true определяет " бесконечный цикл " до выключения цифрового радиоприемника . В приведенной выше программе не определены верхняя и нижняя границы громкости звучания . Для учета этих границ программу можно переписать следующим образом : DEF max=10, min=2 VAR volume: SEQ volume:=0 WHILE true ALT ( volume<max ) & ( louder ? ANY ) SEQ volume:=volume +1 amplifier ! volume ( volume>min ) & (softer ? ANY) SEQ volume:=volume -1 amplifier ! volume В настоящее время используется достаточно большое количество языков параллельного программирования . Это - диалекты и расширения известных языков ( например CC++ , C/C+ , PARSEC и т.д.) , а также языки , специально созданные для параллельных вычислений ( ADA , Concurrent Clean ,MODULA 3 и другие) . Язык OCCAM отличается от всех этих перечисленных языков своей оригинальностью , простотой и , наконец , тем , что он явно базируется на специально созданной для целей параллельного программирования теории . 2.6. Объектно-ориентированное программирование. 2.6.1.Основные определения и принципы. При объектно-ориентированном подходе в качестве основного строительного блока в процессе программирования выступает объект , принадлежащий определенному классу ( являющийся экземпляром определенного класса ) . Идея объектно-ориентированного подхода появилась при проведении исследований в области языков программирования , а впервые была реализована при создании языка моделирования SIMULA , в котором впервые появилось и было использовано в программировании понятие класса объектов. Дальнейшее развитие объектно-ориентированного подхода , вызвавшее достаточно широкий интерес к этому способу программирования , связывают с появлением языка SMALLTALK . Следует отметить важную особенность большинства объектно-ориентированных систем программирования , которые , наряду с объектно - ориентированными средствами , предоставляют программистам возможность процедурно- ориентированного программирования , позволяя гибко сочетать разные подходы в процессе разработки программ. Здесь мы ограничимся рассмотрением только основных принципов объектно- ориентированного программирования . Более полное и детальное описание объектно- - ориентированного подхода можно найти в книге [ 3 ] . Определим ряд основополагающих понятий объектно-ориентированного подхода к проектированию и реализации программного обеспечения . Объектно-ориентированное проектирование - это методология проектирования , основанная на объектной декомпозиции и приемах представления логической , физической ,статической и динамической моделей проектируемого программного обеспечения . При процедурно - - ориентированном походе проектирование основывается на алгоритмической ( процедурной ) декомпозиции , которая предусматривает представление некоторого программного модуля P в виде P = W ( P1 ,P2 ,…,Pn ) , где W - функция , реализуемая в соответствующей среде программирования , а P1 ,P2 ,…,Pn - модули , из которых строится модуль P . Объектная декомпозиция предполагает , что в качестве элементов P , P1 ,P2 ,…,Pn вместо программных модулей фигурируют объекты . Объектно-ориентированное программирование - это методология программирования , основанная на представлении программ в виде совокупности объектов , каждый из которых является экземпляром определенного класса с наследованием свойств этого класса. Поскольку во многих современных объектно-ориентированных системах программирования каждый класс может представляться в качестве экземпляра более абстрактного класса , то в этих случаях классы образуют иерархию наследования . Содержательно класс можно рассматривать как некий абстрактный объект , наделяемый свойствами , характерными для некоторого множества объектов . В последнее время появилось достаточно много различных объектно-ориентированных систем про-граммирования , среди которых нибольшую популярность приобрели C++ , DELPHI , JAVA , UML . Особое место отводится объектно-ориентированным системам управления базами данных ( СУБД ) . В отличие от других систем программирования , СУБД представляют эффективные средства для обработки больших информационных структур . По мнению многих разработчиков программного обеспечения именно появление и дальнейшая модификация СУБД спровоцировало широкое внедрение объектно - - ориентированного подхода . Примерами объектно-ориентированных СУБД , получивших широкое распространение , являются CACHE , VisualFoxpro , MS SQL , JASMINE , ORACLE . С другой стороны многие современные системы программирования (например такие , как C++ ) , изначально не рассматриваемые в качестве СУБД , снабжа-ются в настоящее время дополнительными средствами обработки баз данных . Методы - это процедуры и функции , реализующие операции над классами и объектами в объектно-ориентированном программировании . Основными принципами объектно - ориентированного программирования являются наследование , инкапсуляция и полиморфизм . Принцип наследования заключается в передаче свойств от класса к экземпляру этого класса , который может представлять либо просто объект или в свою очередь класс. Таким образом наследование тесно связано с иерархией классов , определяющей родительские и дочерние классы ( объекты ) . Если некоторый класс обладает некоторым фиксированным набором свойств , то экземпляр этого класса содержит тот же набор свойств и , возможно , дополнительные новые свойства , характерные для соответствующего экземпляра. Ниже следует пример иерархической вложенности классов : класс "Компьютер" -> класс "Персональный компьютер"-> класс " Персональный компьютер типа Pentium 4" -> объект " конкретный персональный компьютер типа Pentium 4 №51175-028-9713636-11440 " Инкапсуляция - это сокрытие деталей реализации классов и объектов. Можно также рассматривать инкапсуляцию как процесс отделения интерфейса от методов реализации . Если вернуться к примеру с классом "Компьютер" , то можно проиллюстрировать инкапсуляцию следующим образом .Основным субъектом , взаимодействующим с этим классом , является пользователь , которому нет необходимости в совершенстве знать внутреннее устройство компьютера . Этот принцип позволяет эффективно модифицировать объектно-ориентированные программы , . Полиморфизм представляет свойство , позволяющее по разному интер-претировать выполняемые одноименные методы в зависимости от того , какому из классов относится тот или иной метод . Например , операция "выключить" по разному выполняется по отношению к таким различным объектам , как электрический свет , компьютер и автомобиль. К другим принципам , которые , как правило , присущи большинству современных объектно-ориентированных систем относятся следующие . Событийно-управляемое программирование основывается на множестве событий E={ e1 , e2 , … en } и множестве методов (процедур или функций ) P={ p1 , p2 , … pn }, запускаемых при активизации соответствующих событий . Более детально это можно выразить следующими соотношениями : e1 -> p1 , e2 -> p2 , … , en -> pn , где активизация события ei предусматривает запуск метода pi ( i=1..n ) . Примерами событий могут быть возникновение какой либо ошибки в процессе выполнении программ , выполнение определенного запланированного условия , выбор элемента меню , активизация командной кнопки , нажатие функциональной клавиши и т.п. . Для описания модели событийно-управляемого программирования идеально подходит теория CSP , представленная в разделе 2.6 . Параллелизм предусматривает одновременную активизацию двух или более событий с параллельным запуском соответствующих методов . Сохранение целостности базы данных является более характерным для объектно-ориентированных СУБД и предусматривает наличие механизма , обеспечивающего целостность . Понятие целостности данных обычно трактуется как наличие специальных выделенных соотношений , являющихся инвариантными по отношению к любым допустимым преобразованиям базы данных . Если эта инвариантность нарушается , то говорят о нарушении целостности данных . Визуальное программирование основано на визуальном представлении объектов программирования , обеспечивая наиболее естественное компъютерное отображение реальной среды . Использование визуальной формы представления данных может помочь пользователю охватить , проанализировать и понять огромные информационные массивы , а также эффективно управлять ими . Реализация объектно-ориентированных систем программирования , по сравнению с процедурно-ориентированными , является более сложной задачей , так как требуется создание так называемой интегрированной среды разработки , представляющей библиотеку сервисных программ для автоматизации процессов разработки , моделирования , программирования и отладки . Переход от традиционного процедурного стиля программирования к объектно -ориентированному , который успешно преодолели многие программисты ведущих индустриальных государств , представляет принципиально новый шаг в направлении концептуального программирования , сопоставимый по своей важности с переходом от машинно -ориентированного программирования к языкам высокого уровня . За время своего развития этот современный стиль программирования обогатился средствами обработки баз данных и визуального представления обрабатываемой информации . Существенное продвижение по пути к стандартизации , повышение производительности труда программистов ,возможность одновременного проектирования , разработки и реализации приложений - все это далеко не полный перечень преимуществ , предоставляемых объектно -ориентированными системами . 2.6.2. Visual FoxPro - пример объектно-ориентированной СУБД. Visual FoxPro [ 7 ] представляет собой принципиально новую версию широко известной СУБД Microsoft FoxPro,которая может функционировать практически во всех версиях операционной системы WINDOWS . Visual FoxPro обеспечивает совместимость с предыдущими версиями процедурно-ориентированной СУБД FoxPro, позволяя сравнительно просто переносить ранее созданные приложения в среду WINDOWS. Эта СУБД разработана в полном соответствии со стандартами фирмы Microsoft, что позволяет сравнительно легко обмениваться данными с другими приложениями WINDOWS. Кроме этого поддерживается доступ к наиболее популярным SQL-серверам баз данных - Microsoft SQL Server, ORACLE, INFORMIX и к другим , используя стандарт ODBC. В настоящее время широко используются последние версии Visual FoxPro (6.0 , 7.0 , 8.0 ) . В отличие от предыдущих версий система Visual FoxPro предлагает новый подход к программированию , известный как событийно - - управляемое программирование, суть которого сводится к определению некоторого множества событий (Click-нажатие левой кнопки мышки , Load- момент загрузки объекта и т .п.), каждое из которых может быть связано с соответствующим программным модулем (методом), запускаемым при активизации соответствующего события . Основные принципы событийно -управляемого программирования наиболее полно реализуются при использовании объектно - -ориентированной среды , когда элемент на экране, с которым манипулирует пользователь, имеет связь с объектом ,созданным программистом . Событийно - управляемая программа достаточно хорошо приспособлена к изменению внешней ситуации и позволяет программисту сравнительно просто добавлять новые средства обработки событий . Визуальные средства представления объектов , заложенные в Visual FoxPro , обеспечивают естественность зрительного восприятия объектов и позволяют существенно повысить эффективность процессов проектирования , разработки , тестирования и отладки приложений .Другой важной особенностью объектно - ориентированной среды является возможность одновременного проектирования , разработки и реализации приложений , обеспечиваемая за счет соединения информационных , логических и алгоритмических связей в единое целое в рамках определяемого объекта обработки ,успешно избегая многих ошибок , возникающих при нарушении принципов адекватности между проектом и его реализацией . Более того , этот принцип позволяет успешно описывать постановку задачи на программирование средствами объектно-ориентированной СУБД . Создание разветвленной и достаточно объемной интегрированной среды , обеспечивающей объектно - ориентированные , визуальные и событийно - управляемые средства программирования , безусловно является дорогим “удовольствием ”, за которое приходится расплачиваться большим расходом памяти , замедлением времени работы приложений и , наконец , громоздкостью системы в смысле ее освоения . Последнее является наиболее уязвимым объектом критики сторонников традиционного процедурно - ориентированного программирования . Однако , необходимо иметь в виду , что грамотное использование всех перечисленных выше возможностей , позволяет существенным образом повысить производительность разработки программ и создавать в итоге высококачественный программный продукт , удовлетворяющий соответствующим стандартам . Об этом свидетельствует богатый опыт разработки многих приложений объектно-ориентированных СУБД .С другой стороны переход от процедурно - -ориентированной модели мышления к объектно - ориентированной - - процесс достаточно долговременный и болезненный . Поскольку объектно-ориентированные системы , как правило , содержат в качестве собственного подмножества процедурно - ориентированную среду , многие программисты часто при переходе от процедурного способа программирования к объектно -ориентированному продолжают по инерции программировать по старому , не используя преимуществ объектно - ориентированной среды . Процесс проектирования и разработки приложений в среде СУБД Visual FoxPro начинается с создания проекта (Project), являющегося главным составляющим разрабатываемого приложения . Механизм развертывания последующих этапов разработки проекта определяется следующей структурой : PROJECT ( проект ) DATA ( базы данных ) DOCUMENTS ( документы ) FORMS ( экранные формы ) REPORTS ( формы вывода на печать ) CLASSES ( классы ) CODE ( программы и приложения ) PROGRAMS ( программы ) APPLICATIONS ( приложения ) OTHER ( другие объекты ) MENU ( меню ) TEXT FILES ( текстовые файлы ) База данных определяется структурой : DATA DCB-файлы ( контейнеры данных ) DBF - файлы (), входящие в состав соответствующих контейнеров FREE TABLES ( свободные таблицы : DBF-файлы, не входящие в состав ни одного из контейнеров ) В отличие от предыдущих версий в СУБД Visual FoxPro введено понятие контейнера данных (базы данных ), представляемого в виде структурированного DCB - файла, который включает в себя множество таблиц (DBF -файлов ) , связываемых друг с другом структурно - -логическими отношениями вида "один к одному" , "один к многим" и "много к многим". Таблицы , входящие в состав контейнера данных, называются связанными.Все остальные таблицы являются свободными . В СУБД Visual FoxPro встроен эффективный механизма защиты целостности баз данных , позволяющего автоматически контролировать и предотвращать нарушения структурных связей в базах данных при выполнении операций над базами данных . Этот механизм основывается на средствах , позволяющих устанавливать структурно - логические отношения между таблицами базы данных и определять специальные функции проверки (триггеры) для разрешения или запрета операций удаления , вставки и модификации записей таблиц в зависимости от определяемых условий . Документы включают в себя экранные формы ( FORMS ) и формы для вывода на печать (REPORTS).Создание каждого нового документа предусматривает как правило установление связи документа с соответствующими базами данных (DATA ENVIRONMENT) и заполнение документа различными объектами на основе встроенной или определяемой библиотеки классов объектов. Для каждого из объектов устанавливаются свойства (Properties), определяющие различные характеристики объекта (связи с полями таблиц , способ размещения на экране , и т .п.).Кроме этого с каждым объектом можно связать некоторое множество событий и запланировать вызов соответствующих подпрограмм (методов), запускаемых автоматически при возникновении тех или иных запланированных событий .Такая возможность позволяет реализовать принцип событийно-управляемого программирования (Event-Driven Programming), обеспечивающего существенное повышение эффективности технологии производства программ . Класс объектов представляет из себя некий абстрактный объект , обобщающий свойства соответствующих однотипных объектов и позволяющий эффективно определять новый объект ( экземляр класса ), наследующий свойства класса .Предоставляя в распоряжение программиста библиотеку встроенных классов , Visual FoxPro позволяет вводить новые классы и создавать новые библиотеки классов . Программы и приложения (CODE).В Visual FoxPro предоставлена возможность гибкого сочетания объектно - ориентированного стиля программирования с процедурно - ориентированными средствами , предусматривающая создание программных и процедурных файлов (PRG - файлов ) на языке FoxPro. Причем один из этих файлов выбирается в качестве главного ("запускающего") модуля , активизирующего соответствующие объекты , каждый из которых в свою очередь активизирует другие и т .п. .В результате компиляции проекта имеется возможность получения как EXE -файла, так и специального APP - файла , представляющего из себя промежуточный результат компиляции и выполняемого интерпретатором Visual FoxPro. Такие APP - - файлы , называемые приложениями , являются более компактными по сравнению с соответствующими EXE - файлами , однако могут выполняться только при наличии среды Visual FoxPro. Другие объекты (OTHER) включают меню , текстовые и другие файлы , необходимые для разработки программ . Visual FoxPro представляет эффективные средства средства генерации меню - диалога . Область применения СУБД Visual FoxPro охватывает достаточно широкий класс задач, однако наиболее очевидный эффект достигается для информационно -расчетных задач , характерной особенностью которых является сочетание обработки больших информационных массивов с вычислительными задачами . Это - бухгалтерский учет , анализ финансово -хозяйственной деятельности предприятий , информационно - поисковые системы , системы автоматизации делопроизводства и т .п. Для эффективной разработки и создания качественного программного продукта , ориентированного на решение перечисленных задач , очень важное значение имеет концептуальный подход к разработкам . Это - - достаточно емкое понятие , предусматривающее в первую очередь строгую математическую формализацию модели разработки , с помощью которой можно было бы наиболее просто и компактно описать и в дальнейшем эффективно реализовать сложные структурные связи между объектами и алгоритмами их обработки , четко отделяя второстепенные моменты от главных . Например , разработка компьютерной бухгалтерии предусматривает создание комплекса подсистем : расчет заработной платы , касса , банк , материально складской учет , учет основных средств , работа с подотчетными лицами , поставщики -получатели и т .п. Каждая из подсистем должна включать в себя средства для получения огромного числа различных отчетных документов с учетом различных бухгалтерских операций и специфики бухгалтерской отчетности для разных типов организаций . Кроме этого необходимо обеспечить возможности обмена данными между этими подсистемами и экспорта результатов работы подсистем в автоматизированное рабочее место главного бухгалтера с целью получения конечных бухгалтерских документов (баланс , главная книга и т .п.). Все это представляет из себя достаточно сложную и трудоемкую задачу ,“лобовое” решение которой как правило не приносит ожидаемых результатов . С другой стороны концептуальный анализ этой проблемы показывает , что основная часть перечисленных подсистем имеет одну и ту же общую основу , сводящуюся к расчету остатков на текущий период из оборотов и остатков предыдущего периода .Следовательно, разработку необходимо начинать с создания средств расчета остатков ,которые в последующем могут существенно облегчить задачу разработки и реализации упомянутых подсистем . Другим важным аспектом разработки бухгалтерской системы является создание единых справочников , представляющих из себя источники первичной информации для всех соответствующих подсистем (план счетов , справочник финансовых операций с бухгалтерскими проводками , справочник источников финансирования , справочник подразделений предприятия и т .п.), правильная организация которых обеспечивает универсальность и хорошую адаптируемость системы к изменениям . Объектно - ориентированные средства , позволяя абстрагирование (обобщения) объектов разработки приложений с последующей их конкретизацией , представляют наиболее адекватный инструмент для создания различных информационно - расчетных приложений и удачно “провоцируют” разработчиков этих приложений на выбор концептуальных решений . 3.Теория и методы трансляции. Трансляция - это процесс перевода текста исходной программы в эквивалентную объектную программу. Программное обеспечение , реализующее этот процесс называется транслятором . Если в результате трансляции генерируется объектная программа на ассемблере или некотором машинном языке, то вместо трансляции используется понятие компиляции , а сам транслятор называется компилятором. Языки интерпретируемого типа предусматривают получение в результате трансляции так называемого промежуточного кода ( традиционно - это линеаризованная структура со ссылками на программные модули) , выполнение которого осуществляется специальной программой , называемой интерпретатором. Для языков интерпретируемого типа происходит частичная компиляция , завершаемая генерацией промежуточного кода , который затем интерпретируется . Чаще всего интерпретатором называется программное обеспечение , реализующее весь этот процесс целиком , то есть частичная компиляция с генерацией промежуточного кода плюс интерпретация промежуточного кода . Поскольку и в том и другом случае выполняется процесс компиляции ( в случае интерпретации неполный ) , в последующем изложении материала будем в основном использовать термины "компиляция" и "компилятор" вместо "трансляция" и "транслятор" соответственно . Большинство теоретических работ и методов для практической реализации компиляторов появилось в 1970-х , а некоторые из них еще раньше. Первые разработки в этой области предусматривали создание нового компилятора для каждого нового появляющегося языка программирования практически с самого начала . Однако существенная трудоемкость этого процесса и стремление к универсализации стимулировали появление инстументальных программных средств для автоматизации процесса создания компиляторов . В результате появился программный инструментарий , обеспечивающий генерацию готового компилятора на основе описания синтаксиса и семантики соответствующего языка программирования . Этот инструментарий , впоследствии названный " компилятором компиляторов " , получил большое распространение в процессе создания компиляторов . К числу самых известных разработок в этом плане можно отнести генераторы лексического и синтаксичес-кого анализаторов LEX и YACC , работающих в UNIX -среде . К настоящему времени опубликовано достаточно большое количество работ , посвященных теории и практике компиляции , однако большинство из них либо содержат сложно воспринимаемый теоретический базис , либо представляют слишком прагматический материал . В этой связи рекомендуется использовать книгу [ 6 ] , которая достаточно прозрачно и компактно представляет теоретические и практические основы компиляции . Представляемый в пособии материал никоим образом не претендует на полноту охвата всех существующих методов компиляции .Вместо этого предлагается материал , позволяющий акцентировать внимание на концептуальных основах процесса компиляции и принципиального понимания соответствующих методов . 3.1. Определение языка. Определение языка программирования также , как и любого другого языка,основывается на двух главных понятиях :синтаксис и семантика. Синтаксис определяет правила для описания правильных конструкций языка , а семантика - смысловую интерпретацию этих конструкций . 3.1.1.Синтаксис . Существует множество различных способов описания синтаксиса языков программирования . Если язык состоит из конечного числа строк , то его определение может быть сделано перечислением всех его элементов . Так как все языки программирования содержат бесконечное число строк , то требуется найти способ представления бесконечного числа строк конечным образом . Рассмотрим примеры описания бесконечного числа строк символов. Пример1 . Язык который состоит из произвольного количества символа x Может быть определен в виде выражения { x n | n>0 } , где n - целое , а умножение здесь трактуется как конкатенация . Пример2 . Язык который состоит из произвольного количества символа x , после которого следует произвольное количество символов y . Этот язык определяется в виде выражения { x m y n | m,n>0 } , где m,n - целые . Пример 3. Если язык определить в виде выражения { x m y n | m,n ³ 0 } , то допустимыми являются строки вида xxx ( при n=0 ) ,уууу (при m=0) , а также пустая строка (при m=0 , n=0), которую будем обозначать <> . Пример 4 . Язык , определенный в примере 3 , можно переопределить по другому : x * y * , где символ "* " (звездочка Клини) обозначает , что предшествующий ему элемент , используется нуль или большее число раз (представление с помощью языка регулярных выражений ). Пример 5 . Выражение вида xx * yy * определяет язык , каждая строка которого содержит как минимум по одному элементу x и y . Рассмотрим формальное определение регулярных выражений , которые были использованы в перечисленных выше примерах . Вводится понятие алфавита , представляющего конечный набор символов . Например , { A..Z } , { 0..9 } , { А..Я } и т.п. . Регулярными выражениями являются : 1) пустая строка (<>) ; 2) любой элемент из алфавита . Далее , если P и Q - регулярные выражения , то регулярными являются выражения : 3) PQ (Q следует за P ) ; 4) P | Q (P или Q) ; 5) P * ( нуль или большее число вхождений P) . Несмотря на компактность и удобство регулярных выражений , далеко не все языки можно определить с помощью регулярных выражений . Существует более универсальный и мощный аппарат описания языка с помощью грамматик . Грамматика определяется в виде четверки объектов (AT , AN ,P,S ), где AT - алфавит терминальных символов , AN - алфавит нетерминальных символов , P - множество продукций ( или правил вывода ) вида a -> b , где a - левая часть , а b - правая часть продукции , S - начальный символ ( аксиома или символ предложения ) грамматики , являющийся элементом множества AN ( SÎ AN ) . При этом имеют место следующие соотношения : AT Ç AN = Æ ,a Î A* , b Î A* , A = AT È AN ( A* определяет строки , состоящие из нуль или более повторений символов из A ) . Особенностью начального символа S является то , что с него начинается генерация любой строки языка . Грамматика используется для генерации строк символов языка начиная с аксиомы грамматики , последовательно применяя правила подстановки ( продукции ) и заменяя нетерминал последователь- ностью символов правой части соответствующей продукции . Процесс завершается получением строки , не содержащей нетерминальных символов . Язык содержит только те строки символов , которые можно сгенерировать с помощью заданной грамматики . В дальнейшем для обозначения терминальных символов будем использовать строчные буквы , или , в некоторых случаях слова , состоящие только из строчных букв ( x , y , if , then , else и т.п.). Для обозначения нетерминальных символов будем использовать заглавные буквы ( X ,Y, S и т.п.) . Аксиому грамматики будем обозначать буквой S . Греческие буквы будут использованы для обозначения строк символов . Рассмотрим примеры различных грамматик. Пример 6 . Грамматикой для языка { x n y n | n>0 } , строки которого состоят из одного или более символов x , после чего следует такое же количество символов y , является G1 = ( { x , y }, { S }, P , S ) , где множество продукций P определяется как : S -> xSy , S -> xy . Пример7 . Грамматикой для языка { x m y n |m, n³ 0 } , строки которого состоят из нулевого числа или более символов x , после чего следует нулевое число или более символов y , является G2 = ( { x , y }, { S , B }, P , S ) , где множество продукций P определяется как : S -> xS S -> yB S -> x S -> y S -> <> B -> yB B -> y . Например , строка xxyyy может быть сгенерирована грамматикой G2 с помощью серии подстановок S=> xS => xxS => xxyB => xxyyB => xxyyy , называемой порождением . Каждая из строк , входящая в порождение , называется сентенциальной формой , а последняя сентенциальная форма , состоящая только из терминальных символов , называется предложением языка . Выражение вида a => b , где a , b - сентенциаль-ные формы означает , что строка b получена из строки a посредством одного порождения . Выражение вида a =* > b означает , что строка b порождается из строки a за нуль или более шагов . Выражение вида a =+ > b означает , что строка b порождается из строки a за один или более шагов . Условимся в дальнейшем обозначать порождения вида B -> yB , B -> y как B -> yB | y . Для классификации грамматик и языков было введено понятие иерархии Хомского . Хомский определил четыре класса грамматик , которые были названы грамматиками 0-го , 1-го , 2-го и 3-го типов . К 0-му типу относятся все грамматики без ограничений на типы продукции . Грамматики 0-го типа называют еще рекурсивно- - перечислимыми грамматиками . Грамматики , все продукции которых ограничены соотношением | a | £ | b | ( то есть длина строки a , исчисляемая количеством входящих символов , не может быть больше длины строки b ) , называ-ются грамматиками 1-го типа , или по другому контекстно- - зависимыми . Если контекстно-зависимую грамматику ограничить условием , которое предусматривает наличие в левой части каждой продукции только одного единственного нетерминального символа , то мы получаем грамматику 1-го типа , или по другому контекстно-свободную грамматику . Для определения 3-го типа грамматик , или так называемых регулярных грамматик , введем сначала ряд вспомогательных определений. Грамматика называется праволинейной , если каждая ее продукция имеет вид A-> a либо A-> bC . Соответственно грамматика называется леволинейной , если каждая ее продукция имеет вид A-> a либо A-> Cb . Грамматика называется регулярной ( грамматикой 3-го типа ), если она является только праволинейной или только левоволинейной . Замечание . В контекстно-свободных грамматиках разрешим использование продукций вида a -> <> , где a -нетерминальный символ ( хотя строго говоря эта продукция не разрешена даже в контекстно- -зависимых грамматиках ). Это необходимо для включения в соответствующий язык пустой строки в целях более удобного описания синтаксиса языков программирования . Классификация Хомского является иерархической в том смысле , что все грамматики 3-го типа являются грамматиками 2-го , все грамматики 2-го типа являются грамматиками 1-го , а все грамматики 1-го типа - - грамматиками 0-го типа . Соответственно , мы можем определить иерархию языков основываясь на порождающих их грамматиках , то есть языки 3-го типа , языки 2-го типа и т.п. . Однако необходимо иметь в виду , что существуют языки , например 3-го типа , которые определяются грамматикой 2-го типа , и в то же время существует эквивалентная грамматика 3-го типа для порождения этого языка (в этом случае она обязательно должна существовать , поскольку речь идет о языке 3-го типа) . Например язык вида { x m y n |m, n³ 0 } (этот пример уже рассматривался выше) . Этот язык можно сгенерировать следующими продукциями : S->XY X->xX X-> <> Y->yY Y-> <> Очевидно , что грамматика с перечисленными выше продукциями не является грамматикой 3-го типа . Однако этот же язык можно определить следующими ниже продукциями 3-го типа . S -> xS S -> yB S -> x S -> y B -> yB B -> y S -> <> В разработке компиляторов широко используются контекстно- -свободные и регулярные грамматики . Регулярные грамматики , являющиеся подмножествами контекстно-свободных , являются более простыми. Поэтому всюду , где это возможно имеет смысл использовать в процессе компиляции регулярные грамматики и языки. В связи с этим возникает необходимость в выявлении способа определения , является ли генерируемый язык регулярным. Такой способ существует и сводится к достаточно простому свойству грамматики , позволяющего определить , является ли генерируемый язык регулярным . Для рассмотрения этого свойства предварительно введем понятие рекурсии в грамматике . Рассмотрим следующие продукции : A -> Ab B -> cB C -> dCf . Это - примеры так называемой прямой рекурсии , при которой нетерминальный символ из левой части продукции входит и в правую часть . В первом случае имеем левую рекурсию ( нетерминал слева ), во втором - правую рекурсию (нетерминал справа) , в третьем - среднюю рекурсию ( нетерминал располагается и не слева и не справа ).Следует отметить , что кроме прямой рекурсии существует еще понятие косвенной ( непрямой ) рекурсии . Например : A -> Bc , B -> Cd , C -> Ae . Поскольку существует простой алгоритм преобразования косвенной рекурсии в прямую (этот алгоритм мы здесь не рассматриваем) , далее мы не будем рассматривать косвенную рекурсию . Теперь мы можем сформулировать важное утверждение , на основе которого можно будет определить , является ли генерируемый язык регулярным : если грамматика не содержит средней рекурсии , то генерируемый этой грамматикой язык является регулярным . Доказательства этого утверждения мы здесь не приводим . Введем несколько полезных определений , которые будут использо-ваны в дальнейшем. Левое порождение определяется как порождение , на каждом шаге которого заменяется крайний левый нетерминал сентенциальной формы. Правое порождение определяется как порождение , на каждом шаге которого заменяется крайний правый нетерминал сентенциальной формы. Рассмотрим в качестве примера язык вида { x m y n |m, n > 0 } , определяемый следующими продукциями : S -> XY X -> xX X -> x Y - >yY Y -> y Строка xxxyy может быть сгенерирована одним из двух порождений : 1) S => XY => xXY => xxXY => xxxY => xxxyY => xxxyy 2) S => XY => XyY => Xyy => xXyy => xxX yy => xxxyy . Первое порождение является левым , а второе - правым . Порождение можно выразить по другому - через синтаксическое дерево ( дерево синтаксического разбора ) . Например порождение S =>XY=>xXY=>xXyY=>xxXyY=>xxXyy=>xxxyy можно выразить следующим синтаксическим деревом : S X Y x X y Y x X y x Рис. 3.1.1-1. Пример синтаксического дерева. Грамматика называется однозначной , если каждое сгенерированное этой грамматикой предложение имеет единственное синтаксическое дерево . В противном случае грамматика называется неоднозначной. Многие компиляторы создаются на основе однозначных грамматик , однако при разработке компиляторов в ряде случаев возникают неоднозначные грамматики , для которых однако чаще всего находятся методы устранения неоднозначности . Неоднозначные языки , для которых не существует однозначной грамматики , обычно не используются в языках программирования . 3.1.2.Семантика . Семантика определяет смысловую интерпретацию конструкций языка. Методы описания семантики как правило принадлежат к одному из перечисленных ниже классов . Денотационная семантика основывается на функциональных вычислениях , определяющих операции в языке в виде отображений в однозначные математические понятия , которые затем используются для описания результата вычислений через входные и выходные данные . Аксиоматическая семантика основывается на исчислении предикатов ,где результат вычислений описывается через взаимоотношения между значениями переменных до и после применения определенных операций . Операционная семантика предусматривает описание операций в языке через деятельность некой абстрактной машины , выполняющей вычисления . 3.2. Основные этапы компиляции. Процесс компиляции обычно принято делить на три основных этапа : предварительная обработка , анализ и синтез . Предварительная обработка предусматривает выполнение так называемых операций периода компиляции , которые включают в себя развертывание макросов , присоединение исходных файлов , удаление комментариев и т.п. . Данный этап представляется достаточно простым и поэтому в дальнейшем мы не будем его рассматривать,ограничившись лишь его кратким объяснением . Этап анализа включает в себя три фазы . 1) Лексический анализ ; 2) Синтаксический анализ ; 3) Семантический анализ . Лексический анализ выполняет формирование символов языка . Ключевые слова языка , идентификаторы , константы и другие элементы языка , представляющие объекты обработки лексического анализа , преобразуются в неделимые символы языка , которые в дальнейшем используются на фазах синтаксического и семантического анализов. Кроме этого лексический анализатор осуществляет обработку пробелов , удаление комментариев и некоторые другие действия , необходимые для подготовки текста программы к последующим фазам . При формировании символов языка лексический анализатор не учитывает их последовательность , то есть как правило не работает с контекстом . Например , если в программе на языке PASCAL появится некорректная конструкция вида if b while P вместо if b then P , лексический анализатор не обнаружит никакой ошибки . Синтаксический анализ строит древовидное представление текста программы , которое называется синтаксическим деревом . В процессе построения анализируется корректность структуры программы . В отличие от лексического анализа , синтаксический анализатор полностью работает с контекстом . Например при анализе упомянутой выше некорректной конструкции синтаксический анализатор обнаружит ошибку . Семантический анализ ориентирован на проверку тех свойств текста исходной программы , которые не могут быть проверены синтаксическим анализатором простым сканированием слева направо. Например , проверка корректного использования типов данных в операциях , функциях и операторах ( проверка совместимости типов ) , для которой необходимо предварительно построить таблицу переменных . Этап синтеза состоит из следующих фаз . 1) Генерация машинно-независимого кода ; 2) Оптимизация машинно-независимого кода ; 3) Распределение памяти ; 4) Генерация машинного кода ; 6) Оптимизация машинного кода . Если компиляция осуществляется непосредственно в машинный код , то первые две фазы отсутствуют . Однако часто в компиляторах используется машинно-независимый код , поскольку в этом случае обеспечивается относительная независимость компилятора от конкретного класса компьютеров и входного языка . Оптимизация кода позволяет получить эффективный код , обеспечивающий оптимальное сочетание двух важных свойств объектного кода : максимально возможная скорость выполнения и минимально возможный объем используемой памяти . Распределение памяти обеспечивает резервирование памяти для переменных , констант и других объектов языка . Результатом работы этого этапа является создание адреса , содержащего полную информацию о структуре распределения памяти . Этап анализа достаточно хорошо автоматизируется с точки зрения создания компилятора компиляторов (наиболее удачными примерами такой автоматизации являются уже упомянутые выше генераторы лексического и синтаксического анализаторов LEX и YACC ) . Автоматизация этапа синтеза представляется существенно более сложной задачей , поэтому средства инструментальной поддержки этого этапа не получили широкого распространения . Кроме рассмотренных выше понятий для компиляторов важным является количество проходов компиляции. Большинство современных компиляторов обеспечивает полный процесс компиляции при однократ-ном чтении кода ( однопроходные компиляторы ) . Ранние компиляторы были многопроходными в основном по причине малых размеров памяти компьютеров того времени . Для современных компиляторов , как правило , такой проблемы не существует , однако имется ряд языков программирования , специфика которых в принципе не позволяет одного прохода (например ALGOL 68). Важной составляющей инструментальных средств реализации современных систем программирования является интегрированная среда разработки ( IDE - Integrated Development Envirinment ) , обеспечивающая автоматизацию процессов разработки , программирования , отладки и компиляции . Понятие интегрированной среды разработки возникло с появлением объектно-ориентированного программирования . 3.3. Лексический анализ. Лексический анализ выполняет формирование символов языка на основе так называемых лексем , к числу которых принадлежат следующие элементы языка. 1) Ключевые слова языка ( if , then , else , while ,do , var , integer и т.п) . 2) Идентификаторы ( custom, x1 ,y1 , name и т.п) 3) Константы ( 14 , 13.06 , 'abc' и т.п. ) . 4) Последовательности знаков (<= , <> ,>=, и т.п . ) . 7) Знаки пунктуации ( { } [ ] … , ; и т.п ) . Лексемы преобразуются в неделимые символы языка , которые в дальнейшем используются на фазах синтаксического и семантического анализов. Кроме этого лексический анализатор осуществляет обработку пробелов , удаление комментариев и некоторые другие действия , необходимые для подготовки текста программы к последу-ющим фазам . При формировании символов языка лексический анализатор не учитывает их последовательность , то есть как правило не работает с контекстом . Например , если в программе на языке PASCAL появится некорректная конструкция вида if b while P вместо if b then P , лексический анализатор не обнаружит никакой ошибки . Для фазы лексического анализа наиболее удобным средством описания символов являются регулярные выражения . Например , идентификатор можно представить в виде буква(буква | цифра)* . Несмотря на относительную простоту процесса лексического анализа, существует ряд языковых особенностей , усложняющих реализацию лексических анализаторов. В основном это - следующие особенности : - ключевые слова разрешено использовать в качестве идентификаторов ; - интерпретация некоторых последовательностей лексем носит контекстно-зависимый характер . Например в языке FORTRAN можно использовать конструкцию вида IF(K) =1 , которую можно интерпретировать как присвоение значения K-ому элементу массива с именем IF . Однако распознавание именно такой интерпретации может быть выполнено только по достижению конца строки , поскольку может появиться конструкция IF(K) 1,2,3 , интерпретируемая как оператор IF . Другим неудобством языка FORTRAN с точки зрения лексического анализа является воможность использования внутренних пробелов при обозначении идентификаторов. Конструкция DO 7 K=1,5 определяет оператор цикла . В то же время , пока не считан символ запятой , начало строки можно спутать с идентификатором DO 7 K . Для устранения подобных неоднозначностей используют предваритель-ный просмотр текста и приведение к некоторому каноническому виду , который уже лексическим анализатором воспринимается однозначным образом . 3.4. Синтаксический анализ. 3.4.1. Цель синтаксического анализа. Первоочередной задачей синтаксического анализа является нахождение порождения (если оно существует) конкретного предложения языка с использованием данной грамматики. В большинстве случаев искомыми являются единственные левые или единственные правые порождения . В случае неоднозначных грамматик порождение не является единственным и поэтому в этом случае требуется наличие правил устранения неоднозначностей . Если анализируемое предложение не принадлежит языку , компилятор не должен прекращать свою работу , ограничившись сообщением об ошибке. В этом случае , как правило , компилятор сообщает об ошибке и указывает на последний символ , после которого возникла ошибка . Затем после соответствующей локализации ошибки процесс анализа продолжается .Далее строится синтаксическое дерево , вершина которого соответствует символу предложения , соединяемого с анализируемым предложением через поддеревья , соответствующие продукциям грамматики . Существует несколько подходов к построению синтаксического дерева. Нисходящий синтаксический анализ (top-down parsing) предусматривает построение синтаксического дерева , начиная с вершины (символа предложения ) с развертыванием дерева в направлении предложения языка . Восходящий синтаксический анализ (bottom-up parsing) предусматривает построение синтаксического дерева , начиная с предложения языка, сворачивая его до получения символа предложения . Нисходящий синтаксический анализ обладает большей степенью наглядности , чем восходящий . Однако на практике большее распространение получил восходящий синтаксический анализ , обладающий большей общностью и более совершенным аппаратом инструментальной поддержки . В ряде компиляторов сочетаются оба эти подхода . 3.4.2. Нисходящий синтаксический анализ . Задача нисходящего анализа , как правило , сводится к нахождению левого порождения . Процесс нисходящего анализа начинается с символа предложения с последующей генерацией предложения языка . Рассмотрим в качестве примера язык вида { x m y n |m, n > 0 } , определяемый следующими продукциями : S -> XY X -> xX X -> x Y - >yY Y -> y Предложение xxxyy можно сгенерировать с помощью следующего левого порождения : S => XY => xXY => xxXY => xxxY => xxxyY => xxxyy . Алгоритм нахождения левого порождения можно наглядно проиллюстрировать с помощью приводимой ниже таблицы . _________________________________________________________ Входная строка Продукция Сентенциальная форма _________________________________________________________ xxxyy S => XY XY xxxyy X => xX xXY x xxyy X => xX xxXY xx xyy X => x xxxY xxx yy X => x xxxY xxxy y Y => yY xxxyY xxxyy Y => yY xxxyY _________________________________________________________ Таблица 3.4.2 -1 . Алгоритм нахождения левого порождения . В этой таблице знаки предложения рассматриваются по одному и используются для управленият процессом синтаксического анализа. После генерации знак предложения подчеркивается во входной строке. Каждому этапу синтаксического анализа соответствуют три позиции таблицы : входная строка с подчеркнутыми символами , текущая продукция , а также текущее состояние сентенциальной формы . В конце синтаксического анализа все знаки входной строки подчеркнуты , а сентенциальная форма полностью совпадает с заданной строкой . На каждом этапе первый неподчеркнутый символ определяется как входной символ и используется для разбора . Если в сентенциальной форме генерируется терминал , появляется еще один подчеркнутый символ. Принятие решений при нисходящем синтаксическом разборе обычно основывается на символе или последовательности символов предосмотра . Под символом предосмотра здесь имеется в виду либо текущий входной символ либо символ , обозначающий признак конца строки . Существуют грамматики , поддерживающие методы нисходящего синтаксического анализа с одним символом предосмотра . Это -так - называемые LL(1) -грамматики . Термин LL(1) означает следующее :первая буква L определяет направление чтения слева ( Left ) направо,вторая буква L определяет использование левых ( Leftmost) порождений, цифра 1- один символ предосмотра . Соответственно LL(1) - язык определяется как язык , генерируемый посредством LL(1) -грамматики .В данном пособии этот класс грамматик и языков подробно не рассматривается . Наиболее удачное и полное изложение материала по LL(1)- грамматикам и языкам можно найти в книге [ 6 ] . 3.4.3. Восходящий синтаксический анализ . Задача восходящего анализа , как правило , сводится к нахождению правого порождения . Рассмотрим в качестве примера рассмотренный в предыдущих разделах язык { x m y n |m, n > 0 } , определяемый следующими продукциями : S -> XY X -> xX X -> x Y - >yY Y -> y Предложение xxxyy можно сгенерировать с помощью следующего правого порождения : S => XY => XyY => Xyy => xXyy => xxX yy => xxxyy . В отличие от нисходящего , при восходящем синтаксическом анализе этапы порождения определяются в противоположном порядке , то есть : xxxyy=> xxX yy=> xXyy=> Xyy=> XyY=> XY=> S . Применение продукции грамматики на каждом этапе предусматривает замену правой части продукции ее левой частью , состоящей из одного символа. При восходящем синтаксическом анализе правые части продукции не распознаются до тех пор , пока не будут полностью считаны . В связи с этим требуется хранение частично распознанных правых частей про-дукций до замены их соответствующими левыми частями. Для этой цели используется стек. Таким образом основные этапы процесса восходящего синтаксического анализа выражаются с помощью двух типов действий . 1) Занесение последнего считанного символа в стек - действие переноса (SA-shift action) . 2) Замена строки наверху стека посредством применения продукции грамматики - действие свертки (RA - reduce action) . Алгоритм восходящего синтаксического анализа иллюстрируется на приводимой ниже таблице . _____________________________________________________________ Входная строка Стек Продукция Сентенциальная форма SA | RA _____________________________________________________________ xxxyy xxxyy x xxyy x xxxyy SA xx xyy xx xxxyy SA xxx yy xxx xxxyy SA xxx yy xxX X -> x xxXyy RA xxx yy xX X -> xX xXyy RA xxx yy X X -> xX Xyy RA xxxy y Xy Xyy SA xxxyy Xyy Xyy SA xxxyy XyY Y -> y XyY RA xxxyy XY Y -> yY XY RA xxxyy S S -> XY S RA ______________________________________________________________ Таблица 3.4.3 -1 . Алгоритм восходящего синтаксического анализа . Вершина стека расположена справа , а в последнем столбце показан применяемый тип операций (SA | RA) . Действие переноса выполняет удаление символа и занесение его в стек . Действие свертки преду-сматривает изменения в вершине стека и в сентенциальной форме посредством применения продукции . В начальном состоянии синтаксического разбора стек пустой , а сентенциальная форма совпадает с анализируемым предложением ( xxxyy ) . В финальном состоянии сентенциальная форма совпадает с начальным символом грамматики ( S ) , стек содержит также начальный символ грамматики , строка полностью прочитана . В приведенной выше таблице явно указывается в какой момент производится одна из операций (SA | RA) , однако из этой таблицы однозначным образом не следует критерий выбора той или иной операции . Очевидно , что необходимым условием применения операции свертки является наличие правой части некоторой продукции на вершине стэка . Однако это условие не является достаточным для применения применения операции свертки . Например , на первых этапах синтаксического разбора , иллюстрируемого на таблице 3.4.3 -1 , в стеке появляется элемент x , совпадающий с правой частью продукции X -> x , однако перехода к операции свертки и соответствующей замены x на X не происходит . Кроме того , вершина стека может содержать например правые части более чем одной продукции и соот-ветственно возникает проблема выбора между разными операциями свертки . Говорят , что имеет место конфликт вида перенос /свертка ( shift/reduce conflict ) , если в оказывается возможным в одно и то же время применение операции переноса и операции свертки . Если возникает проблема выбора между разными операциями свертки , этот случай определяется как конфликт вида свертка /свертка (reduce /reduce conflict ). Для разрешения этих конфликтов применяются различные стратегии , основывающиеся на использовании информации о предшествующих этапах синтаксического анализа , а также информа-ции , полученной путем предосмотра . В приведенной выше таблице символом предосмотра , определяющим применение продукции X -> x , является символ y . Для применения продукции Y -> y в качестве символа предосмотра фигурирует символ обозначающий конец строки . Грамматика , в которой все конфликты при восходящем синтаксическом анализе слева направо могут быть разрешены с использованием фиксированного объема информации , касающейся уже проведенного анализа , и конечного числасимволов предосмотра , называется LR(k) - грамматикой . Здесь буква L означает чтение слева ( Left ) направо, R - правые порождения ( Rightmost ) , k обозначает число символов предосмотра . Соответственно , LR(k) - языком называется язык , который можно сгенерировать LR(k) - грамматикой . Одним из способов решения упомянутых выше конфликтов является использование таблицы синтаксического анализа , в которой может содержаться критерий принятия решения по операциям свертки и переноса. Для иллюстрации этого способа рассмотрим пример грамматики со следующими продукциями : 1) E -> E+T , 2) E -> T , 3)T -> T * F ,4)T -> F , 5) F -> ( E ) , 6) F ->x . В качестве примера синтаксического разбора используем предложение x+x+x*x . Пример анализа иллюстрируется на приводимой ниже таблице . _____________________________________________________________ Входная строка Стек Продукция Сентенциальная форма SA | RA _____________________________________________________________ x+x+x*x x+x+x*x x +x+x*x x x+x+x*x SA x +x+x*x F F -> x F+x+x*x RA x +x+x*x T T -> F T+x+x*x RA x +x+x*x E E ->T E+x+x*x RA x+ x+x*x E+ E+x+x*x SA x+x +x*x E+x E+x+x*x SA x+x +x*x E+F F- > x E+F+x*x RA x+x +x*x E+T T-> F E+T+x*x RA x+x +x*x E E -> E+T E+x*x RA x+x+ x*x E+ E+x*x SA x+x+x *x E+x E+x*x SA x+x+x *x E+F F- > x E+F*x RA x+x+x *x E+T T -> F E+T*x RA x+x+x* x E+T* E+T*x SA x+x+x*x E+T*x E+T*x SA x+x+x*x E+T*F F -> x E+T*F RA x+x+x*x E+T T -> T * F E+T RA x+x+x*x E E -> E+T E RA _____________________________________________________________ Таблица 3.4.3 -2 . Пример восходящего синтаксического анализа . _____________________________________________________________ E T F + * ( ) x ^ ______________________________________________________________ 1 S2 S5 S8 S9 S12 2 S3 3 S4 S8 S9 S12 4 R1 S6 R1 R1 5 R2 S6 R2 R2 6 S7 S9 S12 7 R3 R3 R3 R3 8 R4 R4 R4 R4 9 S10 S5 S8 S9 S12 10 S3 S11 11 R5 R5 R5 R5 12 R6 R6 R6 R6 ______________________________________________________________ Таблица 3.4.3 -3 . Пример заполнения таблицы синтаксического анализа. В таблице синтаксического анализа каждому состоянию синтаксического анализатора (число состояний всегда конечное ) соответствует одна строка , а каждому терминальному и нетерминальному символу грамматики соответствует один столбец. Символ ^ обозначает конец строки . Синтаксический анализ начинается с состояния 1 , а входным символом является первый введенный символ. Каждый шаг анализа определяется позицией таблицы , соответствующей текущему состоянию , и входным символом . Позиция таблицы определяется одним из следующих типов . 1 ) Позиция переноса Sn обеспечивает выполнение операции переноса и переход в состояние n . 2 ) Позиция свертки Rk обеспечивает выполнение операции свертки , используя продукцию k . Пустые позиции таблицы соответствуют синтаксическим ошибкам и для каждой такой позиции можно предусмотреть выдачу своего индивидуального сообщения об ошибке. На каждом этапе синтаксического анализа анализатор находится в одном из конечного числа состояний , и это состояние плюс входной символ ( либо символ предосмотра , либо символ только что свернутого нетерминала ) определяют элемент в таблице синтаксического анализа. Если предположить отсутствие ошибок , этот элемент определяет операцию переноса или свертки. В начале синтаксического анализа анализатор находится в состоянии 1 , а входной символ - это первый символ анализируемого предложения . Пусть позиция таблицы определяет операцию переноса , тогда : - символ , соответствующий столбцу , в котором находится данная позиция таблицы , заносится в стек символов ; - анализатор переходит в состояние , определяемое позицией переноса , и это состояние заносится в стек состояний ; - если входной символ является терминалом , он принимается , и входным символом становится следующий терминал предложения . Пусть позиция таблицы определяет операцию свертки , тогда : - из стека символов удаляются m -символов , а из стека состояний удаляются m состояний , где m - число символов в правой части продукции , фигурирующей в свертке ; - анализатор переходит в состояние , определяемое вершиной стека состояний ; - входной символ становится символом в левой части продукции , определенной в позиции свертки . Ниже приводится пример анализа предложения x+x+x*x на основе использования таблицы 3.4.3 -3 . На начальном этапе имеем : входная строка стек состояний стек символов сентенциальная форма x+x+x*x 1 x+x+x*x Состояние -1 , входной символ -x , значение соответствующего элемента таблицы - S12 ; выполняется переход в состояние 12 , в стек состояний заносится 12 , в стек символов заносится x : входная строка стек состояний стек символов сентенциальная форма x +x+x*x 1,12 x x+x+x*x Состояние -12 , входной символ - + , значение соответствующего элемента таблицы - R6 ; выполняется свертка согласно продукции 6 , удаляется одно состояние из стека состояний и один символ из стека символов ( так как в правой части продукции 6 имеется только один символ) ; входным символом становится F : входная строка стек состояний стек символов сентенциальная форма x +x+x*x 1 x+x+x*x Состояние -1 , входной символ - F , значение соответствующего элемента таблицы - S8 ; выполняется переход в состояние 8 , в стек состояний заносится 8 , в стек символов заносится F : входная строка стек состояний стек символов сентенциальная форма x +x+x*x 1,8 F F+x+x*x Состояние -8 , входной символ - + , значение соответствующего элемента таблицы - R4 ; выполняется свертка согласно продукции 4 , удаляется одно состояние из стека состояний и один символ из стека символов; входным символом становится T : входная строка стек состояний стек символов сентенциальная форма x +x+x*x 1 F+x+x*x Состояние -1 , входной символ - T , значение соответствующего элемента таблицы - S5 ; выполняется переход в состояние 5 , в стек состояний заносится 5 , в стек символов заносится T : входная строка стек состояний стек символов сентенциальная форма x +x+x*x 1,5 T T+x+x*x Далее выполняются аналогичные действия , основанные на приведенной таблице синтаксического анализа , которые завершаются следующим состоянием. Состояние -1 , входной символ - E , значение соответствующего элемента таблицы - S2 ; выполняется переход в состояние 2 , в стек состояний заносится 2 , в стек символов заносится E : входная строка стек состояний стек символов сентенциальная форма x+x+x*x 1,2 E E Как только в стеке символов оказывается символ E и считано все предложение , анализ успешно завершается . В данном пособии этот не рассматриваются способы создания таблицы синтаксического анализа , которые можно найти в книге [ 6 ] . 3.4.4. Префиксная и постфиксная записи выражений. Классическим способом представления выражений для анализа перед генерацией кода являются префиксная и постфиксная записи . Для пояснения рассмотрим выражение вида a+b*c+d/e-f . Такая запись выражения называется инфиксной , что означает расположение знака бинарной операции между операндами . Интерпретация и соответственно анализ такого выражения в общем случае носит неодназначный характер . Для устранения неодназначности используется приоритет операций . Анализ основывается на представлении выражения в древовидной форме следующего вида : - + f + / a * d e b c Рис. 3.4.4-1. Пример древовидного представления выражения . Каждая промежуточная вершина этого дерева помечена знаком соответствующей операции , а дуги , исходящие из данной вершины , ведут к операндам . Теперь , начиная с вершины (сверху вниз) и придерживаясь левоориентированного пути , обойдем это дерево , попутно выписывая в строку все встречающиеся символы . В результате получим выражение вида - + + a * b c / d e f , представляющее префиксную запись. Отличительная собенность префиксной записи заключается в том , что каждый знак операции предшествует своим операндам . Постфиксная запись получается "зеркальным отображением " соответствующей префиксной записи . Таким образом для указанного выше выражения постфиксная запись имеет вид f e d / c b * a + + - . Отличительной собенностью постфиксной записи является то , что каждый знак операции записывается после операндов . Постфиксная запись является очень удобной для вычисления выражений , поскольку в ней все знаки выполняемых операций располагаются в порядке убывания приоритетов. Последнее означает , что первая встретившаяся операция при просмотре выражения слева направо выполняется первой , вторая встретившаяся - второй и т.п. . Для вычисления постфиксной записи используется классический алгоритм с использованием стека . Алгоритм основывается на просмотре символов выражения слева направо и вы- полнении соответствующих действий в зависимости от назначения символа (знак операции , символ операнда или символ конца строки) . Таким образом алгоритм в процессе просмотра выражения может находиться в одном из следующих состояний . 1. Считываемый символ является операндом. В этом случае значение операнда заносится в стек . 2. Считываемый символ является знаком операции . Выполняется соответствующая операция с операндами , которые извлекаются из стека. Извлеченные из стека операнды соответственно удаляю- тся из стека и в стек заносится результат выполнения операции . 3. Считываемый символ определяет конец строки . Алгоритм завер- шает свою работу . В стеке остается единственный элемент , определяющий результат вычисления выражения . Таблица 3.4.4-1 иллюстрирует работу алгоритма на примере