Nitra

Блог посвящен проекту Nitra - средству разработки языков программирования (компиляторов и плагинов к IDE). http://confluence.jetbrains.com/display/Nitra/

Терминология Nitra

VladD2 VladD2
Дерево разбора (ДР, Parse Tree, PT) – это то дерево строящееся для конкретного исходника по конкретной грамматике языка. Оно содержит много не важной типизации/компиляции информации. Например: пробельные символы, ключевые слова, операторы, избыточное ветвление, разделители списков (вроде запятых в списке параметров) и т.п.

Абстрактное Синтаксическое Дерево (АСД, Abstract Syntax Tree, AST) – это дерево, содержащее только информацию важную для дальнейшего анализа. AST значительно компактнее ДР и имеет более простую структуру. В нем устраняются излишние ветвления которые могут появиться в ДР в виду особенностей грамматики.

Декларация (declaration) – ветка AST описывающая декларацию (описание) сущности языка, на которую можно ссылаться (reference) по имени. Такими сущностями являются классы в C++, поля классов, локальные переменные и т.п. Одна сущность языка может иметь одну или более декларацию. Например, partial class или пространства имен в C#.

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

Ссылка (имя, reference) – базовая конструкция языка позволяющая указать на то, что в некоторой конструкции языка нужно сослаться на какую-то сущность языка, то есть на символ языка.

Связывание имен (связывание, binding) – процесс поиска символа (или группы символов) на который ссылается некоторое имя (ссылка). Например, в большинстве языков программирования в выражении «a + 42» имя «a» является ссылкой на некоторую сущность языка (переменную, поле, функцию, тип, и т.п.). Процесс связывания позволяет определить на какие конкретные символы может ссылаться это имя.

Область видимости (Scope) – часть программы в которой «видны» (доступны) некоторые имена. Например, областью видимости локальных переменных в языке C является блок (содержимое заключенное в фигурные скобки). Области видимости могут быть иерархическими. При этом они могут затенять внешние области видмости. Так же они могут проецироваться в другие области видимости. Для процесса связывания необходимо указать области видимости языка и отношения между ними (затенения или проекции). Например, конструкция using в C# может проецировать содержимое пространства имен (которое является областью видимости в C#) в другое пространство имен.

Разрешение имен (name resolving, name resolution) – процесс, позволяющий определить, на какой конкретный символа ссылается некоторое имя в случае, если в результате связывания найдено более одного имени. Обычно этот процесс тесно интегрирован с процессом типизации или выводом типов.
s22
s22
14.03.2015 04:34
Здравствуйте, VladD2, Вы писали:

VD>Область видимости (Scope) – часть программы в которой «видны» (доступны) некоторые имена. Например, областью видимости локальных переменных в языке C является блок (содержимое заключенное в фигурные скобки). Области видимости могут быть иерархическими. При этом они могут затенять внешние области видмости. Так же они могут проецироваться в другие области видимости. Для процесса связывания необходимо указать области видимости языка и отношения между ними (затенения или проекции). Например, конструкция using в C# может проецировать содержимое пространства имен (которое является областью видимости в C#) в другое пространство имен.


для уникальной переменной область вдимости заканчивается местом где она присвавается другому значеню. Пример Раст.
Как тут такое реализовать?
hardcase
hardcase
14.03.2015 03:29
Здравствуйте, s22, Вы писали:

s22>для уникальной переменной область вдимости заканчивается местом где она присвавается другому значеню. Пример Раст.

s22>Как тут такое реализовать?

Dataflow анализом во время/после типизации. Значение этой переменной может быть куда-либо передано, например, в разных ветках if.
Иными словами, попытавшись еще раз раз прочитать значение переменной по некоторому пути исполнения компилятор должен выдать ошибку вида "illegal variable 'x' usage", а не к "unbound name 'x'".
В твоей интерпретации компилятор может использовать имя x из какой-то внешней области видимости, что выглядит довольно странно.
s22
s22
16.03.2015 05:43
Здравствуйте, hardcase, Вы писали:

H>Здравствуйте, s22, Вы писали:


s22>>для уникальной переменной область вдимости заканчивается местом где она присвавается другому значеню. Пример Раст.

s22>>Как тут такое реализовать?

H>Dataflow анализом во время/после типизации. Значение этой переменной может быть куда-либо передано, например, в разных ветках if.

