АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. II. Формальная логика как первая система методов философии.
  2. Аспект «Грамматика»
  3. Грамматика
  4. Грамматика
  5. ГРАММАТИКА АНГЛИЙСКОГО ЯЗЫКА
  6. ГРАММАТИКА И ЕЕ ПРЕДМЕТ
  7. Грамматика Пор-Рояля
  8. Грамматика. Предмет морфологии.
  9. Деловой этикет во Франции: Неформальная беседа
  10. Неформальная структура спортивной команды
  11. ОПЕРАТОРНАЯ ГРАММАТИКА ПРЕДШЕСТВОВАНИЯ
  12. Русская грамматика. М., 1980. Т. 2. С. 79 – 82, 137 – 143

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

Алфавит – непустое конечное множество символов, используемых для записи предложений языка. Например, множество арабских цифр, знаки «+» и «-»: 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 = (VT, VN, P, S),

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

S = <целое>.

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

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

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

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

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

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

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


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |

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



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)