Как создать компилятор

Общие замечания

Сразу скачиваем полный комплект разработчика парсеров.

В инфраструктуре PascalABC.NET несложно создавать компиляторы простых языков программирования. Программы, получаемые на таких языках, компилируются в .NET-код и работают, как и любой .NET-код, практически так же производительно, как и машинный.

Для создания компилятора важно понимать следующее. Компилятор имеет несколько внутренних представлений.

• Вначале текст программы разбирается им в так называемое синтаксическое дерево. Синтаксическое дерево содержит представленный в виде дерева текст программы - семантика на этом уровне не учитывается, проверяется только соответствие синтаксическим конструкциям. Например, на уровне синтаксического дерева не распознаётся ошибка описания двух переменных с одним именем - с точки зрения синтаксиса ошибки нет.
• Затем синтаксическое дерево переводится в семантическое дерево. Семантическое дерево учитывает все правила, которые сформулированы в описании языка: в частности, то, что в одном пространстве имен нельзя описать две переменные с одним именем. Кроме этого, в семантическом дереве хранится существенно больше информации, чем в синтаксическом: каждая переменная имеет тип, относится к определенному пространству имен, для подпрограмм проверяется соответствие количества и типов формальных и фактических параметров и т.д.

Заметим, что семантическое дерево, если получено, то содержит правильную программу. Семантическое дерево откомпилированного модуля можно сохранить на диск для ускорения компиляции. В PascalABC.NET так и происходит: если модуль успешно откомпилирован, то он сохраняется в .pcu-файл - это не что иное как записанное на диск семантическое дерево модуля. Если при компиляции основной программы к ней подключен данный модуль, то он повторно не компилируется - его дерево разворачивается из .pcu-файла в память, что гораздо быстрее.

• Наконец, по семантическому дереву генерируется .NET-код.

Заметим, что такое разделение на синтаксическое и семантическое деревья позволяет упростить процесс создания новых языков. В частности, если язык достаточно простой и похож на Паскаль, то он может быть переведен в синтаксическое дерево, после чего достаточно использовать стандартный преобразователь в семантическое дерево и генератор кода. Для более сложных языков с семантикой, отличной от Паскаля, для некоторых узлов синтаксического дерева необходимо писать свой преобразователь в узлы семантического дерева. в ещё более сложных ситуациях имеющихся узлов семантического дерева может оказаться недостаточно, поэтому придется создавать новые и писать для них генерацию .NET-кода.

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

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

Рассмотрим создание простого языка, который мы назовём Oberon00. Это - подмножество языка Oberon с двумя типами - INTEGER и BOOLEAN - и возможностью вызывать процедуры из внешних модулей.

Что нужно для создания компилятора

Для создания компилятора, интегрированного в среду PascalABC.NET, нам потребуется создать несколько файлов. В случае языка Oberon00 потребуется создать:

• Oberon00Parser.dll - библиотеку, содержащую парсер языка (ее следует скопировать в папку установки PascalABC.NET)
• Oberon00.xhsd - файл подсветки синтаксиса (скопировать в папку PascalABC.NET\Highlighting)

Кроме этого, обычно требуется системный модуль, содержащий стандартные подпрограммы. Его можно создать на языке Паскаль. Пусть для Оберона00 этот модуль называется Oberon00System.pas. Требуется откомпилировать его в .pcu и затем

• Скопировать Oberon00System.pas в папку PascalABC.NET\LibSource
• Скопировать Oberon00System.pcu в папку PascalABC.NET\Lib

Перезапустив среду PascalABC.NET, мы получим новый компилятор.

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

Что входит в комплект разработчика парсеров

1. Папка DLL, содержащая dll из комплекта PascalABC.NET, необходимые для создания парсера. 2. Папка GPLex_GPPG, содержащая генератор компиляторов GPLex+GPPG и документацию к нему. 3. Папка Install, содержащая файлы, которые необходимо скопировать в папку PascalABC.NET для того чтобы в оболочке PascalABc.NET появился компилятор нового языка. 4. Файл generate_all.bat для компиляции файлов .lex и .y в файлы .cs, компиляции проекта и получения библиотеки Oberon00Parser.dll и копирования этого файла в папку Install.

Далее разберем последовательно, как создать парсер.

Лексический анализатор GPLex и синтаксический анализатор GPPG

Итак, наша задача - разобрать текст программы и по нему получить синтаксическое дерево программы. Такой построитель синтаксического дерева программы будем называть парсером или синтаксическим анализатором. Для работы синтаксического анализатора необходим также сканер или лексический анализатор, который разбивает программу на лексемы - неделимые слова. Например, в языке Паскаль лексемами являются ключевые слова, идентификаторы, числовые и строковые константы, знаки операций (:= <> и т.д.).

Синтаксические анализаторы обычно создаются с помощью специальных программ, называемых генераторами компиляторов. Одним из наиболее известных генераторов компиляторов является Yacc (Yet Another Compiler of Compilers) - и в паре с ним работает генератор лексических анализаторов Lex.

Наиболее полной реализацией Yacc-Lex для .NET, генерирующей код парсера на C#, является GPLex+GPPG, разработанный Queensland University of Technology, Австралия. Вот странички продуктов: GPLex и GPPG. Однако, рекомендуется скачать исполнимые файлы отсюда - они содержат небольшие модификации, связанные с корректной русификацией.

Создание лексического анализатора

Класс Scanner

Создаваемый в результате компиляции .lex-файла класс Scanner содержит несколько важных методов и свойств. Рассмотрим их подробнее.

• Функция int yylex() возвращает уникальный номер лексемы. Все лексемы хранятся в перечислимом типе Tokens. По-существу, возвращается номер константы в перечислимом типе Tokens - например, для лексемы ID возвращается (int)Tokens.ID
• Помимо уникального номера некоторые лексемы должны возвращать дополнительные значения. Таким значением для идентификатора является его строковое представление, для INTNUM - целое число и т.д. Дополнительное значение для некоторых лексем возвращается в свойстве yylval, которое имеет тип ValueType и содержит ряд полей различных типов - для каждой лексемы может быть предусмотрено своё поле. Например, для лексемы ID предусмотрено поле string sVal, а для лексемы INTNUM - поле iVal.

Объяснение того, как это поле сопоставляется с типом лексемы, отложим до знакомства с содержимым файла .y

• Свойство yytext возвращает строковое представление текущей лексемы
• Свойство yylloc содержит положение лексемы в тексте, задаваемое типом LexLocation из пространства имен QUT.Gppg. Он хранит координаты начала и конца лексемы

Файл .lex

Лексический анализатор обычно создается в файле с расширением .lex. Он имеет вид:

Определения
%%
Правила
%%
Пользовательский код

Рассмотрим файл лексического анализатора Oberon00.lex:

%namespace GPPGParserScanner

%using PascalABCCompiler.Oberon00Parser;

Alpha [a-zA-Z_]
Digit [0-9]
AlphaDigit {Alpha}|{Digit}
INTNUM {Digit}+
ID {Alpha}{AlphaDigit}* 

%%

":=" { return (int)Tokens.ASSIGN; }
";" { return (int)Tokens.SEMICOLUMN; }
"-" { return (int)Tokens.MINUS; }
"+" { return (int)Tokens.PLUS; }
"*" { return (int)Tokens.MULT; }
"/" { return (int)Tokens.DIVIDE; }
"<" { return (int)Tokens.LT; }
">" { return (int)Tokens.GT; }
"<=" { return (int)Tokens.LE; }
">=" { return (int)Tokens.GE; }
"=" { return (int)Tokens.EQ; }
"#" { return (int)Tokens.NE; }
"(" { return (int)Tokens.LPAREN; }
")" { return (int)Tokens.RPAREN; }
"," { return (int)Tokens.COLUMN; }
"~" { return (int)Tokens.NOT; }
"&" { return (int)Tokens.AND; }
"." { return (int)Tokens.COMMA; }
":" { return (int)Tokens.COLON; }
"!" { return (int)Tokens.EXCLAMATION; }
\x01 { return (int)Tokens.INVISIBLE; }

{ID}  { 
  int res = Keywords.KeywordOrIDToken(yytext);
  if (res == (int)Tokens.ID)
    yylval.sVal = yytext;
  return res;
}

