Как Pythonic способ реализовать простой FSM?

Question

Вчера мне пришлось проанализировать очень простой двоичный файл данных - правило таково: найдите два байта в строке, оба из которых равны 0xAA, затем следующий байт будет байтом длины, затем пропустите 9 байтов и выведите указанное количество данных оттуда. Повторите до конца файла.

Мое решение сработало, и его было очень быстро собрать (хотя я в глубине души программист на C, я все же думаю, что быстрее написать это на Python, чем это было бы на C) - НО, это явно не Pythonic и читается как программа на C (и не очень хорошая в этом!)

Каким был бы лучший / более питонский подход к этому? Является ли простой FSM, как этот, все еще правильным выбором в Python?

Мое решение:

#! /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

Вы могли бы дать своим константным именам состояний вместо использования 0, 1, 2 и т. Д. Для улучшения читаемости.

Вы можете использовать словарь для отображения (current_state, input) -> (next_state), но это на самом деле не позволяет выполнять дополнительную обработку во время переходов. Если вы не включите некоторую «функцию перехода», чтобы выполнить дополнительную обработку.

Или вы можете использовать не-FSM подход. Я думаю, что это будет работать до тех пор, пока 0xAA 0xAA появляется только тогда, когда указывает «начало» (не отображается в данных).

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

Если он появляется в данных, вы можете вместо этого использовать string.find('\xaa\xaa', start) для сканирования строки, задав аргумент start, чтобы начать поиск конца последнего блока данных. Повторяйте, пока не вернет -1.

Answer 2

Самый крутой способ реализации FSM в Python - это генераторы и сопрограммы. Посмотрите этот Очаровательный пост Python для примера. У Эли Бендерского также превосходное отношение к предмету .

Если сопрограммы не являются знакомой территорией, «Любопытный курс по сопрограммам и параллелизму» Дэвида Бизли - звездное введение.

Answer 3

Я немного опасаюсь рассказывать кому-либо, что такое Pythonic, но здесь идет речь. Во-первых, имейте в виду, что в Python функции - это просто объекты. Переходы могут быть определены с помощью словаря, который имеет (input, current_state) в качестве ключа и кортеж (next_state, action) в качестве значения. Действие - это просто функция, которая делает все необходимое для перехода из текущего состояния в следующее.

Есть прекрасный пример сделать это на http://code.activestate.com/recipes/146262-finite-state-machine-fsm. Я не использовал его, но после быстрого прочтения кажется, что он охватывает все.

Подобный вопрос был задан / дан ответ пару месяцев назад: Python-state-machine . Вам также может быть полезно посмотреть на эти ответы.

Answer 4

Вы можете использовать регулярные выражения. Что-то вроде этого кода найдет первый блок данных. Тогда это просто случай начала следующего поиска после предыдущего совпадения.

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]

Answer 5

Я думаю, что самый питонический способ - это то, что предлагает FogleBird, но отображение из (текущего состояния, ввода) в функцию, которая будет обрабатывать обработку и переход.

Answer 6

Предлагаю проверить главу 4 Обработки текста в Python Дэвида Мерца. Он реализует класс конечного автомата в Python, который очень элегантен.

Answer 7

Я думаю, что ваше решение выглядит хорошо, за исключением того, что вы должны заменить count = count - 1 на count -= 1.

Это один из тех случаев, когда причудливые демонстрации кода могут привести к тому, что дикты будут отображать состояния в вызываемые объекты с небольшой функцией драйвера, но это не лучше, просто причудливее и использует более неясные языковые функции .