Лабораторний практикум побудови синтаксичних аналізаторів

Граматика мови програмування визначається множиною БНФ-правил, що записані в текстовому файлі. Кожне провило обов'язково починається з першої позиції рядка. Для зручності правило можна продовжити в наступних рядках, але не з першої позиції. Нетермінал граматики - це ланцюжок літер, який починається з символу < та закінчується символом >, наприклад <програма>. Термінальні ланцюжки записуються традиційно, наприклад, begin. Альтернативи правила для зручності позначаються символом! в першій позиції рядка, при цьому ліва частина правила опускається. Оскільки символи <, > та! є метасимволами при визначенні граматики, то для їх запису в термінальних ланцюжках використовується ще один метасимвол, а саме \. Правило граматики в текстовому файлі записується так:

<програма> program (<список параметрів>) <блок>.

В пам'яті ЕОМ граматика описується наступними структурами:

struct node { int *pd; // посилка на продукцію

int len; // довжина продукції

int teg; // робоче поле

struct node *next; // посилка на наступну продукцію

struct fdata *cont_llk; // посилка на контекст для правила

};

Поле "довжина продукції" визначає кількість елементів продукції включаючи перший. Елементи продукції (нетермінали та термінали) закодовані цілочисловими даними, таким чином, що:

4 біт 12 біт

Дане типу int

Порядковий номер

Код лексеми: 0ХF - нетермінал, 0Х0 - термінал

Для зберігання словарних множин First k та Follow k використовується наступна інформаційна структура:

struct fdata { struct fdata *fnext; // посилка на наступний блок слів

struct fdata *fnext1; // системне поле - не модифікувати

int rdata[60]; // поле для слів

};

Кожне слово - це послідовність лексем довжиною не більше k елементів. Якщо одного блоку для зберігання відповідної множини слів даних не достатньо, то в подальшому пам'ять виділяється динамічно. Признак кінця послідовності слів в одному блоці - (-1). Оскільки слова, які зберігаються в словарному блоці мають різну довжину, то на початку кожного слова стоїть його довжина.

Для доступу до закодованих в пам'яті ЕОМ даних надається ряд інтерфейсних функцій, наприклад:

по коду лексеми отримати її текст:

char * NAME_ELEM(int);

визначити кількість слів в словарній множині:

int calc_word(struct fdata p);

отримати слово з індексом i (індексація починається з нуля) з словарної множини:

int * get_word(struct fdata p, int i);

Решта інтерфейсних функцій описані у файлі mystand.h.

Для виконання лабораторної роботи користувачеві надаються наступні бази даних:

extern struct fdata **ref_FIRST; // масив посилок на множини

extern struct fdata **ref_FOLLOW; // масив посилок на множини

extern struct flang **ref_LOCAL; // масив посилок на множини

extern int LLk_LEN; // довжина llk-контексту

extern int *epsilon, num_epsilon; // список epsilon-нетеpміналів

extern int *netname, numnet; // список нетерміналів граматики

extern int *terminal, numtrm; // список терміналів граматики

extern struct node *q_grammat; // початок списку правил граматики

extern int LL1_USL; // відповідає за LL(1) - умову

extern char *TABL_LL1_UPR; // таблиця управління LL(1) - аналізатора

Число рядків таблиці TABL_LL1_UPR рівне numnet, а число стовпчиків - numtrm+1. Останній стовпчик таблиці відповідає ерсилон-слову.

Відмітимо, що довжина масивів ref_FIRST, ref_FOLLOW та ref_LOCAL - це кількість нетерміналів граматики, а i- й елемент кожної множини асоціюється з i- м елементом списку нетерміналів.