{INTNUM} { 
  yylval.iVal = int.Parse(yytext); 
  return (int)Tokens.INTNUM; 
}

%{
  yylloc = new QUT.Gppg.LexLocation(tokLin, tokCol, tokELin, tokECol);
%}

%%

public override void yyerror(string format, params object[] args) 
{
  string errorMsg = PT.CreateErrorString(args);
  PT.AddError(errorMsg,yylloc);
}

После обработки генератором лексических анализаторов GPLex мы получим одноименный cs-файл Oberon00.cs, содержащий класс Scanner лексического анализатора.

Разберем содержимое .lex-файла подробнее.

Секция определений

Вначале рассмотрим первую часть, содержащую определения лексем:

%namespace GPPGParserScanner

%using PascalABCCompiler.Oberon00Parser;

Alpha [a-zA-Z_]
Digit [0-9]
AlphaDigit {Alpha}|{Digit}
INTNUM {Digit}+
ID {Alpha}{AlphaDigit}*

Строка %namespace GPPGParserScanner означает, что класс сканера будет помещен в пространство имен GPPGParserScanner

Строка %using PascalABCCompiler.Oberon00Parser; приводит к генерации соответствующей строки в cs-файле. Пространство имен PascalABCCompiler.Oberon00Parser полностью находится во вспомогательном файле Oberon00ParserTools.cs, который содержит различные глобальные описания и подпрограммы (подробнее содержимое этого файла будет объяснено позже).

Далее идёт описание некоторых лексем в виде регулярных выражений. Например, целое число INTNUM представляет собой последовательность одной или более цифр {Digit}+, а идентификатор ID - последовательность букв или цифр, начинающуюся с буквы: {Alpha}{AlphaDigit}*

Секция правил

Вторая секция (между первым и вторым %%) является основной и содержит действия, которые необходимо выполнить, когда распознана та или иная лексема.

":=" { return (int)Tokens.ASSIGN; }
";" { return (int)Tokens.SEMICOLUMN; }
"-" { return (int)Tokens.MINUS; }
"+" { return (int)Tokens.PLUS; }
"*" { return (int)Tokens.MULT; }
"/" { return (int)Tokens.DIVIDE; }
"<" { return (int)Tokens.LT; }
">" { return (int)Tokens.GT; }
"<=" { return (int)Tokens.LE; }
">=" { return (int)Tokens.GE; }
"=" { return (int)Tokens.EQ; }
"#" { return (int)Tokens.NE; }
"(" { return (int)Tokens.LPAREN; }
")" { return (int)Tokens.RPAREN; }
"," { return (int)Tokens.COLUMN; }
"~" { return (int)Tokens.NOT; }
"&" { return (int)Tokens.AND; }
"." { return (int)Tokens.COMMA; }
":" { return (int)Tokens.COLON; }
"!" { return (int)Tokens.EXCLAMATION; }
\x01 { return (int)Tokens.INVISIBLE; }

{ID}  { 
  int res = Keywords.KeywordOrIDToken(yytext);
  if (res == (int)Tokens.ID)
    yylval.sVal = yytext;
  return res;
}

{INTNUM} { 
  yylval.iVal = int.Parse(yytext); 
  return (int)Tokens.INTNUM; 
}

Здесь приведены действия в случае если встречена та или иная лексема. Большинство действий просто возвращает порядковый номер лексемы в перечислимом типе Tokens.

Последняя лексема - INVISIBLE - символ с кодом 1 - необязательна и является вспомогательной для компилятора выражений языка (необходим для поддержки IntelliSense).

В случае лексемы INTNUM в поле yylval.iVal дополнительно возвращается целое число, соответствующее лексеме: int.Parse(yytext). Обратим внимание, что здесь нет никакой защиты от неправильного преобразования (например, в случае очень длинного целого). Причина - чтобы пока не усложнять изложение обработкой ошибок.

