Математическая логика и теория алгоритмов. Стенюшкина В.А. - 97 стр.

      6 Языки и грамматики

       Для реализации алгоритмов на ЭВМ требуется составить программу на
входном языке этой машины. Обычно под входным языком понимают язык
программирования высокого уровня. Такие языки предоставляют пользователю
достаточно развитые изобразительные средства и дружественный интерфейс.
Распространёнными языками высокого уровня являются Фортран, Паскаль, Си,
Aда, и другие. Выполнение программ, записанных на языке программирования,
производится с помощью языковых процессоров – программ на машинном язы-
ке, входящем в состав по ЭВМ. Основными типами языковых процессоров яв-
ляются трансляторы и интерпретаторы. Транслятор имеет входом программу на
входном языке, а выходом – эквивалентную программу на машинном (или про-
межуточном) языке. Интерпретатор – программа, которая по мере распознава-
ния конструкций входного языка реализует их, то есть выходом интерпретатора
являются результаты действий предусмотренных исходной программой. В этом
смысле интерпретатором выходной программы транслятор служит сама ЭВМ.
(Для промежуточного языка снова используется либо транслятор, либо интерп-
ретатор). Транслятор для языка высокого уровня называется компилятором. В
основе методики проектирования компиляторов лежит синтаксически управля-
емый метод обработки языков. При этом исходная программа рассматривается
как композиция разделов описания входного языка: лексики, синтактики, сема-
нтики, прагматики /9/.
       В соответствии с общими принципами семантики (науки о знаковых си-
стемах) базой языка программирования является алфавит – множество симво-
лов, называемых буквами. Лексику языка составляет множество допустимых
элементарных цепочек символов, называемых словами, вместе с описанием
способов их представления. Слова объединяются в более сложные конструкции
– предложения. В языках программирования предложение есть оператор. Пра-
вила построения предложений составляют синтактику языка. Семантика опи-
сывает значение слов, смысл предложений и связи между ними. Прагматика
определяет соотношение между смыслом языка и разрешающими возможнос-
тями языкового процессора.

      6. 1 Нормальные формы Бэкуса

       Для описания языка программирования используется метаязык. Одним
из метасинтаксических языков для языков программирования являются так на-
зываемые нормальные формы Бэкуса (НФБ).
       В форме Бэкуса описываются объекты:
       -символы языка программирования;
       -имена конструкций языка (металингвистические переменные).
       Металингвистическая форма состоит из двух частей (левой и правой),
соединённых символом : : = (металингвистическая связка); означающем «есть
по определению». В левой части находится имя конструкции, в правой – вариа-
нты (один или несколько), реализующие конструкции. Если вариантов несколь-