Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции - Языки программирования высокого уровня. Разработка приложений с среде Visual Basic 6.0 - файл 1.doc


Лекции - Языки программирования высокого уровня. Разработка приложений с среде Visual Basic 6.0
скачать (565 kb.)

Доступные файлы (1):

1.doc565kb.17.11.2011 16:18скачать

содержание

1.doc

  1   2   3   4   5   6   7   8   9   ...   12

1Языки программирования высокого уровня

1.1Синтаксис, формальные грамматики.


Для представления алгоритмов, которые предназначены для выполнения на ЭВМ используются языки программирования (ЯП). Внешняя форма программы на ЯП устанавливается с помощью синтаксиса языка, который определяет формальный язык. Он определяется с помощью определенных грамматических правил, аналогичных алгоритму текстовых подстановок. Основой формального определения синтаксиса являются формальные грамматики Хомского.

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



Сердцевину грамматики составляет конечное множество Р правил образования, которые описывают процесс порождения цепочек языка. Правило это пара цепочек, или, точнее, элемент (, ) множества

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

Правило (, ) будем записывать в виде .

^ Определение. Грамматикой называется четверка G=(N, T, P, S), где

  • N- конечное множество нетерминальных символов или нетерминалов;

  • T -конечное множество терминальных символов или терминалов, причем NT= ;



  • P- конечное множество подмножества

  • элемент (, ) множества Р называется правилом или продукцией и записывается в виде .

  • S- выделенный символ из N, называемый начальным символом.

Пример 1. Дана грамматика G=({A, S},{0, 1},P, S), где P={S0A1, 0A00A1, Ae}.

Нетерминальными символами являются A, S, а терминальными 0, 1.

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

Определение. Выводимые цепочки грамматики G=(N, T, P, S) определяются следующим образом:

  • S- выводимая цепочка;

  • Если - выводимая цепочка, и  содержится в Р, то  - тоже выводимая цепочка

Выводимая цепочка грамматики G, не содержащая нетерминальных символов, называется терминальной цепочкой, порождаемой грамматикой G.

Язык, порождаемый грамматикой G (обозначается L(G)),- это множество терминальных цепочек, порождаемых грамматикой G.

Введем следующие обозначения.



Пусть G=(N, T, P, S)- грамматика. Определим отношение на множестве

(формула читается  непосредственно выводима из ) следующим образом: если -цепочка из и - правило из Р, то

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

Для обозначения n правил

удобно пользоваться сокращенной записью

Грамматики можно классифицировать по виду их правил.

