При обнаружении терминального символа в грамматике БНФ, необходимо осуществить переход на первый элемент конструкции с тем же именем. В таблице построений определяется номер последней не занятой строки в формируемой таблице переходов. Номером следующей позиции указывается номер этой строки, номер столбца – 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 | 1 | 1 | 1 | ТС | PROGRAM | PROGRAM | <prog> | –ТС | 1 | 1 | + | 1 | 2 | $1,1 | 1 | 3 | |
| 2 | 2 | 2 | 1 | ИД | Prog1 | <prog-name> | <prog> | НС | 1 | 3 | @2,2 | 2 | 1 | ||||
| 3 | 2 | 2 | 1 | ИД | Prog1 | 2 | 1 | @1,4 | 2 | 2 | |||||||
| 4 | 2 | 2 | 1 | ИД | Prog1 | id | <prog-name> | ИД | 2 | + | 2 | 2 | $2,1 | 2 | 3 | ||
| 5 | 3 | 1 | 27 | ТС | ; | ; | <prog-name> | –ТС | 1 | 27 | + | 2 | 3 | $1,27 | 2 | 4 | |
| 6 | 4 | 1 | 2 | ТС | VAR | <prog-name> | 2 | 4 | 2 | 1 | конец конструкции | ||||||
| 7 | 4 | 1 | 2 | ТС | VAR | 2 | 1 | 1 | 4 | переход | |||||||
| 8 | 4 | 1 | 2 | ТС | VAR | VAR | <prog> | –ТС | 1 | 2 | + | 1 | 4 | $1,2 | 1 | 5 | |
| 9 | 5 | 2 | 2 | ИД | a | <dec-list> | <prog> | НС | 1 | 5 | @3,2 | 3 | 1 | ||||
| 10 | 5 | 2 | 2 | ИД | a | 3 | 1 | @1,6 | 3 | 2 | |||||||
| 11 | 5 | 2 | 2 | ИД | а | <dec> | <dec-list> | НС | 3 | 2 | @4,2 | 4 | 1 | ||||
| 12 | 5 | 2 | 2 | ИД | а | 4 | 1 | @3,3 | 4 | 2 | |||||||
| 13 | 5 | 2 | 2 | ИД | а | <id-list> | <dec> | НС | 4 | 2 | @5,2 | 5 | 1 | ||||
| 14 | 5 | 2 | 2 | ИД | а | 5 | 1 | @4,3 | 5 | 2 | |||||||
| 15 | 5 | 2 | 2 | ИД | а | id | <id-list> | ИД | 2 | + | 5 | 2 | $2,2 | 5 | 3 | ||
| 16 | 6 | 1 | 29 | ТС | , | , | <id-list> | ТС | 1 | 29 | + | 5 | 3 | $1,29 | 5 | 4 | |
| 17 | 7 | 2 | 3 | ИД | b | id | <id-list> | ИД | 2 | + | 5 | 4 | $2,3 | 5 | 5 | ||
| 18 | 8 | 1 | 29 | ТС | , | , | <id-list> | ТС | 1 | 29 | + | 5 | 5 | $1,29 | 5 | 6 | |
| 19 | 9 | 2 | 4 | ИД | c | id | <id-list> | ИД | 2 | + | 5 | 6 | $2,4 | 5 | 7 | ||
| 20 | 10 | 1 | 31 | ТС | : | <id-list> | 5 | 7 | 5 | 1 | конец конструкции | ||||||
| 21 | 10 | 1 | 31 | ТС | : | 5 | 1 | 4 | 3 | переход | |||||||
| 22 | 10 | 1 | 31 | ТС | : | : | <dec> | ТС | 1 | 31 | + | 4 | 3 | : | 4 | 4 | |
| 23 | 11 | 1 | 5 | ТС | INTEGER | <type> | <dec> | НС | 4 | 4 | @6,1 | 6 | 1 | ||||
| 24 | 11 | 1 | 5 | ТС | INTEGER | 6 | 1 | @4,5 | 6 | 2 | |||||||
| 25 | 11 | 1 | 5 | ТС | INTEGER | INTEGER | <type> | ТС | 1 | 5 | + | 6 | 2 | $1,5 | 6 | 3 | |
| 26 | 12 | 1 | 27 | ТС | ; | <type> | 6 | 3 | 6 | 1 | конец конструкции | ||||||
| 27 | 12 | 1 | 27 | ТС | ; | 6 | 1 | 4 | 5 | переход | |||||||
| 28 | 12 | 1 | 27 | ТС | ; | <dec> | 4 | 5 | 4 | 1 | конец конструкции | ||||||
| 29 | 12 | 1 | 27 | ТС | ; | 4 | 1 | 3 | 3 | переход | |||||||
| 30 | 12 | 1 | 27 | ТС | ; | ; | <dec-list> | –ТС | 1 | 27 | + | 3 | 3 | $1,27 | 3 | 4 | |
| 31 | 13 | 1 | 3 | ТС | BEGIN | <dec-list> | 3 | 4 | 3 | 1 | конец конструкции | ||||||
| 32 | 13 | 1 | 3 | ТС | BEGIN | 3 | 1 | 1 | 6 | переход | |||||||
| 33 | 13 | 1 | 3 | ТС | BEGIN | BEGIN | <prog> | ТС | 1 | 3 | + | 1 | 6 | $1,3 | 1 | 7 | |
| 34 | 14 | 2 | 2 | ИД | а | <stmt-list> | <prog> | –НС | 1 | 7 | @7,2 | 7 | 1 | ||||
| 35 | 14 | 2 | 2 | ИД | а | 7 | 1 | @1,8 | 7 | 2 | |||||||
| 36 | 14 | 2 | 2 | ИД | а | <stmt> | <stmt-list> | НС | 7 | 2 | @8,2 | 8 | 1 | ||||
| 37 | 14 | 2 | 2 | ИД | a | 8 | 1 | @7,3 | 8 | 2 | |||||||
| 38 | 14 | 2 | 2 | ИД | a | <assign> | <stmt> | НС | 8 | 2 | @9,2 | 9 | 1 | ||||
| 39 | 14 | 2 | 2 | ИД | a | 9 | 1 | @8,3 | 9 | 2 | |||||||
Продолжение таблицы 13
| Шаги | Таблица кодов лексем | Имя в программе | Элемент грамматики БНФ | Результат сравнения | Формируемая таблица переходов | Выполненное действие | |||||||||||
| текущая позиция | следующая позиция | ||||||||||||||||
| позиция | табл | код, специф | тип | имя | текущая конструкция | тип | табл | код (для ТС) | строка | столбец | вносимое значение | строка | столбец | ||||
| 40 | 14 | 2 | 2 | ИД | a | id | <assign> | ИД | 2 | + | 9 | 2 | $2,2 | 9 | 3 | ||
| 41 | 15 | 1 | 28 | ТС | := | := | <assign> | ТС | 1 | 28 | + | 9 | 3 | $1,28 | 9 | 4 | |
| 42 | 16 | 3 | 1 | ЛЦ | 1 | <exp> | <assign> | НС | 9 | 4 | @10,2 | 10 | 1 | ||||
| 43 | 16 | 3 | 1 | ЛЦ | 1 | 10 | 1 | @9,5 | 10 | 2 | |||||||
| 44 | 16 | 3 | 1 | ЛЦ | 1 | – | <exp> | –ТС | 1 | 33 | – | 10 | 2 | ||||
| 45 | 16 | 3 | 1 | ЛЦ | 1 | <term> | <exp> | НС | 10 | 2 | @11,2 | 11 | 1 | ||||
| 46 | 16 | 3 | 1 | ЛЦ | 1 | 11 | 1 | @10,3 | 11 | 2 | |||||||
| 47 | 16 | 3 | 1 | ЛЦ | 1 | <factor> | <term> | НС | 11 | 2 | @12,2 | 12 | 1 | ||||
| 48 | 16 | 3 | 1 | ЛЦ | 1 | 12 | 1 | @11,3 | 12 | 2 | |||||||
| 49 | 16 | 3 | 1 | ЛЦ | 1 | id | <factor> | ИД | 2 | – | 12 | 2 | |||||
| 50 | 16 | 3 | 1 | ЛЦ | 1 | int | <factor> | ЛЦ | 3 | + | 12 | 2 | $3,1 | 12 | 3 | ||
| 51 | 17 | 1 | 32 | ТС | + | <factor> | 12 | 3 | 12 | 1 | конец конструкции | ||||||
| 52 | 17 | 1 | 32 | ТС | + | 12 | 1 | 11 | 3 | переход | |||||||
| 53 | 17 | 1 | 32 | ТС | + | * | <term> | ТС | 1 | 34 | – | 11 | 3 | ||||
| 54 | 17 | 1 | 32 | ТС | + | DIV | <term> | ТС | 1 | 17 | – | 11 | 3 | ||||
| 55 | 17 | 1 | 32 | ТС | + | / | <term> | ТС | 1 | 37 | – | 11 | 3 | ||||
| 56 | 17 | 1 | 32 | ТС | + | <term> | 11 | 3 | 11 | 1 | конец конструкции | ||||||
| 57 | 17 | 1 | 32 | ТС | + | 11 | 1 | 10 | 3 | переход | |||||||
| 58 | 17 | 1 | 32 | ТС | + | + | <exp> | ТС | 1 | 32 | + | 10 | 3 | $1,32 | 10 | 4 | |
| 59 | 18 | 2 | 3 | ИД | b | <term> | <exp> | НС | 10 | 4 | @13,2 | 13 | 1 | ||||
| 60 | 18 | 2 | 3 | ИД | b | 13 | 1 | @10,5 | 13 | 2 | |||||||
| 61 | 18 | 2 | 3 | ИД | b | <factor> | <term> | НС | 13 | 2 | @14,2 | 14 | 1 | ||||
| 62 | 18 | 2 | 3 | ИД | b | 14 | 1 | @13,3 | 14 | 2 | |||||||
| 63 | 18 | 2 | 3 | ИД | b | id | <factor> | ИД | 2 | + | 14 | 2 | $2,3 | 14 | 3 | ||
| 64 | 19 | 1 | 34 | ТС | * | <factor> | 14 | 3 | 14 | 1 | конец конструкции | ||||||
| 65 | 19 | 1 | 34 | ТС | * | 14 | 1 | 13 | 3 | переход | |||||||
| 66 | 19 | 1 | 34 | ТС | * | * | <term> | ТС | 1 | 34 | + | 13 | 3 | $1,34 | 13 | 4 | |
| 67 | 20 | 1 | 35 | ТС | ( | <factor> | <term> | 13 | 4 | @15,2 | 15 | 1 | |||||
| 68 | 20 | 1 | 35 | ТС | ( | <term> | 15 | 1 | @13,5 | 15 | 2 | ||||||
| 69 | 20 | 1 | 35 | ТС | ( | id | <factor> | ИД | 2 | – | 15 | 2 | |||||
| 70 | 20 | 1 | 35 | ТС | ( | int | <factor> | ЛЦ | 3 | – | 15 | 2 | |||||
| 71 | 20 | 1 | 35 | ТС | ( | real | <factor> | ЛВ | 3 | – | 15 | 2 | |||||
| 72 | 20 | 1 | 35 | ТС | ( | ( | <factor> | ТС | 1 | 35 | + | 15 | 2 | $1,35 | 15 | 3 | |
| 73 | 21 | 2 | 2 | ИД | а | <exp> | <factor> | НС | 15 | 3 | @16,2 | 16 | 1 | ||||
| 74 | 21 | 2 | 2 | ИД | а | 16 | 1 | @15,4 | 16 | 2 | |||||||
| 75 | 21 | 2 | 2 | ИД | а | – | <exp> | –ТС | 1 | 33 | – | 16 | 2 | ||||
| 76 | 21 | 2 | 2 | ИД | а | <term> | <exp> | НС | 16 | 2 | @17,2 | 17 | 1 | ||||
| 77 | 21 | 2 | 2 | ИД | а | 17 | 1 | @16,3 | 17 | 2 | |||||||
| 78 | 21 | 2 | 2 | ИД | а | <factor> | <term> | НС | 17 | 2 | @18,2 | 18 | 1 | ||||
Продолжение таблицы 13