Индивидуальные_задания

This is an old version of this page.

Go to most recent version Browse history

Индивидуальные задания

Везде в [ ] указано число баллов за каждое задание

disclaimer требования к заданию описаны не полностью и должны уточняться по ходу работы (git pull request, комментарии к коммитам, тестам и т.п.)

1. Переменные и области видимости [40]

begin
 var c;
 c = 1;
 begin
   var c;
   c = 2;  // используется локальная c
   write(c);
 end;
end

begin
 var c;
 c = 1;
 begin
   var c = 3;
   c = 2;
   write(global c); // global указывает, что используется "с" объявленная во внешнем блоке
   var m = global c;
   write(2*m*c);
 end;
end

[5] Добавить проверку областей видимости переменных. Необъявленные и повторно объявленные переменные должны приводить к ошибке. Для этого добавить таблицу символов.
[10] Добавить области видимости переменных в генератор кода
[3] Добавить инициализаторы переменных
[7] Добавить поддержку global во все проходы компилятора
[15] Создать визитор, который бы переносил все переменные в самую верхнюю возможную область видимости (c учетом конфликтов)

2. Метки, goto и таблица символов [40]

begin
  l: write(0);
  l1: write(1);
  goto l;
  goto ll; // ошибка
end

begin
  l: a = -2;
  l1: a = a + 1;
  if a then goto l1;
  exit; // завершает выполнение
  goto l; // этот оператор никода не выполнится
end

[5] Добавить метки в лексер, парсер и prettyprinter
[4] Добавить таблицу символов и проверку корректности имен меток в goto
[6] Добавить визитор, который преобразует циклы cycle в goto и if
[9] Добавить визитор, который строит управляющий граф программы
[10] Добавить поддержку меток в генератор IL-кода
[6] Добавить оператор exit и поиск недостижимого кода

3. Функции и параметры [40]

function f(a,b,c) 

 function m(x)
 begin
    return x*x
 end
 
var temp; 
begin
  temp = 0;
  temp = m(a);
  a = temp+b;
  return a+b-m(c)
end

begin
  var a,b,c; a = 1; b = 2; c = 3;
  write(f(a,b,c));
  write(@a)  
end

[10] добавить функции в лексер и парсер
[4] добавить поддержку вложенных функций
[6] добавить передачу параметров по ссылке ("@a") во все этапы компиляции
[10] добавить визитор, который строит граф вызовов
[10] добавить проверку областей видимости переменных внутри функций

4. Массивы и срезы [40]

  begin
     var a[10], b[3], c[4];
     write(a[1]);
     b = a[:4];
     c = a[7:];
     с = a[0:3:]; // начина с 1 с шагом 3
  end

  begin
     //var A[4] = <1,2,3,4>;
	 var A[4];
	 cycle x in a[0:3]
	   write(x);
	   var b[4] 
	 end
     
  end

[6] добавить поддержку статических массивов (определение и описание) в лексер и парсер
[6] добавить поддержку срезов массивов и арифметических операций над массивами в лексер и парсер
[14] добавить проверку совпадения размерностей массивов в выражениях (включая срезы). Например, c[0:4] = a[0:3:9] + b, но не c[0:4] = a[0:3:9] + c
[12] добавить поддержку статических массивов в генератор кода (без срезов)
[12] добавить циклы по элементам массива во все этапы компиляции

5. типы и их вывод [30]

begin
  int x = 2,y = 3; // float, bool, char
  var z = x+y, s = x-y;
  write(z)
end

begin
 char c; int  a = 1;
 string str = 'hello';
 var char = c + str[a];
 var char = a + c + str[a]; // ошибка
 write(char)
end

[15] Добавить встроенные типы int, float, bool, char во все стадии компиляции
[10] Реализовать директиву var, тип переменных в которой выводится из типа результата выражения-инициализатора (и вывод типов)
[5] Добавить тип string с оператором [индекс] и вывод типов из выражений со строковыми переменными и константами

6. типизированные массивы

begin
  int a[10];
  bool b[10];
  float f[10];
  int ib = b[0];
  
end

7. типы и структуры [40]


struct foo
  int a;
  char c;
  float f;
end

begin
  foo f;
  f.f = 5.6;
  f.a = 3;
  write(f.a)
  foo f1;
  f1 = f
end

