Задание 5.1A

Лабораторная №5 — задание 5.1A #

Нужно добавить в спецификацию своего языка поддержку ветвлений, циклов и пользовательских функций.

Порядок выполнения #

Содержание грамматик зависит от особенностей вашего языка — это описано далее. При разработке грамматики полезно проанализировать грамматики двух языков, примеры на которых вы готовили в предыдущих лабораторных.

  1. Отредактируйте файл docs/specification/top-level-grammar.md с описанием грамматики программы на вашем языке программирования
    • опишите в этом файле правила грамматики для ветвлений и циклов
    • опишите в этом файле правила грамматики для определения пользовательских функций
  2. Отредактируйте файл docs/specification/expressions-grammar.md с описанием правил грамматики выражений
    • опишите в этом файле вызов функций
  3. Проверьте расширенную грамматику на отсутствие левой рекурсии и левой факторизации, чтобы не создавать проблем в реализации рекурсивного спуска

Если вы проектируете функциональный язык программирования, то ветвления и циклы будут выражениями, а значит и описывать их нужно в файле docs/specification/expressions-grammar.md.

Общие требования к спецификациям #

  1. Все спецификации находятся в каталоге docs/specification/ основной ветки вашего репозитория
  2. Все спецификации согласуются между собой — например, список ключевых слов в документе lexical-structure совпадает с набором ключевых слов, используемых в EBNF-грамматиках в остальных документах
  3. Все спецификации имеют ясную структуру — например, правила EBNF-грамматик описываются в markdown только блоком кода с языком ebnf, а не списками или иными способами

Требования к грамматике языка #

Рекомендуется на данном поддерживать в языке ровно один тип данных — на выбор либо целые числа, либо числа с плавающей точкой. Вы можете поддерживать несколько типов данных при желании.

  1. Спецификации языка пишутся с использованием возможностей markdown: заголовков, таблиц, списков.
  2. В конце спецификации должна быть грамматика в виде блока кода на языке EBNF — см. EBNF для описания грамматик

Далее описаны рекомендации по проектированию своего языка.

1. Выражения или инструкции #

Требования:

  1. Если вы проектируете императивный язык, то ветвления и циклы относятся к инструкциям (statements)
    • подумайте, как решить проблему висячего else (dangling else) и опишите решение в спецификации
  2. Если вы проектируете функциональный язык, то ветвления и циклы являются выражениями (expressions), при этом любое выражение всегда возвращает результат
    • например, для ветвлений if вы либо помечаете ветку else обязательной, либо определяете в спецификации неявное значение на случай, когда условие if не выполняется

Пример EBNF для императивного языка:

statement = (* ...другие варианты *)
    | if_statement
    | for_statement
    | assignment_statement ;

if_statement = "if"
    , "(", expression, ")"
    , statement
    , [ "else", statement ] ;

for_statement = "for"
    , "(", assignment_statement, expression, assignment_statement, ")"
    , statement ;

Пример EBNF для функционального языка:

(* Первичные выражения *)
primary_expression = (* ...другие варианты *)
    | if_else_expression
    | for_loop_expression ;

(* Ветвление: ветка if является обязательной *)
if_else_expression = "if"
    , "(", expression, ")"
    , expression
    , "else"
    , expression ;

(* Цикл for *)
for_loop_expression = "for",
    , "(", assignment_expression, expression, assignment_expression, ")"
    , "do"
    , expression ;

2. Процедуры и функции #

Справка:

  • Процедуры — подпрограммы, которые не возвращают результата и вызываются только ради побочных эффектов;
  • Функции — подпрограммы, которые возвращают результат и могут иметь, а могут и не иметь побочных эффектов;
  • Примеры побочных эффектов: ввод, вывод, изменение глобальной переменной, системный вызов ОС.

