Металингвистические Бэкуса-Наура формулы

Для правильного понимания языка Pascal ознакомимся с системой построения языков программирования. Для этого опишем свойства языка Pascal на метаязыке математической линг­вистики, а также частично опишем сам этот метаязык.

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

Определение 2. Грамматикой языка называется конечное множество правил, позволяющее рекурсивно породить множество всех допустимых (осмысленных) выражений (строк) языка.

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

программирования, также символизирован.

В нем приняты следующие обозначения:

<Х> означает "объект типа X",

:: = означает "является",

| означает "или".

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

Символы, рассматриваемые как неделимые, называются терминальными символами или терминалами. Терминальный означает окончательный, т.е. терминалы являются окончательными символами языка.

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

Последовательность составленная их терминалов и нетерминалов, называется метаязыковым выражением.

Например, буквы определяются следующим метаязыковым выражением:

<буква>::=a|b|c|d|e|f|g|h|I|j|k|l|m|n

|o|p|q|r|s|t|u|v|w|x|z|A|B|C|D|E

|F|G|H|I|J|K|L|M|N|0|P|Q|R|S|T|U|V|W|X|Y|Z

Этот список состоит из 52 прописных и строчных букв.

Запись в метаязыке

<арифметическая операция>:: = + | - (´ | / |

перечисляет символы арифметических операций, а запись

<логическая константа>::= true|false

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

Эти записи даны в нормальной форме Бэкуса (или Бэкуса - Наура). Формальный язык, заданный совокупностью БНФ - это множество выводимых выражений из объектов ранее определенных типов. В этой форме

имя общего объекта определяемого типа пишется слева от символа :: = в

угловых скобках, а справа от этого символа класс таких объектов либо задается списком (с разделителем |), либо именами объектов ранее определенных типов

в сочетаниях, позволяющих рекурсивно определять новые классы через старые. Дадим рекурсивное определение в форме Бэкуса объекта «идентификатор»:

<идентификатор>:: = <буква> | <идентификатор>

<буква> | < идентификатор) <цифра>

Смысл этой записи состоит в определении класса объектов, называемых

идентификаторами. Сначала утверждается, что вся­кий элемент определенного ранее класса «буква» является иден­тификатором, затем даны правила порождения, состоящие в том, что приписывание к идентификатору буквы или цифры справа снова дает идентификатор.

Пример 2.7. Пусть А есть идентификатор. Приписывая к нему справа В, получаем идентификатор АВ. Аналогично АВС, А1, АВ1 допускаются в качестве идентификаторов. То есть идентификатором может быть любая строка, начинающаяся с буквы (слева), вслед за которой идет любая последовательность букв или цифр. Определение идентификатора рекурсивно; после­довательное применение правил порождения приведет к беско­нечному множеству строк, которые могут быть идентификаторами.

Дадим определение основного символа языка:

<основной символ):= <буква>|<цифра> |<

<логическое значение>|<ограничитель>

Первые три класса справа уже были описаны.

Ограничители определяются так следующим образом:

<ограничитель>::=<операция>|<разделитель>|<описатель>

<операция>:: = <арифметическая операция>|<операция следования)

<операция следования):: =goto | if | then | else | for | to|do

<разделитель>::={}|(**)|[]()|'|:=|;|=|,|..|.|begin|end|repeat|until|while|do

<описатель>:: =integer | real|char| array|string|record|oject

Числа. Синтаксические правила не объясняют «что такое» числа - они просто являются инструкцией для формирования допустимых строк символов, называемых числами. Рекурсивно применяя правила можно поро­дить все целые числа и все десятичные дроби конечной длины.

<число>::=<число без знака> | + <число без знака> | - <число без знака>

<число без знака>::=<десятичное число> |<десятичный порядок> |

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

<целое без знака><десятичная дробь>

<десятичный порядок>:: = E<целое>

<десятичная дробь>: :=.< целое без знака>

<целое>: :=<целое без знака> | +<целое без знака> | —<целое без знака>

<целое без знака>::=<цифра> | <целое без знака> | <цифра>

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