06/10/22 03:33:35
>>85
非終端記号の個数mと入力文字数nに対して、空間計算量はO(mn)。で、
非終端記号の数は通常一定なので、大体O(n)と考えて良いと思う。
ただ、それでも莫大なメモリを消費することには変わりないので、
巨大なXMLファイルなどを解析するのは向いてない。
Java用のPackrat Parser GeneratorでRats!というのがあるので、
興味があれば使ってみれば良いかも。
ちなみに俺はyaccのようなbottom up parserの挙動はイメージしづらいんで、
あんまし好きじゃない。自分では、JavaCCのようなLL(k)
Parser Generatorをもっぱら使ってる。