А. И. Еникеев языки программирования и методы трансляции




страница1/7
Дата02.08.2016
Размер1 Mb.
  1   2   3   4   5   6   7
КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Факультет вычислительной математики и кибернетики

А.И. ЕНИКЕЕВ

ЯЗЫКИ ПРОГРАММИРОВАНИЯ И МЕТОДЫ ТРАНСЛЯЦИИ

КАЗАНЬ 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-х годов идеологи применения математических моделей

в программировании Скотт и Стрэйчи (авторы целого ряда работ по

-исчислению и денотационной семантике) , работавшие в то время

в Оксфордском университе Великобритании ,охарактеризовали в одной из своих публикаций текущее состояние разработок и исследований

по программному обеспечению следующим высказыванием.

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

являются стерильными и совершенно непригодны для анализа и исследования практических разработок в области программирования .

С другой стороны имеется большое количество прагматически -

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

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

Несмотря на то , что с тех пор прошло более 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.Простейшие приемы программирования.
В основе функционального программирования лежит определение

функции в виде так называемого выражения  - выражения . Функция F

определяется следующим образом : F(x,y.z)=df x,y,z . PF , где x,y,z -

аргументы , а PF -выражение , определяющее способ вычисления

функции F.

Замечание. Для определенности мы рассматриваем здесь функцию от

трех переменных . В общем случае функция может содержать любое

количество аргументов.

Примеры:


  1. (n-факториал)

fact(n) )=df n. IF(n=0,1,n*fact(n-1))

  1. (наибольший общий делитель)

gcd(m,n) )=df m,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 , в противном случае .



  1. В классической 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, и т.п. Однако в целях удобства изложения будем использовать привычную математическую нотацию.

  2. Основным признаком функционального стиля программирования

является рекурсивное определение функций , характеризуемое

"обращением самой к себе " . Умение "адекватно" программировать

рекурсивно определяемые алгоритмы требует хорошего представления

о специфике реализации рекурсии. В отличие от итерационного способа программирования выполнение рекурсивно определяемой программы

происходит в два этапа . На первом этапе осуществляется построение рекурсивных соотношений и частичное вычисление с задержкой

выполнения действий , которые не могут быть выполнены на данном

этапе.Задержка вычислений обусловливается тем , что в описании

рекурсивно определяемой функции всегда присутствует явное или

косвенное обращение к той же самой функции . Первый этап

завершается после выполнения так называемого условия завершения рекурсии. На втором этапе осуществляется полное завершение всех задержанных действий путем последовательного "сворачивания"

рекурсивных соотношений.Например , при реализации функции

вычисления факториала , если 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 .


  1. В отличие от многих языков программирования в функциональных

языках программирования отсутствует строгое описание типов

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

Упражнения к разделу.Запрограммировать следующие функции :


  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"))

  1. () - пустой список (или nil ) ;

  2. (F,x,y)

2.3.2.1.Операции над списками.


Над списками определены следующие операции:


  1. head(s) -первый (головной) элемент списка s (s  nil ) ;

  2. tail(s) -список , получающийся из списка s удалением первого

элемента ( tail(nil)= nil ) ;

  1. cons(,s) -список , получающийся в результате добавления

элемента  в начало списка s ;

4) true , если  - атом

atom()= 

false , в противном случае .


Из перечисленных выше определений очевидным образом следует соотношение t= cons(,s)  head(t)=  & 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 .




  1. Пусть 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 x,y. IF( x>y ,x ,y ).Теперь

функция нахождения максимального элемента списка может быть определена так :

max(s) )=df s.IF(tail(s)=nil , head(s) , max2(head(s),max(tail(s))) ) .


  1. Вычисление суммы всех элементов числового списка s .

sum(s) )=df s. IF(tail(s)=nil , head(s) ,head(s) + sum(tail(s)) ) .


  1. Удаление последнего элемента из списка s.

del(s) =df s. IF(tail(s)=nil , nil , cons(head(s),del(tail(s)) ) .


  1. Определение семантики оператора while b do P .

while(b,P) =df s. 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 ) ) ;



  1. удаление из списка первых n-элементов (если n  числа элементов

списка , результат - nil ) ;

  1. удаление из списка последних 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 ) ;



  1. apply(f,s) - применение функции с именем , получаемым в результате

вычисления выражения f , к списку аргументов , который является

результатом вычисления выражения s ;



  1. quote(s) - значением этой функции является само выражение s

(содержательно эта функция задерживает вычисление выражения s ,

которое в данном случае рассматривается как константа ) ;



  1. eval(s) - значением этой функции является результат вычисления

выражения s ( в частности , если вычисление выражения было

задержано функцией quote , функция eval позволяет отменить

задержку и вычислить значение соответствующего выражения ) ;


  1. list(s,t) - значением этой функции является список (s,t) .

При использовании средств функционального программирования

следует учитывать , что функциональные программы , в свою очередь ,

представляются в виде списков. Как уже было отмечено в р. 2.3.1 ,

функциональная программа вида F( x,y,…) , где F - имя функции ,

x,y,… -аргументы функции , представляется в виде списка (F , x,y,…) .

Поэтому в необходимых случаях функциональные программы можно

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

динамического изменения программы в процессе ее выполнения ,

является весьма привлекательным с точки зрения создания

  1   2   3   4   5   6   7


База данных защищена авторским правом ©uverenniy.ru 2016
обратиться к администрации

    Главная страница