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

Материал из Вики проекта PascalABC.NET
Перейти к навигацииПерейти к поиску

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

В инфраструктуре 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, мы получим новый компилятор.

Рассмотрим каждый пункт отдельно. Наиболее сложным является первый пункт, поэтому сконцентрируемся на нем.

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

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

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

Наиболее полной реализацией Yacc-Lex для .NET, генерирующей код парсера на C#, является GPLex+GPPG, разработанный Queensland University of Technology, Австралия. Вот странички продуктов: GPLex и 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}*

Функция yylex()

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

Здесь следует подробнее объяснить, как работает сканер (лексический анализатор) и как он взаимодействует с парсером (синтаксическим анализатором).

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

Создание парсера-плагина для среды PascalABC.NET

Источник — https://pascalabc.net/wiki/index.php?title=Как_создать_компилятор&oldid=1667