Geum.ru

Технология программирования

Вид материалаДокументы

Содержание


Вопрос №11. Языки программирования. Определение. Классификация. Формальные грамматики.
Формальные языки и грамматики
Типы формальных грамматик
Подобный материал:
1   2   3   4   5   6   7   8   9   10
^

Вопрос №11. Языки программирования. Определение. Классификация. Формальные грамматики.


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

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

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

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

Персональные компьютеры IBM используют машинный язык микропроцессоров семейства 8086, т.к. их аппаратная часть основывается именно на данных микропроцессорах.

Существуют различные классификации языков программирования.

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

В группу языков низкого уровня входят машинные языки и языки символического кодирования: (Автокод, Ассемблер). Операторы этого языка – это те же машинные команды, но записанные мнемоническими кодами, а в качестве операндов используются не конкретные адреса, а символические имена. Все языки низкого уровня ориентированы на определенный тип компьютера, т. е. являются машинно-зависимыми. Машинно-ориентированные языки – это языки, наборы операторов и изобразительные средства которых существенно зависят от особенностей ЭВМ (внутреннего языка, структуры памяти и т.д.).

Следующую, существенно более многочисленную группу составляют языки программирования высокого уровня. Это Фортран, Алгол, Кобол, Паскаль, Бейсик, Си, Пролог и т.д. Эти языки машинно-независимы, т.к. они ориентированы не на систему команд той или иной ЭВМ, а на систему операндов, характерных для записи определенного класса алгоритмов. Однако программы, написанные на языках высокого уровня, занимают больше памяти и медленнее выполняются, чем программы на машинных языках.

К языкам сверхвысокого уровня можно отнести лишь Алгол-68 и APL. Повышение уровня этих языков произошло за счет введения сверхмощных операций и операторов.

Другая классификация делит языки на вычислительные и языки символьной обработки. К первому типу относят Фортран, Паскаль, Алгол, Бейсик, Си, ко второму типу - Лисп, Пролог, Снобол и др.

В современном мире можно выделить два основных направления развития языков программирования: процедурное и непроцедурное.

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

Среди процедурных языков выделяют в свою очередь структурные и операционные языки. В структурных языках одним оператором записываются целые алгоритмические структуры: ветвления, циклы и т.д. В операционных языках для этого используются несколько операций. Широко распространены следующие структурные языки: Паскаль, Си, Ада, ПЛ/1. Среди операционных известны Фортран, Бейсик, Фокал.

Непроцедрное (декларативное) программирование появилось в начале 70-х годов 20 века, но стремительное его развитие началось в 80-е годы, когда был разработан японский проект создания ЭВМ пятого поколения, целью которого явилась подготовка почвы для создания интеллектуальных машин. К непроцедурному программированию относятся функциональные и логические языки.

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

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

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

Языки описания сценариев, такие как Perl, Python, Rexx, Tcl и языки оболочек UNIX, предполагают стиль программирования, весьма отличный от характерного для языков системного уровня. Они предназначаются не для написания приложения с нуля, а для комбинирования компонентов, набор которых создается заранее при помощи других языков. Развитие и рост популярности Internet также способствовали распространению языков описания сценариев. Так, для написания сценариев широко употребляется язык Perl, а среди разработчиков Web-страниц популярен JavaScript.

^ Формальные языки и грамматики

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


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

Конечное множество символов, неделимых в данном рассмотрении, называется словарем или алфавитом, а символы, входящие в множество, - буквами алфавита.

Например, алфавит A = {a, b, c, +, !} содержит 5 букв, а алфавит B = {00, 01, 10, 11} содержит 4 буквы, каждая из которых состоит из двух символов.

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

Например, в алфавите A слово a=ab++c имеет длину l(a) = 5, а слово b=00110010 в алфавите B имеет длину l(b) = 4.

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

a $ = $ a = a

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

Формальной грамматикой Г называется следующая совокупность четырех объектов:

Г = { VТ, VA, , R },

где VT - терминальный алфавит (словарь); буквы этого алфавита называются терминальными символами; из них строятся цепочки, порождаемые грамматикой;

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

VA - нетерминальный, вспомогательный алфавит (словарь); буквы этого алфавита используются при построении цепочек; они могут входить в промежуточные цепочки, но не должны входить в результат построения;

