Расширенные грамматики

Формальное определение языка

Способы получения одних цепочек символов из других

1 Это можно сделать непосредственно, т.е. за одну операцию. Условное обозначение Þ.

Например, dÞh означает, что цепочку символов h можно получить из цепочки d за одну операцию.

Пример. Есть цепочка d=aAb и h=anb. Здесь, a,n,b - терминальные символы (обозначены строчными буквами), а А – нетерминальный символ. Пусть среди множества правил Р есть такое: A®nЄР. То есть нетерминальный символ АЄN можно заменить на терминальный n. Таким образом, за одну операцию из d можно получить цепочку h.

2 Одну цепочку из другой можно получить не за одну операцию. Условие обозначения Þ*

Например, a₀ Þ*a_n

Это имеет место, если a₀ = a_n, или существует последовательность непосредственно получаемых цепочек таких, что a₀ Þ a₁ Þ a₂ Þ… a_n-1 Þ a_n

Способы получения цепочек символов необходимы, чтобы формально дать определение языка L(G), описываемое заданной грамматикой G. Язык L(G) – это множество цепочек w терминальных (и только терминальных!) символов, выводимых из начального (стартового, главного) нетерминального символа S. L(G)={w|S Þ*w,w –терминальные цепочки}.

Вертикальная черта после w в выражении означает, что w получены при условии что они выводятся из S. А звездочка означает, что этот вывод может происходить за произвольное количество операций. При этом используется множество P правил, описанное в грамматике G.

Ниже приводятся примеры грамматики и описываемые ими языки.

Пример 1 G=(T,N,P,S)

T={x, y, w, z} – алфавит терминальных символов. Только эти символы можно использовать.

N={S, A, B} – множество нетерминальных символов, из которых S – главный (стартовый) нетерминальный символ. Именно с него должен начинаться вывод цепочек (слов) в соответствии с множеством правил вывода P.

p={S®AB, A®x,A®y, B®w, B®z}.

Эти правила означают, что S можно заменить последовательностью нетерминальных символов AB. A®x, A®y означает, что А можно заменить на x или на y и т.д., осуществляя эти замены, получаем цепочки w из терминальных символов, составляющих формальный язык L(G).

L(G)={xw, yw, xz, yz}.

Только эти четыре цепочки (слова) и составляют язык, описываемый заданной грамматикой G.

Существуют т.н. расширенные грамматики. Они порождают те же языки, что и рассмотренные выше грамматики, но являются более наглядными.

Расширенные грамматики задаются парами

A_i ® r_i,

где A_i ЄN – i-й нетерминальный символ,

r_i – i-е регулярное выражение в алфавите N U I.

Нетерминальный символ первой пары является ГЛАВНЫМ (стартовым)для вывода цепочек.

Например, расширенная грамматика, эквивалентная описанной в примере выше, имеет вид:

S®AB,

A®x|y,

B®w|z.

Напомним, что вертикальная черта читается как “или”. То есть А может быть заменена на x или y, а В – на w или z.

Пример 2

Алфавит терминальных символов

Т={вино, коньяк, каша, борщ, мясо, кофе, чай}

Алфавит нетерминальных символов

N={ОБЕД, АЛКОГОЛЬ, ЕДА, ПИТЬЕ}

ОБЕД®АЛКОГОЛЬ ЕДА ПИТЬЕ

АЛКОГОЛЬ ® коньяк | вино

ЕДА ® борщ каша | мясо

ПИТЬЕ ® чай | кофе

В первой паре описан главный нетерминальный символ ОБЕД. Он описывается как последовательность из АЛКОГОЛЬ, ЕДА, ПИТЬЕ. В свою очередь, АЛКОГОЛЬ – это или коньяк, или вино.

ЕДА состоит из борща, за которым следует или каша, или мясо.

ПИТЬЕ – это или чай, или кофе.

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

Например, ОБЕД ® АЛКОГОЛЬ * ЕДА ПИТЬЕ означает, что АЛКОГОЛЬ может повторяться в цикле нуль и более раз. После этого идут ЕДА и ПИТЬЕ.

Рассмотрим также другие варианты.

Например, АЛКОГОЛЬ ® КОНЬЯК + вино* означает, что должен быть хотя бы раз выпит коньяк, а затем может циклически приниматься вино. Количество этих циклов от нуля и более раз.

Или еще вариант: ЕДА ® борщ * мясо + каша

Борщ может употребляться от нуля и больше раз. Затем обязательно хотя бы один раз мясо и после этого – каша.

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

Дата добавления: 2015-06-27