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

Оглавление.

 

Введение. 2

Особенности языков программирования. 4

Понятие грамматики и формальное определение. Формула  Бэкуса-Наура. 6

Общая схема  распознавателя. 9

Основные  компоненты распознавателя. 11

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

Задача разбора 16

Теоретическая справка. 17

Составление формальной грамматики. 18

Построение  конечного распознавателя. 19

Программное моделирование работы конечного  распознавателя 20

Реализация  алгоритма средствами ООП. 23

Список используемой литературы 38

 

 

 

Введение.

Язык формирует наш  способ мышления и определяет то, о  чем мы можем мыслить. Б. Л. Ворф

Прогресс компьютерных технологий определил процесс появления  новых разнообразных знаковых систем для записи алгоритмов – языков программирования. Смысл появления  такого языка – оснащенный набор  вычислительных формул дополнительной информации, превращает данный набор  в алгоритм. Язык программирования служит двум связанным между собой  целям: он дает программисту аппарат  для задания действий, которые  должны быть выполнены, и формирует  концепции, которыми пользуется программист, размышляя о том, что делать. Первой цели идеально отвечает язык, который  настолько "близок к машине", что  всеми основными машинными аспектами  можно легко и просто оперировать  достаточно очевидным для программиста образом. Второй цели идеально отвечает язык, который настолько "близок к решаемой задаче", чтобы концепции  ее решения можно было выражать прямо  и коротко. Связь между языком, на котором мы думаем программируем, и задачами и решениями, которые мы можем представлять в своем воображении, очень близка. По этой причине ограничивать свойства языка только целями исключения ошибок программиста в лучшем случае опасно. Как и в случае с естественными языками, есть огромная польза быть, по крайней мере, двуязычным. Язык предоставляет программисту набор концептуальных инструментов, если они не отвечают задаче, то их просто игнорируют. Например, серьезные ограничения концепции указателя заставляют, программиста применять вектора и целую арифметику, чтобы реализовать структуры, указатели и т.п. Хорошее проектирование и отсутствие ошибок не может гарантироваться чисто за счет языковых средств. Может показаться удивительным, но конкретный компьютер способен работать с программами, написанными на его родном машинном языке. Существует почти столько же разных машинных языков, сколько и компьютеров, но все они суть разновидности одной идей простые операции производятся со скоростью молнии на двоичных числах. Персональные компьютеры IBM используют машинный язык микропроцессоров семейства 8086, т.к. их аппаратная часть основывается именно на данных микропроцессорах. Можно писать программы непосредственно на машинном языке, хотя это и сложно. На заре компьютеризации(в начале 1950-х г.г.), машинный язык был единственным языком, большего человек к тому времени не придумал. Для спасения программистов от сурового машинного языка программирования, были созданы языки высокого уровня (т.е. немашинные языки), которые стали своеобразным связующим мостом между человеком и машинным языком компьютера. Языки высокого уровня работают через трансляционные программы, которые вводят "исходный код" (гибрид английских слов и математических выражений, который считывает машина), и в конечном итоге заставляет компьютер выполнять соответствующие команды, которые даются на машинном языке. Существует два основных вида трансляторов интерпретаторы, которые сканируют и проверяют исходный код в один шаг, и компиляторы, которые сканируют исходный код для производства текста программы на машинном языке, которая затем выполняется отдельно.

 

Особенности языков программирования.

Языки программирования занимают промежуточное место между формальными  и естественными языками. С формальными  языками их объединяют строгие синтаксические правила, на основе которых строятся предложения языка. От естественных языков в языки программирования перешли лексические единицы, представляющие основные ключевые слова (чаще это английские слова, но бывают и слова других языков). Для задания языка программирования необходимо решить три основных вопроса:

1. определить множество допустимых символов языка;

2. определить множество правильных программ языка;

3. задать смысл каждой правильной программы.

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

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

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

Любой разработчик программ, так или иначе, использует первый подход – это комментарии в программе, построение ее блок-схемы, разработка документации или любое другое описание алгоритма. Все эти способы ориентированы на человека, но универсального способа проверить, насколько описание в действительности соответствует программе, пока не существует. Для изложения программы на языке, понятном машине – в машинных командах – существуют трансляторы. Второй подход используется при отладке программы; оценку результатов выполнения программы при отладке осуществляет человек. Разработчикам компиляторов так или иначе приходится решать вопрос о смысле программ. Во-первых, компилятору для преобразования исходной программы в последовательность машинных команд необходимо иметь представление о том, какая последовательность команд должна соответствовать той или иной части программы. Обычно такие последовательности сопоставляют базовым конструкциям входного языка – используется первый подход к изложению смысла программы. Во-вторых, многие современные компиляторы позволяют выявить сомнительные с точки зрения смысла места в исходной программе – например, недостижимые операторы, неиспользуемые переменные, неопределенные результаты функций и т.п. Обычно компилятор указывает такие места в виде предупреждений, на которые разработчик может обращать или не обращать внимание. Для этого компилятор должен иметь представление о том, как программа будет выполняться, т.е. используется второй подход. Но в любом случае осмысление исходной программы закладывает в компилятор его создатель, который руководствуется неформальными методами – как правило, описанием входного языка. В теории формальных языков вопрос о смысле программ не решается. Итак, возможности трансляторов по проверке осмысленности исходной программы практически равны нулю, поэтому семантические ошибки остаются на совести авторов программ. Выше, когда шла речь о различных способах задания языков, мы выделили как наиболее реальные второй и третий способ, а именно: задание языка с помощью генераторов и распознавателей. В качестве генераторов в общем случае могут использоваться грамматики, а для более узкого класса языков – регулярные выражения. В качестве распознавателей, как правило, применяются автоматы различных типов (в зависимости от класса языка). Рассмотрим способ задания языков с помощью грамматик.

