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 —— 表达式求值：


如果诸位对之前有用过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系列中所用的语法：



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