Разбор делается по данным, полученным от БНФ грамматик, из таблиц терминальных символов, выходных кодов лексем.
Заполнение формируемой таблицы переходов начинается со второй ячейки первой строки.
Для терминальных символов алгоритм может выглядеть таким образом.
Допустим, производится анализ первого элемента таблицы кодов лексем.
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) – вторая строка, третья ячейка.
При несовпадении значений на этапе 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 правее) формируемой таблицы переходов.
Ниже рассматривается пример программы.
Program prog1;
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.
Принятые сокращения в таблице построений.
НС – нетерминальный символ
ТС – терминальный символ
ИД – идентификатор
Лх – литерал, где х: Ц – целый тип, В – вещественный тип, С – строковый тип.
Л – литерал любого типа.
Наличие знака «–» впереди типа у элемента грамматики БНФ показывает, что данный элемент в разборе может не участвовать.
При заполнении таблицы построений особую сложность представляет работа с переходами. Ниже описывается работа с ними.
При обнаружении терминального символа в грамматике БНФ, необходимо осуществить переход на первый элемент конструкции с тем же именем. В таблице построений определяется номер последней не занятой строки в формируемой таблице переходов. Номером следующей позиции указывается номер этой строки, номер столбца – 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
| Шаги | Таблица кодов лексем | Имя в программе | Элемент грамматики БНФ | Результат сравнения | Формируемая таблица переходов | Выполненное действие | |||||||||||
| текущая позиция | следующая позиция | ||||||||||||||||
| позиция | табл | код, специф | тип | имя | текущая конструкция | тип | табл | код (для ТС) | строка | столбец | вносимое значение | строка | столбец | ||||
| 79 | 18 | 1 | @17,3 | 18 | 2 | ||||||||||||
| 80 | 21 | 2 | 2 | ИД | а | id | <factor> | ИД | 2 | + | 18 | 2 | $2,2 | 18 | 3 | ||
| 81 | 22 | 1 | 33 | ТС | – | 18 | 3 | 18 | 1 | конец конструкции | |||||||
| 82 | 22 | 1 | 33 | ТС | – | 18 | 1 | 17 | 3 | переход | |||||||
| 83 | 22 | 1 | 33 | ТС | – | * | <term> | ТС | 1 | 34 | – | 17 | 3 | ||||
| 84 | 22 | 1 | 33 | ТС | – | DIV | <term> | ТС | 1 | 17 | – | 17 | 3 | ||||
| 85 | 22 | 1 | 33 | ТС | – | / | <term> | ТС | 1 | 37 | – | 17 | 3 | ||||
| 86 | 22 | 1 | 33 | ТС | – | 17 | 3 | 17 | 1 | конец конструкции | |||||||
| 87 | 22 | 1 | 33 | ТС | – | 17 | 1 | 16 | 3 | переход | |||||||
| 88 | 22 | 1 | 33 | ТС | – | + | <exp> | ТС | 1 | 32 | – | 16 | 3 | ||||
| 89 | 22 | 1 | 33 | ТС | – | – | <exp> | ТС | 1 | 33 | + | 16 | 3 | $1,33 | 16 | 4 | |
| 90 | 23 | 2 | 4 | ИД | с | <term> | <exp> | НС | 16 | 4 | @19,2 | 19 | 1 | ||||
| 91 | 23 | 2 | 4 | ИД | с | 19 | 1 | @16,5 | 19 | 2 | |||||||
| 92 | 23 | 2 | 4 | ИД | с | <factor> | <term> | НС | 19 | 2 | @20,2 | 20 | 1 | ||||
| 93 | 23 | 2 | 4 | ИД | с | 20 | 1 | @19,3 | 20 | 2 | |||||||
| 94 | 23 | 2 | 4 | ИД | c | id | <factor> | ИД | 2 | + | 20 | 2 | $2,4 | 20 | 3 | ||
| 95 | 24 | 1 | 36 | ТС | ) | <factor> | 20 | 3 | 20 | 1 | конец конструкции | ||||||
| 96 | 24 | 1 | 36 | ТС | ) | 20 | 1 | 19 | 3 | переход | |||||||
| 97 | 24 | 1 | 36 | ТС | ) | * | <term> | – | 19 | 3 | |||||||
| 98 | 24 | 1 | 36 | ТС | ) | DIV | <term> | – | 19 | 3 | |||||||
| 99 | 24 | 1 | 36 | ТС | ) | / | <term> | – | 19 | 3 | |||||||
| 100 | 24 | 1 | 36 | ТС | ) | <term> | 19 | 3 | 19 | 1 | конец конструкции | ||||||
| 101 | 24 | 1 | 36 | ТС | ) | 19 | 1 | 16 | 5 | переход | |||||||
| 102 | 24 | 1 | 36 | ТС | ) | + | <exp> | ТС | 1 | 32 | – | 16 | 5 | ||||
| 103 | 24 | 1 | 36 | ТС | ) | – | <exp> | ТС | 1 | 33 | – | 16 | 5 | ||||
| 104 | 24 | 1 | 36 | ТС | ) | <exp> | 16 | 5 | 16 | 1 | конец конструкции | ||||||
| 105 | 24 | 1 | 36 | ТС | ) | 16 | 1 | 15 | 4 | переход | |||||||
| 106 | 24 | 1 | 36 | ТС | ) | ) | <factor> | ТС | 1 | 36 | + | 15 | 4 | $1,36 | 15 | 5 | |
| 107 | 25 | 1 | 27 | ТС | ; | <factor> | 15 | 5 | 15 | 1 | конец конструкции | ||||||
| 108 | 25 | 1 | 27 | ТС | ; | 15 | 1 | 13 | 5 | переход | |||||||
| 109 | 25 | 1 | 27 | ТС | ; | * | <term> | ТС | 1 | 34 | – | 13 | 5 | ||||
| 110 | 25 | 1 | 27 | ТС | ; | DIV | <term> | ТС | 1 | 17 | – | 13 | 5 | ||||
| 111 | 25 | 1 | 27 | ТС | ; | / | <term> | ТС | 1 | 37 | – | 13 | 5 | ||||
| 112 | 25 | 1 | 27 | ТС | ; | 13 | 5 | 13 | 1 | конец конструкции | |||||||
| 113 | 25 | 1 | 27 | ТС | ; | 13 | 1 | 10 | 5 | переход | |||||||
| 114 | 25 | 1 | 27 | ТС | ; | + | <exp> | ТС | 1 | 32 | 10 | 5 | |||||
| 115 | 25 | 1 | 27 | ТС | ; | – | <exp> | ТС | 1 | 33 | 10 | 5 | |||||
| 116 | 25 | 1 | 27 | ТС | ; | 10 | 5 | 10 | 1 | конец конструкции | |||||||
| 117 | 25 | 1 | 27 | ТС | ; | 10 | 1 | 9 | 5 | переход | |||||||
Продолжение таблицы 13
| Шаги | Таблица кодов лексем | Имя в программе | Элемент грамматики БНФ | Результат сравнения | Формируемая таблица переходов | Выполненное действие | |||||||||||
| текущая позиция | следующая позиция | ||||||||||||||||
| позиция | табл | код, специф | тип | имя | текущая конструкция | тип | табл | код (для ТС) | строка | столбец | вносимое значение | строка | столбец | ||||
| 118 | 25 | 1 | 27 | ТС | ; | <assign> | 9 | 5 | 9 | 1 | конец конструкции | ||||||
| 119 | 25 | 1 | 27 | ТС | ; | 9 | 1 | 8 | 3 | переход | |||||||
| 120 | 25 | 1 | 27 | ТС | ; | <stmt> | 8 | 3 | 8 | 1 | конец конструкции | ||||||
| 121 | 25 | 1 | 27 | ТС | ; | 8 | 1 | 7 | 3 | переход | |||||||
| 122 | 25 | 1 | 27 | ТС | ; | ; | <stmt-list> | –ТС | 1 | 27 | + | 7 | 3 | $1,27 | 7 | 4 | |
| 123 | 26 | 1 | 4 | ТС | END | <stmt-list> | 7 | 4 | 7 | 1 | конец конструкции | ||||||
| 124 | 26 | 1 | 4 | ТС | END | 7 | 1 | 1 | 8 | переход | |||||||
| 125 | 26 | 1 | 4 | ТС | END | END | <prog> | ТС | 1 | 4 | + | 1 | 8 | $1,4 | 1 | 9 | |
| 126 | 27 | 1 | 30 | ТС | . | . | <prog> | ТС | 1 | 30 | + | 1 | 9 | $1,30 | 1 | 10 | |
| 127 | 1 | 10 | 1 | 1 | конец конструкции | ||||||||||||
| 128 | 1 | 1 | |||||||||||||||
Таблица 14 – Формируемая таблица переходов
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ||
| 1 | PROGRAM $1,1 | <prog-name> @2,2 | VAR $1,2 | <dec-list> @3,2 | BEGIN $1,3 | <stmt-list> @7,2 | END $1,4 | . $1,30 | |||
| 2 | <prog-name> | @1,4 | prog1 $2,1 | ; $1,27 | |||||||
| 3 | <dec-list> | @1,6 | <dec> @4,2 | ; $1,27 | |||||||
| 4 | <dec> | @3,3 | <id-list> @5,2 | : $1,31 | <type> @6,2 | ||||||
| 5 | <id-list> | @4,3 | a $2,2 | , $1,29 | b $2,3 | , $1,29 | c $2,4 | ||||
| 6 | <type> | @4,5 | INTEGER $1,5 | ||||||||
| 7 | <stmt-list> | @1,8 | <stmt> @8,2 | ; $1,27 | |||||||
| 8 | <stmt> | @7,3 | <assign> @9,2 | ||||||||
| 9 | <assign> | @8,3 | a $2,2 | := $1,28 | <exp> @10,2 | ||||||
| 10 | <exp> | @9,5 | <term> @11,2 | + $1,32 | <term> @13,2 | ||||||
| 11 | <term> | @10,3 | <factor> @12,2 | ||||||||
| 12 | <factor> | @11,3 | 1 $3,1 | ||||||||
| 13 | <term> | @10,5 | <factor> @14,2 | * $1,34 | <factor> @15,2 | ||||||
| 14 | <factor> | @13,3 | b $2,3 | ||||||||
| 15 | <factor> | @13,5 | ( $1,35 | <exp> @16,2 | ) $1,36 | ||||||
| 16 | <exp> | @15,4 | <term> @17,2 | – $1,33 | <term> @19,2 | ||||||
| 17 | <term> | @16,3 | <factor> @18,2 | ||||||||
| 18 | <factor> | @17,3 | a $2,2 | ||||||||
| 19 | <term> | @16,5 | <factor> @20,2 | ||||||||
| 20 | <factor> | @19,3 | c $2,4 |
Построение деревьев
Для наглядного отображения полученных грамматик используют синтаксические деревья, пример показан на рисунке 3.
На основе введенных значений формируемой таблицы переходов в программу SINAN строится (формируется) синтаксическое дерево (дерево грамматического разбора).
Деревья могут быть представлены в вертикально как показано на рисунке 5, а и горизонтально – рисунок 5, б.
Рассмотрим выражение: a := c – (1 + b)
а)
б)
Рисунок 5 – а) вертикальное дерево, б) горизонтальное дерево
 |
