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
