草庐IT

c++ - 用 g++/bison/boost::variant 编写的解析器编译速度很慢

coder 2024-02-18 原文

我用 bison 编写了一个 verilog 解析器，并使用 boost::variant 来存储每个规则的每个变体的所有不同情况。我用一个小例子，BNF 表达式规则，来展示我的数据结构:

expression :
  primary
  | expression + expression
primary :
  (expression)
  | number

存储它的数据结构是:

typedef boost::variant<
  std::shared_ptr<exp1>,
  std::shared_ptr<exp2>,
> expression
typedef boost::variant<
  std::shared_ptr<prim1>,
  std::shared_ptr<prim2>,
> primary

类 exp1/2 和 prim1/2 用于存储 expression 和 primary 中的两种不同情况:

class exp1 : public BaseClass {
  public :
    std::shared_ptr<primary> mem1;
    exp1(std::shared_ptr<primary> i1):
    mem1(i1)
    {}
}

为了简化，我只展示了exp1，而exp2和prim1/2是相似的。 在 bison 文件中，规则和它们的 Action 是这样写的:

expression :
  primary  {
   $$= std::make_shared<expression>(std::make_shared<exp1>($1));
  }

这样的解决方案会导致两个问题:

1 compiling is veeeeeeeeeeeery slow , cost almost 1 minute with g++ 4.8.4
2 run time is not very fast

我有一个用ocaml和ocamlyacc写的类似的parser，它支持非常优雅的variant规范，1秒编译，运行速度和上面提到的g++版本非常相似。

我使用boost::variant的风格有什么问题吗？

==============

我将所有变体更改为构造函数接受 shared_ptrs 的类:

class ComponentBase {
};
Class VariantBase{
};
class prim1;
class prim2;
class exp1;
class exp2;
class expression : public VariantBase {
  expression (shared_ptr<ComponentBase> i1):
    VariantBase(i1) {}
}
class primary : public VariantBase {
  primary (shared_ptr<ComponentBase> i1):
    VariantBase(i1) {}
}

那么编译就没有任何改进。看来 yacc 生成的代码是慢的根源。

有什么建议吗？

最佳答案

Update Added demos in Boost Spirit Qi instead (because I'm not versed in flex/bison), see block-quote below

如果您的 AST 使用共享指针，我建议运行时性能不是问题。

如果您的 AST 使用变体，我建议编译时性能不是问题。 (因此无需担心 :))

从概念上讲，shared_ptr 与变体背道而驰。 Shared_ptrs 通过生命周期管理的节点动态分配 boost 运行时多态性。

变体 boost 具有自动存储持续时间的静态多态性。

Go 运行时多态性

如果您对运行时多态 AST 节点(这在 AST 上的转换中通常非常方便)没有问题，那么我建议您不要使用这些变体。相反，让它们成为同一节点层次结构的一部分。

草图:

走静态多态

放弃运行时多态性(最好是变体 header )将减少编译时间。当需要创建、内联和优化模板实例化的许多组合时，编译时间会增加。

UPDATE

This demonstrates dropping the shared-pointer and runtime polymorphism for a simpler AST.

The afore-mentioned explosion of template instantiations + inlining thereof explains that the "old-fashioned" Qi implementation would compile slow, possibly slower than your original code. The X3 version doesn't have this problem.

关于c++ - 用 g++/bison/boost::variant 编写的解析器编译速度很慢，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34723754/

amp43变体sharedexpressionc++c++11boostboost-variant

