Книга: Системное программное обеспечение. Лабораторный практикум

Пример 1

Возьмем входную цепочку «if a or b and c then a:= 1 xor c;».

После выполнения лексического анализа, если все лексемы типа «идентификатор» и «константа» обозначить как «a», получим цепочку: «if a or a and a then a:= a xor a;».

Рассмотрим процесс синтаксического анализа этой входной цепочки. Шаги функционирования МП-автомата будем обозначать символом «_?». Символом «_?п» будем обозначать шаги, на которых выполняется сдвиг (перенос), символом «_?с» – шаги, на которых выполняется свертка.

{if a or a and a then a := a xor a;?к|?н |л} ч п

{a or a and a then a := a xor a;?к|?н if|л} ч п

{or a and a then a := a xor a;?к|?н if a|л} ч с

{or a and a then a := a xor a;?к|?н if E|12} ч п

{a and a then a := a xor a;?к|?н if E or|12} ч п

{and a then a := a xor a;?к|?н if E or a|12} ? с

{and a then a := a xor a;?к|?н if E or E|12 12} ? п

{a then a := a xor a;?к|?н if E or E and|12 12} ? п

{then a := a xor a;?к|?н if E or E and a|12 12} ? с

{then a := a xor a;?к|?н if E or E and E|12 12 12} ? с

{then a := a xor a;?к|?н if E or E|12 12 12 10} ? с

{then a := a xor a;?к|?н if E|12 12 12 10 7} ? п

{a := a xor a;?к|?н if E then|12 12 12 10 7} ч п

{:= a xor a;?к|?н if E then a|12 12 12 10 7} ч п

{a xor a;?к|?н if E then a :=|12 12 12 10 7} ч п

{xor a;?к|?н if E then a := a|12 12 12 10 7} ч с

{xor a;?к|?н if E then a := E|12 12 12 10 7 12} ч п

{a;?к|?н if E then a := E xor|12 12 12 10 7 12} ч п

{;?к|?н if E then a := E xor a|12 12 12 10 7 12} ч с

{;?к|?н if E then a:= E xor E|12 12 12 10 7 12} ? с

{;?к|?н if E then a := E|12 12 12 10 7 12 12 8} ? с

{;?к|?н if E then E|12 12 12 10 7 12 12 8 4} ? с

{;?к|?н E|12 12 12 10 7 12 12 8 4 3} ? п

{?к|?н E;|12 12 12 10 7 12 12 8 4 3} ? с

{?к|E?н |12 12 12 10 7 12 12 8 4 3 1}– разбор закончен, МП-автомат перешел в конечную конфигурацию, цепочка принята.

В результате получим последовательность правил: 12 12 12 107 12 12843 1. Этой последовательности правил будет соответствовать цепочка вывода на основе остовной грамматики С:

E?1 E; ?3 if E then E; ?4 if E then a := E; ?8 if E then a := E xor E; ?12 if E then a := E xor a; ?12 if E then a := a xor a; ?7 if E or E then a:= a xor a; ?10 if E or E and E then a := a xor a; ?12 if E or E and a then a := a xor a; ?12 if E or a and a then a := a xor a; ?12 if a or a and a then a := a xor a;

Стоит обратить внимание, что, так как данный МП-автомат строит правосторонний вывод, в цепочке вывода на каждом шаге правило всегда применяется к крайнему правому нетерминальному символу в цепочке.

Дерево синтаксического разбора, соответствующее данной входной цепочке, приведено на рис. 3.2.

Рис. 3.2. Дерево синтаксического разбора входной цепочки «if a or a and a then а:= а хог а;».

Оглавление книги