LR(1)语法的状态,符号和规则数量的合理上限是多少?

Meh*_*dad 4 c++ parsing lr-grammar

我正在制作LR(1)解析器,并且我遇到了各个地方的性能瓶颈.

我想尝试优化解析器的数据结构,但为了做到这一点,我需要大致了解有多少状态,规则和终端符号对于(可能很复杂的)计算机语言(如C++)是合理的.

我的猜测是复杂语言的典型语法会:

  • ≤100个终端符号
  • 每个生产≤50个符号
  • ≤2000规则
  • ≤10,000个州

但我真的不知道他们有多正确.

请注意,我假设每个规则都是非终结符号  → 符号符号 符号 ...,因此看起来像单个复合"规则" foo: (bar | baz)+实际上可能包含5个规则,而不仅仅是1个规则.

他们合理吗?如果没有,我在哪里找到一些数字?

Ira*_*ter 6

我每天开发的DMS系统在一台糟糕的笔记本电脑上(大约现在在笔记本电脑上测量)在大约7秒内处理生产IBM Enterprise COBOL前端语法.

语法有大约500个终端和2500个制作,平均每个制作约2.5个令牌.我们的作品正如你所描述的那样(没有EBNF,只是没有足够的重要,是的,我们是大型的DSL粉丝.有时人们放入DSL的geegaws是不值得的).解析器生成器生成3800个状态.(这些值现在也在测量).

DMS有一个完整的C++ 11语法,有很多额外的东西来处理GCC和MS方言,以及OpenMP.该语法有457个终端,约3000个产品,每个产品平均约2.3个令牌.解析器生成器生成5800个状态.生成需要更长的时间:在i7上生成11秒.您可能会发现令人惊讶的是,生成词法分析器需要几十秒(实际上是多个词法分析器); C++ 11中有许多令人费解的怪异程度超出了你的期望.

生成器是我们自己实现的GLR生成器.

我们没有做很多工作来优化发电时间.它可能会加速10倍或更多; 我们没有像大多数关于LR解析器生成的论文中所建议的那样进行复杂的循环检测优化.结果是生成表需要更长的时间,但功能上没有任何损失.我们从来没有足够的动力来进行优化,因为除了担心解析器表生成时间之外,还有很多其他与语言前端有关的事情.

如果合理设计,我怀疑数据结构是否重要.我们不担心规则,项目集或状态的大小; 我们只是使用动态数组,他们会照顾好自己.我们将前瞻包装成密集的位向量.

作为额外的背景数据,你可能会发现这篇论文很有用:Tiago Alves和Joost Visser,SDF Grammars的Metrication.技术报告,DI-Research.PURe-05.05.01,DepartamentodeInformática,Universidade do Minho,2005年5月.

解析器生成器不是您使用语法困难的地方.它正在为特定的实现获得正确的语法规则.