mycompiler1 大学生利用C++构建一个编译器之词法分析器

mycompiler1 大学生利用C++构建一个编译器之词法分析器

文章目录

• 1. 定义语言
• 2. 编译器工作流程
• • 2.1. 编译器处理的两大过程和分层设计
• 3. 词法分析器的实现
• • 3.1. 有限状态机(正则匹配)
  • 3.2. 多个状态机合并成语法分析器
  • 3.3. 不同状态机
  • • 3.3.1. 引号字符串
    • 3.3.2. 关键字或者变量
    • 3.3.3. 操作符
    • 3.3.4. 注释判断
  • 3.4. 词法分析器知识点汇总
  • • 3.4.1. C++工程管理(Makefile)
    • 3.4.2. 词法分析器
    • 3.4.3. 工程项目的收获
• 4. C++正则匹配应用
• 最后的效果

点击进入本文对应的代码

之前有说过要实现一个myos的操作系统, 但是有了操作系统就需要在这系统上运行一些程序呀, 所以这里想着自己定义一个语言, 在做一个编译器, 最后生成可执行的代码放到myos上应该还是不错的; 注意: 不管是操作系统还是编译器, 都有很多人做了很多成熟的小型开源项目, 我也是基于这些项目拿过来学习一下, 并不是真的每一句都是自己的写的, 只能说就像小时候抄作业一样, 拿班级第一的抄一下, 然后在看看人家写的多好, 然后在改进一下, 然后自然就成班级第一了!!! 哈哈哈哈哈哈哈哈, 这样做的目的主要是为了深度了解操作系统和编译器的底层原理和对一些以前只知其一不知其二的知识来一波庖丁解牛 !!!

这里我看的是 程序员的三大浪漫，编译原理，图形学，操作系统

求老仙老师讲的虽然有很多听不懂的地方, 但是一点点啃下来还是有很多收获的, 这里先介绍求老师定义的一门语言(这里就说C语言吧), 编译器的组成, 以及 编译器中词法分析器的编写; 求老师用的是Java和JavaScript, 这里我把他改成C++了, 深深学了一波语言切换!!!

1. 定义语言

1. 注释: // 注释语言 和 /*注释语言*/
2. 关键字和TokenTypes:

        unordered_set<string> KeywordHelper::Keywords = { "var", "int", "float", "bool", "void", "string", "if", "else", "for", "while", "break", "func",  "return"};// 定义Token的类型enum TokenTypes{Null,KeyWord,Variable,Operator,Bracket,String,Boolean,Float,Integer};
   

3. 剩下的跟C语言基本一致

2. 编译器工作流程

首先编译器的工作是将一种程序语言(高级语言) 翻译为另一种程序语言(汇编语言/机器码)的计算机程序

1. 对源文件进行扫描，将源文件的字符流拆分分一个个的词（记号），此为词法分析
2. 根据语法规则将这些记号构造出语法树，此为语法分析
3. 对语法树的各个节点之间的关系进行检查，检查语义规则是否被违背，同时对语法树进行必要的优化，此为语义分析
4. 遍历语法树的节点，将各节点转化为中间代码，并按特定的顺序拼装起来，此为中间代码生成
5. 对中间代码进行优化
6. 将中间代码转化为目标代码
7. 对目标代码进行优化，生成最终的目标程序

具体而言:

最后的例子:

var a = 1 + 4 * 5 的抽象语法树(AST)

最后:
根据抽象语法树生成的中间代码(下面的三地址代码) 更加接近计算机指令, 也可以对三地址代码进行存储, 传输, 优化

t1 = 4 * 5
t2 = 1 + t1
var a = t2

2.1. 编译器处理的两大过程和分层设计

分层设计的难点:

1. 关注度分离, 每一层都有意义(思考), 有产出, 可以独立使用
2. 层足够强大, 每一层都要优质的算法数据机构, 架构技巧解决大量共性问题

3. 词法分析器的实现

目标:

1. 给定程序语言C, 以及C支持的词汇, 从中找出这些词汇, 并为他们标注词性
2. 如果源码中有C中不支持的词汇, 报错并提示

3.1. 有限状态机(正则匹配)

在这里我将每次进入一个状态机作为一个窗口的左部, 然后通过该状态机的不断跳转, 该窗口不断地扩大, 直到右部到头停止状态机, 而此时的窗口就是一个token, 当状态机结束后, 字符串得滑动指针就指向了该窗口的右部, 并返回一个token;

• 正则表达式

1. 用于正则语言的词法, 用一串字符串描述正则语言L接收哪些语言, 而不需要理解这些语言
2. 最早Kleene提出, 在Unix采用后,被大众认可(Grep, Sed等)
3. 正则语言可以被确定, 有限状态的自动机理解

• 正则描述词法

1. 通常我们可以通过正则表达式标书一类词法单元(符号)
2. 关键词可以这样描述(if|else|)
3. 整数可以表述为[+-]?[0-9]+
4. 运算符号可以描述为(+|-|*|/|^|&|||)

• 实例

3.2. 多个状态机合并成语法分析器

根据右侧的多个有限状态机就能处理一个字符串流提取出所有的token了

3.3. 不同状态机

3.3.1. 引号字符串

/*** @brief 字符串的判定* string s = R"("fsadhgydsrh"sagsdahgaerh)"; ==> "fsadhgydsrh"* @param s * @param it * @return Token* */
Token* Token::makeString(string &s, string::iterator &it) {string word = "";int state = 0; // 初始状态为0while(it != s.end()) {char c = *it;it++;switch (state) {case 0:if(c == '"') {state = 1;} else if(c == ''') {state = 2;}word += c;break;case 1:if(c == '"') {word += c;return new Token(String, word);}else {word += c;}break;case 2:if(c == ''') {word += c;return new Token(String, word);}else {word += c;}break;}}cout<<"判断字符串的状态机 出错了兄弟" << endl;return nullptr;
}

3.3.2. 关键字或者变量

下面给出一个状态机转换的代码例子用来说明状态机的具体实现

Token* Token::makeVarOrKeyword(string &s, string::iterator &it){string word="";while(it != s.end()){char lookahead = *it;it++; // 注意这里需要在获得lookahead 后, 就应该it++到下一个, 这样经过该函数后, it指针就指向了下一个if(AlphabetHelper::isLiteral(lookahead)){word += lookahead;}else{it--;break;}// 循环不变式}if(Debug) cout<< "makeVarOrKeyword: 获得的Token字符串是: " <<  word << endl;// 判断关键词OR变量if(KeywordHelper::isKeyword(word)) {return new Token(KeyWord, word);}if(word=="true" || word=="false"){return new Token(Boolean, word);}return new Token(Variable, word);
}

这里可以发现, 函数的入口参数是字符串引用以及这个字符串的一个迭代器引用(迭代器的引用目的是当本次窗口固定了一个token, 也就是一个变量或者keyword, 函数执行完, it 将会指向字符串当前窗口的右部的下一位, 这样就实现了一个滑动的过程), 之所以it-- 是为了解决之前it++ 之后而中断的状态机;

3.3.3. 操作符

这里缺一个图

3.3.4. 注释判断

    // 删除注释if(c == '/') {if(lookahead == '/') {while (++it != s.end() && *it != 'n'){}// it--;continue;}else if(lookahead == '*') {it++; //  /*abc*/def  此时 c='/' lookahead='*' 该句结束后 *it=abool valid = false;while(it != s.end()){char p = *it; // aif(p == '*' && *(it+1) == '/'){it+=2;valid = true;break;}it++;}if(!valid){cout << "注释未匹配, 直接退出" << endl;return {};}continue;}}    

3.4. 词法分析器知识点汇总

根据上面的几个状态机流程, 以及最开始定义的 token和 keyword, 就能够实现语法分析器了, 具体的工程代码我已经开源到了我的gitee, 有需要的可以点击查看

3.4.1. C++工程管理(Makefile)

make 会默认将 src识别为 cpp 保存文件夹, include 识别为 .h 文件, 因此, 直接使用 g++ -o obj/test.o -c src/test.cpp 就可确定 include中的 test.h一起编译成test.o 了

根据上面的分析, 将所有的 cpp 文件保存到src 文件夹中, 所有的 .h 保存到include , 所有的 .o 文件保存到 obj.o 中, 也就是

object=	obj/lexer.o obj/common.o obj/token.o bj/%.o: src/%.cppmkdir -p $(@D)g++ -o $@ -c $<

注意: 由于我们的入口程序放到了 main.cpp 中, 因此main.cpp 不需要在生成 obj/main.o文件中间代码了, 不然就重复了, 所以使用:

g++ -o main obj/lexer.o obj/common.o obj/token.o obj/keyword.o src/main.cpp

关于如何写 .cpp 以及 .h 和 main.cpp

1. 将定义 class, function, enum和使用到的头文件 #include <iostream> 都存到 .h 中
2. 在同名对应的 .cpp 存放函数实现
3. 注意 .h中定义 static 时, class { public: static func1(); } 需要在 .h 中去掉static的标识, 不然 c/C++ 编译器就不知道怎么处理了

3.4.2. 词法分析器

其实词法分析器很简单, 首先是将所有的注释去掉, 定义的宏进行替换, 这些都是根据正则匹配(有限状态机)进行的静态处理, 只要理解了有限状态机, 从文件中读取整个字符串, 进行字符串流式处理即可; 虽然说简单, 但是中间消耗了很大的精力才搞明白有限状态机的各种跳转关系, 以及C++中string迭代器的使用, 当时在思考要不要直接使用python的正则匹配 import re, 直接就可以搞掉各种注释 , 提取各种关键词, 但是最后还是坚持下来利用有限状态机实现了, 一方面python的 正则匹配确实好用, 但是需要消耗的精力就只是对于正则匹配的运用上了, 对于正则匹配的底层依旧不懂, 此外做C++ 的工程项目, 确实令人收获满满, 因为所有的代码都需要自己做, 没有现成的 API, 是对自己coding 能力的一种考验;

3.4.3. 工程项目的收获

词法分析器也算是一个小项目了, 通过这几天的熬夜coding, 终于根据编译器原理中涉及到的有限状态机实现正则匹配处理字符串流的token, 这里面最大的收获是懂得了一个项目不管是性能, 效果, 还是进展速度, 都离不开最初的框架设计, 如果能够提前把几种有限状态机的模型搭建出来(一边翻书一边刷视频一边coding最后才总结出来的有限状态机图片), 按照集中有限状态机在进行coding, 一定会比直接根据需求coding效果会好很多; 所以这里最核心的东西就是一个项目确定之后, 一定一定要把流程图或者这种状态机图给搞出来, 然后在确定不同的层(keyward → token → lexer), 最后在coding, 最后在coding

还有一个收获必须要提一下, 每写一个 function, 一定要对应写一个测试用例进行检验, 这里可以使用 assert(true) 也可以尝试学习 GoogleTest

4. C++正则匹配应用

/** @description: * @Author: zjq* @Data: Do not edit* @FilePath: /code/regex_c/regex_all.cpp* 永远不要停下前进的脚步*/#include <regex>
#include <iostream>using namespace std;class RegexTest{
public:// 正则匹配static void RegexMatch(string source_string, regex regex_string){if (regex_match(source_string, regex_string))	{cout << " regex " << source_string << endl;}else{cout << " not regex " << source_string << endl;}}// 正则匹配并保存结果static void RegexMatch(string source_string, regex regex_string, smatch& result){if (regex_match(source_string.cbegin(),d(),result,regex_string)){cout << " regex: " << result.str() << endl;;}	else{cout << " not regex " << endl;}}// 正则搜索static void RegexSearch(string source_string, regex regex_string, smatch& result){if (regex_search(source_string, result, regex_string))	{cout << result.str() << endl;} 	else	{cout << "no regex" << endl;}}// 正则迭代器搜索static void RegexSearchIterator(string source_string, regex regex_string, smatch& result){sregex_iterator start(source_string.cbegin(), d(), regex_string);sregex_iterator end;for (auto it = start; it != end; it++)	{result = *it;cout << result.str() << endl;cout << "result size: " << result.size() << endl;cout << "sub regex:" << result.str(1) << endl;}}// 正则替换static void RegexReplace(string source_string, string replace_string, regex regex_string, string& result){result = regex_replace(source_string, regex_string, replace_string);cout << "after replace: " << result << endl;}
private:};int regex_test(){// 次数：+表示一次或多次，？表示0次或1次， *表示0次或多次// {n}表示n次，{n,}表示n次或多次，{n,m}表示n到m次// ()里表示子正则// 匹配数字用d+ 、d*string digital_string = "123456789";       // 字符串regex regexNumber1(R"(d*)");              // 正则表达式，R表示去掉转义RegexTest::RegexMatch(digital_string, regexNumber1);regex regexNumber2(R"(d+)");              // 正则表达式，R表示去掉转义RegexTest::RegexMatch(digital_string, regexNumber2);// 匹配字母。string character_string = "abcdEfsGHHdsasaskkKKKKss";regex  regex26Character("[a-zA-Z]+");       // 匹配26个英文字母RegexTest::RegexMatch(character_string, regex26Character);// 匹配数字字母组合string digital_character_string = "1234abcE45678GHHdabc123456aadddsss1457";regex  regexDigitalCharacter("[1-4]+[a-zA-Z]{4}[4-8]+[a-zA-Z]{4}");  // 匹配字母数组组合RegexTest::RegexMatch(digital_character_string, regexDigitalCharacter);// 将匹配结果输出regex regex_digital(R"(d+)");smatch result;RegexTest::RegexMatch(digital_string, regex_digital, result);// 正则搜索RegexTest::RegexSearch(digital_character_string, regex_digital, result);// 正则搜索 regex regex_complex(R"(abcw+?d)"); // 搜索abcE45678GHHd // ？关闭贪婪模式RegexTest::RegexSearch(digital_character_string, regex_complex, result);RegexTest::RegexSearchIterator(digital_character_string, regex_digital, result); // 搜索输出数字string digital_character_string2 = "Aabc123efgaffffggggabc456efgacccccccabc789efg";regex regex_complex2(R"(abc(d+)efg)");RegexTest::RegexSearchIterator(digital_character_string2, regex_complex2, result); // abc数字efg// 正则替换string output_string;regex replace_regex(R"([a-z])"); // 所有的英文字母regex replace_regex_icase(R"([a-z])",regex::icase); // 所有的英文字母,icase表示忽略大小写string replace_string = ""; // 替换为空,替换时是每个字符的匹配RegexTest::RegexReplace(digital_character_string2, replace_string, replace_regex, output_string);RegexTest::RegexReplace(digital_character_string2, replace_string, replace_regex_icase, output_string);return 0;
}int main(int argc, char const *argv[])
{regex_test();return 0;
}/*
(base) zjq@DESKTOP-82TMKG6:regex_c$ g++ regex_all.cpp && ./a.out regex 123456789regex 123456789regex abcdEfsGHHdsasaskkKKKKssnot regex 1234abcE45678GHHdabc123456aadddsss1457regex: 123456789
1234
abcE45678GHHd
1234
result size: 1
sub regex:
45678
result size: 1
sub regex:
123456
result size: 1
sub regex:
1457
result size: 1
sub regex:
abc123efg
result size: 2
sub regex:123
abc456efg
result size: 2
sub regex:456
abc789efg
result size: 2
sub regex:789
after replace: A123456789
after replace: 123456789
*/

最后的效果

zjq@:mylexer$ make clean && make
-----需要解析的code如下----
int a=0;//fhjkg
float c;/* asgfasharh */sagas;//fsfsstring b = 234235;string ss = "//asharhaerh"; /*fasrhdsarh*/string ss = "//asharhaerh/*  ashsaedrhsjedr */"; //sadjase"fsadar " hkla?? float a = 23;
{int b=34;}"sdgsdgh"
a+b 23+3 32+-43
return abc
----------
type:KeyWord value:int
type:Variable value:a
type:Operator value:=
type:Integer value:0
type:KeyWord value:float
type:Variable value:c
type:Variable value:sagas
type:KeyWord value:string
type:Variable value:b
type:Operator value:=
type:Integer value:234235
type:KeyWord value:string
type:Variable value:ss
type:Operator value:=
type:String value:"//asharhaerh"
type:KeyWord value:string
type:Variable value:ss
type:Operator value:=
type:String value:"//asharhaerh/*  ashsaedrhsjedr */"
type:KeyWord value:float
type:Variable value:a
type:Operator value:=
type:Integer value:23
type:Bracket value:{
type:KeyWord value:int
type:Variable value:b
type:Operator value:=
type:Integer value:34
type:Bracket value:}
type:String value:"sdgsdgh"
type:Variable value:a
type:Operator value:+
type:Variable value:b
type:Integer value:23
type:Operator value:+
type:Integer value:3
type:Integer value:32
type:Operator value:+
type:Integer value:-43
type:KeyWord value:return
type:Variable value:abc