Формальная грамматика и формальный язык

Строки (предложения) любого языка строятся из символов алфавита.

Алфавит – непустое конечное множество символов, используемых для записи предложений языка. Например, множество арабских цифр, знаки «+» и «-»: A = {0,1,2,3,4,5,6,7,8,9,+,-} – алфавит для записи целых десятичных чисел, например: «-365», «78», «+45».

Строка – любая последовательность символов алфавита, расположенных один за другим. Строки в теории формальных языков обозначаются строчными греческими буквами: α, β, γ …. Строка, содержащая 0 символов, называется пустой и обозначается символами e, e или l.

Множество всех составленных из символов алфавита A строк, в которое входит пустая строка, обозначают A*. Множество всех составленных из символов алфавита A строк, в которое не входит пустая строка, обозначают A⁺. Откуда: A* = A⁺ È { e }.

Формальным языком L в алфавите A называют произвольное подмножество множества A*. Таким образом, язык определяется как множество допустимых предложений.

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

Формальная грамматика – это математическая система, определяющая язык посредством порождающих правил – правил продукции. Она определяется как четверка:

G = (V_T, V_N, P, S),

где V_T – алфавит языка или множество терминальных (незаменяемых) символов;

V_N – множество нетерминальных (заменяемых) символов – вспомогательный алфавит, символы которого обозначают допустимые понятия языка, V_T Ç V_N =Æ;

V = V_T È V_N – словарь грамматики;

P – множество порождающих правил – каждое правило состоит из пары строк (α, β), где α Î V ⁺ – левая часть правила, β Î V ^* – правая часть правила: α ® β, где строка α должна содержать хотя бы один нетерминал;

S Î V_N – начальный символ – аксиома грамматики.

Для описания синтаксиса языков с бесконечным количеством различных предложений используют рекурсию. При этом если нетерминал в порождающем правиле расположен справа, то рекурсию называют правосторонней, если слева, то – левосторонней, а, если между двумя подстроками, то – вложенной.

Пример. Определим грамматику записи десятичных чисел G ₀:

V_T = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, -};

V_N = {<целое>, <целое без знака>, <цифра>, <знак>};

P = {<целое> ® <знак><целое без знака>, <целое> ® <целое без знака>,

<целое без знака> ® <цифра><целое без знака>, // правосторонняя рекурсия

<целое без знака> ® <цифра>,

<цифра> ® 0, <цифра> ® 1, <цифра> ® 2, <цифра> ® 3, <цифра> ® 4,

<цифра> ® 5, <цифра> ® 6, <цифра> ® 7, <цифра> ® 8, <цифра> ® 9,

<знак> ® +, <знак> ® - };

S = <целое>.

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

Форма Бэкуса-Наура (БНФ). БНФ связывает терминальные и нетерминальные символы, используя две операции: «::=» – «можно заменить на»; «|» – «или». Основное достоинство – группировка правил, определяющих каждый нетерминал. Нетерминалы при этом записываются в угловых скобках. Например, правила продукции грамматики, рассмотренной выше можно записать следующим образом:

<целое>::= <знак><целое без знака>|<целое без знака>,

<целое без знака>::= <цифра><целое без знака>|<цифра> (правосторонняя рек.),

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

<знак>::= +| -.

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

Поиск по сайту: