Основные понятия теории формальных языков и грамматик

Выводы цепочек формальных грамматик. Деревья КСГ

Старый дуб заслоняет старый дом

Дерево представляет собой синтаксическую структуру предложения. Из него видно, что результирующая цепочка не зависит от порядка, в котором делались замены промежуточных элементов. Элементы грамматики, такие как подлежащее, существительное и другие, называются вспомогательными или нетерминальными символами. В контекстно-свободной грамматике может быть любое конечное число нетерминальных символов. Символы - дуб, дом, старый, заслоняет,., в рассмотренной грамматике играют роль слов из словаря языка и называются терминальными (основными) символами или просто терминалами. Может существовать любое конечное число терминалов в контекстно-свободной грамматике. В языках программирования терминальными являются используемые в них слова и символы: DO, IF, +,...

В общем виде правила грамматики можно записать:

нетерминал ® любая конечная цепочка терминальных и нетерминальных символов или одних терминалов.

Цепочка справа от стрелки может быть пустой, что обозначается в

грамматике следующим образом: < F> ® e. Такое правило называется эпсилон - правилом.

В отдельных языках программированияправилавыглядят в соответствии с записью

< оператор > ® IF < логическое выражение > THEN < оператор >

Один из нетерминальных символов всегда выделяется в качестве начального. Его называют аксиомой грамматики. С него всегда должен начинаться вывод цепочек языка.

Контекстно-свободная грамматика (КСГ) задается:

конечным множеством терминалов; - конечным множеством нетерминалов; конечным множеством правил вида < A > ® a, где А - нетерминал, a - цепочка терминальных и нетерминальных символов (возможно пустая) или цепочка терминальных символов; нетерминал А называется левой частью правила, а a - правой; одним нетерминальным символом, выделенным в качестве начального (аксиомой грамматики).

Проанализируем грамматику, правила которой имеют вид:

1. S ® a A b S 2. S ® b

3. A ® A S c 4. A ® e

Из записи следует: { A,S } - словарь нетерминальных символов;

{a, b, c} - словарь терминальных символов; e - пустая цепочка и, следовательно, не является символом грамматики. Правило 4 можно записать в виде А ®.

Рассмотрим еще один способ записи правил формальной грамматики, называемый формой Бэкуса-Наура:

1. <S>:= a <A> b <S> | b 2. <A>:= <A> <S> c | e

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

Рассмотрим грамматику с аксиомой грамматики < S > и правилами вывода вида:

1. S ® a A B c 2. S ® 3. A ® c S B

2. 4. A ® A b 5. B ® b B 6. B ® a

Если начать вывод цепочек языка, используя первое правило, то последовательность подстановок может быть следующей:

· S ® a A B c (1 правило)

· S ® a A b B c (5 правило)

· S ® a A b a c (6 правило)

· S ® a c S B b a c (3 правило)

· S ® a c S a b a c (6 правило)

· S ® a c a b a c (2 правило)

В рассмотренном выводе присутствует семь цепочек, включая начальную и заключительную.

Определение. Язык, задаваемый грамматикой, есть множество терминальных цепочек, которые можно вывести из начального символа грамматики.

Построим дерево вывода цепочки: a c a b a c, используя выше рассмотренную грамматику.

S

a A B c

A b a

c S B

a

Замечание. Для каждого дерева существует единственный левый и правый выводы, то есть вывод, когда на каждом шаге заменяется самый левый (правый) нетерминальный символ. Многие методы обработки языков рассчитаны исключительно на левый (правый) выводы. В подобных случаях пишут:

a ® _LB (L - left)

a ® _RB (R - right).

Цепочке языка может соответствовать более чем одно дерево, так как она может иметь разные выводы, порождающие разные деревья. Если одна цепочка имеет несколько деревьев вывода, то говорят, что соответствующая грамматика неоднозначна.

Пусть задан алфавит V терминальных символов. Множество всех конечных слов или цепочек в алфавите V обозначим V*.

Формальный язык L над алфавитом V - это подмножество множества V*, то есть L (V) Í V* [10].

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

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

{ V, W, P, S }, где V - словарь терминалов, W - словарь нетерминалов, причем V Ç W = Æ, P - множество правил вида j ® y, где j и y Î (V È W),

S - аксиома грамматики.

Определение. Цепочка b называется выводимой из цепочки a, если они представимы в виде:

b = l j d a = l y d

и в грамматике существует правило вида y ® j.

Определение. Цепочка b называется выводимой из a, если существует конечная последовательность цепочек вывода:

a ® x₀ x₀ ® x_1,....., x_k ® b, где цепочка x_i непосредственно выводима из x_i-1 для всех i=0,1,..., k-1.

Введем обозначение a ® b. Это значит, что b выводима из a

в грамматике G.

Определение. Языком L (G), порождаемым грамматикой G, называется множество всех цепочек, выводимых из аксиомы грамматики.

Определение. Грамматики G1 и G2 эквивалентны тогда и только тогда, когда они порождают один и тот же язык.

Литература

1. Казиев В.М. Введение в информатику. www.intuit.ru

2. Коршунов Ю.М. Математические основы кибернетики. - М.: Энергия,

1980. - 423 с.

3. Мельников В.В. Защита информации в компьютерных системах. М.:

Финансы и статистика, 1997.

4. Жельников В. Криптография от папируса до компьютера. М.: АBF, 1996.

5. Грушо А.А., Тимонина Е.Е. Теоретические основы защиты информации.

М.: Яхтсмен, 1996.

6. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для

инженера. - М.: Энергия, 1980. - 342с.

7. Поспелов Д.А. Логические методы анализа и синтеза схем.- М.:

Энергия, 1974. - 368 с.

8. Динман М.И. С++. Освой на примерах. – СПб.: БХВ Петербург, 2006. –

384 с.

9. Фридман А.Л. Язык программирования Си++. Интернет-университет

информационных технологий - ИНТУИТ.ру, 2004.

10. Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы

проектирования компиляторов. - М.: Мир, 1979. - 654 с.

11. Ленгсам Й., Огенстайн М., Тененбаум. Структуры данных для

персональных ЭВМ. — М.: Мир, 1989. — 568 с.

12. Вирт Н. Алгоритмы + структуры данных = программы. — М.: Мир, 1985.

- 406 с.

Дата добавления: 2014-01-20