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 (ifTabl_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 (ifTabl_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 | <> | не равно |
Таблица представляет собой набор ячеек. Столбцы и строки нумеруются. Столбцы определяют номер распознанной лексемы (элемента конструкции), строки определяют номер полученной конструкции.
В таблице могут существовать только два вида данных: указатели на таблицы и переходы.
Указатели на таблицы состоят из символа признака ссылки на таблицу «$», номера таблицы и, через запятую, кода (для терминального символа) или спецификатора. Номера таблиц: 1– таблица терминальных символов, 2 – таблица символических имен, 3 – таблица литералов.
Указатели на ячейки состоят из символа «@» и следующих за ним через запятую адресов столбца и строки, куда следует перейти, оказавшись в данной ячейке.
Все ячейки первого столбца зарезервированы для значений ссылок обратного перехода на ячейку, следующую за вызвавшей переход в данную строку и называются ячейками возврата.
Чтобы заполнить формируемую таблицу переходов необходимо знать следующие правила.
Таблица заполняется в точности по БНФ, показанной на рисунке 4, при этом строки таблицы являются элементами конструкций данной грамматики. Разбор делается по данным, полученным из таблиц терминальных символов, символических имен, литералов, выходных кодов лексем.
1) Заполнение таблицы начинается с левой верхней ячейки, каждый раз смещаясь на следующую, более правую.
2) При наличии вложенности конструкции (найден нетерминальный символ) создается (заполняется) новая строка, где в первой ячейке указывается адрес возврата: указатель перехода «@», номер строки, номер столбца, откуда осуществлен переход плюс один (т.е. переход на следующую ячейку за той, из которой был произведен вызов).
3) При наличии нескольких элементов, разделенных знаком «|», осуществляется перебор вариантов, которые подходят значениям, указанным в таблице выходных кодов.
4) При соответствии значения ячейки или одного из элементов ИЛИ терминальному символу указывается признак ссылки на таблицу «$», затем номер таблицы – 1 и код элемента в таблице терминальных символов (номер таблицы и код берется из таблицы кодов лексем).
5) При соответствии значения ячейки или одного из элементов ИЛИ идентификатору указывается признак ссылки на таблицу «$», затем номер таблицы – 2 и спецификатор (номер таблицы и спецификатор берется из таблицы кодов лексем).
6) При соответствии значения ячейки или одного из элементов ИЛИ литералу указывается признак ссылки на таблицу «$», затем номер таблицы – 3 и спецификатор (номер таблицы и спецификатор также берется из таблицы кодов лексем).
7) Подчеркнутые элементы в БНФ грамматике не обязательны (они могут отсутствовать).
Разбор делается по данным, полученным от БНФ грамматик, из таблиц терминальных символов, выходных кодов лексем.
Заполнение формируемой таблицы переходов начинается со второй ячейки первой строки.
Для терминальных символов алгоритм может выглядеть таким образом.
Допустим, производится анализ первого элемента таблицы кодов лексем.
1) Номер позиции в таблице кодов лексем равен 1. Производится чтение данных из первого столбца таблицы кодов лексем. Полученное значение номера таблицы – 1 (таблица терминальных символов), код равен 1 (по таблице кодов – «объявление программы»).
2) Рассматривается первый элемент БНФ грамматики, им является ключевое слово PROGRAM, оно принадлежит таблице терминальных символов – 1, по таблице кодов определяется код, он равен 1.
3) Производится сравнение номеров таблиц, полученных на этапе 1 и этапе 2. Значения совпали.
4) Производится сравнение кодов таблиц. Значения совпали.
5) Во вторую ячейку первой строки формируемой таблицы переходов заносится указатель на таблицу 1, код 1 – «$1,1».
6) Номер позиции в таблице кодов лексем увеличивается на 1 (стает равным 2).
7) В грамматике БНФ начинает рассматриваться следующий элемент конструкции – нетерминальный символ <prog-name>.
8) Новое значение в формируемую таблицу переходов будет заноситься в правую ячейку от текущей (номер столбца увеличился на 1).
При несовпадении значений на этапах 3 и 4 происходит прекращение разбора, если только терминальный символ не является элементов массива ИЛИ – «|» (например <type> ::= INTEGER | REAL | STRING) или не является необязательным элементом конструкции (например, PROGRAM <prog-name>), тогда осуществляется переход на следующий элемент массива ИЛИ или переход к следующему элементу конструкции не входящему в данную группу необязательных элементов (подчеркиваются одной общей линией).