I**********s
发帖数: 441 | 1 有人写过或者用过LR(1)paser generator吗? 用KNUTH的算法或者用优化算法的都可以.
有没有 time/memory performance estimation? 有没有这方面的benchmark grammar
set? 谢谢. |
c****r
发帖数: 185 | 2 The performance of a parser generator is far less important than that of the
parser it generates. Most parser generators take just a few seconds to
generate a parser. In practice, LL parsers like antlr javacc seem more
popular than LR parsers. If you are doing research, I doubt if you can
motivate your problem. |
I**********s
发帖数: 441 | 3 javaCC用在java平台上是不错. 说到LR parser, 并没有流行的版本. 常用的yacc,
bison, byacc等都是LALR(1). LR(1)的优点在于可以分析所有context free的语法, 这
一点LALR(1)做不到. 而LL的语法也可以转换成LR(1). Knuth的原LR(1)算法长期一直被
认为速度太慢, 产生的parsing table太大. 即便现在, 用Knuth原算法实现的LR(1)
parser generator也常常需要很长时间才能完成运算. 比如我听说一个C++
implementation对于一个about 120 tokens, 350 production的语法, 要20分钟才能得
到结果. 另外一个implementation(in Python?), 作者称对大约100 tokens, 500
productions的语法, "I let it run for nearly three days, and it was far from
finishing, but using nearly 16GB of memory" |
c****r
发帖数: 185 | 4 Most part of a grammar can be recognized by LL(1) or LALR(1).
The rest can be specially taken care of, like lookahead in javacc.
Theoretically it is LL(k) and the complexity is exponential in k.
But practically it is not a problem. |
I**********s
发帖数: 441 | 5 "Specially take care of" can be a pain sometimes when you need to modify the
grammar, and you may not be sure the modified grammar is the same one as
before. Indeed a lot of things can be solved by precedence and other
conflict resolving methods. yacc/bison and now javacc can be used for most
compiler development tasks. But still there are people puzzled by the "
mysterious reduce/reduce conflict" and hope to find a LR(1) solution. Anyway
, I hope what I did can be an answer to this. |
r***u
发帖数: 241 | 6 what's your opinion on GLR?
the
Anyway
【在 I**********s 的大作中提到】
: "Specially take care of" can be a pain sometimes when you need to modify the
: grammar, and you may not be sure the modified grammar is the same one as
: before. Indeed a lot of things can be solved by precedence and other
: conflict resolving methods. yacc/bison and now javacc can be used for most
: compiler development tasks. But still there are people puzzled by the "
: mysterious reduce/reduce conflict" and hope to find a LR(1) solution. Anyway
: , I hope what I did can be an answer to this.
|
I**********s
发帖数: 441 | 7 GLR is an extension of LR by forking to handle nondeterministic and
ambiguous grammars. But here in the case of deterministic and unambiguous
grammars, LALR(1) parser still may have "mysterious reduce/reduce conflict".
LR(1) parser can handle this. |
