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


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


Грамматика строится по очень простому принципу:

правая часть каждого правила должна начинаться с терминального символа;

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

не допускаются правила с пустой правой частью.

Следующая грамматика является S-грамматикой:

.

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

S ::= aA

S ::= bSb

A ::= aA

A ::= b

 

Данная грамматика порождает цепочки вида aa…aaab и b..baaa..aaabb..b.

Для начала рассмотрим, как будет происходит нисходящий СА для такой грамматики:

дерево разбора строится сверху вниз;

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

принцип замены вытекает из самого определения S-грамматики. Для замены выбирается такое правило, у которого первый терминальный символ совпадает с очередным “незакрытым” символом в входной цепочке. Сказанное поясним примером:


.

    b  b  a  a  b  b  b

    |  |  |  |  |

    |  |  |  |  b                  S ::=b

    |  |  |  |  --

    |  |  |  a  A  b  b            S ::=aA

    |  |  |  ----

    |  |  a  A  b  b               S ::=aA

    |     ----

    |  b  S  b  b                  S ::=bSb

    |  ------- 

       b  S  b

       -------                     S ::=bSb

          S

 

Начальный нетерминальный символ грамматики S. Поэтому он и является начальной цепочкой нисходящего вывода. Он может быть заменен на правую часть одного из двух правил  S ::=aA или S::=bSb. Какое будет выбрано, определяется первым символом в распознаваемой цепочке. Поскольку это - b, то выбирается второе правило и цепочка примет вид bSb. Заметим, что первые символы в распознаваемой и выводимой цепочке совпадают, то есть перекрываются. Тогда второй символ распознаваемой цепочке оказывается “незакрытым” и соответствующим нетерминалу S в выводимой цепочке. Для этой пары такая процедура должна быть повторена.

Если использовать МА, то естественным местом для размещения выводимой цепочки является стек (магазин).


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