Поделиться через

Работающий программист

Тэд Ньюард

Создание комбинаторов

Ted NewardВ прошлой статье (msdn.microsoft.com/magazine/hh580742) я рассмотрел комбинаторы синтаксических анализаторов (parser combinators), т. е. анализаторы текста, которые создаются комбинацией малых, атомарных функций разбора в более крупные функции, а те в свою очередь объединяются в еще более крупные функции, подходящие для синтаксического анализа нетривиальных текстовых файлов и потоков. Это интересная методика, опирающаяся на некоторые базовые концепции функционального программирования, и она заслуживает более глубокого изучения.

Те, кто читал прошлую статью, вспомнят, что мы конструировали синтаксический анализатор для обработки телефонных номер в формате, принятом в США; он работал, но реализация была местами… гм, весьма причудливой. В частности, синтаксис для разбора трех- или четырехзначных комбинаций, если честно, был очень громоздким. Реализация работала, но вряд ли ее можно было назвать элегантной, изящной или хотя бы масштабируемой.

В качестве напоминания вот как выглядел код синтаксического анализатора телефонных номеров:

public static Parser<PhoneNumber> phoneParser =
  (from areaCode in areaCodeParser
   from _1 in Parse.WhiteSpace.Many().Text()
   from prefix in threeNumberParser
   from _2 in (Parse.WhiteSpace.Many().Text()).
        Or(Parse.Char('-').Many())
   from line in fourNumberParser
   select new PhoneNumber() { AreaCode=areaCode,
     Prefix=prefix, Line=line });

Тип PhoneNumber довольно загадочен. На рис. 1 показаны threeNumberParser и fourNumberParser, которые особенно смахивают на профессионального футболиста, решившего попробовать себя в балете да еще на сцене, смазанной гусиным жиром.

Рис. 1. Неуклюжие синтаксическое анализаторы

public static Parser<string> threeNumParser =
  Parse.Numeric.Then(first =>
    Parse.Numeric.Then(second =>
      Parse.Numeric.Then(third =>
        Parse.Return("" + first.ToString() +
          second.ToString() + third.ToString()))));
public static Parser<string> fourNumParser =
  Parse.Numeric.Then(first =>
    Parse.Numeric.Then(second =>
      Parse.Numeric.Then(third =>
        Parse.Numeric.Then(fourth =>
          Parse.Return("" + first.ToString() +
            second.ToString() + third.ToString() +
            fourth.ToString())))));

Вряд ли это можно отнести к воодушевляющей практике кодирования, которую, как я надеюсь, всегда старался доносить до вас на этих страницах. Есть более элегантный способ конструирования анализаторов, но, прежде чем описывать его, нам придется поглубже копнуть, как работают комбинаторы синтаксических анализаторов. И это будет темой сегодняшней статьи. Не только потому, что нужен более элегантный способ конструирования синтаксических анализаторов (хотя он, конечно, нужен), но и потому, что универсальная методика помогает описать, как они работают и, что еще важнее, как можно было бы сконструировать нечто в таком духе в будущем.

От функций к функциям

Важная особенность синтаксических анализаторов, которую следует понимать, заключается в том, что такой анализатор на самом деле является «просто» функцией: функция разбирает текст и может преобразовывать символы в нечто другое. Во что именно, зависит, разумеется, от того, кто реализует этот анализатор. Это могло бы быть дерево абстрактного синтаксиса (abstract syntax tree, AST) для проверки на соответствие и верификации переданного текста (и последующего преобразования в исполняемый код или, возможно, прямой интерпретации, как в некоторых языках), простой объект предметной области или даже значения, включаемые в некий существующий класс, подобный словарю с парами «имя-значение».

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

T Parse<T>(string input);

Иначе говоря, синтаксический анализатор — это обобщенная функция, которая принимает строки и возвращает экземпляр чего-либо.

Как бы просто это ни звучало, это все же не совсем точно. Если бы это было так, мы вновь вернулись бы к написанию полного анализатора в каждой функции, что не слишком способствует повторному использованию. Но если мы будем рассматривать разбор как серию вызовов функций (т. е. полный анализатор состоит из набора небольших анализаторов, каждый из которых умеет обрабатывать только свою часть ввода и возвращать лишь часть конечного объекта), то очевидно, что нам понадобилось бы возвращать не только часть конечного объекта, но и оставшийся, еще не разобранный текст. А это означает, что «T» из предыдущего объявления нужно сделать несколько сложнее, обернув его в тип «Parser Result», который содержит как «T», так и строку с оставшимся текстом, например:

public class ParseResult<T>
{
  public readonly T Result;
  public readonly string Rest;
  public ParseResult(T r, string i) {
    this.Result = r; this.Rest = i;
  }
}

А учитывая, что C# естественным образом обрабатывает функции как типы и экземпляры делегатов, объявление синтаксического анализатора теперь становится объявлением делегата:

public delegate ParseResult<T> ParseFn<T>(string input);

После этого можно представить написании серии небольших анализаторов, которым известно, как разбирать текст на некие другие полезные типы, например ParseFn<int>, принимающий строку и возвращающий int (рис. 2), или ParseFn<string>, выполняющий разбор до первого неотображаемого символа (whitespace character), и т. д.

Рис. 2. Разбор строки и возврат int

 

ParseFn<int> parseInt = delegate(string str)
  {
    // Выдираем только числа
    int numCount = 0;
    foreach (char ch in str)
    {
      if (Char.IsDigit(ch))
        numCount++;
      else
        break;
    }

    // Если в строке нет чисел, выходим
    if (numCount == 0)
        return null;
    else
    {
      string toBeParsed = str.Substring(0, numCount);
      return new ParseResult<int>(
        Int32.Parse(toBeParsed), str.Substring(numCount));
    }
  };
Assert.AreEqual(12, parseInt("12").Result);

Заметьте, что эта реализация анализатора на самом деле весьма «многословна»: чтобы написать анализатор, разбирающий текст вплоть до неотображаемого символа, достаточно заменить вызов IsDigit на вызов IsLetter. Здесь напрашивается рефакторинг, чтобы использовать тип Predicate<T> для создания еще более фундаментального анализатора, но это относится к оптимизации, которая в этой статье не рассматривается.

Эта реализация хороша для разбора чего-то небольшого вроде целых чисел или отдельных слов, но пока что не кажется особым улучшением по сравнению с предыдущей версией. Однако она эффективнее, так как вы можете комбинировать функции, создавая функции, которые принимают и возвращают функции. Это так называемые функции высшего порядка (higher-order functions); хотя теория, связанная с такими функциями, выходит за рамки тематики этой статьи, показать, как они применяются в данном конкретном случае, мне ничто не мешает. Начинать следует с создания функции, которой известно, как принять две функции-анализатора и объединить их в стиле булевой операции AND и OR:

public static class ParseFnExtensions
{
  public static ParseFn<T> OR<T>(this ParseFn<T> parser1,
    ParseFn<T> parser2)
  {
    return input => parser1(input) ?? parser2(input);
  }
  public static ParseFn<T2> AND<T1, T2>(this ParseFn<T1> p1,
    ParseFn<T2> p2)
  {
    return input => p2(p1(input).Rest);
  }
}

Обе эти функции предоставляются как методы расширения в типе делегата ParseFn для поддержки кодирования с использованием нефиксированных, или текучих, интерфейсов, что в конечном счете оказывается более удобочитаемым — если вы, конечно, согласны, что parserA.OR(parserB) понятнее, чем OR(parserA, parserB).

От функций к LINQ

Прежде чем оставить в покое этот набор небольших примеров, давайте сделаем еще один шаг и создадим три метода (рис. 3), которые, по сути, позволят синтаксическому анализатору использовать LINQ; это даст нам уникальные возможности при написании кода (кстати, поддержка LINQ является одной из функций Sprache). Библиотеки и синтаксис LINQ тесно связаны друг с другом в том плане, что синтаксис LINQ («from foo in bar select quux q…») неотделим от ожиданий того, что будет присутствовать несколько сигнатур методов и их можно будет использовать. Конкретнее, если некий класс предоставляет методы Select, SelectMany и Where, то для них можно использовать синтаксис LINQ.

Рис. 3. Методы Where, Select и SelectMany

public static class ParseFnExtensions {
  public static ParseFn<T> Where<T>(
    this ParseFn<T> parser,
    Func<T, bool> pred)
  {
    return input => {
      var res = parser(input);
      if (res == null || !pred(res.Result)) return null;
      return res;
     };
  }
  public static ParseFn<T2> Select<T, T2>(
    this ParseFn<T> parser,
    Func<T, T2> selector)
  {
    return input => {
      var res = parser(input);
      if (res == null) return null;
      return new ParseResult<T2>(selector(
        res.Result),res.Rest);
     };
  }
  public static ParseFn<T2> SelectMany<T, TIntermediate, T2>(
    this ParseFn<T> parser,
    Func<T, ParseFn<TIntermediate>> selector,
    Func<T, TIntermediate, T2> projector)
  {
    return input => {
      var res = parser(input);
      if (res == null) return null;
      var val = res.Result;
      var res2 = selector(val)(res.Rest);
      if (res2 == null) return null;
      return new ParseResult<T2>(projector(
        val, res2.Result),res2.Rest);
    };
  }
}

Это дает LINQ необходимые методы для разбора LINQ-выражений наподобие тех, которые мы рассматривали в предыдущей статье.

У меня нет желания заниматься упражнениями в перепроектировании библиотеки комбинаторов синтаксических анализаторов; на эту тему Люк Хобан (Luke Hoban) и Брайен Макнамара (Brian McNamara) опубликовали в блогах отличные статьи (bit.ly/ctWfU0 и bit.ly/f2geNy соответственно), и эти статьи — я обязан это отметить — служат стандартом для меня при написании статей в этой рубрике. Я лишь хочу продемонстрировать механизм, посредством которого эти виды анализаторов конструируются в библиотеку анализаторов вроде Sprache, потому что он является основой решения изначальной проблемы с анализаторами трех- и четырехзначных кодов в анализаторе телефонных номеров. Если в двух словах, то нам нужен один комбинатор анализаторов, который читает строго три цифры, и один, который читает четыре.

Метод Specifice

Учитывая, что задача заключается в чтении точно трех разрядов и точно четырех, есть смысл в функции, которая считывает именно это количество цифр из потока ввода. Библиотека Sprache не дает нам готового комбинатора такого рода — есть комбинатор, который будет читать повторяющуюся последовательность каких угодно символов, пока эти символы не закончатся, но это правило «ноль ко многим» (отсюда и название — Many), а не правило определенного количества символов, поэтому данный комбинатор нам не поможет. Тем не менее, посмотреть на его определение и интересно, и поучительно (рис. 4).

Рис. 4. Определение комбинатора Many

public static Parser<IEnumerable<T>> Many<T>(
  this Parser<T> parser)
{
  if (parser == null)
    throw new ArgumentNullException("parser");

  return i =>
  {
    var remainder = i;
    var result = new List<T>();
    var r = parser(i);
    while (r is ISuccess<T>)
    {
      var s = r as ISuccess<T>;
      if (remainder == s.Remainder)
          break;

      result.Add(s.Result);
      remainder = s.Remainder;
      r = parser(remainder);
    }

    return new Success<IEnumerable<T>>(result, remainder);
  };
}

Для большинства разработчиков самая трудная часть этого метода (и на самом деле всей библиотеки Sprache) заключается в том, что эта функция возвращает функцию — точнее, лямбда-метод (всегда Parser<> чего-либо), который принимает строку и возвращает IEnumerable<T> в структуре своего результата; суть самого анализатора спрятана в этой возвращаемой функции, и подразумевается, что она будет выполнена позднее — не сейчас. Это далеко не простой возврат T!

Когда вы поймете эту причудливость, остальная часть функции будет достаточно ясной: мы движемся шаг за шагом и вызываем переданный Parser<T> для синтаксического анализа каждого «что бы то ни было»; и пока анализатор успешно возвращает результаты, мы продолжаем цикл и добавляем разобранные результаты в List<T>, который возвращается по завершении всей работы. Это послужило шаблоном для моего расширения библиотеки, которое я пока назову Twice (рис. 5), потому что оно в основном занимается тем, что дважды выполняет данный Parser<T> (и возвращает ошибку, если любая из операций разбора заканчивается неудачей).

Рис. 5. Функция Twice

public static Parser<IEnumerable<T>> Twice<T>(
  this Parser<T> parser)
{
  if (parser == null)
    throw new ArgumentNullException("parser");

  return i =>
  {
    var remainder = i;
    var result = new List<T>();
    var r = parser(i);
    var c = 0;
    while (c < 2 && r is ISuccess<T>)
    {
      var s = r as ISuccess<T>;
      if (remainder == s.Remainder)
          break;

      result.Add(s.Result);
      remainder = s.Remainder;
      r = parser(remainder);

      c++;
    }

    return new Success<IEnumerable<T>>(result, remainder);
  };
}

Хотя писать этот код было бы немного легче, преобразовав цикл с двумя итерациями в два набора императивных выражений, не забывайте, что Twice не предназначена именно для того, к чему мы стремимся. Нам нужны Thrice и Quadrice, и они являются просто особыми случаями Twice с цифрами 3 и 4 в коде вместо 2, а это намекает на то, что мы соберем все версии в один метод, который будет принимать значение, определяющее количество операций разбора. Я предпочел назвать этот метод «Specifice», потому что мы выполняем заданное число операций разбора (рис. 6).

Рис. 6. Метод Specifice

public static Parser<IEnumerable<T>> Twice<T>(
  this Parser<T> parser) {
  return Specifice(parser, 2); }
public static Parser<IEnumerable<T>> Thrice<T>(
  this Parser<T> parser) {
  return Specifice(parser, 3); }
public static Parser<IEnumerable<T>> Quadrice<T>(
  this Parser<T> parser) {
  return Specifice(parser, 4);
}
public static Parser<IEnumerable<T>> Quince<T>(
  this Parser<T> parser) {
  return Specifice(parser, 5);
}
public static Parser<IEnumerable<T>> Specifice<T>(
  this Parser<T> parser, int ct)
{
  if (parser == null)
    throw new ArgumentNullException("parser");

  return i =>
  {
    var remainder = i;
    var result = new List<T>();
    var r = parser(i);
    var c = 0;
    while (c < ct && r is ISuccess<T>)
    {
      var s = r as ISuccess<T>;
      if (remainder == s.Remainder)
          break;

      result.Add(s.Result);
      remainder = s.Remainder;
      r = parser(remainder);

      c++;
    }

    return new Success<IEnumerable<T>>(result, remainder);
  };
}

Таким образом, мы теперь расширили Sprache так, чтобы она могла выполнять ровно «ct» число операций разбора (символов, цифр или любых переданных Parser<T>). Это открывает возможность применения Sprache в сценариях, где необходим синтаксический разбор последовательности фиксированной длины, например распространенных текстовых файлов с записями определенной длины, т. е. плоских файлов.

Функциональный подход

Sprache — библиотека синтаксических анализаторов для проектов среднего масштаба, для которых регулярные выражения слишком сложны, а полноценный генератор анализаторов (вроде ANTLR или lex/yacc) — это уже перебор. Она не идеальна в том плане, что при неудаче анализатор генерирует не слишком внятные сообщения об ошибках, но, как только вы пройдете через начальный этап ее освоения, Sprache может оказаться полезным дополнением в вашем арсенале средств разработки.

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

Но на сегодня все. В следующий раз мы попробуем свои силы в чем-нибудь принципиально другом.

Удачи в кодировании!                                                        

Тэд Ньюард (Ted Neward) — консультант по архитектуре в компании Neudesic LLC. Автор и соавтор многочисленных книг, в том числе «Professional F# 2.0» (Wrox, 2010), более сотни статей, часто выступает на многих конференциях по всему миру; кроме того, имеет звание Microsoft MVP в области C#. С ним можно связаться по адресу ted@tedneward.com или blogs.tedneward.com, если вы заинтересованы в сотрудничестве с его группой. Также читайте его блог blogs.tedneward.com.

Выражаю благодарность за рецензирование статьи эксперту Николасу Блюмхардту (Nicholas Blumhardt).