Quelle est la méthode Pythonic pour implémenter un FSM simple?

Question

Hier, j'ai dû analyser un fichier de données binaires très simple - la règle est de chercher deux octets dans une rangée qui sont tous les deux 0xAA, alors l'octet suivant sera un octet de longueur, puis sauter 9 octets données à partir de là. Répétez jusqu'à la fin du fichier.

Ma solution a fonctionné, et a été très rapide à mettre en place (même si je suis un programmeur C dans l'âme, je pense toujours qu'il était plus rapide pour moi d'écrire ceci en Python qu'en C) - MAIS , il est clairement pas du tout Pythonic et il se lit comme un programme C (et pas un très bon à cela!)

Quelle serait une meilleure approche de Pythonic? Est-ce qu'un simple FSM comme ça est encore le bon choix en Python?

Ma solution:

#! /usr/bin/python 

import sys 

f = open(sys.argv[1], "rb") 

state = 0 

if f: 
    for byte in f.read(): 
     a = ord(byte)  
     if state == 0: 
      if a == 0xAA: 
       state = 1 
     elif state == 1: 
      if a == 0xAA: 
       state = 2 
      else: 
       state = 0 
     elif state == 2: 
      count = a; 
      skip = 9 
      state = 3 
     elif state == 3: 
      skip = skip -1 
      if skip == 0: 
       state = 4 
     elif state == 4: 
      print "%02x" %a 
      count = count -1 
      if count == 0: 
       state = 0 
       print "\r\n" 

Answer 1

Vous pouvez attribuer des noms constants à vos états au lieu d'utiliser 0, 1, 2, etc. pour améliorer la lisibilité.

Vous pouvez utiliser un dictionnaire pour mapper (current_state, input) -> (next_state), mais cela ne vous permet pas vraiment d'effectuer d'autres traitements pendant les transitions. Sauf si vous incluez également une "fonction de transition" pour effectuer un traitement supplémentaire.

Ou vous pourriez faire une approche non-FSM. Je pense que cela fonctionnera tant que 0xAA 0xAA apparaît seulement quand il indique un "début" (n'apparaît pas dans les données).

with open(sys.argv[1], 'rb') as f: 
    contents = f.read() 
    for chunk in contents.split('\xaa\xaa')[1:]: 
     length = ord(chunk[0]) 
     data = chunk[10:10+length] 
     print data 

Si elle apparaît dans les données, vous pouvez utiliser à la place string.find('\xaa\xaa', start) pour parcourir la chaîne, définissant l'argument start pour commencer à regarder où le dernier bloc de données est terminée. Répétez jusqu'à ce qu'il renvoie -1.

Answer 2

Je pense que votre solution semble bien, sauf que vous devez remplacer count = count - 1 avec count -= 1.

C'est l'une de ces périodes où les démonstrations de code sophistiquées trouveront des façons de faire correspondre les états aux callables, avec une petite fonction de driver, mais ce n'est pas mieux, juste plus fantaisiste et utilisant un langage plus obscur. fonctionnalités.

Answer 3

La manière la plus cool que j'ai vu pour implémenter des FSM en Python doit être via des générateurs et des coroutines. Voir ce Charming Python post pour un exemple. Eli Bendersky a également an excellent treatment of the subject.

Si les coroutines ne sont pas un territoire familier, le A Curious Course on Coroutines and Concurrency de David Beazley est une introduction stellaire.

Answer 4

Je suggère de vérifier chapter 4 of Text Processing in Python par David Mertz. Il implémente une classe de machine d'état en Python très élégante.

Answer 5

Je pense que la façon la plus pythonique serait d'aimer ce que FogleBird suggérait, mais de mapper de (état actuel, entrée) à une fonction qui gérerait le traitement et la transition.

Answer 6

Je suis un peu inquiet à l'idée de dire à tout le monde ce qu'est Pythonic, mais voilà. Tout d'abord, gardez à l'esprit que les fonctions python ne sont que des objets. Les transitions peuvent être définies avec un dictionnaire dont la valeur est la valeur (input, current_state) et le tuple (next_state, action). L'action est juste une fonction qui fait tout ce qui est nécessaire pour passer de l'état actuel à l'état suivant.

Voici un bel exemple de réalisation à http://code.activestate.com/recipes/146262-finite-state-machine-fsm.Je ne l'ai pas utilisé, mais d'après une lecture rapide, il semble que ça couvre tout.

Une question similaire a été posée/a été répondue ici il y a quelques mois: Python state-machine design. Vous pourriez également trouver ces réponses utiles.

Answer 7

Vous pouvez utiliser des expressions rationnelles. Quelque chose comme ce code trouvera le premier bloc de données. Ensuite, il suffit de lancer la recherche suivante après le match précédent.

find_header = re.compile('\xaa\xaa(.).{9}', re.DOTALL) 
m = find_header.search(input_text) 
if m: 
    length = chr(find_header.group(1)) 
    data = input_text[m.end():m.end() + length]