编译原理课程设计-词法分析器设计(C语言)
发布网友
发布时间：2022-04-23 07:32
共3个回答
懂视网
时间：2022-05-06 15:12
您现在的位置：首页>教程>编程开发>mssql数据库 > mixer:sql词法分析器设计 mixer:sql词法分析器设计 感谢 3lian8 的投递 时间：2014-03-25 来源：三联教程 介绍 mixer希望在proxy这层就提供自定义路由，sql黑名单，防止sql注入攻击等功能，而这些的基石就在
您现在的位置：首页 > 教程 > 编程开发 > mssql数据库 > mixer:sql词法分析器设计
mixer:sql词法分析器设计
感谢 3lian8 的投递 时间：2014-03-25 来源：三联教程
介绍
mixer希望在proxy这层就提供自定义路由，sql黑名单，防止sql注入攻击等功能，而这些的基石就在于将用户发上来的sql语句进行解析。也就是我最头大的词法分析和语法分析。
到现在为止，我只是实现了一个比较简单的词法分析器，用以将sql语句分解成多个token。而对于从token在进行语法分析，构建sql的AST，，我现在还真没啥经验(编译原理太差了)，急需牛人帮忙。
所以，这里只是简单介绍一下mixer的词法分析。
tokenize
在很多地方，我们都需要进行词法分析，通常会有几种方式：
使用一个强大的工具，譬如lex，mysql-proxy就用的这种方式
使用正则表达式
state machine
对于使用工具，我觉得有一个不怎么好的地方在于学习成本，譬如我用lex的时候就需要学习它的语法，同时通过工具生成的代码可读性都不怎么好，代码量大，更严重的是可能会比较慢。所以mysql自身也是自己实现一个词法分析模块。
而对于正则表达式，性能问题可能是一个很需要考虑的，而且复杂度并不比使用类似lex这样的工具低。
状态机可能是我觉得自己动手实现词法解析一个很好的方式，对于sql的词法解析，我觉得使用state machine的方式来自己写一个难度并不大，所以mixer自己实现了一个。
state machine
通常，一个状态机的实现采用的是state + action + switch的做法，可能如下：
?
1
2
3
4
5
6
7
8
switch state {
case state1:
state = action1()
case state2:
state = action2()
case state3:
state = action3()
}
对于一个state，我们通过switch知道它将会由哪一个action进行处理，而对于每一个action，我们则知道执行完成之后下一个state是什么。
对于上面的实现，如果state过多，可能会导致太多的case语句，我们可以通过state function进行简化。
一个state function就是执行当前的state action，并且直接返回下一个state function。
我们可以这样做：
?
1
2
3
4
5
type stateFn func(*Lexer) stateFn
for state := startState; state != nil {
state = state(lexer)
}
所以我们需要实现的就是每一个state function以及对应的它的下一个需要执行的state function。
mixer lexer
mixer的词法分析实现主要参考这个。主要实现在parser模块。
对于一个lexer，需要提供的是NextToken的功能，供外部获取下一个token，从而进行后续的操作(譬如语法分析)。
lexer的next token如下：
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func (l *Lexer) NextToken() (Token, error) {
for {
select {
case t := <-l.tokens:
return t, nil
default:
if l.state == nil {
return Token{TK_EOF, ""}, l.err
}
l.state = l.state(l)
if l.err != nil {
return Token{TK_UNKNOWN, ""}, l.err
}
}
}
}
tokens是一个channel，每次state解析的token都会emit到这个channel上面，供NextToken获取，如果channel为空了，则再次调用state function。
可以看到，用go实现一个词法解析是很容易的事情，剩下的就是写相应的state function用来解析sql。
todo
mixer的词法分析还有很多不完善的地方，譬如对于科学计数法数值的解析就不完善，后续准备参考mysql官方的词法分析模块在好好完善一下。
相关文章
标签:
[返回三联首页] [返回mssql数据库栏目] / [加入三联文集]
热心网友
时间：2022-05-06 12:20
#include "stdio.h" /*定义I/O库所用的某些宏和变量*/
#include "string.h" /*定义字符串库函数*/
#include "conio.h" /*提供有关屏幕窗口操作函数*/
#include "ctype.h" /*分类函数*/
char prog[80]={'\0'},
token[8]; /*存放构成单词符号的字符串*/
char ch;
int syn, /*存放单词字符的种别码*/
n,
sum, /*存放整数型单词*/
m,p; /*p是缓冲区prog的指针，m是token的指针*/
char *rwtab[6]={"begin","if","then","while","do","end"};
void scaner(){
m=0;
sum=0;
for(n=0;n<8;n++)
token[n]='\0';
ch=prog[p++];
while(ch==' ')
ch=prog[p++];
if(isalpha(ch)) /*ch为字母字符*/{
while(isalpha(ch)||isdigit(ch)) /*ch 为字母字符或者数字字符*/{
token[m++]=ch;
ch=prog[p++];}
token[m++]='\0';
ch=prog[p--];
syn=10;
for(n=0;n<6;n++)
if(strcmp(token,rwtab[n])==0) /*字符串的比较*/{
syn=n+1;
break;}}
else
if(isdigit(ch)) /*ch是数字字符*/{
while(isdigit(ch)) /*ch是数字字符*/{
sum=sum*10+ch-'0';
ch=prog[p++];}
ch=prog[p--];
syn=11;}
else
switch(ch){
case'<':m=0;token[m++]=ch;ch=prog[p++];
if(ch=='>'){
syn=21;
token[m++]=ch;}
else if(ch=='='){
syn=22;
token[m++]=ch;}
else{
syn=20;
ch=prog[p--];}
break;
case'>':m=0;token[m++]=ch;ch=prog[p++];
if(ch=='='){
syn=24;
token[m++]=ch;}
else{
syn=23;
ch=prog[p--];}
break;
case':':m=0;token[m++]=ch;ch=prog[p++];
if(ch=='='){
syn=18;
token[m++]=ch;}
else{
syn=17;
ch=prog[p--];}
break;
case'+':syn=13;token[0]=ch;break;
case'-':syn=14;token[0]=ch;break;
case'*':syn=15;token[0]=ch;break;
case'/':syn=16;token[0]=ch;break;
case'=':syn=25;token[0]=ch;break;
case';':syn=26;token[0]=ch;break;
case'(':syn=27;token[0]=ch;break;
case')':syn=28;token[0]=ch;break;
case'#':syn=0;token[0]=ch;break;
default:syn=-1;}}
main()
{
printf("\n\nThe significance of the figures:\n"
"1.figures 1 to 6 said Keyword\n"
"2.figures 10 and 11 said Other indicators\n"
"3.figures 13 to 28 said Operators\n");
p=0;
printf("\nplease input string:\n");
do {
ch=getchar();
prog[p++]=ch;
}while(ch!='#');
p=0;
do{
scaner();
switch(syn){
case 11: printf("(%d,%d)\n",syn,sum);break;
case -1: printf("\n ERROR;\n");break;
default: printf("(%d,%s)\n",syn,token);
}
}while(syn!=0);
getch();
}
程序测试结果
对源程序begin x:=9: if x>9 then x:=2*x+1/3; end #的源文件，经过词法分析后输出如下图5-1所示：
具体的你在修改修改吧
热心网友
时间：2022-05-06 13:38
定义：
词法分析器的功能输入源程序，按照构词规则分解成一系列单词符号。单词是语言中具有意义的最小单位，包括关键字、标识符、运算符、界符和常量等
(1) 关键字 是由程序语言定义的具有固定意义的标识符。例如，Pascal 中的begin，end，if，while都是保留字。这些字通常不用作一般标识符。
(2) 标识符 用来表示各种名字，如变量名，数组名，过程名等等。
(3) 常数 常数的类型一般有整型、实型、布尔型、文字型等。
(4) 运算符 如+、-、*、/等等。
(5) 界符 如逗号、分号、括号、等等。
输出：
词法分析器所输出单词符号常常表示成如下的二元式：
(单词种别，单词符号的属性值)
单词种别通常用整数编码。标识符一般统归为一种。常数则宜按类型（整、实、布尔等）分种。关键字可将其全体视为一种。运算符可采用一符一种的方法。界符一般用一符一种的方法。对于每个单词符号，除了给出了种别编码之外，还应给出有关单词符号的属性信息。单词符号的属性是指单词符号的特性或特征。
示例：
比如如下的代码段：
while(i>=j) i--
经词法分析器处理后，它将被转为如下的单词符号序列：
<while, _>
<(, _>
<id, 指向i的符号表项的指针>
<>=, _>
<id, 指向j的符号表项的指针>
<), _>
<id, 指向i的符号表项的指针>
<--, _>
<;, _>
词法分析分析器作为一个子程序
词法分析是编译过程中的一个阶段，在语法分析前进行。词法分析作为一遍，可以简化设计，改进编译效率，增加编译系统的可移植性。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。
