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

(К сожалению, принятый во многих современных книгах по програм­ми­рованию уровень строгости изложения заимствован скорее из книг по кулинарии).

Язык формул Бэкуса-Наура

Каждый язык, в том числе и формальный, имеет свой понятийный аппарат (Слово, знак препинания, предложение, … - понятия (языковые конструкции), исполь­зу­е­мые для описания естественных языков).

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

Заметим, что сами эти термины представляют новый (третий) уровень абстракции в описании языка. Определим теперь язык Бэкуса-Наура.

Понятие языка - это (метаязыковое) имя определяемой языковой конст­рукции. Имя конструкции в определении языка играет роль символа, который назы­ва­ется метасимволом (нетерминальным символом).

Определяемый язык представлен в виде конечного набора метасимволов (метасловаря) языка.

Метасловарь пред­став­ляет понятийный аппарат языка программирования.

С формальной точки зрения мета­сло­варь удобно считать алфавитом нетерминальных символов (метаалфавитом)

Вместе с метаалфавитом ЯП определяется и лексический словарь ЯП – конечный набор лексем.

С формальной точки зрения лекси­чес­кий словарь также удобно считать алфавитом терминальных символов.

Лексема - это ато­ма­р­ный объект языка.

Описание ЯП на языке формул Бэкуса – Наура (БНФ) – это набор

< N, T, R, e >

где

N – алфавит нетерминальных символов

T – алфавит терминальных символов

R – конечный набор грамматических правил

e – символ “программа” {начальный нетерминальный символ}

Каждое грамматическое правило имеет вид

a à p,

где a - элемент алфавита Т, p – слово в объединенномалфавите N ÈT. Таким образом,

R = { a₁::= p₁, a₂::= p₂,..., a_k::= p_k }

Символ ::=, отделяющий левую часть правила (определяемый символ) от правой части (определения) означает «есть по определению».

Одно из правил в левой части должно содержать символ e. Обычно это правило в списке указывается первым:

R = { e à p₁, a₂ à p₂,..., a_k à p_k }

Пример правила

<программа>::= <заголовок>; <блок>.

Грамматическое правило описывается формулой

e à a; b.

Где e - символ понятия “программа”, a - символ понятия “заголовок”, b - символ понятия “блок”, а “; ” и “. ” – лексемы.

Правила используются в процессе синтаксического анализа программ на ЯП.

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

Например, оператор While описывается правилом

<Оператор>::= While <Логическое выражение> do <Оператор>

В язык БНФ добавляют дополнительные средства в виде двуместных операций “ * ”, “ | ”, и одноместных операций “ [ ] ”, “ { } ”. Их можно описать как сокращения исходных формул:

a::= pb и b::= q è a::= p * q

a::= p₁ и a::= p₂ è a::= p₁ | p₂

a::= p и a::= pq è a::= p[q]

a::= pa и a::= l è a::= {p}

Здесь l -символ, означающий «пустое слово».

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

Синтаксические диаграммы

Синтаксические диаграммы – наглядный способ изображения формул Бэкуса-Наура.

Понятие языка, определяемое диаграммой, указано в начале диаграммы

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

Лексемы заключаются в овалы

Нетерми­наль­ные символы - в прямоугольники.

Направление движения вдоль диаграм­мы (обхода) указы­вают стрелки, соединяющие объекты.

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

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

Синтаксические диаграммы использовались автором языка Паскаль Н. Виртом при его описании.

В заключение приведем определение блока как на языке Бэкуса-Наура, так и на языке синтаксических диаграмм.

<Блок>::= [<Раздел меток>]

[; <Раздел констант ]

[; <Раздел типов>]

[; <Раздел переменных>]

[; <Раздел процедур и функций>]

<Раздел операторов>

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычис­лить, когда этот...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: