Для нетерминальных символов алгоритм примерно такой.
Допустим, производится анализ второго элемента таблицы кодов лексем. Текущая разбираемая лексема в грамматике БНФ является нетерминальным символом. В формируемой таблице переходов данные заносятся в третью ячейку первой строки.
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) – вторая строка, третья ячейка.
При несовпадении значений на этапе 3, происходит прекращение разбора, если только текущий элемент не является элементов массива ИЛИ – «|» (например <factor> ::= id | int | real | <text-val> | (<exp>) ) или не является необязательным элементом конструкции (например, PROGRAM <prog-name>), тогда осуществляется переход на следующий элемент массива ИЛИ или переход к следующему элементу конструкции не входящему в данную группу необязательных элементов (подчеркиваются одной общей линией).
Если конструкция закончилась, то осуществляется переход на первую ячейку (ячейку возврата) текущей строки в формируемой таблице перехода. По значению адреса, содержащегося в ячейке возврата активной (готовой для внесения данных) стает ячейка с указанным номером строки и номером столбца. В грамматике БНФ осуществляется переход к элементу, следующему за элементом конструкции, который был определен в текущей конструкции. Например, после определения последнего элемента конструкции <prog-name> «;» осуществляется возврат к элементу, следующему за элементом, вызвавшим эту конструкцию. Возврат осуществлен на строку 1 грамматики БНФ, к элементу VAR, следующему за нетерминальным символом <prog-name>.
Для литералов алгоритм примерно такой.
Допустим, производится анализ шестнадцатого элемента таблицы кодов лексем. Текущая разбираемая лексема в грамматике БНФ находится в конструкции <factor> является вторым элементом конструкции ИЛИ. В формируемой таблице переходов данные заносятся во вторую ячейку десятой строки.
1) Номер позиции в таблице кодов лексем равен 16. Производится чтение данных из шестнадцатого столбца таблицы кодов лексем. Полученное значение номера таблицы – 3 (таблица литералов), спецификатор равен 1.
2) Рассматривается второй элемент множества ИЛИ БНФ грамматики конструкции <factor>, этот элемент является литералом целого типа, следовательно является элементом таблицы литералов – таблицы 3.
3) Производится сравнение номеров таблиц. Значения совпали.
4) Во вторую ячейку десятой строки заносится указатель на таблицу 3, спецификатор 1 (его значение берется из таблицы кодов лексем) – «$3,1»
5) Номер позиции в таблице кодов лексем увеличивается на 1 (стает равным 17).
6) В грамматике БНФ начинает рассматриваться следующий элемент конструкции <factor>, т.к. он отсутствует это говорит о том, что конец конструкции.
7) Вызывается обработка конца конструкции.
При несовпадении значений на этапе 3, происходит прекращение разбора, если только текущий элемент не является элементов массива ИЛИ – «|» (например <factor> ::= id | int | real | <text-val> | (<exp>) ) или не является необязательным элементом конструкции (например, PROGRAM <prog-name>), тогда осуществляется переход на следующий элемент массива ИЛИ или переход к следующему элементу конструкции не входящему в данную группу необязательных элементов (подчеркиваются одной общей линией).
Описание работы с элементами массива ИЛИ БНФ грамматики.
Если в БНФ грамматике встречается массив ИЛИ, перебор значений осуществляется с левого.
При возникновении ошибки при работе с одним из элементов массива ИЛИ осуществляется переход к следующему, находящемуся правее.
В случае, когда последний (крайний правый) элемент массива ИЛИ или значение в ячейке не удовлетворительно, происходит прекращение разбора программы.
В случае положительного результата (сравнение одного из элементов удачно или сравнение с конечным результатом переходов удачно) происходит переход на следующую лексему грамматики БНФ, на следующий элемент таблицы кодов лексем, на следующую ячейку (на 1 правее) формируемой таблицы переходов.
Ниже рассматривается пример программы.
Programprog1;
var a,b,c:integer;
begin
a:=1+b*(a–c);
end.
Полученная последовательность символов от программы LEXAN представлена в таблице 12.
Таблица 12 – Таблица выходных символов
| № п.п. | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| Таблица | 1 | 2 | 1 | 1 | 2 | 1 | 2 | 1 | 2 | 1 | 1 | 1 | 1 | 2 | 1 |
| Строка | 1 | 1 | 27 | 2 | 2 | 29 | 3 | 29 | 4 | 31 | 5 | 27 | 3 | 2 | 28 |
| № п.п. | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 |
| Таблица | 3 | 1 | 2 | 1 | 1 | 2 | 1 | 2 | 1 | 1 | 1 | 1 |
| Строка | 1 | 32 | 3 | 34 | 35 | 2 | 33 | 4 | 36 | 27 | 4 | 30 |
По исходным данным, также используя таблицу кодов терминальных символов, заполняется таблица построений.
Для лучшего понимания заполнения формируемой таблицы переходов заполняется таблица построений. Обработка данных и заполнение таблицы процесс довольно трудоемкий, однако, надо понимать, что и для машины данный разбор является самой трудоемкой задачей. Здесь же процесс разбора программы максимально унифицирован. Дается возможность отследить все возможные (исходные) параметры (значения). Прервать заполнение таблицы построений можно в любой момент времени, а потом продолжить, не теряя логику переходов (построения).
Таблица построений состоит из нескольких разделов, они называются: шаги, таблица кодов лексем, имя в программе, элемент грамматики БНФ, результат сравнения, формируемая таблица переходов, выполненное действие.
В разделе «Шаги» перечисляются номера произведенных шагов. Раздел «Таблица кодов лексем» служит для отслеживания позиции в таблице кодов лексем и хранит значения таблицы и кода (или спецификатора) с которыми в дальнейшем происходит сравнение текущего элемента грамматики БНФ. Раздел «Элемент грамматики БНФ» содержит имя элемента, имя конструкции, в которую он входит, тип текущего элемента грамматики, номер таблицы, соответствующей ему, а также код (для терминальных символов), определенный по таблице кодов терминальных символов. В разделе «Формируемая таблица переходов» отслеживается текущая ячейка формируемой таблицы переходов, куда заносится формируемое значение, а также позиция следующей ячейки, с которой будет производиться работа на следующем шаге. В разделе «Выполненное действие» указывается выполненное действие.
Таблица построения предлагается как вспомогательное средство для заполнения формируемой таблицы переходов. Заполнять все шаги и ячейки в ней не обязательно, главное понять логику заполнения формируемой таблицы переходов. Приобретя опыт, в дальнейшем, можно обходиться без таблицы построений, заполняя формируемую таблицу переходов по БНФ грамматике, тексту программы, таблице кодов терминальных символов, таблице кодов лексем.
Из данных, полученных в разделе «Формируемая таблица переходов, текущая позиция» таблицы построения, заполняется формируемая таблица переходов. В результате должна получиться таблица 14.
Принятые сокращения в таблице построений.
НС – нетерминальный символ
ТС – терминальный символ
ИД – идентификатор
Лх – литерал, где х: Ц – целый тип, В – вещественный тип, С – строковый тип.
Л – литерал любого типа.
Наличие знака «–» впереди типа у элемента грамматики БНФ показывает, что данный элемент в разборе может не участвовать.
При заполнении таблицы построений особую сложность представляет работа с переходами. Ниже описывается работа с ними.