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 overflown"); } 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
http://blog.csdn.net/yawsh/article/category/825966
http://download.csdn.net/detail/larryliuqing/4142000 (编辑:李大同)
【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!
|