Multi-Pass 迭代器

server/2025/1/19 10:37:55/

The multi pass iterator - 1.87.0

Multi-Pass 迭代器

Spirit.Qi 的回溯与迭代器类型要求

在 Boost.Spirit.Qi 中，解析回溯需要以下几种迭代器类型之一：前向迭代器（forward iterator）、双向迭代器（bidirectional iterator） 或 随机访问迭代器（random access iterator）。由于回溯需要保存迭代器的当前位置，输入迭代器（input iterator） 无法使用。因此，标准库中的 std::istreambuf_iterator 和 std::istream_iterator 都不能直接应用于 Spirit.Qi。

另一种需要注意的输入迭代器是用于包装词法分析器（lexer）的迭代器，例如 LEX。

注意事项

Spirit.Qi 通常生成递归下降解析器，其设计上依赖回溯功能。因此，至少需要为其 API 提供 前向迭代器。不过，这并非绝对必要。未来可能会出现更加确定性的解析器，它们只需 1 个字符（或 token）作为前瞻即可工作。这类解析器可以直接使用输入迭代器（如 std::istream_iterator）。

输入迭代器的限制

回溯的实现依赖于保存当前迭代器的位置，即对迭代器进行拷贝。然而，输入迭代器不支持位置保存，因此无法用于 Spirit.Qi 的回溯需求。
一种解决方法是将所有需要解析的数据预先加载到一个容器（如 std::vector 或 std::deque）中，然后将容器的起始和结束迭代器传递给 Spirit.Qi。但这种方法可能会对内存造成较大压力，这也是 multi_pass 迭代器被创建的原因。

使用 Multi-Pass

Multi-Pass 的作用

multi_pass 迭代器可以将任何输入迭代器转换为适合 Spirit.Qi 使用的前向迭代器。它会根据需要缓冲数据，并在不再需要时丢弃缓冲区的内容。具体情况包括：

  • 只有一个迭代器副本存在时。
  • 不可能发生回溯时。
使用 Multi-Pass 时的语法设计

当使用 multi_pass 时，需要谨慎设计解析语法（grammar）。例如：

  • 可能触发回溯的规则（如包含选择项的规则）会导致数据被缓冲。
  • 重复性规则（如 Kleene 星号 * 和加号 +）是更高效的选择。
序列规则与缓冲

形如 a >> b 的序列规则也会导致数据缓冲。
这种行为与 Spirit.Classic 的行为不同，但有充分理由：
在序列中，如果某个组件匹配失败，解析器需要将当前迭代器重置为初始状态。

期望点规则（expectation points）

为了优化这种行为，期望点规则（a > b）被引入到解析器中。期望点在语法中引入了确定性点，确保匹配成功时不会发生回溯。在每个期望点，multi_pass 迭代器会清空其缓冲区，从而保证即使是大型语法，缓冲内容也能保持最小化。

重要提示

如果你在使用 multi_pass 时结合了期望点规则和错误处理器，并希望错误处理器强制重试或失败（如 on_error<retry> 或 on_error<fail>），则需要明确地以 retry 或 fail 的形式实例化错误处理器。例如：

rule r<iterator_type> r; 
on_error<retry>(r, std::cout << phoenix::val("Error!"));

如果未按照上述方式处理，则运行时会触发断言错误。

重复性规则的缓冲优化

对于重复性规则（如 *a 或 +a），multi_pass 迭代器只会缓冲当前重复的内容。

在典型的语法中，解析的歧义（即需要前瞻）通常是局部化的。实际上，许多设计良好的语言是完全确定性的（LL(1) 语法），无需前瞻。例如，只需查看输入的第一个字符（或 token），即可决定解析的分支。

即使对于高度歧义的语法，选择项通常也呈现如下形式：

*(a | b | c | d)

此时，输入迭代器会继续前进，而不会卡在开头。例如，以下是 Pascal 中的一段语法：

program =programHeading >> block >> '.';block =*(   labelDeclarationPart|   constantDefinitionPart|   typeDefinitionPart|   variableDeclarationPart|   procedureAndFunctionDeclarationPart)>>  statementPart;

注意，在规则 block 中，Kleene 星号中的选择项会以线性方式解析输入，并在每次迭代中丢弃历史数据。由于这是一个完全确定性的 LL(1) 语法，每个失败的选择项只需查看 1 个字符（或 token）即可决定是否前进。

Flush Multi-Pass

如果语法是确定性的，可以使用 flush_multi_pass 伪解析器来避免不必要的缓冲区。例如：

  • 在 Spirit.Qi 的解析器库中，可以使用 flush_multi_pass 来优化缓冲行为。

示例：解析浮点数列表

以下是一个使用 multi_pass 的最小示例：

#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/support_multi_pass.hpp>
#include <fstream>
#include <iostream>
#include <vector>int main()
{namespace spirit = boost::spirit;using spirit::ascii::space;using spirit::ascii::char_;using spirit::qi::double_;using spirit::qi::eol;std::ifstream in("multi_pass.txt");  // 从文件获取输入if (!in.is_open()) {std::cout << "无法打开输入文件: 'multi_pass.txt'" << std::endl;return -1;}typedef std::istreambuf_iterator<char> base_iterator_type;spirit::multi_pass<base_iterator_type> first =spirit::make_default_multi_pass(base_iterator_type(in));std::vector<double> v;bool result = spirit::qi::phrase_parse(first,spirit::make_default_multi_pass(base_iterator_type()),double_ >> *(',' >> double_),  // 识别浮点数列表space | '#' >> *(char_ - eol) >> eol,  // 跳过注释v);if (!result) {std::cout << "解析输入文件失败！" << std::endl;return -2;}std::cout << "成功解析输入文件！" << std::endl;return 0;
}

此示例展示了如何使用 multi_pass 从文件中解析浮点数列表。multi_pass 提供了默认的策略配置，使其能够轻松与 std::istreambuf_iterator 等输入迭代器结合使用。

使用 flush_multi_pass 解析器

flush_multi_pass 解析器是 Spirit 仓库中的一个组件，它与 multi_pass 迭代器结合使用，可以最小化缓冲需求。通过在语法中插入显式的同步点，确保在这些点之后不会发生回溯，从而可以安全地清除存储的输入数据。

当 flush_multi_pass 与 multi_pass 配合使用时，会调用 multi_pass::clear_queue()，清除任何已缓冲的数据。这将使所有其他 multi_pass 的副本失效，使用这些副本会引发 boost::illegal_backtracking 异常。

multi_pass 策略

multi_pass 的配置

multi_pass 是一个支持策略配置的模板类。上述描述的 multi_pass 行为是其最初实现（没有策略时的默认配置），并且现在仍作为默认行为。然而，multi_pass 支持更多扩展功能。由于策略的开放性，可以通过自定义策略来扩展 multi_pass 的功能。

multi_pass 的模板参数

  1. Input
    定义 multi_pass 获取输入的方式。通常是一个输入迭代器或函数对象。

  2. Policies
    定义用于创建 multi_pass 迭代器实例的组合策略类型。组合策略由以下四种功能策略组成：

default_policy 模板所需的策略

multi_pass 使用模板类 iterator_policies::default_policy 来组合以下四种不同的策略，每种策略负责一种功能：

模板参数描述
OwnershipPolicy决定 multi_pass 如何管理其共享组件。
CheckingPolicy决定如何进行无效迭代器的检查。
InputPolicy定义 multi_pass 如何获取输入，参数化为 Input 模板参数。
StoragePolicy决定并管理 multi_pass 的缓冲方案。

预定义的策略

multi_pass 库为每种策略类型提供了若干预定义实现，均位于 boost::spirit::iterator_policies 命名空间中：

预定义策略类
  1. InputPolicy 类
