При обнаружении литерала, найденная лексема заносится в таблицу, в соответствующем поле заносится ее тип, далее указывается его размер в байтах. Затем заполняется таблица выходных кодов лексем.
В порядке распознавания лексем происходит заполнение таблицы выходных кодов лексем. Если распознанная лексема является терминальным символом, то в ячейку, соответствующую номеру таблицы, заносится номер 1, если является идентификатором – номер 2, если литералом – 3. Спецификатор («код» для терминального символа) заносится в поле «Строка».
Далее происходит пошаговое сравнение значений, полученных программой, со значениями внесенными студентом. Сравнение происходит по таблице выходных кодов лексем. При каждом несоответствии генерируется сообщение в окне сообщений, что в такой-то позиции не верно заполнено значение номера таблицы, кода элемента, спецификатора.
Имеется возможность получения листинга в отдельный файл с расширением LOG.
Кроме того, необходимо сохранить файл для работы на следующем этапе синтаксического анализа.
Цель создания программы SINAN состоит в том, чтобы научить студента проверять правильность грамматики программы с помощью синтаксических деревьев (деревьев грамматического разбора).
Программа SINAN сама производит разбор программы, строит синтаксическое дерево и проверяет введенные пользователем данные на корректность, сообщая обо всех найденных ошибках и несоответствиях.
Существует два пути анализа: восходящий и нисходящий, данный проект реализован с помощью нисходящего, он называется рекурсивный спуск. В проекте грамматический разбор реализован с помощью правил БНФ грамматики, заданных в таблице переходов.
В таблице переходов с помощью специальных кодов реализованы ссылки, переходы, обозначения терминальных символов, идентификаторов и литералов, см. таблицу 10. Нетерминальные символы представляют собой ссылки на конструкции, терминальные – указатели на код элемента соответствующей таблицы, идентификаторы и литералы представляют собой соответствующие обозначения. Для решения проблемы выбора одного из нескольких вариантов введен элемент ИЛИ, позволяющий реализовать все возможные варианты ветвления. Для реализации стека в каждой строке предусмотрена ячейка возврата, в которой указывается адрес, куда следует перейти после отработки соответствующей конструкции.
На основе данной таблицы производится анализ кодов лексем и создается новая формируемая таблица переходов, по которой в дальнейшем строится синтаксическое дерево.
Таблица переходов полностью основана на БНФ грамматике, показанной на рис. 4. Эта таблица предназначена для реализации синтаксического разбора с помощью метода рекурсивного спуска. С помощью нее можно определить законченность выражений, отследить грамматику учебного языка. Она служит основной базой при написании программы, хотя ее можно использовать и для построения формируемой таблицы переходов вручную.
На основе этой таблицы формируется другая (которую при необходимости легко можно преобразовать в дерево грамматического разбора), конечная таблица представляет собой программу, разобранную по грамматикам (на грамматики), представленную переходами (ссылками) и адресами таблиц и спецификаторов (№-в строк) на хранящиеся в них данные.
Работа с данной таблицей не оптимальна по скорости, т.к. при работе не используется стек, зато данное представление более наглядно.
Ячейкой возврата является первая ячейка каждой строки, ее описание: X,1, где Х – строка, 1 – столбец.
~x – переход на строку с номером х, столбец №2, формирование адреса возврата в первой ячейке, если переход был осуществлен от одного из параметров условий ИЛИ, то формирование адреса возврата и адреса перехода при ошибке (отрицательном результате).
| – элемент ИЛИ, предпочтение отдается более левому элементу. Перебором сравнивается каждый элемент, и если не один не подошел, то ошибка.
$x – в таблице переходов – номер строки в таблице терминальных символов
$x,y – в формируемой таблице переходов – одна из трех таблиц (x=1 – терминальных символов, x=2 –идентификаторов, x=3 – литер);
+id – таблица идентификаторов (№2) в таблице переходов.
Элементы, начинающиеся со знака ^ (int, real, string) в таблице переходов являются элементами таблицы литералов (№3).
@x,y,z – переход в строку x, столбец y, параметр z
@x,y,z%a,b,c – переход в строку x, столбец y, параметр z (при наличии элемента ИЛИ), при наличии ошибки в a,b,c (указывается только в ячейках возврата, формируется только при присутствии элемента ИЛИ)
Переход по ошибке (значение после знака % в ячейке возврата) действует только для ячеек столбца №2.
Алгоритмы:
Используются таблицы Table_Perehod[i,j], Table_Perehod1[i1,j1]
Table_Perehod –основная таблица перехода
Table_Perehod1 – формируемая таблица перехода
[i,j] – адреса ячеек внутри Table_Perehod, i – столбцы, j – строки
[i1,j1] – адреса ячеек внутри Table_Perehod1, i1 – столбцы, j1 – строки
count_vs – счетчик перемещения, показывающий текущее положение в таблице выходных символов (Tabl_vs);
pos – номер позиции в ячейке (при наличии элемента ИЛИ).
Таблица №1 – таблица терминальных символов.
Таблица №2 – таблица символических имен (идентификаторов).
Таблица №3 – таблица литералов.
Просмотр осуществляется слева направо, и по переходам. Каждый раз происходит сравнение с текущим элементом из таблицы выходных символов.
При положительном результате сравнения (терминальных символов, идентификаторов, литер), осуществляется переход на более правую ячейку.
При отрицательном результате (err=1), обработка происходит в следующей последовательности:
1) если в ячейке возврата текущей строки нет знака %, то err:=0;
2) если параметр единственный (нет ИЛИ элемента) или это последний элемент последовательности ИЛИ, и в ячейке возврата текущей строки нет знака %, то генерировать ошибку «Должен быть элемент % в позиции %%», где % либо терминальный символ (или его код), либо “идентификатор”, либо “литера”; %% – позиция в таблице выходных символов;
3) при наличии нескольких параметров (разделенных элементом ИЛИ) и если текущий не последний из них, то перейти на следующий параметр, более правый, значение переменной err присвоить значение 0;
4) если номер столбца текущей ячейки – 2, то если в ячейке возврата есть знак %, то перейти по адресу, указанному за знаком % и:
- в таблице переходов очистить ячейку возврата,
- в формируемой таблице переходов удалить последнюю строку.
Если ячейка пуста, то осуществляется переход на первую ячейку текущей строки, i:=1.
Если значение в ячейке типа x,y или x,y,z, то необходимо перейти на строку х, ячейку y, позицию z. При этом: после перехода в указанную ячейку на указанную позицию ячейка с адресом перехода, если она является ячейкой возврата, очищается (Table_Perehod[i,j]:=’’; i:=y; j:=x; pos:=z), в формируемой таблице переходов происходит переход в ячейку, указанную в первой ячейке строки без очищения ее значения (i1:=y; j1:=x).
Если значение в ячейке типа x,y%a,b,c, при этом err=1 и номер столбца равен 2 (i=2), то следует перейти по ссылке a,b,c, очистить ячейку возврата таблицы переходов (Table_Perehod[i,j]:=’’; i:=b; j:=a; pos:=c), в формируемой таблице переходов перейти по адресу возврата и удалить последнюю строку (i1:=y; j1:=x).
Если значение в ячейке типа x,y%a,b,c, и err=0, то перейти по ссылке x,y, в формируемой таблице переходов перейти по адресу, указанному в текущей ячейке.
Если номер столбца текущей ячейки = 3 и err<>0, то в ячейке возврата удалить при наличии знак % и значения за ним.
Если первый символ
^ – значение в ячейке является литерой (таблица литералов – №3). Осуществляемая при этом проверка: если в таблице выходных символов № текущей таблицы равен 3 (if Tabl_vs[count_vs,2]=’3’), то занести в текущую ячейку формируемой таблицы № таблицы (3) и № строки в ней (Table_Perehod1[i1,j1]:=$3,№строки), перейти на следующую ячейку (i:=i+1; i1:=i1+1; count_vs:=count_vs+1). В случае отрицательного результата сравнения переменной err присваивается значение 1.
Если первый символ $ – значение в ячейке является терминальным символом (таблица терминальных символов – №1). Осуществляемая проверка: если в таблице выходных символов № текущей таблицы равен 1 (if Tabl_vs[count_vs,2]=’1’), то занести в текущую ячейку формируемой таблицы № таблицы (1) и № строки в ней (Table_Perehod1[i1,j1]:=$1,код), перейти на следующую ячейку (i:=i+1; i1:=i1+1; count_vs:=count_vs+1). В случае отрицательного результата сравнения переменной err присваивается значение 1.
Если первый символ
~ – это переход на вторую ячейку строки с номером, указанным за символом
~, в формируемой таблице переходов добавляется новая строка и переход осуществляется на нее. При этом осуществляется следующее: в первую ячейку (ячейку возврата) указанной строки заносится адрес возврата: если переход осуществляется с одной из позиций с элементом ИЛИ и не является последним в списке, то в ячейке возврата формируется код возврата типа x,y,z, где x – номер строки, y – номер столбца, z – номер позиции откуда был произведен переход (x:=j; y:=i; z:=pos; j:=a; i:=2, где а номер строки в адресе перехода – ~a), тоже происходит и в формируемой таблицей переходов (x:=j1; y:=i1; j1:=№последней строки; i1:=2).
Коды терминальных символов показаны в таблице 11.
Таблица 11 – Таблица кодов терминальных символов
Код | Терминальный символ | Комментарий | | |
1 | PROGRAM | объявление программу | | |
2 | VAR | объявление переменных | | |
3 | BEGIN | начало тела | | |
4 | END | конец тела | | |
5 | INTEGER | тип целое | | |
6 | REAL | вещественный тип | | |
7 | STRING | строковый тип | | |
8 | FOR | цикл с параметром – ДЛЯ | | |
9 | TO | цикл с параметром – ДО | | |
10 | DO | ВЫПОЛНИТЬ | | |
11 | REPEAT | цикл с постусловием – ПОВТОРЯТЬ | | |
12 | UNTIL | цикл с постусловием – ПОКА НЕ | | |
13 | WHILE | цикл с предусловием – ПОКА | | |
14 | IF | условный оператор – ЕСЛИ | | |
15 | THEN | условный оператор – ТО | | |
16 | ELSE | условный оператор – ИНАЧЕ | | |
17 | DIV | делить на цело | | |
18 | WRITE | вывести на консоль | | |
19 | READ | считать с консоли | | |
20 | DOWNTO | цикл с параметром – ДО | | |
21 | FUNCTION | функция | | |
22 | PROCEDURE | процедура | | |
23 | { | начало комментария | | |
24 | } | конец комментария | | |
25 | [ | открытие квадратных скобок | | |
26 | ] | закрытие квадратных скобок | | |
27 | ; | конец операции | | |
28 | := | присвоить значение | | |
29 | , | разделитель | | |
30 | . | конец программы/отделение дробной части | | |
31 | : | разделение идентификатора от его типа | | |
32 | + | оператор сложения | | |
33 | - | оператор вычитания | | |
34 | * | оператор умножения | | |
35 | ( | открывающаяся скобка | | |
36 | ) | закрывающаяся скобка | | |
37 | / | оператор деления | | |
38 | ΄ | кавычка | | |
39 | < | меньше | | |
40 | > | больше | | |
41 | = | равно | | |
42 | >= | больше или равно | | |
43 | <= | меньше или равно | | |
44 | <> | не равно | | |