Курс Основы построения трансляторов


Грамматики класса Q (Q-грамматики)


Данная грамматика отличается от S-грамматики наличие дополнительных аннулирующих правил вида:

.

A ::= e, где ? - пустая строка

 

Такое правило будем так и называть q-правилом. Приведенную выше S-грамматику  можно превратить в Q-грамматику.

 

T = {a,b}, N = {S,B}, N0 = S

S ::= aA

S ::= bSb

A ::= aA

A ::= e

 

Данная грамматика порождает цепочки вида aa…aaa и b..baaa..aaab..b. Нетрудно заметить, что аннулирующее правило используется для порождения цепочек, которые могут включать повторяющиеся произвольное число раз фрагменты без явного признака их окончания. В данном примере это имеет отношение к последовательности символов a..a , порождаемых двумя последними правилами.

Для Q-грамматик может быть использован тот же метод разбора с применением МА, однако сам принцип необходимо расширить для аннулирующих правил. Заметим, что при замене нетерминального символа правой частью одного из правил мы руководствовались первым терминальным символом правил, которой можно назвать ВЫБИРАЮЩИМ. Тогда для обычного S-правила условием замены является совпадение текущего “незакрытого” символа в распознаваемой цепочке с ВЫБИРАЮЩИМ символом правила. Для Q-правила аналогично можно ввести понятие выбирающего символа.  Рассмотрим, на каком основании тот или иной символ можно назвать выбирающим. Пусть в процессе вывода произвольной       цепочки из начального нетерминала S мы получаем цепочку с последовательностью символов Ab в некотором контексте. Если при этом A  является левой частью аннулирующего правила, то мы имеем все основания его применить. Тогда символ b, следующий за A в любом другом контексте синтаксического разбора является определяет возможность применения такого правила. Сказанное поясним примером.

 

S >> bSb >> baAb >> ba(A::= e)b >> baeb >> bab

 

Таким образом, множество выбирающих символов для применения аннулирующего правила A::=?

состоит из множества всех символов, которые могут следовать за A в любой промежуточной цепочке, выводимой из S.




Начало  Назад  Вперед