учебники, программирование, основы, введение в,

 

НБФ-нотации

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

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

Окончательным выполнимым кодом являются приложения, реализованные как EXE-файлы, DLL-библиотеки, COM-компоненты. К интерпретируемому коду можно отнести байт-код JAVA-программ, выполняемый посредством виртуальной машины JVM.
Языки, формирующие окончательный выполнимый код, называются компилируемыми языками. К ним относятся языки С, C++, FORTRAN, Pascal. Языки, реализующие интерпретируемый код, называются интерпретируемыми языками. К таким языкам относятся язык Java, LISP, Perl, Prolog.
В большинстве случаев код, получаемый в результате процесса трансляции, формируется из нескольких программных модулей. Программным модулем называется определенным образом оформленный код на языке высокого уровня. Процесс трансляции в этом случае может выполняться как единое целое – компиляция и редактирование связей, или как два отдельных этапа – сначала компиляция объектных модулей, а затем вызов редактора связей, создающего окончательный код. Последний подход более удобен для разработки программ. Он реализован в трансляторах языков С и С++.
Объектный код, создаваемый компилятором, представляет собой область данных и область машинных команд, имеющих адреса, которые в дальнейшем "согласуются" редактором связи (иногда называемым загрузчиком). Редактор связи размещает в едином адресном пространстве все по отдельности откомпилированные объектные модули и статически подключаемые библиотеки.
Будем называть выполнимой формой программы код, получаемый в результате трансляции исходной программы.
Процесс трансляции
Программу, написанную на языке программирования высокого уровня, называют исходной программой, а каждую самостоятельную программную единицу, образующую данную программу, - программным модулем. Для преобразования исходной программы в ее выполняемую форму (выполнимый файл) транслятор выполняет некоторую последовательность действий. Эта последовательность зависит как от языка программирования, так и от конкретной реализации самого транслятора. В ходе трансляции важно не просто откомпилировать программу, а получить при этом достаточно эффективный код.
В процессе трансляции выполняется анализ исходной программы, а затем синтез выполнимой формы данной программы. В зависимости от числа просмотров исходной программы, выполняемых компилятором, трансляторы разделяются на однопроходные, двухпроходные и трансляторы, использующие более двух проходов.
К достоинствам однопроходного компилятора можно отнести высокую скорость компиляции, а к недостаткам - получение, как правило, не самого эффективного кода.
Широкое распространение получили двухпроходные компиляторы. Они позволяют при первом проходе выполнить анализ программы и построить информационные таблицы, используемые при втором проходе для формирования объектного кода.
Напредставлены основные этапы, выполняемые в процессе трансляции исходной программы.
Фаза анализа программы состоит из:

  • лексического анализа;
  • синтаксического анализа;
  • семантического анализа.

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

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

Макросом называется некоторый предварительно определенный код, который на этапе компиляции вставляется в программу во всех местах указания вызова данного макроса.
На фазе синтеза программы производится:

  • генерация кода;
  • редактирование связей.

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

http://localhost:3232/img/empty.gifФормальные грамматики

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

  • символ ::= имеет значение "определяется как" и предшествует указанию всех допустимых значений описываемой синтаксической единицы;
  • символ | имеет значение "или" и используется для перечисления альтернативных вариантов;
  • пара символов < > ограничивает имя синтаксической единицы, называемой также нетерминальным символом или синтаксической категорией.

Значения, указываемые вне скобок < >, называются терминальными символами.
НБФ-грамматика состоит из набора правил (называемых иногда металингвистическими формулами или продукциями), записываемых при помощи НБФ-нотации.
Например:
<цифра>::= 0|1|2|3|4|5|6|7|8|9
<целочисленное значение> ::=
цифра | цифра < целочисленное значение>
В данном примере символы 0, 1, 2, 3 и т.д. являются терминальными символами.
При построении грамматики, описывающей язык программирования, выделяется начальный нетерминальный символ, определяющий конструкцию "программа".
Существуют порождающие и распознающие грамматики. Порождающая грамматика генерирует множество цепочек терминальных символов из начального символа, а распознающая грамматика используется для построения по цепочке символов дерева грамматического разбора, ведущего к начальному символу.
Можно сказать, что грамматика состоит из множества терминальных и нетерминальных символов, начального нетерминального символа и набора правил. В 1959 году Ноар Хомский предложил следующую классификацию грамматик:

  • регулярные грамматики, используемые для построения лексических анализаторов;
  • контекстно-свободные грамматики, используемые для построения дерева грамматического разбора. К этому типу относятся НБФ-грамматики;
  • контекстно-зависимые грамматики, представляемые набором правил типа x->y, в которых х может быть любой цепочкой нетерминальных символов, а y – цепочкой терминальных и нетерминальных символов. Этот тип грамматик намного сложнее контекстно-свободных грамматик и не имеет столь широкого применения при моделировании языков программирования;
  • грамматики с фразовой структурой, реализуемые набором правил типа x->y, в которых х может быть любой цепочкой нетерминальных символов, а y – цепочкой терминальных и нетерминальных символов (при этом нет никаких ограничений на длину получаемых цепочек символов). Большинство таких грамматик являются неразрешимыми и не имеют практического интереса.

Расширенная НБФ-нотация
При описании правил НБФ-грамматики с применением стандартной НБФ-нотации синтаксические конструкции, имеющие необязательные или альтернативные элементы, выглядят при всей их простоте достаточно громоздко. Расширенная НБФ-нотация вводит ряд дополнительных элементов, позволяющих значительно улучшить наглядность представления правил НБФ-грамматики.
Расширенная НБФ-нотация вводит следующие дополнительные элементы:

  • необязательные элементы указываются заключенными в квадратные скобки;
  • альтернативные элементы, указываемые через символ вертикальной черты, также могут являться необязательными элементами, заключаемыми в квадратные скобки;
  • последовательность нескольких однотипных элементов обозначается заключением элемента в фигурные скобки, за которыми указывается символ звездочка ({<целое>}*).

http://localhost:3232/img/empty.gifhttp://localhost:3232/img/empty.gif

 
На главную | Содержание | < Назад....Вперёд >
С вопросами и предложениями можно обращаться по nicivas@bk.ru. 2013 г.Яндекс.Метрика