[15] Добавить поддержку встроенных типов во все стадии компиляции
[15] Добавить поддержку структур во все стадии компиляции
[10] Добавить операцию присваивания переменных типа структура во все стадии компиляции

8. структуры и подсказки [40]

struct foo
  var a,b,c;
  // var m = 3
end

begin
  var f = new foo;
  foo.a = 1;
  write(f.a)
end

[15] Добавить поддержку структур во все стадии компиляции
[20] Реализовать сервис подсказок имен полей структуры: на вход подается текст программы и позиция курсора, на выходе - список допустимых имен полей, которые можно вставить после "." Например, "struct foo var a,b; end begin var f = new foo; write(a.<здесь курсор>) end" должно вернуть ["a","b"]
[5] Добавить выражения инциализации полей структуры.

9. классы с методами

10. функции-генераторы

11. циклы по массиву

поддержка var A[N]; cycle a in A s += a end; в лексер и парсер
...

12. функции и goto

function Foo(N) does
var i = N, Sum = 0;
Sum = 1; // при обычном вызове Sum = 1
         // иначе только инициализация
stage1 does:
  cycle 3 Sum += i; i+=1 end; result = Sum;
stage2 does:
  cycle 4 Sum += i end; result = Sum;
stage3 does:
  cycle 5 Sum += i; i-= 2 end; result = Sum;
return 
end

begin

read(t);
if t == 1 then
  goto Foo(5).stage1
  write(Foo.result)
  write(Foo(5))
end

[10] Эти особенные "функции" в лексере и парсере (+ выражения инициализации переменных) var допускается только в начале функций, в теле программы оно не нужно
[10] Контроль корректности объявления переменных и переходов
[10] Вложенные функции

13. модули и файлы

// file1.toy
module mymodule 
public foo(a,b,c);
public goo(x,y);
begin
  function foo(a,b,c)
  begin
  end;
  
  function goo(a,b,c)
  begin
  end; 
end

// file2.toy
from file1.toy import mymodule as mo;
begin
write(mo.foo(mo.goo(),1,1));
end;

добавить все необходимое в лексер и парсер
добавить проход "линковки" модулей в AST после их синтаксического разбора.
добавить эту функциональность в генератор кода

14. препроцессор, макросы и прагмы [32]

 #inlude otherfile.toy
 #def N 100
 #def yes
 begin
 #if yes
 var a,b;
 #else
 #end
 # def foo %1+%2
 #pragma tostderr // эта прагма должна заставить write вывести сообщение в стандартный поток ошибок 
 write(foo(a,b))
 end

[10] препроцессор для подстановки макросов (см. пример)
[10] прагмы (включая изменения в генераторе кода)
[6] include
[6] условная компиляция #if #else

15. типы шаблоны функций (элементарные) [40]

[15] добавить поддержку стандартных типов во все этапы компиляции
[10] добавить поддержку функций с типизированными параметрами во все этапы компиляции
[15] шаблоны функций

  function<T> foo(T a) 
    return a*a
  end

16. функции и lambda

function foo(n)
var i;
begin
  i = 1;
  cycle n
    i = i*2
  end
  return i;
end

begin
  write(foo(10));
  
  write((x)=>[i][cycle n i=i*2  end return i](10))
end

[6] функции с объявлениями локальных переменных в лексере и парсере
[8] lambda-функции вида (фор. параметры)=>[локальные переменные]тело

17. функции, inlining


define inline func(kind)
  if kind == 1 then
     s = 58
  else
     s = 89
  end;
  return s
end

begin
 a = 1;
 write(func(a))
 // 
 // if (a == 1) then temp_var1 = 58 else
 // temp_var1 = 89 end;
 // write(temp_var1)
end

[15] функции с поддержкой рекурсии во всех стадиях компиляции
[15] инлайнинг функций в AST, если указан квалификатор inline
[10] ограничение на глубину инлайнинга для рекурсивных функций

18. функции, параметры по умолчанию

19. функции, предусловия и постусловия [40]

function foo(x) 
begin
  return 1/x
end

begin
  write(foo(2))
end


function foo(x) 
pre
  assert x != 0
begin
  return 1/x
end
  assert 1
post

begin
  write(foo(0))
end

[6] функции в лексере и парсере
[10] предусловия и постусловия, в которых возможны только assert c аргументами функции и глобальными переменными в лексере и парсере
[15] проверка побочных эффектов в предусловиях и постусловиях (отсутствие присваиваний глобальным переменным, включая вызов функций с побочными эффектами)
[9] объявление вложенных функций (тоже с предусловиями)

20. интерпретатор [40]

[15] интерпретатор языка с максимальным набором функций из основных заданий
[15] проверка типов во время выполнения и литеральные константы встроенных типов: int, bool, float, char, string
[10] функция eval("<строка c исходным кодом>") которая выполняет программы на лету, читая их из строки (и учитывая значения глобальных переменных)

21. структуры и полноправные функции [40]


function foo(a,b,c) 
begin
  return object(
     a -> a,
     my_b -> b,
     my_c -> function(x,y) 
             begin
                 return (x*self.a - y*self.my_b)*c;
             end
  );
end

begin

 obj = foo(1,2,3);
 write(obj.my_c(2,2));
 
end

лексер и парсер (функции)
лексер и парсер (структуры)
pretty printer

21. списки

22. атрибуты

23. массивы и выражения-генераторы

   begin
     int M[10];
     write(a) for a in M;
     
   end

24. перегрузка функций [40]

типы переменных
функции с типизированными параметрами и их вызов
проверка соответствия типов формальных и фактических параметров
перегрузка функций, проверка наличия подходящей функции и вывод ошибок

25. строковые операции

 begin
   a = 'string1';
   b = 'string2';
   c = (a + b + c[2]).substr(0,3);
   write(c.toupper());
 end

26. наследование функций [40]

// функция всегда возвращает значение self т.е. ссылку на себя
// все поля предка доступны в потомке
// создание новой функции происходит при указании имени без параметров
function foo(a)
  self.m_a = a;
  write(a);
end;

function goo(b) from foo 
  write(b + self.m_a)
end;

begin
  var f = foo;
  var g = goo;
  foo(1);
  goo(2);
  foo.a = 3;
  goo(2);
end

30. Транслятор в JavaScript [17]

begin
  var a,b,c;
  a = 0;
  b = 2;
  c = 3;
  if a then 
   a = 0
  else a = b+c;
  write(a)
end

нужно перевести в исполняемый код на JavaScript:

  // var a,b,c;
  // a = 0; b = 2; c = 3;  
  let a = 0, b = 2, c = 3;
  if (a) {
     a = 0;
  } else {
     a = b+c;
  }
  console.log(a);

[10] Написать визитор, переводящий AST в программу на JavaScript
[7] Добавить проход, позволяющий найти инициализаторы переменных и выводить их в JS в один оператор

30. Транслятор в C# [17]

begin
  var a,b,c;
  a = 0;
  b = 2;
  c = 3;
  if a then 
   a = 0
  else a = b+c;
  write(a)
end

нужно перевести в исполняемый код на C#:

  using System;
   
  namespace default {
  
  public class MainClass {
  
  public static void main(string[] args) {
  // int a,b,c;
  // a = 0; b = 2; c = 3;  
  var a = 0, b = 2, c = 3;
  if (a != 0) {
     a = 0;
  } else {
     a = b+c;
  }
  Console.WriteLine(a);
  }
  }
  }

[10] Написать визитор, переводящий AST в программу на C#
[7] Добавить проход, позволяющий найти инициализаторы переменных и выводить их в C# в один оператор

31 Фиксированная форма записи и редактор [40]

1_____begin
2_____var x,y;
3l1___cycle 2 y = x+x;
3_____write(y);
4_____if y goto l1
5_____end

первые символы каждой строки программы - шестнадцатеричный номер строки и место для метки.

[10] Добавить поддержку такой записи (включая метки и goto) в лексер и парсер
[15] написать текстовый редактор для таких программ, который бы вставлял номера строк автоматически
[10] реализовать в текстовом редакторе функцию подсказок имен меток при вводе goto
[5] поддержка меток и goto в генераторе IL кода

32 Трассировка и отладка [?]

Добавить к существующему генератору кода возможность трассировки программы с указанием строк в тексте и значений переменных. В созданный генератором код можно вставить вызовы функций, которые бы добавляли записи в трассу: строка в тексте, которая соответствует выполняемому оператору, имена и значения используемых переменных (если возможно).

Admin message