Sqlite3之Lemon语法解析器初探（1） / 四六文摘

转载请注明出处

看sqlite3源码发现用到了lemon语法解析器，然后发现一本好的lemon教程然后参考里面的例子做了一些例子。

Lemon语法分析器非常小巧只依赖于两个文件。

以下的代码实现一个计算器程序。初步的没有加入词法生成器，直接调用了Parse函数来做运算。代码中包含注释，以下并解释具体点。

//在生成的文件中包含以下头文件

%include

{

#include<stdio.h>

#include "calculator-bak2.h"

#include<malloc.h>

#include<assert.h>

}

//计算器里面类型都是整形

%token_type{int}

//计算符结合方法都是左结合的方法

//之所以分开写是因为下面的运算符级别高于上面的这里是乘除高于加减

%left PLUS MINUS.

%left DIVIDE TIMES.

%syntax_error

{

printf("语法分析错误，非法的表达式了 \n");

//自己的处理代码

}

//意思就是expr定义为一个公式

program ::=expr(A).

{

printf("this %d /n",A);

}

expr(A) ::=expr(B) MINUS expr(C).{A=B-C;}

expr(A) ::=expr(B) PLUS expr(C).{A=B+C;}

expr(A) ::=expr(B) TIMES expr(C).{A=B*C;}

expr(A) ::=expr(B) DIVIDE expr(C).{

A=B/C;

}

//这里可以看到 expr到底是什么了

expr(A) ::= INTEGER(B). {A=B;}

//lemon 的两种符号终结符与非终结符

//终结符来自外面大写非终结符来自内部小写

%code

{

void main()

{

void * pParser = ParseAlloc(malloc);

Parse(pParser,INTEGER,1);

Parse(pParser,PLUS,0);

Parse(pParser,INTEGER,2);

Parse(pParser,0,0);

ParseFree(pParser,free);

}

分析main函数里面代码的执行步骤 expr(A) ::= INTEGER(B). {A=B;} expr(A) ::=expr(B) PLUS expr(C).{A=B+C;} program ::=expr(A).

里面先后执行了这几个步骤

INTEGER(1) > expr(1)

PLUS(0)

INTEGER(2) > expr(2)

expr(1)PLUS(0)expr(2) 匹配到了 A=B+C expr(3)被放到分析stack中然后调用了 printf那个语句

最终打印出来 this 3

接下改变 main（）函数里面code 然后+-乘除混合运算

void * pParser = ParseAlloc(malloc);

Parse(pParser,INTEGER,1);

Parse(pParser,PLUS,0);

Parse(pParser,INTEGER,2);

Parse(pParser,TIMES,1);

Parse(pParser,INTEGER,5);

Parse(pParser,0,0);

ParseFree(pParser,free);

打印结果 this 11 说明是混合运算

可以用结构体替换 INTEGER来进行复杂运算这里不做赘述

编译原理部分知识回顾：

关于编译原理知识的一些回顾，发现书本上学的东西基本都忘得差不多了发现。。真是悲剧，不得不对一些编译原理知识进行一些回顾复习：

自底向上分析可以解决更多的文法分析问题

LR(K)文法及LR(K)分析技术。所谓LR(K)分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看K个输入符号，就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作 (是移进还是按某一产生式进行归约等)。