Программно-методический комплекс для обучения процессу создания компиляторов

Продолжение таблицы 10

2.4.2 Правила работы с таблицей переходов

Ячейкой возврата является первая ячейка каждой строки, ее описание: 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), обработка происходит в следующей последовательности:

если в ячейке возврата текущей строки нет знака %, то err:=0;

если параметр единственный (нет ИЛИ элемента) или это последний элемент последовательности ИЛИ, и в ячейке возврата текущей строки нет знака %, то генерировать ошибку «Должен быть элемент % в позиции %%», где % либо терминальный символ (или его код), либо “идентификатор”, либо “литера”; %% - позиция в таблице выходных символов;

при наличии нескольких параметров (разделенных элементом ИЛИ) и если текущий не последний из них, то перейти на следующий параметр, более правый, значение переменной err присвоить значение 0;

если номер столбца текущей ячейки - 2, то если в ячейке возврата есть знак %, то перейти по адресу, указанному за знаком % и:

в таблице переходов очистить ячейку возврата,

в формируемой таблице переходов удалить последнюю строку.

2.4.3 Правила таблицы переходов для написания программы

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

2.4.4 Формируемая таблица переходов. Правила заполнения

Таблица представляет собой набор ячеек. Столбцы и строки нумеруются. Столбцы определяют номер распознанной лексемы (элемента конструкции), строки определяют номер полученной конструкции.

В таблице могут существовать только два вида данных: указатели на таблицы и переходы.

Указатели на таблицы состоят из символа признака ссылки на таблицу «$», номера таблицы и, через запятую, кода (для терминального символа) или спецификатора. Номера таблиц: 1- таблица терминальных символов, 2 - таблица символических имен, 3 - таблица литералов.

Указатели на ячейки состоят из символа «@» и следующих за ним через запятую адресов столбца и строки, куда следует перейти, оказавшись в данной ячейке.

Все ячейки первого столбца зарезервированы для значений ссылок обратного перехода на ячейку, следующую за вызвавшей переход в данную строку и называются ячейками возврата.

Чтобы заполнить формируемую таблицу переходов необходимо знать следующие правила.

Таблица заполняется в точности по БНФ, показанной на рисунке 4, при этом строки таблицы являются элементами конструкций данной грамматики. Разбор делается по данным, полученным из таблиц терминальных символов, символических имен, литералов, выходных кодов лексем.

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

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

При наличии нескольких элементов, разделенных знаком «|», осуществляется перебор вариантов, которые подходят значениям, указанным в таблице выходных кодов.

При соответствии значения ячейки или одного из элементов ИЛИ терминальному символу указывается признак ссылки на таблицу «$», затем номер таблицы - 1 и код элемента в таблице терминальных символов (номер таблицы и код берется из таблицы кодов лексем).

При соответствии значения ячейки или одного из элементов ИЛИ идентификатору указывается признак ссылки на таблицу «$», затем номер таблицы - 2 и спецификатор (номер таблицы и спецификатор берется из таблицы кодов лексем).

При соответствии значения ячейки или одного из элементов ИЛИ литералу указывается признак ссылки на таблицу «$», затем номер таблицы - 3 и спецификатор (номер таблицы и спецификатор также берется из таблицы кодов лексем).

Подчеркнутые элементы в БНФ грамматике не обязательны (они могут отсутствовать).

2.4.5 Правила заполнения формируемой таблицы переходов

Разбор делается по данным, полученным от БНФ грамматик, из таблиц терминальных символов, выходных кодов лексем.

Заполнение формируемой таблицы переходов начинается со второй ячейки первой строки.

Для терминальных символов алгоритм может выглядеть таким образом.

Допустим, производится анализ первого элемента таблицы кодов лексем.

Номер позиции в таблице кодов лексем равен 1. Производится чтение данных из первого столбца таблицы кодов лексем. Полученное значение номера таблицы - 1 (таблица терминальных символов), код равен 1 (по таблице кодов - «объявление программы»).

