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

El trabajo programador

Combinadores analizadores

Ted Neward

Con la conclusión de la serie multiparadigmático, parecía tiempo aventurarse fuera en nuevos caminos. Como destino tendría, sin embargo, algunos trabajos de cliente recientemente me dejaron con material que lleva la discusión, se relaciona con el diseño de software, actúa como otro ejemplo del análisis de compatibilidad y variabilidad en el núcleo de la serie multiparadigmático, interesante y... bueno, al final, es simplemente genial.

El problema

El cliente que tengo es cuello profundo en el mundo científico neuro-óptico y frecuentes me para trabajar con él en un nuevo proyecto diseñado para facilitar la realización de experimentos en tejido óptico. En concreto, estoy trabajando en un sistema de software para controlar una plataforma de microscopio que impulsará diversos dispositivos de estímulo (LEDs, luces, etc.) que van a desencadenar respuestas desde la óptica tejido y luego capturar los resultados medidos por hardware viendo el tejido óptico.

Si todo suena vagamente matriz-y a usted, no estás completamente solo. Cuando primero oí hablar de este proyecto, mi reacción fue simultáneamente, "¡ Oh, wow, es genial!", y "Oh, espera, yo sólo vomitó en mi boca un poco."

En cualquier caso, una de las cosas fundamentales de la plataforma es que tendrá una configuración bastante compleja asociada con cada experimento ejecutar, y que nos llevó a contemplar cómo especificar esa configuración. Por un lado, parecía un problema obvio para un archivo XML. Sin embargo, la gente corriendo la plataforma no va a ser programadores, sino científicos y ayudantes de laboratorio, por lo que parecía un poco autoritaria a esperar que escribir los archivos XML con formato correcto (y hacerlo bien en cada turno). La idea de producir algún tipo de sistema de configuración basado en GUI nos golpeó como altamente sobrediseñada, particularmente como rápidamente convertiría en discusiones de la mejor manera de capturar a abiertas tipos de datos.

Al final, parece más apropiado para darles un formato de configuración personalizada, lo que significaba toneladas de analizar el texto de mi parte. (Para algunos, esto implicaría que estoy construyendo un DSL; Este es un debate mejor izquierda a filósofos y otras personas involucradas en la tarea grave del consumo de alcohol). Afortunadamente, soluciones abundan en este espacio.

Pensamientos

Un analizador sirve a dos propósitos útiles e interesantes: convertir texto en alguna forma de otro, más significativo y verificar validar el texto sigue una cierta estructura (que suele ser parte de ayudar a convertirlo en una forma más significativa). Así, por ejemplo, un número de teléfono, que es su corazón simplemente una secuencia de números, todavía tiene una estructura, que requiere verificación. Ese formato varía de un continente a otro, pero los números son todavía. De hecho, un número de teléfono es un gran ejemplo de un caso donde la "forma más significativa" no es un valor entero, las cifras no son un valor entero, son una representación simbólica que mejor suele ser representada como un tipo de dominio. (Tratarles como "justo" un número hacen difícil extraer el código de país o código de área, por ejemplo.)

Si un número de teléfono se compone de dígitos y también lo son los números (sueldos, ID de empleado, etc.) y, a continuación, va a ser alguna duplicación de código donde analizar y verificar los dígitos, salvo alguna manera extendemos un analizador. Esto implica, entonces, que nos gustaría cualquier analizador que construimos para ser abierta, permitiendo que alguien utilizando la biblioteca de analizador para extender en diferentes formas (códigos postales canadienses, por ejemplo) sin tener que modificar la propia fuente. Esto se conoce como el "principio de abierto-cerrado": entidades de Software debe estar abiertas para la extensión, pero cerrada para su modificación.

Solución: Generativa metaprogramación

Una solución es el enfoque tradicional "lex/yacc", conocido más formalmente como un "generador de analizador". Esto implica especificar la sintaxis del archivo de configuración en un formato abstracto — generalmente alguna variación en la Backus-Naur forman (BNF) sintaxis y gramática utilizada para describir la gramática formal, tales como qué uso de idiomas más programación — entonces ejecutando una herramienta para generar código para seleccionar la entrada de cadena aparte y dar como resultado algún tipo de árbol de estructuras u objetos. Generalmente, este proceso involucrado se divide en dos pasos, "léxico" y "análisis", en el que el lexer primero transforma la cadena de entrada en símbolos, validar que los personajes de hecho formar símbolos legítimos en el camino. Entonces el analizador toma los tokens y valida que los símbolos que aparecen en el orden adecuado y contengan los valores adecuados, y así sucesivamente, normalmente transformando los tokens en algunos tipo de resumen estructura de árbol para un análisis más detenido.

Los problemas con los generadores de analizador son los mismos para cualquier enfoque metaprogramación generativa: el código generado será necesario volver a generarse en el evento que cambia la sintaxis. Pero lo más importante para este tipo de escenario, el código generado será generada por computadora, con todo el maravilloso variable nombre que viene con el código generado por el equipo (alguien dispuesto a levantarse para variables como "integer431" y "cadena$ $x$ y$ z"?), por lo tanto difícil de depurar.

