Правила генерации машинного кода

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

Для построения МП-автомата по переводу ОПЗ в машинные коды и его семантических процедур введем ряд внутренних переменных:

P	-	счетчик вспомогательных переменных;
STR	-	счетчик строк (этот счетчик вводится ввиду специфики выбранного выходного языка - Бейсика, где обязательна нумерация строк; при трансляции в другие выходные (машинные) языки этот счетчик не нужен);

Кроме того, организуем таблицу меток, которая реализует отображение символьных меток исходного языка в номера строк машинного языка:

Метка

Номер строки

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

Рассмотрим работу МП-автомата.

1. Если элемент входной строки ‑ идентификатор или константа, то он заносится в стек (в исходном виде, т.е. не условное обозначение, а имя из таблицы идентификаторов или константа из таблицы констант); вспомогательные переменные и константы переносятся без изменения.

2. Для каждой операции и оператора определяется арность, т.е. количество операндов, и соответствующая семантическая процедура.

3. После выполнения каждой семантической процедуры в выходную строку заносится символ <ВК>, счетчик строк STR наращивается на единицу и заносится в начало новой строки.

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

Таблица 3.1

Лексема	Действия
НП	Извлечь из стека два элемента, занести в выходную строку текст "REM Начало процедуры арг2, арг1"
КП	Занести в выходную строку текст "REM Конец процедуры"
DFD BFD DFT CHAR	Извлечь из стека арг1 - число переменных k; извлечь из стека k аргументов; занести в выходную строку текст "REM Вещественные переменные арг1, арг2,..,аргk"
КО	Извлечь из стека два аргумента
УПЛ	Извлечь из стека два аргумента, занести в выходную строку текст " IF NOT(арг2) THEN GOTO арг1"
БП	Извлечь из стека один аргумент, занести в выходную строку текст "GOTO арг1"
:	Извлечь из стека один аргумент, занести в таблицу меток арг1 и значение счетчика STR
+ * > <	Извлечь из стека два аргумента, нарастить счетчик вспомогательных переменных Р, занести в выходную строку текст "Rp = арг2 <операция> арг1", занести в стек Rp.
:=	Извлечь из стека 2 аргумента и занести в выходную строку текст " арг2 = арг1 "

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

Для арифметических выражений в целях уменьшения количества операторов присваивания и временных переменных возможен вариант формирования строки "(арг2 <операция> арг1)" и занесение ее в стек как единого аргумента для последующих операций и операторов. Недостатком такого подхода является избыточность круглых скобок в выражениях.

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

3.3 Комплексный пример перевода ОПЗ исходной программы в машинный код

Рассмотрим комплексный пример генерации машинного кода на языке Бейсик по ОПЗ исходной программы, которая была построена в примере, рассмотренном в лабораторной работе № 2.

MAIN 1 1 НП A1 A2 2 DFD 1 1 КО A1 378:= A2.73:= CALC2 2 НП

SUM MULT 2 BFD 2 2 КО A1 A2 + 3.2 > M1 УПЛ P БП М1: SUM A2 A1 +:=

P: MULT A1 A2 SUM + *:= КП КП

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

Таблица 3.2

Шаг	Элемент ОПЗ	Стек	P	STR	Машинный код
0.	‑	‑
1.	MAIN	MAIN
2.		1 MAIN
3.		1 1 MAIN
4.	НП	‑			1 REM Начало процедуры MAIN
5.	A1	A1
6.	A2	A2 A1
7.		2 A2 A1
8.	DFD	‑			2 REM Вещественные переменные А1, А2
9.
10.		1 1
11.	КО	‑
12.	A1	A1
13.		378 A1
14.	:=	‑			3 A1=378
15.	A2	A2
16.	.73	.73 A2
17.	:=	‑			4 А2=.73
18.	CALC	CALC
19.		2 CALC
20.		2 2 CALC
21.	НП	‑			5 REM Начало процедуры CALC
22.	SUM	SUM
23.	MULT	MULT SUM
24.		2 MULT SUM
25.	BFD	‑			6 REM Вещественные переменные SUM, MULT
26.
27.		2 2
28.	КО	‑
29.	A1	A1
30.	A2	A2 A1
31.	+	R1			7 R1=A1+A2
32.	3.2	3.2 R1
33.	>	R2			8 R2=R1>3.2
34.	M1	M1 R2
35.	УПЛ	‑			9 IF NOT(R2) GOTO M1
36.	P	P
37.	БП	‑			10 GOTO P
38.	М1	M1
39.	:	‑			Занести в таблицу меток пару M1, 11
40.	SUM	SUM
41.	A2	A2 SUM
42.	A1	A1 A2 SUM
43.	+	R1 SUM			11 R1=A2+A1
44.	:=	‑			12 SUM=R1
45.	P	P
46.	:	‑			Занести в таблицу меток пару P, 13
47.	MULT	MULT
48.	A1	A1 MULT
49.	A2	A2 A1 MULT
50.	SUM	SUM A2 A1 MULT
51.	+	R1 A1 MULT			13 R1=A2+SUM
52.	*	R1 MULT			14 R1=A1*R1
53.	:=	‑			15 MULT=R1
54.	КП	‑			16 REM Конец процедуры
55.	КП	‑			17 REM Конец процедуры

 

После замены символьных меток на числовые получим следующий машинный код

1 REM Начало процедуры MAIN

2 REM Вещественные переменные А1, А2

3 A1=378

4 А2=.73

5 REM Начало процедуры CALC

6 REM Вещественные переменные SUM, MULT

7 R1=A1+A2

8 R2=R1>3.2

9 IF NOT(R2) GOTO 11

10 GOTO 13

11 R1=A2+A1

12 SUM=R1

13 R1=A2+SUM

14 R1=A1*R1

15 MULT=R1

16 REM Конец процедуры

17 REM Конец процедуры

Полученный текст на машинном языке соответствует всем требованиям языка Бейсик.