Формальные языки и грамматики.

 

Необходимость создания формальных языков связана с определенными недостатками естественного языка, которые выявились при его использовании в теории алгоритмов. Рассмотрим некоторые из них:

1. зависимость способов построения предложений (синтаксиса) от их смысла (семантики). Например, необходимо использовать предложение “Врач осмотрел больного” или “Врач осмотрела больного” в зависимости от принадлежности врача к соответствующему полу;

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

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

4. наличие парадоксов, рассмотренных в предыдущем параграфе.

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

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

(X,Y,R,S),

где Х - алфавит терминальных символов формального языка;

Y - вспомогательный алфавит нетерминальных символов;

R - конечный набор синтаксических правил;

S - начальный вспомогательный символ из множества нетерминальных символов (терминальный символ – наименьший значимый элемент формального языка).

Каждое синтаксическое правило из R представляет собой подстановку А→В, в которой А и В - некоторые слова, образованные из символов алфавитов Х и Y. Предложения формального языка начнем получать, если применим к нетерминальному символу S некоторую подстановку из R. Такая подстановка, левая часть которой соответствует нетерминальному символу S, должна находиться в R. Если полученный результат содержит только терминальные символы, то это значит, что предложение языка уже получено. Если в полученной цепочке присутствуют нетерминальные символы, то начинаем опять применять к этой цепочке одну из подстановок из R, причем любую из них. Если полученная цепочка имеет несколько вхождений слова А, то соответствующая подстановка допускает замену любого из этих вхождений А на В.

Рассмотрим пример формальной грамматики, в которой X={1,0}, Y={S}, а система подстановок имеет вид:

1. S→0;

2. S→1;

3. S→0S0;

  1. S→lSl.

Такая грамматика порождает формальный язык, содержащий двоичные числа, которые слева направо читаются так же, как справа налево. Например, применение подстановок 3, 4, 1 приведет к получению числа 01010; подстановок 4, 3, 3, 2 - к получению числа 1001001 и т.д.

Нормальная форма Бэкуса-Наура.

 

Нормальная форма Бэкуса-Наура (БНФ) - это еще один способ описания формального языка.

Для описания формального языка при помощи БНФ будем использовать синтаксические правила (продукции), в которых будем использовать следующие символы:

1. ::= - это символ, который отделяет левую часть продукции, являющейся нетерминальным символом, от правой части, являющейся непустой, конечной цепочкой терминальных и нетерминальных символов. Символ ::= читается как по определению есть или как может состоять из;

2. | - это разделитель, который помещается между различными формами одного и того же нетерминального понятия. Символ читается как или;

3. < > - угловые скобки используются для выделения нетерминального символа, т.е. такого понятия, которое не может встречаться в предложениях описываемого языка и применяется для того, чтобы помочь описать эти предложения.

Рассмотрим примеры описания десятичных цифр и констант целого типа при помощи БНФ.

Тот факт, что 1 является цифрой, выражается при помощи БНФ следующим образом:

<цифра>::=1.

При этом угловые скобки < > используются для того, чтобы выделить нетерминальный символ, который не может встречаться в предложениях описываемого формального языка, и предназначен для описания синтаксического правила. Символ 1 может встречаться в предложениях описываемого формального языка и является терминальным символом.

Для того чтобы показать, что нетерминальный символ <цифра> может быть 0 или 1, можно воспользоваться следующим синтаксическим правилом:

<цифра>::=0 | 1.

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

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

 

Константы целого типа могут быть рекурсивно определены следующим образом:

  1. <константа>::=<цифра>;
  2. <константа>::=<константа> <цифра>;
  3. <цифра>::=0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9.

Первое из правил читается: <константа> может состоять из <цифры>. Второе правило читается: <константа> может состоять из другой <константы>, за которой следует <цифра>.

Приведенные синтаксические правила образуют грамматику для языка <констант>. Предложениями этого языка являются последовательности терминальных символов, которые могут быть выведены из нетерминального символа <константа>. Рассмотрим пример получения константы 673 посредством использования синтаксических правил, записанных при помощи БНФ:

  1. используем второе правило: нетерминальный символ <константа> заменяем на цепочку <константа> <цифра>;
  2. используем третье правило: нетерминальный символ <цифра> заменяем на терминальный символ 3;
  3. используем снова второе правило и получаем <константа> <цифра>3;
  4. используем третье правило и получаем <константа> 73;
  5. используем первое правило: нетерминальный символ <константа> заменяем на нетерминальный символ <цифра>, в результате получаем цепочку <цифра> 73;
  6. используем третье правило и получаем 673.

БНФ и ее модификации являются в настоящее время стандартным средством описания синтаксиса языков программирования.