- Если считанный символ – одинарная кавычка, то текст, следующий за ней до следующей одинарной кавычки, будет являться строковой константой, а знаки кавычек будут определены как специальные символы.
- Если считанный символ является знаком «{», то сам знак и следующие за ним символы до знака «}» включительно игнорируются, так как являются комментарием.
- Если считанный символ является специальным символом, происходит проверка, является ли данный символ сдвоенным и проверяется второй символ. Если второй символ не образует пару или первый из двух найденных является одинарным, то происходит обработка данного терминального символа, поиск его кода.
После распознавания лексемы происходит заполнение таблиц, соответствующих типу лексемы. Если предполагается, что полученная лексема является терминальным символом, то происходит перебор всех значений таблицы терминальных символов. В случае, когда лексема найдена, необходимо получить ее код и заполнить соответствующим образом таблицу выходных кодов лексем. В случае, когда лексема не найдена предполагается, что лексема является идентификатором. Происходит поиск по таблице символьных имен. В случае, когда в таблице такая лексема уже имеется, происходит заполнение таблицы выходных кодов лексем, иначе лексема включается в таблицу и также заполняется таблица кодов лексем.
При обнаружении литерала, найденная лексема заносится в таблицу, в соответствующем поле заносится ее тип, далее указывается его размер в байтах. Затем заполняется таблица выходных кодов лексем.
В порядке распознавания лексем происходит заполнение таблицы выходных кодов лексем. Если распознанная лексема является терминальным символом, то в ячейку, соответствующую номеру таблицы, заносится номер 1, если является идентификатором – номер 2, если литералом – 3. Спецификатор («код» для терминального символа) заносится в поле «Строка».
Далее происходит пошаговое сравнение значений, полученных программой, со значениями внесенными студентом. Сравнение происходит по таблице выходных кодов лексем. При каждом несоответствии генерируется сообщение в окне сообщений, что в такой-то позиции не верно заполнено значение номера таблицы, кода элемента, спецификатора.
Имеется возможность получения листинга в отдельный файл с расширением LOG.
Кроме того, необходимо сохранить файл для работы на следующем этапе синтаксического анализа.
Цель создания программы SINAN состоит в том, чтобы научить студента проверять правильность грамматики программы с помощью синтаксических деревьев (деревьев грамматического разбора).
Программа SINAN сама производит разбор программы, строит синтаксическое дерево и проверяет введенные пользователем данные на корректность, сообщая обо всех найденных ошибках и несоответствиях.
Существует два пути анализа: восходящий и нисходящий, данный проект реализован с помощью нисходящего, он называется рекурсивный спуск. В проекте грамматический разбор реализован с помощью правил БНФ грамматики, заданных в таблице переходов.
В таблице переходов с помощью специальных кодов реализованы ссылки, переходы, обозначения терминальных символов, идентификаторов и литералов, см. таблицу 10. Нетерминальные символы представляют собой ссылки на конструкции, терминальные – указатели на код элемента соответствующей таблицы, идентификаторы и литералы представляют собой соответствующие обозначения. Для решения проблемы выбора одного из нескольких вариантов введен элемент ИЛИ, позволяющий реализовать все возможные варианты ветвления. Для реализации стека в каждой строке предусмотрена ячейка возврата, в которой указывается адрес, куда следует перейти после отработки соответствующей конструкции.
На основе данной таблицы производится анализ кодов лексем и создается новая формируемая таблица переходов, по которой в дальнейшем строится синтаксическое дерево.
Таблица переходов полностью основана на БНФ грамматике, показанной на рис. 4. Эта таблица предназначена для реализации синтаксического разбора с помощью метода рекурсивного спуска. С помощью нее можно определить законченность выражений, отследить грамматику учебного языка. Она служит основной базой при написании программы, хотя ее можно использовать и для построения формируемой таблицы переходов вручную.
На основе этой таблицы формируется другая (которую при необходимости легко можно преобразовать в дерево грамматического разбора), конечная таблица представляет собой программу, разобранную по грамматикам (на грамматики), представленную переходами (ссылками) и адресами таблиц и спецификаторов (№-в строк) на хранящиеся в них данные.
Работа с данной таблицей не оптимальна по скорости, т.к. при работе не используется стек, зато данное представление более наглядно.
Таблица 10 – Таблица переходов
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 1 | <prog> | PROGRAM| 1,4$1 |@1,4 | <prog-name>~2 | VAR| 1,6$2 | @1,6 | <dec-list>~3 | BEGIN$3 | <stmt-list>~7 | END$4 | .$30 |
| 2 | <prog-name> | +id | ;$27 | ||||||
| 3 | <dec-list> | <dec>~4 | ;$27 | <dec>| ~4 | @3,1 | ;$27 | @3,4 | |||
| 4 | <dec> | <id-list>~6 | :$31 | <type>~5 | |||||
| 5 | <type> | INTEGER| REAL | STRING $5 | $6 | $7 | |||||||
| 6 | <+id-list> | +id | , | $29| @6,1 | +id | @6,3 | ||||
| 7 | <stmt-list> | <stmt> | ~8 | @7,1 | ; | $27| @7,1 | @7,2 | |||||
| 8 | <stmt> | <assign>|<for>|<read>|<write>|<for>|<while>|<repeat>| <if> ~9 | ~15 | ~13 | ~14 | ~15 | ~24 | ~25 | ~21 | |||||||
| 9 | <assign> | +id | :=$28 | <exp>~10 | |||||
| 10 | <exp> | - | + | $33 | $32 | @10,3 | <term>~11 | + | - | $32| $33| @10,1 | <term>~11 | @10,4 | |||
| 11 | <term> | <factor>~12 | * | DIV | / |$34| $17 | $37|11,1 | <factor>~12 | 11,3 | ||||
| 12 | <factor> | +id | ^int | ^real | ^string |@12,4 | ($35| @12,1 | <exp>~10 | )$36 | ||||
| 13 | <read> | READ$19 | ($35 | <id-list> ~6 | )$36 | ||||
| 14 | <write> | WRITE$18 | ($35 | <VALUE> ~18 | , | 14,9$29| @14,9 | <VALUE>~18 | @14,5 | )$36 | |
| 15 | <for> | FOR$8 | <index-exp>~16 | DO$10 | <body>~17 | ||||
| 16 | <index-exp> | +id | :=$28 | <exp>~10 | TO|DOWNTO $9 | $20 | <exp>~10 | |||
| 17 | <body> | <stmt>| 17,4 ~8 | @17,4 | BEGIN$3 | <stmt-list> | END$4 | ; | $27| @17,1 | |||
| 18 | <value> | <id-list>| <text-val> ~6 | ~19 | |||||||
Продолжение таблицы 10
| 19 | <text-val> | ′$38 | <text>~20 | ′$38 | |||
| 20 | <text> | ^string | |||||
| 21 | <if> | IF $14 | <сравнение>~22 | THEN$15 | <body>~17 | ELSE | $16 | @21,1 | <body>~17 |
| 22 | <сравнение> | <factor>~12 | <условие>~23 | <factor>~12 | |||
| 23 | <условие> | < | > | = | >= | <=| <>$39|$40|$41|$42|$43|$44 | |||||
| 24 | <while> | WHILE~13 | <сравнение>~22 | DO$10 | <body>~17 | ||
| 25 | <repeat> | REPEAT$11 | <body>~17 | UNTIL$12 | <сравнение>~22 |
Ячейкой возврата является первая ячейка каждой строки, ее описание: 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;