张磊的blog

用Racc编写解释器

在Twitter上看到盛大举办的校园牛人大赛，其中有“云计算脚本比赛”。看了下题目，开始悔恨大学里没好好学编译原理。但又手痒，就想用Racc试试。做题过程居然很顺利，从学习Racc到做完前三道题花了两三个小时，于是写一点有关Racc的示例，算是学习笔记。

以“云计算脚本比赛”第一题为例，要求执行如下脚本后，得到“Hello, 老赵”。

SET name = "老赵"
RETURN "Hello, " + name

简单来说，用Racc写成解释器，可以把上面的脚本，转化为Ruby代码并执行。

安装Racc：
gem install racc

创建一个level_1.y文件，定义一个JeffParser类。

class JeffParser
token T_SET T_RETURN T_STRING T_VAR
rule
  lines:
    | lines T_SET T_VAR '=' T_STRING {@local_vars[val[2]] = val[4] }
    | lines T_RETURN exp {result = val[2]}
  exp: exp '+' exp {result = val[0] + val[2] }
    | T_STRING
    | T_VAR {result = @local_vars[val[0]]}
end

先定义几个token。因为语法比较简单，只有 SET/RETURN/变量名/字符串四种。

在rule部分，格式是 token: token token … {action} 。中括号中的action 部分就是Ruby代码了，调试时可以把一些需要的变量打出来。val变量是由左边token的值构成的数组，0表示第一个token的值，依此类推。

之后是词法分析的部分。做的事儿是用正则表达式，把上面定义的4种token识别出来，并放到 @tokens 数组中。

---- header
require 'strscan'
---- inner
 def parse(str)
   @local_vars = {};
   @tokens = []
   s = StringScanner.new(str)
   until s.eos?
     case
     when s.scan(/SET/)
       @tokens << [:T_SET, s[0]]
     when s.scan(/RETURN/)
       @tokens << [:T_RETURN, s[0]]
     when s.scan(/".+"/)
       @tokens << [:T_STRING, eval(s[0])]
     when s.scan(/[a-z0-9]+/)
       @tokens << [:T_VAR, s[0]]
     when s.skip(/[ \t\r\n]/)
     else
       @tokens << [s.getch, nil]
     end
   end
   do_parse()
 end

 def next_token
   @tokens.shift
 end

保存后运行 `racc level_1.y ` 将生成一个名为level_1.tab.rb的文件，这就是我们想要的解释器了。

简单测试（假设脚本存放在level_1.file文件中）：

ruby -r level_1.tab.rb -e \
  'print JeffParser.new.parse(open("level_1.file").read())'

输出：

Hello, 老赵

当然，题目还只做了一半。题目要求：需要用http访问并得到结果。可以在前面挂一个Webrick来做到，就和Racc没关系了。

后面几道题，也可以如法泡制。

–广告时间–

赵姐夫(@jeffz_cn)说这次的题目是他经手的，后悔没把blog的链接放上去，于是我帮他打个广告，欢迎大家猛点此处。