Lemon语法分析生成器_sql

概述 http://www.hwaci.com/sw/lemon/index.html 1、概述 Lemon是一个LALR(1)语法分析器生成器。与GNU Bison和Yacc不同。为了减少编写代码的错误，它使用了一种不同的语法。Lemon使用了一种更为高级的分析引擎（LALR的好处就是产生的状态表比较小），运行速度快，并且该引擎是可重入的和线程安全的。更进一步的，Lemon实现了能够消除资源

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

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

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

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

下面的文章可以帮助理解内部处理流程和相关源码
http://www.gnudeveloper.com/groups/lemon-parser/understanding-lemon-generated-parser.html