H>Иными словами, попытавшись еще раз раз прочитать значение переменной по некоторому пути исполнения компилятор должен выдать ошибку вида "illegal variable 'x' usage", а не к "unbound name 'x'".
H>В твоей интерпретации компилятор может использовать имя x из какой-то внешней области видимости, что выглядит довольно странно.

спасибо, Вы правы.
btn1
btn1
18.03.2015 06:09
Здравствуйте, VladD2, Вы писали:

VD>Дерево разбора (ДР, Pars Tree, PT)

VD>Абстрактное Синтаксическое Дерево (АСД, Abstract Syntax Tree, AST)

Вопрос с задних рядов: а как они синхронизируются? (если это физически два разных дерева) Или AST "вплетён" в PT? А если меняют код исходника в IDE, перестраиваются оба дерева?

Ну и попутно для эрудиции: команда шарподелов хвалилась серобуромалиновыми деревьями (цвета точно не помню), суть которых в том, что узлы одного цвета — неизменяемые, а другие — изменяемые. Используют ли девелоперы два разных дерева или одно разноцветное — не помню, мельком читал. Сам вопрос: в Нитре тоже подобный подход?
VladD2
VladD2
18.03.2015 06:36
Здравствуйте, btn1, Вы писали:

B>Вопрос с задних рядов: а как они синхронизируются? (если это физически два разных дерева) Или AST "вплетён" в PT? А если меняют код исходника в IDE, перестраиваются оба дерева?


Pars Tree отображается в AST. Считай, что копируется информация.

B>Ну и попутно для эрудиции: команда шарподелов хвалилась серобуромалиновыми деревьями (цвета точно не помню), суть которых в том, что узлы одного цвета — неизменяемые, а другие — изменяемые. Используют ли девелоперы два разных дерева или одно разноцветное — не помню, мельком читал. Сам вопрос: в Нитре тоже подобный подход?


Pars Tree полностью не изменяемый, но есть поддержка смлайсебл. Это позволяет распознавать Pars Tree или конструировать его из кусков. AST не подлежит ручному конструированию. Он получается отображением (мапингом) по спецификации отображения.

В AST есть свойства двух типов:
1. Структурные. Именно они и заполняются при отображении из Pars Tree.
2. Зависимые. Они вычисляются в специальной процедуре и имеют семантику сходную с функциональными вычислениями. По сути это реализация атрибутных грамматик. Значение такого свойства может быть присвоено (рассчитано) только один раз. Вычисления зависимых свойств производится в псевдо-линивом порядке, так что зависимость между свойствами определяет порядок их вычислений. Зависимые свойства могут быть рассчитаны инкрементально).

Короче, нам пока что просто не надо псевдо-неизменяемых структур данных.
s22
s22
25.03.2015 03:53
Здравствуйте, VladD2, Вы писали:


VD>2. Зависимые. Они вычисляются в специальной процедуре и имеют семантику сходную с функциональными вычислениями. По сути это реализация атрибутных грамматик. Значение такого свойства может быть присвоено (рассчитано) только один раз. Вычисления зависимых свойств производится в псевдо-линивом порядке, так что зависимость между свойствами определяет порядок их вычислений. Зависимые свойства могут быть рассчитаны инкрементально).


как я понял на зависимые накладывается ограничение в виде топологической сортируемости? Т.е. спекулятивность они не поддерживают?
VladD2
VladD2
25.03.2015 12:45
Здравствуйте, s22, Вы писали:

s22>как я понял на зависимые накладывается ограничение в виде топологической сортируемости? Т.е. спекулятивность они не поддерживают?


Что, в твоем понимании, означает "спекулятивность"?
s22
s22
27.03.2015 11:51
Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, s22, Вы писали:


s22>>как я понял на зависимые накладывается ограничение в виде топологической сортируемости? Т.е. спекулятивность они не поддерживают?


VD>Что, в твоем понимании, означает "спекулятивность"?


Спекулятивность — аналог прологовского вывода.
VladD2
VladD2
27.03.2015 12:51
Здравствуйте, s22, Вы писали:

s22>Спекулятивность — аналог прологовского вывода.


Это называется — "унификация". И этот тут совсем не причем. Унификация будет в движке типизации.
s22
s22
27.03.2015 04:08
Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, s22, Вы писали:


s22>>Спекулятивность — аналог прологовского вывода.


VD>Это называется — "унификация". И этот тут совсем не причем. Унификация будет в движке типизации.


Не только унификация, а еще и поиск с возвратом.