类名描述
input_iterator指示 multi_pass 从 Input 类型的输入迭代器中读取数据。
buffering_input_iterator类似于 input_iterator，但会缓冲从底层迭代器读取的最后一个字符（如 std::istreambuf_iterator）。
istream指示 multi_pass 从 Input 类型的输入流（通常是 std::basic_istream）中读取数据。
lex_input通过调用 yylex() 获取输入，通常由 Flex 生成的扫描器提供。需要链接到 Flex 生成的扫描器。
functor_input通过调用 Input 类型的函数对象获取数据。函数对象需包含 result_type 和 eof 静态变量。
split_functor_input类似于 functor_input，但分离了唯一和共享的子类，可以整合其数据成员与 multi_pass 的数据。
  1. OwnershipPolicy 类
类名描述
ref_counted使用引用计数机制，在引用计数归零时释放共享组件。
first_owner第一个创建的 multi_pass 拥有共享数据，其它副本不拥有数据。适合于栈分配的迭代器。
  1. CheckingPolicy 类
类名描述
no_check不进行任何检查。
buf_id_check使用缓冲区 ID，每次调用 clear_queue() 时更新缓冲区 ID，并在迭代器解引用时检查一致性。适用于 split_std_deque。
full_check（尚未实现）未来将跟踪所有迭代器以确保它们有效，适合调试使用但开销较大。
  1. StoragePolicy 类
类名描述
split_std_deque使用 std::vector 存储所有缓冲数据，适合需要动态缓冲的场景。
fixed_size_queue<N>使用固定大小的环形缓冲区，缓冲区大小为 N+1，适合对内存需求受限的场景。

自定义策略

尽管 multi_pass 提供了丰富的预定义策略，但也可以根据需求实现自己的策略。以下是一些自定义策略的设计指南：

  1. 输入策略（InputPolicy）
    确保定义清晰的输入获取机制和终止条件（如 eof 变量）。

  2. 存储策略（StoragePolicy）
    平衡内存使用和性能需求。例如，如果数据较大且解析复杂，可以选择动态缓冲策略；如果数据较小且固定，可以选择固定缓冲策略。

  3. 检查策略（CheckingPolicy）
    根据调试需求选择合适的检查策略。例如，开发阶段可以使用严格的检查策略（如 buf_id_check），而在生产阶段可以选择 no_check 以减少开销。

使用自定义 multi_pass 的方法

Boost.Spirit 提供了一种基于策略的设计方式，通过组合各种策略，可以灵活定制 multi_pass 迭代器的行为。以下是关于自定义 multi_pass 的关键点和步骤：

1. 定义自定义的 multi_pass 类型

以下是一个基于 std::istream_iterator<char> 的示例，比默认的 multi_pass 更高效：

typedef multi_pass<std::istream_iterator<char>,iterator_policies::default_policy<iterator_policies::first_owner,          // 所有权策略iterator_policies::no_check,            // 检查策略iterator_policies::buffering_input_iterator, // 输入策略iterator_policies::split_std_deque      // 存储策略>
> first_owner_multi_pass_type;

此定义的 multi_pass 使用了 iterator_policies::first_owner 和 iterator_policies::no_check 策略，从而略微提高了效率。

2. 默认参数解释

默认情况下，如果使用 multi_pass<std::istream_iterator<char>>，它将采用以下默认策略：

  • 所有权策略：iterator_policies::ref_counted
  • 检查策略：iterator_policies::no_check（若定义了 BOOST_SPIRIT_DEBUG，则为 iterator_policies::buf_id_check）
  • 输入策略：iterator_policies::buffering_input_iterator
  • 存储策略：iterator_policies::split_std_deque
3. 处理固定的前瞻量

look_ahead 是一个预定义的类，提供固定大小的前瞻功能。它适用于对性能要求更高的场景：

typedef look_ahead<std::istream_iterator<char>, 10> look_ahead_iterator;
  • 第二个模板参数 10 指定缓冲区大小。
  • 适合需要快速解析固定前瞻量的场景。
4. 从标准输入流读取

basic_istream_iterator 是一个可以替代 std::istream_iterator 的前向迭代器。与 std::istream_iterator 不同，它是前向迭代器而非输入迭代器：

typedef basic_istream_iterator<char, std::char_traits<char>> istream_iterator;

