Универсальная процедура разборки текстов

[ipatov_net]

Проголосуйте, что ли, на харбахабре, у кого инвайт есть?
Вот, собсна тот же текст, но тут:

Зачем?

Каждому из нас, рано или поздно, приходила в голову идея создания собственного небольшого языка программирования (как пишется в умных книжках, Domain Specific Language). Задача это, разумеется, непростая - и, в лучшем случае, на выходе получался колченогий инвалид, со своей работой справляющийся, но синтаксис языка выходил зависящим не столько от задачи, сколько от особенностей реализации парсера. В худшем же случае, всё заканчивалось сакраментальной фразой «А ну её к чёрту!».
Автор данной статьи тоже пытался наступать на эти грабли, и в результате прошёл некую эволюцию - сначала это был интерпретатор с жёстко заданным синтаксисом (и весьма плачевной производительностью), следующим шагом была попытка создать некий «универсальный» кросс-транслятор (с компиляцией «на лету» получившихся в результате трансляции исходных текстов на языке Object Pascal), обвешанный уймой конфигурационных файлов, задающих синтаксис - но, в конечном итоге, с появлением в нашей жизни .NET 3.5, LINQ и более-менее вменяемых элементов из области функционального программирования в C#, я решил написать очередную итерацию «универсального парсера».

Идеи

Исходный текст программы будем представлять в виде «синтаксического дерева», описывающего её структуру в виде некоего иерархически-организованного набора объектов. Введём следующие понятия:

1. Парсер - средство перевода исходного текста в набор объектов-тегов.
2. Трансформер - средство перевода одного набора тегов в другой.
3. Генератор - средство перевода набора тегов в исходный текст (что необходимо при создании кросс-трансляторов).

Соответственно, определим интерфейсы:
public interface IParser
{
    IEnumerable Parse(IEnumerable Source);
}

public interface ITransformer
{
    IEnumerable Transform(IEnumerable Source);
}

public interface IGenerator
{
    IEnumerable Generate(IEnumerable Source);
}

Примечание: ITag - это интерфейс к нашим объектам-тегам.

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

С чего начать?

Начал я, разумеется, с определения объектов-тегов и их интерфейсов:
public interface INamedObject
{
    string Name { get; }
}

public interface IDataObject
{
    T Data { get; }
}

public interface IVersionedObject : INamedObject
{
    int[] Version { get; }
}

public struct ObjVersion
{
    public string Name;
    public int[] Version;
}

public interface ITag : IVersionedObject
{
}

public interface ITag : ITag, IDataObject
{
}

public interface ITagCollection
{
    IEnumerable Tags { get; }
}

public interface ITagMap
{
    IDictionary TagMap { get; }
}

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

[Serializable]
public class SimpleTag : ITag
{
    public string Name { get; private set; }
    public int[] Version { get; private set; }
    public T Data { get; private set; }
    public SimpleTag(string Name, int[] Version, T Data)
    {
        this.Name = Name;
        this.Version = Version;
        this.Data = Data;
    }
    public SimpleTag(ObjVersion Version, T Data)
      :this(Version.Name, Version.Version, Data)
    {
    }

public override string ToString()
    {
        return string.Format("[{0}] {1}", Name, Data);
    }
}

После определения тегов, можно браться за реализацию универсального парсера.

Универсальный парсер

Как оказалось, технология LINQ в сочетании с некоторыми элементами функционального программирования (например, т.н. «функций высших порядков») как нельзя лучше подходит для решения задачи разбора текстов. Для разбора каждого конкретного вида тега используем обработчик (делегат), определяющий, является ли набор входных символов правильно сформированным тегом. Парсер или трансформер имеет набор обработчиков, вызываемых последовательно для проверки входного потока.
Общий алгоритм процедуры парсинга незамысловат:

1. Каждый входящий символ помещается в FIFO-очередь Queue(в качестве элемента может применяться как элемент входного файла char, так и ссылка на интерфейс ITag)
2. Каждый из обработчиков проверяет очередь на наличие определяемого тега - если тег обнаружен, обработчик возвращает тег и удаляет из «головы» очереди символы, относящиеся к обнаруженному тегу.
3. Повторяем процедуру до тех пор, пока во входном потоке есть символы и пока очередь не опустошится (используем дополнительный булевский признак, сигнализирующий о том, что символы во входном потоке закончились; если входной поток исчерпан, и ни один из обработчиков не распознал тег - сигнализируем об ошибке)

От теории - к практике:
public delegate ITag SequentalParserHandler(Queue Buffer, bool IsLast);

public class SequentalParser: IVersionedObject
{
    public string Name { get; private set; }
    public int[] Version { get; private set; }
    protected SequentalParserHandler[] Handlers;

protected ITag TryTags(Queue Buffer, bool IsLast)
    {
        if (Buffer.Count > 0)
        {
            return Handlers.Select(Handler => Handler(Buffer, IsLast)).FirstOrDefault(obj => obj != null);
        }
        else return null;
    }

protected IEnumerable Process(IEnumerable Source)
    {
        Queue Buffer = new Queue();
        IEnumerable Result = Source.Select(ch =>
        {
            Buffer.Enqueue(ch);
            return TryTags(Buffer, false);
        }
        );

foreach (ITag Tag in Result)
        {
            if (Tag != null) yield return Tag;
        }

if (Buffer.Count > 0)
        {
            ITag Tag;
            do
            {
                Tag = TryTags(Buffer, true);
                if (Tag != null) yield return Tag;
            } while (Tag != null && Buffer.Count > 0);
        }
        if (Buffer.Count > 0)
        {
            StringBuilder sb = new StringBuilder().AppendFormat("{0}: Can not parse input stream", Name);
            throw new Exception(sb.ToString());
        }
    }

public SequentalParser(string Name, int[] Version, IEnumerable> Handlers)
    {
        this.Name = Name;
        this.Version = Version;
        this.Handlers = Handlers.ToArray();
    }
    public SequentalParser(ObjVersion Version, IEnumerable> Handlers)
      : this(Version.Name, Version.Version, Handlers)
    {
    }
}

Осталось определить несколько обработчиков, реализующих разбор тегов:
// Определение тега "пустое место"
public static ITag Whitespace(Queue Buffer, bool IsLast)
{
    ITag Result = null;
    if (char.IsWhiteSpace(Buffer.Peek()))
    {
        int Count = Buffer.ToArray().TakeWhile(ch => char.IsWhiteSpace(ch)).Count();
        if (Count < Buffer.Count || IsLast)
        {
            StringBuilder sb = new StringBuilder();
            for (; Count > 0; Count--)
            {
                sb.Append(Buffer.Dequeue());
            }
            Result = new SimpleTag(Tags.StdNames.WhiteSpace, AutoGenCore.Version1, sb.ToString());
        }
    }
    return Result;
}

private static readonly HashSet DigitChars = new HashSet(new char[]{'-', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'});

// Определение тега "Целое число"
public static ITag Integer(Queue Buffer, bool IsLast)
{
    ITag Result = null;
    if ( DigitChars.Contains(Buffer.Peek()))
    {
        char[] Buf = Buffer.ToArray().TakeWhile(ch => !char.IsWhiteSpace(ch)).ToArray();
        int Count = Buf.Count();
        if (Count < Buffer.Count || IsLast)
        {
            string res = new string(Buf, 0, Count);
            int ires;
            if (int.TryParse(res, out ires))
            {
                Result = new SimpleTag(Tags.StdNames.Integer, AutoGenCore.Version1, ires);
                for (; Count > 0; Count--)
                {
                    Buffer.Dequeue();
                }
            }
        }
    }
    return Result;
}

Или, в общем случае:
// Применяем нечто из функционального программирования для получения "общих" обработчиков, годных для типичных сценариев разборки.

// IsStart - функция определения возможного тега по содержимому буфера
// IsNext - функция определения границ тега (возвращает true, если рассматриваемый символ принадлежит тегу)
// TagMaker - функция создания объекта-тега по его строковому представлению
public static SequentalParserHandler GenericHandler(Func IsStart, Func IsNext, Func TagMaker)
{
    return (Queue Buffer, bool IsLast) =>
    {
        ITag Result = null;
        char[] Buf = Buffer.ToArray();
        if (IsStart(new string(Buf), IsLast))
        {
            int Count = Buf.TakeWhile(ch => IsNext(ch, IsLast)).Count();
            if (Count < Buffer.Count() || IsLast)
            {
                StringBuilder sb = new StringBuilder();
                for (; Count > 0; Count--)
                {
                    sb.Append(Buffer.Dequeue());
                }
                Result = TagMaker(sb.ToString());
            }
        }
        return Result;
    };
}

// То же самое, но определение возможного тега производится по первому символу входного буфера
public static SequentalParserHandler GenericHandler(Func IsStart, Func IsNext, Func TagMaker)
{
    return GenericHandler(
        (chars, IsLast) => IsStart(chars[0], IsLast),
        IsNext,
        TagMaker
        );
}

// IsTag - функция определяющая тег
// CutRawTag - функция, выделяющая текстовое представление тега из входного потока
// TagMaker - функция создания объекта-тега по его строковому представлению
public static SequentalParserHandler GenericHandler(Func IsTag, Func CutRawTag, Func TagMaker)
{
    return (Buffer, IsLast) =>
    {
        ITag Result = null;
        string buf = new string(Buffer.ToArray());
        if (IsTag(buf, IsLast))
        {
            string RawTag = CutRawTag(buf);
            for (int i = RawTag.Length; i > 0; i--)
            {
                Buffer.Dequeue();
            }
            Result = TagMaker(RawTag);
        }
        return Result;
    };
}

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

Итого?

Вот так, «на коленке», используя технологию LINQ и вдохновляясь принципами функционального программирования, можно создавать парсеры неограниченной сложности. Развивая идею, можно прийти к созданию кросс-транслятора, создающего исходные тексты парсеров и генераторов, основанных на некоем «общем» описании их работы. Но всё это - вопрос времени, и уж точно, не вопрос для данной статьи. Надеюсь, что данная статья натолкнёт кого-либо на новые мысли и поможет сделать этот мир чуточку лучше :)

Искренне ваш.