可爱的Python:使用状态机

状态机从理论上说是几乎与计算机和编程相关的每件事的基础。从实用角度来看,状态机还有助于解决许多常见问题(特别适用于 Python 程序员)。本文中,David Mertz 讨论了何时以及如何使用 Python 编码状态机的实际例子。

什么是 Python?

请简要回顾本专栏中的 第一篇文章 ,Python 是由 Guido van Rossum 开发的免费高级解释型语言。其语法简单易懂,而其面向对象的语义功能强大(但又灵活)。Python 可以广泛使用并具有高度的可移植性。

什么是状态机?

关于状态机的一个极度确切的描述是它是一个有向图形,由一组节点和一组相应的转移函数组成。状态机通过响应一系列事件而“运行”。每个事件都在属于“当前”节点的转移函数的控制范围内,其中函数的范围是节点的一个子集。函数返回“下一个”(也许是同一个)节点。这些节点中至少有一个必须是终态。当到达终态,状态机停止。

但一个抽象的数学描述(就像我刚给出的)并不能真正说明在什么情况下使用状态机可以解决实际编程问题。另一种策略就是将状态机定义成一种强制性编程语言,其中节点也是源码行。从实用角度看,这个定义尽管精确,但它和第一种描述一样,都是纸上谈兵、毫不实用。(对于说明型、函数型或基于约束的语言,例如,Haskell、Scheme 或 Prolog,不一定会发生这种情况。)

让我们尝试使用更适合身边实际任务的例子来进行讨论。逻辑上,每个规则表达式都等价于一个状态机,而每个规则表达式的语法分析器都实现这个状态机。实际上,大多数程序员编写状态机时,并没有真正考虑到这一点。

在以下这个例子中,我们将研究状态机的真正探索性定义。通常,我们有一些不同的方法来响应一组有限数量的事件。某些情况下,响应只取决于事件本身。但在其它情况下,适当的操作取决于以前的事件。

本文中讨论的状态机是高级机器,其目的是演示一类问题的编程解决方案。如果有必要按响应事件行为的类别来讨论编程问题,那么您的解决方案很可能是显式状态机。

文本处理状态机

最可能调用显式状态机的一个编程问题涉及到处理文本文件。处理文本文件通常包括读取信息单元(通常叫做字符或行),然后对刚读取的单元执行适当操作。某些情况下,这个处理是“无状态的”(即每个这样的单元都包含了足够的信息,可以正确确定要执行什么操作)。在其它情况下,即使文本文件不是完全无状态,数据也只有有限的上下文(例如,操作取决于不比行号更多的信息)。但是,在其它常见文本处理问题中,输入文件是极具“状态”的。每一块数据的含义取决于它前面的字符串(也许是它后面的字符串)。报告、大型机数据输入、可读文本、编程源文件和其它种类的文本文件都是有状态的。一个简单例子是可能出现在 Python 源文件中的一行代码:

myObject = SomeClass(this, that, other)

这行表示,如果恰好有以下几行围绕着这一行,则有部分内容不同:

"""How to use SomeClass:
myObject = SomeClass(this, that, other)
"""

我们应知道我们处于“块引用” 状态 以确定这行代码是一部分注释而不是 Python 操作。

何时不使用状态机

当开始为任何有状态的文本文件编写处理器的任务时,问一问自己,您希望在文件中找到什么类型的输入项。每种类型的输入项都是一种状态的候选项。这些类型共有几种。如果数字很大或者不确定,则状态机也许不是正确的解决方法。(在这种情况下,某些数据库解决方案可能更适合。)

还请考虑您是否需要使用状态机。许多情况下,最好从更简单的方法入手。也许会发现即使文本文件是有状态的,也有一种简单的方法可以分块读取它(其中每一块是一种类型的输入值)。实际上,在单一状态块中,仅当文本类型之间的转移需要基于内容的计算时,才有必要实现状态机。

下面这个简单的例子说明了需要使用状态机的情况。请考虑用于将一列数字划分成几块的两个规则。在第一个规则中,列表中的零表示块之间的间断。第二个规则中,当一个块中的元素总和超过 100 时,会发生块之间的间断。由于它使用累加器变量来确定是否达到了阈值,您不能“马上”看到子列表的边界。因此,第二个规则也许更适合于类似于状态机的机制。

稍微有些状态、但由 不 太适合用状态机处理的文本文件的例子是 Windows 风格的 .ini 文件。这种文件包括节头、注释和许多赋值。例如:

; set the colorscheme and userlevel
[colorscheme]
background=red
foreground=blue
title=green
[userlevel]
login=2
title=1

时间: 2024-12-03 12:34:23

可爱的Python:使用状态机的相关文章

可爱的Python: 用基于生成器的状态机和协同程序增加效率

Python 2.2 中引进的简单生成器可用于简化状态机以及模仿协同程序.David 在"可爱的 Python"专栏较早前的一个部分中介绍了一个 状态机处理的抽象模式.从那时起,简单生成器的引进就为描述机器提供了一些更自然的范例.协同程序是一种"外来"流机制,广泛使用的语言几乎都不支持这种机制(甚至连非 Stackless Python 都不支持它).然而,Python 的新生成器 几乎完全支持协同程序,几乎不用模仿任何额外的步骤.在本文中,David 通过说明性代