Рассматривается первый элемент БНФ грамматики, им является ключевое слово PROGRAM, оно принадлежит таблице терминальных символов - 1, по таблице кодов определяется код, он равен 1.

Производится сравнение номеров таблиц, полученных на этапе 1 и этапе 2. Значения совпали.

Производится сравнение кодов таблиц. Значения совпали.

Во вторую ячейку первой строки формируемой таблицы переходов заносится указатель на таблицу 1, код 1 - «$1,1».

Номер позиции в таблице кодов лексем увеличивается на 1 (стает равным 2).

В грамматике БНФ начинает рассматриваться следующий элемент конструкции - нетерминальный символ <prog-name>.

Новое значение в формируемую таблицу переходов будет заноситься в правую ячейку от текущей (номер столбца увеличился на 1).

При несовпадении значений на этапах 3 и 4 происходит прекращение разбора, если только терминальный символ не является элементов массива ИЛИ - «|» (например <type> ::= INTEGER | REAL | STRING) или не является необязательным элементом конструкции (например, PROGRAM <prog-name>), тогда осуществляется переход на следующий элемент массива ИЛИ или переход к следующему элементу конструкции не входящему в данную группу необязательных элементов (подчеркиваются одной общей линией).

Для нетерминальных символов алгоритм примерно такой.

Допустим, производится анализ второго элемента таблицы кодов лексем. Текущая разбираемая лексема в грамматике БНФ является нетерминальным символом. В формируемой таблице переходов данные заносятся в третью ячейку первой строки.

Номер позиции в таблице кодов лексем равен 2. Производится чтение данных из второго столбца таблицы кодов лексем. Полученное значение номера таблицы - 2 (таблица символических имен), спецификатор равен 1.

Конструкция, определяющая структуру нетерминального символа <prog-name>, в грамматике БНФ имеет номер 2.

В формируемой таблице переходов добавляется новая строка, где в первую ячейку заносится адрес возврата на ячейку, вызвавшую переход, смещенную на 1 вправо (в данном случае указывается переход на четвертую ячейку первой строки - «@1,4»).

Номер позиции в таблице кодов лексем не изменяется (остается равным 2).

В грамматике БНФ начинает рассматриваться следующий элемент конструкции - id (идентификатор).

Новое значение в формируемую таблицу переходов будет заноситься в правую ячейку от текущей (в данном примере строка 2, столбец 2).

Для идентификаторов алгоритм примерно такой.

Допустим, производится анализ второго элемента таблицы кодов лексем. Текущая разбираемая лексема в грамматике БНФ находится в конструкции <prog-name> является первым ее элементом. В формируемой таблице переходов данные заносятся во вторую ячейку второй строки.

Номер позиции в таблице кодов лексем равен 2. Производится чтение данных из второго столбца таблицы кодов лексем. Полученное значение номера таблицы - 2 (таблица символических имен), спецификатор равен 1.

Рассматривается первый элемент БНФ грамматики конструкции <prog-name>, этот элемент является идентификатором, следовательно является элементом таблицы символических имен - таблицы 2.

Производится сравнение номеров таблиц. Значения совпали.

Во вторую ячейку второй строки заносится указатель на таблицу 2, спецификатор 1 (его значение берется из таблицы кодов лексем) - «$2,1»

Номер позиции в таблице кодов лексем увеличивается на 1 (стает равным 3).

В грамматике БНФ начинает рассматриваться следующий элемент конструкции <prog-name> - терминальный символ «;».

Новое значение в формируемую таблицу переходов будет заноситься в правую ячейку от текущей (номер столбца увеличился на 1) - вторая строка, третья ячейка.

