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

Требования к выполнению работы

Порядок выполнения работы

Для выполнения лабораторной работы требуется написать программу, которая выполняет лексический анализ входного текста в соответствии с заданием, порождает таблицу лексем и выполняет синтаксический разбор текста по заданной грамматике с построением дерева разбора. Текст на входном языке задается в виде символьного (текстового) файла. Синтаксис входного языка и перечень допустимых лексем указаны в задании. Допускается исходить из условия, что текст содержит не более одного предложения входного языка.

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

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

Для выполнения лексического анализа рекомендуется использовать программные модули, созданные в результате выполнения лабораторной работы № 2.

Длину идентификаторов и строковых констант можно считать ограниченной 32 символами. Программа должна допускать наличие комментариев неограниченной длины во входном файле. Форму организации комментариев предлагается выбрать самостоятельно.

1. Получить вариант задания у преподавателя.

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

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

4. Подготовить и защитить отчет.

5. Написать и отладить программу на ЭВМ.

6. Сдать работающую программу преподавателю.

Требования к оформлению отчета

Отчет должен содержать следующие разделы:

• Задание по лабораторной работе.

• Краткое изложение цели работы.

• Запись заданной грамматики входного языка в форме Бэкуса—Наура (если для построения синтаксического распознавателя используется механизм, требующий преобразования исходной грамматики входного языка, то эти преобразования и полученная в результате их грамматика должны быть отражены в отчете).

• Множества крайних правых и крайних левых символов с указанием шагов построения.

• Множества крайних правых и крайних левых терминальных символов.

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

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

• Текст программы (оформляется после выполнения программы на ЭВМ).

Основные контрольные вопросы

• Какую роль выполняет синтаксический анализ в процессе компиляции?

• Какие проблемы возникают при построении синтаксического анализатора и как они могут быть решены?

• Какие типы грамматик существуют? Что такое КС-грамматики? Расскажите об их использовании в компиляторе.

• Какие типы распознавателей для КС-грамматик существуют? Расскажите о недостатках и преимуществах различных типов распознавателей.

• Поясните правила построения дерева вывода грамматики.

• Что такое грамматики простого предшествования?

• Как вычисляются отношения предшествования для грамматик простого предшествования?

• Что такое грамматика операторного предшествования?

• Как вычисляются отношения для грамматик операторного предшествования?

• Расскажите о задаче разбора. Что такое распознаватель языка?

• Расскажите об общих принципах работы распознавателя языка.

• Что такое перенос, свертка? Для чего необходим алгоритм «перенос-свертка»?

• Расскажите, как работает алгоритм «перенос-свертка» в общем случае (с возвратами).

• Как работает алгоритм «перенос-свертка» без возвратов (объясните на своем примере)?

Варианты заданий

Варианты исходных грамматик

Далее приведены варианты грамматик. Во всех вариантах символ S является начальным символом грамматики; S, F, T и Е обозначают нетерминальные символы.

Терминальные символы выделены жирным шрифтом. Вместо символа а должны подставляться лексемы.

1. S → a:= F;

F → F+T |Т

Т → Т·Е | TIE | Е

Е → (F) | – (F) | а

2. S → a:= F;

F → F or Т | F хог T | T

T → Т and E | Е

Е → (F) | not (F) | a

3. S → F;

F → if E then T else F| if E then F| a:= a

T → if E then T else T | a:= a

E → a<a | a>a | a=a

4. S → F;

F → for (T) do F | a:= a

T → F;E;F |;E;F | F;E; |;E;

E → a<a I a>a I a=a

Исходные грамматики и типы допустимых лексем

Ниже в табл. 3.1 приведены номера заданий. Для каждого задания указана соответствующая ему грамматика и типы допустимых лексем.

Таблица 3.1. Номера заданий для выполнения лабораторной работы

Примечание.

• Римскими числами считать последовательности больших латинских букв X, V и I.

• Шестнадцатеричными числами считать последовательность цифр и символов «а», «Ь», «с», «d», «е» и «f», начинающуюся с цифры (например: 89, 45ас9, 0abc4).

• Для выполнения работы рекомендуется использовать лексический анализатор, построенный в ходе выполнения лабораторной работы № 2.

Пример выполнения работы

Задание для примера

Для выполнения лабораторной работы возьмем тот же самый язык, который был использован для выполнения лабораторной работы № 2.