условимся для обозначения нетерминальных символов использовать идентификаторы, состоящие из прописных букв латинского алфавита и заключенные в угловые скобки;

- начальный символ или аксиома грамматики Î VA.

R - множество правил вывода или порождающих правил вида a ® b , где a и b - цепочки, построенные из букв алфавита VТ È VA, который называют полным алфавитом (словарем) грамматики Г.

В множество правил грамматики могут также входить правила с пустой правой частью вида <Е> . Чтобы избежать неопределенности из-за отсутствия символа в правой части правила, условимся использовать символ пустой цепочки, записывая такое правило в виде <Е> $.

^ Типы формальных грамматик

В теории формальных языков выделяются 4 типа грамматик, которым соответствуют 4 типа языков. Эти грамматики выделяются путем наложения ограничений на правила грамматики.

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

r = 

может быть построено с использованием произвольных цепочек   (Vт  Va)*. Например,

 или x b x .

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

1 2 1 2,

где 1,2 - цепочки, возможно пустые, из множества (Vт  Va)*, символ <А> Va и цепочка ω (Vт  Va)*. Цепочки 1 и2 остаются неизменными при применении правила, поэтому их называют контекстом (соответственно левым и правым), а грамматику - контекстно зависимой.

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

Например, грамматика:

Г1.5:

VТ = {a, b, c, d}, VА = {, , }

R = { a ,

 ,

  ,

 b,

b b c d ,

b b a }

является контекстно-зависимой, поскольку второе и шестое правила имеют непустой левый контекст, а третье и пятое правила содержат оба контекста. Вывод в такой грамматике может иметь вид:

a a ab abb abba.

Грамматики типа 2 называют контектно-свободными и бесконтекстными грамматиками ( КС-грамматики или Б-грамматики). Правила вывода таких грамматик имеют вид:

,

где  VА и (VТ  VА)*.

Очевидно, что эти правила получаются из правил грамматики типа 1 при условии 1 = 2 = $. Поскольку контекстные условия отсутствуют, то правила КС-грамматик получаются проще, чем правила грамматик типа 1. Именно такие грамматики используются для описания языков программирования. Примером КС-грамматики может служить следующая грамматика:

Г1.6: VТ= {a, b}, VА = {},

R = {  aa,

bb,

aa,

bb}.

Эта грамматика порождает язык, который состоит из цепочек, каждая из которых в свою очередь состоит из двух частей, цепочки VТ* и зеркального отображения этой цепочки '.

L( Г1.6 ) = { ' | VТ+},

где VТ+ - это множество VТ* без пустой цепочки. С помощью правил этой грамматики может быть построена, например, следующая цепочка:

aaabbaabaabaababbaba.

Грамматики типа 3 называют автоматными грамматиками (А - грамматиками). Правила вывода в таких грамматиках имеют вид:

a или a или  a,

где a VТ, и , VА, причем грамматика может иметь только правила вида  a - правосторонние правила, либо только вида  a - левосторонние правила.

Примерами автоматных грамматик могут служить правосторонняя грамматика Г1.7 и левосторонняя грамматика Г1.8

Г1.7: VТ = {a, b}, VА = {, },

R = { a ,

a ,

b ,

b ,

 $ }.

Г1.8:

VТ= {a, b}, VА = {, },

R = {  b,

 b,

 a,

 a,

 $ }.

Эти грамматики прождают один и тот же язык. Если обозначать цепочки, состоящие из k одинаковых символов x как xk, например x4 = xxxx, то порождаемый этими грамматиками язык можно определить следующим образом:

L(Г1.8) = { anbm | n,m > 0}.

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

Например, если грамматика типа 2 содержит правило вида

<А> ® a1 a2 a3 a4,

то преобразовать ее в автоматную грамматику нельзя. Следовательно, язык, порождаемый такой грамматикой, относится к языкам типа 2. Если же схема грамматики типа 2 содержит правила вида

<А> ® a1 a2 a3 a4 ,

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

Если обозначить множество языков типа k выражением {Lтипаk}, то отношение между множеством языков различных типов можно определить с помощью следующего включения:

{ L типа3 } Ì { L типа2 }{ L типа1 }{ L типа0}.

При этом доказано, что существуют языки типа 0, не являющиеся языками типа 1, языки типа 2, не являющиеся языками типа 1, и языки типа 3, не являющиея языками типа 2.

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