impwx 21 ноя 2013 в 19:48

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

12 мин

96K

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

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

Но обо всем по порядку.

Первый блин

Как было сказано выше, в качестве ядра парсера мы использовали библиотеку 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). Генерация кода в данной статье рассматриваться не будет, однако элементы синтаксического дерева, как результат работы парсера, будут время от времени упоминаться.

Итак, на входе мы имеем строку. Набор символов. Работать с ней в таком виде напрямую не слишком удобно — приходится учитывать пробелы, переносы строк и комментарии. Для упрощения себе жизни разработчики парсеров обычно разделяют разбор на несколько проходов, каждый из которых выполняет какую-то одну простую задачу и передает результат своей работы следующему:

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

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

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

Требования:

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

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

Все лексемы изначально стоит поделить на 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;
	}
}

Преимущества:

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

Недостатки:

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

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

Требования:

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

Для того, чтобы упростить себе жизнь при написании парсера, следует оформить грамматику специальным образом. Никаких сложных конструкций! Все правила можно поделить на 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();
...

Признаюсь, свой первый серьезный парсер я написал именно так. Однако это плохая идея!

Во-первых, заглянуть можно только на фиксированное число символов. Для всяких 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:

Первой вызывается альтернатива id_assign.
Идентификатор a успешно совпадает.
Дальше идет точка, а ожидается знак «равно». Однако с идентификатора могут начинаться и другие правила, поэтому ошибка не выбрасывается.
Правило assign откатывает состояние назад и пробует дальше.
Вызывается альтернатива member_assign.
Идентификатор и точка успешно совпадают. В грамматике нет других правил, которые начинаются с идентификатора и точки, поэтому дальнейшие ошибки не имеет смысл пытаться обработать откатыванием состояния.
Число 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 и забивать стек вызовов.

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

Откат состояния — очень дешевая операция
Легко управлять тем, до куда можно откатываться
Легко отображать детальные сообщения об ошибках
Не требуются никакие внешние библиотеки
Небольшой объем генерируемого кода

Недостатки:

Реализация парсера вручную занимает время
Сложность написания и оптимальность работы зависят от качества грамматики
Леворекурсивные грамматики следует разруливать самостоятельно

Операторы и приоритеты

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

expr = expr_1 { op_1 expr_1 }
expr_1 = exp2_2 { op_2 expr_2 }
expr_2 = exp2_3 { op_3 expr_3 }
expr_3 = int | float | identifier
op_1 = "+" | "-"
op_2 = "*" | "/" | "%"
op_3 = "**"

Теперь представим, что у нас есть еще булевы операторы, операторы сравнения, операторы сдвига, бинарные операторы, или какие-нибудь собственные. Сколько правил получается, и сколько всего придется поменять, если вдруг придется добавить новый оператор с приоритетом где-то в середине?

Вместо этого, можно убрать из грамматики вообще все описание приоритетов и закодить его декларативно.

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

expr = sub_expr { op sub_expr }
sub_expr = int | float | identifier

partial class Parser
{
	private static List<Dictionary<LexemType, Func<Node, Node, Node>>> Priorities =
		new List<Dictionary<LexemType, Func<Node, Node, Node>>>
		{
			new Dictionary<LexemType, Func<Node, Node, Node>>
			{
				{ LexemType.Plus, (a, b) => new AddNode(a, b) },
				{ LexemType.Minus, (a, b) => new SubtractNode(a, b) }
			},
			
			new Dictionary<LexemType, Func<Node, Node, Node>>
			{
				{ LexemType.Divide, (a, b) => new DivideNode(a, b) },
				{ LexemType.Multiply, (a, b) => new MultiplyNode(a, b) },
				{ LexemType.Remainder, (a, b) => new RemainderNode(a, b) }
			},
			
			new Dictionary<LexemType, Func<Node, Node, Node>>
			{
				{ LexemType.Power, (a, b) => new PowerNode(a, b) }
			},
		};
		
	public NodeBase ProcessOperators(Func<Node> next, int priority = 0)
	{
		if (priority == Priorities.Count)
			return getter();
	
		var node = ProcessOperators(next, priority + 1);

		var ops = Priorities[priority];
		while (Lexems[LexemId].IsAnyOf(ops.Keys))
		{
			foreach (var curr in ops)
			{
				if (check(curr.Key))
				{
					node = curr.Value(
						node,
						ensure(() => ProcessOperators(next, priority + 1), "Ожидается выражение!")
					);
				}
			}
		}

		return node;
	}
}

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

Добавление поддержки унарных префиксных операторов оставляю в качестве тренировки для особо любопытных.

Что нам это дало?

Написанный вручную парсер, как ни странно, стало гораздо легче поддерживать. Добавил правило в грамматику, нашел соответствующее место в коде, дописал его использование. Backtracking hell, который частенько возникал при добавлении нового правила в старом парсере и вызывал внезапное падение целой кучи на первый взгляд не связанных тестов, остался в прошлом.

Итого, сравнительная таблица результатов:

Параметр	FParsec Parser	Pure C#
Время парсинга при 1 прогоне	220 ms	90 ms
Время парсинга при дальнейших прогонах	5 ms	6 ms
Размер требуемых библиотек	800 KB + F# Runtime	260 KB

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

Избавившись от головной боли с изменениями в грамматике, мы смогли запилить в 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.

Теги:

Хабы: