sigmarik/ast-standard

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

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

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

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

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

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

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

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

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

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

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

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

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

• Синтаксические деревья представляются в виде текстового файла, использующего кодировку ASCII.
• Символы, не входящие в набор ASCII являются недопустимыми.
• Пробельные символы, не находящиеся внутри лексемы, являются незначимыми и игнорируются.
• Числа могут записываться как в формате с десятичной точкой, так и без неё. При записи в формате с десятичной точкой после неё может быть указано не более трёх десятичных разрядов.

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

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

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

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

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.
• print(x) - выводит число x в стандартный поток вывода и возвращает значение x
• set_pixel(x, y, ch) - записывает символ ch в видеопамять, используя числа x и y в качестве его относительных координат. ch интерпретируется как код символа в таблице ASCII, дробная часть числа отбрасывается. x и y - числа от -1 до 1, интерпретируются как относительные координаты пикселя на экране относительно центра экрана. x - координата по горизонтали, y - координата по вертикали.
• flush() - обновляет экран, выводя содержимое видеопамяти.

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

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

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

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