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

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

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

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

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

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

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

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

Возьмем входную цепочку «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 а:= а хог а;».

Возьмем входную цепочку «if {a or b then а:= 25;».

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

Рассмотрим процесс синтаксического анализа этой входной цепочки:

{if ( a or a then a := a ;⊥к|⊥н |λ} ÷ п

{( a or a then a := a ;⊥к|⊥н if|λ} ÷ п

{ a or a then a := a ;⊥к|⊥н if(|λ} ÷ п

{or a then a := a ;⊥к|⊥н if(a|λ} ÷ с

{or a then a := a ;⊥к|⊥н if(E|12} ÷ п

{ a then a := a ;⊥к|⊥н if( E or|12} ÷ п

{then a := a ;⊥к|⊥н if( E or a |12} ÷ с

{then a := a ;⊥к|⊥н if( E or E |12 12} ÷ с

{then a := a ;⊥к|⊥н if( E |12 12 7} – нет отношения предшествования между лексемами «(» и «then», разбор закончен, МП-автомат не перешел в конечную конфигурацию, цепочка не принята (выдается сообщение об ошибке).

В лабораторной работе № 3, так же, как и в лабораторной работе № 2, модули, реализующие синтаксический анализатор разделены на две группы:

• модули, программный код которых не зависит от входного языка;

• модули, программный код которых зависит от входного языка.

В первую группу входят модули:

• SyntSymb – описывает структуры данных для синтаксического анализа и реализует алгоритм «сдвиг-свертка» для грамматик операторного предшествования;

• FormLab3 – описывает интерфейс с пользователем.

Во вторую группу входит один модуль:

• SyntRulе – содержит описания матрицы операторного предшествования и правил исходной грамматики.

Такое разбиение на модули позволяет использовать те же самые структуры данных для организации синтаксического распознавателя при изменении входного языка.

Кроме этих модулей для реализации лабораторной работы № 3 используются программные модули TblElem и FncTree, позволяющие работать с комбинированной таблицей идентификаторов, которые были созданы при выполнении лабораторной работы № 1, а также модули LexType, LexElem, и LexAuto, которые обеспечивают работу лексического распознавателя (эти модули были созданы при выполнении лабораторной работы № 2).

Кратко опишем содержание программных модулей, используемых для организации синтаксического анализатора.

Модуль SyntRulе содержит структуры данных, которые описывают матрицу операторного предшествования и правила остовной грамматики.