Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Написание парсера с нуля: так ли ужасен черт?

Anna | 17.06.2014 | нет комментариев
В прошлом топике я рассказывал о том, как мы с ином решили ради веселия написать свой встраиваемый язык программирования для платформы .NET. У первой версии был солидный недочет — парсер был реализован на F# с поддержкой сторонней библиотеки. Из-за этого требовалась куча зависимостей, парсер работал медлительно, а помощь его была весьма муторным занятием.

Видимо, что парсер необходимо было переписать на C#, но при мысли о написании парсера с нуля внезапно находилась дюжина других срочных дел. Таким образом таск перекидывался и откладывался фактически полгода и казался непосильным, а в результате был сделан за 4 дня. Под катом я расскажу об комфортном методе, дозволившим реализовать парсер довольно трудной грамматики без применения сторонних библиотек и не тронуться умом, а также о том, как это дозволило усовершенствовать язык LENS.

Но обо каждому по порядку.

1-й блин

Как было сказано выше, в качестве ядра парсера мы применяли библиотеку FParsec. Поводы данного выбора скорее исторические, нежели непредвзятые: понравился легкий синтаксис, хотелось поупражняться в применении F#, и автор библиотеки дюже оперативно отвечал на несколько вопросов по email.

Основным недостатком этой библиотеки для нашего плана оказались внешние зависимости:

  • Приблизительно десятимегабайтный F# Runtime
  • 450 кб сборок самого FParsec

Помимо того, сам компилятор разбился на 3 сборки: парсер, синтаксическое дерево и точку входа. Сборка парсера занимала значительные 130 кб. Для встраиваемого языка это безусловно неприлично.

Иной задачей было отображение ошибок. Лаконичная запись грамматики на здешнем DSL при некорректно введенной программе выдавала нечитаемую ошибку c перечислением ожидаемых лексем:

> let x =

> Оплошность: ожидается идентификатор
          либо число
          либо скобка
          либо вызов функции
          либо 'new'
          либо ...

Правда кастомная обработка ошибок и допустима, DSL для нее очевидно не предуготовлен. Изложение грамматики некрасиво распухает и становится безусловно неподдерживаемым.

Еще одним неприятным моментом была скорость работы. При «холодном старте» компиляция всякого, даже самого простого скрипта занимала на моей машине приблизительно 350-380 миллисекунд. Судя по тому, что повторный запуск такого же скрипта занимал теснее каждого-то 5-10 миллисекунд, задержка была вызвана JIT-компиляцией.

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

Немножко теории

Сферический парсер в вакууме представляет собой функцию, которая принимает начальный код, а возвращает некое промежуточное представление, по которому комфортно будет сгенерировать код для применяемой виртуальной машины либо процессора. Почаще каждого это представление имеет древовидную конструкцию и именуется абстрактным синтаксическим деревом — АСД (в зарубежной литературе — abstract syntactic tree, AST).

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

Выходит, на входе мы имеем строку. Комплект символов. Трудиться с ней в таком виде напрямую не слишком комфортно — доводится рассматривать пробелы, переносы строк и комментарии. Для облегчения себе жизни разработчики парсеров традиционно разделяют разбор на несколько проходов, всякий из которых исполняет какую-то одну примитивную задачу и передает итог своей работы дальнейшему:

  1. Лексический анализатор: string -> IEnumerable<Lexem>
  2. Синтаксический анализатор: IEnumerable<Lexem> -> IEnumerable<Node>
  3. Семантический анализатор: IEnumerable<Node> -> ?

От того что семантический анализатор — штука сугубо индивидуальная, ее изложение в данную статью не входит. Тем не менее, я поделюсь некоторыми пригодными приемами для первых 2-х анализаторов.

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

Требования:

  • Скорость работы
  • Легкость растяжения
  • Простота реализации
  • Отслеживание расположения в начальном тексте

Алгорифм лексера примитивен: он сканирует строку слева направо, пытаясь сопоставить нынешнее расположение в строке с всякой знаменитой ему лексемой. При благополучном сравнении лексер сдвигается по строке направо на столько символов, сколько заняла предыдущая лексема, и продолжает поиск по новой до конца строки. Пробелы, табуляции и переводы строки для большинства грамматик дозволено легко игнорировать.

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

Статические лексемы, в свою очередь, есть резон поделить на операторы и ключевые слова. Ключевые слова сопоставляются только в том случае, если дальнейший за ними символ не является возможным для идентификатора (либо дальше — конец строки). В отвратном случае возникнут задачи с идентификаторами, чье предисловие совпадает с ключевым словом: скажем, "information" -> keyword(in), keyword(for), identifier(mation).

Пример реализации

enum LexemKind
{
	Var,
	Print,
	Plus,
	Minus,
	Multiply,
	Divide,
	Assign,
	Semicolon,
	Identifier,
	Number
}

class LocationEntity
{
	public int Offset;
	public int Length;
}

class Lexem : LocationEntity
{
	public LexemKind Kind;
	public string Value;
}

class LexemDefinition<T>
{
	public LexemKind Kind { get; protected set; }
	public T Representation  { get; protected set; }
}

class StaticLexemDefinition : LexemDefinition<string>
{
	public bool IsKeyword;

	public StaticLexemDefinition(string rep, LexemKind kind, bool isKeyword = false)
	{
		Representation = rep;
		Kind = kind;
		IsKeyword = isKeyword;
	}
}

class DynamicLexemDefinition : LexemDefinition<Regex>
{
	public DynamicLexemDefinition(string rep, LexemKind kind)
	{
		Representation = new Regex(@"\G"   rep, RegexOptions.Compiled);
		Kind = kind;
	}
}

static class LexemDefinitions
{
	public static StaticLexemDefinition[] Statics = new []
	{
		new StaticLexemDefinition("var", LexemKind.Var, true),
		new StaticLexemDefinition("print", LexemKind.Print, true),
		new StaticLexemDefinition("=", LexemKind.Assign),
		new StaticLexemDefinition(" ", LexemKind.Plus),
		new StaticLexemDefinition("-", LexemKind.Minus),
		new StaticLexemDefinition("*", LexemKind.Multiply),
		new StaticLexemDefinition("/", LexemKind.Divide),
		new StaticLexemDefinition(";", LexemKind.Semicolon),
	};

	public static DynamicLexemDefinition[] Dynamics = new []
	{
		new DynamicLexemDefinition("[a-zA-Z_][a-zA-Z0-9_]*", LexemKind.Identifier),
		new DynamicLexemDefinition("(0|[1-9][0-9]*)", LexemKind.Number),
	};
}

class Lexer
{
	private char[] SpaceChars = new [] { ' ', '\n', '\r', '\t' };
	private string Source;
	private int Offset;

	public IEnumerable<Lexem> Lexems { get; private set; }

	public Lexer(string src)
	{
		Source = src;
		Parse();
	}

	private void Parse()
	{
		var lexems = new List<Lexem>();

		while(InBounds())
		{
			SkipSpaces();
			if(!InBounds()) break;

			var lex = ProcessStatic() ?? ProcessDynamic();
			if(lex == null)
				throw new Exception(string.Format("Unknown lexem at {0}", Offset));

			lexems.Add(lex);
		}

		Lexems = lexems;
	}

	private void SkipSpaces()
	{
		while(InBounds() && Source[Offset].IsAnyOf(SpaceChars))
			Offset  ;
	}

	private Lexem ProcessStatic()
	{
		foreach(var def in LexemDefinitions.Statics)
		{
			var rep = def.Representation;
			var len = rep.Length;

			if(Offset   len > Source.Length || Source.Substring(Offset, len) != rep)
				continue;

			if(Offset   len < Source.Length && def.IsKeyword)
			{
				var nextChar = Source[Offset   len];
				if(nextChar == '_' || char.IsLetterOrDigit(nextChar))
					continue;
			}

			Offset  = len;
			return new Lexem { Kind = def.Kind, Offset = Offset, Length = len };
		}

		return null;
	}

	private Lexem ProcessDynamic()
	{
		foreach(var def in LexemDefinitions.Dynamics)
		{
			var match = def.Representation.Match(Source, Offset);
			if(!match.Success)
				continue;

			Offset  = match.Length;
			return new Lexem { Kind = def.Kind, Offset = Offset, Length = match.Length, Value = match.Value };
		}

		return null;
	}

	private bool InBounds()
	{
		return Offset < Source.Length;
	}
}

Превосходства:

  • Работает стремительно
  • Элементарное устройство, дозволено написать за 30 мин
  • Новые лексемы добавляются дюже легко
  • Метод подходит для множества грамматик

Недочеты:

  • Танцы с бубном при разборе языка со важными пробелами
  • Порядок объявления лексем значим: желанно сортировать по длине

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

Требования:

  • Легкость растяжения при изменении грамматики
  • Вероятность описывать подробные сообщения об ошибках
  • Вероятность заглядывать вперед на неограниченное число позиций
  • Механическое отслеживание расположения в начальном коде
  • Лаконичность, близость к начальной грамматике

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

  • Изложение — один определенный узел:
    (var_expr = "var" identifier "=" expr)
  • Повторение — один определенный узел повторяется неоднократно, допустимо с разделителем:
    main = { stmt ";" }
  • Альтернатива — выбор из нескольких узлов
    (stmt = var_expr | print_expr | assign_expr | other)

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

Правило-перечисление — это цикл. Дабы воротить последовательность значений, в C# есть дюже комфортный функционал для создания генераторов с поддержкой yield return.

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

Здесь любопытный читатель спросит:
— Как это, легко вызываются по порядку? А как же опережающие проверки? Скажем, так:

if(CurrentLexem.Type == LexemType.Var) return parseVar();
if(CurrentLexem.Type == LexemType.For) return parseFor();
...

Сознаюсь, свой 1-й солидный парсер я написал именно так. Впрочем это плохая идея!

Во-первых, заглянуть дозволено только на фиксированное число символов. Для каждых for либо var, безусловно, подойдет. Но, возможен, у нас есть такие правила в грамматике:

assign = id_assign | member_assign | index_assign
id_assign = identifier "=" expr
member_assign = lvalue "." identifier "=" expr
index_assign = lvalue "[" expr "]" "=" expr

Если с id_assign еще все ясно, то оба других правила начинаются с нетерминала lvalue, под которым может скрываться километровое выражение. Видимо, что никаких опережающих проверок здесь не напасешься.

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

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

Разглядим на примере выше. Возможен, у нас есть текст: a.1 = 2:

  1. Первой вызывается альтернатива id_assign.
  2. Идентификатор a удачно совпадает.
  3. Дальше идет точка, а ожидается знак «равно». Впрочем с идентификатора могут начинаться и другие правила, следственно оплошность не выбрасывается.
  4. Правило assign откатывает состояние назад и пробует дальше.
  5. Вызывается альтернатива member_assign.
  6. Идентификатор и точка удачно совпадают. В грамматике нет других правил, которые начинаются с идентификатора и точки, следственно последующие ошибки не имеет толк пытаться обработать откатыванием состояния.
  7. Число 1 не является идентификатором, следственно выкидывается оплошность.

Вначале напишем несколько пригодных способов:

Спрятанный текст

partial class Parser
{
	private List<Lexem> Lexems;
	private int LexemId;

	#region Lexem handlers

	[DebuggerStepThrough]
	private bool Peek(params LexemType[] types)
	{
		var id = Math.Min(LexemId, Lexems.Length - 1);
		var lex = Lexems[id];
		return lex.Type.IsAnyOf(types);
	}

	[DebuggerStepThrough]
	private Lexem Ensure(LexemType type, string msg, params object[] args)
	{
		var lex = Lexems[LexemId];

		if(lex.Type != type)
			error(msg, args);

		Skip();
		return lex;
	}

	[DebuggerStepThrough]
	private bool Check(LexemType lexem)
	{
		var lex = Lexems[LexemId];

		if (lex.Type != lexem)
			return false;

		Skip();
		return true;
	}

	[DebuggerStepThrough]
	private void Skip(int count = 1)
	{
		LexemId = Math.Min(LexemId   count, Lexems.Length - 1);
	}

	#endregion

	#region Node handlers

	[DebuggerStepThrough]
	private T Attempt<T>(Func<T> getter) where T : LocationEntity
	{
		var backup = LexemId;
		var result = Bind(getter);
		if (result == null)
			LexemId = backup;

		return result;
	}

	[DebuggerStepThrough]
	private T Ensure<T>(Func<T> getter, string msg) where T : LocationEntity
	{
		var result = Bind(getter);
		if (result == null)
			throw new Exception(msg);

		return result;
	}

	[DebuggerStepThrough]
	private T Bind<T>(Func<T> getter) where T : LocationEntity
	{
		var startId = LexemId;
		var start = Lexems[LexemId];

		var result = getter();

		if (result != null)
		{
			result.StartLocation = start.StartLocation;

			var endId = LexemId;
			if (endId > startId && endId > 0)
				result.EndLocation = Lexems[LexemId - 1].EndLocation;
		}

		return result;
	}

	#endregion
}

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

partial class Parser
{
	public Node ParseAssign()
	{
		return Attempt(ParseIdAssign)
			   ?? Attempt(ParseMemberAssign)
			   ?? Ensure(ParseIndexAssign, "Неведомый тип выражения!");
	}

	public Node ParseIdAssign()
	{
		var id = TryGetValue(LexemType.Identifier);
		if (id == null) return null;
		if (!Check(LexemType.Assign)) return null;
		var expr = Ensure(ParseExpr, "Ожидается присваиваемое выражение!");

		return new IdAssignNode { Identifier = id, Expression = expr };
	}

	public Node ParseMemberAssign()
	{
		var lvalue = Attempt(ParseLvalue);
		if (lvalue == null) return null;
		if (!Check(LexemType.Dot)) return null;

		var member = TryGetValue(LexemType.Identifier);
		if (member == null) return null;
		if (!Check(LexemType.Assign)) return null;

		var expr = Ensure(ParseExpr, "Ожидается присваиваемое выражение!");

		return new MemberAssignNode { Lvalue = lvalue, MemberName = member, Expression = expr };
	}

	public Node ParseIndexAssign()
	{
		var lvalue = Attempt(ParseLvalue);
		if (lvalue == null) return null;
		if (!Check(LexemType.SquareBraceOpen)) return null;

		var index = Ensure(ParseExpr, "Ожидается выражение индекса!");
		Ensure(LexemType.SquareBraceClose, "Не закрыта скобка!");
		Ensure(LexemType.Assign, "Ожидается знак присваивания!");

		var expr = Ensure(ParseExpr, "Ожидается присваиваемое выражение!");

		return new IndexAssignNode { Lvalue = lvalue, Index = index, Expression = expr };
	}
}

Признак DebuggerStepThrough крепко помогает при отладке. От того что все вызовы вложенных правил так либо напротив проходят через Attempt и Ensure, без этого признака они будут непрерывно кидаться в глаза при Step Into и забивать стек вызовов.

Превосходства данного способа:

  • Откат состояния — дюже дешезапилить в LENS несколько славных пророческой:

    Цикл for

    Применяется как для обхода последовательностей, так и для диапазонов:

    var data = new [1; 2; 3; 4; 5]
    for x in data do
        println "value = {0}" x
    
    for x in 1..5 do
        println "square = {0}" x
    

    Композиция функций

    С поддержкой оператора :> дозволено создавать новые функции, «нанизывая» существующие:

    let invConcat = (a:string b:string) -> b   a
    let invParse = incConcat :> int::Parse
    
    invParse "37" "13" // 1337
    

    Частичное использование допустимо с поддержкой неизвестных функций:

    fun add:int (x:int y:int) -> x   y
    let addTwo = int::TryParse<string> :> (x:int -> add 2 x)
    addTwo "40" // 42
    

    Совершенствования синтаксиса

    • Однострочные комментарии:
      somecode () // comment
    • Неинициализированные переменные:
      var x : int
    • Скобки вокруг исключительного довода лямбды опциональны:
      var inc = x:int -> x   1
    • Скобки в руководящих конструкциях убраны:
      if x then
          a ()
      else
          b ()
      
      while a < b do
          println "a = {0}" a
          a = a   1
    • Возник блок try/finally
    • Скобки при передаче индекса либо поля в функцию опциональны:
      print "{0} = {1}" a[1] SomeType::b

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

    • Объявление generic-типов и функций
    • Вероятность пометить функции либо типы признаками
    • Поддержку событий

    Также дозволено скачать собранные демки под Windows.

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB