Интерпретатор

После лексической обработки и расстановки ссылок последовательность лексем, массивы идентификаторов и констант поступают на обработку интерпретатору. Задача интерпретатора - распознать конструкции языка и выполнить действия, предписанные входной программой. Учитывая, что синтаксический разбор будет производиться над массивом лексем, уточним грамматику языка МИЛАН, которая будет использована для синтаксического анализа последовательности лексем. Множество терминалов в уточненной грамматике - это множество лексем.

Уточненная грамматика языка МИЛАН:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

12)

Здесь и - число идентификаторов и констант; нетерминалы обозначают конструкции языка: - <программа>; -<последовательность операторов>; - <оператор>; - <условие>; - <выражение>; - <терм>; - <множитель>; - <константа>; O - <знак отношения>; M - <операция типа умножения>; N - <операция типа сложения>; I - <идентификатор>.

Построим синтаксические диаграммы интерпретатора языка МИЛАН (рис. 9-10). Из диаграммы видно, чтограмматика языка МИЛАН является - грамматикой.

Для описания семантических функций синтаксической диаграммы интерпретатора введем следующие обозначения: $Number_Lexem - номер очередной рассматриваемой лексемы в массиве лексем; $Stek Res - стек результатов вычислений; $StekIdent - стек идентификаторов; $StekMul - стек для операций типа умножения; $StekSum - стек для операций типа сложения; $StekRel - стек для операции отношения; $Arrident – стек текущих значений идентификаторов.

 

Рис. 9. R-схема интерпретатора: нетерминальные символы , , .

Рис. 10. R-схема интерпретатора: нетерминальные символы , , , .

Семантические функции к R-схеме интерпретатора:

y0: инициализация стеков и переменных;

y1: занесение в стек $StekRes идентификатора $Tab_Lexems[$Number_Lexem]->Value;

y2: занесение в стек $StekRes константы $Tab_Lexems[$Number_Lexem]->Value;

y3: прочитать целое число с терминала в переменную $Cifra и положить его в $StekRes ($Cifra→$StekRes);

y4: чтение следующей лексемы ($Number_Lexem++);

y5: занесение в стек $StekMul значение операции типа умножения ($Tab_Lexems[$Number_Lexem]->Value→$StekMul);

y6: в переменную $Bi снять элемент со стека $StekRes ($Bi←$StekRes), в переменную $Ai снять элемент со стека $StekRes ($Ai←$StekRes), в переменную $kmul снять элемент со стека $StekMul ($kmul←$StekMul), выполнить операцию типа умножение $Ai otu($kmul) $Bi и результат занести в стек $StekRes;

y7: занесение в стек $StekSum кода операции типа сложения;

y8: в переменную $ksum снять со стека $StekSum значение лексемы ots ($ksum←$StekSum), если $ksum=1, то снять в переменную $Ai элемент со стека $StekRes ($Ai←$StekRes), сменить знак этого числа и занести его в стек $StekRes (-$Ai→$StekRes);

y9: занесение в стек $StekSum кода операции типа сложения;

y10: в переменную $Bi снять элемент со стека $StekRes ($Bi←$StekRes), в переменную $Ai снять элемент со стека $StekRes ($Ai←$StekRes), в переменную $ksum снять элемент со стека $StekSum ($ksum←$StekSum), вы полнить операцию типа сложение $Ai ots($ksum) $Bi и результат занести в стек $StekRes;

y11: добавление в стек $StekRel значения операции типа отношение ($Tab_Lexems[$Number_Lexem]->Value→$StekRel);

y12: в переменную $Bi снять элемент со стека $StekRes ($Bi←$StekRes), в переменную $Ai снять элемент со стека $StekRes ($Ai←$StekRes), в переменную $krel снять элемент со стека $StekRel ($krel←$StekRel), выполнить операцию сравнения $Ai otn($krel) $Bi и результат занести в стек $StekRes ([0, 1] →$StekRes);

y13: добавить значение лексемы с номером Number_Lexem в стек StekIdent ($Tab_Lexems[$Number_Lexem]->Value→$StekIdent);

y14: в переменную $Ai снять элемент со стека $StekRes ($Ai←$StekRes), в переменную $Bi снять со стека $StekIdent значение лексемы ident ($Bi←$StekIdent), идентификатору с номером $Bi, присвоить значение $Ai ($ArrIdent[$Bi]=$Ai);

y15: в переменную $Ai снять элемент со стека $StekRes ($Ai←$StekRes), на печатать переменную $Ai;

y16: в переменную $Ai снять элемент со стека $StekRes ($Ai←$StekRes), если $Ai=1, то это истина, иначе - ложь;

y17: перейти на лексему номер $Tab_Lexems[$Number_Lexem]->Value;

y18: в переменную $Ai снять элемент со стека $StekRes ($Ai←$StekRes), если $Ai=1, то это истина, иначе - ложь;

y19: перейти на лексему номер $Tab_Lexems[$Number_Lexem]->Value-1;

y20: завершение работы;

Пример №3: Рассмотрим пример обработки программы на языке МИЛАН.

BEGIN x:=2; y:=5; OUTPUT(x+y) END

Результаты работы лексического анализатора:

1) Таблица лексем

номер
  1 , 0 19 , 1 16 , 0 20 , 1 12 , 0 19 , 2 16 , 0 20 ,2 12 ,0
8 , 0 17 , 0 19, 1 14 , 0 19 , 2 18 , 0 4 , 0      

2) Таблица идентификаторов 3) Таблица констант

номер идентификатор
x
y
номер константа