[公告] rsec-0.0.8
 |
night_stalker
2010-02-13
See English document in github
rsec 是一个 Ruby 的动态解析器生成器（parser generator），可以用来构建解析器（parser）。只支持 Ruby 1.9 （不支持 1.8 及 jruby 等）。 注：Antlr、YACC 等工具为静态解析器生成器，Parsec、Boost::spirit 等为动态解析器生成器。一般静态的解析器生成器速度稍快，应用广泛，但是动态生成器可以在运行时变化，使用起来灵活得多。另外引入了 packrat parsing 等手段后，速度已经不慢了。 和 rparsec 的一个区别是底层为 StringScanner，没有 char() parser。 安装： gem install rsec helloworld 中的 helloworld: （最简单的解析器：匹配一个字符串） require 'rsec' parser = 'abcd'.r # String#r 方法将它转变成解析器 parser.parse 'abc' #=> 不匹配，我们失败了。 parser.parse 'abcd' #=> "abcd" 我们成功了！ 复杂的解析器都是从简单的解析器慢慢成长起来的。通过 parser combinator，我们可以极大简化构建解析器的过程。 synopsis: （helloworld 真达人）
# coding:utf-8
# 四则运算，永远的 helloworld
require "rsec"
include Rsec::Helpers
def arithmetic
calculate = proc do |(p, *ps)|
ps.each_slice(2).inject(p) do |left, (op, right)|
left.send op.strip, right
end
end
num = /[+-]?[1-9]\d*(\.\d+)?/.r.map &:to_f
bra = /\(\s*/.r.skip
ket = /\s*\)/.r.skip
expr = nil # declare for lazy
paren = bra >> lazy{expr} << ket
factor = num | paren
term = factor.join(/\s*[\*\/]\s*/).map &calculate
expr = term.join(/\s*[\+\-]\s*/).map &calculate
expr.eof
end
str = '1+2-3*4*5/((2*3)+6)-7'
print str, ' = '
puts arithmetic.parse str #=> -9
puts "ruby gets #{eval str}, too!" #=> 如果我没算错的话，应该也是 -9
tricks： 1. lazy{expr}：在 paren 规则调用 expr 的时候， expr 还没定义，所以要用 lazy 去包起它，等到 parse 的时候再找 expr。 用 lazy 之前需要先声明 expr，避免 not defined variable or methods。 2. 二元操作符 combinator 的右边可以直接用 String 或者 Regexp，可以自动转换成对应的 parser。 3. 在 map 中返回 Rsec::SKIP 也能产生 skip parser 的效果。 源代码（欢迎添加 issue）： http://github.com/luikore/rsec |
||||||||||||||||||||||||||||||
|
night_stalker
2010-02-14
parser 方法汇总
String#r 和 Regexp#r 产生原子 parser。 原子 parser 调用各种方法或者运算符可以产生新的 parser。 最后调用 parser 的 parse 方法就 OK 了，相当的简单呢。 （注：parse 解析失败返回 Rsec::INVALID。 parse! 会对语法错误产出异常。异常类型为 Rsec::ParseError，其 to_s 方法可以打印错误的行列和出错位置附近的代码。） 下面假设 par 和 ser 都是一个 parser，那么以下方法都能产生一个新的 parser。 基本组合子 --------------------------------------------------------[par, ser, par].r 顺序 parser，也就是先匹配 par，然后匹配 ser，再匹配 par，输出的结果是一个数组，对应 [par, ser, par] [par, ser].r skip: /\ / 顺序 parser，元素之间的空格会被跳过。 par >> ser 先匹配 par，然后匹配 ser，输出 ser 的匹配结果。 par << ser 先匹配 par，然后匹配 ser，输出 par 的匹配结果。 par | ser 如果 par 失败，便尝试 ser par._? 出现 0 次或一次 （不出现时返回 Rsec::SKIP） par * n par 连续出现 n 次。 par * (n..m) par 连续出现 n.abs 到 m 次。 如果 m < 0，par 至少匹配 n 次。（即匹配 n 到无穷次） par ** n 至少匹配 n 次的另一种写法，相当于 par * (n..-1) 更多的组合子 --------------------------------------------------------par.eof 如果解析完输入还没结束，返回 nil （不匹配） par.map{|node| ... } 这是一个映射 parser，将 par 的解析结果赋给 node，传给 block，然后 block 返回的结果作为 parse 结果。SDT 主要靠这个求值。根据 parser 的类型不同，node 可能是一个数组或者字符串。 par.on{|node| ... } 将 par 的解析结果传给 block，不改变 parse 结果。 技巧：可以在 on 之中给 node 添加属性或者方法，例如： par.on{|node|
def node.sum
inject(&:+)
end
end
par.fail('oh no!') 设定 fail 信息，par 失败时弹出一个包含此信息的异常（默认是 "syntax error"）。可以用来定制语法错误。 par.skip 成功就跳过。相当于 par.map{Rsec::SKIP}，不过会针对 pattern parser 作优化。 par & ser 正向环视（lookahead）。就是说 par 后面是 ser，但是 parse 结果不包括 ser。 par ^ ser negative lookahead。par 后面不是 ser 才通过。 join 系列 --------------------------------------------------------par.join ser 1 到任意个 par 之间以 ser 为间隔串在一起，方便进行二元运算符的解析。譬如 '1'.r.join ',' 可以 parse '1,1,1,1'。结果是一个数组 ['1',',','1',',','1',',','1']。 如果 ser 是一个 skip parser（也就是成功时输出 Rsec::SKIP 的 parser），join 的输出结果就会忽略掉 ser 的内容。假如上面的字符串如果被 '1'.r.join ','.r.skip 解析，结果就是数组 ['1','1','1','1'] par.join ser, /\s*/ 跳过可选空格 /\s*/ Pattern parser (原子 parser) 的专有方法 --------------------------------------------------------pattern.until 匹配以 pattern 结尾的字符串。 Sequence parser (顺序 parser) 的专有方法 --------------------------------------------------------par[n] 依然匹配原序列，但是产生的不是数组，而是其中一个子元素的 parse 结果。如： par = %w[( b )].r
par.parse '(b)' #=> ['(', 'b', ')']
par[1].parse '(b)' #=> 'b'
include Rsec::Helpers 之后的额外方法 --------------------------------------------------------lazy{ par } 有时一个 parser 还没定义，但又想引用它 —— 就用 lazy 吧。 注： 如果 par 是局部变量，应该在 lazy 之前加上 "par = nil" 声明一下。 dynamic{ par } 类似于 lazy，但每次调用的时候都会 call block，所以可以动态更改 parser 成分。 bol() 返回一个匹配行首的 parser。 value(1234) 不做任何事情，只返回值 1234。常用的手段是和 >> 或者 << 组合： /\w+/.r >> value(1234) # 匹配多个单词字符，如果匹配，输出 1234 skip_n(n) 跳过 n 个字符（可以为负）。如果越界，返回 nil，否则返回 Rsec::SKIP 和 PEG 的对应表 --------------------------------------------------------
|
||||||||||||||||||||||||||||||
|
night_stalker
2010-02-14
关于速度的讨论
1. vs treetop 和 treetop 作了一下性能比较： rsec result: 32918.38 0.266000 0.000000 0.266000 ( 0.273437) treetop result: 32918.38 2.171000 0.000000 2.171000 ( 2.175781) treetop without calculation 1.782000 0.000000 1.782000 ( 1.774414) 比 treetop 快呢 …… 代码见 http://github.com/luikore/rsec/tree/master/bench/ 假设有个递归定义的规则 s ： s = ss / a ss = a '+' s a = 'xyz' 那么在解析 'xyz' 的时候，规则应用的顺序是： s (左) ss (左) a -> 'xyz' 匹配 回到 ss (中) -> '+' 不匹配 回到 s (右) a -> 'xyz' 匹配 规则 a 在同一位置解析了两遍，导致了解析器的重复劳动。一种解决方法是对规则 a 进行缓存，如 Treetop 的 packrat parsing。它的缺点是：内存消耗变大，而且当定义是非递归的时候，缓存反而降低了解析速度。 另外还可以得到结论： 应该只针对 Or parser（例如 a | b | c 产生的结果） 的选择支中的公共元素进行缓存，其它 parser 是确定的，缓存也没有用。 对下面 3 个版本的 arithmetic 作了一下性能测试 递归定义的版本：
def arithmetic1
calc = proc do |left, op, right|
left.send op, right
end
num = /[+-]?[1-9]\d*(\.\d+)?/.r.map(&:to_f)
bra = /\(\s*/.r.skip
ket = /\s*\)/.r.skip
expr, term = nil
# paren = ( expr )
paren = bra >> lazy{expr} << ket
# factor = num | paren
factor = num | paren
# term = factor */ term | factor
term = [factor, /[\*\/]/, lazy{term}].r(skip: /\s*/).map(&calc) | factor
# expr = term +- expr | term
expr = [term, /[+-]/, lazy{expr}].r(skip: /\s*/).map(&calc) | term
expr.eof
end
使用了缓存的递归版本：
def arithmetic2
calc = proc do |left, op, right|
left.send op, right
end
num = /[+-]?[1-9]\d*(\.\d+)?/.r.map(&:to_f)
bra = /\(\s*/.r.skip
ket = /\s*\)/.r.skip
expr, term = nil
# paren = ( expr )
paren = bra >> lazy{expr} << ket
# factor = num | paren
factor = num | paren
# term = factor */ term | factor
_term = [factor,/[\*\/]/,lazy{term}].r(skip: /\s*/).map(&calc) | factor
term = _term.cached
# expr = term +- expr | term
_expr = [term,/[+-]/,lazy{expr}].r(skip: /\s*/).map(&calc) | term
expr = _expr.cached
expr.eof
end
利用 join combinator 消除了大部分递归，缓存完全派不上用场的版本： def arithmetic3
calculate = proc do |(p, *ps)|
ps.each_slice(2).inject(p) do |left, (op, right)|
left.send op, right
end
end
num = /[+-]?[1-9]\d*(\.\d+)?/.r.map(&:to_f)
bra = /\(\s*/.r.skip
ket = /\s*\)/.r.skip
expr = nil # declare for lazy
paren = bra >> lazy{expr} << ket
factor = num | paren
term = factor.join(/[\*\/]/, /\s*/).map &calculate
expr = term.join(/[\+\-]/, /\s*/).map &calculate
expr.eof
end
测试的结果： arithmetic3 完胜，arithmetic2 比起 arithmetic1 有巨大的进步，但还是比 arithmetic3 慢一些。 arithmetic3 的性能和下面的 Shunting-Yard 算法（转换成逆波兰表达式）的结果相近，只比 operator table 略差一点： # rpn: reverse polish notation
def arithmetic_rpn
float = /[\+\-]?\d+(?:\.\d+)?/.r.map(&:to_f)
bra = /\(\s*/.r.skip
ket = /\s*\)/.r.skip
expr = nil # declare for lazy
term = float | bra >> lazy{expr} << ket
# op[s] is a parser, it parses s and returns s.to_proc
op = proc {|s|
s.to_s.r >> value(s.to_proc)
}
# build operator table
expr = term.join_infix_operators(
calculate: true,
left: {
op[:+] => 5,
op[:-] => 5,
op[:**] => 15,
op[:*] => 10,
op[:/] => 10,
op[:%] => 10
}
)
expr.eof
end
------------------------------------------------------------------------- 2. vs haskell 下面和 ssword 童鞋的 FParsec 做一下比较： 下载 FParsec git clone git://github.com/Fleurer/FParser.git 计算器和 FFI 代码 Arithmetic.hs module Arithmetic where
import Control.Monad
import Data.Maybe
import Internal
import Combinator
import Lexer
import Foreign.C.String
expr = term `chain` addop
term = factor `chain` mulop
factor = (parens expr) <|> number
mulop = do { sym "*"; return (*); }
<|> do { sym "/"; return (div);}
addop = do { sym "+"; return (+); }
<|> do { sym "-"; return (-);}
calculate :: CString -> IO Int
calculate cs = do
s <- peekCString cs
(Right x, _) <- return (parse expr s)
return (fromIntegral x)
donothing :: CString -> IO Int
donothing cs = return 0
foreign export stdcall calculate :: CString -> IO Int
foreign export stdcall donothing :: CString -> IO Int
在 windows 下编译成 dll 需要创建一个 dllmain.c，内容如下：（linux 就不需要了） #include <windows.h>
#include <Rts.h>
extern void __stginit_Arithmetic(void);
static char* args[] = { "ghcDll", NULL };
BOOL APIENTRY DllMain(HANDLE hModule, DWORD reason, void* reserved)
{
if (reason == DLL_PROCESS_ATTACH) {
startupHaskell(1, args, __stginit_Arithmetic);
return TRUE;
}
return TRUE;
}
编译： ghc -c Type.hs Internal.hs Combinator.hs -fglasgow-exts -O2 ghc -c Lexer.hs Arithmetic.hs -fglasgow-exts -O2 ghc -c dllmain.c -O2 ghc -shared *.o -o Arithmetic.so -O2 测试代码 require 'dl/import'
require 'dl/types'
module Arithmetic
extend DL::Importer
dlload 'Arithmetic.so'
extern "long calculate(char *)", :stdcall
extern "long donothing(char *)", :stdcall
end
require "benchmark"
s = '(3+24/5)/10-3*4+((82321+12-3)-3*4+(82321+12-3))/5'
print "calc result: ", Arithmetic.calculate(s), "\n"
puts Benchmark.measure {
1000.times {
Arithmetic.calculate s
}
}
# 对照组，因为 dl 做类型转换时有些消耗，所以上述时间减去对照组要准确些
puts Benchmark.measure {
1000.times {
Arithmetic.donothing s
}
}
测试结果 calc result: 32917 0.156000 0.000000 0.156000 ( 0.155273) 0.000000 0.016000 0.016000 ( 0.016601) 最后还是 haskell 快呢。不过 0.27: 0.14，只慢一倍相对于总是很慢的 ruby 来说已经不错了 …… ps - 为什么要绕那么一大圈在 ruby 里作比较： 因为这种 repeat 类型的测试对 haskell 基本行不通，相同的调用会被自动 cache，对结果没影响的调用会被忽略 …… |
||||||||||||||||||||||||||||||
|
night_stalker
2010-02-17
添加了个 BNF 的例子：
http://github.com/luikore/rsec/blob/master/examples/bnf.rb 下面可以写个 EBNF --> rsec 的东西？ Edit 添加了 C-Minus 的例子（有点粗）： http://github.com/luikore/rsec/blob/master/examples/c_minus.rb |
||||||||||||||||||||||||||||||
 |
RednaxelaFX
2010-02-17
话说我想起这么一个课件，PEGs, Packrats and Parser Combinators
NS要不要考虑一下到底rsec是用来支持CFG还是用来支持PEG？如果支持的是PEG的话，就不太可能轻松的做“EBNF -> rsec”的转换了，因为EBNF是CFG的表示方式，而CFG与PEG表达的语言范围是不完全一样的 |
||||||||||||||||||||||||||||||
|
night_stalker
2010-02-17
它主要是 PEG，因为 | 组合子是确定的、会短路的。（手动用 map 处理成非确定的也可以 ……）
处理 EBNF 的一个小小的子集应该是可以的 …… |
||||||||||||||||||||||||||||||
|
night_stalker
2010-02-23
更新
|
||||||||||||||||||||||||||||||
 |
ssword
2010-03-04
还没有实现try...
这样parse ((sym "aabc") <|> (sym "abc")) $ "abc" 会跟着第一个字符'a'进入第一个分支然后报错～囧 |
