2.5 Регулярные выражения и синтаксические диаграммы

Многие языковые конструкции удобно описываются регулярными выражениями. Эти выражения вводятся через понятие "регулярное множество".

Определение. Пусть - конечный алфавит. Регулярное множество в алфавите определяется рекурсивно следующим образом:

1) Æ- регулярное множество;

2) {e}-регулярное множество;

3) {a}-регулярное множество для всех ;

4) если P и Q -регулярные множества, то регулярными являются

множества:

(объединение);

PQ (конкатенация);

(итерация), где итерация множества P определяется так:

5) ничто другое не является регулярным множеством в алфавите S.

Определение. Регулярные выражения в алфавите S обозначают регулярные множества и определяются следующим образом:

1) Æ - обозначает пустое множество ;

2) е - обозначает множество {e};

3) если , то а - обозначает {a};

4) если p и q обозначают P и Q соответственно, то

(p+q) - обозначает ,

(pq) - обозначает PQ,

- обозначает ;

5) ничто другое не является регулярным выражением. ¨

Замечания:

1. Можно показать, что .

2. Лишние скобки могут устраняться из выражений, если это не приводит к недоразумениям.

3. Приоритеты операций: "*", "конкатенация", "+".

Регулярные выражения имеют следующие алгебраические свойства: если - регулярные выражения, то:

Æ - играет роль нуля ( свойство 8);

е - играет роль единицы (свойство 7).

Пример 2.16. Рассмотрим примеры регулярных выражений:

1) 01 обозначает {01};

2) 0 обозначает {0 };

3) (0+1) обозначает {0,1};

4) обозначает множество всех цепочек, составленных

из 0 и 1 и оканчивающихся цепочкой 011;

5) обозначает множество всех цепочек, составленных из 0,1,a,b и начинающихся с а или b;

6) - обозначает множество всех цепочек, содержащих четное число нулей и четное число единиц.

В практике разработки формальных языков для их описания нередко используют синтаксические диаграммы. Синтаксическая диаграмма является эквивалентным представлением грамматики языка и в ряде случаев она оказывается предпочтительнее в силу своей большей наглядности и компактности. Применение этого способа для описания лексем и конструирования сканеров будет рассмотрено в гл. 3.

2.6. Автоматы с магазинной памятью (мп - автоматы )

МП - автоматы представляют собой естественную модель синтаксических анализаторов КС - языков .

Определение. МП-автомат - это семерка

P =(Q , S , G , d , q₀ , Z₀ , F ),

где Q - конечное множество символов состояний , представляющих всевозможные состояния управляющего устройства (УУ);

S - конечный входной алфавит ;

G - конечный алфавит магазинных символов ;

d - отображение Q ´ (S È {e}) ´ G ® (Q ´ G ^* );

q₀ Î Q - начальное состояние УУ;

Z₀ Î G - символ , находящийся в магазине в начальный момен времени (начальный символ) ;

F Í Q - множество заключительных состояний .

Структура МП - автомата показана на рис.2.4.

Рис. 2.4.

Определение. Конфигурацией МП - автомата Р называется

тройка (q , w , a) Î Q ´ S ^* ´ G ^* ,

где q - текущее состояние УУ;

w- неиспользованная часть входной цепочки, причем первый символ цепочки w находится под входной головкой (если w =е , то считается, что вся входная лента прочитана);

a - содержимое магазина , причем самый левый символ

цепочки a считается верхним символом магазина ( если a= е , то магазин считается пустым ). ¨

Определение. Такт работы МП -автомата Р будем представлять в виде бинарного отношения _р ,определенного на конфигурациях. Будем записывать (q, aw , Za) ( , w , ga), если множество

d(q , a , Z) содержит ( , g) , где q, Î Q , a Î S È {e} , w Î S ^* ,

Z Î G , a,g Î G ^* . ¨

Если а¹е , то данная запись означает следующее :

МП - автомат Р , находясь в состоянии q и имея а в качестве текущего входного символа , расположенного над входной головкой , а Z - в качестве верхнего символа магазина , может перейти в новое состояние , сдвинуть входную головку на одну ячейку вправо и заменить верхний символ магазина цепочкой g магазинных символов. Если g = е , то верхний символ просто удаляется из магазина .

Если а=е, такт называется е- тактом . В таком такте текущий входной символ не принимается во внимание и входная головка не сдвигается . Однако состояния УУ и содержимое памяти могут изменяться .

Следующий такт невозможен , если магазин пуст .

Определение. Начальной конфигурацией МП - автомата Р называется конфигурация вида (q₀ , w , Z₀) , где w Î S ^* , т.е. УУ находится в начальном состоянии , входная лента содержит цепочку, которую нужно распознать , а в магазине есть только начальный символ Z₀ .

Заключительная конфигурация: (q , e , a) , где q Î F ,a Î G ^* .

Говорят , что цепочка w допускается МП - автоматом Р , если

(q₀ , w , Z₀) ^* (q , e , a) , для некоторых qÎF и a Î G ^* .

Язык, определяемый (допускаемый ) автоматом P (обозначается L(P)), - это множество цепочек допускаемых Р . ¨

Пример 2.17. Пусть Р=( {q₀ , q₁ , q₂ },{0,1},{Z ,0} , d , q₀ , Z, {q₀ }),

где d(q₀ , 0 , Z)={(q₁ , 0Z)};

d(q₁ , 0 , 0)={(q₁ , 00)};

d(q₁ , 1 , 0)={(q₂ , e)};

d(q₂ , 1 , 0)={(q₂ , e)};

d(q₂ , e , Z)={(q₀ , e)}.

Словесное описание функции d : МП - автомат копирует в магазин начальную часть входной цепочки , состоящую из нулей , а затем устраняет из магазина по одному нулю на каждую единицу, которую он видит на входе .

Рассмотрим, как этот автомат распознает w = 0011 :

(q₀ , 0011 , Z) ( q₁ , 011 , 0Z) (q₁ , 11 , 00Z)

(q₂ , 1 , 0Z) (q₂ , e , Z) (q₀ , e , e) < s t o p> .