При несовпадении значений на этапе 3, происходит прекращение разбора, если только текущий элемент не является элементов массива ИЛИ - «|» (например <factor> ::= id | int | real | <text-val> | (<exp>) ) или не является необязательным элементом конструкции (например, PROGRAM <prog-name>), тогда осуществляется переход на следующий элемент массива ИЛИ или переход к следующему элементу конструкции не входящему в данную группу необязательных элементов (подчеркиваются одной общей линией).

Если конструкция закончилась, то осуществляется переход на первую ячейку (ячейку возврата) текущей строки в формируемой таблице перехода. По значению адреса, содержащегося в ячейке возврата активной (готовой для внесения данных) стает ячейка с указанным номером строки и номером столбца. В грамматике БНФ осуществляется переход к элементу, следующему за элементом конструкции, который был определен в текущей конструкции. Например, после определения последнего элемента конструкции <prog-name> «;» осуществляется возврат к элементу, следующему за элементом, вызвавшим эту конструкцию. Возврат осуществлен на строку 1 грамматики БНФ, к элементу VAR, следующему за нетерминальным символом <prog-name>.

Для литералов алгоритм примерно такой.

Допустим, производится анализ шестнадцатого элемента таблицы кодов лексем. Текущая разбираемая лексема в грамматике БНФ находится в конструкции <factor> является вторым элементом конструкции ИЛИ. В формируемой таблице переходов данные заносятся во вторую ячейку десятой строки.

Номер позиции в таблице кодов лексем равен 16. Производится чтение данных из шестнадцатого столбца таблицы кодов лексем. Полученное значение номера таблицы - 3 (таблица литералов), спецификатор равен 1.

Рассматривается второй элемент множества ИЛИ БНФ грамматики конструкции <factor>, этот элемент является литералом целого типа, следовательно является элементом таблицы литералов - таблицы 3.

Производится сравнение номеров таблиц. Значения совпали.

Во вторую ячейку десятой строки заносится указатель на таблицу 3, спецификатор 1 (его значение берется из таблицы кодов лексем) - «$3,1»

Номер позиции в таблице кодов лексем увеличивается на 1 (стает равным 17).

В грамматике БНФ начинает рассматриваться следующий элемент конструкции <factor>, т.к. он отсутствует это говорит о том, что конец конструкции.

Вызывается обработка конца конструкции.

При несовпадении значений на этапе 3, происходит прекращение разбора, если только текущий элемент не является элементов массива ИЛИ - «|» (например <factor> ::= id | int | real | <text-val> | (<exp>) ) или не является необязательным элементом конструкции (например, PROGRAM <prog-name>), тогда осуществляется переход на следующий элемент массива ИЛИ или переход к следующему элементу конструкции не входящему в данную группу необязательных элементов (подчеркиваются одной общей линией).

Описание работы с элементами массива ИЛИ БНФ грамматики.

Если в БНФ грамматике встречается массив ИЛИ, перебор значений осуществляется с левого.

При возникновении ошибки при работе с одним из элементов массива ИЛИ осуществляется переход к следующему, находящемуся правее.

В случае, когда последний (крайний правый) элемент массива ИЛИ или значение в ячейке не удовлетворительно, происходит прекращение разбора программы.

В случае положительного результата (сравнение одного из элементов удачно или сравнение с конечным результатом переходов удачно) происходит переход на следующую лексему грамматики БНФ, на следующий элемент таблицы кодов лексем, на следующую ячейку (на 1 правее) формируемой таблицы переходов.

Ниже рассматривается пример программы.

Program prog1;

var a,b,c:integer;

begin

a:=1+b*(a-c);

end.

Полученная последовательность символов от программы LEXAN представлена в таблице 12.

Таблица 12 - Таблица выходных символов

По исходным данным, также используя таблицу кодов терминальных символов, заполняется таблица построений.

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

Таблица построений состоит из нескольких разделов, они называются: шаги, таблица кодов лексем, имя в программе, элемент грамматики БНФ, результат сравнения, формируемая таблица переходов, выполненное действие.

В разделе «Шаги» перечисляются номера произведенных шагов. Раздел «Таблица кодов лексем» служит для отслеживания позиции в таблице кодов лексем и хранит значения таблицы и кода (или спецификатора) с которыми в дальнейшем происходит сравнение текущего элемента грамматики БНФ. Раздел «Элемент грамматики БНФ» содержит имя элемента, имя конструкции, в которую он входит, тип текущего элемента грамматики, номер таблицы, соответствующей ему, а также код (для терминальных символов), определенный по таблице кодов терминальных символов. В разделе «Формируемая таблица переходов» отслеживается текущая ячейка формируемой таблицы переходов, куда заносится формируемое значение, а также позиция следующей ячейки, с которой будет производиться работа на следующем шаге. В разделе «Выполненное действие» указывается выполненное действие.

Таблица построения предлагается как вспомогательное средство для заполнения формируемой таблицы переходов. Заполнять все шаги и ячейки в ней не обязательно, главное понять логику заполнения формируемой таблицы переходов. Приобретя опыт, в дальнейшем, можно обходиться без таблицы построений, заполняя формируемую таблицу переходов по БНФ грамматике, тексту программы, таблице кодов терминальных символов, таблице кодов лексем.

Из данных, полученных в разделе «Формируемая таблица переходов, текущая позиция» таблицы построения, заполняется формируемая таблица переходов. В результате должна получиться таблица 14.

Принятые сокращения в таблице построений.

НС - нетерминальный символ

ТС - терминальный символ

ИД - идентификатор

Лх - литерал, где х: Ц - целый тип, В - вещественный тип, С - строковый тип.

Л - литерал любого типа.

Наличие знака «-» впереди типа у элемента грамматики БНФ показывает, что данный элемент в разборе может не участвовать.

При заполнении таблицы построений особую сложность представляет работа с переходами. Ниже описывается работа с ними.

При обнаружении терминального символа в грамматике БНФ, необходимо осуществить переход на первый элемент конструкции с тем же именем. В таблице построений определяется номер последней не занятой строки в формируемой таблице переходов. Номером следующей позиции указывается номер этой строки, номер столбца - 1. Значение вносимого значения должно указывать на вторую ячейку последней пустой строки. Следующим шагом заполняется значение текущий позиции, адрес возврата и адрес следующей позиции. Например. После нахождения терминального символа <prog-name> начинает рассматриваться первый элемент конструкции <prog-name> - id. В формируемой таблице переходов последней свободной строкой является строка 2, на нее и осуществляется переход, следующая позиция указывает на строку 2, столбец 1 (шаг 2). На третьем шаге в ячейку возврата 2,1 (где 2 - номер строки, 1 - номер столбца) будет внесено значение, указывающее на ячейку 1,4, т.к. переход осуществлен из ячейки 1,3. Текущая позиция - 2,1, следующая позиция - 2,2.

При возврате возникают другие трудности. К примеру, при окончании конструкции происходит переход на пустую ячейку, затем осуществляется переход на ячейку возврата. Значение, заполненное в ячейке возврата ищется по таблице. По полученному значению осуществляется переход. Например, при окончании конструкции <id-list> (шаг 20), текущей ячейкой оказывается ячейка 5,7. Затем производится переход в ячейку 5,1 (шаг 21). По таблице определяем, что адрес возврата @4,3 (значение из шага 14), т.е. перейти на четвертую строку, третий столбец.

Далее отыскивается положение в грамматике БНФ по имени предыдущей позиции. Например, после перехода в ячейку 4,3 (шаг 22) отыскиваем в таблице имя элемента грамматики ячейки 4,2 (значение из шага 13), им оказывается нетерминальный символ <id-list> конструкции <dec>. По грамматике БНФ определяется, что следующий элемент конструкции <dec> является «:».

Таблица 13 - Таблица построений

Страницы: 1, 2, 3, 4, 5