Язык постфиксного промежуточного представления.
К А З А Н С К И Й Г О С У Д А Р С Т В Е Н Н Ы Й
У Н И В Е Р С И Т Е Т
Кафедра теоретической кибернетики
К У Р С " Языки и методы программирования "
( для студентов 2 куpса )
Семестровое задание №1.
Цель: Отработка техники построения программ лексического и синтаксического
анализа на основе языка программирования ПАСКАЛЬ(DELPHI). Изложение
дальнейшего материала дается в терминах ПАСКАЛЯ, однако задания можно выполнять также на С++.
Предусматривается программирование отдельных алгоритмов синтаксического анализа и компиляции на основе рекурсивных определений, являющихся наиболее адекватными для упомянутого класса задач. В качестве исходного текста , являющегося объектом обработки, используются язык арифметических выражений и язык функционального программирования на основе ЛИСПа.
Срок выполнения: 2-месяца.
Пояснения к заданию:
Язык арифметических выражений.
Выражения строятся из простых переменных , констант (типа integer или real) ,
знаков операций (+ , - , * , / , DIV , MOD) и функций.
Например : (a1+a2)*(b1-b2 DIV b3)-15+F(x,y,z).
Язык фукционального программирования.
Программы строятся в виде суперпозиции функций. Например :
F1(G1(x,y),G2(a,b,c)). Каждая функция представляется в виде
полноскобочного представления вида (F , p1, p2, … , pn) , где
F-наименование функции , p1, p2, … , pn – аргументы (параметры) ,
каждый из которых является простой переменной , константой
(типа integer , real , boolean) или в свою очередь полноскобочным выражением.
Например (F1,(G1,x,y),(G2,a,b,c)) .
Язык префиксного промежуточного представления.
Промежуточное представление программы получается в результате полного синтаксического разложения программы и затем используется для
дальнейшей генерации кода или интерпретации. Промежуточное представление является структурным списком , который описывается
динамическим типом языка ПАСКАЛЬ.
  KOD
| NAME | LL | RL |
type list=^element;
element=record
KOD:0..4;
NAME:string;
LL:list;
RL:list
end;
{ 1- если поле NAME определяет имя функции (или знак операции)
KOD= { 2- если поле NAME определяет имя переменной
{ 3- если поле NAME определяет константу
{ 4- поле NAME – пустая строка , поле LL ссылается на другой
{ список (нижний уровень иерархии)
LL-ссылка на нижний уровень иерархии , RL ссылка на следующий элемент данного уровня иерархии.
LL=> NIL , если KOD= 1 | 2 | 3
Пример:( F , x ,(G,z,15))
 |  |  |
|
NIL
NIL NIL
|
|
NIL
 |  |  | |||||||||
| |  |  | |||||||||
NIL
Язык постфиксного промежуточного представления.
В постфиксном представлении знак операции (функции) указывается после аргументов.
Вид представления:
 |
В дальнейшем префиксное промежуточное представлении будем называть просто промежуточным представлением, специально выделяя постфиксное представление.
Пример: ((15,z,G),x,F) (префиксное представление ( F , x ,(G,z,15)))
NIL
 |  |  | |||
NIL NIL
NIL
 |  |  |
NIL NIL NIL
Примерные задания.
1. Преобразовать арифметическое выражение, не содержащее скобок (и соответственно функциональных символов) в промежуточное представление.
Например , A1+B1-X/15.5 .
2. Получить из промежуточного представления арифметическое выражение.
3. Преобразовать полноскобочное представление функциональной программы в промежуточное представление.
5. Получить из промежуточного представления функциональной программы
полноскобочное представление.
6.Запрограммировать процесс интерпретации промежуточного представления арифметического выражения, ограничившись только знаками операций + , - ,* , / .
В качестве исходных данных кроме промежуточного представления использовать
таблицу значений переменных, организованную в виде массива.
7. Преобразовать арифметическое выражение, не содержащее скобок ( и соответственно функциональных символов) в полноскобочное представление.
Например , A1+B1-X/15.5 => ( - , (+ , A1, B1) , ( / , X , 15.5 ))
8. Преобразовать полноскобочное представление арифметического выражения в обычное арифметическое выражение.
Например , ( - , (+ , A1, B1) , ( / , X , 15.5 )) => A1+B1-X/15.5
9. Выполнить проверку парности открывающих и закрывающих скобок в
обычном арифметическом выражении.
10. Выполнить проверку парности открывающих и закрывающих скобок в
полноскобочном представлении.
11. Выполнить проверку соответствия типов в операциях (функциях) на
основе промежуточного представления. Тип переменной определяется
первой буквой ее наименования (I – Integer , R-real , B-Boolean). Если
на каком этапе обнаруживается ошибка несоответствия типов , процесс проверки завершается с выдачей сообщения об ошибке (далее не проверять). В качестве исходных данных кроме промежуточного представления использовать
таблицу схем операций (функций). Например , (+,Integer ,integer) => integer .
12. На основе промежуточного представления создать линейный список, содержащий
список наименований используемых операций (функций).
13. Преобразовать префиксное промежуточное представление в постфиксное.
14. Преобразовать постфиксное промежуточное представление в префиксное.
15.Запрограммировать процесс интерпретации постфиксного промежуточного представления арифметического выражения, ограничившись только знаками операций + , - ,* , / .
В качестве исходных данных кроме промежуточного представления использовать
таблицу значений переменных, организованную в виде массива.
16. Выполнить лексический анализ полноскобочного представления , ограничившись только знаками операций + , - ,* , / (не используя функциональные символы). Суть лексического анализа сводится к проверке правильности написания переменных , констант и знаков операций . Например :
(+,(-,a1,b1),(*,c1,15)) – выражение корректное ; (+,(-,a,b),(*,c1,1d1)) – в выражении допущена ошибка (1d1- не является идентификатором) .
17.Для заданного промежуточного представления получить списки наименований операций , функций , переменных и констант. Например , если промежуточное представление получено из выражения F(X1,255)+G(X1*Y1/16,Y2) , то в результате мы должны получить (+,*) –список операций , (F,G) –список функций , (X1,Y1,Y2) – список переменных , (255,16) – список констант.
18.Для заданного полноскобочного представления получить списки наименований операций , функций , переменных и констант. Например , если промежуточное представление получено из выражения F(X1,255)+G(X1*Y1/16,Y2) , то в результате мы должны получить (+,*) –список операций , (F,G) –список функций , (X1,Y1,Y2) – список переменных , (255,16) – список констант.