Este artigo foi traduzido por máquina.
O trabalho programador
Combinadores de analisador
.jpg "Ted Neward")
Com a conclusão da série multiparadigmatic, pareceu-me tempo para aventure-se em novos caminhos. Como ele teria sorte, no entanto, alguns trabalhos de cliente recentemente me deixaram com interessante material que ostenta a discussão, prende-se com o design de software, atua como um outro exemplo da análise de variabilidade/aspectos comuns no núcleo da série multiparadigmatic, e … bem, no final, é apenas muito legal.
O problema
O cliente que eu tenho é pescoço de profundidade no mundo científico neuro-óptica e freqüentes me para trabalhar com ele em um projeto novo projetado para facilitar a realização de experimentos em tecido óptico. Especificamente, eu estou trabalhando em um sistema de software para controlar um rig de microscópio que irá conduzir a vários dispositivos de estímulo (LEDs, luzes e assim por diante) que irão desencadear respostas de tecido óptico e, em seguida, capture os resultados medidos por hardware assistindo o tecido óptico.
Se tudo parece vagamente Matrix-y para você, você não está totalmente sozinho. Quando ouvi pela primeira vez sobre este projeto, minha reação foi simultaneamente, "Oh, wow, que é legal!" e, "Oh, espera, eu só joguei na minha boca um pouco."
De qualquer forma, uma das coisas importantes sobre o rig é que ele terá uma configuração bastante complexa associada com cada experimento executado, e que levou-na contemplar como especificar essa configuração. Por um lado, pareceu-me um problema óbvio para um arquivo XML. No entanto, as pessoas que executam a plataforma não vão ser programadores de computador, mas os cientistas e assistentes de laboratório, assim pareceu um pouco pesada para esperar que eles gravar arquivos XML bem-formado (e fazer a coisa certa em cada volta). O pensamento de produzir algum tipo de sistema de configuração baseado em GUI surpreendeu-nos como altamente exageradas, particularmente como rapidamente se transformaria em discussões sobre a melhor forma de capturar open-ended tipos de dados.
No final, parecia mais apropriado dar-lhes um formato de configuração personalizada, que significava toneladas de análise de texto da minha parte. (Para alguns, isso implicaria que eu estou construindo uma DSL; Este é um debate melhor à esquerda para filósofos e outros envolvidos na tarefa grave de consumo de álcool). Felizmente, as soluções são abundantes neste espaço.
Pensamentos
Um analisador serve a dois propósitos úteis e interessantes: conversão de texto em alguma forma de outra, mais significativa e verificar/validar o texto seguem uma certa estrutura (que normalmente é parte de contribuir para convertê-lo em um formulário mais significativo). Assim, por exemplo, um número de telefone, que está em seu coração apenas uma seqüência de números, ainda tem uma estrutura que requer verificação. Esse formato varia de continente para continente, mas os números ainda são números. Na verdade, um número de telefone é um grande exemplo de um caso onde a "forma mais significativa" não é um valor inteiro — os dígitos não são um valor inteiro, eles são uma representação simbólica que geralmente é melhor representada como um tipo de domínio. (Tratá-los como "apenas" um número torna difícil extrair o código do país ou código de área, por exemplo.)
Se um número de telefone é composto de dígitos e assim são números (salários, identificações e assim por diante) e, em seguida, vai ser alguma duplicação no código onde podemos analisar e verificar dígitos, a menos que nós de alguma forma estender um analisador. Então, isso implica que gostaríamos que qualquer analisador criamos para ser aberto, permitindo que alguém usando a analisador/biblioteca para estendê-lo de diferentes maneiras (canadianas códigos postais, por exemplo) sem ter que modificar a própria fonte. Isso é conhecido como o "princípio aberto-fechado": entidades de Software deve ser abertas para extensão, mas fechado para modificação.
Solução: Generativo metaprogramação
Uma solução é a abordagem tradicional "lex/yacc", conhecida mais formalmente como um "gerador de analisador". Isso implica especificando a sintaxe do arquivo de configuração em um formato abstrato — formam usualmente alguma variação de Backus-Naur (BNF) sintaxe/gramática usada para descrever a gramática formal, tais como o uso de línguas mais programação — em seguida, executando uma ferramenta para gerar código para escolher a string de entrada distante e produzir algum tipo de árvore de estruturas ou objetos como resultado. Geralmente, esse processo envolvido é dividido em duas etapas, "léxico" e "análise", em que o analisador léxico primeiro transforma a Cadeia de caracteres de entrada em fichas, validar que os caracteres de fato formar legítimos símbolos ao longo do caminho. Em seguida, o analisador leva os tokens e valida que os tokens estão aparecendo na ordem apropriada e contêm os valores apropriados, e assim por diante, geralmente transformando os tokens em algum tipo de abstrair a estrutura de árvore para uma análise mais aprofundada.
Os problemas com os geradores de analisador são os mesmos para qualquer abordagem metaprogramação gerativa: O código gerado precisará ser regenerado no evento que a sintaxe é alterado. Mas mais importante para esse tipo de cenário, o código gerado será gerada por computador, com todos os o maravilhoso variável nomes que vem com o código gerado pelo computador (alguém pronto a levantar-se para variáveis tais como "integer431" e "string$ $x$ y$ z"?), assim, difícil de Depurar.
Solução: funcional
Em um certo tipo de luz, de análise é fundamentalmente funcional: ele toma a entrada, executa algum tipo de operação nele e produz saída como resultado. Uma visão crítica, ele gira para fora, é que é possível criar um analisador de lotes de analisadores pouco, cada qual analisa um pouquinho de entrada de Cadeia de caracteres, em seguida, retorna um token e outra função para analisar o próximo pouco de Cadeia de caracteres de entrada. Estas técnicas, que penso que foram introduzidas em Haskell, são formalmente conhecidas como combinadores analisador, e eles acabam por ser uma solução elegante para "midsize" análise de problemas — analisadores que não são necessariamente tão complexos como uma linguagem de programação exigiria, mas algo mais do que o que pode fazer Split (ou uma série de cima cortada de varreduras de regex).
No caso de combinadores analisador, a exigência de abrir para a extensão é conseguida criando funções pequenas e, em seguida, usando técnicas funcionais "combinar"-os em funções maiores (que é onde podemos obter os combinadores"nome"). Analisadores de maiores podem ser compostas por qualquer pessoa com habilidade suficiente para compreender a composição de funções. Essa técnica é uma geral que tem exploração, mas eu vou guardar que para uma próxima coluna.
Como se vê, existem várias bibliotecas de combinator analisador disponíveis para o Microsoft.NET Framework, muitos com base no módulo Parsec escrito em Haskell que tipo de definir o padrão para o analisador de bibliotecas combinatória. Duas dessas bibliotecas são FParsec, escrito para o F # e Sprache, escrito para c#. Cada um é open source e relativamente bem documentados, que servem o duplo objectivo de estado a ser útil fora da caixa e como um modelo do qual deseja estudar idéias de design. Eu também vou deixar FParsec para uma coluna futura.
"Sprache Sie análise"?
Sprache, disponível em code.google.com/p/sprache, descreve-se como uma "simple e leve biblioteca para a construção de analisadores diretamente no código c#," que "não compete com bancadas de linguagem 'força industrial'. Ele se encaixa em algum lugar entre as expressões regulares e um conjunto de ferramentas completo como o ANTLR." (ANTLR é um gerador de analisador, cabendo na categoria Generative metaprogramação, como lex/yacc).
Guia de introdução com Sprache é simples: Faça Download do código, compilar o projeto, em seguida, copiar o assembly Sprache.dll no diretório de dependência do seu projeto e adicionar a referência para o projeto. A partir daí, todos os trabalhos de definição do analisador é feito por declarar instâncias Sprache.Parser e combiná-los de maneiras específicas para criar instâncias de Sprache.Parser, que por sua vez pode, se desejar (e geralmente é), retornam objetos de domínio contendo alguns ou todos os valores analisados.
Sprache simples
Para começar, vamos começar com um analisador que sabe como analisar os números de telefone inserido pelo usuário em um tipo de domínio PhoneNumber. Para manter a simplicidade, eu vou ficar com o U.S.-estilo format—(nnn) nnn-nnnn — mas queremos especificamente reconhecer a repartição em códigos de área, prefixo e linha e permitir letras de dígitos (assim que alguém pode introduzir o seu número de telefone como "(800) EAT-NUTS" se desejarem). Idealmente, o tipo de domínio PhoneNumber irá converter entre alfa e numéricos de todos os formulários sob demanda, mas essa funcionalidade será deixada como um exercício para o leitor (que significa, essencialmente, que eu não quero incomodar-se com ele).
(Pedante em mim exige assinalar que não simplesmente converter todos as alfas para números é uma solução totalmente compatível, aliás. Na faculdade, era comum no meu círculo de amigos para tentar chegar a números de telefone que enunciados "cool" coisas — um ex-colega de quarto ainda está esperando para 1-800-CTHULHU para se tornar livre, na verdade, para que ele pode ganhar o jogo para toda a eternidade.)
O lugar mais fácil para começar é com o tipo de domínio PhoneNumber:
class PhoneNumber
{
public string AreaCode { get; set; }
public string Prefix { get; set; }
public string Line { get; set; }
}
Isso foi um tipo de domínio "real", CódigoDeÁrea, prefixo e linha teria código de validação em seus métodos de conjunto de propriedades, mas que levaria a uma repetição de código entre o analisador e a classe de domínio (que, aliás, vamos corrigir antes de tudo isso é feito).
Em seguida, precisamos saber como criar um analisador simple que sabe como analisar n número de dígitos:
public static Parser<string> numberParser =
Parse.Digit.AtLeastOnce().Text();
Definir o numberParser é simples. Começar com o analisador primitivo dígito (uma instância de um analisador de <T> definido na classe Sprache.Parse) e descrever o que nós queremos pelo menos um dígito no fluxo de entrada, implicitamente consumir todos os dígitos até o fluxo de entrada ou executa seco ou o analisador encontra um caractere não dígito. O método de texto converte o fluxo dos resultados analisados em uma única seqüência de caracteres para o nosso consumo.
Este teste é muito fácil — alimentá-lo uma Cadeia de caracteres e deixar er rip:
[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"));
}
Quando executado, armazena "101" em resultado. Se o método Parse é alimentado uma Cadeia de entrada de "abc", isso resultará em uma exceção. (Se o comportamento nonthrowing é preferido, Sprache também tem um método TryParse que retorna um objeto resultado que pode ser interrogado sobre o sucesso ou fracasso.)
A situação de análise do número de telefone é um pouco mais complicada, embora; ele precisa analisar apenas três ou quatro dígitos — nem mais, nem menos. A definição de um tal analisador (parser três dígitos) é um pouco mais complicado, mas ainda factível:
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()))));
O analisador numérico leva uma personagem e, se for um dígito, avança para o próximo caractere. O então método leva uma função (sob a forma de uma expressão lambda) para executar. O método de retorno coleta cada um em uma única seqüência de caracteres e, como seu nome implica, usa-os como o valor de retorno (consulte Figura 1).
Figura 1 um número de telefone de análise
[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"));
}
Sucesso. Até agora. (Sim, a definição de threeNumberParser é inábil — certamente tem que haver uma maneira melhor para definir isso! Não tenha medo: existe, mas para compreender como estender o analisador, temos de mergulhar mais fundo como Sprache é construído e que é o assunto da próxima parte desta série.)
Agora, no entanto, precisamos lidar com a esquerda-parens, direita -parens e o traço e converter tudo em um objeto PhoneNumber. Pode parecer um pouco estranho com o que podemos ver até agora, mas ver o que acontece em seguida, conforme mostrado na Figura 2.
Figura 2 da conversão de entrada em um 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);
}
O melhor de tudo, o analisador é totalmente extensível, porque ele, também, pode ser composto em um analisador maior que transforma a entrada de texto em um objeto de endereço ou objeto ContactInfo ou qualquer coisa senão imagináveis.
O conceito de análise combinatória
Historicamente, texto de análise tem sido a província de "investigadores de língua" e as universidades, em grande parte devido ao complicado e difícil editar-gerar-compile-teste-debug ciclo inerente com soluções metaprogramação gerativa. Tentando andar através de computador -gerado código — particularmente as finito-estado-máquina-versões com base em que muitos geradores de analisador churn para fora — em um depurador é um desafio para as mais hard-bitten do desenvolvedor. Por esse motivo, a maioria dos desenvolvedores não pensar em soluções ao longo de linhas quando apresentado com um problema com base em texto de análise. E, na verdade, na maioria das vezes, uma solução baseada em gerador de analisador seria um exagero drástico.
Combinadores de analisador servem como uma solução agradável no meio: suficientemente flexível e poderoso o suficiente para lidar com alguma análise não trivial, sem exigir um pH.d. em ciência da computação para entender como usá-los. Ainda mais interessante, o conceito de análise combinatória é um fascinante e leva a algumas outras idéias interessantes, que alguns dos quais vamos explorar mais tarde.
No espírito em que nasceu nesta coluna, certifique-se de manter um "olho" de minha próxima coluna (Desculpe, não poderia resistir), em que eu vou estender Sprache apenas um toque, para reduzir a feiúra os analisadores de três e quatro dígitos definida aqui.
Codificação feliz!
Ted Neward é um consultor arquitectónico com Neudesic LLC. Ele tem escrito mais de 100 artigos e foi autor ou co-autor de uma dúzia de livros, incluindo "Profissional F # 2.0" (Wrox, 2010). Ele é um MVP c# e dá palestras em conferências em todo o mundo. Ele consulta, mentores regularmente — contatá-lo em ted@tedneward.com ou Ted.Neward@neudesic.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: Luke Hoban