草庐IT

c++ - 解析 C++ 的复杂性

coder 2023-11-14 原文

出于好奇，我想知道关于解析 C++ 的一些“理论”结果是什么。

让 n 成为我的项目的大小(例如，在 LOC 中，但由于我们将处理 big-O 它不是很重要)

  • C++ 的解析时间复杂度是 O(n) 吗？如果不是，复杂性如何？
  • C(或 Java 或任何语法意义上更简单的语言)是否在 O(n) 中解析？
  • C++1x 是否会引入更难解析的新特性？

非常感谢引用!

最佳答案

我认为出于问题的目的，不同的人以不同的方式解释了“解析”一词。

从狭义的技术意义上讲，解析只是验证源代码是否与语法匹配(或者甚至可能构建树)。

有一个相当普遍的民间定理，它说您根本无法解析 C++(在这个意义上)，因为您必须解析要解析的某些符号的含义。那个民间定理是完全错误的。

它源于使用“弱”(LALR 或回溯递归下降)解析器，如果它们错误地选择了文本的局部歧义部分的几个可能的子解析(this SO thread discusses an example)，则完全失败由于有时会做出这样的选择。使用此类解析器解决困境的方法是在解析发生时收集符号表数据，并将额外的检查混入解析过程中，以强制解析器在遇到此类选择时做出正确的选择。这是以名称和类型解析与解析显着纠缠为代价的，这使得构建这样的解析器非常困难。但是，至少对于遗留的 GCC，他们使用了 LALR，它是解析的线性时间，如果你包括解析器所做的名称/类型捕获，我认为它不会更昂贵(解析后还有更多工作要做，因为我不不要以为他们什么都做)。

至少有两个使用“纯”完成的 C++ 解析器实现 GLR parsing技术，它只是承认解析可能在本地不明确，并在没有注释或显着开销的情况下捕获多个解析。 GLR 解析器是线性时间，没有局部歧义。它们在歧义区域的成本更高，但实际上，标准 C++ 程序中的大部分源文本都属于“线性时间”部分。所以有效率是线性的，甚至可以捕获歧义。两个已实现的解析器都在解析后进行名称和类型解析，并使用不一致来消除不正确的歧义解析。 (这两个实现是 Elsa 和 our (SD's) C++ Front End 。我不能代表 Elsa 的当前能力(我认为它多年来没有更新)，但我们的实现了所有 C++11 [2015 年 1 月编辑:现在完整的 C++14 编辑 2017 年 10 月:现在完整的 C++17] 包括 GCC 和 Microsoft 变体)。

如果您采用严格的计算机科学定义，即一种语言被扩展定义为一组任意字符串(语法应该是有意编码的简洁方法)并将解析视为“检查程序的语法是否正确"那么对于 C++，您已经展开模板以验证每个模板是否确实完全展开。模板中隐藏着一台图灵机，因此理论上检查 C++ 程序是否有效是不可能的(没有时间限制)。真正的编译器(遵守标准)对它们将执行多少模板展开设置了固定的限制，实际内存也是如此，因此在实践中 C++ 编译器会完成。但是从这个意义上说，他们可以花任意长的时间来“解析”一个程序。我认为这是大多数人关心的答案。

实际上，我猜大多数模板实际上都非常简单，因此 C++ 编译器的平均完成速度与其他编译器一样快。只有疯狂到用模板编写图灵机的人才会付出沉重的代价。 (观点:代价实际上是将复杂的东西硬塞到模板上的概念成本，而不是编译器执行成本。)

关于c++ - 解析 C++ 的复杂性，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4172342/

amp43C++的sectionc++parsingtheorybig-ocompiler-theory

有关c++ - 解析 C++ 的复杂性的更多相关文章

  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 - 用逗号、双引号和编码解析 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.\"\

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

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

  5. 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

  6. 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.你能做的最好的事情是:

  7. ruby - 用 YAML.load 解析 json 安全吗？ - 2

    我正在使用ruby2.1.0我有一个json文件。例如:test.json{"item":[{"apple":1},{"banana":2}]}用YAML.load加载这个文件安全吗？YAML.load(File.read('test.json'))我正在尝试加载一个json或yaml格式的文件。 最佳答案 YAML可以加载JSONYAML.load('{"something":"test","other":4}')=>{"something"=>"test","other"=>4}JSON将无法加载YAML。JSON.load("

  8. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  9. ruby - 使用 AES 的 Rails 加密，过于复杂 - 2

    我在加密来self正在使用的第三方供应商的值时遇到问题。他们的指令如下:1)Converttheencryptionpasswordtoabytearray.2)Convertthevaluetobeencryptedtoabytearray.3)Theentirelengthofthearrayisinsertedasthefirstfourbytesontothefrontofthefirstblockoftheresultantbytearraybeforeencryption.4)EncryptthevalueusingAESwith:1.256-bitkeysize,2.25

  10. ruby - 如何使用 Nokogiri 解析纯 HTML 表格？ - 2

    我想用Nokogiri解析HTML页面。页面的一部分有一个表，它没有使用任何特定的ID。是否可以提取如下内容:Today,3,455,34Today,1,1300,3664Today,10,100000,3444,Yesterday,3454,5656,3Yesterday,3545,1000,10Yesterday,3411,36223,15来自这个HTML:TodayYesterdayQntySizeLengthLengthSizeQnty345534345456563113003664354510001010100000344434113622315

随机推荐