Artigo
08/18/2015

Este artigo foi traduzido por máquina.

O trabalho programador

Criando combinadores

Ted Neward
Na minha coluna de Dezembro (msdn.microsoft.com/magazine/hh580742), eu olhei combinadores analisador, analisadores de texto que são criados através da combinação de pequenas, atômica analisar funções em funções maiores e aqueles que, por sua vez em funções ainda maiores, adequadas para análise de arquivos de texto não-trivial e fluxos. Esta é uma técnica interessante, que se baseia em alguns conceitos funcionais do núcleo, e que merece a exploração mais profunda.

Os leitores da coluna anterior Lembre-se que o analisador que construímos para lidar com números de telefone do U.S.-estilo trabalhados, mas a implementação foi um pouco … digamos … peculiares em lugares. Em particular, a sintaxe para analisar combinações de três e quatro dígitos — bem, para ser honesto, ele clunked. Funcionou, mas ele quase não foi bonita, elegante ou em qualquer maneira escalonável.

Como um atualizador, aqui está o código do analisador de número de telefone:

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 });

O tipo PhoneNumber é bastante adivinháveis. Figura 1 mostra o threeNumberParser e fourNumberParser, que, em particular, são que "clunk" com a graça de uma bola de futebol defensiva pro atacante tentar balé pela primeira vez em um palco lubrificado com gordura de pato.

Figura 1 analisadores desajeitados

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())))));

Isso é quase o tipo de prática de codificação inspirador que espero poder transmitir nestas páginas. Há uma maneira mais elegante para construir estes, mas para descrevê-lo, precisamos aprofundar um pouco mais profundo em como funcionam combinadores analisador. E que é o assunto da coluna deste mês. Não só porque precisamos de uma maneira mais elegante para construir analisadores, você mente, mas porque a técnica geral ajuda a descrever como eles funcionam e mais importante, como você pode construir algo assim no futuro.

De funções para funções

O ponto importante perceber sobre combinadores analisador é que um analisador é realmente "apenas" uma função: A função analisa o texto e, em seguida, pode transformar os caracteres em outra coisa. O que essa outra coisa acaba por ser é, naturalmente, até à pessoa implementando o analisador. Poderia ser uma árvore sintática abstrata (AST) para validação e verificação do texto passado (e posterior conversão em código executável ou talvez interpretados diretamente, como em alguns idiomas), ou pode ser um objeto de domínio simples, ou mesmo apenas valores conectados a uma classe existente, como um dicionário de pares nome-valor.

Falando em código, em seguida, um analisador é semelhante ao seguinte:

T Parse<T>(string input);

Em outras palavras, um analisador é uma função genérica, tendo a seqüências de caracteres e retornar uma instância de algo.

Tão simples como isto é, porém, não é inteiramente exata. Foram que a soma total da história, seria voltar a escrever um analisador completo por função, que realmente não permite para muito em termos de reutilização. Mas se olharmos para analisar como uma série de funções — em outras palavras, um analisador é composto por um bando de analisadores de pouco, cada um deles sabe como processar apenas um pedaço da entrada e retornar apenas um pedaço do objeto resultante — é claro que precisamos de retorno não só o objeto resultante, mas também o texto restante que requer análise. E o que significa o "T" da declaração anterior tem que ser feito um pouco mais complicado enrolando-lo em um tipo de "Resultado analisador" contém "T" e uma Cadeia de caracteres com o restante analisar o texto, da seguinte forma:

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

E dado que c# naturalmente gerencia funções como delegar tipos e instâncias, declarar um analisador agora torna-se uma declaração delegate:

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

Agora, podemos imaginar escrever uma série de pequenas analisadores que sabe como analisar texto em alguns útil outro tipo, como um ParseFn <int> que recebe uma string e retorna um int (ver Figura 2), ou um ParseFn <string> que analisa até o primeiro caractere de espaço e assim por diante.

Figura 2 analisar uma seqüência de caracteres e retornar um Int

ParseFn<int> parseInt = delegate(string str)
{
  // Peel off just numbers
  int numCount = 0;
  foreach (char ch in str)
  {
    if (Char.IsDigit(ch))
      numCount++;
    else
      break;
  }
  // If the string contains no numbers, bail
  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);

Observe que a implementação do analisador aqui é realmente uma que é muito repetitivo: para escrever um analisador que analisa o texto acima para um caractere de espaço em branco, tudo o que você precisaria fazer é alterar a chamada IsDigit para uma chamada de IsLetter. Esta grita para uma refatoração para usar o predicado <T> Digite para criar um analisador ainda mais fundamental, mas que é uma otimização que não tentarmos aqui.

Essa implementação é ótimo para análise de pequenas coisas, como números inteiros e palavras isoladas, mas até agora ele não parece muito de uma melhoria sobre a versão anterior. Isso é mais poderoso, no entanto, porque você pode combinar funções através da criação de funções que usam funções e retornam funções. Estes são chamados de funções de ordem superior. enquanto a teoria está além do escopo deste artigo, mostrar como eles se aplicam neste caso específico não é. O ponto de partida é quando você cria funções que sabem tomar duas funções de analisador e combiná-los em um Boolean "AND" e moda "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);
  }
}

Estes dois são fornecidos como métodos de extensão sobre o ParseFn delegar tipo para permitir um "infixo" ou "interface fluent" estilo de codificação, para torná-lo mais legível no final, sobre a teoria de que "parserA.OR(parserB)" lê melhor do que "OR(parserA, parserB)."

De funções para LINQ

Antes de nós deixar este conjunto de pequenos exemplos, vamos dar mais um passo e criar três métodos, como mostrado na Figura 3, que essencialmente dará o analisador a capacidade de ligar para LINQ para fornecer uma experiência única ao escrever código (Esta é uma das características do Sprache também). As bibliotecas LINQ e sintaxe são em sincronia estreita com um outro, em que a sintaxe do LINQ ("de foo na barra Selecionar quux q...") está intimamente ligada à expectativa de que várias assinaturas de método estão presentes e disponíveis para uso. Especificamente, se uma classe fornece o Select, SelectMany e onde métodos e, em seguida, sintaxe LINQ pode ser usados com eles.

Figura 3 Where, Select e métodos de SelectMany

ParseFn<int> parseInt = delegate(string str)
  {
    // Peel off just numbers
    int numCount = 0;
    foreach (char ch in str)
    {
      if (Char.IsDigit(ch))
        numCount++;
      else
        break;
    }
    // If the string contains no numbers, bail
    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);
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);
     };
  }
}

Isso dá LINQ os métodos necessários para analisar expressões LINQ, tais como o que você viu no artigo anterior.

Eu não quero ir através do exercício de (re) criando uma biblioteca de analisador combinator aqui; Luke Hoban e Brian McNamara tem excelente blog posts sobre o assunto (bit.ly/ctWfU0 e bit.ly/f2geNy, respectivamente), que, eu deve assinalar, servir como padrão contra que esta coluna está sendo escrita. Eu apenas quero demonstrar o mecanismo pelo qual esses tipos de analisadores são construídos em uma biblioteca de combinator analisador como Sprache, porque que fornece o núcleo da solução para o problema anterior os analisadores de três e quatro dígitos no analisador de número de telefone. Em suma, precisamos combinator um analisador que lê exatamente três dígitos e outro que lê exatamente quatro dígitos.

Specifice

Dado que o problema é ler precisamente três dígitos e precisamente quatro dígitos, é lógico que queremos uma função que lê exatamente para esse número de caracteres do fluxo de entrada. A biblioteca Sprache não nos dar esse tipo de combinator — há um combinador que irá ler uma seqüência de repetição de qualquercoisa tipo de caractere até que se esgote que tipo-de-caracteres, mas que é um "zero-para-muitos" (daí seu nome, muitos) regra de produção, não uma regra número específico de caracteres e, portanto, inútil. Olhando para sua definição pode ser interessante e perspicaz, no entanto, como Figura 4 mostra.

Figura 4 definição de muitos Combinator

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);
  };
}

Para a maioria dos desenvolvedores, a parte mais difícil deste método (e, na verdade, toda a biblioteca Sprache) é que o valor de retorno desta função é uma função — especificamente, um método lambda < (sempre um analisador > de alguma forma, lembre-se) que leva a Cadeia de caracteres e retorna um IEnumerable <T> em sua estrutura de resultado; a carne do analisador real é enterrada dentro que retornou a função, o que significa que ele será executado depois, não agora. Este é um longo caminho de simplesmente retornar um T!

Uma vez que essa estranheza é tratada, o resto da função é bastante claro: imperativa, podemos percorrer e chamar o analisador passado em <T> para analisar cada "whatever"; e enquanto o analisador mantém retornar com êxito, devemos manter um loop e adicionando os resultados analisados para uma lista de <T> que obtém retornado quando tudo for concluída. Este serve como modelo para minha extensão para a biblioteca, que eu vou chamar duas vezes por agora, essencialmente executando um analisador determinado <T> duas vezes (e gerando um erro se quer analisar falha), como mostrado na Figura 5.

Figura 5 A funcionar duas vezes

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);
  };
}

De fato, enquanto teria sido um pouco mais fácil de escrever esse código pelo desenrolar-se o ciclo de dois em dois conjuntos de demonstrações imperativos, lembre-se, duas vezes é especificamente o que estamos procurando. Precisamos de Thrice e Quadrice, e esses são casos especiais apenas versões de duas vezes, com "3" e "4" em vez de "2" no código, que soa como se nós pode extraí-los em um único método que usa o número de vezes para analisar. Eu escolho chamar esse método "Specifice," porque nós estamos analisando um número específico de vezes (consulte Figura 6).

Figura 6 O método de 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);
  };
}

Assim, agora nós estendemos Sprache para analisar exatamente "ct" número de analisa (caracteres, dígitos, independentemente da sua natureza de analisador <T> passamos em), que abre Sprache para uso em cenários de análise de comprimento fixo, como o arquivo de texto de registro de comprimento fixo onipresente, também conhecido como o arquivo simples.

Uma abordagem funcional

Sprache é uma biblioteca de analisador para empresas de médio porte analisar projetos, para que as expressões regulares são demasiado complexas e um gerador de analisador full-blown (tais como ANTLR ou lex/yacc) é um exagero. É não é perfeito, em que falhas analisador geram mensagens de erro que podem ser difíceis de entender, mas uma vez que você tenha obtido através das complexidades iniciais, Sprache pode ser uma ferramenta útil na sua caixa de ferramentas do desenvolvedor.

Mais do que isso, porém, Sprache demonstra alguns do poder e capacidade oferecida por uma abordagem diferente para programação do que o que nós estamos habituados — neste caso, do mundo funcional. Para a próxima vez que alguém pergunta, "que bom vem de aprender sobre outras línguas se você não está indo para usá-los no trabalho?" não há uma resposta fácil: "Mesmo se você não estiver usando uma linguagem diretamente, ele pode te ensinar técnicas e idéias que você pode usar."

Mas isso é tudo por agora. No mês que vem, vamos dar uma facada em algo inteiramente diferente. Porque há somente tanto conceito e teoria da que audiência de um colunista língua pode ter ao mesmo tempo.

Codificação feliz!

Ted Neward é um consultor arquitectónico com Neudesic LLC. Ele escreveu mais de 100 artigos, é um MVP c# e INETA orador e tem o autor e co-autor de uma dúzia de livros, incluindo o recém-lançado "profissional F # 2.0" (Wrox). Ele consulta, mentores regularmente. Contatá-lo em ted@tedneward.com se você estiver interessado em ter-lhe vir trabalhar com sua equipe, ou ler seu blog em blogs.tedneward.com.

Graças ao seguinte especialista técnico para revisão deste artigo: Nicholas Blumhardt