В случае лексемы ID вначале проверяется, не является ли она ключевым словом, и если является, то возвращается целое, соответствующее лексеме ключевого слова (например, для BEGIN возвращается (int)Tokens.BEGIN), а если не является, то возвращается (int)Tokens.ID и параллельно в поле yylval.sVal возвращается строковое представление идентификатора. Именно на этом уровне мы можем задать, чувствителен ли наш язык к регистру (например, преобразованием всех идентификаторов к UpperCase).

Секция правил завершается следующим кодом:

%{
  yylloc = new QUT.Gppg.LexLocation(tokLin, tokCol, tokELin, tokECol);
%}

Этот код позволяет для каждой лексемы получать её местоположение в тексте. Вникать в этот код не надо - он просто необходим.

Секция пользовательского кода

Наконец, в секции пользовательского кода содержится единственный переопределенный в классе Scanner метод

public override void yyerror(string format, params object[] args) 
{
  string errorMsg = PT.CreateErrorString(args);
  PT.AddError(errorMsg,yylloc);
}

Он вызывается всякий раз когда происходит синтаксическая ошибка. Здесь мы пользуемся услугами статического класса PT, который находится в файле Oberon00ParserTools.cs. PT.CreateErrorString(args) формирует строку ошибки, а PT.AddError(errorMsg,yylloc); добавляет ошибку в список ошибок компиляции PascalABC.NET. Здесь интересно то, что в случае автоматического вызова yyerror в args попадают токены, которые ожидались после данного.

Генерация кода лексического анализатора

Для генерации кода лексического анализатора следует выполнить команду:

gplex.exe /unicode oberon00.lex

Здесь gplex.exe - генератор лексических анализаторов, хранящийся в папке GPLex_GPPG, параметр /unicode указывает на то, что созданный лексический анализатор будет распознавать файлы в кодировке unicode (заметим, что он будет распознавать и однобайтные кодировки).

Создание синтаксического анализатора

Общая информация

Синтаксический анализатор - ядро нашего компилятора. Он строится по .y - файлу, в котором записываются правила грамматики языка и действия, которые выполняются по этим правилам. Каждое из действий создает соответствующий узел в синтаксическом дереве. Все узлы синтаксического дерева представляют собой иерархию классов с общим предком syntax_tree_node и описаны во внешней библиотеке SyntaxTree.dll.

Для понимания дальнейшего следует иметь некоторое начальное представление о грамматиках языков программирования, о том, как они порождают языки и об автоматах, которые проверяют, принадлежит ли данная цепочка символов языку, порождаемому грамматикой. Более конкретно, следует представлять, что такое контекстно-свободная грамматика, что Yacc-Lex системы работают с так называемыми LL(k) грамматиками, являющимися достаточно широким подмножеством контекстно-свободных грамматик.

В процессе построения грамматик придется сталкиваться с недостижимыми и циклическими продукциями грамматик, неоднозначными грамматиками. Необходимо уметь исправлять подобные ситуации хотя бы методом проб и ошибок. Особенно необходимо понимать, что Shift-Reduce - конфликты грамматик допустимы и разрешаются в пользу более длинной правой части продукции, а Reduce-Reduce - конфликты недопустимы и свидетельствуют об ошибках проектирования грамматики.

Соответствующую информацию можно прочитать в книге Ахо "Компиляторы: принципы, технологии, инструменты".

Правила грамматики

Правила грамматики содержат терминальные символы (терминалы), которые распознаются лексическим анализатором, и нетерминальные символы (нетерминалы). Каждое правило грамматики выражает нетерминал через другие терминалы и нетерминалы. Например, для оператора присваивания имеется следующее правило:

AssignOperator : ID ASSIGN expr ;

Здесь нетерминал AssignOperator выражается через терминалы ID и ASSIGN и нетерминал expr, который будет определен в другом правиле.

Нетерминал, с которого начинается разбор, называется стартовым символом грамматики. Этот нетерминал описывает всю программу. В нашей грамматике это module, а соответствующее стартовое правило имеет вид:

module : MODULE ident SEMICOLUMN Declarations BEGIN StatementSequence END ident COMMA

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

В каждом правиле может быть несколько альтернатив, разделяемых символом |:

IfStatement 
	: IF expr THEN StatementSequence END 
	| IF expr THEN StatementSequence ELSE StatementSequence END 
	;

