Транслятор языка высокого уровня

6)  Операторы отделяются друг от друга знаком конца строки.

3 Синтаксический анализатор транслятора

            3.1 Формальная грамматика языка

Для построения управляющей таблицы МПА необходимо нахождение множества ВЫБОР. Исходной для множества выбора является следующая грамматика:

[P]~[Z][D][B]

[Z]~program[I]

[D]~var[I][L-V]:[TP]

[L-V]~,[L-V]

[L-V]~$

[TP]~real

[I]~i

[B]~begin[L-S]end

[L-S]~repeat[L-S]until[SRAV][L-S]

[L-S]~[S][L-S]

[L-S]~write(i)[L-S]

[L-S]~read(i)[L-S]

[L-S]~$

[S]~[I]=[G]

[G]~[T][E-C]

[E-C]~+[T][E-C]

[E-C]~$

[T]~[F][T-C]

[T-C]~*[F][T-C]

[T-C]~$

[F]~([G])

[F]~i

[SRAV]~[FT][ZNAK][FT]

[ZNAK]~>

[ZNAK]~<

[ZNAK]~=

[FT]~[I]

             3.2 Нахождение множества ВЫБОР

ШАГ 1  процедуры  определяет  аннулирующие  нетерминалы  и  правила.

5. [L-V] → $

13. [L-S] → $

17.[E-C] → $

20.[T-C] → $

ШАГ 2  процедуры  состоит  в  нахождении отношения,  называемого  НАЧИНАЕТСЯ  ПРЯМО  С (НПС).

Эти отношения определяются на множестве символов грамматики и означают, что если, применив к нетерминалу <A> точно одно правило и, возможно, заменив в нем некоторые аннулирующие нетерминалы на $, можно получить цепочку, начинающуюся, например с <B>. В этом случае пишут <A>НПС<B>.

На рисунке 2 показан фрагмент полученных отношений.

ШАГ 3  процедуры - это вычисление отношения  НАЧИНАЕТСЯ С (НС).

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

Формальный алгоритм транзитивного замыкания включает в себя следующие шаги:

1)     для каждого единичного элемента aij исходной матрицы в строку i  дописать единичные элементы из строки j;

п.1 повторять сверху вниз и слева направо для всех элементов матрицы.

На рисунке 3 показан фрагмент полученного отношения.

Рисунок 2

ШАГ 4  вычисляет  множество  ПЕРВЫЙ.

Для  каждой  строки  матрицы  отношения  НС  отмеченные  столбцы,  соответствующие  терминальным  символам,  указывают  терминалы,  составляющие  множество  ПЕРВЫЙ  для  символа,  которым  помечена  данная  строка .  Так,  в  нашем  примере:

ПЕРВЫЙ ([P])={ program}

ПЕРВЫЙ ([Z])={ program }

ПЕРВЫЙ ([D])={ var } и.т.д.

ШАГ 5  -  вычисление  множества  ПЕРВЫЙ  для  правой  части  каждого  правила.  Имея  информацию,  полученную  на  шаге 4,  эти  вычисления  проделать  очень  просто.

ПЕРВЫЙ (1)={ program}

ПЕРВЫЙ (2)={ program }

ПЕРВЫЙ (3)={ var } и.т.д.

Рисунок 3

ШАГ 6   -  это  построение  отношения,  нызываемого  ПРЯМО - ПЕРЕД (ПП):

Эти отношения определяются следующим образом: мы пишем А ПП В тогда и только тогда, когда существуют правила вида:     <D> → <A> <B> ,

<D> → <A> β <B> , где <А>, <В> - НТ символы, β - аннулирующая цепочка.

На рисунке 4 показан фрагмент полученного отношения.

ШАГ 7 -  это  построение  отношения  ПРЯМО-НА-КОНЦЕ (ПНК).

