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

Ruby里的元编程

一个场景 元编程在所有的Lisp系语言中应该都是一个必备的feature,coommon lisp, scheme等包含该功能自然不在话下,而比较主流的编程语言如JavaScript,python之流,也或多或少的受到了lisp得影响,在面向对象的同时,也嵌入了一些元编程的特性。 而元编程在ruby中,虽然不如在lisp的宏那样灵活/强大,但是对于被“主流”编程语言影响很久的程序员 – 如我,来说,已经非常震撼了。 很多ruby程序员都是通过rails才慢慢接触到ruby本身的,在rails中,ORM是通过强大到无穷大得ActiveRecord来完成的。 一个简单的示例如: class Person < ActiveRecord::Base end 对应的,数据库中有一个Person的表: CREATE TABLE person ( id int(11) NOT NULL auto_increment, name varchar(255), age int, email varchar(255), PRIMARY KEY (id) ); 这样,在使用模型Person的地方,可以很容易的编写这样的代码: juntao = Person.new juntao.name = 'juntao' juntao.age = 28 juntao.email = 'juntao.qiu@gmail.com' juntao.save 也就是说,开发者仅仅需要简单的创建一个与数据库同名的ruby类,然后这个类(Person)只需要继承自ActiveRecord::Base,那么它就自动的获得了很多的功能。这些神奇的功能就是通过ruby的元编程来完成的。 一个ActiveRecord的拙劣模仿 我们在这里将编写一个简单的类InactiveRecord,当有其他类继承自此类时,会完成如ActiveRecord那样的功能,当然第一步我们并没有数据校验之类的功能,只是简单的将数据存储起来即可: 在person.rb文件中 class Person < InactiveRecord::Base end 在address.rb中: class Address < InactiveRecord::Base end 而在使用他们的地方: require './person' require './address' def test juntao = Person....

December 15, 2013 · 3 min · 邱俊涛 | Juntao Qiu