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

Материал из Вики проекта PascalABC.NET
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигацииПерейти к поиску

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

Сразу скачиваем парсер подмножества Паскаля.

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

Для узлов синтаксического дерева используется библиотека SyntaxTree.dll, заимствованная из проекта PascalABC.NET. Ее необходимо заменить собственной библиотекой (!!!)

Рассмотрим создание простого языка, являющегося подмножеством языка Pascal.


Что входит в парсер подмножества Паскаля

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

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

Лексический анализатор 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 SimplePascalParser;

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

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

Строка %using SimplePascalParser; приводит к генерации соответствующей строки в cs-файле. Пространство имен SimplePascalParser полностью находится во вспомогательном файле SimplePascalParserTools.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, который находится в файле SimplePascalParserTools.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, которые будут нами использованы для реализации парсера Паскаля: 

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  
	: PROGRAM ident SEMICOLUMN mainblock DOT

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

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

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

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

factparams
	: expr 
	| factparams COLUMN expr 
	;

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

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

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

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

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

Общий вид

Рассмотрим раздел определений файла SimplePascal.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 SimplePascalParser

означают подключение в коде парсера соответствующих пространств имен (точки с запятой в конце строк не нужны в отличие от лексического анализатора - видимо, это ошибка проектирования 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 - фиктивный - он не может возникнуть при лексическом разборе, и задаётся только в секции приоритетов операций - последним и, значит, самым приоритетным.

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

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

module : PROGRAM ident SEMICOLUMN mainblock DOT

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

{
  // Формирование модуля основной программы 
  root = program_module.create($2, null, $4, @$);
}

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

Вывод текста программы по синтаксическому дереву

Основная программа, расположенная в файле Parser.cs, строит синтаксическое дерево программы на языке Паскаль и затем выводит по нему текст программы. Если же построение дерева неуспешно, то выводится соответствующая диагностика. 

        public static void Main()
        {
            string FileName = "D:\\aa.pas";
            StreamReader sr = new StreamReader(FileName);
            string Text = sr.ReadToEnd();
            PT.CurrentFileName = FileName;
            
            Scanner scanner = new Scanner();
            scanner.SetSource(Text, 0);
            
            GPPGParser parser = new GPPGParser(scanner);
                      
            var b = parser.Parse();
            sr.Close();
            if (!b)
            {
                if (PT.Errors.Count == 0)
                    PT.AddError("Неопознанная синтаксическая ошибка!", null);
                Console.WriteLine(PT.Errors[0]);
            }
            else Console.WriteLine("Синтаксическое дерево построено");
            // parser.root содержит корень синтаксического дерева
            PrintNode(parser.root);

            Console.ReadLine();
        }
Источник — https://pascalabc.net/wiki/index.php?title=Построение_синтаксического_дерева_программы_на_языке_Паскаль&oldid=2132