Сообщений 12 
Оценка 660 
Оценить 
| Сообщений 12 Оценка 660 Оценить
|
Mini C – это сильно урезанная версия языка программирования C. Практического смысла этот язык не имеет. Единственная цель его существования – являться примером полноценного ЯП, на котором можно демонстрировать техники разработки компиляторов.
Существует ряд реализаций Mini C на разных языках программирования с применением разных генераторов парсеров. Комьюнити Nitra выбрало этот простой язык для демонстрации техники разработки компилятора (и сопутствующих утилит) с помощью Nitra.
За основу была взята реализация Mini C на F#. Эта реализация находится в данном репозитории и описана в данном блоге. В свою очередь она основана на грамматике, взятой отсюда. Реализацию Mini C на Java можно найти этом репозитории.
Прелесть этого урезанного варианта C в том, спецификация языка получается очень простой (короткой), и при этом это настоящий язык программирования, на котором можно писать настоящие программы. Конечно, для реальной разработки ПО его недостаточно, но написанную на нем программу можно скомпилировать, запустить на выполнение, а полученный результат сравнить с ожидаемым. В общем, это пример настоящего компилятора, при этом его реализацию можно охватить взглядом, так как она не содержит тучи деталей присущих полноценным ЯП.
Реализацию Mini C на Nitra создал один человек – Василий Кириченко. До этого он не имел опыта использования Nitra и Nemerle (на котором написан сопутствующий код), но знал F#. Я помогал Василию (в основном советами). На реализацию Mini C ушло где-то около месяца (причем в нерабочее время).
Nitra позволяет создать как компилятор командой строки, так и плагин для IDE. Причем плагин будет получен практически в автоматическом режиме. В отличие от традиционных генераторов парсеров Nitra предоставляет не только парсер, но и позволяет описать:
Все, что нужно сделать, чтобы превратить описание языка на Nitra в компилятор – написать код генерации кода под нужную платформу. В следующих версиях Nitra будет предоставлять и средства генерации кода на низкоуровневых языках (MSIL, байткод Java, LLVM и т.п.), но на сегодня есть только зачатки бэкенда для .Net, позволяющего читать символы из метаданных .Net. Mini C очень прост, поэтому в нем не использован даже бэкенд для .Net. Вместо этого сделан свой простенький аналог.
Разработка компилятора на Nitra состоит из следующих этапов:
Для каждого из пунктов (кроме последнего) в Nitra имеется специализированный язык (DSL).
Если заранее имеется спецификация языка, можно последовательно написать синтаксические модули, описывающие грамматику, затем описать AST, затем отображение дерева разбора на него, затем описать вычисления по AST, и в итоге написать бэкенд, который прочтет аннотированный AST и сгенерирует исполнимый код.
Если еще нет спецификации языка, а сам язык проектируется в процессе, можно совершать итерации в каждой из которых создается фича языка и код для каждого из перечисленных выше пунктов. Это позволяет развивать язык инкрементально, продумывая, реализуя и тестируя каждую фичу по отдельности. Более того, фичи языка могут быть оформлены в виде плагинов к компилятору (Nitra предоставляет все средства для этого).
Проект языка в Nitra может состоять из одного или более .nitra-файлов и нуля или более .n- и/или .cs-файлов. Чтобы собрать Nitra-проект, можно воспользоваться:
Первый путь хорош, если вам не хочется связываться с Nemerle, и вы готовы вести сборку языковых проектов из командной строки. Второй путь позволяет осуществлять разработку в рамках MS VS.
В проекте Mini C был выбран второй путь.
Репозиторий проекта находится здесь.
В нем есть следующие проекты:
Для того чтобы можно было собрать Nitra-Mini-C.sln (находится в корне проекта), нужно иметь:
Чтобы проект Nemerle стал проектом Nitra, нужно создать в нем ссылку на макробиблиотеку Nitra.Compiler.dll. Именно это и сделано в проекте Nitra-Mini-C.nproj. Это приводит к тому, что файлы с расширением .nitra обрабатываются не компилятором Nemerle, а плагином Nitra. Таким образом файлы .nitra становятся штатными файлами Nemerle-проекта. Пока что интеллисенс для них не поддерживается, но мы исправим это в будущих версиях.
Проект Nitra-Mini-C.nproj состоит из следующих файлов:
Чтобы описать в Nitra новый формат файла, нужно добавить в проект описание языка. Это делает с помощью конструкции «language». Данная конструкция для Mini C расположена в файле MiniC-Language.nitra:
language MiniC { span class Variable { ForegroundColor=Maroon; } span class Function { ForegroundColor=Chocolate; } extension = .minic; syntax module MiniCSyntax start rule CompilationUnit; } |
Variable и Function – это так называемые классы подсветки. Что-то вроде стилей, которыми будут подсвечиваться символы языка. В Mini C есть два типа символов: переменные и функции. Вот для них и описываются классы подсветки.
Директива «extension» описывает расширение файла. У Mini C это «.minic». Данная директива не обязательна, но ее наличие позволит получить поддержку IDE для файлов с указанным расширением.
Последняя директива задает стартовое синтаксическое правило (CompilationUnit) и синтаксический модуль (MiniCSyntax), из которого его нужно брать. С этого правила будет начинаться парсинг файла с указанным расширением.
Конструкция «language» поддерживает наследование (по аналогии с наследованием в ООЯ), но в данном случае нам это не требуется. В реальном мире наш язык может быть унаследован от базового языка, например, от DotNetLang (базового языка для всех языков .Net).
Вот как выглядит исходная грамматика (в формате БНФ):
program → decl_list
decl_list → decl_list decl
| decl
decl → var_decl
| fun_decl
var_decl → type_spec IDENT ;
| type_spec IDENT [ ] ;
type_spec → VOID
| BOOL
| INT
| FLOAT
fun_decl → type_spec IDENT ( params ) compound_stmt
params → param_list
| VOID
param_list → param_list , param
| param
param → type_spec IDENT
| type_spec IDENT [ ]
stmt_list → stmt_list stmt
| ε
stmt → expr_stmt
| compound_stmt
| if_stmt
| while_stmt
| return_stmt
| break_stmt
expr_stmt → expr ;
| ;
while_stmt → WHILE ( expr ) stmt
compound_stmt → { local_decls stmt_list }
local_decls → local_decls local_decl
| ε
local_decl → type_spec IDENT ;
| type_spec IDENT [ ] ;
if_stmt → IF ( expr ) stmt
| IF ( expr ) stmt ELSE stmt
return_stmt → RETURN ;
| RETURN expr ;
// выражения описаны в порядке увеличения приоритетов
expr → IDENT = expr
| IDENT [ expr ] = expr
→ expr OR expr
→ expr EQ expr
| expr NE expr
→ expr LE expr
| expr < expr
| expr GE expr
| expr > expr
→ expr AND expr
→ expr + expr
| expr - expr
→ expr * expr
| expr / expr
| expr % expr
→ ! expr
| - expr
| + expr
→ ( expr )
→ IDENT
| IDENT [ expr ]
| IDENT ( args )
| IDENT . size
→ BOOL_LIT
| INT_LIT
| FLOAT_LIT
| NEW type_spec [ expr ]
arg_list → arg_list , expr
| expr
args → arg_list
| ε |
Правила грамматики в Nitra задаются в так называемых синтаксических модулях. Вся грамматика Mini C был описана в одном синтаксическом модуле MiniCSyntax, но на практике она может быть разнесена на несколько модулей. Модули могут находиться как в разных файлах одного проекта, так и импортироваться из внешних бинарных библиотек. Синтаксический модуль MiniCSyntax описан в файле MiniC-syntax.nitra:
namespace MiniC { syntax module MiniCSyntax { using Nitra.Core; using Nitra.CStyleComments; keyword regex ['a'..'z', '_'..'_']+ rule S; regex KeywordToken = "if" | "else" | "while" | "return" | "break" | "void" | "int" | "true" | "false" | "bool" | "float"; [Keyword] token Keyword = Name=KeywordToken !IdentifierPartCharacters; [Reference] token Reference = !Keyword IdentifierBody; [Name] token Name = !Keyword IdentifierBody; syntax CompilationUnit = (TopDeclaration nl)*; syntax TopDeclaration { | VarDeclaration = VarDeclaration ";" | FunDeclaration = TypeRef Name "(" (VarDeclaration; "," sm)* ")" CompoundStatement } syntax VarDeclaration { | Scalar = TypeRef Name | Array = TypeRef Name "[" "]" } syntax TypeRef { | "void" sm | "int" sm | "float" sm | "bool" sm } syntax CompoundStatement = "{" inl (VarDeclaration ";" nl)* (Statement nl)* d "}"; syntax Statement { | Expression = Expr ";" | Empty = ";" | Compound = CompoundStatement | If = "if" sm "(" Expr ")" sm Statement | IfElse = "if" sm "(" Expr ")" sm TrueBranch=Statement "else" FalseBranch=Statement | While = "while" sm "(" Expr ")" sm Statement | ReturnVoid = "return" ";" | Return = "return" sm Expr ";" | Break = "break" ";" } regex DecimalDigit = ['0'..'9']; literal Operator = "||", "==", "!=", "<=", "<", ">=", ">", "+", "-", "*", "/", "+", "-", "!"; syntax Argument = Expr; syntax Expr { | [SpanClass(Number)] IntegerLiteral = Digits { regex Digits = ("+" | "-")? DecimalDigit+; } | [SpanClass(Number)] FloatLiteral = Digits { regex Digits = ("+" | "-")? DecimalDigit+ "." DecimalDigit+; } | "true" | "false" | VariableRef = Reference | ArrayRef = Reference "[" Expr "]" | FunCall = Reference "(" (Argument; "," sm)* ")" | ArraySize = Reference "." "size" | Braces = "(" Expr ")" | ArrayAllocation = "new" TypeRef "[" Expr "]" precedence Assignment: | ScalarAssignment = Reference sm "=" sm Expr right-associative | ArrayAssignment = Reference "[" Index=Expr "]" sm "=" sm Expr right-associative precedence Or: | Or = Expr sm "||" sm Expr precedence And: | And = Expr sm "&&" sm Expr precedence Equal: | Equal = Expr sm "==" sm Expr | NotEqual = Expr sm "!=" sm Expr precedence LessGreater: | LessEqual = Expr sm "<=" sm Expr | Less = Expr sm "<" sm Expr | GreaterEqual = Expr sm ">=" sm Expr | Greater = Expr sm ">" sm Expr precedence Sum: | Sum = Expr sm "+" sm Expr | Sub = Expr sm "-" sm Expr | Modulus = Expr sm "%" sm Expr precedence Mul: | Multiply = Expr sm "*" sm Expr | Divide = Expr sm "/" sm Expr precedence Unary: | Plus = "+" Expr | Minus = "-" Expr | LogicalNegate = "!" Expr } } } |
Конструкция:
syntax module MiniCSyntax { |
Описывает синтаксический модуль MiniCSyntax, в котором описаны все правила грамматики языка Mini C. Именно на этот модуль идет ссылка в описании языка.
Конструкции:
using Nitra.Core; using Nitra.CStyleComments; |
описывают импорт других синтаксических модулей, в данном случае модулей Nitra.Core и Nitra.CStyleComments из стандартной библиотеки Nitra (Nitra.Runtime.dll).
В синтаксическом модуле Nitra.Core находятся стандартные правила и маркеры, которые используются при описании Mini C. Модуль Nitra.CStyleComments содержит описание комментариев в стиле C и C++.
Конструкция:
keyword regex ['a'..'z', '_'..'_']+ rule S; |
описывает регулярное выражение которое будет использоваться Nitra, чтобы отличить литералы (например, "if"), представляющие собой ключевые слова, от других литералов. В данном случае ключевыми словами будут считаться литералы, содержащие латинские буквы в нижнем регистре и подчеркивания. Таким образом "while", "true" и "type_of" будут распознаваться как ключевые слова, а "TRUE", "==" или "true+" – не будут.
Собственно, понятие «ключевое слово» в Nitra несколько размыто. Для парсера совершенно все равно, является литерал ключевым словом или нет, но это важно при восстановлении после ошибок и для алгоритма расстановки пробельных правил. Nitra использует безлексерный алгоритм парсинга, но при этом помогает автоматизировать расстановку пробельных правил. Данная директива, кроме регулярного выражения, так же позволит задать правило, которое будет автоматически вставляться после ключевых слов. В данном случае это правило S, импортированное из синтаксического модуля Nitra.Core. Если Nitra встретит в грамматике литерал, разбираемый заданным регулярным выражением, то подставит после этого литерала правило «S». В противном случае будет подставлено правило «s» (так же импортируемое из модуля Nitra.Core).
В общем, можно рассматривать данную директиву как стандартное заклинание :).
Правило:
regex KeywordToken = "if" | "else" | "while" | "return" | "break" | "void" | "int" | "true" | "false" | "bool" | "float"; |
описывает ключевые слова Mini C. Точнее, оно описывает регулярное правило, разбирающее подстроку, с ними совпадающую. Сами же ключевые слова описываются правилом:
[Keyword] token Keyword = Name=KeywordToken !IdentifierPartCharacters; |
Данное правило помечено атрибутом Keyword, что говорит Nitra, что данное правило используется для описания ключевых слов. Эта информация используется Nitra при восстановлении после обнаружения ошибок.
Так как парсер Nitra безлексерный, разобранная правилом KeywordToken подстрока может быть префиксом более длинной конструкции, например:
trueData |
что обычно не должно восприниматься как ключевое слово. Чтобы парсер не разбирал такие префиксы как ключевые слова, в правиле Keyword используется негативный предикат «!IdentifierPartCharacters». Это предотвращает разбор правила Keyword в случае, когда следующий за разобранной конструкцией символ является символом, из которых могут состоять идентификаторы языка. Правило IdentifierPartCharacters импортируется из синтаксического модуля Nitra.Core. Оно разбирает Unicode-символ или «_».
Конструкция «Name=KeywordToken» это подправило, которому задано имя. «Name» – это имя, заданное для поля дерева разбора, формируемого для данного продправила. Если бы имя не было задано явно, поле получило бы имя «KeywordToken» (в соответствии с алгоритмом выведения имен для подправил).
Правило:
[Reference] token Reference = !Keyword IdentifierBody; [Name] token Name = !Keyword IdentifierBody; |
Описывает идентификатор языка. В Nitra есть два вида идентификаторов:
Name используется для описания идентификаторов, используемых для задания имени некоторой именованной конструкции. В случае Mini C правило Name используется для задания имен переменных и функций.
Reference используется во всех остальных местах.
По сути, любой язык программирования является некоторым видом базы данных, где описываются именованные сущности, а далее (в коде) на них делаются ссылки. Nitra предоставляет средства обработки этих ссылок. Процесс типизации, в сущности, заключается в том, чтобы понять, на что указывают ссылки в коде компилируемой программы.
Атрибуты Reference и Name подсказывают Nitra, что данные правила описывают имя и ссылку (соответственно) и автоматически генерируют код отображения (mapping) дерева разбора, порождаемого этими правилами, на специальные виды AST, описывающие имена и ссылки на них.
Так как идентификаторы не должны совпадать с ключевыми словами, перед телом идентификатора используется негативный предикат !Keyword предотвращающий это.
syntax CompilationUnit = (TopDeclaration nl)*; |
описывает стартовое правило грамматики. То, что оно является стартовым, указано в описании языка.
«(TopDeclaration nl)*» – разбирает последовательность правил TopDeclaration состоящую из нуля или более элементов. «nl» - это маркер, указывающий процедуре pretty-print, что за каждым вхождением декларации языка (кода, разбираемого правилом TopDeclaration) нужно печатать символ конца строки. Таким образом, при печати декларации всегда будут печататься с новой строки.
В Mini C есть два типа деклараций: декларация переменной и декларация функции. Они разбираются, соответственно, подправилами VarDeclaration и FunDeclaration правила TopDeclaration:
syntax TopDeclaration { | VarDeclaration = VarDeclaration ";" | FunDeclaration = TypeRef Name "(" (VarDeclaration; "," sm)* ")" CompoundStatement } |
В Nitra конструкция:
syntax ИмяПравила
{
| ИмяПервогоПодправила = ...
| ИмяВторогоПодправила = ...
} |
описывает альтернативу, что аналогично БНФ-описанию:
ИмяПравила → ...
| ... |
В отличии от BNF, в Nitra-грамматике каждой альтернативе должно быть задано имя. Имена могут выводиться из первого подправила или задаваться явно. В данном случае имена подправил заданы явно.
Задавать имена явно необходимо потому, что правила в Nitra заодно описывают дерево разбора (Parse Tree). Этим же объясняется и необычный синтаксис правил, описывающих альтернативы в Nitra.
Каждая альтернатива отделяется от предыдущей знаком «|». Первой альтернативе также может предшествовать знак «|», хотя в данном случае он необязателен.
Конструкция:
(VarDeclaration; "," sm)* |
из FunDeclaration разбирает список деклараций переменных, разделенных запятыми. Nitra поддерживает специальный синтаксис для разбора списков с разделителями. Он отличается наличием «;», за которой идет правило, описывающее разделитель. В данном случае список параметров разделяется запятой.
«sm» - это еще один маркер pretty-print, указывающий, что в данном месте должен в обязательном порядке печататься пробел. На разбор кода маркеры не влияют, так что в коде пробелы могут отсутствовать, или может присутствовать множество пробелов.
В Mini C глобальные переменные, локальные переменные и параметры описываются одним и тем же правилом VarDeclaration:
syntax VarDeclaration { | Scalar = TypeRef Name | Array = TypeRef Name "[" "]" } |
Переменная может описывать единичное значение:
| Scalar = TypeRef Name |
или массив значений:
| Array = TypeRef Name "[" "]" |
Обратите внимание на то, что имя переменной задается с помощью правила «Name» – это важно, так как впоследствии данные подправила будут описывать декларацию языка, а их имена должны отображаться на специализированный тип Nitra.
Список типов в Mini C фиксирован. Допускаются только типы void, int, float и bool. Посему ссылка на тип вырождается в простое правило TypeRef:
syntax TypeRef { | "void" sm | "int" sm | "float" sm | "bool" sm } |
TypeRef описывает ссылку на типы, а не сами типы. Сами типы в Mini C предопределены.
В более серьезных языка типы могут быть как предопределенными, так и определяемыми (декларируемые) пользователем (например, в C можно определять структуры и псевдонимы для типов). Причем в более современных языках (к которым, впрочем, не относятся C и C++) типы мог быть загружены из внешних библиотек. В Mini C все типы предопределены и не требуют отдельной декларации в коде. Тем не менее, для представления типов нужны символы. В Nitra единственным способом описать новый тип символа является описание его декларации (специальные конструкции Nitra). Так как типы предопределены, в Mini C отсутствует синтаксическое описание и отображение для этих деклараций. Вместо этого описанные этими декларациями символы создаются императивно, в коде. Чуть позже мы вернемся к вопросу символов и деклараций. А пока что давайте рассмотрим синтаксис выражений языка.
В Mini C, как и в обычном C, локальные переменные могут быть описаны только в начале блока стейтментов (обрамляемого фигурными скобками).
Вот пример корректного блока кода в C / Mini C:
{
int i;
int ary[];
foo(i, ary);
} |
А вот пример некорректного блока:
{
int i;
bar(i);
int ary[]; // Ошибка: переменная должна идти вначале блока!
foo(i, ary);
} |
Соответственно, блок Mini C задается следующим правилом:
syntax CompoundStatement = "{" inl (VarDeclaration ";" nl)* (Statement nl)* d "}"; |
В отличие от БНФ-декларации, в данной реализации описание переменных и параметров не дублируется. Вместо этого все они описываются одним правилом VarDeclaration, а разделители (которые отличаются для переменных (точка с запятой) и параметров (запятая), задаются при описании списков.
«inl», «nl» и «d» – это маркеры pretty-print, означающие «перенос строки и начало нового уровня отступа», «перенос строки» и «конец уровня отступа», соответственно.
Правило Statement – описывает стейтменты Mini C (к сожалению, нормального перевода для этого понятия в русском нет).
syntax Statement { | Expression = Expr ";" | Empty = ";" | Compound = CompoundStatement | If = "if" sm "(" Expr ")" sm Statement | IfElse = "if" sm "(" Expr ")" sm TrueBranch=Statement "else" FalseBranch=Statement | While = "while" sm "(" Expr ")" sm Statement | ReturnVoid = "return" ";" | Return = "return" sm Expr ";" | Break = "break" ";" } |
На мой взгляд, оно очевидно и не требует отдельного описания. Единственное, на что стоит обратить внимание – это на то, что правила CompoundStatement и Statement взаимно рекурсивны. Таким образом, блоки кода могут быть вложены в другие стейтменты, и наоборот.
Правило DecimalDigit описывает десятичное число:
regex DecimalDigit = ['0'..'9']; |
Правила типа regex не порождают AST и очень эффективно разбираются (для них формируется ДКА, по которому генерируется очень эффективный код). В результате их разбора получается только диапазон текста. Это позволяет экономить память, занимаемую AST. Минусом regex-правил является то, что они не могут быть рекурсивными и не могут иметь внутренней структуры (все их подправила сплющиваются, формируя единое регулярное выражение).
Конструкция:
literal Operator = "||", "==", "!=", "<=", "<", ">=", ">", "+", "-", "*", "/", "+", "-", "!"; |
не является правилом грамматики. Она помогает задать имя для литерального подправила. Если после этого объявления встретится литерал, полю дерева разбора (формируемому для этого подправила) будет дано имя «Operator». Если бы конструкции «literal» не было, пришлось бы задавать имя для каждого поля, формируемого для литерала.
Чтобы не занимать лишнего места, приводятся не все альтернативы правила Expr, а только те, которые требуют дополнительного пояснения.
syntax Expr { | [SpanClass(Number)] IntegerLiteral = Digits { regex Digits = ("+" | "-")? DecimalDigit+; } |
Атрибут «SpanClass(Number)» задает класс подсветки для альтернативы «IntegerLiteral». Это приведет к тому, что в IDE и Nitra.Visualizer (утилиты, используемой для отладки языков в Nitra) разобранные этим правилом числа будут подсвечиваться стилем Number (это стандартный стиль VS).
Digits – это вложенное правило. Nitra позволят вкладывать одно правило в другое, ограничивая тем самым область видимости вложенного правила. Во всем остальном это обычное правило.
«?» означает «необязательное подправило» (optional subrule).
«+» означает последовательность, которая может состоять из одного или более элементов.
Таким образом, правило Digits разбирает целое число, состоящее из одной или более цифр, и которому может предшествовать знак «+» или «-».
Так как Digits является regex-правилом, в AST для него формируется поле типа NSpan (описывающее диапазон текста, разобранного данным правилом).
Альтернатива:
| "true" |
разбирает литерал «true». Это правило интересно лишь тем, что для него не задано имя. В таком случае Nitra пытается вывести имя из первого подправила. Первая буква в выведенном имени делается заглавной. Таким образом, Nitra даст этой альтернативе имя «True».
В альтернативе:
| ArrayRef = Reference "[" Expr "]" |
интересно имя, которое формируется для подправил "[" и "]". Эти подправила получают имена «Operator1» и «Operator2» соответственно. Имя «Operator» определяется директивой «literal», описанной выше, а суффиксы «1» и «2» добавляются Nitra, чтобы избежать дублирования имен. Если такое поведение не устраивает, можно задать имена подправилам вручную:
| ArrayRef = Reference LeftBracket="[" Expr RightBracket="]" |
Автоматический вывод имен и директива «literal» позволяют убрать лишний «шум» из грамматики.
При описании операторов в выражении Mini C используется встроенная в Nitra поддержка разбора операторов с приоритетом и ассоциативностью:
precedence Assignment: | ScalarAssignment = Reference sm "=" sm Expr right-associative | ArrayAssignment = Reference "[" Index=Expr "]" sm "=" sm Expr right-associative precedence Or: | Or = Expr sm "||" sm Expr |
С помощью конструкций «precedence» задается так называемый список приоритетов.
В Nitra нет специальной конструкции для декларации приоритетов. Подразумевается, что любой приоритет, на который сослались (по его имени), автоматически существует. Это позволяет расширять грамматики внешними модулями, вводя в расширениях дополнительные приоритеты, и упорядочивать их по отношению к имеющимся приоритетам.
Приоритеты упорядочены по отношению друг к другу. Их порядок определяется последовательностью их размещения внутри описания расширяемого правила.
Чем ниже по коду расположено вхождение приоритета, тем больше значение приоритета. Таким образом, операторы располагаются в порядке увеличения приоритетов, что соответствует описанию
В данном случае приоритет Assignment меньше чем Or. Соответственно, оператор «||» будет иметь более высокий приоритет, нежели оператор присвоения.
Выражения (операторы), идущие после директивы «precedence» и до следующей директивы «precedence», имеют одинаковый приоритет. Приоритет влияет на то, как будут интерпретироваться операторы, если они идут друг за другом. Например, выражение:
a = b || c |
может быть интерпретировано как:
(a = b) || c |
или как:
a = (b || c) |
Так как в грамматике Mini C приоритет оператор «||» (Assignment) выше, чем у «=» (Assignment), данное выражение будет интерпретировано как:
a = (b || c) |
Директива «right-associative» задает ассоциативность для конкретного оператора (выражения). Она действует только на бинарные операторы (т.е. на выражения, имеющие два рекурсивных обращения в начале и в конце выражения).
Ассоциативность влияет на то, как будут рассматриваться идущие подряд операторы, имеющие одинаковый приоритет. Например:
a = b = 3 |
может быть интерпретировано как:
(a = b) = 3 |
или как:
a = (b = 3) |
Первый случай – это левоассоциативная интерпретация. Она принята по умолчанию. По правилам C (и Mini C) верна вторая интерпретация. Поэтому для правил присвоения используется директива «right-associative».
Выражения, заданные до первого вхождения приоритета, принадлежат к группе с так называемым «нулевым» приоритетом. Этот приоритет выше любых других.
Описав на Nitra грамматику Mini C, мы автоматически получили парсер Mini C и такие сервисы IDE, как:
Парсер, генерируемый Nitra, позволяет отпарсить исходный файл на Mini C и получить для него дерево разбора. Полученное дерево разбора можно анализировать «walker-ами», «посетителями» или с помощью описываемых прямо внутри правил rule-методов. Однако для того чтобы грамматика стала полноценным компилятором языка или движком IDE, нужно выполнить еще очень много действий, требующих немалой компетентности от автора. Самым сложным из них является типизация, или как ее еще называют, «семантический анализ».
Nitra предоставляет полный ряд специализированных языков, позволяющих упростить процесс типизации и сделать его почти таким же декларативным, как описание грамматики.
Следующие разделы будет посвящены этим языкам.
В Nitra сбор информации о компилируемой программе осуществляется по AST, а не по дереву разбора (получаемому автоматически по грамматике).
Если дерево разбора отражает синтаксические особенности языка, то AST отражает его логическую структуру. В AST отсутствуют следующие детали, присутствующие в дереве разбора:
Структура AST проще, чем структура дерева разбора. В ней отсутствуют излишняя вложенность, мелкие детали вроде разделителей списков и т.п.
AST больше поход на классы традиционных ООЯ, нежели на правила грамматики.
В Nitra AST содержит вычислимые поля, позволяющие производить сбор и агрегацию информации по разбираемому коду.
И наконец, в Nitra AST позволяет автоматически описывать символы. Для этого существует специальный вид AST – «декларации».
Собственно, сбор информации о символах и является конечной целью процесса типизации. Имея список символов программы, можно сгенерировать исполняемый модуль для нее.
IDE (точнее плагины к ней) используют символы для предоставления сервисов IDE.
В AST могут быть ссылки на символы. Nitra предоставляет механизм связывания (binding) этих ссылок с реальными символами.
Чтобы описать код типизации в Nitra, сначала нужно описать AST для языка и произвести отображение правил грамматики (точнее, порождаемого ими дерева разбора) на AST.
Код AST для Mini C находится в файле Nitra-Mini-C/MiniC-ast.nitra.
В Nitra AST содержит как структурные поля, содержащие информацию, получаемую путем отображения дерева разбора на AST, так и так называемые зависимые свойства (ЗС), с помощью которых производятся вычисления на AST. Чтобы сделать объяснение более понятным, сначала будет показан AST без ЗС и отображение на него дерева разбора, а потом уже будет показан AST с ЗС и описан процесс типизации.
Вот AST с удаленными ЗС:
using Nitra; using Nitra.Declarations; namespace MiniC { ast CompilationUnit { TopDeclarations : TopDeclaration*; } abstract declaration TopDeclaration { } abstract ast VarHeader { | Global | Parameter | Local } abstract declaration VarDeclaration : TopDeclaration { TypeRef : TypeReference; Header : VarHeader; | ScalarDeclaration {} | ArrayDeclaration {} } abstract ast LocalVariableContainer { } declaration FunDeclaration : TopDeclaration { ReturnTypeRef : TypeReference; Parameters : VarDeclaration*; Body : CompoundStatement; } ast CompoundStatement : BindableAst, LocalVariableContainer { LocalVariables : VarDeclaration*; Statements : Statement*; } abstract ast Statement: BindableAst, LocalVariableContainer { | Empty { } | Expression { Body : Expr; } | Compound { Nested : CompoundStatement; } | If { Condition : Expr; Body : Statement; } | IfElse { Condition : Expr; TrueBranch : Statement; FalseBranch : Statement; } | While { Condition : Expr; Body : Statement; } | ReturnVoid { } | Return { Value : Expr; } | Break { } } abstract ast Unary : Expr { Expr1 : Expr; } abstract ast NumericUnary : Unary { } abstract ast BoolUnary : Unary { } abstract ast Binary : Expr { Expr1 : Expr; Expr2 : Expr; } abstract ast SameTypesExpr : Binary { } abstract ast OrAndExpr : SameTypesExpr { } abstract ast EqualExpr : SameTypesExpr { } abstract ast NumericBinary : SameTypesExpr { } abstract ast Comparison : NumericBinary { } abstract ast Arithmetic : NumericBinary { } abstract ast Expr : BindableAst { | IntegerLiteral { Value : int; } | FloatLiteral { Value : double; } | FalseLiteral { } | TrueLiteral { } | VariableRef { Reference : Reference; } | ArrayRef { Reference : Reference; Index : Expr; } | FunCall { Arguments : Expr.Argument*; Reference : Reference; } | Argument { Expr : Expr; } | ArraySize { Reference : Reference; } | ArrayAllocation { TypeRef : TypeReference; Size : Expr; } | ScalarAssignment { Reference : Reference; Value : Expr; } | ArrayAssignment { Reference : Reference; Index : Expr; Value : Expr; } | Or : OrAndExpr { } | And : OrAndExpr { } | Equal : EqualExpr { } | NotEqual : EqualExpr { } | LessEqual : Comparison { } | Less : Comparison { } | GreaterEqual : Comparison { } | Greater : Comparison { } | Sum : Arithmetic { } | Sub : Arithmetic { } | Modulus : Arithmetic { } | Multiply : Arithmetic { } | Divide : Arithmetic { } | Minus : NumericUnary { } | LogicalNegate : BoolUnary { } } abstract ast TypeReference { | Void { } | Int { } | Float { } | Bool { } } declaration Void : Type {} declaration Int : Type {} declaration Float : Type {} declaration Bool : Type {} } |
Нетрудно заметить, что описание AST очень похоже на описания аналогичных классов, только содержит меньше «шума».
Например, следующее описание:
ast CompilationUnit
{
TopDeclarations : TopDeclaration*;
} |
описывает тип AST с именем «CompilationUnit», используемый для хранения корневой ветки в единице компиляции (файле).
CompilationUnit содержит одно поле с именем «TopDeclarations» и типом «TopDeclaration*».
Поля с AST могут быть типа AST, примитивного типа (int, float, string и т.п.) или списком этих типов. Символ «*» в определении поля «TopDeclarations», идущий за типом, как раз и указывает на то, что это список, элемент которого имеет тип TopDeclaration.
Конструкция:
abstract declaration TopDeclaration { } |
описывает абстрактную декларацию. Декларация (declaration) – это специальный тип AST. От обычного AST он отличается тем, что неявно вводит новый тип символа.
| ПРИМЕЧАНИЕ Как классы в ООЯ, AST и декларации поддерживают наследование и могут быть абстрактными. В Nitra поддерживается множественное наследование от абстрактных AST и деклараций. Абстрактные AST и декларации похожи на интерфейсы в .Net и Java, но при этом могут содержать реализацию ЗС. Все декларации неявно унаследованы от декларации Declaration, в которой объявлено поле с именем «Name». Так что у TopDeclaration (и любой другой декларации) подразумевается наличие этого свойства. Свойство «Name» содержит имя декларации. Оно используется для порождения символа, на который, впоследствии, можно ссылаться из других ветвей AST. |
Конструкция:
abstract ast VarHeader { | Global | Parameter | Local } |
объявляет абстрактный AST VarHeader и три его наследника: Global, Parameter и Local.
| ПРИМЕЧАНИЕ В отличие от обычных классов, AST неявно содержит местоположение всех свих узлов. Каждый узел AST реализует интерфейс IAst в котором объявлены свойства Span (типа NSpan) и Source (типа SourceSnapshot). Таким образом, можно всегда сопоставить AST с текстом или деревом разбора (из которых он был получен). Это нужно для корректной выдачи сообщений об ошибках в компиляторе и для сервисов IDE. |
Приведенное выше описание можно переписать с использованием синтаксиса наследования:
abstract ast VarHeader { } ast Global : VarHeader { } ast Parameter : VarHeader { } ast Local : VarHeader { } |
Различие здесь только в синтаксисе. Синтаксис в стиле вариантных типов Nemerle более выразителен, но не покрывает всех возможных случаев использования, связанных с множественным наследованием.
Можно сочетать наследование и вариантный синтаксис:
abstract declaration VarDeclaration : TopDeclaration { TypeRef : TypeReference; Header : VarHeader; | ScalarDeclaration {} | ArrayDeclaration {} } |
VarDeclaration – это абстрактная декларация, унаследованная от абстрактной же декларации TopDeclaration, и имеющая два потомка: ScalarDeclaration и ArrayDeclaration. Кроме того, в VarDeclaration объявлено два поля, TypeRef и Header. TypeRef является ссылкой на тип переменной, описываемой VarDeclaration. А Header определяет вид переменной (глобальная, параметр или локальная).
AST CompoundStatement описывает блок кода:
ast CompoundStatement : BindableAst, LocalVariableContainer
{
LocalVariables : VarDeclaration*;
Statements : Statement*;
} |
В блоке кода могут встречаться объявления переменных (поле LocalVariables) и стейтменты (поле Statements).
Интересным здесь является, то что это первый в Mini C случай использования множественного наследования AST. С одной стороны, CompoundStatement унаследован от BindableAst, объявленного в стандартной библиотеке. А с другой, от LocalVariableContainer. Оба они добавляют к CompoundStatement необходимые при типизации зависимые свойства.
В отличии от интерфейсов, абстрактные AST могут иметь ЗС, содержащие расчеты. Это делает множественное наследование мощнейшим механизмом декомпозиции и повторного использования кода.
Следующая конструкция:
abstract ast Expr : BindableAst { | Or : OrAndExpr { } |
является примером сочетания множественного наследования и вариантного синтаксиса, почерпнутого из Nemerle. Сам Nemerle не поддерживает множественного наследования для вхождений вариантов. Nitra же расширяет этот синтаксис и позволяет унаследовать вхождение также и от дополнительных типов. В данном примере AST «Or» унаследован как от «Expr», так и от «OrAndExpr».
Последним интересным моментом является описание деклараций для типов:
declaration Void : Type {} declaration Int : Type {} declaration Float : Type {} declaration Bool : Type {} |
Как уже говорилось ранее, типы в Mini C предопределены и, казалось бы, не требуют деклараций. Но в программах на Mini C неизбежно будут ссылки на эти типы, так что для них придется создать символы.
| ПРИМЕЧАНИЕ Символы Программы похожи на своеобразные СУБД. В программах есть именованные сущности, хранящие информацию, и есть ссылки на эти сущности в виде имен. Например, локальная переменная – это сущность, имеющая такие свойства, как тип, область видимости, в которой объявлена переменная, и инициализирующее выражение. У каждой переменной есть имя, идентифицирующее эту переменную в рамках области видимости, в которой она объявлена. В других частях программы можно ссылаться на переменную по ее имени. Такие именованные сущности в Nitra называются символами. Каждый символ должен иметь имя и произвольный набор свойств. Символы создаются для всех значимых сущностей в ЯП. Например, в C# символы создаются для: пространств имен, типов (классов, делегатов, перечислений, структур, встроенных типов и т.п.), членов типов (методов, свойств, полей, событий, ...), параметров методов, параметров типов, локальных переменных и т.п. Список далеко не полон. Главное – понять, что символ – это основной способ описать некоторую именованную сущность языка, на которую можно ссылаться посредством имени (простого или квалифицированного, неважно). Для одной логической сущности в программе создается один экземпляр символа. Каждый символ имеет свой тип, который может отличаться от типа других символов. У типа символов может быть несколько предков. Например, в C# у символа TopClassSymbol (класса, объявляемого в пространстве имен) может быть два предка GenericContainerTypeSymbol и TypeMemberSymbol, у символа NestedClassSymbol предками могут быть GenericContainerTypeSymbol и TypeMemberSymbol. Другими словами, для типов символов (как и для типов AST) поддерживается множественное наследование. |
Единственным способом объявить символ в Nitra является объявление декларации. Вот приведенные выше декларации и созданы, чтобы породить символы.
Все декларации типов унаследованы от декларации Type (из стандартной библиотеки). Это приводит к тому, что все символы, порождаемые описанными выше декларациями, становятся наследниками TypeSymbol (порождаемого декларацией Type). Стало быть, все символы типов имеют общего предка.
Вряд ли имеет смысл описывать каждое поле AST. Так что перейдем к отображению.
| ПРЕДУПРЕЖДЕНИЕ Если это не так, просьба написать мне об этом в комментариях к статье или по почте. |
Итак, у нас есть грамматика языка Mini C. При ее компиляции создается парсер, который при запуске порождает конкретное дерево разбора для заданного исходника. У нас также есть AST. Теперь надо создать функцию преобразования дерева разбора в AST.
Для этой цели в Nitra имеется специальный язык отображения.
Код отображения для Mini C находится в файле Nitra-Mini-C/MiniC-Mapping.nitra:
using Nitra; using Nitra.Runtime; using Nitra.Declarations; using System.Globalization; namespace MiniC { map syntax MiniCSyntax.CompilationUnit -> CompilationUnit { TopDeclarations -> TopDeclarations; } map syntax MiniCSyntax.TypeRef -> TypeReference { | Void -> Void {} | Int -> Int {} | Float -> Float {} | Bool -> Bool {} } map syntax MiniCSyntax.TopDeclaration -> TopDeclaration { | VarDeclaration -> VarDeclaration(VarHeader.Global {}) | FunDeclaration -> FunDeclaration { Name -> Name; TypeRef -> ReturnTypeRef; VarDeclarations.Item1(VarHeader.Parameter {}) -> Parameters; CompoundStatement -> Body; } } map syntax MiniCSyntax.CompoundStatement -> CompoundStatement { VarDeclarations(VarHeader.Local {}) -> LocalVariables; Statements -> Statements; } map syntax MiniCSyntax.Statement -> Statement { | Expression -> Expression { Expr -> Body; } | Empty -> Empty { } | Compound -> Compound { CompoundStatement -> Nested; } | If -> If { Expr -> Condition; Statement -> Body; } | IfElse -> IfElse { Expr -> Condition; TrueBranch -> TrueBranch; FalseBranch -> FalseBranch; } | While -> While { Expr -> Condition; Statement -> Body; } | ReturnVoid -> ReturnVoid {} | Return -> Return { Expr -> Value; } | Break -> Break {} } map syntax MiniCSyntax.Argument -> Expr.Argument { Expr -> Expr; } map syntax MiniCSyntax.Expr -> Expr { | IntegerLiteral -> IntegerLiteral { Value = ParsedValue(Digits, int.Parse(GetText(Digits))); } | FloatLiteral -> FloatLiteral { Value = ParsedValue(Digits, double.Parse(GetText(Digits), CultureInfo.InvariantCulture)); } | True -> TrueLiteral { } | False -> FalseLiteral { } | VariableRef -> VariableRef { Reference -> Reference; } | ArrayRef -> ArrayRef { Reference -> Reference; Expr -> Index; } | FunCall -> FunCall { Reference -> Reference; Arguments.Item1 -> Arguments; } | ArraySize -> ArraySize { Reference -> Reference; } | Braces -> this.Expr | ArrayAllocation -> ArrayAllocation { TypeRef -> TypeRef; Expr -> Size; } | ScalarAssignment -> ScalarAssignment { Reference -> Reference; Expr -> Value; } | ArrayAssignment -> ArrayAssignment { Reference -> Reference; Index -> Index; Expr -> Value; } | Or { Expr1 -> Expr1; Expr2 -> Expr2; } | And { Expr1 -> Expr1; Expr2 -> Expr2; } | Equal { Expr1 -> Expr1; Expr2 -> Expr2; } | NotEqual { Expr1 -> Expr1; Expr2 -> Expr2; } | LessEqual { Expr1 -> Expr1; Expr2 -> Expr2; } | Less { Expr1 -> Expr1; Expr2 -> Expr2; } | GreaterEqual { Expr1 -> Expr1; Expr2 -> Expr2; } | Greater { Expr1 -> Expr1; Expr2 -> Expr2; } | Sum { Expr1 -> Expr1; Expr2 -> Expr2; } | Sub { Expr1 -> Expr1; Expr2 -> Expr2; } | Modulus { Expr1 -> Expr1; Expr2 -> Expr2; } | Multiply { Expr1 -> Expr1; Expr2 -> Expr2; } | Divide { Expr1 -> Expr1; Expr2 -> Expr2; } | Minus { Expr -> Expr1; } | LogicalNegate { Expr -> Expr1; } | Plus -> this.Expr } map syntax MiniCSyntax.VarDeclaration (header : VarHeader) -> VarDeclaration { | Scalar -> ScalarDeclaration { Name -> Name; TypeRef -> TypeRef; header -> Header; } | Array -> ArrayDeclaration { Name -> Name; TypeRef -> TypeRef; header -> Header; } } } |
По сути, язык отображения указывает, какой узел дерева разбора взять и в какой узел AST поместить.
Зачем же нужен отдельный язык? Нельзя ли было произвести это отображение в обычном коде на языке программирования общего назначения (таком как Nemerle или C#)?
Конечно же, это сделать можно, но при этом придется проделать много однотипных операций, не пропустить и не перепутать копирование множества значений.
Задача усложняется тем, что в дереве разбора могут быть:
Кроме того, каждая ветка дерева разбора хранит информацию о местоположении, которую нужно скопировать в порождаемые ветки AST. Ошибка в копировании местоположения приведет к некорректной работе IDE и/или к неверной позиции ошибок.
В общем, это работа машины. DSL отображения скрывает все эти особенности, требуя от разработчика языка выразить только то, что необходимо для решения задачи отображения. При этом автоматически копируются местоположения, и автоматически порождаются специальные ветки AST в случае неоднозначностей и пропущенных значений.
Кроме того, язык отображения имеет ряд специальных возможностей, упрощающих решение задачи.
| ПРИМЕЧАНИЕ В будущем мы постараемся упростить процесс отображения за счет вывода информации об отображении в случаях, когда дерево разбора и AST имеют схожую структуру и имена полей. |
Итак, конструкция:
map syntax MiniCSyntax.CompilationUnit -> CompilationUnit { TopDeclarations -> TopDeclarations; } |
отображает результат разбора (т.е. дерево разбора) правила CompilationUnit из синтаксического модуля MiniCSyntax в AST типа CompilationUnit. В теле производится отображение поля TopDeclarations дерева разбора одноименному полю в AST. Красным выделены элементы дерева разбора.
Как в AST, так и в дереве разбора TopDeclarations, это список типа TopDeclaration. Nitra автоматически делает отображение для списков, если в проекте имеется отображение между типами их элементов.
В случае расширяемых правил отображение выглядит следующим образом:
map syntax MiniCSyntax.TypeRef -> TypeReference { | Void -> Void {} | Int -> Int {} | Float -> Float {} | Bool -> Bool {} } |
Здесь MiniCSyntax.TypeRef – это дерево разбора, формируемое для соответствующего правила. Void, Int, Float и Bool, выделенные в коде – это альтернативы правила TypeRef, а TypeReference – AST, у которого есть наследники Void, Int, Float и Bool (черного цвета). Полей у данных правил и AST нет, так что тела пусты. Обратите внимание, что конструкция Void {} по сути является конструктором (или инициализатором, если угодно). Она порождает экземпляр AST. При этом тип конструируемого AST должен быть наследником типа, указанного в определении отображения.
Теперь давайте рассмотрим более сложный вариант отображения – отображение для TopDeclaration:
map syntax MiniCSyntax.TopDeclaration -> TopDeclaration { | VarDeclaration -> VarDeclaration(VarHeader.Global {}) | FunDeclaration -> FunDeclaration { Name -> Name; TypeRef -> ReturnTypeRef; VarDeclarations.Item1(VarHeader.Parameter {}) -> Parameters; CompoundStatement -> Body; } } |
Как и TypeRef, правило MiniCSyntax.TopDeclaration является расширяемым и состоит из двух вхождений VarDeclaration и FunDeclaration. AST TopDeclaration также имеет двух наследников: VarDeclaration и FunDeclaration.
Этот случай более сложный потому что в нем используются параметризованное правило отображения для VarDeclaration (выделено красным). Вот как оно выглядит:
map syntax MiniCSyntax.VarDeclaration(header : VarHeader) -> VarDeclaration { | Scalar -> ScalarDeclaration { Name -> Name; TypeRef -> TypeRef; header -> Header; } | Array -> ArrayDeclaration { Name -> Name; TypeRef -> TypeRef; header -> Header; } } |
У этого правила отображения имеется параметр header (выделен красным). VarHeader – это тип AST, описанный выше. Значение этого параметра передается при применении правила:
VarDeclaration(VarHeader.Global {}) |
Здесь «VarHeader.Global {}» – это конструируемый по месту AST-тип VarHeader.Global. В конструируемом по месту AST можно задавать значения полей, но в данном случае это не нужно. В данном случае VarHeader задает тип переменной (Global, Parameter или Local).
Параметризованные правила могут быть перегруженными (по числу и типу параметров), но в данном случае это не требовалось.
Значение параметра используется для задания значения поля Header. Так как тип параметра уже AST, отображение не требуется. Если аргументом параметризированного правила будет поле дерева разбора, для которого есть отображение, оно будет задействовано неявно.
В правиле отображения для MiniCSyntax.TopDeclaration есть два обращения к параметризованному правилу MiniCSyntax.VarDeclaration. Первый мы уже рассмотрели. Давайте рассмотрим второй:
VarDeclarations.Item1(VarHeader.Parameter {}) -> Parameters; |
VarDeclarations – это поле дерева разбора, созданное для правила, выделенного красным:
| FunDeclaration = TypeRef Name "(" (VarDeclaration; "," sm)* ")" CompoundStatement |
Имя автоматически формируется Nitra (берется имя его элемента, которое приводится во множественное число).
Отображение происходит на поле Parameters, тип которого «VarDeclaration*» (список VarDeclaration).
VarDeclarations содержит два поля, Item1 и Item2. Первое содержит список VarDeclaration в котором лежит дерево разбора для параметров, а второе содержит список NSpan, описывающий местоположение запятых (используемых в качестве разделителей параметров). Так как в AST разделители параметров не хранятся, нужно произвести отображение первого списка (Item1), в котором лежат деревья разбора для параметров.
Чтобы добраться до этого списка, используется доступ через точку «VarDeclarations.Item1». Результатом этого является список. Далее включается «магия» Nitra. Она видит, что тип VarDeclarations.Item1 – это список, и автоматически добавляет код преобразования списков. Так что AST, передающийся в качестве параметра:
VarHeader.Parameter {} |
дублируется для каждого из параметров.
Результатом отображения для:
VarDeclarations.Item1(VarHeader.Parameter {}) |
является VarDeclaration* (список VarDeclaration), что совпадает с типом поля Parameters AST-а (идущего за стрелкой).
В результате для каждого элемента в списке параметров применяется правило MiniCSyntax.VarDeclaration, которому в качестве аргумента передается «VarHeader.Parameter {}». В результате формируется список параметров, который помещается в поле Parameters AST-а TopDeclaration. Вот так Nitra позволяет отображать списки без циклов и прочих сложностей.
Пропустим неинтересные правила отображения и перейдем к разбору правила MiniCSyntax.Expr. Это правило интересно двумя аспектами. Во-первых, в нем встречается «ручное» отображение:
| IntegerLiteral -> IntegerLiteral
{
Value = ParsedValue(Digits, int.Parse(GetText(Digits)));
} |
Value – это поле AST типа int. Поля примитивных типов Nitra оборачивает в специальный тип-обертку ParsedValue. Этот тип решает две задачи:
Конструктор ParsedValue принимает два значения: местоположение (NSpan) и само значение. Если есть необходимость хранить в AST примитивы или пользовательские типы (например, цвета) следует помнить, что их нужно оборачивать в ParsedValue.
Так как поле (дерева разбора) Digits имеет тип NSpan (в следствии того, что оно сформировано для regex-правил) оно просто передается в качестве первого аргумента. Так как значение поля int, а поле Digits представляет собой местоположение спарсенного текста, нужно сначала извлечь текст, а затем преобразовать его в число. Метод GetText (объявленный в дереве разбора) позволяет получить текст по местоположению, а стандартная .Net-функция int.Parse позволяет преобразовать текст в число.
| ПРИМЕЧАНИЕ В будущих версиях будет реализована встроенная поддержка для примитивных типов. И данный код будет выглядеть следующим образом: «Digits -> Value». |
Второе, на что стоит обратить внимание в правиле отображения выражений, это:
| Braces -> this.Expr |
В AST скобки не нужны, так как он по определению однозначен. Посему нужно просто взять значение поля Expr.Braces.Expr, отобразить его в AST и вернуть как значение текущего отображения. Конструкция «this.» указывает Nitra, что справа от «->» идет обращение к полю дерева разбора. Это позволяет Nitra понять, что требуется преобразовать его в AST и вернуть полученное значение. Таким образом, данная конструкция может рассматриваться как «проброс» значения поля.
Единственное о чем осталось сказать в отношении отображения – это напомнить, что отображение для правил Reference и Name делается непосредственно Nitra. Об этом говорилось выше, но, скорее всего, вы уже забыли об этом.
В процессе типизации (семантического анализа) формируются символы. В них агрегируется вся информация, получаемая в процессе типизации.
В Mini C есть только три типа сущностей, на которые можно сослаться (по имени):
Именно эти сущности и должны быть символами Nitra. Символ агрегирует информацию о сущности программы и позволяет на нее (точнее на себя) сослаться. Обычно ссылка на символ производится по его имени. Поэтому в Nitra символы имеют встроенную поддержку имен (и работы с ними).
В Nitra символы формируются автоматически на основе деклараций. Как говорилось ранее, декларации – это специальный вид AST, имеющий имя и кое-какие особенности.
Вот список деклараций Mini C:
abstract declaration TopDeclaration { } abstract declaration VarDeclaration : TopDeclaration { TypeRef : TypeReference; Header : VarHeader; | ScalarDeclaration {} | ArrayDeclaration {} } declaration FunDeclaration : TopDeclaration { ReturnTypeRef : TypeReference; Parameters : VarDeclaration*; Body : CompoundStatement; } declaration Root : Container {} declaration Void : Type {} declaration Int : Type {} declaration Float : Type {} declaration Bool : Type {} |
По ним Nitra, формирует следующие символы: TopDeclarationSymbol, VarDeclarationSymbol, ScalarDeclarationSymbol, ArrayDeclarationSymbol, FunDeclarationSymbol, VoidSymbol, IntSymbol, FloatSymbol и BoolSymbol. Иерархия наследования символов повторяет иерархию наследования деклараций. Вот как выглядит дерево наследования для символов Mini C:
RootSymbol
TopDeclarationSymbol
VarDeclarationSymbol
ScalarDeclarationSymbol
ArrayDeclarationSymbol
FunDeclarationSymbol
TypeSymbol
VoidSymbol
IntSymbol
FloatSymbol
BoolSymbol |
RootSymbol – это корневой символ. Символы глобальных переменных и функций являются его членами. Его декларация отсутствует в исходных файлах на Mini C. А его единственный экземпляр создается в коде инициализации проекта.
Задачей семантического анализа является сборка информации о программе и проверка внутренних условиях. Важнейшей подзадачей семантического анализа является определение типов выражений и проверка соответствия типов связанных выражений.
При создании компилятора традиционными средствами семантический анализ выполняется в виде ряда проходов по AST. Есть языки, которые (теоретически) могут быть типизированы в один проход. К таким языкам относятся языки родом из 70-х годов прошлого века, например, C и Pascal. Но в наше время такие языки скорее являются устаревшими. Современные процессоры и большой объем памяти подталкивают авторов языков использовать многопроходные схемы. Это позволяет сделать язык более удобным для человека, менее многословным и более модульным.
Nitra изначально рассчитывалась на разработку многопроходных языков со сложной логикой. Mini C не позволяет продемонстрировать всей мощи Nitra, но и для такого простого языка Nitra является очень удобным инструментом.
Типизация в Nitra описывается прямо в AST, в виде зависимых свойств (ЗС) и вычислений на них. Зависимые свойства вычисляются в порядке своих зависимостей. Если первое свойство ссылается на второе, то сначала будет вычислено второе свойство, а потом уже первое. В процессе вычисления строится граф зависимости свойств, а вычисления являются как бы виртуальным обходом этого графа. Это позволяет не задавать ход вычислений явно и получать уникальный код вычислений для каждого конкретного дерева разбора. Кроме того, использование ЗС позволяет создавать на Nitra расширяемые языки, т.е. языки, синтаксис которых может изменяться прямо во время парсинга.
Ниже приведен AST с ЗС и вычислениями на них (файл Nitra-Mini-C/MiniC-ast.nitra):
using Nitra; using Nitra.Declarations; using System.Linq; using System.Collections.Generic; namespace MiniC { ast CompilationUnit { in ContainingTable : TableScope; TopDeclarations.ContainingTable = ContainingTable; TopDeclarations : TopDeclaration*; } abstract declaration TopDeclaration {} abstract ast VarHeader { | Global | Parameter | Local } abstract declaration VarDeclaration : TopDeclaration { symbol { in Type : TypeSymbol; in VarKind : VariableKind; SpanClass = MiniC.VariableSpanClass; Kind = "variable"; } Symbol.Type = TypeRef.Type; Symbol.VarKind = VariableKind.FromHeader(Header); TypeRef : TypeReference; Header : VarHeader; | ScalarDeclaration {} | ArrayDeclaration {} } abstract ast LocalVariableContainer { in DeclaredIn : FunDeclarationSymbol; in Loop : option[Statement.While] = None(); } declaration FunDeclaration : TopDeclaration { symbol { in ReturnType : TypeSymbol; in Parameters : ImmutableArray[VarDeclarationSymbol]; in FunScope : Scope; out ParameterScope : TableScope = TableScope("parameters", this); SpanClass = MiniC.FunctionSpanClass; Kind = "function"; } Symbol.ReturnType = ReturnTypeRef.Type; Parameters.ContainingTable = Symbol.ParameterScope; Symbol.FunScope = ContainingTable.HideWith( Symbol.ParameterScope); Symbol.Parameters = Parameters.Symbol; Body.DeclaredIn = Symbol; Body.OuterScope = Symbol.FunScope; when (Name.Text == "main" && !MiniCTypeUnifier.Instance.TryUnify(Symbol.ReturnType, context.GetVoidSymbol()) && !MiniCTypeUnifier.Instance.TryUnify(Symbol.ReturnType, context.GetIntSymbol()) ) ReturnTypeRef.Error(context, $"Return type of main function " "must be void or int, but it's $(Symbol.ReturnType)"); ReturnTypeRef : TypeReference; Parameters : VarDeclaration*; Body : CompoundStatement; } ast CompoundStatement : BindableAst, LocalVariableContainer { in OuterScope : Scope; out LocalVariableScope : TableScope = TableScope("local variables", DeclaredIn); LocalVariables.ContainingTable = LocalVariableScope; Scope = OuterScope.HideWith(LocalVariableScope); Statements.Scope = Scope; Statements.DeclaredIn = DeclaredIn; Statements.Loop = Loop; LocalVariables : VarDeclaration*; Statements : Statement*; } abstract ast Statement: BindableAst, LocalVariableContainer { | Empty {} | Expression { Body.Scope = Scope; Body : Expr; } | Compound { Nested.OuterScope = Scope; Nested.DeclaredIn = DeclaredIn; Nested.Loop = Loop; Nested : CompoundStatement; } | If { Condition.Scope = Scope; Condition.Used = true; Body.Scope = Scope; Body.DeclaredIn = DeclaredIn; Body.Loop = Loop; Condition : Expr; Body : Statement; } | IfElse { Condition.Scope = Scope; Condition.Used = true; TrueBranch.Scope = Scope; FalseBranch.Scope = Scope; TrueBranch.DeclaredIn = DeclaredIn; FalseBranch.DeclaredIn = DeclaredIn; TrueBranch.Loop = Loop; FalseBranch.Loop = Loop; Condition : Expr; TrueBranch : Statement; FalseBranch : Statement; } | While { Condition.Scope = Scope; Condition.Used = true; Body.Scope = Scope; Body.DeclaredIn = DeclaredIn; Body.Loop = Some(this); Condition : Expr; Body : Statement; } | ReturnVoid {} | Return { Value.Scope = Scope; Value.Used = true; unless (MiniCTypeUnifier.Instance.TryUnify(Value.Type, DeclaredIn.ReturnType) ) Value.Error(context, $"Expected $(DeclaredIn.ReturnType) but found $(Value.Type)"); Value : Expr; } | Break { when (Loop.IsNone) Error(context, "Break out of while."); } } abstract ast Unary : Expr { Expr1.Scope = Scope; Expr1.Used = true; Type = Expr1.Type; Expr1 : Expr; } abstract ast NumericUnary : Unary { unless (MiniCTypeUnifier.Instance.TryUnify(Expr1.Type, context.GetIntSymbol()) || MiniCTypeUnifier.Instance.TryUnify(Expr1.Type, context.GetFloatSymbol()) ) Expr1.Error(context, $"Expected int or float, but found $(self.Expr1.Type)"); } abstract ast BoolUnary : Unary { unless (MiniCTypeUnifier.Instance.TryUnify(Expr1.Type, context.GetBoolSymbol()) ) Expr1.Error(context, $"Expected bool but found $(self.Expr1.Type)"); } abstract ast Binary : Expr { Expr1.Scope = Scope; Expr2.Scope = Scope; Expr1.Used = true; Expr2.Used = true; Expr1 : Expr; Expr2 : Expr; } abstract ast SameTypesExpr : Binary { unless (MiniCTypeUnifier.Instance.TryUnify(Expr1.Type, Expr2.Type)) Expr2.Error(context, $"$(self.Expr2.Type) is not compatible with $(self.Expr1.Type)."); } abstract ast OrAndExpr : SameTypesExpr { Type = context.GetBoolSymbol(); unless (MiniCTypeUnifier.Instance.TryUnify(Expr1.Type, context.GetBoolSymbol()) ) Expr1.Error(context, $"Expected boolean expression but found $(self.Expr1.Type)."); } abstract ast EqualExpr : SameTypesExpr { Type = context.GetBoolSymbol(); } abstract ast NumericBinary : SameTypesExpr { unless (MiniCTypeUnifier.Instance.TryUnify(Expr1.Type, context.GetIntSymbol()) || MiniCTypeUnifier.Instance.TryUnify(Expr1.Type, context.GetFloatSymbol()) ) Expr1.Error(context, $"Expected int or float, but found $(self.Expr1.Type)"); } abstract ast Comparison : NumericBinary { Type = context.GetBoolSymbol(); } abstract ast Arithmetic : NumericBinary { Type = Expr1.Type; } abstract ast Expr : BindableAst { in Type : TypeSymbol = context.GetVoidSymbol(); in ExpectedType : TypeSymbol = MiniCTypeUnifier.Instance.CreateTypeVar(); in Used : bool = false; unless (MiniCTypeUnifier.Instance.TryUnify(Type, ExpectedType)) Error(context, $"Expected $(self.ExpectedType) but got $(self.Type)"); | IntegerLiteral { Type = context.GetIntSymbol(); Value : int; } | FloatLiteral { Type = context.GetFloatSymbol(); Value : double; } | FalseLiteral { Type = context.GetBoolSymbol(); } | TrueLiteral { Type = context.GetBoolSymbol(); } | VariableRef { out Ref : Ref[VarDeclaration.ScalarDeclarationSymbol] = Reference.Ref.Resolve(); Reference.Scope = Scope; Type = Ref.Symbol.Type; Reference : Reference; } | ArrayRef { out Ref : Ref[VarDeclaration.ArrayDeclarationSymbol] = Reference.Ref.Resolve(); Reference.Scope = Scope; Index.Scope = Scope; Index.ExpectedType = context.GetIntSymbol(); Index.Used = true; Type = Ref.Symbol.Type; Reference : Reference; Index : Expr; } | FunCall { out Ref : Ref[FunDeclarationSymbol] = Reference.Ref.Resolve(); Reference.Scope = Scope; Arguments.Scope = Scope; when (Arguments.Count != Ref.Symbol.Parameters.Count) Reference.Error(context, $"Wrong number of arguments: expected " "$(Ref.Symbol.Parameters.Count), but given $(Arguments.Count)"); Arguments.IndexIn = 0; Arguments.Func = Ref.Symbol; Arguments.Used = true; Type = Ref.Symbol.ReturnType; Arguments : Expr.Argument*; Reference : Reference; } | Argument { inout Index : int; in Func : FunDeclarationSymbol; Expr.Scope = Scope; Expr.Used = true; IndexOut = IndexIn + 1; ExpectedType = AstUtils.GetParameterType(Func, IndexIn); Type = Expr.Type; Expr : Expr; } | ArraySize { out Ref : Ref[VarDeclaration.ArrayDeclarationSymbol] = Reference.Ref.Resolve(); Reference.Scope = Scope; Type = context.GetIntSymbol(); Reference : Reference; } | ArrayAllocation { Type = TypeRef.Type; Size.Scope = Scope; Size.ExpectedType = context.GetIntSymbol(); Size.Used = true; TypeRef : TypeReference; Size : Expr; } | ScalarAssignment { out Ref : Ref[VarDeclarationSymbol] = Reference.Ref.Resolve(); Reference.Scope = Scope; Value.Scope = Scope; Value.ExpectedType = Ref.Symbol.Type; Value.Used = true; Used = true; Reference : Reference; Value : Expr; } | ArrayAssignment { out Ref : Ref[VarDeclaration.ArrayDeclarationSymbol] = Reference.Ref.Resolve(); Reference.Scope = Scope; Index.Scope = Scope; Index.ExpectedType = context.GetIntSymbol(); Index.Used = true; Value.Scope = Scope; Value.ExpectedType = Ref.Symbol.Type; Value.Used = true; Used = true; Reference : Reference; Index : Expr; Value : Expr; } | Or : OrAndExpr {} | And : OrAndExpr {} | Equal : EqualExpr {} | NotEqual : EqualExpr {} | LessEqual : Comparison {} | Less : Comparison {} | GreaterEqual : Comparison {} | Greater : Comparison {} | Sum : Arithmetic {} | Sub : Arithmetic {} | Modulus : Arithmetic {} | Multiply : Arithmetic {} | Divide : Arithmetic {} | Minus : NumericUnary {} | LogicalNegate : BoolUnary {} } abstract ast TypeReference { in Type : TypeSymbol; | Void { Type = context.GetVoidSymbol(); } | Int { Type = context.GetIntSymbol(); } | Float { Type = context.GetFloatSymbol(); } | Bool { Type = context.GetBoolSymbol(); } } declaration Root : Container {} declaration Void : Type {} declaration Int : Type {} declaration Float : Type {} declaration Bool : Type {} } |
В корневой ветке:
ast CompilationUnit { in ContainingTable : TableScope; TopDeclarations.ContainingTable = ContainingTable; TopDeclarations : TopDeclaration*; } |
объявлено единственное зависимое свойство (ЗС) ContainingTable типа TableScope. В него помещается глобальная таблица имен. В эту таблицу помещаются все декларации верхнего уровня: функции и глобальные переменные.
В Nitra есть встроенная поддержка областей видимости (Scopes). TableScope – это специальный видов области видимости, позволяющий добавлять (и хранить) символы в нем. Он выполняет роль таблицы имен.
Свойство CompilationUnit.ContainingTable задается в коде, отвечающем за работу с проектом. О нем будет сказано позже (в разделе, посвященном IProjectSupport).
Строка:
TopDeclarations.ContainingTable = ContainingTable; |
присваивает значение зависимого свойства ContainingTable (из CompilationUnit) одноименному зависимому свойству из AST TopDeclaration.
TopDeclarations – это свойство, содержащее список TopDeclaration. В Nitra списки – это специализированные объекты, у которых есть те же свойства, что и у типа, являющегося элементом списка. При присвоении значения свойству списка это значение присваивается одноименным свойствам всех элементов списка. Таким образом, данная строка присваивает таблицу имен свойствам ContainingTable всех деклараций в проекте Mini C.
ЗС ContainingTable объявлено не в самом TopDeclaration, а в одном из его наследников. TopDeclaration является декларацией, а декларации неявно наследуются от Declaration, а тот является наследником ScopedAst, в котором и объявлено свойство ContainingTable.
Так как ContainingTable является ЗС, то как только этому свойству присваивается значение, производятся связанные с ним вычисления. В данном случае происходит создание символов и добавление их в таблицу имен, помещенную в это ЗС. Создание символа и добавление его в таблицу имен выполняет код, генерируемый Nitra. Для разработчика, использующего Nitra, этот происходит автоматически. Ему достаточно только лишь присвоить значения ContainingTable. Все остальное сделает Nitra.
Таким образом, одна строчка приводит к тому, что в таблицу имен попадают символы для описанных в коде глобальных переменных и функций.
Первым наследником TopDeclaration является VarDeclaration:
abstract declaration VarDeclaration : TopDeclaration { symbol { in Type : TypeSymbol; in VarKind : VariableKind; SpanClass = MiniC.VariableSpanClass; Kind = "variable"; } Symbol.Type = TypeRef.Type; Symbol.VarKind = VariableKind.FromHeader(Header); TypeRef : TypeReference; Header : VarHeader; | ScalarDeclaration {} | ArrayDeclaration {} } |
VarDeclaration является декларацией, а стало быть, для нее создается символ, который помещается в таблицу имен из свойства ContainingTable, о котором говорилось выше.
Раздел «symbol» описывает ЗС, описанные на символе VarDeclarationSymbol: Type и VarKind, а так же присвоения встроенных свойств SpanClass и Kind.
SpanClass используется для оформления символов определенным стилем, а Kind используется при текстовом представлении символа (например, в списке автодополнения в IDE).
VarKind – имеет тип VariableKind. Это пользовательский тип, описанный в коде (на Nemerle). Функция FromHeader преобразует VarHeader в VariableKind:
public variant VariableKind { | Global | Parameter | Local public static FromHeader(header: VarHeader) : VariableKind { match (header) { | Global => Global() | Parameter => Parameter() | Local => Local() | _ => assert(false, $"Unexpected var header $header") } } } |
Свойство VarKind присваивается в строчке:
Symbol.VarKind = VariableKind.FromHeader(Header); |
эта строчка вычисляется сразу после того как вычисляется свойство Symbol (объявленное в Declaration). Свойство же символ устанавливается в момент создания символов.
Зависимость между свойствами автоматически выстраивает порядок вычислений в правильном порядке. Разработчик должен лишь обеспечить, чтобы между свойствами не было циклической зависимости.
Строка:
Symbol.Type = TypeRef.Type; |
присваивает значение свойству Type символа VarDeclarationSymbol. Оно так же зависит от вычисленности свойства Symbol.
TypeRef.Type – это ЗС описанное в AST TypeReference:
abstract ast TypeReference { in Type : TypeSymbol; | Void { Type = context.GetVoidSymbol(); } | Int { Type = context.GetIntSymbol(); } | Float { Type = context.GetFloatSymbol(); } | Bool { Type = context.GetBoolSymbol(); } } |
Тип этого ЗС – TypeSymbol. Он описан в стандартной библиотеке. Подсистема вывода типов работает с наследниками этого символа, так что декларации типов нужно наследовать от Type.
Для вычисления этого ЗС используется обращение к методам context.GetXxxSymbol(), где Xxx.
«context» - это локальная переменная, доступная в коде вычисления ЗС. Контекст создается автором языка и передается в вычислитель ЗС внутри метода RefreshProject, запускающего вычисления ЗС для всего проекта.
Контекст должен иметь тип DependentPropertyEvalContext или унаследованный от него. В Mini C создан наследник этого типа. Его имя – MiniCDependentPropertyEvalContext. В нем объявлены поля, в которые и помещаются ссылки на символы предопределенных типов:
[Record] public class MiniCDependentPropertyEvalContext : DependentPropertyEvalContext { public Void : VoidSymbol; public Int : IntSymbol; public Float : FloatSymbol; public Bool : BoolSymbol; } |
Создание экземпляра контекста и инициализация данных полей производится в методе RefreshReferences.
Но обратиться из кода ЗС к данным полям не получится, так как в коде ЗС контекст имеет тип DependentPropertyEvalContext. Для доступа к этим полям создан ряд методов расширений (описанных в модуле AstUtils в файле Nitra-Mini-C/AstUtils.n). Именно они и используются в коде расчета свойства Type:
| Void { Type = context.GetVoidSymbol(); } |
Так как в коде расчета данных свойств нет обращения к другим ЗС, этот код выполняется немедленно, зависимые свойства Type сразу же становятся вычисленными и приводят к вычислению зависящих от них свойств VarDeclarationSymbol.Type.
Расчеты в FunDeclaration несколько сложнее:
declaration FunDeclaration : TopDeclaration { symbol { in ReturnType : TypeSymbol; in Parameters : ImmutableArray[VarDeclarationSymbol]; in FunScope : Scope; out ParameterScope : TableScope = TableScope("parameters", this); SpanClass = MiniC.FunctionSpanClass; Kind = "function"; } Symbol.ReturnType = ReturnTypeRef.Type; Parameters.ContainingTable = Symbol.ParameterScope; Symbol.FunScope = ContainingTable.HideWith(Symbol.ParameterScope); Symbol.Parameters = Parameters.Symbol; Body.DeclaredIn = Symbol; Body.OuterScope = Symbol.FunScope; when (Name.Text == "main" && !MiniCTypeUnifier.Instance.TryUnify(Symbol.ReturnType, context.GetVoidSymbol()) && !MiniCTypeUnifier.Instance.TryUnify(Symbol.ReturnType, context.GetIntSymbol()) ) ReturnTypeRef.Error(context, $"Return type of main function " "must be void or int, but it's $(Symbol.ReturnType)"); ReturnTypeRef : TypeReference; Parameters : VarDeclaration*; Body : CompoundStatement; } |
У поля есть только тип, а у функции (кроме типа возвращаемого значения) есть еще список параметров и тело (код).
Для типизации вызова функций в символе, описывающем функцию, нужно сформировать список параметров (чтобы можно было получать доступ к параметрам по индексу). Этот список помещается в ЗС Parameters (объявленное в разделе «symbol»). Тип этого свойства – «IList[VarDeclarationSymbol]», т.е. список символов описывающих переменные.
Чтобы символы создались, нужно задать им таблицу имен. Для этого нужно установить их свойство ContainingTable. Так как символы параметров должны быть видны только в рамках тела метода, для них нужно создать отдельную таблицу имен. Она помещается в ЗС ParameterScope:
out ParameterScope : TableScope = TableScope("parameters", this); |
Первый параметр позволяет задать имя таблице имен, что упрощает отладку.
Данная таблица имен присваивается свойству ContainingTable списка параметров:
Parameters.ContainingTable = Symbol.ParameterScope; |
Symbol – это ЗС, объявляемое в Declaration (неявно базовом типе для всех деклараций). Через него в коде декларации можно получить доступ к символу порождаемому этой декларацией.
Данное присвоение копирует значение в одноименные свойства каждого из параметров. Как только в них помещается таблица имен, происходит создание символов параметров. Это приводит к вычислению свойства Parameters.Symbol, что приводит к вычислению строки:
Symbol.Parameters = Parameters.Symbol; |
Так как свойство Symbol декларации являются out-свойством, одноименное свойство в списке параметров (доступном через поле Parameters) имеет тип:
ImmutableArray[FunDeclarationSymbol] |
что совпадает с типом ЗС Parameters, объявленного в символе.
Строка:
Symbol.FunScope = ContainingTable.HideWith(Symbol.ParameterScope); |
формирует новую область видимости путем комбинации двух других. В ContainingTable находится глобальная таблица имен. Метод HideWith формирует новую область видимости в которой символы из глобальной таблицы имен скрываются символами параметров. В результате, если имеются глобальная переменная и параметр с одинаковым именем, то при связывании этого имени будет выбран символ параметра, а не глобальной переменной. Подробнее области видимости описаны здесь.
Полученная область видимости помещается в свойство OuterScop тела функции:
Body.OuterScope = Symbol.FunScope; |
после присвоения этого свойства и помещения символа в свойство DeclaredIn:
Body.DeclaredIn = Symbol; |
начинается типизация тела функции.
В Mini C (как и в C) локальные переменные могут объявляться только вначале блока. Кроме того, телом функции всегда является блок. В Mini C блоку соответствует AST CompoundStatement:
ast CompoundStatement : BindableAst, LocalVariableContainer { in OuterScope : Scope; out LocalVariableScope : TableScope = TableScope("local variables", DeclaredIn); LocalVariables.ContainingTable = LocalVariableScope; Scope = OuterScope.HideWith(LocalVariableScope); Statements.Scope = Scope; Statements.DeclaredIn = DeclaredIn; Statements.Loop = Loop; LocalVariables : VarDeclaration*; Statements : Statement*; } |
Поле Body имеет тип CompoundStatement.
ЗС LocalVariableScope хранит таблицу имен для текущего блока. Переменные, объявленные в блоке, добавляются в нее. Чтобы это происходило, ссылка на таблицу имен помещается в ЗС ContainingTable списка переменных:
LocalVariables.ContainingTable = LocalVariableScope; |
и, в соответствии с магией ЗС для списков, распространяется всем декларациям переменных. Присвоение этого свойства приводит к созданию символов локальных переменных.
В базовом AST BindableAst объявлено ЗС Scope. Это свойство используется для хранения текущей области видимости. Она используется для связывания имен в текущем AST. Связывание имен отвечает за то, как будет интерпретироваться ссылка на имя.
Так как свойство Scope принадлежит к стадии «1», весь код, пытающийся прочесть его значение, откладывается до стадии «1» (вычисления ЗС начинаются на нулевой стадии). Однако присваивать это свойство можно и на более ранних стадиях. Строка:
Scope = OuterScope.HideWith(LocalVariableScope); |
формирует новую область видимости из внешней области видимости (OuterScope) и таблицы имен локальных переменных (LocalVariableScope). Как и в прошлый раз, локальные переменные скрывают одноименные переменные из внешней области видимости.
Ссылка на текущую область видимости передается вложенным стейтментам:
Statements.Scope = Scope; |
Далее ссылка на символ текущей функции копируется из ЗС DeclaredIn в одноименное свойство вложенных стейтментов:
Statements.DeclaredIn = DeclaredIn; |
При типизации стейтмента «break» нужно знать, к какому циклу применяется этот оператор. Так как «break» может быть глубоко вложен в другие стейтменты, нужно в каждом из них хранить значение текущего цикла. Для этого значение текущего цикла копируется из ЗС Loop в одноименное ЗС вложенных стейтментов.
Statements.Loop = Loop; |
Само свойство Loop определено в базовом AST LocalVariableContainer. От него унаследован не только CompoundStatement, но и Statement.
После того как все ЗС становятся вычисленными, начинается типизация вложенных стейтментов.
Код Statement довольно прост и в основном занимается передачей значений текущей области видимости (ЗС Scope), текущего цикла (ЗС Loop) и текущей функции (ЗС DeclaredIn). По этому мы не будем разбирать их все. Вместо этого остановимся на отдельных стейтментах.
abstract ast Statement: BindableAst, LocalVariableContainer
{
... |
Начнем с цикла:
| While
{
Condition.Scope = Scope;
Condition.Used = true;
Body.Scope = Scope;
Body.DeclaredIn = DeclaredIn;
Body.Loop = Some(this);
Condition : Expr;
Body : Statement;
} |
В отличие от других стейтментов, которые просто протаскивают значение своего ЗС Loop во вложенные стейтменты, While помещает в Body.Loop ссылку на себя:
Body.Loop = Some(this); |
Свойство Loop объявлено в LocalVariableContainer как опциональное значение:
abstract ast LocalVariableContainer { in DeclaredIn : FunDeclarationSymbol; in Loop : option[Statement.While] = None(); } |
Это позволяет или передавать в него конкретное значение, завернутое в Some(), или значение None(), означающее «отсутствие значения». По умолчанию ЗС Loop содержит None(), что говорит, что текущий стейтмент не находится внутри цикла.
Стейтменты же внутри вложенного в цикл блока кода содержат в свойстве Loop ссылку на AST цикла, завернутую в Some().
В Statement.Compound в общем-то нет ничего интересного, но это обертка над CompoundStatement:
| Compound
{
Nested.OuterScope = Scope;
Nested.DeclaredIn = DeclaredIn;
Nested.Loop = Loop;
Nested : CompoundStatement;
} |
CompoundStatement и Statement являются взаимно рекурсивными. В CompoundStatement могут быть Statement-ы, а в Statement могут содержаться CompoundStatement-ы.
Statement.Return интересен наличием проверки:
| Return
{
Value.Scope = Scope;
Value.Used = true;
unless (MiniCTypeUnifier.Instance.TryUnify(Value.Type,
DeclaredIn.ReturnType)
)
Value.Error(context,
$"Expected $(DeclaredIn.ReturnType) but found $(Value.Type)");
Value : Expr;
} |
Конструкция:
unless (MiniCTypeUnifier.Instance.TryUnify(Value.Type, DeclaredIn.ReturnType)) Value.Error(context, $"Expected $(DeclaredIn.ReturnType) but found $(Value.Type)"); |
Очень похожа на императивную проверку, но это не так. Это тоже зависимое вычисление. Причем вычисление производимое ровно один раз (вне зависимости от количества проходов осуществляемых системой вычисления ЗС).
Вызов Value.Error() формирует сообщение об ошибке. Но этот вызов осуществляется только после того, как все использованные в выражении ЗС будут вычислены. Таким образом, сообщение об ошибке появится (или не появится), как только это будет возможно (как только для этого будут готовы все данные).
Данная конструкция проверяет, совместимы ли типы возвращаемого значения текущей функции и тип выражения. Если это не так, выводится сообщение об ошибке в котором указывается, какой тип ожидался, а какой был обнаружен.
Похожая проверка осуществляется в Statement.Break:
| Break
{
when (Loop.IsNone)
Error(context, "Break out of while.");
} |
Здесь проверяется, задано ли значение свойства Loop. Если оно не задано (Loop.IsNone вернет истину), выводится сообщение об ошибке.
Обратите внимание, что в первом примере для вывода сообщения об ошибке использовался вызов Value.Error(), а в данном случае просто Error(). Разница между ними заключается лишь в том, какое местоположение ошибки будет указано. При вызове Value.Error() будет использовано местоположение выражения Value, а во втором случае это будет местоположение всего стейтмента Break.
Собственно именно типизация выражений и может по праву называться типизацией, а не более абстрактным термином «семантический анализ», так как проверка типов характерна именно для выражений.
В Mini C набор типов ограничен четырьмя предопределенными типами. В этом языке нет ни неявного приведения типов, ни перегрузок, ни каких либо других сложных операций с типами. Поэтому проверку типов для столь простого языка можно было организовать и без использования мощных возможностей Nitra. Однако цель этого языка – на простом примере продемонстрировать разработку ЯП на Nitra. Посему для проверки типов в Mini C используется стандартный механизм работы с типами Nitra. Когда он проектировался, то подразумевалось, что с его помощью можно будет осуществлять любую обработку типов, включая такие сложные вещи, как:
Для этих целей в Nitra реализована подсистема логической унификации типов (аналогичная унификации в логическом программировании).
Выражение в Mini C представляет AST Expr:
abstract ast Expr : BindableAst { in Type : TypeSymbol = context.GetVoidSymbol(); in ExpectedType : TypeSymbol = MiniCTypeUnifier.Instance.CreateTypeVar(); in Used : bool = false; unless (MiniCTypeUnifier.Instance.TryUnify(Type, ExpectedType)) Error(context, $"Expected $(self.ExpectedType) but got $(self.Type)"); |
ЗС Type предназначена для хранения типа выражения. Оно имеет значение по умолчанию – тип void. Но это значение используется только если ЗС не будет задано где-то в другом месте.
Также у выражения есть ожидаемый тип. Он хранится в ExpectedType. Использование двух типов, ожидаемого и реального – это классический прием, используемый в более сложных языках. В Mini C можно было бы обойтись и одним Type, но так как это демонстрационный язык, было принято решение сделать все как во «взрослых» языках (с использованием ExpectedType и подсистемы унификации типов).
Во «взрослых» наличие ExpectedType позволяет добавить неявное приведение типов. В Mini C оно не поддерживается, но зато поддерживаются сообщении о несоответствии типов. ExpectedType позволяет упростить эту процедуру.
Значением по умолчанию для ExpectedType является переменная типа. Переменная является наследником символа типа. Она может быть связана с любыми типом (причем эта связь может производиться отложено и опосредовано), а может быть не связанной (свободной). По умолчанию переменная не связана, что означает, что она может принять любое значение впоследствии. Переменная типа создается функций CreateTypeVar(). Эта функция объявлен в классе-унификаторе (MiniCTypeUnifier):
public sealed class MiniCTypeUnifier : TypeUnifier { public static Instance : MiniCTypeUnifier = MiniCTypeUnifier(); protected override IsSubtype(subtype : TypeSymbol, supertype : TypeSymbol) : bool { subtype.Equals(supertype); } public CreateTypeVar(): TypeVarSymbol { CreateTypeVar(null, null); } } |
Доступ к его экземпляру осуществляется через статическое поле Instance.
Метод IsSubtype этого класса отвечает, является ли один тип подтипом другого, и использует сравнения типов при унификации. Так как Mini C не поддерживает subtyping, данный метод реализуется через эквивалентность. В более серьезном языке стоит реализовать эту функцию более тщательно.
Данный класс является наследником класса TypeUnifier из стандартной библиотеки Nitra. В нем реализованы методы унификации типов, используемые для вывода типов:
public Unify(t1 : TypeSymbol, t2 : TypeSymbol) : bool public TryUnify(t1 : TypeSymbol, t2 : TypeSymbol) : bool |
Первая изменяет состояние переменных типа (причем даже в случае неудачи), а вторая нет.
В TypeUnifier также имеются функции унификации с учетом сабтайпинга:
public Require(t : TypeSymbol, baseTypeConstraint : TypeSymbol) : bool public TryRequire(t : TypeSymbol, baseTypeConstraint : TypeSymbol) : bool public Provide(t : TypeSymbol, derivedTypeConstraint : TypeSymbol) : bool public TryProvide(t : TypeSymbol, derivedTypeConstraint : TypeSymbol) : bool |
но они не имеют смысла для Mini C, в котором сабтайпинг не поддерживается.
При унификации свободной переменной с типом переменная принимает значение типа. Если же переменная уже была унифицирована с каким-то типом, то она будет унифицироваться только с эквивалентным типом. Если при унификации типы не совпадают, функция унификации возвращает ложь.
Выражение:
unless (MiniCTypeUnifier.Instance.TryUnify(Type, ExpectedType)) Error(context, $"Expected $(self.ExpectedType) but got $(self.Type)"); |
использует унификатор для проверки соответствия типов.
Так как все свойства переменных типов являются ЗС, данная проверка осуществляется только тогда, когда значение свойств Type и ExpectedType будут вычислены.
Для литералов типизация выглядит совсем просто:
| IntegerLiteral
{
Type = context.GetIntSymbol();
Value : int;
} |
Здесь вызов context.GetIntSymbol() возвращает ссылку на символ предопределенного типа, который помещается в ЗС Type. Значение ExpectedType не задается, а значит, для него используется значение по умолчанию, которым является свободная переменная типа. Свободная переменная унифицируется с любым типом, так что проверка:
MiniCTypeUnifier.Instance.TryUnify(Type, ExpectedType) |
проходит успешно и сообщение об ошибке для этого выражения не выдается.
Более интересной является типизация ссылки на переменную:
| VariableRef
{
out Ref : Ref[VarDeclaration.ScalarDeclarationSymbol] =
Reference.Ref.Resolve();
Reference.Scope = Scope;
Type = Ref.Symbol.Type;
Reference : Reference;
} |
после того как ЗС Scope получает значение и наступает стадия с индексом «1» (так как ЗС Scope объявлено как принадлежащее к стадии «1»), выполняется присвоение:
Reference.Scope = Scope; |
ЗС Reference имеет тип Reference, объявленный в стандартной библиотеке Nitra:
ast Reference { in Scope : Scope; out Ref : Ref[DeclarationSymbol] = Scope.Bind(this); } |
присвоение значения свойству Reference.Scope приводит к запуску процедуры связывания (binding):
out Ref : Ref[DeclarationSymbol] = Scope.Bind(this); |
в результате возвращается объект типа Ref[TSymbol], объявленного в стандартной библиотеке. Этот объект описывает результат связывания. Он может содержать одно из трех значений:
Процедура связывания не находит символы всех типов и не делает дополнительного анализа/фильтрации найденных символов.
Если при связывании получено значение Ref[DeclarationSymbol].Unresolved, будет выдано сообщение об ошибке.
В случае возврата одного из оставшихся значений все будет зависеть от последующих действий. Если с полученным объектом Ref[DeclarationSymbol] ничего не делать, то для значения Unresolved будет выдано сообщение об ошибке, а Some будет рассматриваться как удачное связывание.
Однако Ref[DeclarationSymbol], получаемый при связывании, редко когда нужен непосредственно, так как он может содержать ссылку на символ любого типа. Обычно в конкретном месте требуется ссылка на более конкретный символ. Для уточнения типа символа и для дополнительной фильтрации используется процедура разрешения имен (name resolution). В нашем примере это:
out Ref : Ref[VarDeclaration.ScalarDeclarationSymbol] =
Reference.Ref.Resolve[VarDeclaration.ScalarDeclarationSymbol](); |
Метод Resolve имеет сигнатуру:
Resolve[TConcreteSymbol](
algorithm : ResolutionAlgorithm[DeclarationSymbol, TConcreteSymbol] = null)
: Ref[TConcreteSymbol]
where TConcreteSymbol : DeclarationSymbol; |
Этот метод позволяет передать ссылку на алгоритм разрешения имен (в виде делегата). Если этот параметр не задан или равен null (как в данном случае), производится фильтрация по параметру типа. В нашем случае это – VarDeclaration.ScalarDeclarationSymbol.
Таким образом, в ЗС Ref оказывается новый объект типа Ref[VarDeclaration.ScalarDeclarationSymbol], в котором находится результат разрешения имен – символы (ноль или более) типа VarDeclaration.ScalarDeclarationSymbol, т.е. скалярная переменная.
Данный механизм универсален и позволяет производить разрешение имен в языках любой сложности. Кроме метода Resolve, в Ref[TSymbol] имеется метод
public ResolveMany[TConcreteSymbol]( algorithm : ResolveManyAlgorithm[TSymbol, TConcreteSymbol]) : Ref[TConcreteSymbol] where TConcreteSymbol : DeclarationSymbol |
который позволяет выбрать из списка неоднозначностей, сравнивая их между собой. Он подходит для разрешения имен перегруженных символов (например, методов в C#).
Ref[TSymbol] интересен тем, что его свойство Symbol является ЗС. Причем его значение становится вычисленным, только если в Ref[TSymbol] является Ref[TSymbol].Some. Таким образом, строка:
Type = Ref.Symbol.Type; |
вычислится только в случае, если в результате вызова Resolve() будет возвращен объект типа Ref[VarDeclaration.ScalarDeclarationSymbol].Some.
В противном случае эта строка вычислена не будет, и значение ЗС Type (в VariableRef) останется не вычисленным. Это приведет к тому, что не будут выполнены другие вычисления, зависящие от значения этого свойства. Такое поведение очень удобно, так как спасает от моря проверок и предотвращает выдачу «наведенных» сообщений об ошибках. Ведь если пользователь написал неверное имя переменной, ему достаточно получить сообщение о том, что переменной с таким именем нет. При этом он не захочет получать наведенные сообщения о том, что тип отсутствующей переменной не соответствует ожидаемому и т.п.
Итак давайте повторим еще раз ход вычислений при типизации VariableRef:
Типизация выражения типа ArrayRef:
| ArrayRef
{
out Ref : Ref[VarDeclaration.ArrayDeclarationSymbol] =
Reference.Ref.Resolve();
Reference.Scope = Scope;
Index.Scope = Scope;
Index.ExpectedType = context.GetIntSymbol();
Index.Used = true;
Type = Ref.Symbol.Type;
Reference : Reference;
Index : Expr;
} |
почти аналогична типизации VariableRef, за тем исключением, что в ArrayRef присутствует типизация индексатора массива:
Index.Scope = Scope;
Index.ExpectedType = context.GetIntSymbol();
Index.Used = true; |
Тут все довольно просто. Во вложенное выражение передается текущая область видимости и задается ожидаемый тип – int.
Так как значение свойства ExpectedType задается явно, значение по умолчанию игнорируется.
Если при дальнейшей типизации ExpectedType его тип не совпадет с ожидаемым, проверка:
unless (MiniCTypeUnifier.Instance.TryUnify(Type, ExpectedType)) Error(context, $"Expected $(self.ExpectedType) but got $(self.Type)"); |
выдаст сообщение об ошибке.
Типизация вызова функции:
| FunCall
{
out Ref : Ref[FunDeclarationSymbol] = Reference.Ref.Resolve();
Reference.Scope = Scope;
Arguments.Scope = Scope;
when (Arguments.Count != Ref.Symbol.Parameters.Count)
Reference.Error(context, $"Wrong number of arguments: expected "
"$(Ref.Symbol.Parameters.Count), but given $(Arguments.Count)");
Arguments.IndexIn = 0;
Arguments.Func = Ref.Symbol;
Arguments.Used = true;
Type = Ref.Symbol.ReturnType;
Arguments : Expr.Argument*;
Reference : Reference;
} |
начинается с копирования текущей области видимости в Reference.Scope:
Reference.Scope = Scope; |
Это приводит к связыванию имени функции, что, в свою очередь, запускает процедуру разрешения имени функции:
out Ref : Ref[FunDeclarationSymbol] = Reference.Ref.Resolve(); |
если все происходит успешно, в свойстве Ref окажется ссылка на имя функции или сообщение об ошибке (что имя не найдено или найдено более одного имени).
В случае успеха становится доступным значение свойства Ref.Symbol, а значит, может вычислиться проверка:
when (Arguments.Count != Ref.Symbol.Parameters.Count) Reference.Error(context, $"Wrong number of arguments: expected " "$(Ref.Symbol.Parameters.Count), but given $(Arguments.Count)"); |
В ней сравнивается количество аргументов, переданных в вызов, с количеством формальных параметров функции. Если они не совпадают, выдается сообщение об ошибке. Ни свойство Arguments, ни Arguments.Count не являются зависимыми (они являются структурными свойствами, значения которых получаются при отображении), так что эта проверка может быть осуществлена сразу после того как становится доступным значение Ref.Symbol.
Тип возвращаемого значения функции получается из символа функции:
Type = Ref.Symbol.ReturnType; |
он также вычисляется сразу после разрешения имени функции.
Для вычисления списка параметров, кроме свойства Scope, списку параметров задается еще два ЗС, IndexIn и Func:
Arguments.IndexIn = 0; Arguments.Func = Ref.Symbol; |
Чтобы понять, как они вычисляются и для чего нужны, рассмотрим эти присвоения вместе с выражением Argument:
| Argument
{
inout Index : int;
in Func : FunDeclarationSymbol;
Expr.Scope = Scope;
Expr.Used = true;
IndexOut = IndexIn + 1;
ExpectedType = AstUtils.GetParameterType(Func, IndexIn);
Type = Expr.Type;
Expr : Expr;
} |
Для вычисления порядкового номера (индекса) параметра было введено inout-свойство Index. В Nitra inout-ЗС – это как бы два отдельных ЗС (in и out), но их вычисления связаны. Если имеется список объектов, имеющих inout-свойство, то в списке это inout-свойство будет как бы протягиваться между всеми элементами списка.
В данном случае эта возможность используется для вычисления индекса каждого из аргументов.
Первому элементу списка задается (в FunCall) значение «0»:
Arguments.IndexIn = 0; |
при вычислении значения для каждого из элемента ему присваивается значение IndexOut предыдущего элемента или инициализирующее значение (для первого элемента списка). Прибавляя 1 к значению предыдущего индекса:
IndexOut = IndexIn + 1; |
каждый последующий элемент получает в IndexIn значение своего индекса.
Наверно это звучит слишком сложно. Чтобы упростить понимание, вот псевдо-код сеттера свойства IndexIn у списка аргументов:
set { _indexIn = value; mutable current = value; foreach (item in _items) { item.IndexIn = current; current = item.IndexOut; } _indexOut = value; _indexOut } |
Это именно псевдо-код, так как в нем не учитывается специфика зависимых свойств. В реальности все намного сложнее. Это концептуальная схема того, как вычисляются inout-свойства.
Таким образом, в свойстве IndexIn у параметра помещается индекс параметра.
Этот индекс используется для получения типа формального параметра, который используется как ожидаемый тип:
ExpectedType = AstUtils.GetParameterType(Func, IndexIn); |
GetParameterType – это простой метод, необходимый из-за ограничений подсистемы зависимых свойств:
// Hack: Nitra de+pendent property not support (yet) of indexer access. public GetParameterType(func : FunDeclarationSymbol, index : int) : TypeSymbol { def parameters = func.Parameters; if (index < parameters.Length && parameters[index].IsTypeEvaluated) parameters[index].Type else // Use TypeVar to prevent phantom type mismatch error messages MiniCTypeUnifier.Instance.CreateTypeVar() } |
Func – это ЗС в которое передается (в FunCall) символ, описывающий вызываемый метод:
Arguments.Func = Ref.Symbol; |
Итак, в свойство ExpectedType попадает тип формального параметра. Тип же аргумента берется из выражения:
Type = Expr.Type; |
Это приводит к выполнению общей для всех выражений проверки соответствия типа и ожидаемого типа.
Выражения типа ArraySize,ArrayAllocation и ScalarAssignment опустим, так как в них применяются уже описанные возможности, и перейдем к типизации операторов. Операторов в Mini C довольно много, но их можно разбить на группы. Чтобы описывать логику типизации не для каждого отдельного выражения, а для групп, было применено множественное наследование:
| Or : OrAndExpr {}
| And : OrAndExpr {}
| Equal : EqualExpr {}
| NotEqual : EqualExpr {}
| LessEqual : Comparison {}
| Less : Comparison {}
| GreaterEqual : Comparison {}
| Greater : Comparison {}
| Sum : Arithmetic {}
| Sub : Arithmetic {}
| Modulus : Arithmetic {}
| Multiply : Arithmetic {}
| Divide : Arithmetic {}
| Minus : NumericUnary {}
| LogicalNegate : BoolUnary {} |
Все приведенные выражения унаследованы от Expr, и помимо этого, от других типов AST:
Причем эти типы AST также имеют общие базовые типы AST. Это позволяет соблюсти одно из правил хорошего тона в программировании – «не повторяйся» (do not repeat yourself). В первую очередь все выражения делятся на унарные:
abstract ast Unary : Expr { Expr1.Scope = Scope; Expr1.Used = true; Type = Expr1.Type; Expr1 : Expr; } |
и бинарные:
abstract ast Binary : Expr { Expr1.Scope = Scope; Expr2.Scope = Scope; Expr1.Used = true; Expr2.Used = true; Expr1 : Expr; Expr2 : Expr; } |
их типизация тривиальна, и, в основном, сводится к передаче (вниз по дереву) областей видимости. Уже от них наследуются более конкретные (но все равно абстрактные) типы AST. Например, NumericUnary:
abstract ast NumericUnary : Unary { unless (MiniCTypeUnifier.Instance.TryUnify(Expr1.Type, ontext.GetIntSymbol()) || MiniCTypeUnifier.Instance.TryUnify(Expr1.Type, ontext.GetFloatSymbol()) ) Expr1.Error(context, $"Expected int or float, but found $(self.Expr1.Type)"); } |
Это наследник для унарных операторов, работающих с числами (в Mini C таких, правда, одна штука). Так как основная логика типизации для унарных выражений описана в Unary, в NumericUnary остается только проверить, что операнд имеет числовой тип (в Mini C к таковым относятся только int и float.
Обратите внимание на то, как множественное наследование реализации элегантно решает задачу декомпозиции.
Похожая проверка делается и в BoolUnary, с той лишь разницей, что тут операнд должен быть типа bool.
OrAndExpr, EqualExpr, Comparison и Arithmetic имеют общее свойство – они имеют два операнда, типы которых должны быть эквивалентны. Это выражается через введение общего (для них) базового типа AST :
abstract ast SameTypesExpr : Binary { unless (MiniCTypeUnifier.Instance.TryUnify(Expr1.Type, Expr2.Type)) Expr2.Error(context, $"$(self.Expr2.Type) is not compatible with $(self.Expr1.Type)."); } |
В нем производится сравнение типов аргументов, и если они не идентичны, выдается сообщение об ошибке.
OrAndExpr реализовано следующим образом:
abstract ast OrAndExpr : SameTypesExpr { Type = context.GetBoolSymbol(); unless (MiniCTypeUnifier.Instance.TryUnify(Expr1.Type, context.GetBoolSymbol()) ) Expr1.Error(context, $"Expected boolean expression but found $(self.Expr1.Type)."); } |
Так как OrAndExpr является наследником SameTypesExpr, проверка на идентичность типов аргументов уже выполняется. Остается только задать тип всего выражения – bool, и проверить, что тип одного из операндов (в данном случае первого) тоже является bool.
С EqualExpr все еще проще:
abstract ast EqualExpr : SameTypesExpr { Type = context.GetBoolSymbol(); } |
Тут только задается тип выражения (опять же bool).
У Comparison и Arithmetic также есть общее свойство (как и NumericUnary) – их аргументы должны быть числового типа. Опять же, так как они являются наследниками SameTypesExpr, можно проверять только один из операндов:
abstract ast NumericBinary : SameTypesExpr { unless (MiniCTypeUnifier.Instance.TryUnify(Expr1.Type, context.GetIntSymbol()) || MiniCTypeUnifier.Instance.TryUnify(Expr1.Type, context.GetFloatSymbol()) ) Expr1.Error(context, $"Expected int or float, but found $(self.Expr1.Type)"); } |
Реализация Comparison и Arithmetic становится совсем примитивной и заключается в вычислении типа выражения:
abstract ast Comparison : NumericBinary { Type = context.GetBoolSymbol(); } abstract ast Arithmetic : NumericBinary { Type = Expr1.Type; } |
Как видите, множественное наследование реализации очень мощный инструмент Nitra. Он позволяет существенно упростить и сократить код. Причем, в отличие от ЯП общего назначения, поддерживающих множественное наследование, это не создает дополнительных проблем. Зависимые свойства хорошо ложатся на концепцию множественного наследования.
Проблема бриллиантового наследования устраняется за счет того, что все наследование является виртуальным (в терминах C++).
В случае определения одного и того же свойства в двух базовых AST, Nitra требует, чтобы это свойство было переопределено в наследнике.
В Nitra поддержка проектов пока что выполняется по временной схеме. В дальнейшем для поддержки проектов в Nitra будет добавлен специальный DSL.
Пока что для поддержки проектов нужно реализовать в AST, являющемся верхом иерархии (файла), интерфейс IProjectSupport:
public interface IProjectSupport { RefreshReferences(cancellationToken : CancellationToken, project : Project) : object; RefreshProject(cancellationToken : CancellationToken, files : ImmutableArray[FileEvalPropertiesData], data : object) : void; } |
Метод RefreshReferences вызывается при открытии проекта или при изменении ссылок на библиотеки в проекте.
Метод RefreshProject вызывается при любом изменении проекта, после того как измененные файлы будут разобраны парсером и для них будет получен новый AST. В задачи этого метода входит вычисление зависимых свойств на AST.
Nitra генерирует классы для не абстрактных AST. Эти классы помечаются как partial. Это позволяет добавить к этим классам необходимую функциональность.
Для того чтобы Mini C мог поддерживать проекты, в корневом AST, CompilationUnit, нужно реализовать интерфейс IProjectSupport. Для этого в проект был добавлен файл CompilationUnit.n, содержащий класс CompilationUnit:
public partial class CompilationUnit : AstBase, IProjectSupport { static NoLocation : Location = Location(SourceSnapshot.Default.File, NSpan(0)); static NoFile : ProjectSystem.File = SourceSnapshot.Default.File; static NoSpan : NSpan = NSpan(0); public RefreshReferences(cancellationToken : CancellationToken, project : Project) : object { def root = RootSymbol() <- { FullName = "<root>"; Kind = "root"; }; root.MemberTable = TableScope("<root>", root); root.Scope = root.MemberTable; def defineSymbol[Type](name : string, putToRootScope : bool = true) : Type where Type: DeclarationSymbol { def name = Name(NoLocation, name); def symbol = if (putToRootScope) ExternalDeclaration.[Type](name).DefineSymbol(root.MemberTable) else ExternalDeclaration.[Type](name).DefineSymbol(); symbol } def voidSymbol = defineSymbol.[VoidSymbol]("void"); def intSymbol = defineSymbol.[IntSymbol]("int"); def floatSymbol = defineSymbol.[FloatSymbol]("float"); def boolSymbol = defineSymbol.[BoolSymbol]("bool"); def context = MiniCDependentPropertyEvalContext(voidSymbol, intSymbol, floatSymbol, boolSymbol); def definePrintSymbol(name : string, argType: TypeSymbol) { def symbol = defineSymbol.[FunDeclarationSymbol](name); symbol.ReturnType = voidSymbol; def printParam = defineSymbol.[VarDeclaration.ScalarDeclarationSymbol]( "value", false); printParam.Type = argType; symbol.Parameters = ImmutableArray.Create(printParam); printParam.EvalProperties(context); symbol.EvalProperties(context) } definePrintSymbol("iprint", intSymbol); definePrintSymbol("bprint", boolSymbol); definePrintSymbol("fprint", floatSymbol); root.AddDeclaration(ExternalDeclaration.[RootSymbol]( Name(NoLocation, "<root>"))); voidSymbol.EvalProperties(context); intSymbol.EvalProperties(context); floatSymbol.EvalProperties(context); boolSymbol.EvalProperties(context); root.EvalProperties(context); project.Data = (context, root); project.Data } public RefreshProject(cancellationToken : CancellationToken, files : ImmutableArray[FileEvalPropertiesData], data : object) : void { def (context, root) = data :> MiniCDependentPropertyEvalContext * RootSymbol; context.CancellationToken = cancellationToken; root.MemberTable.Undefine(_.IsParsed); def evalHost = MiniCProjectEvalPropertiesHost(files, root); evalHost.EvalProperties(context, "Symbol hierarchy", 0); evalHost.EvalProperties(context, "Scopes", 1); } } |
В RefreshReferences передается cancellationToken, с помощью которого можно проверить, нужно ли продолжать загрузку, и project, через который можно получить доступ к информации о проекте (например, к списку библиотек, на который ссылается проект).
В начале RefreshReferences происходит инициализация корневого символа AST:
def root = RootSymbol() <- { FullName = "<root>"; Kind = "root"; }; |
Это искусственный символ. В его ЗС MemberTable располагается таблица имен, хранящая глобальные символы (глобальные переменные и функции):
root.MemberTable = TableScope("<root>", root); |
Эта таблица имен делается текущей областью видимости для корневого символа:
root.Scope = root.MemberTable; |
Локальная функция defineSymbol используется для добавления предопределенных символов:
def defineSymbol[Type](name : string, putToRootScope : bool = true) : Type where Type: DeclarationSymbol { def name = Name(NoLocation, name); def symbol = if (putToRootScope) ExternalDeclaration.[Type](name).DefineSymbol(root.MemberTable) else ExternalDeclaration.[Type](name).DefineSymbol(); symbol } |
Символы в Nitra должны иметь декларации, но так как предопределенные символы деклараций не имеют, для них используется тип ExternalDeclaration[TSymbol], предназначенный для формирования деклараций импортируемых символов (символов, загружаемых из внешних библиотек).
С помощью этой функции добавляются символы для предопределенных типов:
def voidSymbol = defineSymbol.[VoidSymbol]("void"); def intSymbol = defineSymbol.[IntSymbol]("int"); def floatSymbol = defineSymbol.[FloatSymbol]("float"); def boolSymbol = defineSymbol.[BoolSymbol]("bool"); |
Далее создается контекст вычисления зависимых свойств (MiniCDependentPropertyEvalContext), которому передаются созданные выше символы:
def context = MiniCDependentPropertyEvalContext(voidSymbol,
intSymbol, floatSymbol, boolSymbol); |
Этот класс уже приводился выше. Данный класс является наследником класса DependentPropertyEvalContext из стандартной библиотеки Nitra. Он хранит служебную информацию, к которой требуется доступ подсистеме вычисления зависимых свойств. MiniCDependentPropertyEvalContext же добавляет к нему поля, хранящие предопределенные типы.
Далее описывается функция definePrintSymbol, предназначенная для добавления предопределенных функций:
def definePrintSymbol(name : string, argType: TypeSymbol) { def symbol = defineSymbol.[FunDeclarationSymbol](name); symbol.ReturnType = voidSymbol; def printParam = defineSymbol.[VarDeclaration.ScalarDeclarationSymbol]( "value", false); printParam.Type = argType; symbol.Parameters = ImmutableArray.Create(printParam); printParam.EvalProperties(context); symbol.EvalProperties(context) } |
Эта функция используется для добавления предопределенных функций печати «iprint», «bprint» и «fprint», выводящих на консоль целочисленное, булево и вещественное значение:
definePrintSymbol("iprint", intSymbol); definePrintSymbol("bprint", boolSymbol); definePrintSymbol("fprint", floatSymbol); |
Далее корневому символу добавляется декларация:
root.AddDeclaration(ExternalDeclaration.[RootSymbol](
Name(NoLocation, "<root>"))); |
В Nitra символы обязаны иметь хотя бы одну декларацию.
Далее следует код, выполняющий вычисления зависимых свойств символов:
voidSymbol.EvalProperties(context); intSymbol.EvalProperties(context); floatSymbol.EvalProperties(context); boolSymbol.EvalProperties(context); root.EvalProperties(context); |
похожие вызовы присутствовали и в definePrintSymbol. Они нужны, так как символы являются объектами, содержащими зависимые свойства (зависимого объекта, т.е. объекта, имеющего ЗС). Так как символы используются из кода на языке программирования общего назначения (ничего не знающего о ЗС), подсистема вычисления ЗС не знает о том, что нужно вычислять ЗС. Вызов метода EvalProperties у зависимого объекта приводит к попытке вычисления его ЗС. При этом вычисляются только те ЗС, зависимости которых доступны (уже вычислены). Если не вызвать EvalProperties, то часть ЗС объекта может остаться не вычисленными.
Внимательный читатель мог обратить внимание на то, что метод EvalProperties не вызывался для символов предопределенных типов. Этот вызов делает конструктор контекста (MiniCDependentPropertyEvalContext), которому передаются символы предопределенных типов.
Предпоследним действием в методе RefreshReferences является сохранение кортежа из контекста и корневого символа в поле Data проекта (это поле имеет тип object и предназначено для хранения специфичной для конкретного типа проектов информации).
project.Data = (context, root); |
Это же значение возвращается из метода RefreshReferences:
project.Data |
Метод RefreshProject производит вычисление ЗС:
public RefreshProject(cancellationToken : CancellationToken, files : ImmutableArray[FileEvalPropertiesData], data : object) : void |
В параметр data ему передаются специфичные для проекта данные. Это те самые данные, которые возвратил метод RefreshReferences.
Кроме того, он получает cancellationToken, с помощью которого можно узнать, нужно ли продолжать вычисления ЗС или операция уже отменена, а также информацию о файлах проекта.
FileEvalPropertiesData – это класс:
[Record] public class FileEvalPropertiesData { public FullName : string; public Title : string; public FileId : int; public FileVersion : int; public Ast : IAst; public Statistics : StatisticsTask.Container; public HasCompilerMessage : bool { get; } public GetCompilerMessage() : CompilerMessageList; } |
содержащий информацию о файле проекта и его AST. Кроме того, он содержит список сообщений об ошибках, возникших при вычислении зависимых свойств, и статистику.
Первая строка метода RefreshProject распаковывает информацию о контексте вычисления ЗС и корневом символе:
def (context, root) = data :> MiniCDependentPropertyEvalContext * RootSymbol; |
Далее в контекст помещается текущий токен отмены:
context.CancellationToken = cancellationToken; |
это позволит подсистеме вычисления ЗС прекратить вычисления, если данный токен будет сигнализировать об отмене операции.
После этого из глобальной таблицы имен удаляются символы, полученные при парсинге:
root.MemberTable.Undefine(_.IsParsed); |
Проект может работать под управлением IDE или тестовой утилиты. В этом случае RefreshProject может вызываться многократно (после каждого изменения файла). Так как в Nitra используется реализация таблицы имен на базе хэш-таблицы (а не неизменяемых структур вроде дерева), таблицу имен необходимо очистить от символов, полученных в процессе вычисления ЗС. Предопределенные же символы (и символы загруженные из библиотек, в более серьезных языках) удалять не надо. Это существенно ускоряет типизацию в случае наличия множества символов, загружаемых из внешних библиотек.
Далее производится расчет зависимых свойств:
def evalHost = MiniCProjectEvalPropertiesHost(files, root);
evalHost.EvalProperties(context, "Symbol hierarchy", 0);
evalHost.EvalProperties(context, "Scopes", 1); |
Для вычисления ЗС используется объект класса MiniCProjectEvalPropertiesHost:
public class MiniCProjectEvalPropertiesHost : ProjectEvalPropertiesHost { _root : RootSymbol; public this(files : ImmutableArray[FileEvalPropertiesData], root : RootSymbol) { base(files, ImmutableArray.Create(root)); _root = root; } protected override BeforeStage(context : DependentPropertyEvalContext, _passName : string) : void { match (context.Stage) { | 0 => foreach (file in _files) when (file.Ast is CompilationUnit as cu) cu.ContainingTable = _root.MemberTable; | _ => () } } } |
Этот класс наследуется от ProjectEvalPropertiesHost, который объявлен в стандартной библиотеке. Он берет на себя все, что связано с вычислением ЗС.
У разных языков может быть разное количество стадий типизации (одна или более). В Mini C стадий две – нулевая и первая. Для вычисления этих стадий нужно вызвать (у evalHost) метод EvalProperties:
evalHost.EvalProperties(context, "Symbol hierarchy", 0); evalHost.EvalProperties(context, "Scopes", 1); |
| СОВЕТ Закомментировав вторую строку, можно получить состояние типизации на начало стадии «1». Это может быть полезно при отладке. |
В классе MiniCProjectEvalPropertiesHost переопределяется метод BeforeStage. В нем можно произвести инициализацию зависимых свойств корневых AST для каждого из файлов и для каждой из стадий.
Для Mini C нужно проинициализировать ЗС ContainingTable у корневого AST (CompilationUnit) таблицей глобальных символов. Это делают следующие строки:
foreach (file in _files) when (file.Ast is CompilationUnit as cu) cu.ContainingTable = _root.MemberTable; |
| ПРИМЕЧАНИЕ В будущем в Nitra будет реализован DSL для поддержки проектов, и весь код, связанный с IProjectSupport, уйдет туда, а сам код станет декларативным и прозрачным. Не нужно будет вручную создавать символы и вызвать их метод EvalProperties. |
Генерация исполняемых модулей вынесена в проект MiniC.Compiler\MiniC.Compiler.nproj. Он использует Nitra-Mini-C.dll для парсинга исходных файлов Mini C, типизации и выявления ошибок. Генерация исполняемого модуля производится только в случае ошибок типизации. Если при разработке на предыдущих стадиях не было сделано ошибок, то аннотированный AST не может содержать ошибок, и по нему довольно просто сгенерировать исполнимый файл.
MiniC.Compiler (далее – компилятор) генерирует исполнимые файлы в формате .Net. Для генерации сборок (и содержащихся в них MSIL и метаданных) используется библиотека Microsoft CCI.Metadata. Она подключена к проекту через NuGet-пакет (CustomMetadataFix.Microsoft.Cci.Metadata). Эту библиотеку можно также собрать из исходников.
В задачи компилятора входит:
За считывание и разбор метаданных отвечает класс Config (см. Config.n). В результате данные из командной строки попадают в его поля:
class Config { public FileName : string { get; private set; } public OutputPath : string { get; private set; } public Success : bool { get; } |
Этот класс используется в функции Main компилятора (Main.n), которая выглядит следующим образом:
Main() : void { def config = Config(); when (config.Success) { def solution = GenerateSolution(config); mutable hasError = false; RefreshSolution(solution); foreach (project in solution.Projects) foreach (file in project.Files) foreach (msg in file.GetCompilerMessages()) { hasError = true; WriteLine(msg); } when (hasError) return; foreach (project in solution.Projects) DotNetBackend.GenerateAssembly(project, config.OutputPath); } } |
Функция GenerateSolution загружает FsSolution (решение Nitra читающее исходники из файловой системы):
GenerateSolution(cfg : Config) : FsSolution[IAst]
{
def solution = FsSolution();
_ = FsProject(solution, Path.GetDirectoryName(cfg.FileName),
[FsFile(cfg.FileName, MiniC.Instance)], []);
solution
} |
FsSolution, FsProject и FsFile – это реализации (наследники) классов Solution, Project и File соответственно. Данные классы описывают структуру решения и проектов в Nitra. Терминология соответствует и используемой в VS.
Компилятор Mini C поддерживает только однофайловые проекты (это несложно изменить). Путь к единственному файлу доступен через свойство cfg.FileName.
FsFile принимает путь к файлу и ссылку на «язык» (описание метаданных языка).
MiniC.Instance – это ссылка на объект, описывающий метаданные языка Mini C. Он генерируется по описанию из Nitra-Mini-C/MiniC-Language.nitra.
Вся обработка решения (парсинг и типизация) производится в функции RefreshSolution:
public RefreshSolution(solution : Solution) : void { foreach (project in solution.Projects) { def projectSupport = project.GetProjectSupport(); def data = projectSupport.RefreshReferences( CancellationToken.None, project); def files = project.Files .Select(x => x.GetEvalPropertiesData()) .ToImmutableArray(); projectSupport.RefreshProject(CancellationToken.None, files, data); } } |
Эта функция пробегает по проектам решения (которых в Mini C всегда один), получает ссылку на IProjectSupport (projectSupport) и вызывает его методы – сначала RefreshReferences, а затем RefreshProject.
В результате производится парсинг исходных файлов, затем генерируется AST, а затем выполняется расчет зависимых свойств.
Далее управление возвращается в функцию Main, где сначала производится попытка вывести сообщения об ошибках на консоль:
foreach (project in solution.Projects) foreach (file in project.Files) foreach (msg in file.GetCompilerMessages()) { hasError = true; WriteLine(msg); } |
Если ошибок нет, для проекта вызывается функция DotNetBackend.GenerateAssembly:
when (hasError) return; foreach (project in solution.Projects) DotNetBackend.GenerateAssembly(project, config.OutputPath); |
DotNetBackend – это класс, в котором реализована вся логика генерации исполняемых модулей для .NET. В демонстрационных целях, и вследствие того, что Mini C очень простой язык, не требующий импорта внешних символов, весь бэкенд реализован в одном классе и не использует бэкенда для .Net-языков, имеющегося в стандартной библиотеке Nitra.
Статический метод GenerateAssembly:
public static GenerateAssembly(project : Project, outputPath : string) : void { def (context, rootSymbol) = project.Data :> MiniCDependentPropertyEvalContext * RootSymbol; using (backend = DotNetBackend(project)) { foreach (symbols in rootSymbol.MemberTable.Symbols) foreach (topDeclSymbol in symbols) { | funcDecl is FunDeclarationSymbol => backend.Add(funcDecl) | varDecl is VarDeclarationSymbol => backend.Add(varDecl) | s when ReferenceEquals(s, context.Void) || ReferenceEquals(s, context.Bool) || ReferenceEquals(s, context.Int) || ReferenceEquals(s, context.Float) => () | _ => assert(false, $"Unknown top declaration symbol type $topDeclSymbol"); } backend.GenerateAssembly(outputPath); } } |
Он распаковывает контекст и корневой символ из свойства project.Data, создает экземпляр DotNetBackend, перебирает все глобальные символы и вызывает для каждого из них метод Add. Предопределенные символы при этом игнорируются.
В конце вызывается метод GenerateAssembly, который записывает сборку в файл.
Метод Add имеет две перегрузки, одну для VarDeclarationSymbol и одну для FunDeclarationSymbol.
Первая из них совсем простая:
public Add(var : VarDeclarationSymbol) : void { def field = FieldDefinition() <- { ContainingTypeDefinition = _mainClass; Name = _nameTable.GetNameFor(var.Name); Type = GetVariableType(var); IsStatic = true; Visibility = TypeMemberVisibility.Public; IsReadOnly = false; InternFactory = _host.InternFactory; }; _mainClass.Fields.Add(field); _globalVarMap[var] = field } |
По VarDeclarationSymbol она формирует CCI-описание статического поля. Это описание добавляется в главный класс и в хэш-таблицу _globalVarMap. Эта хэш-таблица используется для отображения символов переменных на CCI-описания соответствующих полей.
| ПРИМЕЧАНИЕ В Nemerle при вызове конструктора не используется оператор «new», а вместо инициализатора используется оператор «->». Этот оператор похож на инициализатор, но позволяет инициализировать не только создаваемый объект, но и имеющийся. |
Метод, добавляющий функции, немного посложнее своего аналога для глобальных переменных:
public Add(func : FunDeclarationSymbol) : void { if (func.HasParsedDeclarations) { def name = func.Name; def method = MethodDefinition() <- { ContainingTypeDefinition = _mainClass; InternFactory = _host.InternFactory; IsCil = true; IsStatic = true; Name = _nameTable.GetNameFor(name); Type = GetType(func.ReturnType); Parameters = List(); Visibility = TypeMemberVisibility.Public; InternFactory = _host.InternFactory; }; _mainClass.Methods.Add(method); _functionMap[func] = method; method.Body = EmitFunctionBody(func, method); when (name.Equals("main", StringComparison.InvariantCultureIgnoreCase)) _assembly.EntryPoint = method; } else { def writeLineFun(returnType) { def systemConsole = UnitHelper.FindType(_nameTable, _coreAssembly, "System.Console"); TypeHelper.GetMethod(systemConsole, _nameTable.GetNameFor("WriteLine"), returnType); } _functionMap[func] = writeLineFun(GetType(func.Parameters[0].Type)); } } |
Этот метод формирует CCI-описание статического метода, соответствующего символу, полученному через параметр «func». Полученное описание добавляется в список методов глобального объекта и добавляется в _functionMap (для дальнейшего поиска этого описания по символу).
Далее вызывается метод генерации тела функции:
method.Body = EmitFunctionBody(func, method); |
Ели метод имеет имя «main», он помечается как точка входа сборки:
when (name.Equals("main", StringComparison.InvariantCultureIgnoreCase)) _assembly.EntryPoint = method; |
Если символ получен не из исходников (func.HasParsedDeclarations == false), это символы для предопределенных функций «iprint», «bprint» и «fprint». Они заменяются на вызов System.Console.WriteLine:
def writeLineFun(returnType) { def systemConsole = UnitHelper.FindType(_nameTable, _coreAssembly, "System.Console"); TypeHelper.GetMethod(systemConsole, _nameTable.GetNameFor("WriteLine"), returnType); } _functionMap[func] = writeLineFun(GetType(func.Parameters[0].Type)); |
| ПРИМЕЧАНИЕ UnitHelper и TypeHelper – это вспомогательные типы (хелперы) CCI, используемые для упрощения работы с типами. |
Функция GetType, использованная в методе Add, преобразует символы Mini C (описывающие типы) в ссылку на тип в формате CCI:
public GetType(typeSymbol : TypeSymbol) : ITypeReference { | IntSymbol => _host.PlatformType.SystemInt32 | FloatSymbol => _host.PlatformType.SystemFloat64 | BoolSymbol => _host.PlatformType.SystemBoolean | VoidSymbol => _host.PlatformType.SystemVoid | _ => assert(false, $"Unhandled $typeSymbol") } |
GetArrayType получает символ, описывающий тип элемента массива, и формирует CCI-ссылку на тип массива:
GetArrayType(typeSymbol : TypeSymbol) : IArrayTypeReference
{
VectorTypeReference() <-
{
TypeCode = PrimitiveTypeCode.NotPrimitive;
PlatformType = _host.PlatformType;
ElementType = GetType(typeSymbol);
InternFactory = _host.InternFactory;
}
} |
Функция GetVariableType использует две описанные выше функции для формирования CCI-ссылки на тип переменной:
public GetVariableType(var : VarDeclarationSymbol) : ITypeReference { | VarDeclaration.ScalarDeclarationSymbol => GetType(var.Type) | VarDeclaration.ArrayDeclarationSymbol => GetArrayType(var.Type) | _ => assert(false) } |
Метод EmitFunctionBody:
EmitFunctionBody(func : FunDeclarationSymbol, method : MethodDefinition)
: IMethodBody
{
def compoundStatement = func.Declarations.First().Body;
def isVoid = ReferenceEquals(method.Type,
_host.PlatformType.SystemVoid);
def methodContext = MethodContext(this, _nameTable, method, isVoid,
ILGenerator(_host, method));
foreach (parameter in func.Parameters)
methodContext.AddParameter(parameter);
EmitCompoundStatement(methodContext, compoundStatement);
methodContext.EmitReturn();
ILGeneratorMethodBody(methodContext.IlGenerator, true, 10, method,
methodContext.LocalVars, []);
} |
формирует контекст метода (MethodContext), добавляет в него описания параметров, вызывает процедуру генерации кода (EmitCompoundStatement), вызывает метод генерации return и создает экземпляр ILGeneratorMethodBody – это обертка над телом метода в CCI. Ей передаются ILGenerator, CCI-определение метода и список локальных переменных.
MethodContext – это вспомогательный класс, инкапсулирующий работу с описанием метода в формате CCI. Он позволяет добавить параметры, локальные переменные, и хранит некоторую другую служебную информацию связанную с методом. Этот класс автоматически создает объект CCI для соответствующих символов Mini C.
EmitCompoundStatement – генерирует код для области блока Mini C:
EmitCompoundStatement(methodContext : MethodContext,
compoundStatement : CompoundStatement) : void
{
def gen = methodContext.IlGenerator;
gen.BeginScope();
foreach (variable in compoundStatement.LocalVariables)
methodContext.AddLocalVar(variable.Symbol);
foreach (statement in compoundStatement.Statements)
EmitStatement(methodContext, statement);
gen.EndScope();
} |
В переменную gen помещается ссылка на IlGenerator, с помощью которого и производится генерация MSIL.
Так как блок в Mini C определяет область видимости, производится вызов:
gen.BeginScope(); |
это информирует CCI, что открыта новая область видимости.
Далее в контекст метода добавляются локальные переменные. При этом в методе AddLocalVar создаются CCI-описания локальных переменных, которые ассоциируются с символами этих переменных:
public AddLocalVar(varDeclSymbol : VarDeclarationSymbol) : void { def cciLocalVar = CreateLocalVar(varDeclSymbol.Name, _backend.GetVariableType(varDeclSymbol)); _localVarMap[varDeclSymbol] = cciLocalVar; } |
Далее происходит генерация кода вложенных стейтментов. Для каждого стейтмента вызывается метод EmitStatement:
EmitStatement(methodContext : MethodContext, statement : Statement): void { def gen = methodContext.IlGenerator; match (statement) { | Expression as s => EmitExpression(methodContext, s.Body); | ReturnVoid => gen.Emit(Op.Ret); | Return as s => EmitExpression(methodContext, s.Value); when (methodContext.Return is Some(ret)) { gen.Emit(Op.Stloc, ret.Var); gen.Emit(Op.Br, ret.Label); } | Compound as s => EmitCompoundStatement(methodContext, s.Nested); | If as s => def exitLabel = ILGeneratorLabel(); EmitExpression(methodContext, s.Condition); gen.Emit(Op.Brfalse, exitLabel); // if true EmitStatement(methodContext, s.Body); gen.MarkLabel(exitLabel); | IfElse as s => def falseBranchLabel = ILGeneratorLabel(); def exitLabel = ILGeneratorLabel(); EmitExpression(methodContext, s.Condition); gen.Emit(Op.Brfalse, falseBranchLabel); // true branch EmitStatement(methodContext, s.TrueBranch); gen.Emit(Op.Br, exitLabel); // false branch gen.MarkLabel(falseBranchLabel); EmitStatement(methodContext, s.FalseBranch); gen.MarkLabel(exitLabel); | While as w => def bodyLabel = ILGeneratorLabel(); def conditionLabel = ILGeneratorLabel(); gen.Emit(Op.Br, conditionLabel); // loop body gen.MarkLabel(bodyLabel); EmitStatement(methodContext, w.Body); // loop condition gen.MarkLabel(conditionLabel); EmitExpression(methodContext, w.Condition); gen.Emit(Op.Brtrue, bodyLabel); when (methodContext.TryFindWhileExitLabel(w) is Some(whileExitLabel)) gen.MarkLabel(whileExitLabel); | Break (Loop = Some(loop)) => def whileExitLabel = methodContext.GetOrNewWhileExitLabel(loop); gen.Emit(Op.Br, whileExitLabel); | _ => WriteLine($"Unhandlend statement! $statement"); } } |
Здесь для каждого подтипа стейтмента генерируется свой набор MSIL-инструкций. Код генерации очевиден и единообразен, так что давайте разберем только один подтип Statement.While.
Стейтмент передается оператору сопоставления с образцом:
match (statement)
{ |
если runtime-тип statement является Statement.While, управление передается к строке:
| While as w => |
Конструкция «as w» вводит локальную переменную «w», в которую помещается значение сопоставленного значения. Таким образом, через «w» можно получить доступ к полям AST цикла.
Так как в MSIL нет структурных конструкций, все ветвления необходимо выразить через конструкции лейблов и условных переходов.
Для начала рассмотрим схематическое представление MSIL для цикла:
br conditionLabel; // безусловный переход bodyLabel: $Body$ // инструкции тела цикла conditionLabel: $Condition$ // помещает на стек результат проверки brtrue bodyLabel; // перейти несли на стеке не «0» |
Как видите, для реализации цикла потребовалось две метки (conditionLabel и bodyLabel) и две инструкции перехода – безусловная br и условная brtrue.
Генерация MSIL с помощью CCI эмулирует расстановку команд MSIL посредством API-вызовов.
Для работы с метками их нужно создать в виде объектов:
def bodyLabel = ILGeneratorLabel(); def conditionLabel = ILGeneratorLabel(); |
Само по себе это не приводит ни к какой генерации кода, но это позволяет ссылаться на эти метки в дальнейшем. Далее идет генерация инструкции безусловного перехода «br»:
gen.Emit(Op.Br, conditionLabel); |
В качестве параметра ей передается метка (куда надо перейти). Обратите внимание, что сама метка к этому времени еще не сгенерирована.
Далее генерируется мета bodyLabel:
// loop body
gen.MarkLabel(bodyLabel); |
Метод MarkLabel помечает место, в котором должна размещаться метка.
Далее генерируется код тела метода:
EmitStatement(methodContext, w.Body); |
Затем генерируется метка, идущая перед кодом проверки условия цикла:
gen.MarkLabel(conditionLabel); |
А затем сами инструкции проверки условия цикла:
EmitExpression(methodContext, w.Condition); |
Теперь генерируется условный переход по метке начала цикла (bodyLabel):
gen.Emit(Op.Brtrue, bodyLabel); |
Завершающий штрих – если в цикле есть инструкция break, генерируется метка перехода для него:
when (methodContext.TryFindWhileExitLabel(w) is Some(whileExitLabel)) gen.MarkLabel(whileExitLabel); |
Все остальные стейтменты устроены аналогичны, так что мы их рассматривать не будем.
Функция генерации кода для выражений во многом похожа на функцию генерации кода стейтментов. Так что я не будут ее специальным образом комментировать. Если вы не знакомы с генерацией MSIL, можете брать в буфер обмена коды инструкций и смотреть их описание в MSDN.
EmitExpression(methodContext : MethodContext, expr : Expr) : void { def gen = methodContext.IlGenerator; match (expr) { | IntegerLiteral as e => gen.Emit(Op.Ldc_I4, e.Value.Value) | FloatLiteral as e => gen.Emit(Op.Ldc_R8, e.Value.Value) | TrueLiteral => gen.Emit(Op.Ldc_I4_1) | FalseLiteral => gen.Emit(Op.Ldc_I4_0) | VariableRef as e => LoadVar(gen, methodContext, e.Ref.Symbol) | ScalarAssignment as assignment => EmitExpression(methodContext, assignment.Value); SetVarValue(gen, methodContext, assignment.Ref.Symbol); | FunCall as call => foreach (arg in call.Arguments) EmitExpression(methodContext, arg); gen.Emit(Op.Call, GetFunction(call.Ref.Symbol)) | Argument as arg => EmitExpression(methodContext, arg.Expr) | Binary as bin => EmitExpression(methodContext, bin.Expr1); EmitExpression(methodContext, bin.Expr2); def opCode = match (bin) { | Or => Op.Or | And => Op.And | Equal => Op.Ceq | NotEqual => gen.Emit(Op.Ceq); gen.Emit(Op.Ldc_I4_0); Op.Ceq; | LessEqual => gen.Emit(Op.Cgt); gen.Emit(Op.Ldc_I4_0); Op.Ceq | Less => Op.Clt | GreaterEqual => gen.Emit(Op.Clt); gen.Emit(Op.Ldc_I4_0); Op.Ceq | Greater => Op.Cgt | Sum => Op.Add | Sub => Op.Sub | Modulus => Op.Rem | Multiply => Op.Mul | Divide => Op.Div | _ => assert(false, $"Unhandled binary expression $bin") }; gen.Emit(opCode); | Unary as unary => EmitExpression(methodContext, unary.Expr1); match (unary) { | Minus => gen.Emit(Op.Neg) | LogicalNegate => gen.Emit(Op.Ldc_I4_0); gen.Emit(Op.Ceq) | _ => assert(false, $"Unhandled unary expression $unary") } | ArraySize as e => LoadVar(gen, methodContext, e.Ref.Symbol); gen.Emit(Op.Ldlen); | ArrayAllocation as a => EmitExpression(methodContext, a.Size); gen.Emit(Op.Newarr, GetArrayType(a.Type)); | ArrayAssignment as a => LoadVar(gen, methodContext, a.Ref.Symbol); EmitExpression(methodContext, a.Index); EmitExpression(methodContext, a.Value); gen.Emit(Op.Stelem, GetType(a.Ref.Symbol.Type)); | ArrayRef as a => LoadVar(gen, methodContext, a.Ref.Symbol); EmitExpression(methodContext, a.Index); gen.Emit(Op.Ldelem, GetType(a.Type)); | _ => WriteLine($"Unhandled expression! $expr") } // we must pop expression result out from stack if it's not used unless (expr.Used || MiniCTypeUnifier.Instance.TryUnify(expr.Type, _context.Void)) gen.Emit(Op.Pop); } |
Как видите, генерация MSIL довольно рутинный процесс. Единственное, что в нем нужно знать – это сам MSIL :).
Символы Nitra позволяют подготовить исчерпывающие данные, необходимые для генерации кода. Их обход не представляет труда, так как символы превращаются в обычные .Net-классы.
Код генерации MSIL избавлен от проверок, так как все проверки осуществляются еще при вычислениях на AST. В случае возникновения ошибок (неважно, парсинга или типизации) стадия генерации кода просто не запустится.
Мы планируем разработать специализированный DSL, призванный еще более упростить этот процесс, сделать генерацию кода расширяемой и позволить генерировать код под разные платформы.
Так же мы ведем работу над сменяемыми бэкендами. Они позволят читать и сохранять информацию о символах в формате этих платформ и генерировать для них код.
Реализация Mini C позволяет не только получить полноценный компилятор урезанного C, но также в автоматическом режиме сгенерировать плагин к VS. Этот плагин предоставляет базовые возможности IntelliSense: автодополнение при вводе, подсветку синтаксиса и символов, навигацию по символам (переход к определению, поиск вхождений), рефакторинг переименования, свертку кода и многое другое. Кроме того, с помощью Nitra можно делать рефаторинги и прочие фичи IDE.
Созданные на Nitra языки легче сопровождать.
Кроме того, любой созданный на Nitra язык является автоматически расширяемым. Так что к нашему Mini C можно легко приделать макросы в стиле Nemerle или расширить его какими-то новыми конструкциями. Как это сделано описано здесь.
Nitra скрывает от разработчика языка все сложности, связанные с разработкой движка IDE, и позволяет, не меняя исходного кода языка, получать улучшения от развития Nitra.
DSL-подход, использованный при разработке Nitra, как бы развязывает код языка и лежащую под этим реализацию.
Пока что в коде Nitra-проектов еще требуется писать код на языках общего назначения, но в каждой последующей версии необходимости в этом будет все меньше и меньше.
В будущем мы планируем разработать DSL для описания проектов и предопределенных символов.
Nitra – это открытый проект. Мы призываем всех, кого он заинтересовал, участвовать в его развитии.
Также мы призываем программистов создавать новые языки на Nitra и делать Nitra-реализации для старых языков.
Я уверен, что через какое-то время подход, использованный в Nitra будет преобладающим в области разработки языков. Присоединяйтесь к нам!
| Сообщений 12 Оценка 660 Оценить
|