К А З А Н С К И Й Г О С У Д А Р С Т В Е Н Н Ы Й
У Н И В Е Р С И Т Е Т
Кафедра теоретической кибернетики
К У Р С " Языки и методы программирования "
(для студентов 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) – список констант.
