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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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>), тогда осуществляется переход на следующий элемент массива ИЛИ или переход к следующему элементу конструкции не входящему в данную группу необязательных элементов (подчеркиваются одной общей линией).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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