Задание 4.1A

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

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

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

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

  1. Создайте файл docs/specification/top-level-grammar.md — там будет спецификация в формате Markdown с описанием грамматики программы на вашем языке программирования
  2. Опишите в новом файле правила грамматики, выходящие за рамки выражений, например:
    • Правило для основной программы (можно назвать program, file или module)
    • Правила для инструкций (statements)
    • Правила для объявлений переменных (variable declarations)
    • Добавьте в файл описание семантических правил (например, запрет на повторное объявление переменных с тем же именем)
  3. Допишите в файле docs/specification/expressions-grammar.md правила для выражений, например:
    • Правило для доступа к переменным, как в выражении x = y = 5
  4. Проверьте, что теперь ваш язык поддерживает:
    • Переменные и/или константы
    • Инструкции, исполняемые последовательно
    • Инструкции ввода-вывода
  5. Проверьте расширенную грамматику на отсутствие левой рекурсии и левой факторизации, чтобы не создавать проблем в реализации рекурсивного спуска

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

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

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

Документ docs/specification/top-level-grammar.md пишется с использованием возможностей markdown: заголовков, таблиц, списков:

  1. В начале документа обязательно должны быть один или несколько примеров кода
  2. В середине документа опишите кратко
    • ключевые особенности языка
    • семантические правила (например, запрет на повторное объявление переменных с тем же именем)
  3. В конце документа опишите грамматику в виде блока кода на языке EBNF — см. EBNF для описания грамматик

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

1. Структура программы #

Структура программы зависит от парадигмы и решений аналитика.

Возможные на данном этапе варианты:

  1. Программа состоит из объявления точки входа, внутри которой находятся инструкции
    • пример: функция main в языках C / C++
    • пример: класс Program с функцией main в Java
  2. Программа состоит из инструкций и объявлений
    • пример: PROGRAM Name; VAR ...; BEGIN ... END. в языке Pascal
    • из инструкций и объявлений функций состоят простые скрипты на Python или JavaScript
  3. Программа состоит из выражений и объявлений
    • характерно для функциональных языков программирования
    • пример: язык Haskell

Язык Kaleidoscope следует функциональной парадигме — в нём программа состоит из выражений и объявлений функций/констант:

(* Программа находится в одном файле *)
program = top_level_statement, { top_level_statement } ;

(* Выражение либо объявление *)
top_level_statement = (
      function_or_constant_definition
      | extern_function_declaration
      | operator_definition
      | expression
   ), [ ";" ] ;

2. Область действия #

Scope переводится как «область действия» или «область видимости». Первый вариант перевода более точный, второй — более распространённый.

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

  1. Можно ограничить область видимости блоком кода
    • примеры: C/C++
  2. Можно ограничить область видимости функцией
    • примеры: Pascal, Python
  3. Существует глобальная область видимости — для переменных и констант, объявленных на верхнем уровне (top-level declarations).

Интересный факт: в языке JavaScript ключевые слова var и let задают разную область видимости и правила переопределения:

  • var x — переменная существует до конца функции и может быть повторно объявлена с тем же именем;
  • let x — переменная существует до конца блока (до закрывающей фигурной скобки) и не может быть повторно объявлена с тем же именем.

3. Переменные и константы #

Переменные могут работать по-разному в зависимости от решений аналитика:

  1. Если переменные объявляются явно, то доступ к необъявленной переменной считается ошибкой
    • повторное объявление переменной с тем же именем обычно тоже считается ошибкой
  2. Если переменные создаются присваиванием, то ошибкой считается использование переменной, которую не присваивали в данной области действия (scope)
  3. Аналитик может выбирать между переменными и константами:
    • можно поддерживать только изменяемые (mutable) переменные
    • можно поддерживать только неизменяемые (immutable) переменные
    • можно поддерживать оба вида — с похожим либо различным синтаксисом

Примеры языков, где поддерживаются как изменяемые, так и неизменяемые переменные:

ЯзыкОбъявление неизменяемой переменнойОбъявление изменяемой переменной
Rustlet x = init_expr;let mut x = init_expr;
JavaScriptconst x = init_expr;let x = init_expr;
Kaleidoscopedef x init_exprvar x = init_expr in expr

4. Ввод/вывод #

Аналитик выбирает способ поддержи ввода-вывода. Возможные варианты:

  1. Ввод-вывод с помощью встроенных функций, например: x = readInt(); writeLine(x * x)
  2. Ввод-вывод с помощью инструкций с ключевыми словами, например: read x; print x * x;
  3. Ввод-вывод с помощью особых операторов, например: -> x; <- x * x;
  4. Ввод-вывод с помощью встроенных объектов или модулей, например: Console.Writeln(x * x);

5. Виды инструкций #

Аналитик выбирает допустимые виды инструкций. Возможные варианты для выбора:

  1. Любое выражение является инструкцией: statement = expression | (* ... другие варианты правила *) ;
  2. Присваивание не является выражением, но является инструкцией: statement = assignment
  3. Отдельные инструкции для чтения и печати, например: print x + 10;
  4. Отдельные инструкции объявления переменных и/или констант, например: var x = y * 2;

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

Тогда вместо statement = expression ; вводят более ограниченные правила:

statement = assignment_statement
   | function_call_expression 
   | (* ... другие варианты правила *)

Такая грамматика разрешает использовать в качестве инструкции только выражения с побочными эффектами:

// допускается грамматикой:
var x = 10;
writeInt(x);

// не допускается грамматикой (не сохраняется результат, нет побочных эффектов):
x + 10;

6. Разделитель инструкций #

Эта лабораторная не требует реализации восстановления после ошибок.

Аналитик выбирает, нужны ли в языке разделители инструкций и какими они могут быть. Возможные варианты:

  1. Символы-разделители, такие как “;”
  2. Переносы строк как разделители
  3. Нет разделителей инструкций

Неочевидная задача разделителей — упрощать восстановление после ошибок разбора. Например, промышленный компилятор может:

  1. В случае появления ошибки разбора сообщать о ней и далее игнорировать все токены (лексемы) до разделителя (такого как точка с запятой)
  2. После получения разделителя обрабатывать файл дальше
  3. После завершения обработки файла всё равно сообщить об фатальной ошибке в духе fatal errors: 10 compilation errors

Такая стратегия помогает программисту получить больше обратной связи. Если же восстановления после ошибок нет, то программист увидит только первую ошибку и будет вынужден циклично устранять проблемы по одной, пока ошибки не закончатся.

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

  1. EBNF для описания грамматик
Previous 4. Таблицы символов Задание 4.2A Next