Понятие грамматики и формальное определение. Формула Бэкуса-Наура.

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

Формальное описание грамматики построено на основе системы правил, или продукций. Правило представляет собой упорядоченную пару цепочек  символов (a,b), которую обычно записывают, как a®b и читают как «a порождает b».

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

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

Формально грамматика G определяется как четверка G(VT,VN,P,S), где VT – множество терминальных символов (символы алфавита);

VN – множество нетерминальных символов (слова, понятия, конструкции языка); VTÇVN=Æ; V=VTÈVN – полный алфавит грамматики G;

P – Множество правил вида a®b, где aÎV⁺, bÎV*;

SÎVN – начальный (целевой) символ грамматики G, с которого начинается процесс порождения цепочек языка.

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

Во множестве правил грамматики может быть несколько правил, имеющих  одинаковые левые части, например: a®b₁, a®b₂, …, a®b_n. Тогда эти правила записываются в одну строку: a®b₁½b₂½…½b_n.

Рассмотренная форма записи правил грамматики называется формой Бэкуса-Наура. В ней, как правило, нетерминальные символы заключаются  в угловые скобки <>.

Пример: грамматика порождения целых десятичных чисел со знаком.

G({0,1,2,3,4,5,6,7,8,9,–,+}, {<число>,<чс>,<цифра>}, P, <число>).

P:

<число>®<чс>½+<чс>½–<чс>

<чс>®<цифра>½<чс><цифра>

<цифра>® 0½1½2½3½4½5½6½7½8½9

 

В данной грамматике множество  нетерминальных символов содержит 3 элемента (символы <число>,<чс>,<цифра>), множество терминальных символов – 12 элементов (10 цифр и два знака), множество P – 15 правил, записанных в три строки. Начальный символ грамматики – <число>.

В грамматике можно изменить названия нетерминальных символов без  какого-то изменения языка, заданного  ею. Терминальные символы изменять нельзя! Они соответствуют алфавиту задаваемого языка.

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

 

G¢({0,1,2,3,4,5,6,7,8,9,–,+}, {S,T,F}, P, S).

P:

S ® T½+T½–T

T®F½TF

F® 0½1½2½3½4½5½6½7½8½9.

 

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

В грамматиках G и G¢ явная рекурсия присутствует во второй части второго правила: <чс>®<чс><цифра>, T®TF.

Чтобы рекурсия не была бесконечной, участвующий в ней нетерминальный символ должен обязательно присутствовать в левой части другого правила, где он определяется, минуя самого себя. В грамматиках G и G¢ это достигается в первой части второго правила: <чс>®<цифра>, T®F.

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

Общая схема распознавателя.

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

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

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

 

 

Условная схема распознавателя имеет следующий вид:

Основные компоненты распознавателя:

• входная лента – линейная последовательность клеток, или ячеек, каждая из которых содержит ровно один символ входного алфавита;
• входная (считывающая) головка обозревает одну входную ячейку; на каждом шаге работы может сдвигаться на одну ячейку вправо, влево или оставаться на месте;
• устройство управления (УУ), которое координирует работу распознавателя, имеет некоторое множество состояний и конечную память;
• внешняя (рабочая) память может хранить некоторую информацию в процессе работы распознавателя и может иметь неограниченный объем.

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

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

Работа распознавателя состоит  из последовательности шагов, или тактов. То, каким должен быть этот такт, определяется текущим входным символом, состоянием УУ и символом, извлеченным из памяти. Итак,

Такт состоит из следующих  моментов:

• входная головка распознавателя сдвигается на одну ячейку вправо, влево или остается на месте;
• в память помещается некоторая информация;
• изменяется состояние УУ.

В процессе работы распознавателя происходит смена конфигураций. Конфигурация распознавателя (мгновенное описание) определяется следующими параметрами:

• состояние УУ;
• содержимое входной ленты и положение считывающей головки в ней;
• содержимое внешней памяти.

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