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

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

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

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

  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 - конфликты недопустимы и свидетельствуют об ошибках проектирования грамматики.

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

Некоторые классы синтаксического дерева

Как уже было сказано, синтаксическое дерево состоит из объектов классов - наследников syntax_tree_node. Перечислим некоторые важные классы - наследники syntax_tree_node, которые будут нами использованы для реализации парсера Оберона00: 

ident                   - идентификатор
ident_list              - список идентификаторов
uses_list               - список модулей и пространств имен в секции uses
unit_or_namespace       - модуль или пространство имен
block                   - блок 
program_module          - программа
int32_const             - целая константа
bool_const              - логическая константа
expression              - выражение (базовый класс для всех выражений)
expression_list         - список выражений
un_expr                 - унарное ввыражение
bin_expr                - бинарное выражение
assign                  - оператор присваивания
if_node                 - условный оператор
while_node              - оператор цикла while
empty_statement         - пустой оператор
method_call             - вызов метода или внешней подпрограммы
statement_list          - последовательность операторов
named_type_reference    - имя типа
declarations            - описания
var_def_statement       - описания переменных с одним типом
variable_definitions    - секция объявлений переменных
simple_const_definition - определение именованной константы
consts_definitions_list - секция определений именованных констант

Каждый класс имеет свои поля, все необходимые поля заполняются обычно в конструкторе класса. В базовом классе syntax_tree_node имеется поле source_context типа SourceContext, определяющее местоположение конструкции, соответствующей синтаксическому узлу, в тексте программы. Именно поэтому каждый конструктор синтаксического дерева содержит последним параметром объект класса SourceContext.

Просмотреть все узлы синтаксического дерева, их свойства и методы можно с помощью утилиты Просмотрщик классов синтаксического дерева

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

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

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) { }

Здесь root - корневой узел синтаксического дерева программы, он явно описан как поле класса GPPGParser. Описываемый во второй строке конструктор носит технический характер - его просто необходимо в этом месте написать. Думаю, что эта строчка связана с неудачным проектированием генератора парсеров GPPG - разработчик забыл в генерируемый класс включить этот нужный конструктор.

Строка 

%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 (обычно эту строку можно не писать - считается, что стартовым является нетерминал в левой части первого правила).

Описание используемых терминалов

Все используемые терминалы должны быть описаны в секции определений следующим образом: 

%token ASSIGN SEMICOLUMN LPAREN RPAREN COLUMN COMMA COLON EXCLAMATION

Именно по этим определениям формируется перечислимый тип Tokens, который встречался в .lex-файле.

Кроме этого, некоторым терминалам и нетерминалам можно задавать тип.

Типы терминалов и нетерминалов

Большинство нетерминалов и некоторые терминалы должны иметь тип. Например, терминал ID имеет тип string, а терминал INTNUM - тип int. Для задания этих типов используют структуру-объединение вида 

%union  
{ 
  public bool bVal; 
  public string sVal; 
  public int iVal; 
  public ident id;
  public ident_list il;
  public statement st;
  public statement_list sl;
  ...
}

Если с терминалом или нетерминалом необходимо связать значение некоторого типа, то поле этого типа описывается в структуре union. Например, чтобы связать с терминалом ID значение строкового типа, необходимо описать в структуре union поле 

public string sVal;

После этого необходимо описать типизированный терминал следующим образом: 

%token <sVal> ID

Аналогично чтобы связать с нетерминалом Assignment тип statement, необходимо описать в структуре union поле 

public statement st;

и после этого связать поле st с нетерминалом Assignment следующим образом: 

%type <st> Assignment

Полный код описаний для типов терминалов и нетерминалов, а также полей структуры union имеет вид: 

%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;
}

%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
Приоритеты операций языка

Чтобы не задавать приоритеты операций в грамматике, в Yacc-системах используется секция задания приоритетов операций. Она имеет вид: 

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

Операции задаются в порядке от самого низкого приоритета до самого высокого.

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

expr 
  : expr PLUS expr 
  | expr MULT expr 
  | expr AND expr 
  | expr OR expr 
  | expr EQ expr
  ...

и это не вызовет неоднозначности грамматики.

Секция правил грамматики

Попробуем проследить, как распознаются правила грамматики.

Правило Assignment

Рассмотрим вначале правило для оператора присваивания: 

Assignment : ident ASSIGN expr {
	$$ = new assign($1, $3, Operators.Assignment,@$);
}
;

Здесь формируется узел синтаксического дерева для оператора присваивания. assign - это класс - наследник syntax_tree_node, который хранит всю синтаксическую информацию об операторе присваивания: идентификатор в левой части, выражение в правой части, тип оператора присваивания (в данном случае обычное присваивание, есть ещё += *= и т.д.), а также позиция конструкции присваивания в тексте программы. В данной записи $$ обозначает нетерминал в левой части, $1 - первый символ (нетерминал или терминал) в правой части правила, $2 - второй символ в правой части правила и т.д. Таким образом, $$ соответствует символу Assignment, $1 - символу ident, а $3 - символу expr. Очень важно, что если типы соответствующих символов были прописаны в секции описаний, то выражения $$, $1, $2 и т.д. имеют ровно эти типы. Узнаем в разделе описаний типы Assignment, ident и expr: 

%type <st> Assignment 
%type <id> ident
%type <ex> expr

Теперь заглянём в структуру union: 

%union  
{ 
  public expression ex;
  public ident id;
  public statement st;
}

Таким образом, можно сделать вывод, что $$ имеет тип statement, $1 - тип ident, а $3 - тип expression. Если окажется, что для какого-то нетерминала или терминала не определен тип, то считается, что соответствующий символ $... имеет тип Object.

