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

Аналогично, для заполнения столбца, помеченного ⊥_к, возьмем множество R^(S). В это множество входит только один символ —;. Поэтому в столбце матрицы, помеченном символом ⊥_к, ставим знак «.>» («следует») в клетке на пересечении со строкой, помеченной символом;.

В итоге получим заполненную матрицу операторного предшествования, которая представлена в табл. 3.8.

Таблица 3.8. Матрица операторного предшествования

Теперь на основе исходной грамматики G можно построить остовную грамматику G'({if,then,else,a,=,or,xor,and,(,),},{E},P',E) с правилами P':

E → E; – правило 1;

E → if E then E else E | if E then E | a:= E – правила 2, 3 и 4;

E → if E then E else E | a:= E – правила 5 и 6;

E → E or E | E xor E | E – правила 7, 8 и 9;

E → E and E | E – правила 10 и 11;

E → a | (E) – правила 12 и 13.

Жирным шрифтом в грамматике и в правилах выделены терминальные символы.

Всего имеем 13 правил грамматики. Причем правила 2 и 5, а также правила 4 и 6 в остовной грамматике неразличимы, а правила 9 и 11 не имеют смысла (как было уже сказано, цепные правила в остовных грамматиках теряют смысл). То, что две пары правил стали неразличимы, не имеет значения, так как по смыслу (семантике входного языка) эти две пары правил обозначают одно и то же (правила 2 и 5 соответствуют полному условному оператору, а правила 9 и 11 – оператору присваивания). Поэтому в дереве синтаксического разбора нет необходимости их различать. Следовательно, синтаксический распознаватель может пользоваться остовной грамматикой G'.

Примеры выполнения разбора предложений входного языка

Рассмотрим примеры разбора цепочек входного языка в виде последовательности конфигураций МП-автомата, выполняющего разбор. Результат разбора будем представлять в виде последовательности номеров правил грамматики. На основе найденной последовательности правил после выполнения разбора при отсутствии ошибок (когда входная цепочка принята МП-автоматом) можно построить дерево синтаксического разбора.

Рассматриваемый МП-автомат имеет только одно состояние. Тогда для иллюстрации работы МП-автомата будем записывать каждую его конфигурацию в виде трех составляющих {α|β|γ}, где:

• α – непрочитанная часть входной цепочки;

• β – содержимое стека МП-автомата;

• γ – последовательность номеров примененных правил.

В начальном состоянии вся входная цепочка не прочитана, стек автомата содержит только лексему типа «начало строки», последовательность номеров правил пуста.

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

Пример 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;

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