Mapfile解析器

前言 Mapfile是MapServer用来描述一个地图的配置文件。它是一个很简单的声明式语言,一个地图(Map)可以有多个层(Layer),每个层可以有很多属性(键值对)。在一个层的定义中,还可以定义若干个类(Class),这个类用以管理不同的样式(Style)。而每个类或者样式都可以由若干个属性(键值对)。 这里有一个实际的例子: LAYER NAME "counties" DATA "counties-in-shaanxi-3857" STATUS default TYPE POLYGON TRANSPARENCY 70 CLASS NAME "polygon" STYLE COLOR 255 255 255 OUTLINECOLOR 40 44 52 END END END 最简单的层的定义 最简单的情形是,我们定义了一个层Layer,但是没有指定任何的属性: LAYER END 我们期望parser可以输出: {layer: null} 要做到这一步,首先需要定义符号LAYER和END,以及一些对空格,非法字符的处理等: \s+ /* skip whitespace */ \n|\r\n /* skip whitespace */ "LAYER" return "LAYER" "END" return "END" <<EOF>> return 'EOF' . return 'INVALID' 对于,空格,回车换行等,我们都直接跳过。对应的BNF也非常简单: expressions : decls EOF {return $1;} ; decls : LAYER END {$$ = {layer: null}} ; 为层添加属性 接下来我们来为层添加Name属性,首先还是添加符号NAME和对字符串的定义。这里的字符串被定义为:由双引号括起来的所有内容。...

October 5, 2015 · 3 min · 邱俊涛 | Juntao Qiu

如何手写一个解释器

前言 在代码编写中,很多时候我们都会处理字符串:发现字符串中的某些规律,然后将想要的部分抽取出来。对于发杂一些的场景,我们会使用正则表达式来帮忙,正则表达式强大而灵活,主流的变成语言如Java,Ruby的标准库中都对其由很好的支持。 但是有时候,当接收到的字符串结构更加复杂(往往会这样)的时候,正则表达式要么会变的不够用,要么变得超出我们能理解的复杂度。这时候,我们可能借助一些更为强大的工具。 下面是一个实际的例子,这个代码片段是MapServer的配置文件,它用来描述地图中的一个层,其中包含了嵌套的CLASS,而CLASS自身又包含了一个嵌套的STYLE节。显然,正则表达式在解释这样复杂的结构化数据方面,是无法满足需求的。 LAYER NAME "counties" DATA "counties-in-shaanxi-3857" STATUS default TYPE POLYGON TRANSPARENCY 70 CLASS NAME "polygon" STYLE COLOR 255 255 255 OUTLINECOLOR 40 44 52 END END END 在UNIX世界,很早的时候,人们就开发出了很多用来生成解释器(parser)的工具,比如早期的lex/yacc之类的工具和后来的bison。通过这些工具,程序员只需要定义一个结构化的文法,工具就可以自动生成解释器的C代码,非常容易。在JavaScript世界中,有一个非常类似的工具,叫做jison。在本文中,我将以jison为例,说明在JavaScript中自定义一个解释器是何等的方便。 注意,我们这里说的解释器不是一个编译器,编译器有非常复杂的后端(抽象语法树的生成,虚拟机器指令,或者机器码的生成等等),我们这里仅仅讨论一个编译器的前端。 一点理论知识 本文稍微需要一点理论知识,当年编译原理课的时候,各种名词诸如规约,推导式,终结符,非终结符等等, 上下文无关文法(Context Free Grammar) 先看看维基上的这段定义: 在计算机科学中,若一个形式文法 G = (N, Σ, P, S) 的产生式规则都取如下的形式:V -> w,则称之为上下文无关文法(英语:context-free grammar,缩写为CFG),其中 V∈N ,w∈(N∪Σ)* 。上下文无关文法取名为“上下文无关”的原因就是因为字符 V 总可以被字串 w 自由替换,而无需考虑字符 V 出现的上下文。 基本上跟没说一样。要定义一个上下文无关文法,数学上的精确定义是一个在4元组:G = (N, Σ, P, S),其中 N是“非终结符”的集合 Σ是“终结符”的集合,与N的交集为空(不想交) P表示规则集(即N中的一些元素以何种方式) S表示起始变量,是一个“非终结符” 其中,规则集P是重中之重,我们会在下一小节解释。经过这个形式化的解释,基本还是等于没说,在继续之前,我们先来看一下BNF,然后结合一个例子来帮助理解。...

September 30, 2015 · 3 min · 邱俊涛 | Juntao Qiu