有关c++ - 用 g++/bison/boost::variant 编写的解析器编译速度很慢的更多相关文章

  1. Ruby 解析字符串 - 2

    我有一个字符串input="maybe(thisis|thatwas)some((nice|ugly)(day|night)|(strange(weather|time)))"Ruby中解析该字符串的最佳方法是什么？我的意思是脚本应该能够像这样构建句子:maybethisissomeuglynightmaybethatwassomenicenightmaybethiswassomestrangetime等等，你明白了......我应该一个字符一个字符地读取字符串并构建一个带有堆栈的状态机来存储括号值以供以后计算，还是有更好的方法？也许为此目的准备了一个开箱即用的库？

  2. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

  3. ruby - 在 Ruby 中编写命令行实用程序 - 2

    我想用ruby​​编写一个小的命令行实用程序并将其作为gem分发。我知道安装后，Guard、Sass和Thor等某些gem可以从命令行自行运行。为了让gem像二进制文件一样可用，我需要在我的gemspec中指定什么。 最佳答案 Gem::Specification.newdo|s|...s.executable='name_of_executable'...endhttp://docs.rubygems.org/read/chapter/20 关于ruby-在Ruby中编写命令行实用程序

  4. ruby - 用逗号、双引号和编码解析 csv - 2

    我正在使用ruby​​1.9解析以下带有MacRoman字符的csv文件#encoding:ISO-8859-1#csv_parse.csvName,main-dialogue"Marceu","Giveittohimóhe,hiswife."我做了以下解析。require'csv'input_string=File.read("../csv_parse.rb").force_encoding("ISO-8859-1").encode("UTF-8")#=>"Name,main-dialogue\r\n\"Marceu\",\"Giveittohim\x97he,hiswife.\"\

  5. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  6. ruby - 用 Ruby 编写一个简单的网络服务器 - 2

    我想在Ruby中创建一个用于开发目的的极其简单的Web服务器(不，不想使用现成的解决方案)。代码如下:#!/usr/bin/rubyrequire'socket'server=TCPServer.new('127.0.0.1',8080)whileconnection=server.acceptheaders=[]length=0whileline=connection.getsheaders想法是从命令行运行这个脚本，提供另一个脚本，它将在其标准输入上获取请求，并在其标准输出上返回完整的响应。到目前为止一切顺利，但事实证明这真的很脆弱，因为它在第二个请求上中断并出现错误:/usr/b

  7. ruby-on-rails - 我更新了 ruby​​ gems，现在到处都收到解析树错误和弃用警告! - 2

    简而言之错误:NOTE:Gem::SourceIndex#add_specisdeprecated,useSpecification.add_spec.Itwillberemovedonorafter2011-11-01.Gem::SourceIndex#add_speccalledfrom/opt/local/lib/ruby/site_ruby/1.8/rubygems/source_index.rb:91./opt/local/lib/ruby/gems/1.8/gems/rails-2.3.8/lib/rails/gem_dependency.rb:275:in`==':und

  8. ruby - Sinatra set cache_control to static files in public folder编译错误 - 2

    我不知道为什么，但是当我设置这个设置时它无法编译设置:static_cache_control，[:public，:max_age=>300]这是我得到的syntaxerror,unexpectedtASSOC,expecting']'(SyntaxError)set:static_cache_control,[:public,:max_age=>300]^我只想将“过期”header设置为css、javaascript和图像文件。谢谢。 最佳答案 我猜您使用的是Ruby1.8.7。Sinatra文档中显示的语法似乎是在Ruby1.

  9. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  10. 安卓apk修改(Android反编译apk) - 2

    最近因为项目需要，需要将Android手机系统自带的某个系统软件反编译并更改里面某个资源，并重新打包，签名生成新的自定义的apk，下面我来介绍一下我的实现过程。APK修改，分为以下几步：反编译解包,修改,重打包,修改签名等步骤。安卓apk修改准备工作1.系统配置好JavaJDK环境变量2.需要root权限的手机（针对系统自带apk,其他软件免root）3.Auto-Sign签名工具4.apktool工具安卓apk修改开始反编译本文拿Android系统里面的Settings.apk做demo,具体如何将apk获取出来在此就不过多介绍了，直接进入主题：按键win+R输入cmd，打开命令窗口，并将路

随机推荐