从这一节开始，进行词法解析器的原理分析和代码实现，我们以C的语法为模板，用C++来进行编译器的代码开发，开发语言任意选择自己熟悉的一种都行。
观察以下代码块，分析其结构。
int main(){int a = 10;string b = "hello world";return a;}
在上一节中我们知道，词法解析就是将源代码中的字符识别成高级语言中定义的各种标识符，如变量和函数。很显然，a、b即为变量，main为函数，int、return为关键字。
常见的词法记号为：标识符(变量/方法)、常量、关键字、运算符、逗号、分号等。
我们的目标是构建一个词法解析器，并输出词法标记的序列，流程如下。
词法解析器可以用状态转换图或者有限自动机的方式实现，我们采用后者中的确定有限自动机，具体定义可以参见编译原理等相关教材。此外也使用正则表达式等工具来构建。
一 定义词法标记
/*** 标记类型*/enum Tag {ID,//标识符INT, CHAR, STR, VOID, BOL,//变量类型NUM,//数字类型ADD, SUB, MUL, DIV, AND, OR,//运算符ASSIGN,//赋值符LPR, RPR, //()LBK, RBK, //[]LBE, RBE, //{}SEM, //;COMMA, //,COL, //:RETURN,END,ERO, //错误标记UKN//未知};
定义词法标记基类。
/*** 词法标记基类*/class Token {public:Tag tag;Token(Tag t);virtual string toString();virtual ~ Token();};
定义词法标记的各种类型，暂只包括标识符、数字类型、字符串和关键字。
class Id : public Token{public:string name;Id(string name);virtual string toString();};class Num : public Token{public:int value;Num(int v);virtual string toString();};class Str : public Token{public:string str;Str(string str);virtual string toString();};class Keyword {public://初始化所有关键字std::tr1::unordered_map<string, Tag> keywords;Keyword();Tag getTag(string name);}
二 构造字符扫描器
class Scanner {public:FILE *file;//源文件char scan();//扫描并返回一个字符Scanner(FILE *file);~Scanner();};
可以一次性读取多个，减少操作文件的次数。
//scan()伪码int readPos = 0;//上次读取的位置char line[100];//一次读取100个int lineLen = fread(line, 1, 100, file);//如果line中存在就不用再操作文件char ch = line[readPos];readPos ++;
三 构造词法解析器
class Lexer {public:FILE *file; //源文件Scanner &scanner; //扫描器char ch; //读取的字符Token* fetch();//有限自动机读取一个词法标记Lexer(Scanner &scanner);~ Lexer();};
有限自动机的实现。
Token *Lexer::fetch() {//循环读取字符直至结束for (;ch != -1;) {Keyword keyword;while (ch == ' ' || ch == 'n' || ch == 't') {//空格、换行符、制表符继续读取下一个ch = scanner.scan();}if(ch == -1){//读取完毕，返回结束标记return new Token(END);}if (ch >= 'a' && ch <= 'z') {//识别标识符: 以小写字符开头return fetchId();} else if (ch >= '0' && ch <= '9') {//识别数字类型: 以数字开头return fetchNum();} else if(ch == '"'){//识别字符串: 以"开头return fetchStr();}else {//识别其他符号return fetchMark();}}return new Token(END);}
识别标识符。
Token *Lexer::fetchId() {Keyword keyword;string id = "";id.push_back(ch);while (ch != -1) {ch = scanner.scan();//如果读到数字或者下划线，则说明是标识符if ((ch >= '0' && ch <= '9') || '_' == ch || (ch >= 'a' && ch <= 'z')) {id.push_back(ch);} else if(ch == 'n'){//换行符，继续读取下一个continue;}else{//否则结束break;}}Tag tag = keyword.keywords[id];//判断是否为关键字return tag ? new Token(tag) : new Id(id);}
我们依次实现ferchNum()、fetchStr()和fetchMark()等函数。注意，数字类型需要先判断其进制。
十进制：以0~9的任意数字组合；八进制：以0开头，0~7的任意数字组合；二进制：以0b开头，0和1的任意组合；十六进制：以0x开头，数字0-9及字母a~z的任意组合。
识别数字类型。
Token* Lexer::fetchNum() {int num = 0;int hex = 2; // 0, 二进制；1，八进制；2，十进制；3，十六进制；char old = ch;ch = scanner.scan();char next = ch;if (old == '0') {//第一个非零为十进制,通过第二个字符判断具体数值进制if (ch == 'b') {hex = 0;} else if (ch == 'x') {hex = 3;} else if (ch = '0' && ch <= '7') {hex = 1;num = convertNum(hex, num, ch);} else if (ch == ' ') {return new Num(num);} else if (ch == 'n') {//继续读} else {return new Token(ERO);}} else {hex = 2;//如果第二个为终止符，直接返回;如果为换行符，继续往下读，否则校验值的类型并追加到num中if (ch == ';') {return new Num(convertNum(hex, num, old));}if (ch != 'n') {//如果是其他类型且不属于数值，返回错误Token *t = validNum(hex, ch);if (t != NULL) {return t;}}}//明确数值类型进行初始值计算num = convertNum(hex, num, old);while (ch != -1) {num = convertNum(hex, num, ch);ch = scanner.scan();if (ch == ';') {return new Num(num);}Token *t = validNum(hex, ch);if (t) {return t;}if (ch == 'n') {continue;}if (ch == ' ') {return new Num(convertNum(hex, num, next));}}return nullptr;}
将单个字符数字转换成相应进制的具体数值。
int convertNum(int type, int origin, int current) {if (current == 'n') {return origin;}if (type == 0) {return origin * 2 + current - '0';} else if (type == 1) {return origin * 8 + current - '0';} else if (type == 2) {return origin * 10 + current - '0';} else if (type == 3) {return origin * 16 + current - '0';}return origin;}
至此，我们完成词法解析器的构造，输出其解析的结果，如下图。
1.一个hello world的诞生
2.词法解析器
3.从自然语言认识文法
4.构造文法
5.语义分析
6.生成中间代码
7.函数的帧栈调用过程
8.汇编
9.编译和链接
10.终于跑起来了
11.多文件编译
12.丰富数据类型
13.流程控制语句
14.编译优化算法
15.文件读取
16.一个线程的实现
17.什么是锁
18.网络编程
19.面向对象
20.其他规划
发表评论