@H_403_2@http://www.hwaci.com/sw/lemon/index.html
@H_403_2@1、概述
@H_403_2@ Lemon是一个LALR(1)语法分析器生成器。与GNU Bison和Yacc不同。为了减少编写代码的错误，它使用了一种不同的语法。Lemon使用了一种更为高级的分析引擎（LALR的好处就是产生的状态表比较小），运行速度快，并且该引擎是可重入的和线程安全的。更进一步的，Lemon实现了能够消除资源泄漏的特性，适合于要求长时间稳定运行的程序。
@H_403_2@操作的原理
@H_403_2@Lemon的主要功能就是是把一个特定语言的上下文无关文法（CFG）翻译成C语言的语法分析器例程（routine）。程序有两个输入：
@H_403_2@a).语法规范文件(.y)
@H_403_2@b).分析器模板文件
@H_403_2@典型的，程序员只需提供语法规范即可。Lemon自带了一个语法分析器模板，这对大多数的应用足够了。如果需要的话，用户可以替换一个新的分析器模板文件。
@H_403_2@根据命令行参数，Lemon会产生下面文件中的一个到三个：
@H_403_2@1).分析器的C语言代码(.c file)
@H_403_2@2).一个头文件，为每个终结符定义了一个整型ID(.h file)
@H_403_2@3).描述产生的语法分析器的状态表的信息文件(.out file)
@H_403_2@完整的源代码包含在两个文件中，lemon.c就是生成器本身。一个单独的文件lempar.c是lemon产生语法分析子程序需要的模板文件。
@H_403_2@可以参考sqlite数据库引擎。lemon目前作为sqlite项目的一部分维护。
@H_403_2@http://www.sqlite.org/src/doc/trunk/doc/lemon.html
@H_403_2@关于lemon的一个比较不错的指南：
@H_403_2@http://freshmeat.net/articles/lemon-parser-generator-tutorial
@H_403_2@2、使用
@H_403_2@Lemon 的command line option
@H_403_2@-m 不产生 header file (no .h file)
@H_403_2@-q 不产生 state report (no .out file)
@H_403_2@-b 简易 state report (brief .out)
@H_403_2@-c 取消state table 压缩,debug语法错误较容易
@H_403_2@-g 去除注解,及action routine. 把纯文法档输出到stdout
@H_403_2@-s Summary
@H_403_2@Lemon不会生成一个完整的、可以运行的程序。用户必须通过调用其中的子例程生成一个完整的分析器。
@H_403_2@Lemon parser 是Token Scanner取得token时,调用Parser处理得到的token. 而Yacc/Bison 是parser需要一个token时调用Token Scanner解析语句.
@H_403_2@1). 程序在使用Lemon生成的分析器之前，必须创建一个分析器
@H_403_2@ void* ParserAlloc(void *(*mallocProc)(size_t));
@H_403_2@2). 当程序不再使用分析器时，应该回收为其分配的内存。
@H_403_2@ void ParserFree( void *p,/* The parser to be deleted */
@H_403_2@ void (*freeProc)(void*) /* Function used to reclaim memory */);
@H_403_2@3). Parse，Lemon生成的分析器的核心例程，每当toekn scanner解析出一个toekn时,叫用Lemon parser函数，即将切分的词传递给Parse，进行语法分析。
@H_403_2@ void Parser(
@H_403_2@ void *p,/* The parser */
@H_403_2@ int hTokenID,/* The major token code number */
@H_403_2@ Token sTokenData,/* The value for the token */
@H_403_2@ Parse* pArg /* Optional %extra_argument parameter */ )
@H_403_2@hTokenID 是一个整数对到文法的终端符号,(lemon 产生之.h file)
@H_403_2@sTokenData 终端符号的原始字串,或是终端符号的值
@H_403_2@pArg 程式员自定之资料结构,Lemon不作修改,直接传给action routine.
@H_403_2@通过 %extra_argument 来定义
@H_403_2@3. Lemon parser 的语法
@H_403_2@1). 终结符与非终结符(Terminals and Nonterminals)
@H_403_2@ 终结符通常是大写的字符串(数字或字母)。非终结符是小写的字符串(数字或字母)。
@H_403_2@Terminal表示解析已经完成,不再有新的状态变化.
@H_403_2@Nonterminal表示需要文法来转变. 让它最后到达终端符号
@H_403_2@2). Precedence Rules 优先级规则
@H_403_2@Lemon采用与Yacc和Bison相同的方法处理歧义性问题。移进/规约冲突，则选择移进；规约/规约冲突，则选择先出现的规则。
@H_403_2@同样，Lemon也允许通过优先级规则来解决冲突。
@H_403_2@%left,%right,%nonassoc 指定终端符号的结合优先顺序,最先出现的优先级最低,越后面的优先级越高，在同一行的优先顺序一样例如：
@H_403_2@%left AND.
@H_403_2@%left OR.
@H_403_2@%nonassoc EQ NE GT GE LT LE.
@H_403_2@%left PLUS MINUS.
@H_403_2@%left TIMES DIVIDE MOD.
@H_403_2@%right EXP NOT.
@H_403_2@a AND b OR c 会处理成 a AND (b OR c).
@H_403_2@a AND b AND c 会处理成 (a AND b) AND c
@H_403_2@a EXP b EXP c 会处理成 a EXP (b EXP c)
@H_403_2@a EQ b EQ c 会产生一个错误
@H_403_2@通常优先顺序适用于到多数的文法规则,如果在某一规则想用暂时更改. 可以在规则后使用方括符号. 放在规则结束后,C动作程式前. 例如
@H_403_2@expr = MINUS expr. [NOT] 告诉Lemon 这里MINUS 的优先等级跟"NOT"一样.
@H_403_2@Lemon 是LALR parser,所以使用%left 会比使用%right 更有效率,且节省堆栈空间.
@H_403_2@3).Lemon的特殊文法指令
@H_403_2@%parse_accept
@H_403_2@定义parser语法分析成功时的动作
@H_403_2@eg. %parse_accept { printf("parsing complete!\n"); }
@H_403_2@%parse_failure
@H_403_2@定义parser 失败时的动作
@H_403_2@eg. %parse_failure {
@H_403_2@fprintf(stderr,"Giving up. Parser is hopelessly lost...\n"); }
@H_403_2@%Syntax_error
@H_403_2@语法错误时,如果有定义这个指令,就首先用此指令
@H_403_2@然后Lemon会尝试从堆栈移除发生错误的非终端规则,然后从这非终端符号的其他规则重新处理. 若是这过程堆栈被归零,就调用%parse_failure
@H_403_2@%stack_overflow
@H_403_2@分析器内部堆栈溢出的处理，通常输出错误信息，重置分析器
@H_403_2@eg. %stack_overflow {
@H_403_2@fprintf(stderr,"Giving up. Parser stack overflow\n"); }
@H_403_2@Lemon 是LALR,使用左边递回,会使用较少堆栈空间.
@H_403_2@list ::= list ATOM. #good
@H_403_2@list ::=.
@H_403_2@list ::= ATOM list. #bad!
@H_403_2@list ::=.
@H_403_2@%stack_size
@H_403_2@增加堆叠空间,预设值是100
@H_403_2@eg. %stack_size 2000
@H_403_2@%start_symbol
@H_403_2@Lemon 预设从第一个非终端符号的规则开始处理,使用这个指令,可以改变初始的第一个规则.
@H_403_2@eg. %start_symbol prog
@H_403_2@%type
@H_403_2@定义某个非终端符号的结构，通常，每个非终结符都有各自的数据类型。例如，通常非终结符为指向的分析树的根结点的数据类型指针，该根结点包含非终结符的所有信息。
@H_403_2@eg. %type expr {Expr*}
@H_403_2@%token_type
@H_403_2@定义终端符号的相关结构体类型,所有终端符号的结构体都一样. 用于Parse()的第3个参数. 预设结构是"int".
@H_403_2@eg. %token_type {Token*}
@H_403_2@%destructor
@H_403_2@非终端符号的析构.
@H_403_2@每当非终端符号从堆叠弹出时,可以叫用解构的C动作.
@H_403_2@有这些情形会用到 %destructor
@H_403_2@a). 运行ParseFree()
@H_403_2@b). 因为错误处理,从堆栈弹出
@H_403_2@b). 当一个规则发生规约，而非终端符号右边没有动作程序
@H_403_2@如果当一个规则规约且有C动作程序,则由该动作程序负责资源释放相关动作. 而不会执行%destructor
@H_403_2@%token_destructor
@H_403_2@动作原理跟%destructor一样,但是只针对终端符号。
@H_403_2@透过%token_destructor & %destructor的设计可以减少内存资源泄漏.
@H_403_2@下面的文章可以帮助理解内部处理流程和相关源码
@H_403_2@http://www.gnudeveloper.com/groups/lemon-parser/understanding-lemon-generated-parser.html
