Атрибуты (attributes) и действия (actions) в грамматиках #

В предшествующих разделах мы разработали первый анализатор на основе грамматики, который умеет разобрать текст программы, и ответить на вопрос «Соответствует ли программа грамматике или содержит ошибки?».

Однако только проверка текста – слишком узкая задача. Используя только определение грамматики, мы не сможем решить не только нашу основную задачу – генерацию машинного или IL-кода, но и даже более простую, например, задачу составления карты используемых переменных (какие переменные используются в программе, какого типа, как инициализируются, и т.д.).

Есть несколько способов обработки результатов разбора входной строки. Одним из самых известных является добавление в грамматику семантических атрибутов (attributes) и семантических правил (rules) или действий (actions). Этот способ используется во многих средствах автоматического создания компиляторов, ANTLR – не исключение

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

• атрибут – это свойство (переменная), которое, как правило, связано с правилом, и хранит какую-либо его специфическую характеристику. Например, атрибут может хранить текст разобранной строки, связанной с правилом, или глубину вложений оператора if, …
• действие – некоторый программный код, срабатывающий в определенные моменты при разборе входной строки (в ANTLR понятие действия трактуется несколько шире: действия – это механизм добавления произвольного кода к генерируемому коду анализаторов, не обязательно связанному с разбором).

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

Действия #

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

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

stmt	
	:	input_stmt { Console.WriteLine("Input statement!"); }
	| 	print_stmt { Console.WriteLine("Print statement!"); }
	| 	assign_stmt { Console.WriteLine("Assignment statement!"); }
	;

Теперь по завершении разбора каждого оператора на консоль будет выдаваться сообщение, описывающее, какой именно оператор встретился при разборе. Однако по умолчанию пространство имен System, в котором объявлен класс Console, не добавляется в генерируемые классы (и при компиляции будет выдано сообщение “The name ‘Console’ does not exist in the current context”). Чтобы решить эту проблему в начало файла грамматики, сразу за объявление опций, мы добавим такую конструкцию:

@header { using System; }

Т.е. начало файла будет выглядеть как:

grammar Simple;
options { language = CSharp3; }
@header { using System; }
public
program	: ( stmt ';') +	;
…

Если теперь заново сгенерировать анализаторы, перекомпилировать и запустить наш пример, то в результате будет выдано:

Assignment statement!
Input statement!
Print statement!
All ok!

С точки зрения ANTLR, все, что содержится в фигурных скобках – представляет собой код на целевом языке (том, который указан в опции language). ANTLR не проверяет этот код на корректность – это целиком забота программиста.

Обратите внимание, что в фигурные скобки также заключается код семантических предикатов (они используются для проверки каких-либо условий в процессе разбора). Отличить действия и предикаты можно по знаку вопроса, стоящему сразу за закрывающей фигурной скобкой:

{isMethodBody}?

Некоторые важные замечания по применению действий:

• действия могут находиться в любой части выражения грамматики, при этом порядок выполнения, для, например, такой строки (часть правила):