Рисунок 6 – Горизонтальное синтаксическое дерево
На рисунке 6 показано горизонтальное синтаксическое дерево, построенное по следующей программе:
PROGRAM prog1;
VAR a,b:INTEGER;
s:STRING;
BEGIN
b:=78;
s:='Дерево';
WRITE(s);
a:=b*(2+a);
END.
Семантический анализ
Функции семантического анализатора:
1) ведение табличных символов;
2) включение неявной информации (по умолчанию);
3) обнаружение ошибок;
4) макрообработка и операции, выполняемые во время компиляции.
После проведения синтаксического анализа формируется дерево грамматического разбора, представленное в виде таблицы. По этому дереву на этапе семантического анализа производится новый смотр.
Одно из предназначений семантического анализатора – поиск ошибок. Существуют следующие критерии поиска ошибок:
1) не должно быть повторного описания идентификатора;
2) все идентификаторы, используемые в программе, должны быть описаны;
3) запрещается присвоение значению переменной одного типа значение другого типа (возможно только присвоение вещественному типу целого значения);
4) результат деления “ / “ всегда вещественное число;
5) перед использованием переменной (идентификатора) ей должно быть присвоено значение (данная ошибка не относится к критическим).
6) в цикле FOR, структуре <index-exp>, идентификатор должен быть целого типа, как и оба значения возвращаемые структурой <exp>.
Пример неправильно написанных элементов программы.
VAR
A,B,C:INTEGER;
C,D:REAL – повторное описание переменной C
BEGIN
A:=3.5; – присвоение переменной целого типа вещественного значения
B:=A/2; – присвоение переменной целого типа вещественного значения, образующегося при делении
D:=F*5; – не описана переменная F
FOR A:=1 TO D DO C:=C+A – переменная D вещественного типа
END.
Дата: 2019-05-29, просмотров: 165.