可爱的Python: 使用Spark模块解析

Spark 是一种用 Python 编写的强大的.通用的解析器/编译器框架.在某些方面,Spark 所提供的比 SimpleParse 或其它 Python 解析器提供的都要多.然而,因为它完全是用 Python 编写的,所以速度也会比较慢.David 在本文中讨论了 Spark 模块,给出了一些代码样本,解释了它的用途,并对其应用领域提供了一些建议. 继"可爱的 Python"系列中专门讲述 SimpleParse 的 前一篇文章之后,我将在本文中继续介绍一些解析的基本概念,并对 S

可爱的Python:Decorator简化元编程

Python 使元编程成为可能,不过每个版本的 Python 都有一些细微的区别(并且不是完全兼容),这使我们实现元编程的道路变得更加崎岖.一类函数对象的使用由来已久,同样还有一些技术用于探索和实现魔术般的属性.在版本 2.2 中,Python 增加了一种很有帮助的定制元类机制,但是其代价就是令用户绞尽脑汁.最近,在 2.4 版本中,Python 增加了 "decorator" ,这是适于执行大部分元编程的最新方式 -- 也是到目前为止对用户最友好的方式. 少劳多得 Decorator

可爱的Python: 用Python生成器实现“轻便线程”

在 "可爱的 Python"的前面一部分中,David 介绍了一种用生成器和简单的调度程序模拟完整协同程序的方法.我们也许可以用直观的方式来扩展这种调度程序,使其允许对多进程使用极为轻量级的线程.与 Stackless Python 微线程非常相似,伪协同程序"轻便线程"几乎不需要 OS(甚至用户区)线程的上下文切换和内存开销.David 在这里介绍了轻便线程,一种巧妙的解决方案,它用来解决使用普通解决方案处理将涉及大量协同进程的问题. 微线程领域(至少在 Pyth

可爱的Python:将XML和Python结合起来

开始在 Python 中使用 XML 的一个主要要素是排列出所有可用模块的可比性能力.在他的新 Python 专栏"可爱的 Python"的第一部分中,David Mertz 简要描述了最流行和实用的关于 XML 的 Python 模块,并指出可以下载的单独模块以及可供阅读的参考资料.本文有助于确定哪些模块最适合特定任务. 在许多情况下,Python 是使用 XML 文档的理想语言.像 Perl.REBOL.REXX 和 TCL 一样,它是一种灵活的脚本语言,并且有强大的文本操作能力.

可爱的Python:动态重新装入

与大多数其它编程语言相比,Python 的一大优点就是其强大的运行时动态能力.感谢方便的 reload() 函数,我们可以编写持续运行的程序,但它可以在进程运行期间装入经过修改的组件(对于那些持续运行时间至关重要的服务来说, 相当有用).b本文在 David 以前的文章中讨论的对 Txt2Html 前端的某些增强基础上,说明了运行时程序修改.特别是,我们的样本程序将对因特网上 Txt2Html 转换库的新版本进行后台检查, 并下载和重新装入所需的新版本,无需用户手工介入. 让我们描绘一下本文的情

可爱的Python:Curses编程

某一类 Python应用程序最好使用交互式用户界面,这样可以消除图形环境的系统开销或复杂性.交互式文本模式程序(在Linux/UNIX 中),例如封装在 Python 的标准 curses模块中的 ncurses 库,正是您所需要的.本文中,DavidMertz 讨论了在 Python 中 curses 的用法.他使用从前端到 Txt2Html程序的样本源代码阐述了 curses 环境. curses 库 ( ncurses ) 提供了控制字符屏幕的独立于终端的方法.curses 是大多数类似于

可爱的Python: 重温Python的XML工具

David Mertz 创作的 可爱的 Python的第一.第二部分概述了在 Python 中使用XML.然而,在那些最初的文章出现后,Python 中的 XML工具有了很大的发展.不幸的是,这些改进中的大多数并不向后兼容.在这个特别部分中,重温了作者先前对XML 工具的讨论,并提供最新的代码示例. 在许多情况下,Python 是使用 XML 文档的理想语言.像 Perl.REBOL.REXX 和 TCL 一样,它是一种灵活的脚本语言,并且有强大的文本操作能力.而且,除了对多数类型的文本文件(或

可爱的Python: 使用SimpleParse模块进行解析

与大多数程序员一样,我经常需要标识存在于文本文档中的部件和结构,这些文档包括:日志文件.配置文件.分隔的数据以及格式更自由的(但还是半结构化的)报表格式.所有这些文档都拥有它们自己的"小语言",用于规定什么能够出现在文档内. 我编写处理这些非正式解析任务的程序的方法总是有点象大杂烩,其中包括定制状态机.正则表达式以及上下文驱动的字符串测试.这些程序中的模式大概总是这样:"读一些文本,弄清是否可以用它来做些什么,然后可能再多读一些文本,一直尝试下去." 各种形式的解析