Solución: funcional

En un cierto tipo de luz, el análisis es fundamentalmente funcional: toma de entrada, realiza algún tipo de operación y genera como resultado. La visión crítica, que resulta, es que se puede crear un analizador de lotes de analizadores poco, cada uno de los cuales analiza un poco pequeño de la entrada de la cadena y, a continuación, devuelve un token y otra función a analizar la siguiente poco de entrada de la cadena. Estas técnicas, que creo que se introdujeron en Haskell, formalmente son conocidas como combinadores de analizador, y resultan para ser una solución elegante a "mediano" analizar problemas — analizadores que no son necesariamente tan complejos como requeriría un lenguaje de programación, pero algo más allá de lo que puede hacer String.Split (o una serie de arriba hackeado de exploraciones de regex).

En el caso de los combinadores de analizador, el requisito de abrir para extensión se logra crear funciones pequeñas y, a continuación, utilizando técnicas funcionales "combinarlas" en funciones más grandes (que es donde tenemos los "combinadores" de nombre). Analizadores más grandes pueden ser compuestos por alguien con suficiente habilidad para comprender la composición de la función. Esta técnica es un general que lleva a la exploración, pero ahorrará para una columna futura.

Pues resulta que, existen varias bibliotecas de Combinador de analizador para Microsoft.NET Framework, muchos de ellos basados en el módulo de Parsec escrito en Haskell que tipo de establece el estándar para el analizador de bibliotecas combinatorios. Dos de esas bibliotecas son FParsec, escrito por F # y Sprache, escrito en C#. Cada uno es abierto y relativamente bien documentadas, que sirven el doble propósito de ser tanto útil fuera de la caja y como un modelo para estudiar ideas de diseño. Te dejo FParsec para una columna futura.

"Sprache Sie análisis?"

Sprache, disponible en code.google.com/p/sprache, describe a sí mismo como una "simple y ligera biblioteca para construir analizadores directamente en código C#," que "no competir con bastidores de lenguaje 'fuerza industrial'. Encaja en algún lugar entre expresiones regulares y un conjunto completo de herramientas tales como ANTLR." (ANTLR es un generador, colocar en la categoría de metaprogramación generativa, como lex/yacc).

Getting started with Sprache es sencilla: Descargar el código, generar el proyecto, a continuación, copie el ensamblado Sprache.dll en el directorio de la dependencia de su proyecto y agregar la referencia al proyecto. Desde aquí, todo el trabajo de definición de analizador es hecho por declarar instancias Sprache.Parser y combinarlos en particulares formas de crear instancias de Sprache.Parser, que a su vez podrán, si lo desea (y normalmente es) devuelven objetos de dominio que contiene algunos o todos los valores analizados.

Sprache Simple

Para empezar, vamos a comenzar con un analizador que sabe cómo analizar los números de teléfono introducido por el usuario en un tipo de dominio PhoneNumber. Para mayor simplicidad, yo me quedo con el estilo de U.S. format—(nnn) nnn-nnnn — pero queremos específicamente reconocer la ruptura de los códigos de área y prefijo de línea y permiten letras en lugar de dígitos (por lo que alguien puede introducir su número de teléfono como "EAT (800)-NUTS" si desean). Idealmente, el tipo de dominio PhoneNumber convertirá entre alfa y numérico de todas formas en la demanda, pero esa funcionalidad se quedará como un ejercicio para el lector (es decir, esencialmente, que no quiero molestar con ella).

(El pedante me exige al señalar que no simplemente convertir todos los alphas a números es una solución totalmente compatible, por cierto. En la Universidad, fue común en mi círculo de amigos para intentar llegar a números de teléfono que cosas "cool", un ex-compañero todavía está esperando a 1-800-CTHULHU a ser libre, de hecho, por lo que puede ganar el juego para toda la eternidad.)

Es el lugar más fácil para comenzar con el tipo de dominio PhoneNumber:

class PhoneNumber
{
  public string AreaCode { get; set; }
  public string Prefix { get; set; }
  public string Line { get; set; }
}

Esto eran un tipo de dominio "real", el país, prefijo y línea tendría el código de validación en sus métodos de propiedad establecida, pero que llevaría a una repetición de código entre el analizador y la clase de dominio (que, por cierto, nosotros lo arreglamos antes de todo esto se realiza).

A continuación, necesitamos saber cómo crear un analizador simple que sabe cómo analizar n cantidad de dígitos:

public static Parser<string> numberParser =
  Parse.Digit.AtLeastOnce().Text();

Definición de la numberParser es sencillo. Comenzar con el analizador primitivo dígito (una instancia de un analizador <T> definido en la clase Sprache.Parse) y describir que queremos al menos un dígito en la secuencia de entrada, implícitamente consumir todos los dígitos hasta la secuencia de entrada o bien se ejecuta seco o un dígito no encuentra con el analizador. El método de texto convierte la secuencia de los resultados analizados en una única cadena para nuestro consumo.

Prueba de esto es bastante fácil, alimentan una cadena y 'er permiten extraer:

