Exemplo reduzido de expressão regular convertido em uma máquina de estado?
https://stackoverflow.com/questions/525004
-
22-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
No Stack Overflow Podcast # 36 ( http://blog.stackoverflow.com/2009/01/ Podcast-36 / ), esta opinião foi expressa: Depois de entender como é fácil de configurar uma máquina de estado, você nunca vai tentar usar uma expressão regular de forma inadequada nunca mais.
Eu fiz um monte de pesquisa. Eu encontrei alguns trabalhos acadêmicos e outros exemplos complicados, mas eu gostaria de encontrar um exemplo simples que iria me ajudar a entender esse processo. Eu uso um monte de expressões regulares, e eu gostaria de ter certeza que eu nunca use um "inapropriadamente" nunca mais.
Solução
Claro que, embora você precisará exemplos mais complicados para compreender verdadeiramente como REs trabalho. Considere o seguinte RE:
^[A-Za-z][A-Za-z0-9_]*$
que é um identificador comum (deve começar com alfa e pode ter qualquer número de caracteres alfanuméricos e undescore seguinte, incluindo nenhum). O seguinte mostra pseudo-código como isso pode ser feito com uma máquina de estado finito:
state = FIRSTCHAR
for char in all_chars_in(string):
if state == FIRSTCHAR:
if char is not in the set "A-Z" or "a-z":
error "Invalid first character"
state = SUBSEQUENTCHARS
next char
if state == SUBSEQUENTCHARS:
if char is not in the set "A-Z" or "a-z" or "0-9" or "_":
error "Invalid subsequent character"
state = SUBSEQUENTCHARS
next char
Agora, como eu disse, este é um exemplo muito simples. Ele não mostra como fazer jogos gananciosos / não greedy, retrocesso, correspondência dentro de uma linha (em vez de toda a linha) e outros recursos mais esotéricos de máquinas de estado que são facilmente manipulados pela sintaxe RE.
É por isso que REs são tão poderosos. O código de máquina de estado finito real necessário para fazer o que a RE one-liner pode fazer é geralmente muito longo e complexo.
A melhor coisa que você poderia fazer é pegar uma cópia de algum código lex / yacc (ou equivalente) para uma linguagem simples específico e ver o código que gera. Não é bonito (ele não tem que ser uma vez que não é suposto ser lido por seres humanos, eles deveriam estar olhando para a lex / yacc código), mas pode dar-lhe uma idéia melhor de como eles funcionam.
Outras dicas
A forma bastante conveniente de ajuda olhar para este a bandeira conhecida-pouco uso de python re.DEBUG em qualquer padrão:
>>> re.compile(r'<([A-Z][A-Z0-9]*)\b[^>]*>(.*?)</\1>', re.DEBUG)
literal 60
subpattern 1
in
range (65, 90)
max_repeat 0 65535
in
range (65, 90)
range (48, 57)
at at_boundary
max_repeat 0 65535
not_literal 62
literal 62
subpattern 2
min_repeat 0 65535
any None
literal 60
literal 47
groupref 1
literal 62
Os números após 'gama' 'literal' e referem-se aos valores inteiros dos caracteres ASCII que supostamente para corresponder.
Faça o seu próprio na mosca!
http: //osteele.com/tools/reanimator/ ???
Esta é uma ferramenta em conjunto realmente muito bem colocado que visualiza expressões regulares como FSMs. Ele não tem suporte para alguns dos a sintaxe que você vai encontrar em motores de expressão regular do mundo real, mas certamente o suficiente para entender exatamente o que está acontecendo.
É a pergunta "Como faço para escolher os estados e as condições de transição?", Ou "Como posso implementar a minha máquina de estado abstrato em Foo?"
Como faço para escolher os estados e as condições de transição?
Eu costumo usar FSMs para problemas bastante simples e escolhê-los intuitivamente. Em minha resposta a outra pergunta sobre expressões regulares , eu só olhei para o problema de análise como uma das sendo ou Inside ou outside um par de tags, e escreveu as transições de lá (com um início e fim do estado para manter a implementação limpo).
Como posso implementar a minha máquina de estado abstrato em Foo?
Se o seu idioma implementação suporta uma estrutura como declaração c de switch, em seguida, ligar o estado atual e processar a entrada para ver qual ação e / ou de transição também realizar seguinte.
Sem switch-like estruturas, ou se eles são deficientes, de alguma forma, você if ramificação estilo. Ugh.
Escrito em um só lugar em c o exemplo que eu ligada seria algo parecido com isto:
token_t token;
state_t state=BEGIN_STATE;
do {
switch ( state.getValue() ) {
case BEGIN_STATE;
state=OUT_STATE;
break;
case OUT_STATE:
switch ( token.getValue() ) {
case CODE_TOKEN:
state = IN_STATE;
output(token.string());
break;
case NEWLINE_TOKEN;
output("<break>");
output(token.string());
break;
...
}
break;
...
}
} while (state != END_STATE);
o que é bastante confuso, por isso eu costumo rasgar os casos state para funções distintas.
Eu tenho certeza que alguém tem melhores exemplos, mas você poderia verificar este post por Phil Haack , que tem um exemplo de uma expressão regular e uma máquina de estado fazendo a mesma coisa (há um post anterior com alguns exemplos mais regex lá também eu acho ..)
Verifique a "HenriFormatter" nessa página.
Eu não sei o que trabalhos acadêmicos você já leu, mas ele realmente não é tão difícil de entender como implementar uma máquina de estado finito. Há um pouco de matemática interessantes, mas a ideia é realmente muito trivial para entender. A maneira mais fácil de entender um FSM é através de entrada e saída (na verdade, este compreende a maior parte da definição formal, que eu não vou descrever aqui). Um "estado" é, essencialmente, apenas descrevem um conjunto de entradas e saídas que tenham ocorrido e pode ocorrer a partir de um certo ponto.
máquinas de estados finitos são mais fáceis de entender através de diagramas. Por exemplo:
alt texto http://img6.imageshack.us/img6/7571/mathfinitestatemachinedco3 .gif
Tudo isso está dizendo é que se você começar em algum q0 estado (aquele com o símbolo Iniciar ao lado) você pode ir para outros estados. Cada estado é um círculo. Cada seta representa uma entrada ou saída (dependendo de como você olha para ele). Outra maneira de pensar de uma máquina de estados finitos é em termos de entrada "válida" ou "aceitável". Há certas cadeias de saída que não são possíveis certas máquinas de estados finitos; isso permitiria que você a expressões "jogo".
Agora, suponha que você começa na q0. Agora, se você uma entrada de 0 você vai para o Q1 estado. No entanto, se você uma entrada de 1 irá para o Q2 estado. Você pode ver isso pelos símbolos acima das setas de entrada / saída.
Digamos que você começar em q0 e obter esta entrada
0, 1, 0, 1, 1, 1
Isto significa que passaram por estados (sem entrada para q0, você acabou de começar lá):
q0 -> Q1 -> q0 -> Q1 -> q0 -> q2 -> Q3 -> Q3
Traço a imagem com o dedo se não faz sentido. Observe que q3 volta para si próprio para as duas entradas 0 e 1.
Outra maneira de dizer tudo isso é "Se você estiver em q0 estado e você vê um 0 Vai para o Q1, mas se você ver um 1 Vá para Q2." Se você fizer essas condições para cada estado que você está quase pronto definir sua máquina de estado. Tudo que você tem a fazer é ter uma variável de estado e, em seguida, uma maneira de bombear entrada e que é basicamente o que está lá.
Ok, então por que isso é importante sobre a declaração de Joel? Bem, construindo a "única verdadeira expressão regular para governá-los todos" pode ser muito difícil e também difícil manter modificar ou até mesmo para os outros para voltar e entender. Além disso, em alguns casos, é mais eficiente.
Claro, máquinas de estado tem muitos outros usos. Espero que isso ajude de alguma maneira. Note, eu não me incomodei de ir para a teoria, mas existem algumas provas interessantes sobre FSMs.