Правила могут быть рекурсивными. Например, правило для фактических параметров имеет вид:

factparams
	: expr 
	| factparams COLUMN expr 
	;

Обратим внимание, что данное правило является леворекурсивным, поскольку рекурсивное вхождение нетерминала factparams в правую часть правила находится с левой стороны. Для рассматриваемых нами генераторов компиляторов леворекурсивные правила являются предпочтительнее праворекурсивных.

Формат .y-файла

.y-файл имеет такой же формат, как и .lex:

Определения
%%
Правила
%%
Пользовательский код

Раздел определений .y-файла

Общий вид

Рассмотрим раздел определений файла Oberon00.y

%{
    public syntax_tree_node root; // Корневой узел синтаксического дерева 
    public GPPGParser(AbstractScanner<ValueType, LexLocation> scanner) : base(scanner) { }
%}

%output=oberon00yacc.cs 

%parsertype GPPGParser

%union  
{ 
	public bool bVal; 
	public string sVal; 
	public int iVal; 
	public named_type_reference ntr;
	public ident_list il;
	public var_def_statement vds;
	public variable_definitions vdss;
	public expression ex;
	public expression_list el;
	public ident id;
	public statement st;
	public statement_list sl;
	public declarations decl;
	public Operators op;
	public simple_const_definition scd;
	public consts_definitions_list cdl;
}

%using PascalABCCompiler.SyntaxTree
%using PascalABCCompiler.Errors
%using PascalABCCompiler.Oberon00Parser

%namespace GPPGParserScanner

%start module

%token <sVal> ID
%token <iVal> INTNUM 
%token <bVal> TRUE FALSE
%token <op> PLUS MINUS MULT DIVIDE AND OR LT GT LE GE EQ NE 
%token NOT 
%token ASSIGN SEMICOLUMN LPAREN RPAREN COLUMN COMMA COLON EXCLAMATION
%token TRUE FALSE ODD BOOLEAN INTEGER
%token IF THEN ELSE BEGIN END WHILE DO MODULE CONST VAR
%token INVISIBLE

%type <id> ident
%type <ntr> type
%type <ex> expr ConstExpr
%type <st> Assignment IfStatement WhileStatement WriteStatement Statement  
%type <st> EmptyStatement ProcCallStatement
%type <sl> StatementSequence
%type <decl> Declarations
%type <el> factparams
%type <il> IDList
%type <vds> VarDecl
%type <vdss> VarDeclarations VarDeclarationsSect
%type <scd> ConstDecl
%type <cdl> ConstDeclarations ConstDeclarationsSect

%left LT GT LE GE EQ NE
%left PLUS MINUS OR
%left MULT DIVIDE AND 
%left NOT
%left UMINUS

Начальные строки

Он состоит из нескольких неравнозначных частей. Первая часть заключена в символы %{  %} и содержит код на C#, который будет вставлен в создаваемый класс Parser:

    public syntax_tree_node root; // Корневой узел синтаксического дерева 
    public GPPGParser(AbstractScanner<ValueType, LexLocation> scanner) : base(scanner) { }

Строка

%output=oberon00yacc.cs

означает, что компиляция .y-файла с помощью gppg.exe будет осуществляться в файл oberon00yacc.cs

Строка

%parsertype GPPGParser

говорит о том, что класс парсера будет иметь имя GPPGParser

Строки

%using PascalABCCompiler.SyntaxTree
%using PascalABCCompiler.Errors
%using PascalABCCompiler.Oberon00Parser

означают подключение в коде парсера соответствующих пространств имен (точки с запятой в конце строк не нужны в отличие от лексического анализатора - видимо, это ошибка проектирования gppg), а строка

%namespace GPPGParserScanner

означает, что класс парсера будет помещен в пространство имен GPPGParserScanner.

Строка

%start module

означает, что стартовым в нашей грамматике является нетерминал module (обычно эту строку можно неписать - считается, что стартовым является нетерминал в левой части первого правила).

Тип-объединение для типов терминалов (токенов) и нетерминалов

Большинство нетерминалов и некоторые терминалы должны иметь тип. Например, терминал ID имеет тип string, а терминал INTNUM - тип int.