[TestMethod]
public void ParseANumber()
{
  string result = numberParser.Parse("101");
  Assert.AreEqual("101", result);
}
[TestMethod]
public void FailToParseANumberBecauseItHasTextInIt()
{
  string result = numberParser.TryParse("abc").ToString();
  Assert.IsTrue(result.StartsWith("Parsing failure"));
}

Cuando se ejecuta, este almacena "101" en el resultado. Si el método Parse es alimentado a una cadena de entrada "ABC", producirá una excepción. (Si se prefiere el comportamiento nonthrowing, Sprache también tiene un método TryParse que devuelve un objeto de resultado que puede ser interrogado en relación con el éxito o el fracaso).

La situación de análisis del número de teléfono es un poco más complicada, sin embargo; es necesario analizar sólo tres o cuatro dígitos, ni más, ni menos. La definición de un tal analizador (analizador de tres dígitos) es un poco más complicado, pero es aún factible:

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

El analizador numérico toma un personaje y, si es un dígito, avanza al siguiente carácter. El entonces método tiene una función (en forma de una expresión lambda) para ejecutar. El método de devolución recoge cada una de ellas en una sola cadena y, como su nombre lo implica, que utiliza como el valor devuelto (véase figura 1).

Figura 1 analizar un número de teléfono

[TestMethod]
public void ParseJustThreeNumbers()
{
  string result = threeNumberParser.Parse("123");
  Assert.AreEqual("123", result);
}
[TestMethod]
public void ParseJustThreeNumbersOutOfMore()
{
  string result = threeNumberParser.Parse("12345678");
  Assert.AreEqual("123", result);
}
[TestMethod]
public void FailToParseAThreeDigitNumberBecauseItIsTooShort()
{
  var result = threeNumberParser.TryParse("10");
  Assert.IsTrue(result.ToString().StartsWith("Parsing failure"));
}

Correcto. Hasta el momento. (Sí, la definición de threeNumberParser es torpe, seguramente tiene que haber una mejor manera de definir esto! No temáis: existe, pero para entender cómo extender el analizador, tenemos que bucear más profundo en cómo se construye Sprache, y que es el tema de la siguiente parte de esta serie.)

Ahora, sin embargo, tenemos que manejar el paréntesis izquierdo, el derecho -­parens y el guión y convertir todo en un objeto PhoneNumber. Puede parecer un poco torpe con lo que vemos hasta ahora, pero mira lo que sucede a continuación, como se muestra en figura 2.

Figura 2 convertir entrada en un objeto PhoneNumber

public static Parser<string> fourNumberParser =
  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())))));
public static Parser<string> areaCodeParser =
  (from number in threeNumberParser
  select number).
XOr(
  from lparens in Parse.Char('(')
  from number in threeNumberParser
  from rparens in Parse.Char(')')
  select number);
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});
Using the parser becomes pretty straightforward at this point:
[TestMethod]
public void ParseAFullPhoneNumberWithSomeWhitespace()
{
  var result = phoneParser.Parse("(425) 647-4526");
  Assert.AreEqual("425", result.AreaCode);
  Assert.AreEqual("647", result.Prefix);
  Assert.AreEqual("4526", result.Line);
}

Lo mejor de todo, el analizador es totalmente extensible, ya que, también, puede ser compuesta en un analizador más grande que transforma la entrada de texto en un objeto de dirección o ContactInfo objeto o cualquier otra cosa imaginable.

El concepto de combinatoria

Históricamente, el análisis de texto ha sido la provincia de "investigadores de lengua" y la academia, en gran medida debido al complicado y difícil editar-generar-compilación-prueba-depuración ciclo inherente con soluciones metaprogramación generativas. Tratando de caminar a través de equipo -­código generado — especialmente las versiones de finito base de máquina de Estado que producen muchos generadores de analizador — en un depurador es un desafío para desarrolladores incluso más hard-bitten. Por esa razón, la mayoría de los desarrolladores no pensar en soluciones a lo largo de las líneas cuando se presenta un problema basado en texto de análisis. Y, en verdad, la mayoría del tiempo, una solución basada en el generador de analizador sería excesivo drástica.

Combinadores de analizador servir como una buena solución intermedias: suficientemente flexible y lo suficientemente poderoso como para manejar algunos análisis no trivial, sin requerir un pH.d. en Ciencias de la computación para entender cómo usarlos. Incluso más interesante, el concepto de combinatoria es fascinante y conduce a algunas otras ideas interesantes, que algunas de las cuales explorará más adelante.

En el espíritu en el que nació esta columna, asegúrese de mantener un "ojo" fuera de mi próxima columna (lo siento, no podía resistir), en el que podrá extender Sprache sólo un toque, para reducir la fealdad de los analizadores de tres y cuatro dígitos definido aquí.

¡Feliz codificación!

Ted Neward es un consultor arquitectónico con Neudesic LLC. Ha escrito más de 100 artículos y autor o coautor de una docena de libros, incluyendo "Profesional F # 2.0" (Wrox, 2010). Es un MVP de C# y habla en conferencias alrededor del mundo. Él consulta y mentores regularmente — llegar a él en ted@tedneward.com o Ted.Neward@neudesic.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: Luke Hoban