作者:杨超
本文地址:http://sokoban.ws/blog/?p=225
正则表达式(Regular Expressions)在编写计算机程序中有广泛和重要的作用。无论是编译器把源程序编译成可执行文件,还是浏览器把HTML文件渲染成可视化的页面,其中第一步都是在做类似一个的工作,那就是有一个通称为词法分析器(Lexer)的组成部分把源程序或是HTML文件分离成一个个最小的单位,称为单词(Token)。这一过程中,词法分析器所作的事情就是通过正则表达式的匹配,把单词逐一识别出来。
正则表达式的匹配有非常成熟的通用算法,很多时候并不需要手动编写。很多编译器或是浏览器(如 webkit )的词法分析器都用一个叫 flex 的程序自动生成的。使用 flex 程序,先把需要分析的词法用正则表达式写到一个.l文件中,然后 flex 程序根据.l文件的描述生成c文件。flex 程序也可以用来读取 XSB 格式的推箱子关卡文件。XSB 的基本格式可以参看这里的介绍。除了用 #@$*+. 等字符来表示推箱子关卡中的不同元素之外,很多关卡文件还在每个关卡后面用 Title, Author, Comment 等关键词来标识关卡的标题、作者和注释等信息。下面是一个例子:
######### # # # # #***# # ######### * * # ## # * * # ## * * * # *** # # * * * # * * # ####*### * # * * # # #*@* *** # # * * # * # # # #### #*$*** #* # * # # # # ******* # #***** # # * * # # ## *****# # ###### # # * * # # $. # * * # # # ******** # ###### * # ##### * #### # . # ##### Title: 2004-01-08 MF8 8th anniversary Author:gyjgw
上面的关卡如下图所示。
这样的 XSB 推箱子关卡格式完全可以用正则表达式来识别。近日,我的合作者 anian 先生就向我展示了他用 flex 工具编写的推箱子关卡转换器,非常可靠地把 XSB 格式转换成其它格式。
无独有偶的是,更早些时候,大概是2011年底,一位 Debian 开发者修改了我的自由软件 USokoban 。USokoban 的读取关卡部分是我手动编写的,不太稳定,是引起程序崩溃的主要原因之一。这位 Debian 开发者用了一个匹配正则表达式的函数库 PCRE 重新改写了关卡读取部分,使得程序更加健壮,打开关卡文件基本再也不会引起程序崩溃了。