Наконец, обратим внимание на символ @$. Он соответствует положению в тексте символа Assignment из левой части правила. Тип символа @$ - LexLocation (это стандартный тип библиотеки GPPG), неявно преобразующийся в тип SourceContext (это тип библиотеки PascalABC.NET; можно для простоты считать, что @$ имеет тип SourceContext). Аналогично @1 - это SourceContext для первого символа в правой части, @2 - для второго и т.д.

Как правило, в большинстве узлов @$ будет передаваться в качестве последнего параметра конструктора.

Правило StatementSequence

Правило для StatementSequence имеет вид: 

StatementSequence 
	: Statement {
		$$ = new statement_list($1,@$);
	}
	| StatementSequence SEMICOLUMN Statement {
		$1.Add($3,@$);
		$$ = $1;
	}
	;

Здесь формируется список операторов, которые в программе разделены точкой с запятой. Обратим внимание, что за счёт леворекурсивности этого правила первым заканчивается разбор первого оператора Statement - в этот момент мы и создаём statement_list вызовом конструктора. В рекурсивной части считается, что statement_list уже создан, и мы добавляем в него следующий Statement с помощью метода Add класса statement_list.

Во втором правиле есть и ещё одна тонкость, рассмотрим её подробнее - она часто встречается. Рассмотрим ещё раз второе правило внимательнее: 

StatementSequence : StatementSequence SEMICOLUMN Statement 
{
  $1.Add($3,@$);
  $$ = $1;
}

Здесь надо понимать, что на момент разбора этого правила StatementSequence в левой части ещё не определен, а StatementSequence в правой части, напротив, определен на предыдущих шагах. Поэтому мы вначале к переменной $1, связанной со StatementSequence в правой части и имеющей тип statement_list, добавляем Statement, хранящийся в $3, после чего инициализируем StatementSequence в левой части, присваивая ему StatementSequence из правой части: $$ = $1. За счёт ссылочной модели объектов в C# здесь можно было бы поступить и иначе: 

{
  $$ = $1;
  $$.Add($3,@$);
}

или даже так: 

{
  $$ = $1;
  $1.Add($3,@$);
}

- всё равно после присваивания $$ = $1 переменные $$ и $1 указывают на один объект.

Правила Statement

Проследим далее за правилами Statement: 

Statement: Assignment
	| IfStatement
	| WhileStatement
	| WriteStatement
	| ProcCallStatement
	| EmptyStatement
	;

Здесь нет действий в {}, поэтому по умолчанию всегда подразумевается действие $$ := $1, что нам и надо.

Рассмотрим ещё несколько правил, в которых есть ранее не встречавшиеся моменты.

Правило ident

Чтобы не преобразовывать всякий раз строковый ID в узел синтаксического дерева ident, введено правило: 

ident : ID {
  $$ = new ident($1,@$); 
}
;
Правило для унарного минуса

Правило для унарного минуса имеет вид: 

expr : MINUS expr %prec UMINUS {
  $$ = new un_expr($2,Operators.Minus,@$);
}

Ключевое слово %prec меняет в рамках одного правила приоритет операции MINUS и делает его таким же, как и у UMINUS. Заметим, что терминал UMINUS - фиктивный - он не может возникнуть при лексическом разборе, и задаётся только в секции приоритетов операций - последним и, значит, самым приоритетным.

Правило для всей программы

Вся программа на Oberon00 представляет собой модуль: 

module : MODULE ident SEMICOLUMN mainblock ident COMMA

По этому правилу производятся следующие действия: 

{
if ($2.name != $5.name)
  PT.AddError("Имя "+$5.name+" должно совпадать с именем модуля "+$2.name,@5);
		
  // Подключение стандартного модуля Oberon00System, написанного на PascalABC.NET
  var ul = new uses_list("Oberon00System");

  // Формирование модуля основной программы (используется фабричный метод вместо конструктора)
  root = program_module.create($2, ul, $4, @$);
}

Поясним их подробнее. Во-первых, проверяется, совпадает ли имя модуля в начале и в конце программы и если нет. то генерируется семантическая ошибка с помощью PT.AddError (эта ошибка будет добавлена в окно ошибок компиляции). Заметим, что на этапе построения синтаксического дерева можно распознать и диагностировать некоторые синтаксические ошибки.

Затем в начало списка подключаемых модулей добавляется так называемый системный модуль Oberon00System - он написан на Паскале и должен быть откомпилирован в .pcu.

После этого формируется синтаксический узел для всей программы (класс program_module) и присваивается переменной root.

Создание системного модуля

Напишем для компилятора Oberon00 простой системный модуль на паскале Obеron00System.pas: 

unit Oberon00System;

interface

procedure Print(o: object);
procedure Println(o: object);
procedure Println;

implementation

uses System; 

procedure Print(o: object);
begin
  Console.Write(o);
end;

/// Вывести значение
procedure Println(o: object);
begin
  Console.WriteLine(o);
end;

procedure Println;
begin
  Console.WriteLine;
end;
 
end.

Именно он подключается автоматически к любой программе на Обероне в действиях для правила module: 

...
var ul = new uses_list("Oberon00System");

В принципе, этот модуль можно было написать на самом Обероне, но в Обероне нет возможности прямого доступа к .NET-библиотекам.

Замечательная особенность среды PascalABC.NET - возможность совмещать разные языки программирования в одном проекте на уровне исходных кодов.

Обработка ошибок

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

Инсталляция плагина

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