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