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