Этот язык может быть задан, например, с помощью следующей КС-грамматики

G({if,then,else,a,=,or,xor,and,(,),},{S,F,E,D,C},P,S) с правилами P:

S → F;

F → if E then T else F | if E then F | a:= E

T → if E then T else T | a:= E

E → E or D | E xor D | D

D → D and C | C

C → a | (E)

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

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

Построение матрицы операторного предшествования

Построение множеств крайних правых и крайних левых символов

Построение множеств крайних левых и крайних правых символов выполним согласно описанному ранее алгоритму.

На первом шаге возьмем все крайние левые и крайние правые символы из правил грамматики G. Получим множества, представленные в табл. 3.2.

Таблица 3.2. Множества крайних левых и крайних правых символов. Шаг 1

Из табл. 3.2 видно, что множества L(U) для символов S, Е, D, а также множества R(U) для символов F, Т, Е, D содержат другие нетерминальные символы, а потому должны быть дополнены. Например, L(S) должно быть дополнено L(F), так как символ F входит в L(S): F е L(S), а R(F) должно быть дополнено R(E), так как символ Е входит в R(F): Е е R(F).

Выполним необходимые дополнения и получим множества, представленные в табл. 3.3.

Таблица 3.3. Множества крайних левых и крайних правых символов. Шаг 2

Практически все множества в табл. 3.3 изменились по сравнению с табл. 3.2 (кроме множеств для символа С), а значит, построение не закончено. Продолжим дополнять множества. Получим множества, представленные в табл. 3.4.

В табл. 3.4 по сравнению с табл. 3.3 изменились множества для символов F, Г и Е – построение не закончено. Продолжим дополнять множества. Получим множества, представленные в табл. 3.5.

Таблица 3.4. Множества крайних левых и крайних правых символов. Шаг 3

Таблица 3.5. Множества крайних левых и крайних правых символов. Шаг 4 (результат)

В табл. 3.5 по сравнению с табл. 3.4 изменились только множества R(U) для символов F иT– построение не закончено. Продолжим дополнять множества. Но если выполнить еще один шаг (шаг 5), то можно убедиться, что множества уже больше не изменятся (чтобы не создавать еще одну лишнюю таблицу, этот шаг здесь выполнять не будем). Таким образом, множества, представленные в табл. 3.5, являются результатом построения множеств крайних левых и крайних правых символов грамматики G.

Построение множеств крайних правых и крайних левых терминальных символов

Построение множеств крайних левых и крайних правых терминальных символов также выполним согласно описанному выше алгоритму.

На первом шаге возьмем все крайние левые и крайние правые терминальные символы из правил грамматики G. Получим множества, представленные в табл. 3.6.

Таблица 3.6. Множества крайних левых и крайних правых терминальных символов. Шаг 1

Дополним множества, представленные в табл. 3.6, на основании ранее построенных множеств крайних левых и крайних правых символов, представленных в табл. 3.5. Например, L_t(Е) должно быть дополнено L_t(D) и L_t(C), так как символы D и C входят в L(E): D, С e L(E), а R_t(F) должно быть дополнено R_t(E), R_t(D) и R_t(C), так как символы E, D и С входят в R(F): E, D, С е R(F).

Получим итоговые множества крайних левых и крайних правых терминальных символов, которые представлены в табл. 3.7.

Таблица 3.7. Множества крайних левых и крайних правых терминальных символов. Результат

Теперь все готово для заполнения матрицы операторного предшествования.

Заполнение матрицы предшествования

Для заполнения матрицы операторного предшествования необходимы множества крайних левых и крайних правых терминальных символов, представленные в табл. 3.7, и правила исходной грамматики G.

