boost spirit介绍.doc

一、 Spirit介绍 Spirit，递归下降分析器框架,是传统的过程式代码； 和STL都具有易于理解、流畅、高效等优秀特性。 Spirit主要特性：模块性和可扩展性 Spirit不是给你一个大锤，它提供方便打造大锤的正确成分。 Spirit使用基本元素(终结符)和复合元素(产生式)的层次对象组合来模块化递归下降分析器。现在的Spirit版本使用了大量的表达式模版 ( Expression Templates , C+ Report, June 1995) 和静态多态特性。 Spirit是一个面相对象的递归下降分析器生成器框架，以 模板元编程技术 实现。 表达式模板 使我们能够在C中使用近似于EBNF范式的语法。 基于表达式模版技术，Spirit可以用C+代码来表示EBNF文法，这样就减少了传统编译器生成器中将EBNF文法转换未c、c+代码的步骤。在spirit中用如下符号来同等替代EBNF文法中的符号： C+ EBNF = := 连接符 | 或者（选择符) () 组合 *前置 *（ Kleene Star) ;(结束规则) Spirit框架以层次结构来组织， 因此 当掌握了最小部分的核心内容和基本概念之后，所需要学习的，仅仅是需要使用的。Spirit的易用性和可伸缩性，使其在开发小型分析器时成为最佳的选择。为了简化开发和部署，Spirit整个框架只包含了头文件，不需要在编译时链接库。所要作的只是把Spirit放到你的包含路径，编译，运行。代码规模？很小。 分析器可以越来越大，嵌套越来越多。无论何时，当你把两个分析器粘到一块儿，你得到的是一个更大的分析器，这是一个重要的概念。 二、Spirit基本概念以及简单用法 1. 基本概念 规则(rule) 分析器(parser) 规则是分析器的组合，而你可以通过规则的 名字 来使用这些不同的组合。 匹配(Match) 扫描器(Scanner) 语义动作(Semantic Actions) Liner input - scanner - parser - Match - actor - parser tree( other formats ) 2. Spirit简单使用： （1) 创建分析器( 可以使用预定义的分析器(_p后缀) ) real_p *( ch_p(,) int_p ) (2) 创建一条规则用于存储复合规则 r = real_p *( ch_p(,) int_p ) ; (3) 使用全局函数parse()使用分析器分析格式流 parse_info parse( input, parser, skip_parser ); input: 格式输入流 parser: 格式流分析器 skip_parser: 分析器元素之间字符忽略分析器 parse函数返回一个对象（称为parse_info）用来保留分析的结果。 (4) 语义动作 语义动作依附于分析器，表示当输入匹配分析器时进行的动作。 比如一个分析器 P 和一个函数 F ，如果想让 P 在成功匹配输入时调用 F ，可以以如下的方式连接： P&F 。或者F是个函数对象： PF；函数或函数对象的参数取决于分析器的类型，如果分析器的属性为nil_t，则函数原型为: Void F( Iterator first, Iterfaotr last); or struct F Void opetator()(Iterator first,Iterator last); ; 如果分析器的属性类型不为nil_t，则： Void F(T val); or Struct F Void operator()(T val); ; 三、基本概念 3.1 分析器 框架的中心，接受扫描器的输入，并根据语法规则对输入流进行匹配，匹配成功后执行语义动作，进行输入数据的处理。 分析器分成两类：基本元素(Primitives)和复合元素(Composities)。相当于编译器中的终结符和非终结符。 内嵌对象的灵活性和递归的合成，开创了一个统一的分析方法。 派生类可以构成任意复杂度的聚合或算法。复杂的分析器可以仅经由少数元素类合成而创建。 3.2 扫描器 扫描器分析线性输入流并输出给parser使用。 scanner( IteratorT & first_, iter_param_t last_, PoliciesT const& policies = PoliciesT() first_,last_)执行输入流范围，first_采用引用传递方便parser重定位。policies指定扫描器的扫描策略。扫描器策略用于控制扫描器的行为。Spirit预定义了一些扫描器策略，客户程序可以自定义扫描器策略来解析输入流。 3.3 匹配 派生的分析器都要实现一个parse成员函数： typename parser_result:type parse(ScannerT const& scan) const; parser_result 元函数返回给定分析器和扫描器的匹配对象类型。匹配对象的主要作用是报告分析是否成功给parser的调用者。parse成功时, match.length()为成功匹配的字符数(0);parse失败时，match.length() = -1; match.length()=0也是一个成功的匹配。 分析器都有关联的属性数据，缺省的属性类型为nil_t。如real_p有一个关联的数值属性，即分析过的数据。分析器属性在parse成功时，也通过匹配对象返回。 3.4 语义动作 语义动作hook到parser上，档parser成功匹配输入时，将会出发语义动作函数(actor)。这样可以在语义动作函数中进一步处理分析器的属性信息。 四、 框架组织 Spirit模块化设计： iterator actor (独立层) debug attribute dynamic error_handling symbols tree utility meta - 元编程技巧 core scanner primitives composite non_terminal Spirit有四层和一个独立层。层与层之间时非循环的，即层与层间是相互独立的。低层不依奈于高层，甚至同层间的模块也是相互独立的。 iterator模块：独立于spirit。 actor模块： 独立与spirit，实际上它只是一些函数对象和函数对象生成器而已。 debug模块：提供库级别的parser调试。在需要是会透明的挂钩到spirit核心上。 attribute模块： 介绍高级的语义动作机制，主要是通过继承和合成属性来提取parser层次上的属性。此外，attribute还可以用于控制分析行为，生成动态分析器。 dynamic模块：运行时动态修改的分析器 error_handling模块：异常处理，在Spirit这种嵌套递归调用中非常有用。 symbols模块：符号表管理模块 tree模块：分析树和抽象语法树 utility模块：通用模块 meta模块：为Spirit高级用户提供元编程技术 四、 核心学习(Core) 5.1 Primitives 基本元素(终结符) Spirit预定义了大量的基于类模版的基本元素，可以方便构建复杂的分析器。 每个基本的分析器都有对应的一个分析器生成函数。 5.1.1 单字符分析器( character literal parser ) (1) 描述 基本分析器(parser primitives) 分析器生成函数（Parser Generator) chlit ch_p (2) 例子 rule r1 = chlit(Z) ; rule r2 = ch_p(X) ; (3) 重载问题 两个重载函数模版（boost/spirit/core/composite/impl/sequence.ipp) ： template inline sequenceA, chlit operator(parser const& a, char b) return sequenceA, chlit (a.derived(), b); template inline sequencechlit, B operator(char a, parser const& b) return sequencechlit, B(a, b.derived(); 根据这两个重载函数， c expr， expr c等两边不是同为字符时，单个字符会隐士转换为chlit(ch)； 注意 x y是不正确的，只能是ch_p(x) y、 x ch_p(y)、 chlit(x) y、 x chlit(y)。 5.1.2 字符区间分析器 ( range parser ) (1) 描述 基本分析器(parser primitives) 分析器生成函数（Parser Generator) range range_p 该分析器识别区间中的任意一个字符，构造函数接收一对字符区间： range(CharT first_, CharT last_); / first_ 必须在last_之前 (2) 例子 range(A,Z) / matches A.Z range_p(a,z) / matches a.z 5.1.3 词法级别的字符串分析器 (strlit or str_p ) (1) 描述 该分析器识别一个字符串。Strlit有两个构造函数： strlit(IteratorT first, IteratorT last) / 字符串迭代区间 strlit(IteratorT first) / 0结束字符串 (2) 例子 strlit(Hello World) str_p(Hello World) std:string msg(Hello World); strlit(msg.begin(), msg.end(); 5 .1.4 语法级别的字符串分析器 ( chseq or chseq_p ) (1) 描述 chseq也是识别一个字符串，但是和strlit不同的是，chseq它是语法层面上的分析器，因此可以忽略字符串之间的空格。 (2) 例子 chseq(ABCDEFG) 可以识别： ABCDEFG A B C D E F G AB CD EFG 【学习】 词法级别分析器和语法级别分析器 传统的编译器词法分析和语法分析的区分是相当明显的，比如yacc和lex的分工相当明确，lex分析线性输入流，并生成标记流(token stream，单词流)；yacc接受lex的标记流，并根据文法来生成句子。 和传统的处理方式不一样， spirit缺省情况下将词法分析器隐藏在语法分析器下面，这样就出现了上面的词法层面的分析器和语法层面的分析器。词法层面的分析器， 分析线性输入流，生成单词序列(标记流)； 语法层面分析器，分析词法分析器生成的单词序列，因此语法层面的分析器匹配的是单词序列。 5.1.5 其他字符分析器 anychar_p 匹配任意字符(包括0) alnum_p 匹配 a-zA-Z0-9 alpha_p 匹配 a-zA-Z blank_p 匹配空格和tab cntrl_p 匹配控制字符 digit_p 匹配数字0-9 graph_p 匹配图形字符 lower_p 匹配小写字符a-z print_p 匹配打印字符 punct_p 匹配标点符号 space_p 匹配空格，tab，换行，回车 upper_p 匹配大写字符A-Z xdigit_p 匹配十六进制数 0-9A-F 5.1.6 杂项 单字符分析器，如chlit,range都可以使用来修饰，表示匹配除。之外的字符。 ch_p(x) / 匹配x之外的其他字符 eol_p / eol_p 匹配换行回车 nothing_p / 不匹配任何东西，永远失败 end_p / 匹配输入结束，这时返回的匹配对象中length=0 5.2 数值分析器(终结符) Spirit预定义大量的数值分析器，包括符号(无符号)整数分析器，符号(无符号)浮点分析器等。数值分析器可进行进制，小数点左右精度等参数的配置，此外数值分析器的行为是通过数值分析器策略来控制，用户可以自定义策略来实现不同的操作。 uint_parser 无符号整数分析器 ( boost_operator.cpp ) template struct uint_parser /*.*/ ; 模版参数： T 数值分析器基本类型 Radix 数值进制 MinDigits 允许的最少位数 MaxDigits 允许的最大位数 预定义的数值分析器： bin_p 二进制数值分析器 uint_parser cosnt bin_p; oct_p 八进制数值分析器 uint_parser cosnt oct_p; uint_p 十进制数值分析器 uint_parser cosnt bin_p; hex_p 十六进制数值分析器 uint_parser cosnt bin_p; int_parser 符号数分析器 real_parser 实数分析器 template typename T = double, typename RealPoliciesT = ureal_parser_policies struct real_parser; 模版参数类型： T 实数类型 float, double ,long double或用户自定义类型 RealPoliciesT 实数分析器策略 预定义实数分析器： ureal_p 无符号实数分析器 real_p 实数分析器 strict_ureal_p 严格无符号实数分析器 strict_real_p 严格实数分析器 严格实数要求 小数点 必须出现。 实数分析器策略： 1. parse_sign 分析符号前缀+, - 2. parse_n 分析小数点左边整数部分 3. parse_dot 分析小数点 4. parse_frac_n 分析小数点右边整数部分 5. parse_exp 分析指数前缀E , e 6. parse_exp_n 分析指数部分 这些子分析步骤的交互由另外的三个策略进行控制： allow_leading_dot 允许前导小数点，如 .1342 allow_trailing_dot 允许尾部小数点，如 1324. expect_dot 数值部分必须由小数点 策略： 策略名称 修改部分 ureal_parser_policies real_parser_policies : ureal_parser_policies parse_sign strict_urel_parser_policies : ureal_parser_policies expect_dot = true strict_real_parser_policies : real_parser_policies expect_dot = true 用户自定义的实数分析器策略可以通过修改预定义的实数策略来完成特殊的操作。 如分析千位分隔、最多两位小数、没有指数部分的实数。 thousand_seperated.cpp 5.3 规则(Rule) EBNF 产生式规则，由左边的非终结符 和 右边的EBNF C+表达式组成。 template typename ScannerT = scanner, typename ContextT = parser_context, typename TagT = parser_address_tag class rule; 模版参数： ScannerT 扫描器类型 scanner ContextT 分析器上下文 parser_context TagT 规则标签 parser_address_tag 在1.8.0这个版本中， ScannerT，ContextT和TagT可以以任意顺序排列 。如果某个模板参数缺失，则适用默认的参数。 在1.8.0中，规则可以使用一个或者多个扫描器类。引入多扫描器是为了支持语法层面和词法层面的不同分析操作。 typedef scanner_listscanner, phrase_scanner_t scanners; rule r = +anychar_p; assert( parse(abcdefghijk, r).full ); assert( parse(a b c d e f g h i j k, r, space_p).full ); 为了支持多扫描器，必须在boost头文件引用前定义宏 # define BOOST_SPIRIT_RULE_SCANNERTYPE_LIMIT 3 / 多扫描器最大限制 当规则在EBNF表达式右边引用时，表达式使用的是规则的引用。规则是C+的一个特例，它没有拷贝和赋值语义，不能以值进行存储和引用。必须显示调用copy()函数来实现拷贝操作。规则是动态的，对一个规则进行二次赋值会引起它的析构和重定义。 规则本质上来说是一个动态分析器。 为了识别，可以给规则加上标签(Tag)，尤其是在分析树和AST树中要判断是那条规则产生该结点时。每条规则都有一个类型为parser_id的ID，通过成员函数id()获取。 parser_address_tag 使用rule的内存地址作为rule tag parser_tag 使用常数N作为rule tag （静态） dynamic_parser_tag 使用动态数值作为rule tag （动态） 5.4 空串 (Epsilon) epsilon_p , eps_p Epsilon空串 空串用途： 1. 零长度匹配 通常用于无条件触发一个语义动作。如： R = A | B | C | eps_p error ; / error if A, B or C fails to match 2. 语义断言 Semantic Predicate 语义断言允许你在语法的任意点上挂接函数，eps_p接受零元函数对象，该函数对象通常用于解决语法二义性的一个测试。如果函数对象的结果为false，则分析失败。 eps_p(f) rest; / 函数f触发调用，检测一个符号是否在符号表中，如果返回true，则继续分析 3. 语法断言（句意断言） Syntactic Predicate 类似于语义断言，语法断言在推演后续产生式之前检测语法断言。这时eps_p的输入为条件分析器，如： eps_p(p) rest ; / 分析器p进行语法检测，如果输入匹配p，则进行后续推演。eps_p空串不消耗任何输入。 eps_p( 0 ) oct_p ; / 匹配前导0的八进制数值，如果发现一个0，epsilon_p将报告一个零长度的成功匹配。 4. 基本类型参数 eps_p接受c+内置类型作为参数。如char, wchar_t, char *, wchar *。 5. 抑制语义动作 Inhibiting Semantic Actions 在语法断言中，直接或间接作用于条件分析器的语义动作都不会调用，但是作用于eps_p的语义动作总是被调用(因为eps_p总是返回true)。如： eps_p( pf ) / f not called eps_p( p ) f / f is called eps_pf / f is called 作为条件分析器要求必须不具有副作用（语义动作）。条件分析器的作用是通过 前向匹配(forward-match) 输入来消除语法二义性。二义性和语义动作不能够很好的结合使用，在一个二义性文法中，会产生回溯。当回溯产生时，已触发的语义动作无法回溯。 6. 反操作符 Negation eps_p eps_p 对 结果 进行取反操作。 5.5 Directives ( 指示器) 形式： directiveexpression Spirit预定义少量directives，框架使用者可以自定义directive. Directive控制expression的行为。 lexeme_d 功能：禁用空格忽略。 在短语级别，分析器将忽略空格和注释。当我们想在字符界别而不是短语级别操作时，使用lexeme_d。将分析器封闭在lexeme_d中初始分析器在字符级别工作。如： integer = lexeme_d !(ch_p(+) | -) +digit ; lexeme _d指定使得封闭的分析器处于字符界别进行操作。如果没有使用lexeme_d的话，rule( !(ch_p(+) | -) +digit ) 将会把1 2 3 4 5分析为12345，允许数字之间出现的不正确的空格。 as_lower_d 功能：忽略大小写,将所有字符转换为小写字符处理。 例子： as_lower_d begin 匹配 begin, BEGIN .。 注意：as_lower_d只是将输入转换为小写字符处理，它不能够将中的字符转换为小写字符处理。如果as_lower_d 中出现大写字符，则会出现分析错误。如：as_lower_d X ，该分析器永远无法匹配成功，因为分析器想要匹配大写字符X，但是as_lower_d不支持这种功能。 no_actions_d 功能：禁止语义动作的触发。 directive工作原理： lexeme_d，as_lower