… “строка 1” { // код } “строка 2” …

будет следующим:

1. …
2. сопоставление с токеном «строка 1»
3. выполнение кода
4. сопоставление с токеном «строка 2»
5. …

• у каждой альтернативы могут быть свои уникальные действия. Например:

expression : 
        mult ( 
        ( '+' { Console.WriteLine("Add"); }  
        | '-' {Console.WriteLine("Sub"); } 
        ) 
        mult)*

• операторы +, *, ? распространяются и на действия. При разборе входного текста действие, будет выполнено столько раз, сколько произойдет сопоставлений со строкой.

Например, для приведенного в предыдущем пункте правила строка:

a - 1 + 1 + 1

породит вывод:

Sub
Add
Add

• если в коде нужно использовать скобки, то нужно следить за тем, чтобы в рамках одного действия все открытые фигурные скобки были корректно закрыты. Два примера (внешние скобки, обрамляющие действие, выделены полужирным):

Правильный вариант:

{ { Console.WriteLine("Add"); } }  

Неправильный вариант (хотя общий баланс скобок и соблюдён, но действие будет разбито на 2):

{ } Console.WriteLine("Add"); { } 

Действия, в том виде, в каком они приведены в этом разделе, обладают очень существенным недостатком – они практически никак не используют информацию о результатах разбора (максимум – разные действия для разных альтернатив). Для решения этой проблемы используются атрибуты.

Атрибуты #

Для демонстрации использования атрибутов вернемся к нашему исходному примеру (до добавления действий) и модифицируем следующее правило:

assign_stmt
	: IDENT '=' expression 
            { Console.WriteLine("Assign to " + $IDENT.text.ToUpper() + 
            " value of " + $expression.text); 
            }
            ;

Соберем измененный пример (не забыв добавить @header { using System; }) и выполним. В результате получим:

Assign to A value of 3 + 4
All ok!

В данном примере мы дважды обращались к результатам разбора из действий: в строке $IDENT.text (ToUpper() – это уже стандартный метод для строк в .Net Framework) и $expression.text.

В общем виде обращение к атрибутам токенов или результатов работы синтаксических правил осуществляется как:

$<имя токена или правила>.<имя атрибута>

Если нужно обратиться к атрибуту текущего правила (т.е. того, которое сейчас разбирается), то обращение происходит просто в виде:

$<имя атрибута>

Однако, в этом случае доступны не все атрибуты (для некоторых просто еще не определены значения). Состав атрибутов для токенов предопределен заранее и не может меняться. Основные атрибуты токенов:

В отличие от токенов, атрибуты правил могут расширяться разработчиком. Однако, есть и ряд предопределенных:

В приведенном примере использование имени токена или правила было однозначным, т.к. каждое имя встречалось ровно 1 раз. Однако, например, вот в таком правиле:

if_stmt 	: 'if' expression 'then' stmt ('else' stmt)? 'endif';

правило stmt встречается дважды, поэтому, при ссылке на него из действий, возникнет вопрос: о каком из двух операторов идет речь?

Для разрешения этой неоднозначности возможны два подхода:

1. размещать действие по обработке каждого из операторов в том месте, где этот оператор встречается – до того, как встретится следующий:

if_stmt : 
    'if' expression 'then' stmt { // обработка ветки then }
    ('else' stmt { // обработка ветки else } )? 
    'endif';

2. использовать механизм меток для назначения каждому оператору уникального имени:

if_stmt : 
    'if' expression 'then' then_stmt = stmt 
    (else_token = 'else' else_stmt = stmt )? 
    'endif'
    { 
        Console.WriteLine("then " + $then_stmt.text);
        if ($else_token != null)  
        Console.WriteLine("else " + $else_stmt.text);  
        else 
        Console.WriteLine("'else' not present");   
    }
    ;

В этом примере каждому оператору stmt присваивается уникальная метка (then_stmt или else_stmt), а также уникальная метка присваивается токену ‘else’. Последнее сделано для того, чтобы проверить была ли распознана ветка с ‘else’ – если переменная не пустая, то распознавания токена прошло, иначе нет (к сожалению, подобную проверку нельзя сделать с использованием самого правила – в действиях ANTLR только по имени, без указания атрибута, можно обращаться лишь к токенам, но не к правилам).

Вся обработка производится в одном общем действии в конце правила:

• оператор, помещенный в ветку then, печатается всегда
• если встретилось слово ‘else’ то печатается оператор ветки else, иначе выдается сообщение ’else’ not present.

Еще один пример использования меток – это коллекции значений в правилах с операторами * и +. Например, в правиле (слегка модифицированное правило ввода):

input_stmt : 'input' IDENT (',' IDENT) *	;

токен IDENT может встречаться 1 или более раз, причем для нас все идентификаторы равноправны (максимум, что важно – это порядок их следования).

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

input_stmt
	:	'input' id+=IDENT (',' id+=IDENT) * 
		{ 
			Console.WriteLine("Input " + $id.Count);
			foreach(IToken t in $id)
			{
				Console.WriteLine(t.Text);
			} 
		}
	; 

Обратите внимание, что в списке набираются объекты типа IToken, у которых свойство Text , в отличие от атрибута text, указывается с прописной буквы.

К сожалению, подобная техника не применима к выражениям, в которых повторяются не токены, а синтаксические правила, например, как в выражении

 print_stmt : 'print' expression (',' expression )* ;

(точнее списочные метки с синтаксическими правилами можно использовать, если грамматика генерирует AST-деревья, но о них будет сказано позже).

Именованные действия #

Кроме действий внедряемых непосредственно в правила, в ANTLR существует также механизм, позволяющий добавлять код не к отдельным правилам и альтернативам, а сразу ко всему генерируемому классу или даже в заголовок файла. Ранее мы уже встречались с таким механизмом, когда использовали конструкцию

@header { using System; }

В общем виде синтаксис именованных действий выглядит следующим образом:

@<имя действия> { <код> }

ANTLR поддерживает следующие именованные действия уровня грамматики (т.е. распространяющихся на всю грамматику разом) или глобальные действия:

Кроме глобальных именованных действий, существуют также именованные действия на уровне правил. Эти действия называются init и after и указывают код, который должен выполнится:

• при вызове правила, до начала какого-либо разбора (init)
• после полного завершения разбора и выполнения всех встроенных действий (after)

Синтаксис именованных действий уровня правил аналогичен глобальным правилам, но задаются они не один раз на всю грамматику, а в каждом правиле. Например, модифицировав правило для оператора вывода:

print_stmt
    @init {List<string> exp = new List<string>(); }
    @after {
	    Console.WriteLine("Print " + exp.Count);
	    foreach(String t in exp)
	    { 
            Console.WriteLine(t);	
        } 
    }

    : 'print' exp1=expression { exp.Add($exp1.text); } 
    (',' exp2=expression { exp.Add($exp2.text); } )*
	    ;

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

Передача данных между правилами. #

Параметры правил и возвращаемые значения #

Глобальные и динамические области (scope) #

// TODO

Генератор IL-кода на основе действий и атрибутов #

Теперь, когда мы знакомы в общих чертах с работой атрибутов действий, можно применить эти знания для решения нашей основной задачи – построения компилятора с языка Simple на IL.

Для того, чтобы упростить разработку кода по генерации IL (чтобы его разрабатывать в Visual Studio, а не ANTLRWorks, который ничего не знает о языке C#), а также упростить разработку и чтение файлов грамматики, которые становится очень сложно читать, если размещать в действиях много кода мы всю кодогенерацию вынесем в отдельный класс Emitter, который будет предоставлять набор методов для генерации тех или иных структур и кода.

Грамматика

grammar Simple;
options { language = CSharp3; }

@header { using SimpleCompilator; }

@members {
  Emitter emitter; 
  public SimpleParser(ITokenStream input, Emitter emitter)
  	: this(input) 
  {
    this.emitter = emitter;
  }
}

public
program 	: (stmt ';') + ;
	
stmt	: input_stmt | print_stmt | assign_stmt	;

assign_stmt
	:	IDENT '=' expression { emitter.AddAssignStatement($IDENT.text ); }
	;

print_stmt
	:	'print'	expression { emitter.AddPrintStatement(); } 
(',' expression { emitter.AddPrintStatement(); } )*
;

expression
	:	mult ( op=('+' | '-') mult { emitter.AddOperation($op.text); } )* 
	;

mult	
	:	atom ( op=( '*' | '/') atom { emitter.AddOperation($op.text); } )*
	;

atom	
	:	IDENT { emitter.AddLoadID($IDENT.text); }
	| 	NUMBER { emitter.AddLoadConst($NUMBER.text); }
	| 	'(' expression ')'
	;

input_stmt
	:	'input' IDENT { emitter.AddInputStatement($IDENT.text ); }
	;


NUMBER	:	DIGIT +	;
	
IDENT	:	(LETTER | '_') (LETTER | '_' | DIGIT)* ;

fragment LETTER 	:	'A'..'Z' | 'a'..'z';
	
fragment DIGIT	:	'0'..'9'	;

WS	:	('\t' | '\r'? '\n' | ' ')+ { $channel = Hidden; };

Класс-эмиттер

using System.Collections.Generic;
using System.Text;
using System.IO;

namespace SimpleCompilator
{
    public class Emitter
    {
        /// Класс для хранения информации о переменных
        public class VariableInfo
        {
            public VariableInfo(string name)     {  Name = name; }
            public string Name { get; set; }
        }

        /// Таблица переменных
        IDictionary<string, VariableInfo> variableTable = 
            new Dictionary<string, VariableInfo>();

        /// Буфер для формирования тела основного метода
        StringBuilder methodBody = new StringBuilder();

        /// Запись в выходной поток шапки файла
        void WriteHeader(StreamWriter outWriter)
        {
            // Объявление сборки, модуля и подключаемых сборок
            outWriter.WriteLine(".assembly Program { }");
            outWriter.WriteLine(".module Program.exe");
            outWriter.WriteLine(".assembly extern mscorlib { }");
            outWriter.WriteLine();

            // Объявление основного метода - точки входа (стек ставим условно)
            outWriter.WriteLine(".method public static void Main() {");
            outWriter.WriteLine(".entrypoint");
            outWriter.WriteLine(".maxstack 300");
        }

        /// Запись окончания файла
        void WriteFooter(StreamWriter outWriter)
        {
            outWriter.WriteLine("ret");
            outWriter.WriteLine("}");
        }

        /// Запись объявления всех встреченных локальных переменных
        void WriteLocals(StreamWriter outWriter)
        {
            if (variableTable.Count == 0) return;

            StringBuilder localsString = new StringBuilder();
            localsString.Append(".locals (");
            foreach (VariableInfo variable in variableTable.Values)
            {
                localsString.AppendFormat("int32 {0},", variable.Name);
            }
            localsString.Remove(localsString.Length - 1, 1);
            localsString.Append(")");

            outWriter.WriteLine(localsString.ToString());
        }

        /// Запись ранее сгенерированного тела метода
        void WriteMethodBody(StreamWriter outWriter)
        {
            outWriter.WriteLine(methodBody.ToString());
        }

        /// Запись всего выходного файла
        public void SaveMSIL(string fileName)
        {
            StreamWriter outWriter = 
                new StreamWriter(File.Create(fileName), 
                    new System.Text.UTF8Encoding(true));

            WriteHeader(outWriter);
            WriteLocals(outWriter);
            WriteMethodBody(outWriter);
            WriteFooter(outWriter);

            outWriter.Flush();
        }

        /// Добавление кода для оператора присваивания
        public void AddInputStatement(string variableName)
        {
            if (!variableTable.Keys.Contains(variableName))
            {
                variableTable.Add(variableName, new VariableInfo(variableName));
            }

            methodBody.AppendLine("ldstr \"Введите значение переменной " 
                + variableName + ": \"");
            methodBody.AppendLine("call void [mscorlib]System.Console::Write(string)");

            methodBody.AppendLine("call string [mscorlib]System.Console::ReadLine()");
            methodBody.AppendLine("call int32 [mscorlib]System.Int32::Parse(string)");
            methodBody.AppendLine("stloc  " + variableName);

        }

        /// Добавление кода для оператора печати (только целые значения)
        /// Здесь формируется только операция вывода - само значение в этот момент уже в стеке
        public void AddPrintStatement()
        {
            methodBody.AppendLine("call void [mscorlib]System.Console::WriteLine(int32)");
        }

        /// Добавление кода для оператора присваивания
        /// Аналогично оператору печати здесь формируется только код загрузки переменной 
        /// - значение уже в стеке
        public void AddAssignStatement(string variableName)
        {
            if (!variableTable.Keys.Contains(variableName))
            {
                variableTable.Add(variableName, new VariableInfo(variableName));
            }

            methodBody.AppendLine("stloc  " + variableName);
        }

        /// Загрузка в стек значения локальной переменной
        public void AddLoadID(string variableName)
        {
            methodBody.AppendLine("ldloc  " + variableName);
        }

        /// Загрузка в стек константы
        public void AddLoadConst(string number)
        {
            methodBody.AppendLine("ldc.i4  " + number);
        }

        /// Генерация кода операций
        public void AddOperation(string op)
        {
            switch (op)
            {
                case "+":
                    methodBody.AppendLine("add");
                    break;
                case "-":
                    methodBody.AppendLine("sub");
                    break;
                case "*":
                    methodBody.AppendLine("mul");
                    break;
                case "/":
                    methodBody.AppendLine("div");
                    break;
                default:
                    break;
            }
        }
    }
}

Код основной программы

using System;

namespace SimpleCompilator
{
    class Program
    {
        static void Main(string[] args)
        {
            if (args.Length == 2)
            {
                Antlr.Runtime.ANTLRFileStream inStream = 
                    new Antlr.Runtime.ANTLRFileStream(args[0]);
                SimpleLexer lexer = new SimpleLexer(inStream);

                Emitter emitter = new Emitter();

                Antlr.Runtime.CommonTokenStream tokenStream = 
                    new Antlr.Runtime.CommonTokenStream(lexer);
                SimpleParser parser = 
                    new SimpleParser(tokenStream, emitter);
              
                parser.program();
                emitter.SaveMSIL(args[1]);
            }
            else
            {
                Console.WriteLine("usage: <program> <inputfile> <outputfile>");
            }
        }
    }
}