Стандарт представления синтаксических деревьев

Цели стандарта

Создателями стандарта ставится цель создания унифицированного формата текстового представления синтаксических деревьев, генерируемых front-end-компиляторами при распознавании файлов программ на различных высокоуровневых языках.

Список используемых сокращений

В тексте стандарта используются следующие сокращения

• ЯВУ - язык программирования высокого уровня

Поставленные задачи

Создаваемые ЯВУ должны уметь решать каждую из нижеприведённых задач:

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

Требования к стандарту

При создании стандарта были выдвинуты следующие требования:

1. Универсальность. Программа, написанная написанная на целевом ЯВУ должна быть корректно представима в формате, регламентируемом стандартом.
2. Ориентированность на задачу. Стандарт должен учитывать специфику проблем, решаемых при помощи программ на целевых ЯВУ.
3. Простота в реализации. Стандарт должен быть достаточно естественным, чтобы создатели компиляторов для целевых ЯВУ не испытывали чрезмерных сложностей при следовании ему.

Общие положения стандарта

• Синтаксические деревья представляются в виде текстового файла, использующего кодировку ASCII.
• Символы, не входящие в набор ASCII являются недопустимыми.
• Пробельные символы, не находящиеся внутри лексемы, являются незначимыми и игнорируются.
• Числа могут записываться как в формате с десятичной точкой, так и без неё. При записи в формате с десятичной точкой после неё может быть указано не более трёх десятичных разрядов.
• Любое синтаксическое дерево программы на целевом ЯВУ обязано содержать определение функции main(), не принимающей аргументов. Функция main() считается точкой входа в программу.
• Любая объявленная функция обязана содержать узел типа RET (см. Типы узлов), лежащий в поддереве правого сына узла объявления функции, но не в поддереве никакого другого узла типа BLOCK.
• Все функции и переменные должны быть объявлены до своего использования. Порядок объявлений определяется "post-order" обходом дерева.
• Поддерево узла типа BLOCK (см. Типы узлов) задаёт область видимости. Не допускается использование переменной вне её области видимости. Глобальные переменные (т.е переменные, объявленные вне какого либо блока) имеют глобальную область видимости и доступны из любой точки программы.

Формат записи узла дерева

Каждый узел дерева записывается в фигурных скобках ('{' и '}'). Внутри фигурных скобок через запятую записываются тип узла, хранимое значение, левый дочерний узел, правый дочерний узел. Пустой узел обозначается пустой парой фигурных скобок ("{ }").

Если правый дочерний узел пуст, пустым обязан быть и левый дочерний узел (т.е. если узел унарный, то его единственный ребёнок - правый).

Далее приведено формальное описание грамматики записи синтаксического дерева.

G    ::= Node '\0'
Node ::= ('{' _ '}') | ('{' _ Type _ ',' _ ',' Val _ ',' _ Node _ ',' _ Node _ '}')
_    ::= [' ', '\n', '\t', '\v', '\f', '\r']*
Type ::= "DEFS" | "NVAR" | "NFUN" | "BLOCK" | "ARG" | "OP" | "SEQ" |
         "ASS" | "WHILE" | "IF" | "BRANCH" | "CALL"  | "PAR" | "RET" |
         "CONST" | "VAR"
Val  ::= Num | Name | Op | "NULL" 
Num  ::= [0-9]+ ('.'[0-9]? [0-9]? [0-9]? )?
Name ::= [A-Za-z_]+ [A-Za-z0-9_]*
Op   ::= "ADD" | "SUB" | "MUL" | "DIV" | "NEG" |
         "AND" | "OR"  | "NOT" |
         "GEQ" | "LEQ" | "GT" | "LT" | "EQ" | "NEQ"

Типы узлов

Список определений DEFS

Список глобальных определений функций и переменных.

• Значение: NULL
• Левый сын: NVAR или NFUN
• Правый сын: DEFS или пустой узел

Определение переменной NVAR

Определение и инициализация глобальной либо локальной переменной.

• Значение: имя переменной
• Левый сын: пустой узел
• Правый сын: OP, CONST, VAR или CALL

Определение функции NFUN

Определение новой функции.

• Значение: имя функции
• Левый сын: ARG
• Правый сын: BLOCK

Унарная либо бинарная операция OP

Арифметическая, логическая операция или операция сравнения.

• Значение: тип операции (см. раздел Типы операторов)
• Левый сын: OP, CONST, VAR, CALL или пустой узел
• Правый сын: OP, CONST, VAR или CALL

