Язык и грамматика (формы Бэкуса-Наура)
Формальный язык является объединением нескольких множеств:
· множества исходных символов, называемых литерами (алфавит),
· множества правил, которые позволяют строить из букв алфавита новые слова (правила порождения слов или идентификаторов),
· множества предопределённых идентификаторов или словаря ключевых слов (прочие идентификаторы называются именами),
· множества правил, которые позволяют собирать из имён и ключевых слов выражения, на основе которых строятся простые и сложные предложения (правила порождения операторов или предложений).
Грамматические правила можно записывать различными способами. Грамматика естественного языка традиционно описывается в виде грамматических правил на естественном языке.
Грамматика формального языка также может быть описана в виде множества правил на естественном языке. Но обычно для этого используют специальные средства записи: формулы и схемы. В качестве примера рассмотрим простой формальный язык.
Алфавит этого языка состоит из 17 букв:
А Б Е З И Й К Н О П Р С Т У Ч Ш Ы
и одного знака пунктуации - '.' (точки).
Рассмотрим систему правил, составляющих грамматику языка.
Правила словообразования (мы не будем вдаваться в их подробное описание) позволяют сформировать из букв языка 5 различных идентификаторов (имён и ключевых слов):
КУБ ШАР ПРОЗРАЧНЫЙ СИНИЙ УКРАШАЕТ
и ни одним идентификатором больше.
Идентификаторы КУБ
и ШАР
считаются именами, прочие идентификаторы считаются ключевыми словами.
По весьма отдалённой аналогии с естественным языком, ключевые слова будут играть роли членов предложения и частей речи.
· Определение сказуемого (это член предложения): ключевое слово УКРАШАЕТ
будем считать сказуемым.
· Определение прилагательного (это часть речи): ключевые слова ПРОЗРАЧНЫЙ
и СИНИЙ
будем считать прилагательными.
· Имена играют роль существительных.
По аналогии с естественным языком, где предложения строятся из членов предложений, предложения-операторы языка состоят из членов предложений-выражений. Часть выражений считается подлежащими, часть - дополнениями.
· Определение подлежащего: выражения-подлежащие состоят из ключевого слова-прилагательного и имени.
· Определение дополнения: выражения-дополнения состоят из ключевого слова-прилагательного и имени (одного из двух).
· Определение оператора (это последнее правило грамматики): предложение состоит из тройки выражений, самым первым из которых является подлежащее, затем сказуемое и дополнение. Предложение заканчивается точкой.
Только что нами была определена грамматика формального языка. Она была описана привычным способом, с помощью нескольких предложений русского языка.
Рассмотрим ещё один способ записи этой грамматики - с помощью формул. Запишем сначала в виде формулы определение оператора:
оператор ::= подлежащее сказуемое дополнение. (1)
В этой формуле символ ::= следует читать как "является" или "заменить".
Затем определим в виде формул подлежащее и дополнение:
подлежащее ::= прилагательное существительное (2)
дополнение ::= прилагательное существительное (3)
Следующая формула отражает тот факт, что сказуемым является ключевое слово УКРАШАЕТ.
сказуемое ::= УКРАШАЕТ (4)
Следующее правило определяет прилагательное:
прилагательное ::= ПРОЗРАЧНЫЙ | СИНИЙ (5)
Здесь вертикальная черта между двумя ключевыми словами означает, альтернативу (прилагательным в выражении может быть либо ключевое слово ПРОЗРАЧНЫЙ, либо ключевое слово СИНИЙ). Существует еще, по крайней мере, один способ описания альтернативы. Воспользуемся им при определении существительного. Это правило задаёт множество имён:
существительное ::= ШАР (6)
::= КУБ
Правила построения предложений в нашем языке оказались записаны с помощью шести коротких формул. Слова, стоящие справа и слева от знака "заменить" принято называть символами формальной грамматики, а сами формулы - грамматическими правилами.
Заметим, что символы в формулах грамматики не являются словами в о
· Символы, которые встречаются только в левой части правил, называются начальными нетерминальными символами или начальными нетерминалами.
· Символы, которые встречаются как в левой, так и в правой части грамматических правил называются нетерминальными символами.
· Символы, которые встречаются только в правой части правил, называются терминальными символами.
Воспользуемся этой грамматикой и построим несколько предложений.
Алгоритм порождения операторов-предложений и отдельных выражений с помощью правил формальной грамматики очень прост:
1. Выбрать начальный нетерминал (оператор) или отдельный нетерминальный символ, найти правило, содержащее этот символ в левой части и заменить его на символ или на последовательность символов из правой части правила.
2. Процесс замены продолжать до тех пор, пока в предложении будут встречаться нетерминальные символы.
Выбор нетерминального символа обеспечивает порождение выражения, выбор начального нетерминала обеспечивает вывод оператора:
оператор (1)
подлежащее сказуемое дополнение. (2)
прилагательное существительное сказуемое дополнение. (3)
прилагательное существительное сказуемое прилагательное существительное. (4)
прилагательное существительное УКРАШАЕТ прилагательное существительное. (5)
ПРОЗРАЧНЫЙ существительное УКРАШАЕТ СИНИЙ существительное. (6)
ПРОЗРАЧНЫЙ ШАР УКРАШАЕТ СИНИЙ КУБ.
Больше терминальных символов нет. По правилам формальной грамматики мы построили первое предложение языка.
СИНИЙ КУБ УКРАШАЕТ ПРОЗРАЧНЫЙ КУБ.
Это ещё одно предложение нашего языка.
Формальная грамматика может использоваться не только для порождения предложений, но и для проверки, является ли какая-либо последовательность символов выражением языка. Для этого среди символов исследуемой последовательности надо сначала отыскать терминальные символы и применяя правила формальной грамматики, справа налево заменять терминальные символы нетерминальными, а затем "сворачивать" последовательности нетерминальных символов до тех пор, пока не будет получен начальный нетерминал, или окажется единственный нетерминальный символ.
Так последовательность символов
СИНИЙ КУБ ВЕНЧАЕТ ПРОЗРАЧНЫЙ КУБ.
не является оператором языка, поскольку символ ВЕНЧАЕТ не встречается среди нетерминальных символов. В свою очередь, пара терминальных символов СИНИЙ ШАР является выражением нашего языка и может быть как подлежащим, так и дополнением, поскольку может быть преобразована как в нетерминальный символ подлежащее, так и в нетерминальный символ дополнение.
Рассмотренный нами способ записи правил грамматики языка называется формой Бэкуса-Наура (сокращенно БНФ).
Символы формальной грамматики складываются в основном из букв родного алфавита. Формулы кратки и информативны. Правила, для изложения которых обычно требуется несколько фраз естественного языка, часто описываются одной формой Бэкуса-Наура. После небольшой тренировки чтение этих форм становится лёгким и приятным занятием.
Впервые БНФ были использованы при описании языка программирования Алгол более 30 лет назад и до сих пор БНФ применяются для описания грамматики при разработке новых языков программирования. Это очень эффективное и мощное средство. Без лишних слов, просто, лаконично, наглядно.
Подобно предложениям естественного языка, которые обычно служат основой связного повествования (сказки, романа, научного исследования), предложения формального языка также могут быть использованы для описания всевозможных явлений и процессов. Множества операторов языка программирования служат для создания программ - основного жанра произведений, для которых и используются эти языки. Программы пишут для различных программируемых устройств. К их числу относятся и электронно-вычислительные машины, которые в настоящее время являются наиболее универсальными вычислительными устройствами и основными потребителями программ.