Определение. Грамматика G=(N, T, P, S) называется

  • праволинейной, если каждое правило из Р имеет вид AxB или Ax, где A,B,N, (NT)*;

  • контекстно- свободной (бесконтекстной), если каждое правило из Р имеет вид A, где AN, (NT)*;

  • контекстно- зависимой (неукорачивающей., если каждое правило из Р имеет вид , где ≤.

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

Пример 2. Праволинейная грамматика G1=({S}, {0, 1}, {S0S|1S|e},S) порождает язык L(G1)={0,1}*.

Пример 3. Пусть G2=({E, T, F}, {a, +, *, (, )}, P, E), где Р состоит из правил

EE+T|T

TT*F|F

F(E)|a

Язык L(G2) представляет собой множество арифметических выраженгий, построенных из символов a, +, *, (, ). Грамматика G2- контекстно- свободная.

Пример 4. Пусть G3=({C, B, S}, {a, b, c}, P, S), где Р состоит из правил

SaSBC|abC

CBBC

bBbb

bCbc

cCcc

Эта грамматика порождает язык {anbncn| n≥1}.Очевидно, это контекстно- зависимая грамматика.

Для записи синтаксиса конструкций языков программирования часто используют форму Бэкуса- Наура. Она практически ничем не отличается от нотаций продукций формальных грамматик, только вместо знака  используется обозначение ::=.

Пример 5. Десятичное целое без знака.

<Десятичное целое без знака>::=<Цифра>|< Десятичное целое без знака><Цифра>

<Цифра>::=0|1|2|3|4|5|6|7|8|9

1.2Семантика.


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

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

  1. Определить виды используемых в языке программирования простых операторов, а также часто используемые методы композиции решений подзадач.

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

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

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



Рис 3.1.

Здесь S- оператор, группа операторов или программа; Р- логическое предусловие, которое должно быть истинным перед выполнением S; Q- логическое постусловие, которое должно принимать истинное значение при выходе из вычислений S. Более краткая нотация свойства , изображеного на рис 3.1. имеет вид:

{P} S {Q} (1)

Это- спецификация программы со следующим смыслом: если соотношение Р истинно перед выполнением S, то q будет истинно после выполнения S.



Определим понятие подстановки. Пусть P - логическое выражение. Нотация используется для выражения, которое получается в результате систематической подстановки выражения у вместо всех свободных вхождений переменной х в Р. Аналогично



обозначает одновременную подстановку вместо всех свободных вхождений любой переменной xi в P соответствующего выражения yi. Вхождения xi в некоторые yi не замещаются. Переменные x1…xn должны быть различными, в противном случае подстановка не определена.

Пример 1.



^ Правила вывода- это схемы рассуждений , позволяющие доказывать свойства программы. Они имеют следующий вид:



Если H1,…,Hn- истинные утверждения, то H- также истинное утверждение.

Рассмотрим правила вывода для простых операторов

Пустой оператор. Он не оказывает никакого воздействия на значения программных переменных. Для любого P имеем правило вывода

{P}{P} (5)

Оператор присваивания. Он имеет вид x:=e и устанавливает значение x равным значению выражения e. Тогда для любого P



Пример 2.

{x+y=10} z:=x+y {z=10}

{x-y>0} x:=x-y {x>0}

Рассмотрим правила вывода для более сложных конструкций- составных и условных операторов.

Составной оператор. Он образуется путем последовательной композиции операторов S1, S2,…, Sn. Представим составной оператор програмной конструкцией

Begin S1; S2;…; Sn End (7)

Правило вывода для составного оператора имеет вид:



Пример 3. Дан составной оператор

Begin z:=z+y; u:=u-1 End

Известно постусловие Q={z+u*y=x*y, u≥ 0}

Тогда согласно правилу вывода для оператора присваивания легко установить

{z+(u-1)*y=x*y, u-1≥0} u:=u-1 {z+u*y=x*y, u≥ 0}

{z+u*y=z+u+(u-1)*y=x*y, u>0} z:=z+y {z+(u-1)*y=x*y, u-1≥0}

Следовательно, для рассматриваемого составного оператора справедливо соотношение

{z+u*y=z+u+(u-1)*y=x*y, u>0} Begin z:=z+y; u:=u-1 End {z+u*y=x*y, u≥ 0}

Условный оператор. Если S1 и S2- операторы, а B- булево выраженние, то

If B then S1 else S2 (9)

есть оператор, выполняющий следующие действия: вычисляется B; если B= true, то выполняется оператор S1, в противном случае- S2 . Пусть предусловие этого оператора есть P, а постусловие- Q. Тогда если значение B есть true, то оператор S1 будет иметь постусловие Q, если справедливо соотношение

{PB} S1 {Q} (10)

Аналогично для оператора S2 должно быть справедливо соотношение

{PB} S2 {Q} (11)



Объединяя (10,11) легко получить правило вывода для условного оператора

Ряд языков программирования содержат более простую форму условного оператора

If B then S (13)

По этому оператору вначале вычисляется B. Если B истинно, то выполняется оператор S, иначе должна быть выполнена тождественная операция. Правило вывода для оператора (13) имеет вид



Пример 4.

Легко доказать, что оператор

If r<y then begin r:=r-y;q:=q+1 end

сохраняет истинным предикат q*y+r=x,r≥0 при условии y>0. В самом деле, составной оператор удовлетворяет соотношению

(q*y+r=x,0≤r<y} begin r:=r-y;q:=q+1 end { q*y+r=x,r≥0}

Тогда согласно (14)

(q*y+r=x,0≤r<y} If r<y then begin r:=r-y;q:=q+1 end { q*y+r=x,r≥0},

а это означает инвариантность предусловия.

Селективный оператор выбора. Он имеет вид

Case x of k1:S1;…; kn:Sn end (15)

Оператор Case выбирает для выполнения тот оператор- компоненту, метка которого ki совподает с текущим значением селектора x. Если такой метки не обнаружено, то действие оператора (15) не определено. Очевидно, если требуется чтобы Q должно быть справедливо независимо от того, какой оператор Si выбирается для выполнения. Это означает справедливость соотношения

{Pi (x=ki)}Si {Q}



Тогда правило вывода для оператора выбора должно иметь вид:

Рассмотрим правило вывода для операторов итераций.

Оператор цикла с предусловием. Если B- булево выражение, а S- оператор, то

While B do S (17)

Обозначает итерационное выполнение оператора S пока B истинно. Если B ложно с самого начала, то S не будет выполняться совсем. Процесс итерации заканчивается , когда В становится ложным. Определим правило вывода для этого оператора. Если Р- его предусловие, то предусловие для оператора S имеет вид PB. Для итерационного повторения выполнения оператора S в цикле его постусловие должно совпадать с P. Следовательно, оператор S должен удовлетворять соотношению

{ PB} S {B}

Оператор цикла с предусловием завершит свою работу, если справедливо

PB

Итак, получаем следующее правило выводв для оператора с предусловием



Далее будем называть Р инвариантом цикла.

Пример 5. Рассмотрим оператор цикла

While r≥y do begin r:=r-y;q:=1+q end

в предположении, что {x≥0 y>0}. Покажем, что данный цикл имеет инвариант

(x=q*y+r)0≤r

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

{x=q*y+r0≤r-y} begin r:=r-y;q:=1+q end {(x=q*y+r)0≤r}

Предусловие составного оператора имеет форму PB. Поэтому для рассматриваемого цикла справедливо согласно (17) соотношение

{(x=q*y+r)0≤r} While r≥y do begin r:=r-y;q:=1+q end {(x=q*y+r)0≤r<y}

Оператор цикла с постусловием имеет вид

Do S loop until B (18)

Где S- последовательность и B- булево выражение. Здесь S выполняется перед вычислением B. Затем, если В ложно, процесс итерационного выполнения S продолжается, в противном случае он завершается.

Предположим, доказано, что {P}S{Q} и Q BP. Тогда возможно повторное выполнение оператора S. Выход из цикла влечет за собой условие QB. Тогда правило вывода для цикла с постусловием имеет вид

Из сравнения соотношения (18) и (19) можно сделать вывод, что цикл с постусловием более сложен в использовании.



Пример 6. Пусть дан цикл с постусловием

Do z:=z+y; u:=u-1 loop until u=0.

Предположим, что x, y- переменные целого типа, которые удовлетворяют условию x>0  y>0. Пусть требуемое постусловие цикла есть {z=x*y}. Очевидно, если объединить его с условием завершения цикла u=0, то его можно переписать в виде z+u*y=x*y. Используя правила вывода для операторов присваивания и составного оператора begin z:=z+y; u:=u-1 end легко показать, что он имеет предусловие и постусловие { z+u*y=x*y}. Отсюда легко получить числитель правила вывода (19):

{ z+u*y=x*y} begin z:=z+y; u:=u-1 end { z+u*y=x*y}, { z+u*y=x*y} u>0

Отсюда и из правила вывода (19) следует, что

{ z+u*y=x*y} begin z:=z+y; u:=u-1 end {{ z+u*y=x*y} u=0}

Очевидно, полученное постусловие эквивалентно {z=x*y}. Следует обратить внимание, что неявно мы здесь воспользовались еще одной группой правил вывода- правилами консеквенции.

Правила консеквенции имеют вид



Таким образом, мы строго определили семантику основных операторов некоторого гипотетического языка программирования посредством формальных правил вывода.
  1   2   3   4   5   6   7   8   9   ...   12



Скачать файл (565 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации