2015-08-18

Este artículo proviene de un motor de traducción automática.

El trabajo programador

Creación de combinadores

Ted Neward En mi columna de diciembre (msdn.microsoft.com/magazine/hh580742), miré combinadores analizador, analizadores de texto que se crean combinando pequeños, atómica analizar funciones en funciones más grandes y quienes a su vez en funciones aún más grandes, aptos para analizar archivos de texto no trivial y arroyos. Se trata de una técnica interesante, uno que se construye sobre algunos conceptos básicos funcionales, y merece una exploración más profunda.

Los lectores de la columna anterior recordarán que el analizador construimos para manejar números de teléfono de U.S. estilo trabajados, pero la ejecución fue un poco... digamos... peculiar en lugares. En particular, la sintaxis para analizar combinaciones de tres y cuatro dígitos: bien, para ser honesto, lo clunked. Funcionó, pero apenas fue bonita, elegante o de cualquier manera escalable.

Como un repaso, aquí está el código de analizador de número de teléfono:

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

El tipo PhoneNumber es bastante guessable. Figura 1 muestra la threeNumberParser y fourNumberParser, que, en particular, son lo que "clunk" con toda la gracia de un pro fútbol defensivo liniero intentando ballet por primera vez en un escenario untado con grasa de pato.

Figura 1 desgarbados analizadores

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

Este es apenas el tipo de práctica de codificación inspirador que espero poder transmitir dentro de estas páginas. Hay una manera más elegante para construir estas, pero para describirlo, tenemos que bucear un poco más profundo en el funcionan de los combinadores de analizador. Y es el tema de la columna de este mes. No sólo porque necesitamos construir analizadores, cuenta que una forma más elegante, sino porque la técnica general ayuda a describir cómo funcionan y más importante, cómo se podría construir algo como esto en el futuro.

De funciones a funciones

El punto importante para darse cuenta acerca de combinadores analizador es que un analizador es realmente "sólo" una función: La función analiza el texto y, a continuación, puede transformar los caracteres en algo más. Lo que esa cosa resulta para ser es, por supuesto, hasta la persona aplicando el analizador. Podría ser un árbol de sintaxis abstracta (AST) para la validación y verificación del texto aprobado en (y posterior conversión en código ejecutable o quizás interpretados directamente, como en algunos idiomas), o podría ser un objeto de dominio simple, o incluso sólo valores enchufados a una clase existente, como un diccionario de pares nombre / valor.

Hablando en código, entonces, un analizador el siguiente aspecto:

T Parse<T>(string input);

En otras palabras, un analizador es una función genérica, tomando las cadenas y devolver una instancia de algo.

Tan simple como eso, sin embargo, no es exacta. Fueron la suma total de la historia, tenemos que volver a escribir un analizador completo por función, que no permite realmente mucho en la forma de reutilización. Pero si nos fijamos en el análisis de una serie de funciones: en otras palabras, un analizador se compone de un montón de analizadores poco, cada uno de ellos sabe cómo analizar sólo una pieza de la entrada y devolver sólo una pieza del objeto resultante: está claro que necesitamos volver no sólo el objeto resultante, sino también el resto del texto que requiere análisis. Y que significa la "T" de la declaración anterior tiene que hacerse un poco más complicado envolviendo en un tipo de "Resultado del analizador" que contiene "T" y una cadena con el resto de analizar el texto, así:

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

Y dado que C# naturalmente administra funciones como delegado de tipos e instancias, declarando un analizador ahora se convierte en una declaración de delegado:

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

Ahora, podemos imaginar escribiendo una serie de pequeños analizadores que saben analizar el texto en algunos útiles otro tipo, como un ParseFn <int> que toma una cadena y devuelve un valor int (véase figura 2), o un ParseFn <string> analiza hasta el primer carácter espacio en blanco y así sucesivamente.

Figura 2 analizar una cadena y devolver un valor 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);

Tenga en cuenta que la aplicación de analizador aquí es realmente que es bastante predecible: para escribir un analizador que analiza el texto hasta un carácter de espacio en blanco, lo único que tienes que hacer es cambiar la llamada IsDigit a una llamada de IsLetter. Esto grita para una refactorización para utilizar el predicado <T> Escriba para crear un analizador incluso más fundamental, pero que es una optimización que no tratamos aquí.

Esta aplicación es excelente para analizar cosillas como enteros y palabras sueltas, pero hasta ahora no parece como demasiado de una mejora sobre la versión anterior. Sin embargo, esto es más potente, porque puede combinar funciones creando funciones que toman funciones y devuelven funciones. Se denominan funciones de orden superior; Aunque la teoría está fuera del alcance de este artículo, mostrando cómo se aplican en este caso en particular no es. El punto de partida es al crear funciones que saben tomar dos funciones de intérprete y combinarlos en un booleano "AND" y moda "O":

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

Ambos son siempre como métodos de extensión en la ParseFn delegado tipo para permitir una "infijo" o "interfaz fluida" al estilo de codificación hacerlo más legible en el final, en la teoría de que "parserA.OR(parserB)" Lee mejor que "OR(parserA, parserB)."

De funciones a LINQ

Antes de que nos deja este conjunto de pequeños ejemplos, vamos a dar un paso más y crear tres métodos, como se muestra en figura 3, que esencialmente dará el analizador de la capacidad para enganchar en LINQ, para proporcionar una experiencia única al escribir el código (esta es una de las características del Sprache así). Las bibliotecas LINQ y sintaxis están en estrecha sincronización con uno y otro, en que la sintaxis LINQ ("de foo en barra seleccionar quux q …") está íntimamente ligada a la expectativa de que varias firmas de método están presentes y disponibles para su uso. Específicamente, si una clase proporciona la Select, SelectMany y donde se puede utilizar métodos y, a continuación, la sintaxis LINQ con ellos.

Figura 3 donde, Select y SelectMany métodos

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

Esto proporciona LINQ los métodos necesarios para analizar expresiones de LINQ, tales como lo vimos en el artículo anterior.

No quiero pasar por el ejercicio de la (re) diseñar una biblioteca de Combinador de analizador aquí; Luke Hoban y Brian McNamara tienen entradas de blog excelente sobre el tema (bit.ly/ctWfU0 y bit.ly/f2geNy, respectivamente), los cuales, yo debo señalar, sirven como el estándar contra el cual se está escribiendo esta columna. Sólo quiero demostrar el mecanismo por el cual estos tipos de analizadores se construyen en una biblioteca de Combinador de analizador como Sprache, debido a proporciona el núcleo de la solución al problema anterior de los analizadores de tres y cuatro dígitos en el analizador de número de teléfono. En resumen, necesitamos Combinador de un analizador que Lee exactamente tres dígitos y otro que dice exactamente cuatro dígitos.

Specifice

Dado que el problema es leer precisamente tres dígitos y precisamente cuatro dígitos, se sitúa a la razón que queremos una función que Lee exactamente ese número de caracteres de la secuencia de entrada. La biblioteca Sprache no darnos ese tipo de combinador — hay un combinador que leerá una secuencia repetida de cualquier tipo de personaje hasta que se queda sin que-tipo-de-personaje, sino que es un "cero a muchos" (de ahí su nombre, muchos) regla de producción, no una regla número específico de caracteres y por lo tanto inútil. Mirando su definición puede ser interesante y perspicaz, sin embargo, como figura 4 muestra.

Figura 4 definición de los muchos combinador

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 la mayoría de los desarrolladores, la parte más difícil de este método (y, de hecho, toda la biblioteca Sprache) es que el valor devuelto por esta función es una función — concretamente, un método lambda < (siempre un analizador > de alguna forma, recuerdo) que lleva la cadena y devuelve un IEnumerable <T> en su estructura de resultado; la carne del analizador real está enterrada dentro que devuelve la función, lo que significa que se ejecutará más adelante, no ahora. Esto es un largo camino desde simplemente devolver un T!

Una vez que se aborda esa rareza, el resto de la función es bastante claro: imperativamente, que paso a paso y llamar el analizador pasa en <T> para analizar lo que cada "sea"; y mientras el analizador mantiene regresar con éxito, nos seguimos bucles y sumando los resultados analizados a una lista de <T> Obtiene regresó cuando todo termine. Este sirve como plantilla para mi ampliación de la biblioteca, que llamaré dos veces por ahora, esencialmente ejecutar un analizador dado <T> dos veces (y dando un error si bien analizar falla), como se muestra en figura 5.

Figura 5 la función dos veces

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 hecho, mientras que habría sido un poco más fácil escribir este código por desenrollar el bucle de dos en dos conjuntos de instrucciones imperativas, recuerda, dos veces no específicamente lo que estamos buscando. Necesitamos Thrice y Quadrice, y esas son versiones simplemente extraordinario caso de dos veces, con "3" y "4" en lugar de "2" en el código, que suena como si podemos extraer en un único método que toma el número de veces para analizar. Opto por llamar a este método "Specifice", porque nos estamos analizando un número específico de veces (véase figura 6).

Figura 6 el 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);
  };
}

Por lo tanto, ahora hemos ampliado Sprache analizar exactamente "TC" número de analiza (caracteres, dígitos, cualquier tipo de analizador <T> pasamos en), que se abre Sprache para uso en escenarios de análisis de longitud fija, como el archivo de texto de registros de longitud fija ubicua, aka el archivo plano.

Un enfoque funcional

Sprache es una biblioteca de analizador para analizar los proyectos, para que las expresiones regulares son demasiado complejas de mediano tamaño y un auténtico generador (como ANTLR o lex/yacc) es excesiva. Es no es perfecto, en el que fallas de analizador generan mensajes de error que pueden ser difíciles de entender, pero una vez que ha llegado a través de las complejidades iniciales, Sprache puede ser una herramienta útil en su caja de herramientas de desarrollador.

Más que eso, sin embargo, Sprache demuestra algunas de la potencia y capacidad ofrecida por un enfoque diferente a la programación de lo que estamos acostumbrados, en este caso, desde el mundo funcional. Así que la próxima vez que alguien le pide, "lo bueno viene de aprender otros idiomas, si no vas a utilizarlos en el trabajo?" hay una respuesta fácil: "Incluso si no utiliza un lenguaje directamente, pueden enseñar técnicas e ideas que puede utilizar."

Pero eso es todo por ahora. El mes próximo, tomaremos una puñalada en algo totalmente diferente. Porque hay tanta concepto y teoría de la que audiencia de un columnista lenguaje puede tomar a la vez.

¡Feliz codificación!

Ted Neward es un consultor arquitectónico con Neudesic LLC. Ha escrito más de 100 artículos, es un orador C# MVP y INETA y ha autor y coautor de una docena de libros, incluyendo el recientemente lanzado al mercado "profesional F # 2.0" (Wrox). Consulta y mentores con regularidad. Llegar a él en ted@tedneward.com si estás interesado en lo que vienen a trabajar con su equipo, o lee su blog en blogs.tedneward.com.

Gracias al siguiente experto técnico para revisar este artículo: Nicholas Blumhardt

Compartir a través de