Язык постфиксного промежуточного представления.

      Комментарии к записи Язык постфиксного промежуточного представления. отключены

К А З А Н С К И Й Г О С У Д А Р С Т В Е Н Н Ы Й

У Н И В Е Р С И Т Е Т

Кафедра теоретической кибернетики

К У Р СЯзыки и методы программирования

( для студентов 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))

1 G

NIL

NIL NIL

2Z
315

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) – список констант.

Статьи к прочтению:

04 Психология сознания


Похожие статьи: