[Nitra] Пример простого языка вычисляющего выражения
От: VladD2 Российская Империя www.nemerle.org
Дата: 02.12.15 07:31
Оценка: 21 (2)
#Имя: wiki.nitra.SimpleLanguage
В качестве примера опишу создание простого (но тем не менее не тривиального) языка.

Этот язык создан в целях демонстрации того чтобы на простом примере продемонстрировать как использовать AST, декларации, символы, области видимости (Scope's) и зависимые свойства для типизации. Для понимания проходящего сначала рекомендую прочесть Описание подсистемы сбора информации «Nitra»
Автор(ы):
.

Для начала пример кода на этом языке:
var x = y + 2 * z;
var z = y + 3;
var y = 1;


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

Особенность данного примере в том, что он не порождает ничего. Он только демонстрирует расчеты на зависимых свойствах. Аналогом этому примеру является свертка констант (constant folding) в языках программирования общего назначения.

Весь код (без комментариев) этого примера доступен здесь.

Для начала опишем синтаксис:
[cut]
syntax module SampleSyntax
{
  using Nitra.Core; // https://github.com/JetBrains/Nitra/blob/master/Nitra/Nitra.Runtime/Core.nitra
  using Nitra.CStyleComments; // https://github.com/JetBrains/Nitra/blob/master/Nitra/Nitra.Runtime/CStyleComments.nitra

  // директива keyword regex приказывает генератору парсеров вставлять правило S за литералами
  // соответствующими регулярной грамматике ['a'..'z', '_'..'_']+. Это нужно, чтобы парсер не
  // распознавал ключевое слово "var" в конструкции вида "varx= 42", а считал varx единым идентификатором.
  keyword regex ['a'..'z', '_'..'_']+ rule S;

  regex Keyword = "var";

  // это и последующее правило описывает идентификатор языка.
  // В Нитре поддерживается автоматическое связывание имен, по этому идентификатор 
  // разделяется на правило объявляющее имя символа (в данном случае "Name")
  // и правило описывающее ссылку на имя (в данном случае "Reference").
  // Атрибут "Name" производит автоматическое отображение идентификатора на предопределенный
  // в библиотеке Nitra.Runtime.dll ast типа Name: 
  // https://github.com/JetBrains/Nitra/blob/master/Nitra/Nitra.Runtime/Declarations/Name.nitra.
  [Name]
  token Name = !Keyword IdentifierBody;

  // Атрибут "Reference" производит автоматическое отображение идентификатора на предопределенный
  // в библиотеке Nitra.Runtime.dll ast типа Reference:
  // https://github.com/JetBrains/Nitra/blob/master/Nitra/Nitra.Runtime/Declarations/Reference.nitra.
  [Reference]
  token Reference = !Keyword IdentifierBody;

  // Стартовое правило. Разбирает 0 или более переменных (описанных в правиле VariableDeclaration).
  // nl - это маркер указывающий претипринтеру, что переменные нужно разделять переносом строки.
  [StartRule]
  syntax TopRule = (VariableDeclaration nl)*;

  // Правило описывающее переменную. Обратите внимание, что для указания имени мы 
  // использовали правило Name - это нужно для автоматического порождения символа для переменной.
  syntax VariableDeclaration = "var" sm Name sm "=" sm Expression ";";

  // Expression - Выражение нашего языка. В Expression описывается несколько альтернатив.
  // В Nitra единственный способ сделать набор альтернатив (т.е. связать правила по ИЛИ)
  // это описать расширяемое правило. Каждая альтернатива отделяется знаком "|" (шпалой, как мы ее называем).
  syntax Expression
  {
    | [SpanClass(Number)] Num = Digits // альтернатива разбирающая число
      {
        regex Digits = ['0'..'9']+; // вложенное правило типа regex разбирающее последовательность цифр - число
      }

    | Braces = "(" Expression ")"; // очевидно - скобки

    | Variable = Reference; // ссылка на другие переменные. 

  precedence Sum: // группа приоритетов для операторов "+" и "-"
    | Sum = Expression sm Operator="+" sm Expression; // оператор "+". 
    | Sub = Expression sm Operator="-" sm Expression; // sm - это маркер заставляющий претипринтер напечатать пробел

  precedence Mul: // Mul имеет более высокий приоритет нежели Sum но более низкий чем Unary
    | Mul = Expression sm Operator="*" sm Expression; // конструкция "Operator=" задает имя образуемому подправилом полю
    | Div = Expression sm Operator="/" sm Expression;

  precedence Unary:
    | Plus  = Operator="+" Expression
    | Minus = Operator="-" Expression
  }
}

[/cut]
Скормив этот файл nitra и получив dll мы уже получим возможность забирать код на нашем языке, подсветку и претипринт.

Чтобы наш можно было использовать из IDE или из тестовой утилиты нужно написать еще один файл Sample-Language.nitra с описанием языка:
language Sample
{
  syntax module SampleSyntax start rule TopRule;
}

Здесь SampleSyntax — это имя описанного выше синтаксического модуля, а TopRule имя стартового правила. Еще в этом файле может быть множество информации: расширение файла, информация об авторе, информация о стилях подсветки и т.п. Как это выглядит для более серьезного языка можно посмотреть здесь. Описание языка для самой Nitra.

Теперь нам нужно писать AST нашего языка в которых будут располагаться вычисления необходимые нам. AST находится в файле Sample-Ast.nitra:
[cut]
using Nitra;
using Nitra.Declarations;
using Nitra.Runtime.Binding;

// Стартовый AST. Обычно он называется CompileUnit, так 
// как описывает код отдельного файла.
ast Top
{
  // Зависимое свойство хранящее TableScope. TableScope находится в библиотеке 
  // и предоставляет функциональность таблицы имен. По совместительству TableScope
  // является областью видимости, и может использоваться в формировании более 
  // сложных областей видимости.
  // Значение этого свойства задается ивзне. В реализации интерфейса IProjectSupport (см. ниже)
  in ContainingTable : TableScope;

  // Данное присваивание присваевает таблицу имен на которую ссылается ContainingTable
  // всем AST-ам переменных (их свойствам ContainingTable). Variables - это структурная 
  // коллекция, а у них в Nitre автоматически генерируются свойства имеющие тот же тип и имя, 
  // что свойство у элемента коллекции. Подробнее см.
  // http://rsdn.ru/article/nitra/Nitra-Ast-and-Symbols-doc.xml#EAEAC
  Variables.ContainingTable = ContainingTable;

  // Структурное поле Variables хратит список AST-ов переменных.
  // Значение этого поля заполняется путем отображения на него дерева разбора.
  // Как это делается можно будет увидеть ниже.
  Variables : Variable*;
}

// Variable описывает декларацию переменной в нашем языке.
// Декларация - это особый вид AST, который порождает новый символ.
// Для описания декларации используем синтаксис "declaration", а не "ast".
// Декларации неявно унаследованы от Declaration:
// https://github.com/JetBrains/Nitra/blob/master/Nitra/Nitra.Runtime/Declarations/Declaration.n
// В Declaration объявлено структурное свойство Name и зависимое свойство ContainingTable.
// Для каждой декларации автоматически создается соответствующий ей символ.
declaration Variable
{
  // Декларация может содержать секцию symbol, в которой описываются зависимые 
  // свойства символа поражаемого деклараций. Собственно задача типизации вычислить
  // и собрать данные с AST и поместить их в свойства символов. Набор символов и будет
  // детальным описанием нашей программы.
  symbol
  {
    Kind = "var"; // Kind - это предопределенное свойство используемое при визуализации.

  // Директива stage позволяет задать стадию на которой могут быть вычисленные зависимые 
  // свойства объявленные после нее. Стадии нумеруются с нуля.
  stage 1: 
    // зависимое свойство которое будет хранить результат вычисления 
    // инициализирующего выражения.
    in Result : double; 
  }

  // Зависимое свойство ContainingTable унаследовано от неявного предка Declaration.
  // По этому нам не надо объявлять его явно.
  //in ContainingTable : TableScope;
  // Это свойство используется Nitra для размещения символа автоматически создаваемого 
  //по декларации. Символ будет создан как только будет задано значение этого свойства.

  // Передаем область видимости выражению. Она будет использоваться для автоматического
  // связывания имен.
  Expression.Scope = ContainingTable;
  // Помещаем результат вычисления выражения в свойство Result символа порождаемого для переменной.
  Symbol.Result    = Expression.Result;

  // Структурное свойство содержащее AST выражения инициализирующего переменную. 
  // Заполняется при отображении (см. отображение ниже).
  Expression : Expression;
}

// Абстрактный базовый AST описывающий выражение.
abstract ast Expression
{
stage 1:
  // Обратите внимание, на то, что Scope выражения задан на стадии 1. Это приводит к тому, что к
  // моменту начала его использования в Scope попадут все символы переменных имеющиеся в программе.
  // Так же обратите внимание на то, что тип данного свойства "Scope". Scope - это абстрактный тип
  // объявленный в библиотеке. Все области видимости обязаны наследоваться от него. Это поволяет
  // формировать сложную структуру областей видимости. Подробнее см. раздел 
  // "Области видимости, таблицы имен и связывание"
  // http://rsdn.ru/article/nitra/Nitra-Ast-and-Symbols-doc.xml#EPFAE
  in  Scope  : Scope;
  out Result : double;
}

// AST хранящий значение числа (числового литерала) в нашем языке.
// Он унаследован от Expression и не является абстрактным (может быть создан его экземпляр).
ast Number : Expression
{
  // Берем значение числа или 0, если его не удалось разобрать.
  Result = Value.ValueOrDefault;

  // Value - это структурно поле заполняемое при отображении. Его реальный тип ParsedValue<double>.
  // ParsedValue<> оборачивает значения простых типов решая две задачи:
  // 1. Добавляет к значению координаты откуда оно было разобрано.
  // 2. Позволяет хранить информацию о том, что значение не удалось разобрать.
  Value : double;
}

// Так как в нашем языке есть несколько типов выражений с похожей структурой AST,
// объявляем для них абстрактный базовый AST с именем "Binary".
abstract ast Binary : Expression
{
  // назначаем область видимости обоим подвыражениям.
  Expression1.Scope = Scope;
  Expression2.Scope = Scope;

  // структурные свойства описывающие два подвыражения.
  Expression1 : Expression;
  Expression2 : Expression;
}

// теперь в конкретных AST нам остается описать только вычисление зависимого
// свойства Result (описанного в Expression). Структурные свойства Expression1 и Expression2 у нас уже есть.
ast Sum : Binary { Result = Expression1.Result + Expression2.Result; }
ast Sub : Binary { Result = Expression1.Result - Expression2.Result; }
ast Mul : Binary { Result = Expression1.Result * Expression2.Result; }
ast Div : Binary { Result = Expression1.Result / Expression2.Result; }

// аналогично поступаем для выражений с одним подвыражением...
abstract ast Unary : Expression
{
  Expression.Scope = Scope;
  
  Expression : Expression;
}

ast Plus  : Unary { Result = Expression.Result; }
ast Minus : Unary { Result = -Expression.Result; }

// VariableRef - пожалуй это самая интересная часть описания AST. 
// Это описание ссылки на значение другой переменной в выражении.
ast VariableRef : Expression
{
  // Ref<> - это специальный тип позволяющий выразить результат разрешения имен или связывания.
  // Этот типа позволят хранить 
  // 1. Обычную ссылку на символа (при удачном связывании/разрешении имен).
  // 2. Информацию о том, что связывание/разрешение имен прошли ну дачно (символ не определен, Unresolved).
  // 3. При связывании или разрешении имен было найдено более одного символа с тем же именем (неоднозначность, ambigouty).
  // Метод Ref<>.Resolve() позволяет произвести разрешение имер (обычно выражающееся в фильтрации 
  // информации некоторым алгоритмом.
  // Reference.Ref (объявленный в библиотеке) имеет тип Ref[DeclarationSymbol]. См.
  // https://github.com/JetBrains/Nitra/blob/master/Nitra/Nitra.Runtime/Declarations/Reference.nitra 
  // Нам же нужно убедиться, что связывание произошло не с каким-то любым символом, а с символом 
  // типа VariableSymbol (образованного декларацией Variable, см. выше).
  // Метод Resolve производит эту операцию и в случае успеха помещает в зависимое свойство Ref результат.
  out Ref : Ref[VariableSymbol] = Reference.Ref.Resolve();

  // передает область видимости Reference-у. Это приведет к тому, что в нем автоматически произойдет
  // связывание ссылки на имя с символом. При этом результат помещается в свойство Reference.Ref.
  Reference.Scope = Scope;
  // Обращаемся к значению свойства Result символа с которым было связано имя. 
  // Обратите внимание, что этот код выполнится только при успешном разрешении имени
  // (при выполнении Reference.Ref.Resolve()). В ином случае значение свойства Ref.Symbol останется не вычисленным,
  // соответственно не будет вычесано и значение зависимого свойства Result (и так по цепочке вверх).
  Result     = Ref.Symbol.Result;

  // Структурное свойство значение которого получается при отображении.
  // Отображение для AST Reference генерируется автоматически, так как
  // на правило Reference был повешен атрибут "Reference".
  Reference : Reference;
}

[/cut]

AST и расчеты на нем готовы, но AST не появится сам собой. Нам нужно проецировать дерево разбора на него, чтобы Nitra автоматически строила AST для кода на нашем языке.
Отображение (оно же проекция, оно же маппинг) находится в файле Sample-Mapping.nitra.
[cut]
using Nitra;
using Nitra.Runtime;
using Nitra.Declarations;
using Nitra.Runtime.Binding;

// Отображаем дерево разбора правила TopRule из синтаксического модуля SampleSyntax на AST типа Top (см. их объявления выше).
map syntax SampleSyntax.TopRule -> Top
{
  // отображаем поле TopRule.VariableDeclarations (дерева разбора) на структурное свойство Top.Variables
  VariableDeclarations -> Variables;
}

// здесь все аналогично...
map syntax SampleSyntax.VariableDeclaration -> Variable
{
  // в AST Variable нет объявления поле Name. Оно неявно унаследовано от базового типа 
  // Declaration описанного в библиотеке. Но проецировать значения нужно и на свойства
  // базовых типов.
  Name       -> Name;
  Expression -> Expression;
}

// Отображение для расширяемого правила (описывающего ИЛИ в грамматике Nitra).
// Здесь опять же все похоже на самое первое отражение. Сначала указывается тип дерева 
// разбора (имя правил), а затем имя AST-типа.
map syntax SampleSyntax.Expression -> Expression
{
  // описание отображения для каждого расширения правила SampleSyntax.Expression
  // Num - это имя расширяемого правила (SampleSyntax.Expression.Num) 
  // Number - это имя AST-типа в который происходит отображение.
  | Num -> Number
    {
      // для вычисления значение структурного свойства Value используется выражение на Nemrle.
      // Мы это называем ручное или программное отображение. Оно нужно потому что Nitra не умеет
      // отображать распарсенные значения в double.
      // Значение типов не являющихся AST в Nitra должны быть обернуты в тип ParsedValue<>.
      // При этом ему передается позиция значения в коде (поле Digits дерева разбора имеет тип NSpan),
      // а так же самое значение.
      Value = ParsedValue(Digits, double.Parse(GetText(Digits)));
    }

  // остальное отображение тривиально и аналогично описанному выше, так что я не буду его описывать.

  | Braces -> Expression
  | Variable -> VariableRef
    {
      Reference -> Name;
    }
  | Sum
    {
      Expression1 -> Expression1;
      Expression2 -> Expression2;
    }
  | Sub
    {
      Expression1 -> Expression1;
      Expression2 -> Expression2;
    }
  | Mul
    {
      Expression1 -> Expression1;
      Expression2 -> Expression2;
    }
  | Div
    {
      Expression1 -> Expression1;
      Expression2 -> Expression2;
    }
  | Plus
    {
      Expression -> Expression;
    }
  | Minus
    {
      Expression -> Expression;
    }
}

[/cut]

Последний штрих... Для того чтобы написанные нами вычисления работали нам нужно написать небольшой обвязочный код, который запустит их и проинициализирует ContainingTable у корневых элементов AST-а (т.е. у Top). Пока что в Nitra это делается так. Нужно создать паршал-класс корневого элемент AST и реализовать в нем интерфейс IProjectSupport. Вот как это сделано в данном примере (файл Main.n):

[cut]
public partial class Top : AstBase, IProjectSupport
{
  public RefreshProject(project : Project) : void
  {
    // получаем файлы проекта
    def files   = project.Files.ToArray(); 
    // неведанная хфигня :) необходимая для вычисления зависимых свойств
    def context = DependentPropertyEvalContext(); 
    // Таблица имен, она же глобальная область видимости (Scope).
    // В ней будут объявлены все наши ременные. 
    def scope   = TableScope("Variables", null);

    foreach (file in files)
      when (file.Ast is Top as top)
        // задаем глобальную область видимости каждому Top AST нашего проекта.
        top.ContainingTable = scope;

    // Прогоняем первую стадию вычислений. На ней будут сформированы 
    // и помещены в таблицу имен символы переменных.
    AstUtils.EvalProperties(context, files, "Collect variables", 0);
    // Прогоняем вторую стадию. На ней будут произведены вычисления и получен результат.
    AstUtils.EvalProperties(context, files, "Compute variables", 1);
  }
}

[/cut]

Заключение

Данный пример аналогичен свертке констант (constant folding) применяемому в большинстве языков программирования. Он изначально игрушечный и не предполагает компиляции в машинный код и т.п. Его цель показать как производятся расчеты на зависимых свойствах.

Интересно то, что данные вычисления не могут зациклиться. Если в выражениях двух или более переменных создать циклическую зависимость, то все переменные входящие в эту зависимость не будут вычислены. Это особенность вычислительной модели зависимых свойств. Если надо ее можно обойти. Но это уже отдельная тема.

Посмотреть на результат можно поместив полученную dll в нашу тестовую утилиту (Nitra.Visualizer.exe). Так же пример будет работать и в IDE, но там будет доступна только подсветка и навигация, а результат расчетов увидеть не удастся.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Отредактировано 14.01.2017 23:36 VladD2 . Предыдущая версия . Еще …
Отредактировано 14.01.2017 23:12 VladD2 . Предыдущая версия .
Отредактировано 17.12.2015 20:58 VladD2 . Предыдущая версия .
Отредактировано 04.12.2015 16:03 VladD2 . Предыдущая версия .
Отредактировано 02.12.2015 9:35 VladD2 . Предыдущая версия .
Отредактировано 02.12.2015 9:28 VladD2 . Предыдущая версия .
Отредактировано 02.12.2015 9:21 VladD2 . Предыдущая версия .
Отредактировано 02.12.2015 9:07 VladD2 . Предыдущая версия .
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.