Требования:

  1. Если вы проектируете императивный язык, то вы можете предусмотреть поддержку процедур либо функций без возвращаемого значения. Если вы не планируете поддержку процедур, то напишите об этом в спецификации.
  2. Для функционального языка поддержка процедур не нужна — но в будущем вы можете добавить поддержку специального типа, обозначающего отсутствие значения.

3. Инструкция return #

Требования:

  • Для императивного языка в функциях потребуется инструкция return либо альтернативное решение для возврата значения.
  • Для функционального языка можно явно обозначить правило: тело функции — это одно выражение. При этом может быть полезен оператор последовательности выражений, возвращающий результат последнего выражения.

Пример для императивного языка:

statement = (* ...другие варианты *)
    | return_statement ;

(* Инструкция возврата из функции или процедуры *)
return_statement = "return", [ expression ] ;

Пример для функционального языка:

(* Тело функции состоит из одного выражения. *)
function_declaration = "function"
    , "(", parameter_list, ")"
    , expression ;

(* Выражение может быть последовательностью выражений. *)
expression = (* ...другие варианты *)
    | sequence_expression ;

(* Последовательность выражений, разделённая запятыми. Возвращается результат последнего из выражений. *)
sequence_expression = expression, { ",", expression } ;

4. Параметры и аргументы функции #

Справка:

  • Функции без параметров нужны только ради побочных эффектов либо как альтернатива константам.
  • Порядок вычисления аргументов вызова функции может иметь значение, если при вычислении аргумента возникают побочные эффекты — например, из-за вызова ещё одной функции: sum(readInt(), readInt()).

Требования:

  1. Определите правила грамматики для списка параметров в объявлении функции
    • Определите, допускаются ли в языке функции без параметров.
    • Определите, содержит ли объявление параметра указание на его тип данных
  2. Определите правила грамматики для списка аргументов при вызове функции
    • Укажите в тексте спецификации порядок вычисления аргументов функции

Дополнительные возможности #

Чтобы сделать язык сложнее, вы должны добавить в него четыре расширенные возможности из списка ниже:

  1. Логические операторы “И”, “ИЛИ”, “НЕ”
    • Эти операторы могут работать в языке, где есть только числовой тип данных
    • В этом случае они возвращают 1 в качестве значения “Истина”, 0 в качестве значения “Ложь”
  2. Short-circuit evaluation для логических операторов
  3. Ветвление switch или его аналог — в дополнение к обычному ветвлению
    • Подумайте, как должен работать case x: без последующего break — аналогично языкам C/C++ или иначе?
  4. Тернарный оператор — в дополнение к обычному ветвлению
    • Подумайте, каким должен быть приоритет тернарного оператора
  5. Два типа циклов с условием до первой итерации и после первой итерации
    • Пример: while (condition) body и do body while (condition)
    • Вы можете использовать различный синтаксис для таких циклов
    • Пример из Pascal: WHILE condition DO body и REPEAT body UNTIL condition
  6. Два типа циклов для итерации по условию и итерации по диапазону значений
    • Пример: while (condition) body) и for i = 0 to 10 do body
  7. Инструкция break для прерывания цикла
    • Если у вас есть несколько типов циклов, то break работает для всех
    • Если у вас есть switch, то break работает и для него
  8. Инструкция continue для продолжения цикла
    • Если у вас есть несколько типов циклов, то continue работает для всех
    • Если у вас есть switch, то вы можете применять continue и для него с целью перехода на следующую метку
  9. Взаимная рекурсия, то есть возможность функций A и B вызывать друг друга рекурсивно
    • Подумайте, нужно ли для взаимной рекурсии специальное правило грамматики для предварительного объявления функции без описания тела этой функции
  10. Поддержка возврата нескольких значений из функции
  11. Поддержка out параметров функции, в которые записываются дополнительные результаты функции

Справочные материалы #

  1. Пример PsKaleidoscope
  2. EBNF для описания грамматик
Previous 5. Поток выполнения Задание 5.2A Next