注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

中吴南顾惟一笑

成功法则就是那19个字

 
 
 

日志

 
 

Lemon语法分析生成器  

2011-01-24 18:17:49|  分类: R&D |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://www.hwaci.com/sw/lemon/index.html

1、概述
    Lemon是一个LALR(1)语法分析器生成器。与GNU Bison和Yacc不同。为了减少编写代码的错误,它使用了一种不同的语法。Lemon使用了一种更为高级的分析引擎(LALR的好处就是产生的状态表比较小),运行速度快,并且该引擎是可重入的和线程安全的。更进一步的,Lemon实现了能够消除资源泄漏的特性,适合于要求长时间稳定运行的程序。

操作的原理
Lemon的主要功能就是是把一个特定语言的上下文无关文法(CFG)翻译成C语言的语法分析器例程(routine)。程序有两个输入:

a).语法规范文件(.y)
b).分析器模板文件

典型的,程序员只需提供语法规范即可。Lemon自带了一个语法分析器模板,这对大多数的应用足够了。如果需要的话,用户可以替换一个新的分析器模板文件。

根据命令行参数,Lemon会产生下面文件中的一个到三个:

1).分析器的C语言代码(.c file)
2).一个头文件,为每个终结符定义了一个整型ID(.h file)
3).描述产生的语法分析器的状态表的信息文件(.out file)


完整的源代码包含在两个文件中,lemon.c就是生成器本身。一个单独的文件lempar.c是lemon产生语法分析子程序需要的模板文件。

可以参考SQLite数据库引擎。lemon目前作为SQLite项目的一部分维护。
http://www.sqlite.org/src/doc/trunk/doc/lemon.html

关于lemon的一个比较不错的指南:
http://freshmeat.net/articles/lemon-parser-generator-tutorial


2、使用

Lemon 的command line option
-m 不产生 header file (no .h file)
-q 不产生 state report (no .out file)
-b 简易 state report (brief .out)
-c 取消state table 压缩, debug语法错误较容易
-g 去除注解, 及action routine. 把纯文法档输出到stdout
-s Summary

Lemon不会生成一个完整的、可以运行的程序。用户必须通过调用其中的子例程生成一个完整的分析器。
Lemon parser 是Token Scanner取得token时, 调用Parser处理得到的token. 而Yacc/Bison 是parser需要一个token时调用Token Scanner解析语句.

1). 程序在使用Lemon生成的分析器之前,必须创建一个分析器
    void* ParserAlloc(void *(*mallocProc)(size_t));

2). 当程序不再使用分析器时,应该回收为其分配的内存。
    void ParserFree( void *p,                    /* The parser to be deleted */
                                  void (*freeProc)(void*)     /* Function used to reclaim memory */);


3). Parse,Lemon生成的分析器的核心例程,每当toekn scanner解析出一个toekn时, 叫用Lemon parser函数,即将切分的词传递给Parse,进行语法分析。
    void Parser(
      void *p,                                 /* The parser */
      int hTokenID,                        /* The major token code number */
      Token sTokenData,                /* The value for the token */
      Parse* pArg                            /* Optional %extra_argument parameter */    )

hTokenID 是一个整数对到文法的终端符号, (lemon 产生之.h file)
sTokenData 终端符号的原始字串, 或是终端符号的值
pArg 程式员自定之资料结构, Lemon不作修改, 直接传给action routine.
通过 %extra_argument 来定义

3. Lemon parser 的语法

1). 终结符与非终结符(Terminals and Nonterminals)
  终结符通常是大写的字符串(数字或字母)。非终结符是小写的字符串(数字或字母)。
Terminal表示解析已经完成, 不再有新的状态变化.
Nonterminal表示需要文法来转变. 让它最后到达终端符号

2). Precedence Rules 优先级规则
Lemon采用与Yacc和Bison相同的方法处理歧义性问题。移进/规约冲突,则选择移进;规约/规约冲突,则选择先出现的规则。
同样,Lemon也允许通过优先级规则来解决冲突。

%left, %right, %nonassoc 指定终端符号的结合优先顺序, 最先出现的优先级最低, 越后面的优先级越高,在同一行的优先顺序一样例如:
%left AND.
%left OR.
%nonassoc EQ NE GT GE LT LE.
%left PLUS MINUS.
%left TIMES DIVIDE MOD.
%right EXP NOT.

a AND b OR c 会处理成 a AND (b OR c).
a AND b AND c 会处理成 (a AND b) AND c
a EXP b EXP c 会处理成 a EXP (b EXP c)
a EQ b EQ c 会产生一个错误

通常优先顺序适用于到多数的文法规则, 如果在某一规则想用暂时更改. 可以在规则后使用方括符号. 放在规则结束后, C动作程式前. 例如
expr = MINUS expr. [NOT] 告诉Lemon 这里MINUS 的优先等级跟"NOT"一样.

Lemon 是LALR parser, 所以使用%left 会比使用%right 更有效率, 且节省堆栈空间.


3).Lemon的特殊文法指令

%parse_accept
定义parser语法分析成功时的动作
eg. %parse_accept { printf("parsing complete!\n"); }

%parse_failure
定义parser 失败时的动作
eg. %parse_failure {
fprintf(stderr,"Giving up. Parser is hopelessly lost...\n"); }

%syntax_error
语法错误时, 如果有定义这个指令, 就首先用此指令
然后Lemon会尝试从堆栈移除发生错误的非终端规则, 然后从这非终端符号的其他规则重新处理. 若是这过程堆栈被归零, 就调用%parse_failure

%stack_overflow
分析器内部堆栈溢出的处理,通常输出错误信息,重置分析器
eg. %stack_overflow {
fprintf(stderr,"Giving up. Parser stack overflow\n"); }
Lemon 是LALR, 使用左边递回, 会使用较少堆栈空间.

list ::= list ATOM. #good
list ::=.

list ::= ATOM list. #bad!
list ::=.


%stack_size
增加堆叠空间, 预设值是100
eg. %stack_size 2000

%start_symbol
Lemon 预设从第一个非终端符号的规则开始处理, 使用这个指令, 可以改变初始的第一个规则.
eg. %start_symbol prog


%type
定义某个非终端符号的结构,通常,每个非终结符都有各自的数据类型。例如,通常非终结符为指向的分析树的根结点的数据类型指针,该根结点包含非终结符的所有信息。
eg. %type expr {Expr*}

%token_type
定义终端符号的相关结构体类型, 所有终端符号的结构体都一样. 用于Parse()的第3个参数. 预设结构是"int".
eg. %token_type {Token*}

%destructor
非终端符号的析构.
每当非终端符号从堆叠弹出时, 可以叫用解构的C动作.
有这些情形会用到 %destructor
a). 运行ParseFree()
b). 因为错误处理, 从堆栈弹出
b). 当一个规则发生规约,而非终端符号右边没有动作程序


如果当一个规则规约且有C动作程序, 则由该动作程序负责资源释放相关动作. 而不会执行%destructor

%token_destructor
动作原理跟%destructor一样, 但是只针对终端符号。

透过%token_destructor & %destructor的设计可以减少内存资源泄漏.

下面的文章可以帮助理解内部处理流程和相关源码
http://www.gnudeveloper.com/groups/lemon-parser/understanding-lemon-generated-parser.html
  评论这张
 
阅读(2246)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017