Отношение определяется следующим образом: если <А> и <В> символы грамматики, то   <А> ПНК <В> тогда и только тогда, когда  есть правила вида <B> →α <A>, <B> →α <A> β, где β - аннулирующая цепочка, α - произвольная цепочка. Это отношение является инверсией отношения НПС, если правую часть правила рассматривать "справа - налево".

На рисунке 5 показан фрагмент полученного отношения.

Рисунок 4

Рисунок 5

ШАГ 8 - построение отношения НА-КОНЦЕ (НК).

Отношение  НК  -  это  рефлексивно-транзитивное  замыкание  отношения  ПНК.

На рисунке 6 показан фрагмент полученных отношений.

Рисунок 6

ШАГ  9  -  это  вычисление  отношения,  называемого  ПЕРЕД (П):

Мы пишем <А> П <В> тогда и только тогда, когда из начального символа можно вывести цепочку, в которой за вхождением <А> сразу же следует вхождение <В>. Можно записать без вывода, что отношение П является произведением отношений НК, ПП и НС. Это отношение также соответствует тем символам, которые находятся НА КОНЦЕ начального нетерминала для всех выводимых из него цепочек.

ШАГ 10 заключается  в расширении отношение ПЕРЕД (П+) за счет включения в него концевого маркера (последний столбец)

Это отношение соответствует тем терминальным символам, которые находятся НА КОНЦЕ начального нетерминала для всех выводимых из него цепочек (первый столбец матрицы НК).

На рисунке 7 показан фрагмент полученных отношений для шагов 9 и 10.

Рисунок 7

ШАГ 11 -  это  вычисление  множества  СЛЕД для  каждого  аннулирующего  нетерминала. Множество СЛЕД будет содержать все терминальные символы, для которых аннулирующие нетерминалы расположены ПЕРЕД.

ШАГ 12 -  вычисление  множеств  ВЫБОР,  которые  можно  получить  из  уже  вычисленных  значений  множеств  ПЕРВЫЙ  и  СЛЕД.

На рисунке 8 показан фрагмент множества ВЫБОР, из которого  видно,  что  множества  выбора  правил,  имеющих  одинаковые левые части,  не  пересекаются. Грамматика,  порождающая  рассматриваемый  язык,  является  LL(1)-грамматикой  и  для  неё  можно  построить   МП-распознаватель.

Управляющая таблица МПА представлена на рисунке 9, а правила его  работы на рисунке 10.

Работа синтаксического блока:

1.   Начальное состояние  магазина -  нетерминал <P>.

2.   Автомат считывает очередную лексему и верхний символ из магазина.

3.   Автомат обращается к управляющей таблице по двум значениям и получает управляющее правило — выход таблицы.

4.   Автомат действует согласно управляющему правилу.

Рисунок 8

Рисунок 9

Рисунок 10

4 Описание программы

            4.1 Общие сведения

Весь программный продукт  хранится в виде файлa “Progect.exe”. К нему прилагаются файлы с программами (*.txt), грамматиками (*.gra).

В программу встроен редактор для написания и редактирования программ и грамматик. Для обеспечения нормального функционирования программы необходима операционная система Windows 95 и выше.

Программа создана с учетом современных требований к интерфейсу и интерактивным программным продуктам.

    4.2 Работа с программой

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

Порядок работы  программы.

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

Рисунок 11

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

С помощью меню «файл» можно открывать/создавать/сохранять файлы программ, а также открывать базу анализатора и выходить из программы.

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

Рисунок 12

После открытия файла базы анализатора и написания текста программы можно нажать кнопку «Стек» для просмотра стека, после чего необходимо в меню «Обработка» выбрать либо пошаговое выполнение (F8), либо запуск (F9). В поле порядка выполнения программы можно будет увидеть сообщение об успешной или ошибочной обработке (рисунок 12).

Заключение

Разработанная программа реализует лексический и синтаксический анализаторы транслятора в соответствии с выданным заданием. Ее достоинствами являются: удобный интерфейс и наглядность работы. Программа используется при изучении формальных грамматик и трансляторов в учебном процессе.