草庐IT

c++ - 有限状态机解析器

coder 2024-02-07 原文

我想使用类似 FSM 的解析器在 C++ 中 解析自行设计的文件格式(这是一个teach-myself-c++-the-hard-way-by-做一些大而难的 类的项目 :))。我有一个带有换行符的标记化字符串，表示一行结束。参见 here for an input example .所有的评论都会被过滤掉，所以我有一个像这样的 std::string:

global \n { \n SOURCE_DIRS src \n HEADER_DIRS include \n SOURCES bitwise.c framing.c \n HEADERS ogg/os_types.h ogg/ogg.h \n } \n ...

语法解释:

  • { } 是范围，大写单词表示后面是选项/文件列表。
  • \n 仅在选项/文件列表中很重要，表示列表的结尾。

所以我认为 FSM 足够简单/可扩展，足以满足我的需求/知识。据我所知(并希望我的文件设计如此)，我不需要并发状态或类似的东西。一些设计/实现问题:

  1. 我应该为状态使用 enum 还是抽象 class + 衍生物？第一个对于小语法可能更好，但以后可能会变得丑陋，而第二个则恰恰相反。我倾向于第一个，因为它很简单。 enum example和 class example .编辑:那this suggestion呢？对于 goto，我认为它们在 C++ 中是邪恶的？
  2. 阅读列表时，我需要注意不要忽略 \n。我的首选方式是通过 stringstream 使用 string，默认情况下会忽略 \n。所以我需要简单的方法来告诉(相同!)stringstream 在启用特定状态时不要忽略换行符。
  3. 简单的 enum 状态是否足以进行多级解析(范围 {...{...}...} 内的范围)或者是否需要骇人听闻的实现？
  4. 这是我想到的草案状态:
    • upper:读取全局、exe、lib+目标名称...
    • 正常:在作用域内，可以读取 SOURCES...，创建用户变量...
    • list:将项目添加到列表中，直到遇到换行符。

每个作用域都有一种条件(例如 win32:global { gcc:CFLAGS = ... })并且需要以完全相同的方式处理每个地方(即使在 list 中)状态，每个项目)。

感谢任何输入。

最佳答案

如果您有嵌套作用域，那么有限状态机不是正确的方法，您应该查看上下文无关语法分析器。一个LL(1) parser可以写成一组递归函数，或 LALR(1) parser可以使用解析器生成器(例如 Bison)编写。

如果您将堆栈添加到 FSM，那么您将进入 pushdown automaton领土。非确定性下推自动机等同于上下文无关文法(虽然 deterministic pushdown automaton 严格来说没有那么强大。)LALR(1) 解析器生成器实际上在内部生成确定性下推自动机。一本好的编译器设计教科书将涵盖从语法构造下推自动机的确切算法。 (这样，添加堆栈就不是“hacky”了。)This Wikipedia article还介绍了如何根据您的语法构造 LR(1) 下推自动机，但 IMO，这篇文章并没有那么清晰。

如果您的范围嵌套只有有限深度(即您有 upper、normal 和 list 级别，但您没有嵌套 list 或嵌套的 normal)，那么您可以使用没有堆栈的 FSM。

关于c++ - 有限状态机解析器，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3085070/

amp43codenoreferrernoopenerc++parsingstreamfsm

有关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 - 跳过状态机方法的所有验证 - 2

    当我的预订模型通过rake任务在状态机上转换时，我试图找出如何跳过对ActiveRecord对象的特定实例的验证。我想在reservation.close时跳过所有验证!叫做。希望调用reservation.close!(:validate=>false)之类的东西。仅供引用，我们正在使用https://github.com/pluginaweek/state_machine用于状态机。这是我的预订模型的示例。classReservation["requested","negotiating","approved"])}state_machine:initial=>'requested

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

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

  8. 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("

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

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

  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

随机推荐