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解釋器。