推箱子关卡文件和正则表达式

作者：杨超

本文地址：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 重新改写了关卡读取部分，使得程序更加健壮，打开关卡文件基本再也不会引起程序崩溃了。