前幾天在JavaEye海闊被標題黨陰了一把，看了一篇轉的文章叫《被中國人誤傳了數千年的七句話》，頗有些哭笑不得的感慨：

1. 這些話的確是被誤傳了不假，但是最多也就一百年吧。中國知識分子不讀四書五經史子集的壞風氣大抵是開始于所謂的新文化運動吧。再往前的人，對于這些典籍字字爬梳，提了上句馬上背下句，就算是以章句式解讀為主的宋元，也不應該隨隨便便就被忽悠了，更不用說反對宋儒理學講究正本清源的明清了。

2. 古人斷章取義是一種風雅的言談習慣，所謂“雅言”是要字字出典的，有點像對暗號。比如我們家貓跑了，擱古代我肯定問“誰之過歟？”，十有八九會回答說，“言是典守者之過也”，這句射的是“虎兕出于柙”，正好應景。甚至為了詼諧應景，故意曲解文義的情況也是很常見的。如果以此為證說誤傳的話，恐怕只能算是牛嚼牡丹了。順便多說一句，其實這個毛病現代人也有，不過不再是古文了，大多數是電影電視臺詞：“空氣在顫抖仿佛天空在燃燒。是啊，暴風雨就要來了”，“道哥，牌子啊”，“你看我的英語，有沒有長進”之類的，雖不復古韻，但也還算有趣。


P.S. : 今天team里有人把David Wheeler的名言，貼在了Quote Wall上：“Any problem in computer science can be solved with another layer of indirection.”

這到的確算是一句被誤傳的名言吧，原文是“Any problem in computer science can be solved with another layer of indirection. But that usually will create another problem.”

Aurum is a Ruby-based LALR(n) parser generator that you can use to develop your own domain specified languages, scripting languages and programming languages.Although it's just yet another parser generator, Aurum is slightly different from other widely used parser generators:

1. One of major targets of Aurum is to simplify external DSL development, espectually Ruby external DSL.
2. Aurum uses incremental LALR(n) algorithm instead of the common used LALR(1)/Full LALR(n) algorithm. That means:
   
   •   Allowing the user to express grammars in a more intuitive mannar.
   •   Making it easier to handle complicated grammars. For exmaple, COBOL(LALR(2 or 3)), simplified nature language(LALR(3+)) and etc.
   •   Closer to Generalized LR in language recognizing but much more faster.
   •   Smaller parsing table comparing to Full LALR/LR(n) algorithm.
3. Aurum supports grammar reuse, and itslef'll be shipped with some pre-defined common structures. One of the pain points of external DSL is that you have to re-define lots of common structures, such as if statements, block structure and etc. With Aurum, you could simply reuse them.
4. Aurum uses a Ruby interal DSL as meta-language, and provides a generic lexer/parser as well. You could test your grammar by the comprehensive testing libraries Ruby has(you could even develop your lexer/parser in the TDD fashion).
5. As the name suggested, Aurum, the Latin word for Gold, is partially inspired by the GOLD Parsing System. The grammar you created with Aurum could be completely independent of any implementation language,even Ruby.(not implemented yet :) )

Ok, let's start from the 'Hello World in Compiler Construction' —— Expression Evaluation


If you has any experience with other compiler compiler/parser generator, you probably could understand what happens above quite easily. Instead of explaining things like token, character class, and production, I'd like to emphasise some Aurum conventions:

1. At point a, we use 'ignore' directive to declare the ignored pattern, such as whitespaces etc.'string' is one of the helper methods(others are enum, range and concat), which is used to define lexical patterns. It will create a pattern matching the given string exactly.
2. At point b, we declare a lexical token named '_number'. In Aurum, lexical tokens, or terminals from syntax perspective, always start with '_'. The expression '_token_name pattern' is equivalent to 'match pattern, :recognized => :_toke_name'. The 'match' directive is a common way to associate lexical action with leixcal pattern.
3. At point c, we declare operator precedences of the Expression grammar.The eariler the operators definied, the higher precedence they will have.
4. At point d, we declare syntax rules of Expression grammar. According to Aurum naming convention, all terminals should start with '_' while all nontermainls start with lower case alphabet character. String literals will be interpreted as reserve words, and added to lexer automatically.
5. At point e, we define a semantic action to the Addition rule. In semantic action, you could access to the objects in value stack via the name of corresponding symbols.If there are more than one symbol with the same name, you could differentiate them by the order they appered in the production.
6. At point f, we use do..end instead of {..}. Using Ruby internal DSL as meta-langauge is a double-side sword, you have to bear its flaws while enjoying the remaining parts. There is no perfect world, isn't it?

Now, let's find out how we could use this expression grammar. You could use the helper method as below(it will recalcuate lexical table and parsing table for every call, could be quite slow):


or use the lexical table and parsing table to create your own lexer & parser:
 

At the end of this post, I'd like to give another grammar example coming from Martin Fowler's HelloParserGenerator series:



P.S.:The post is based on the developing version of Aurum(0.2.0). You could get it from the svn repository.
P.S.P.S.: There is a more complicated example in the examples directory, a simple Smalltalk interpreter. Have fun:)

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

《Programming Erlang》第8章后面有一個練習，Ring Benchmark。就是說創建N個進程，把它們組合成環狀。然后在這個環上把一條消息在環上傳遞M圈，然后記錄所有的時間。實現起來也挺簡單，20行左右吧：


有意思是它還有一個第二問，讓你用另外一種熟悉的語言實現同樣的功能，發送同樣多的消息，也把時間記錄下來，然后寫一篇blog來publish你的結果。其實，大家心知肚明，這種lightweight process啊，message passing concurrency啊都是Erlang的強項，而且實測結果也著實頗為恐怖，一般也就沒那閑心拿別的東西來陪襯一把了（Armstrong同學自己實現了一個Java version，效率大約能差到百倍吧）。不過還真有那寫不信邪的老大，用stackless python實現了同樣的ring benchmark，發現比erlang還快...后來修改代碼去掉io操作，Erlang倒是比stackless python快些，但也只是一些而已。