БНФ - метаязык описания синтаксиса языков программирования

По мере создания все новых и новых языков программирования в связи с проблемой программирования трансляторов появилась острая необходи­мость в формализации описания синтаксиса языка. Язык, используемый для формализации синтаксиса другого языка, называется метаязыком. В насто­ящее время наиболее употребительным для описания синтаксиса языков программирования является метаязык форм Бэкуса?Наура (сокращенно БНФ). Идея этого метаязыка заключается в структурировании понятий исходного языка программирования и определения более сложных понятий через более простые. Для этого в языке БНФ приняты следующие соглашения.

Любое понятие Паскаля изображается своим наименованием, заключенным в угловые скобки: <...> . Предложение БНФ представляет собой одно определение некоторого понятия Паскаля через другие в форме: понятие Паскаля, после которого следует знак  “::=“, после которого записывается определение понятия. В составе определения могут использоваться другие понятия языка программирования (в нашем случае Паскаля), символы алфавита (терминальные символы) и ключевые слова языка программирования, а также специальные символы языка БНФ, которые имеют определенный смысл. В качестве таких символов используются вертикальная черта и круглые, квадратные и фигурные скобки. Их использование подчиняется следующим правилам:

• запись <понятие1> ::= <понятие2>  <понятие3>

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

• запись <понятие1> ::= <понятие2> | <понятие3> | и т.д. означает, что первое понятие совпадает с одним из остальных понятий;
• круглые скобки используются для группировки сложных конструкций БНФ внутри простых;
• часть определения, заключенная в квадратные скобки, не обязательна;
• часть определения, заключенная в фигурные скобки, может быть повторена произвольное число раз (в том числе ни одного раза);
• вместо сложного понятия Паскаля в формы БНФ могут входить терминальные символы и ключевые слова; для того, чтобы отличать их от символов БНФ (например, скобок) условимся, что мы будем выделять символы Паскаля и ключевые слова жирным курсивом .

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

<список> ::= <элемент списка> {, <элемент списка>}

Если же список может быть пустым, то его описание будет выглядеть так:

<список> ::=  | <элемент списка> {, <элемент списка>}




Другой пример. Идентификатором является последовательность букв и цифр, начинающаяся с буквы:

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

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

<заголовок процедуры> ::=

procedure <имя процедуры> [(<параметры>)];

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

<процедура или функция>::=(<процедура>|<функция>);

Мы не будем давать полного описания синтаксиса Турбо Паскаля на языке БНФ, а приведем несколько фрагментов. Вот как описывается общая структура программы на Паскале в терминах языка БНФ:

<описание программы> ::=

    <заголовок программы>

    <блок объявлений>

    <блок процедур и функций>

    <операторная часть> .

<заголовок программы> ::=

    program

<имя программы> [ (<список параметров>) ];

<блок объявлений> ::={<раздел объявлений>; }

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

    <раздел переменных> | <раздел меток> | <раздел модулей>

<раздел констант> ::=

    const <описание константы> {; <описание константы>}

<описание константы> ::= <имя константы> [ : <тип> ] =

<выражение>

<раздел типов> ::= type <описание типа> {; <описание типа>}

<описание типа> ::= <имя типа> = <тип>

<раздел переменных> ::=



    var

<объявление переменных> {; <объявление переменных>}

<объявление переменных> ::=

    <имя переменной> {, <имя переменной> }:

<тип>

<раздел меток> ::= label <метка> {, <метка>}

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

<раздел модулей> ::= uses <имя модуля> {, <имя модуля>}

<блок процедур и функций> ::= {<описание процедуры или функции> }

<описание процедуры или функции>::=

    (<описание процедуры> | <описание функции>) ;

<описание процедуры> ::=

    <заголовок процедуры>

    <блок объявлений>

    <заголовок процедуры> ::=

procedure

<имя процедуры> [(<список формальных параметров>)];

<список формальных параметров> ::=

    <формальный параметр> { ; <формальный параметр> }

<формальный параметр> ::=

    [var] <имя параметра> {, <имя параметра> }: <имя типа>

<описание функции> ::=

    <заголовок функции>

    <блок объявлений>

    <операторная часть>

<заголовок функции> ::= function <имя функции>

    [ (<список формальных параметров>) ] : <имя типа>;

<операторная часть> ::=

    begin (  | <оператор>{; <оператор>

}) end

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

В качестве другого примера фрагмента синтаксиса Паскаля приведем описание спецификации типа:

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

    <перечислимый тип> | <диапазон> | <тип массива> | <тип записи> |

    <тип множества> | <тип файла>

<перечислимый тип> ::= ( <идентификатор> {,

<идентификатор> } )

<диапазон> ::= <значение> .. <значение>

<тип массива> ::= array [<имя типа> | <диапазон>] of  <тип>

<тип записи> ::= record  <поле записи> {; <поле записи> } end

<поле записи> ::= <имя поля> : <тип>

<тип множества> ::= set of  ( <имя типа> | <диапазон> )

<тип файла> ::= file of  <тип>


Содержание раздела






---