Список аргументов ARG

Список формальных аргументов функции.

• Значение: имя аргумента
• Левый сын: пустой узел
• Правый сын: ARG или пустой узел

Блок кода BLOCK

Блок кода с собственной областью видимости.

• Значение: NULL
• Левый сын: пустой узел
• Правый сын: SEQ

Последовательность команд SEQ

Последовательность команд и объявлений.

• Значение: NULL
• Левый сын: BLOCK NVAR, ASS, IF, WHILE, RET или CALL
• Правый сын: SEQ или пустой узел

Присваивание ASS

Изменение значения переменной.

• Значение: имя переменной
• Левый сын: пустой узел
• Правый сын: OP, CONST, VAR или CALL

Цикл WHILE

Цикл с предусловием.

• Значение: NULL
• Левый сын: OP, CONST, VAR или CALL
• Правый сын: BLOCK, ASS, IF, WHILE, RET или CALL

Условная конструкция IF

Конструкция условного выполнения кода.

• Значение: NULL
• Левый сын: OP, CONST, VAR или CALL
• Правый сын: BRANCH

Ветвление BRANCH

Ветви кода при условной конструкции.

• Значение: NULL
• Левый сын: BLOCK, ASS, IF, WHILE, RET или CALL
• Правый сын: BLOCK, ASS, IF, WHILE, RET, CALL или пустой узел

Вызов функции CALL

Вызов функции с передачей параметров.

• Значение: имя функции
• Левый сын: пустой узел
• Правый сын: PAR

Параметры функции PAR

Фактические аргументы функции, передаваемые при вызове.

• Значение: NULL
• Левый сын: OP, CONST, VAR или CALL
• Правый сын: PAR или пустой узел

Возврат из функции RET

Завершение выполнения функции с возвращением значения.

• Значение: NULL
• Левый сын: пустой узел
• Правый сын: OP, CONST, VAR или CALL

Число CONST

Действительная численная константа с фиксированной точностью.

• Значение: число с фиксированной точкой (не более трёх знаков после десятичной точки)
• Левый сын: пустой узел
• Правый сын: пустой узел

Переменная VAR

Обращение к объявленной ранее локальной или глобальной переменной.

• Значение: имя переменной
• Левый сын: пустой узел
• Правый сын: пустой узел

Типы операторов

Узлы типа OP в качестве значения содержат одно из следующих значений:

• Бинарные операции
  • ADD арифметическое сложение
  • SUB арифметическое вычитание
  • MUL арифметическое умножение с фиксированной точностью
  • DIV арифметическое деление с фиксированной точностью
  • AND логическая конъюнкция
  • OR логическая дизъюнкция
  • LT меньше
  • GT больше
  • LEQ меньше или равно
  • GEQ больше или равно
  • EQ равно
  • NEQ не равно
• Унарные операции
  • NEG арифметический унарный минус
  • NOT логическое отрицание

Стандартная библиотека

Для решения поставленных перед стандартом задач, авторами стандарта было принято решение, о создании набора функций, не требующих явного объявления в коде на целевом ЯВУ, но при этом всегда доступных для использования. В целях предотвращения конфликтов имён, в дереве не должны встречаться узлы объявления функций с именами, совпадающих с именами функций стандартной библиотеки.

В стандартную библиотеку входят следующие функции:

• sqrt(x) - возвращает значение квадратного корня из x, вычисленное с фиксированной точностью.
• abs(x) - возвращает абсолютную величину x.
• read() - возвращает число, считанное из стандартного потока ввода.
• print(x) - выводит число x в стандартный поток вывода и возвращает значение x.
• set_pixel(x, y, ch) - записывает символ ch в видеопамять, используя числа x и y в качестве его относительных координат. ch интерпретируется как код символа в таблице ASCII, дробная часть числа отбрасывается. x и y - числа от -1 до 1, интерпретируются как относительные координаты пикселя на экране относительно центра экрана. x - координата по горизонтали, y - координата по вертикали. Возвращает значение ch
• flush() - обновляет экран, выводя содержимое видеопамяти. Возвращает число 1.

Рекомендации по использованию

Если ну ооочень захочется, стандарт можно не соблюдать т.к. он - общепризнанное г**но.

Как поблагодарить нас

Ну оплату за стандарт занесёшь в комнату №123, там дверь может упасть и не бойся ведра тараканов в углу, но там брось пачку на верхнюю полку косого шкафа в место, где там почище.