此迭代器提供更强的功能，并且可以用于标准输入流的封装。

....


http://www.ppmy.cn/server/159604.html

相关文章

实战指南：使用Wireshark捕获并解密HTTPS数据包

实战指南：使用Wireshark捕获并解密HTTPS数据包

在网络安全和数据分析领域&#xff0c;捕获和分析网络数据包是理解网络行为、诊断问题和进行安全审计的重要手段。HTTPS&#xff08;HyperText Transfer Protocol Secure&#xff09;作为现代Web通信的主要协议&#xff0c;通过SSL/TLS加密确保了数据的安全传输。然而&#xff…
阅读更多...
PP-OCR系统

PP-OCR系统

我看书上的只到v2系统&#xff0c;所以我这里也只介绍V2&#xff0c;实际上他的包&#xff0c;我看了&#xff0c;已经出到V4了 整个系统包括&#xff0c;文本检测&#xff0c;方向分类&#xff0c;最后进行文本识别 PP-OCRV2改进如下&#xff1a; • 检测模型优化: (1) 采用…
阅读更多...
centos 7 Mysql服务

centos 7 Mysql服务

将此服务器配置为 MySQL 服务器&#xff0c;创建数据库为 hubeidatabase&#xff0c;将登录的root密码设置为Qwer1234。在库中创建表为 mytable&#xff0c;在表中创建 2 个用户&#xff0c;分别为&#xff08;xiaoming&#xff0c;2010-4-1&#xff0c;女&#xff0c;male&…
阅读更多...
【0393】Postgres内核 checkpointer process ③ 构建 WAL records 工作缓存区

【0393】Postgres内核 checkpointer process ③ 构建 WAL records 工作缓存区

1. 初始化 ThisTimeLineID、RedoRecPtr 函数 InitXLOGAccess() 内部会初始化 ThisTimeLineID、wal_segment_size、doPageWrites 和 RedoRecPtr 等全局变量。 下面是这四个变量初始化前的值： (gdb) p ThisTimeLineID $125 = 0 (gdb) p wal_segment_size $126 = 16777216 (gdb…
阅读更多...
生成模型：生成对抗网络-GAN

生成模型：生成对抗网络-GAN

1.原理 1.1 博弈关系 1.1.1 对抗训练 GAN的生成原理依赖于生成器和判别器的博弈 生成器试图生成以假乱真的样本。判别器试图区分真假样本。 这种独特的机制使GAN在图像生成、文本生成等领域表现出色。 具有表现为: 生成器 (Generator, G) 生成器的目标是从一个随机噪声&…
阅读更多...
python之二维几何学习笔记

python之二维几何学习笔记

一、概要 资料来源《机械工程师Python编程&#xff1a;入门、实战与进阶》安琪儿索拉奥尔巴塞塔 2024年6月 点和向量&#xff1a;向量的缩放、范数、点乘、叉乘、旋转、平行、垂直、夹角直线和线段&#xff1a;线段中点、离线段最近的点、线段的交点、直线交点、线段的垂直平…
阅读更多...
Hadoop 和 Spark 的内存管理机制分析

Hadoop 和 Spark 的内存管理机制分析

&#x1f496; 欢迎来到我的博客&#xff01; 非常高兴能在这里与您相遇。在这里&#xff0c;您不仅能获得有趣的技术分享&#xff0c;还能感受到轻松愉快的氛围。无论您是编程新手&#xff0c;还是资深开发者&#xff0c;都能在这里找到属于您的知识宝藏&#xff0c;学习和成长…
阅读更多...
重回C语言之老兵重装上阵（九）字符串

重回C语言之老兵重装上阵（九）字符串

C 语言字符串 在 C 编程语言中&#xff0c;字符串是由一系列字符组成的字符数组。字符串是以 空字符 \0 结尾的&#xff0c;以此标志字符串的结束。 1. 字符串的定义与表示 1.1 字符串定义 在 C 语言中&#xff0c;字符串是通过字符数组来定义的。定义字符串的一种常见方式是…
阅读更多...
最新文章

Copyright @ 2022~2023