A very brief introduction to Aurum

Aurum是一个用Ruby实现的LALR(n) parser generator(是的,又是一个parser generator),不过它和其他一些广泛应用的parser generator相比略有不同的:

1.Aurum的主要目标之一,是简化external DSL的开发(尤其是ruby external DSL)。
2.Aurum采用增量LALR(n)算法,而不是通常的LALR(1)。这意味着:
  a.不必由于LALR(1)能力的限制,而改写语法,很多在LALR(1)中冲突的语法在LALR(n)中可以比较自然地表达。
  b.由于识别能力的增强,可以处理一些比较复杂的语法,比如COBOL(LALR(2)或LALR(3)),比如一些简化的自然语言(LALR(3+))。
  c.处理能力接近Generalized LR,却快很多
  d.比起Full LALR/LR(n),增量算法生成的语法表更小。
3.出于简化external DSL实现的考虑,Aurum支持语法重用。
4.Aurum采用Ruby internal DSL作为语法声明的元语言,可以利用Ruby丰富的测试框架,有效地对编译/解释/分析器进行测试。
5.正如名字所暗示的,Aurum(Gold的化学名称)的一部分灵感来自GOLD parsing system,它将支持独立于平台和语言的编译器开发。

好,闲话少说,看一个例子,编译原理中的Hello World —— 表达式求值:
 1 require 'aurum'
 2 
 3 class ExpressionGrammar < Aurum::Grammar
 4   tokens do
 5     ignore string(' ').one_or_more     # <= a
 6     _number range(?0?9).one_or_more  # <= b
 7   end
 8 
 9   precedences do  # <= c
10     left '*''/'
11     left '+''-'
12   end
13 
14   productions do # <= d
15     expression expression, '+', expression {expression.value = expression1.value + expression2.value} # <= e
16     expression expression, '-', expression {expression.value = expression1.value - expression2.value}
17     expression expression, '*', expression {expression.value = expression1.value * expression2.value}
18     expression expression, '/', expression {expression.value = expression1.value / expression2.value}
19     expression '(', expression, ')'        do expression.value = expression1.value end # <= f
20     expression _number                     {expression.value = _number.value.to_i}
21     expression '+', _number                {expression.value = _number.value.to_i}
22     expression '-', _number                {expression.value = -_number.value.to_i}
23   end
24 end


如果诸位对之前有用过compiler compiler或者parser generator的话,应该能看个七七八八吧。我大概解释一下:
 a.这里定义了文法空白,也就是被lexer忽略的部分,在通常的语言中,是空格回车换行之类的字符;string是用于定义lexical pattern的helper方法(出了string之外,还有range, enum和concat);ignore是一个预定义的说明指令,表示若文本匹配给定模式则该文本会被lexer自动忽略,其格式为:
    ignore pattern {//lexical action}
 b.此处为lexical token声明,所有lexical token必须以_开头,其格式为:
    _token_name pattern {//lexical action}
   这里其实是一个简略写法,等价于
    match pattern, :recognize => :_token_name
 c.此处为运算符优先级声明,支持左/右结合运算符(无结合属性运算符开发中);每一行中所有运算符具有相同优先级;比它下一行的运算符高一个优先级。比如在这个例子中,'*'和'/'具有相同优先级,但是比'+'和'-'的优先级别高。
 d.此处为语法规则声明,所使用的symbol主要有三种,nonterminal(小写字母开头),terminal(其实就是lexical token,以_开头)和literal(字符串常量),其中所有literal都会被自动声明为保留字。
 e.此处定义了一条文法规则(加法),以及对应的semantic action。在semantic action中可以直接通过symbol的名字来获取值栈中的对象。如遇到同名symbol,则按照出现顺序进行编号即可。
 f.其实这个没啥,只不过由于我们使用的是Ruby DSL,所以有时候不能都用{},需要do end,这就是一个例子。

最后测试一下实际中如何使用定义好的语法(使用helper method,注意由于分析表没有缓存,每次都会重算语法表,仅仅适用于debug mode。)
  puts ExpressionGrammar.parse_expression('1+1').value
或者通过分析表自己构造lexer和parser
  lexer = Aurum::Engine::Lexer.new(ExpressionGrammar.lexical_table, '1+1')
  parser = Aurum::Engine::Parser.new(ExpressionGrammar.parsing_table(:expression))
  puts parser.parse(lexer).value

最后最后,给另外一个例子,就是Martin Fowler Blog上的HelloParserGenerator系列中所用的语法:

 1 require 'aurum'
 2 
 3 Item = Struct.new(:name)
 4 
 5 class Catalog < Aurum::Grammar
 6   tokens do
 7     ignore enum(" \r\n").one_or_more
 8     _item range(?a,?z).one_or_more
 9   end
10 
11   productions do
12     configuration configuration, item {configuration.value = configuration1.value.merge({item.value.name => item.value})}
13     configuration _                   {configuration.value = {}}
14     item 'item', _item                {item.value = Item.new(_item.value)}
15   end
16 end
17 
18 config = Catalog.parse_configuration(<<EndOfDSL).value
19   item camera
20   item laser
21 EndOfDSL
22 
23 puts config['camera'].name


P.S.:本文是根据Aurum0.2.0写成的,你可以从rubyforge的svn上得到它。
P.S.P.S.: 在exmaples目录里有一个更复杂一些的例子,是一个简单的Smalltalk解释器。