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

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

Содержание

Данный материал устарел

Мы будем создавать парсер языка - программу, переводящую текст программы на языке программирования, в так называемое синтаксическое дерево. По-существу, парсер является первой частью компилятьра, его front-endом.

Папка с грамматикой

В папке с грамматикой - 2 файла - .grm и .pgt. .grm содержит файл с грамматикой в формате Gold Parser Builder, дополненный шаблонами действий (действия - в стиле Yacc). Шаблоны действий хранятся в виде комментариев Gold Parser Builder, так что на компиляцию им грамматики не влияют.

.pgt - это шаблон для создания скелета парсера, имеется для различных языков, мы используем для C#. Это означает, что сами парсеры

Все остальные файлы, если они есть, - можно убить - они генерируются автоматически.

По .grm файлу Gold Parser Builder автоматически создает .cgt файл - это файл откомпилированной грамматики - пока без правил. Они будут учтены позже.

Шаблоны в .grm файле

Шаблоны создавались Ткачуком для облегчения автоматической генерации кода. Рассмотрим пример:

!<%NAME%> %CODE%
!*
[TERMINALTEMPLATE]
		{
			%NAME% _%NAME%=new %NAME%(%PARAMS%);
			_%NAME%.source_context=parsertools.GetTokenSourceContext();
			%CODE%
			return _%NAME%;
		}
*!

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

tkIf 			= 'if'                          !*<token_info>*!

Здесь - первая строка

!<%NAME%> %CODE%

задает вид правой части: <token_info>. В данном случае %NAME%=token_info, %CODE% - пустой

Все терминальные символы подвергаются действию этого шаблона. В результате в данном случае <token_info> переходит в

token_info _token_info=new token_info(%PARAMS%);
_token_info.source_context=parsertools.GetTokenSourceContext();
// пусто
return _token_info;

%PARAMS% - это параметр в круглых скобках в <> в правилах. Поскольку правило имеет вид <token_info> и не содержит круглых скобок, то здесь здесь %PARAMS% - пустой.

source_context - это объект класса SourceСontext, хранящий строку и столбец начала и конца узла в синтаксическом дереве.

Шаблон для нетерминала

Рассмотрим нетерминал:

<if_then_else_branch>
        ::= tkThen <then_branch>        !*3if_node<null,(statement)$2,null>
								parsertools.create_source_context($$,$1,parsertools.sc_not_null($2,$1));

Цифра 3 говорит о том, что используется шаблон нетерминала №3:

!*
[NONTERMINALTEMPLATE3]         
		{
			%NAME% _%NAME%=new %NAME%(%PARAMS%);
			%CODE%
			return _%NAME%;
		}
*!

Если цифра не присутствует, то шаблон не применяется.

Как и в Yacc, в правилах доступны $$ (левая часть правила), $1 - первый параметр и т.д.

Как генерируется парсер

Вначале мы подаем файл .grm программе Gold Parser Builder или ее консольной версии. Если ошибок нет, то генерируется файл .cgt - это откомпилированный файл грамматики. Он не содержит правил.

Затем по файлу .cgt и файлу .pgt (заготовка для скелета парсера) с помощью программы createskelprog_main.exe (программа входит в консольную версию Gold Parser Builder, скачать ее можно со страницы [1]) генерируется скелет парсера на конкретном языке (в нашем случае - на C#). Этот скелет содержит парсер, в котором для каждого правила создан пустой метод. Эти методы и надо заполнить действиями по генерации синтаксического дерева программы.

При изменении грамматики такой подход чрезвычайно неудобен, именно поэтому Ткачук создал программу, которая по файлу грамматики и по получаемому скелету парсера на C# вписывает в этот скелет правила, содержащиеся в комментариях !* *! в .grm файле после каждого правила.

Программа Ткачука, выполняющая это действие, называется grmCommentCompiler.exe. В итоге вся последовательность действий имеет вид (на примере грамматики для языка КуМир):

goldbuilder_main.exe KuMir.grm KuMir.cgt
createskelprog_main.exe KuMir.cgt KuMir.pgt KuMir.tmpl
grmCommentCompiler.exe KuMir.grm KuMir.tmpl KuMir.cs

Заметим, что для работы парсера необходим так называемый движок парсера (Parser Engine). В нашем случае он находится в файле ParserTools.dll, построенном на движке Морозова Morozov C# Engine со страницы [2]

Основные узлы синтаксического дерева

Все узлы синтаксического дерава наследуются от базового класса tree_node

	public class tree_node
	{
		public tree_node()
		public tree_node(SourceContext _source_context)
		public SourceContext source_context
		public virtual void visit(IVisitor visitor)
	}

Для реализации механизма визиторов каждом узле дерева определен метод

		public virtual void visit(IVisitor visitor)
		{
			visitor.visit(this);
		}

Для обхода дерева необходимо написать класс визитор, в котором будет переопределена функция visit для всех типов узлов

	class visualizator : IVisitor
	{
		public void visit(tree_node _tree_node)
		{}
	. . .
        }

Этот пункт не закончен.

Устройство парсера

Чтобы встроить парсер в оболочку PascalABC.NET, необходимо создать в папке Parsers проекта подпапку с именем языка. Рассмотрим этот процесс на примере создания парсера Оберона.

Создадим подпапку OberonParser. Скопируем в нее созданный на предыдущем этапе парсер в файл Oberon_lrparser_rules.cs Скопируем остальные файлы из любой папки с парсерами, переименовав некоторые из них:

Parser.cs 
Oberon_lrparser.cs 
OberonParserTools.cs 
Errors.cs 

Parser.cs

Parser.cs содержит реализацию интерфейса IParser. Для этого кода сделаю абстрактный класс. Безобразие - тут всё повторяется.

Приведем код на примере парсера КуМира:

namespace PascalABCCompiler.KuMirParser
{
 
    public class KuMirLanguageParser : IParser
    {
        GPBParser_KuMir parser;
 
        public KuMirLanguageParser()
        {
            filesExtensions = new string[1];
            filesExtensions[0] = ".alg";
        }
 
        string[] filesExtensions;
        public string[] FilesExtensions
        {
            get
            {
                return filesExtensions;
            }
        }
 
        public ILanguageInformation LanguageInformation {
			get {
        		return new DefaultLanguageInformation(this);
			}
		}
 
        public void Reset()
        {
            parser = new GPBParser_KuMir(CGTResourceExtractor.Extract(new ResourceManager("KuMirParser.KuMirLang", Assembly.GetExecutingAssembly()), "KuMirLanguage"));
            parser.max_errors = 30;
        }
 
        public bool CaseSensitive
        {
            get
            {
                return parser.LanguageGrammar.CaseSensitive;
            }
        }
 
 
        public List<compiler_directive> CompilerDirectives
        {
            get
            {
                return new List<compiler_directive>();
            }
        }
        SourceFilesProviderDelegate sourceFilesProvider = null;
        public SourceFilesProviderDelegate SourceFilesProvider
        {
            get
            {
                return sourceFilesProvider;
            }
            set
            {
                sourceFilesProvider = value;
            }
        }
 
        List<Error> errors = new List<Error>();
        public List<Error> Errors
        {
            get
            {
                return errors;
            }
            set
            {
                errors = value;
            }
        }
        public Keyword[] Keywords
        {
            get
            {
                return new Keyword[0];
            }
        }
 
 
        public syntax_tree_node BuildTree(string FileName, string Text, string[] SearchPatchs, ParseMode ParseMode)
        {
            if (parser == null)
                Reset();
            parser.errors = Errors;
            parser.current_file_name = FileName;
            parser.parsertools.LineCorrection = 0;
            syntax_tree_node cu = null;
            switch (ParseMode)
            {
                case ParseMode.Normal:
                    cu = (syntax_tree_node)parser.Parse(Text);
                    break;
                case ParseMode.Expression:
                case ParseMode.Statement:
                    return null;
            }
            if (cu != null && cu is compilation_unit)
            {
                (cu as compilation_unit).file_name = FileName;
                (cu as compilation_unit).compiler_directives = CompilerDirectives;
            }
            return cu;
        }
 
        public string Name
        {
            get
            {
                return "KuMir";
            }
        }
        public string Version
        {
            get
            {
                return "1.0";
            }
        }
        public string Copyright
        {
            get
            {
                return "(c) 3 course";
            }
        }
 
        public override string ToString()
        {
            return "KuMir Language Parser v1.0";
        }
 
        public IPreprocessor Preprocessor
        {
            get
            {
                return null;
            }
        }
    }
}

Errors.cs

Этот код тоже везде повторяется. В PascalABC - самый полный набор ошибок:

namespace PascalABCCompiler.PascalABCParser.Errors
{
    public class bad_operand_type: SyntaxError
	{
		public bad_operand_type(string _file_name,SourceContext _source_context,syntax_tree_node _node):
            base(StringResources.Get("OPERATOR_NOT_IMPLEMET_TO_THIS_OPEAND_TYPE"), _file_name, _source_context, _node)
		{
		}
	}
    public class statement_expected : SyntaxError
	{
		public statement_expected(string _file_name,SourceContext _source_context,syntax_tree_node _node):
            base(StringResources.Get("STATEMENT_EXPECTED"), _file_name, _source_context, _node)
		{
		}
 
	}
    public class bad_leftside_assigment : SyntaxError
	{
		public bad_leftside_assigment(string _file_name,SourceContext _source_context,syntax_tree_node _node):
            base(StringResources.Get("LEFT_SIDE_ASSIGN_MUST_BE_VARIABLE"), _file_name, _source_context, _node)
		{
		}
	}
    public class nonterminal_token_return_null : SyntaxError
	{
		public nonterminal_token_return_null(string _file_name,SourceContext _source_context,syntax_tree_node _node,string nonterminal_token_name):
            base(string.Format(StringResources.Get("NONTERMINALTOKEN_{0}_RETURN_NULL"), nonterminal_token_name),
				_file_name,_source_context,_node)
		{
		}
	}
    public class unexpected_return_value : SyntaxError
    {
        public unexpected_return_value(string _file_name, SourceContext _source_context, syntax_tree_node _node)
            : base(StringResources.Get("PROCEDURE_CANNOT_HAVE_RETURNED_VALUE"), _file_name, _source_context, _node)
        { 
        }
    }
    public class unexpected_ident : SyntaxError
    {
        public unexpected_ident(string _file_name,ident unexpected_id,string expected,SourceContext _source_context, syntax_tree_node _node)
            : base(string.Format(StringResources.Get("EXPECTED_{0}_BUT_FOUND_{1}"), expected, unexpected_id.name), _file_name, _source_context, _node)
        {
        }
    }
    public class PABCNETUnexpectedToken : SyntaxError
    {
        private string _message;
        public PABCNETUnexpectedToken(PascalABCCompiler.ParserTools.GPBParser parser)
            : base("", parser.current_file_name, parser.parsertools.GetTokenSourceContext(parser.LRParser), (syntax_tree_node)parser.prev_node)
        {
            List<GoldParser.Symbol> Symbols = parser.parsertools.GetPrioritySymbols(parser.LRParser.GetExpectedTokens());
            if (Symbols.Count == 1)
            {
                string OneSybmolText = "ONE_" + Symbols[0].Name.ToUpper();
                string LocOneSybmolText = StringResources.Get(OneSybmolText);
                if (LocOneSybmolText != OneSybmolText)
                {
                    _message = string.Format(LocOneSybmolText);
                    return;
                }
            }
            _message = string.Format(StringResources.Get("EXPECTED{0}"), PascalABCCompiler.FormatTools.ObjectsToString(parser.parsertools.SymbolsToStrings(Symbols.ToArray()), ","));
        }
        public PABCNETUnexpectedToken(string _file_name, string expected, SourceContext _source_context, syntax_tree_node _node)
            : base("", _file_name, _source_context, _node)
        {
            _message = string.Format(StringResources.Get("EXPECTED{0}"), expected);
        }
        public override string Message
        {
            get
            {
                return _message;
            }
        }
    }
 
}

Остальные парсеры заимствуют только UnexpectedToken - видимо, из лени. Надо всё это переделывать - всё повторяется.

ИмяЯзыка_lrparser.cs

ИмяЯзыкаParserTools.cs

Тут тоже свален всякий мусор, который в другие места никуда видимо не пихался. Привожу для Kumir - в PascalABC есть что-то дополнительное. Это тоже надо переделывать, вынося в абстрактный класс.

Суть здесь - простая: когда возникает ошибка, в которой ожидалось несколько токенов, выбирается один согласно приоритету, и говорится: ожидался такой-то токен. Для этого все токены разбиты по приоритетам - в symbol_priority. Метод symbol_to_string переводит токен в строку.

namespace PascalABCCompiler.KuMirParser
{
    public static class StringResources
    {
        private static string prefix = "KUMIRPARSER_";
        public static string Get(string Id)
        {
            string ret = PascalABCCompiler.StringResources.Get(prefix + Id);
            if (ret == prefix + Id)
                return Id;
            else
                return ret;
        }
    }
 
    public class KuMir_parsertools : parser_tools
    {
        public override string symbol_to_string(Symbol symbol)
        {
            switch (symbol.Index)
            {
                case (int)GPBParser_KuMir.SymbolConstants.SYMBOL_TK_MINUS:
                case (int)GPBParser_KuMir.SymbolConstants.SYMBOL_TK_DIV:
                case (int)GPBParser_KuMir.SymbolConstants.SYMBOL_TK_MULT:
                case (int)GPBParser_KuMir.SymbolConstants.SYMBOL_TK_GREATER:
                case (int)GPBParser_KuMir.SymbolConstants.SYMBOL_TK_GREATEREQUAL:
                case (int)GPBParser_KuMir.SymbolConstants.SYMBOL_TK_LOWER:
                case (int)GPBParser_KuMir.SymbolConstants.SYMBOL_TK_LOWEREQUAL:
                case (int)GPBParser_KuMir.SymbolConstants.SYMBOL_TK_NOTEQUAL:
                case (int)GPBParser_KuMir.SymbolConstants.SYMBOL_TK_POWER:
                    return StringResources.Get("OPERATOR");
            }
            string res = StringResources.Get(symbol.Name);
            /*if (res.IndexOf("TK_") == 0)
                return res.Remove(0, 3).ToLower();
            return res;*/            
 
            return res;
        }
 
        public override int symbol_priority(Symbol symbol)
        {
 
            switch (symbol.Index)
            {
                case (int)GPBParser_KuMir.SymbolConstants.SYMBOL_TK_END:
                    return 8;
                case (int)GPBParser_KuMir.SymbolConstants.SYMBOL_TK_BEGIN:
                case (int)GPBParser_KuMir.SymbolConstants.SYMBOL_TK_INTEGER:
                case (int)GPBParser_KuMir.SymbolConstants.SYMBOL_TK_ROUNDCLOSE:
                    return 9;
                case (int)GPBParser_KuMir.SymbolConstants.SYMBOL_TK_IDENTIFIER:
                    return 10;
 
                case (int)GPBParser_KuMir.SymbolConstants.SYMBOL_TK_ASSIGN:
                    return 25;
 
                case (int)GPBParser_KuMir.SymbolConstants.SYMBOL_TK_EQUAL:
                    return 25;
 
                case (int)GPBParser_KuMir.SymbolConstants.SYMBOL_EXPRESSION:
                    return 100;
                case (int)GPBParser_KuMir.SymbolConstants.SYMBOL_STATEMENT:
                    return 110;
                case (int)GPBParser_KuMir.SymbolConstants.SYMBOL_TK_SEMICOLON:
                    return 1000;
            }
            if (symbol.SymbolType == SymbolType.Terminal)
                return 1;
            return 0;
        }
    }
}
Персональные инструменты