Заполнение таблицы рассмотрим на примере лексем or и (.

Символ or не стоит рядом с другими терминальными символами в правилах грамматики. Поэтому знак «=.» («составляет основу») для него не используется. Символ or стоит слева от нетерминального символа D в правиле Е → Е or D. В множество L_t(D) входят символы and, а и (. Поэтому в строке матрицы, помеченной символом or, ставим знак «<.» («предшествует») в клетках на пересечении со столбцами, помеченными символами and, а и (.

Кроме того, символ or стоит справа от нетерминального символа Е в том же правиле Е → Е or D. В множество R_t(E) входят символы or, xor, and, а и). Поэтому в столбце матрицы, помеченном символом or, ставим знак «.>» («следует») в клетках на пересечении со строками, помеченными символами or, xor, and, а и).

Больше ни в каких правилах символ or не встречается, поэтому заполнение матрицы для него закончено.

Символ (стоит рядом с терминальным символом) в правиле С → (Е) (между ними должно быть не более одного нетерминального символа – в данном случае один символ Е). Поэтому в строке матрицы, помеченной символом (, ставим знак «=.» («составляет основу») на пересечении со столбцом, помеченным символом).

Символ (также стоит слева от нетерминального символа Е в том же правиле С → (Е). В множество L_t(E) входят символы or, xor, and, а и (. Поэтому в строке матрицы, помеченной символом (, ставим знак «<.» («предшествует») в клетках на пересечении со столбцами, помеченными символами or, xor, and, а и (.

Больше ни в каких правилах символ (не встречается, поэтому заполнение матрицы для него закончено.

Повторяя описанные выше действия по заполнению матрицы для всех терминальных символов грамматики G, получим матрицу операторного предшествования. Останется только заполнить строку, соответствующую символу «начало строки», и столбец, соответствующий символу «конец строки».

Начальным символом грамматики G является символ S, поэтому для заполнения строки, помеченной ⊥н, возьмем множество L_t(S). В это множество входят символы if, а и;. Поэтому в строке матрицы, помеченной символом ⊥н, ставим знак «<.» («предшествует») в клетках на пересечении со столбцами, помеченными символами if, а и;.

Аналогично, для заполнения столбца, помеченного ⊥_к, возьмем множество 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;

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

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

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

Пример 2

Возьмем входную цепочку «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е содержит структуры данных, которые описывают матрицу операторного предшествования и правила остовной грамматики.

Матрица операторного предшествования (GramMatrix) описана как двумерный массив, каждой строке и каждому столбцу которого соответствует лексема (тип TLexType). Важно, чтобы данные в строках и столбцах матрицы были заполнены в том же порядке, в каком перечислены типы лексем в описании TLexType в модуле LexType. В каждой клетке матрицы находится символ, обозначающий тип отношения предшествования:

• < – для отношения «<.» («предшествует»);

• > – для отношения «.>» («следует»);

• = – для отношения «=.» («составляет основу»);

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

Кроме матрицы операторного предшествования и правил грамматики в модуле SyntRulе описана функция корректировки отношений предшествования CorrectRul е, которая позволяет расширять возможности грамматики операторного предшествования. В данной лабораторной работе эта функция не используется (о технике ее использования можно узнать далее из описания примера выполнения курсовой работы).

В целом описанная в модуле SyntRulе матрица операторного предшествования GramMatrix полностью соответствует построенной матрице операторного предшествования (см. табл. 3.8). Отличие заключается в том, что, поскольку терминальному символу a в грамматике G могут соответствовать два типа лексем входного языка (переменные и константы), в матрице GramMatrix строка и столбец, соответствующие символу a в табл. 3.8, продублированы.

Таким образом, построенный на основе матрицы предшествования из табл. 3.8 синтаксический анализатор не различает константы и переменные. Это соответствует синтаксису заданного входного языка. Для этого языка проводить различие между переменными и константами необходимо только в одном случае: при анализе оператора присваивания (присваивать значение константе нельзя). Для того чтобы компилятор находил такого рода ошибки, возможны два варианта:

1. Изменить синтаксис входного языка (грамматику G) так, чтобы константы и переменные различались в правилах грамматики, и перестроить синтаксический анализатор.

2. Обрабатывать присваивание значений константам на этапе семантического анализа.

В данном случае выбран второй вариант, который реализован в лабораторной работе № 4 (где рассматриваются генерация кода и подготовка к генерации кода). Позже, при разработке компилятора для выполнения курсовой работы, рассмотрен первый вариант (см. главу, посвященную выполнению курсовой работы). Каждый из рассмотренных вариантов имеет свои преимущества и недостатки. В общем случае выбор того, на каком этапе компиляции будет обнаружена та или иная ошибка, зависит от разработчика компилятора.

Правила остовной грамматики G' описаны в виде массива строк GramRules. Каждому правилу в этом массиве соответствует строка, по написанию совпадающая с правой частью правила (пробелы игнорируются). Правила пронумерованы в порядке слева направо и сверху вниз – так, как они были пронумерованы в остовной грамматике G. Для поиска подходящего правила используется метод простого перебора – так как правил мало (всего 13), в данном случае этот метод вполне удовлетворителен.

Кроме двух упомянутых структур данных (GramMatrix и GramRules) в модуле SyntRulе описана также функция MakeSymbolStr, возвращающая наименование нетерминального символа в правилах остовной грамматики. В грамматике G во всех правилах символ обозначен Е, поэтому функция MakeSymbolStr всегда возвращает 'Е' как результат своего выполнения. Но тем не менее эта функция не бессмысленна, так как могут быть другие варианты остовных грамматик.

Модуль структур данных для синтаксического анализа и реализации алгоритма «сдвиг-свертка»

Модуль SyntSymb содержит реализацию алгоритма «сдвиг-свертка» и описания всех структур данных, необходимых для этой реализации. Поскольку сам алгоритм «сдвиг-свертка» не зависит от входного языка, реализующий его модуль также не зависит от входного языка и правил исходной грамматики (они специально вынесены в отдельный модуль).

Основу модуля составляют следующие структуры данных:

• TSymbInfo – описание двух типов символов грамматики: терминальных и нетерминальных;

• TSymbol – описание всех данных, связанных с понятием «символ грамматики»;

• TSymbStack – описание синтаксического стека.

Структура TSymbInfo содержит информацию о типе символа грамматики – поле SymbType, которое может принимать два значения: SYMBLEX (терминальный символ) или SYMBSYNT (нетерминальный символ), и дополнительные данные:

• ссылку на лексему (LexOne) – для терминального символа;

• перечень всех составляющих (LexList) – для нетерминального символа.

Перечень всех составляющих нетерминального символа LexList построен на основе динамического массива (тип TList из библиотеки VCL системы программирования Delphi 5). В него вносятся ссылки на символы, на основании которых создан данный символ, в том порядке, в котором они следуют в правиле грамматики.

Структура TSymbol содержит информацию о символе (поле SymbInfo типа TSymbInfo), а также номер правила грамматики, на основании которого создан символ (поле данных iRuleNum). Для терминальных символов номер правила равен 0, для нетерминальных символов он может быть от 1 до 13.

Кроме этих данных структура содержит методы, необходимые для работы с символами грамматики:

• конструктор CreateLex для создания терминального символа на основе лексемы;

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

• деструктор Destroy для освобождения занятой памяти при удалении символа (при удалении нетерминального символа удаляются все ссылки на его составляющие и динамический массив для их хранения);

• функции, процедуры и свойства для работы с информацией, хранящейся в структуре данных.

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

Третья структура данных TSymbStack построена на основе динамического массива типа TList из библиотеки VCL системы программирования Delphi 5. Она предназначена для того, чтобы моделировать синтаксический стек МП-автомата. В этой структуре нет никаких данных (используются только данные, унаследованные от класса TList), но с ней связаны методы, необходимые для работы синтаксического стека:

• функция очистки стека (Clear) и деструктор для освобождения памяти при удалении стека (Destroy);

• функция доступа к символам в стеке начиная от его вершины (GetSymbol);

• функция для помещения в стек очередной входящей лексемы (Push), при этом лексема преобразуется в терминальный символ;

• функция, возвращающая самую верхнюю лексему в стеке (TopLexem), при этом нетерминальные символы игнорируются;

• функция, выполняющая свертку (MakeTopSymb); новый символ, полученный в результате свертки, помещается на вершину стека.

Кроме трех перечисленных ранее структур данных в модуле SyntSymb описана также функция Bui 1 dSyntList, моделирующая работу алгоритма «сдвиг-свертка» для грамматик операторного предшествования. Входными данными для функции являются список лексем (1 istLex), который должен быть заполнен в результате лексического анализа, и синтаксический стек (symbStack), который в начале выполнения функции должен быть пуст. Результатом функции является:

• нетерминальный символ (ссылающийся на корень синтаксического дерева), если разбор был выполнен успешно;

• терминальный символ, ссылающийся на лексему, где была обнаружена ошибка, если разбор выполнен с ошибками.

Функция BuildSyntList моделирует алгоритм «сдвиг-свертка» для грамматик операторного предшествования так, как он был описан в разделе «Краткие теоретические сведения».