Chinaunix首页 | 论坛 | 博客
  • 博客访问: 142660
  • 博文数量: 35
  • 博客积分: 245
  • 博客等级: 二等列兵
  • 技术积分: 320
  • 用 户 组: 普通用户
  • 注册时间: 2011-05-06 14:31
文章分类

全部博文(35)

文章存档

2017年(8)

2015年(1)

2014年(7)

2013年(11)

2012年(1)

2011年(7)

我的朋友

分类: C/C++

2017-04-07 14:56:39

一、 Spirit介绍

Spirit,递归下降分析器框架,是传统的过程式代码; 和STL都具有易于理解、流畅、高效等优秀特性。

Spirit主要特性:模块性和可扩展性

Spirit不是给你一个大锤,它提供方便打造大锤的正确成分。 Spirit使用基本元素(终结符)和复合元素(产生式)的层次对象组合来模块化递归下降分析器。现在的Spirit版本使用了大量的表达式模版 ("  ", 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是个函数对象: P[F];函数或函数对象的参数取决于分析器的类型,如果分析器的属性为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 sequence

operator>>(parser


5.2  数值分析器(终结符)

Spirit预定义大量的数值分析器,包括符号(无符号)整数分析器,符号(无符号)浮点分析器等。数值分析器可进行进制,小数点左右精度等参数的配置,此外数值分析器的行为是通过数值分析器策略来控制,用户可以自定义策略来实现不同的操作。

uint_parser     无符号整数分析器 ( boost_operator.cpp )

template <

        typename T = unsigned,

        int Radix = 10,

        unsigned MinDigits = 1,

        int MaxDigits = -1 >

    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_list, 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( p[f] )    //  f  not called

eps_p( p ) [f]   //  f  is called

eps_p[f]      //  f  is called

作为条件分析器要求必须不具有副作用(语义动作)。条件分析器的作用是通过 前向匹配(forward-match)  输入来消除语法二义性。二义性和语义动作不能够很好的结合使用,在一个二义性文法中,会产生回溯。当回溯产生时,已触发的语义动作无法回溯。

6.  反操作符 Negation

~eps_p    ~~eps_p

 结果 进行取反操作。

5.5  Directives  ( 指示器)

形式: directive[expression]

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_d和no_actions_d的原理主要时通过将 扫描器策略(Sanner Policy) 组合起来实现不同的功能。规则rule属于一个特殊的分析器(更精确的说是一个或多个分析器),如果将规则放到lexeme_d,as_lower_d或no_actions_d当中,除非你将扫描器和规则关联起来,否则编译器会出现扫描器不匹配错误。( why?)

longest_d

功能:匹配所有可选项,获取一个最长匹配。(仅对于或运算符)

或运算符在spirit框架当中采取短路匹配方式来进行匹配。也就是说对于规则:

rule<> r1 = p1 | p2 | p3 ... | pn, 对于i <= n,如果对于任意的j < i,pj都无法匹配输入,但是pi匹配输入,那么后续的分析器就无需进行匹配。虽然spirit或运算符的短路行为对于具有优先情况的匹配操作可能是非常好的, 但是也存在这样一种情况, 如:

rule<> r2 =  real_p | int_p;

对于输入为"1234",由于整数本身也是实数, 因此该输入永远只匹配real_p,不会匹配int_p;但是如果将规则转变为:

rule<> r2 = int_p | real_p ;

对于输入为"1234",这时输入永远只匹配int_p,不会匹配real_p。但如果输入为: "124321.3242",这种情况下由于或运算符的短路行为,只会用int_p来匹配输入的前部分"124321("."分隔)。这并不是我们想要的结果,通过使用longest_d将规则封装起来,这样就会用所有的选择项来匹配输入并选取一个最长匹配项real_p。

shortest_d

功能:与longest_d相反

limit_d ,min_limit_d和max_limit_d

功能:限定分析器结果范围(对于数值分析器)

虽然数值分析器可以通过模版参数限定数值位数,但是要限定结果范围只能通过limit_d,min_limit_d和max_limit_d来限定。使用方法如下:

limit_d(min, max)[expression] 

min_limit_d(min) [expression] min_limit_d(1900u)[uint_p] >= 1900u 

max_limit_d(max) [expression] max_limit_d(1900u)[uint_p] <= 1900u 


转载:http://blog.chinaunix.net/uid-10716167-id-2934085.html


阅读(2330) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~