序
对于一个源码文件而言,里面的内容只是一个个字符,机器是无法识别的,而词法分析器的作用类似于转义器,将一个个字符拆成若干个有特定意义的词,而这一过程称为词法分析,此时它也不能被机器(或者这个虚拟机)识别
词法分析器
Token,Keyword,界符,常数,运算符
token
以及 keyword
是存在区别的,像token
可以是认为是一个此的描述,如:
const int sum = 100;
typedef struct my_struct{
int a ;
unsigned int b;
char *c;
};
学过语言的都知道,什么是语言关键字。
typedef
,struct
,int
,my_struct
等都可以认为是一个token
,可以简单理解为一个词的代号,而keyword
属于被包含关系,typedef
,struct
,int
它们属于keyword
,因为它们是程序内部定义"词",而my_struct
则属于用于定义的,
像类似于 +,-,*,/
等都属于运算符
其中 const int sum = 100;
中的100
则认为是一个常数.
基本设计
- 首先我们为一个词定义一些
token
,如
typedef enum Token {
EOF = 0,
COMMENT,
IDENT,
__KEYWORD_BEGIN
IF,
ELSE,
SWITCH,
CASE,
RETURN,
// etc...
__KEYWORD_END,
__MATH_BEGIN
Add, // +
Sub, // -
Mul, // *
Quo, // /
Rem, // %
And, // &
Or, // |
__MATH_END
};
可以属于到几个特殊的定义 __XXX_BEING,__XXX_END
这是为了方便后续快速区分这些"词"是属于那些种类
-
其次我们需要定义一个辅助函数,如上所述
const int sum = 100
; 而这100
解析出来应该是个数字而不是一个字符串bool is_dight(char c){ return '0'<=c && c <='9'; }
这一步只处理了一个字符,而后续只需要一直扫描直到不能满足条件为止,如出现一个字母,那么可以认为语法错误,扫描到
;
则认为是结束了bool is_letter(char c) { return ('a' <=c && c <='z') || ('A' <=c && c <='Z'); }
这个函数专门处理一些关键字,和
identity
辅助函数只能处理当前字符,那么如何知道是否满足某个条件,如变量只允许下划线和字母开头,答案就是状态机,类似于一个临时缓冲,将扫描到的字符放入其中方便做检测,而实际开发中其实只需要记录两次偏移的位置就可以拿到这段字符了
分析器的分析流程
分析器其实就是按照一个个遍历的方式将这串文本拆成一个个的token
的过程
typedef struct lex {
unsigned int size; // sizeof the buf length
unsigned int offset; // current read offset
unsigned int line;
char *buf;
};
typedef struct token{
Token __token;
unsigned int line;
};
int lex_next(lex *l,token *tk){
while(l->offset < l ->size){
// lex_skipwhitespace()
switch (l->buf[l->offset]){
case '/':
if (l->buf[l->offset +1] == '/'){
// lex_skipcomment()
tk->__token = COMMENT;
}else{
// maybe is math div
}
break
// etc ... switch
}
}
}
至此,词法分析器的大致原理已经分析完毕了,后续可以参考 AST
以及 语法分析器Grammar
优化
emmm… 本身而言这个可以段可以不写,如果你能看到这,你可以接触更高阶的知识。作为一个由追求的程序员,优化是必须的,去tm的后续优化,哥写代码就是要一边写一边优化 :)
-
I/O 读取优化 通常而言,对于不大的文件,我们直接读取全部内容到内存中,然后进行处理,但是这样会存在一个问题,就是如果文件过大,那么内存会爆,所以需要进行优化,将文件内容分段读取,然后进行处理,这样可以避免一次性读取过多内容,从而避免内存溢出,以及过多的内存碎片。 如上述改为
lex
结构改为固定缓冲,如char buf[512]
并增加一个offset
偏移量和文件编译指针,对于后续其它文件而言都可以复用这个结构。 -
扫描优化 机器不同于人脑,人脑可以可以同时处理多个字符输入,但对于计算机而言,只能一个一个处理,我们可以定义一些非二义性的关键字和词组,如
\\
我们可以立刻判断这是注释,直接goto
到对应的label
,而不是逐个字符判断。直接人为处理 -
伪共享优化 CPU在读取数据时,是以一个缓存行为单位读取的(64byte),假设这个缓存行中有两个long类型的变量a、b,当一个线程A读取a,并修改a,线程A在未写回缓存之前,另一个线程B读取了b,读取的这个b所在的缓存是无效的(前面说的缓存失效),本来是为了提高性能是使用的缓存,现在为了提高命中率,反而被拖慢了,这就是传说中的伪共享。最简单的方式就是以一个缓存行为单位读取,这样就不会存在伪共享问题了。从上述可知
sizeof(lex)== 24
我们只需要填充char byte[40]
让它一次能填满缓冲行即可。更多的可以查看 MESI协议
上述优化完毕的测试结果,对于以下脚本仅需 1.216ns
// this is a comment
int32 a // this is back comment
int32 b=33
float32 c = 3.14
int32 a1 = 0b0101
int32 a2 = 0x123456789abcdef
int32 a3 = 012323
bool d = false
bool c = true
function fib(int32 n) int32 {
if (n < 2){
return n
}
return fib(n-1) + fib(n-2)
}
fib(b)