Язык и грамматика формы Бэкуса-Наура

Язык и грамматика (формы Бэкуса-Наура)

Формальный язык является объединением нескольких множеств:

· множества исходных символов, называемых литерами (алфавит),

· множества правил, которые позволяют строить из букв алфавита новые слова (правила порождения слов или идентификаторов),

· множества предопределённых идентификаторов или словаря ключевых слов (прочие идентификаторы называются именами),

· множества правил, которые позволяют собирать из имён и ключевых слов выражения, на основе которых строятся простые и сложные предложения (правила порождения операторов или предложений).

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

Грамматика формального языка также может быть описана в виде множества правил на естественном языке. Но обычно для этого используют специальные средства записи: формулы и схемы. В качестве примера рассмотрим простой формальный язык.

Алфавит этого языка состоит из 17 букв:

А Б Е З И Й К Н О П Р С Т У Ч Ш Ы

и одного знака пунктуации - '.' (точки).

Рассмотрим систему правил, составляющих грамматику языка.

Правила словообразования (мы не будем вдаваться в их подробное описание) позволяют сформировать из букв языка 5 различных идентификаторов (имён и ключевых слов):

КУБ
ШАР
ПРОЗРАЧНЫЙ
СИНИЙ
УКРАШАЕТ

и ни одним идентификатором больше.

Идентификаторы КУБ и ШАР считаются именами, прочие идентификаторы считаются ключевыми словами.

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

· Определение сказуемого (это член предложения): ключевое слово УКРАШАЕТ будем считать сказуемым.

· Определение прилагательного (это часть речи): ключевые слова ПРОЗРАЧНЫЙ и СИНИЙ будем считать прилагательными.

· Имена играют роль существительных.

По аналогии с естественным языком, где предложения строятся из членов предложений, предложения-операторы языка состоят из членов предложений-выражений. Часть выражений считается подлежащими, часть - дополнениями.

· Определение подлежащего: выражения-подлежащие состоят из ключевого слова-прилагательного и имени.

· Определение дополнения: выражения-дополнения состоят из ключевого слова-прилагательного и имени (одного из двух).

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

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

Рассмотрим ещё один способ записи этой грамматики - с помощью формул. Запишем сначала в виде формулы определение оператора:

оператор ::= подлежащее сказуемое дополнение. (1)

В этой формуле символ ::= следует читать как "является" или "заменить".

Затем определим в виде формул подлежащее и дополнение:

подлежащее ::= прилагательное существительное (2)

дополнение ::= прилагательное существительное (3)

Следующая формула отражает тот факт, что сказуемым является ключевое слово УКРАШАЕТ.

сказуемое ::= УКРАШАЕТ (4)

Следующее правило определяет прилагательное:

прилагательное ::= ПРОЗРАЧНЫЙ | СИНИЙ (5)

Здесь вертикальная черта между двумя ключевыми словами означает, альтернативу (прилагательным в выражении может быть либо ключевое слово ПРОЗРАЧНЫЙ, либо ключевое слово СИНИЙ). Существует еще, по крайней мере, один способ описания альтернативы. Воспользуемся им при определении существительного. Это правило задаёт множество имён:

существительное ::= ШАР (6)

::= КУБ

Правила построения предложений в нашем языке оказались записаны с помощью шести коротких формул. Слова, стоящие справа и слева от знака "заменить" принято называть символами формальной грамматики, а сами формулы - грамматическими правилами.

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

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

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

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

Воспользуемся этой грамматикой и построим несколько предложений.

Алгоритм порождения операторов-предложений и отдельных выражений с помощью правил формальной грамматики очень прост:

1. Выбрать начальный нетерминал (оператор) или отдельный нетерминальный символ, найти правило, содержащее этот символ в левой части и заменить его на символ или на последователь

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать