编译原理实验一 《词法分析程序设计与实现》

一、实验目的

​加深对词法分析器的工作过程的理解；加强对词法分析方法的掌握；能够采用一种编程语言实现简单的词法分析程序；能够使用自己编写的分析程序对简单的程序段进行词法分析。

二、实验内容

自定义一种程序设计语言，或者选择已有的一种高级语言，编制它的词法分析程序。词法分析程序的实现可以采用任何一种编程语言和编程工具。从输入的源程序中，识别出各个具有独立意义的单词，即关键字、标识符、常数、运算符、界符。并依次输出各个单词的内部编码及单词符号自身值（遇到错误时可显示“Error”，然后跳过错误部分继续显示）。

三、实验要求

1、对单词的构词规则有明确的定义；
2、编写的分析程序能够正确识别源程序中的单词符号；
3、识别出的单词以<种别码，值>的形式保存在符号表中，正确设计和维护符号表；
4、对于源程序中的词法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成整个源程序的词法分析。

四、实验步骤

1、定义目标语言的可用符号表和构词规则；
这里使用简化的C++语言作为编译对象的程序设计语言，考虑从关键字、标识符、常数、运算符、分隔符五个方面描述其构词规则。
(1) 假设一段简单的C++程序代码需要识别的词如下：
① 关键字：if、int、for、while、do、return、break、continue；单词种别码为1；
② 标识符；单词种别码为2；
③ 常数为无符号整形数；单词种别码为3；
④ 运算符包括：+、-、*、/、=、>、<、>=、<=、==；单词种别码为4；
⑤ 分隔符包括：,、;、{、}、(、)； 单词种别码为5。

(2) 考虑该简单C++程序代码的文法的符号串集合 $\Sigma$ 为（综合上面的词的构成）：
Σ = { a , … z , A , … Z , 0 , 1 , … 9 , , + , − , ∗ , / , < , > , = , , , ; , { , } , ( , ) } \Sigma = \{a,…z, A,…Z, 0, 1,…9, _, +, -, *, /, <, >, =, ,, ;, \{, \}, (, )\} Σ={a,…z,A,…Z,0,1,…9,,​+,−,∗,/,<,>,=,,,;,{,},(,)}

(3) 考虑该简单C++程序代码的LEX描述如下：
① AUXILIARY DEFINITION /* 辅助定义 */
k e y → i f ∣ i n t ∣ f o r ∣ w h i l e ∣ d o ∣ r e t u r n ∣ b r e a k ∣ c o n t i n u e l e t t e r → a ∣ b ∣ … ∣ z ∣ A ∣ B ∣ … ∣ Z ∣ _ d i g i t → 0 ∣ 1 ∣ 2 ∣ … ∣ 9 o p e r a t o r → + ∣ − ∣ ∗ ∣ / s e p a r a t o r → , ∣ ; ∣ { ∣ } ∣ ( ∣ ) \begin{align*} & \mathbf { key → if | int | for | while | do | return | break | continue }\\ & \mathbf {letter → a|b|…|z|A|B|…|Z|\_ }\\ & \mathbf {digit → 0|1|2|…|9 }\\ & \mathbf {operator → + | - | * | / }\\ & \mathbf {separator → , | ; | \{ | \} | ( | ) }\\ \end{align*} ​key→if∣int∣for∣while∣do∣return∣break∣continueletter→a∣b∣…∣z∣A∣B∣…∣Z∣_digit→0∣1∣2∣…∣9operator→+∣−∣∗∣/separator→,∣;∣{∣}∣(∣)​

② RECOGNITION RULES /* 识别规则 */

词形	动作
key	{return(1, -)}
letter(letter|digit)*	{return(2, -)}
digit(digit)*	{return(3, -)}
operator|<|>|=|<=|>=|==	{return(4, -)}
separator	{return(5, -)}

注：考虑到<=、>=、==等复合操作符的特殊性，为方便使用类似超前搜索的方法，将<、>、=从operator中分离开来，作为一个单独的部分处理；为了方便实现，将下划线“_”归到letter当中。

2、构造相应的确定有限自动机DFA或者可以编程实现的状态转换图；
对于该简单C++程序代码，根据LEX描述构造状态转换图如下：(关键字 key 和一般标识符的识别方式相同，因此将 key 的识别归在标识符的识别当中，在具体编程实现时再进行区分)

3、为编译程序的具体实现进行必要的准备工作；（使用 C++、STL）
① 准备工作1：从.txt文件当中读取出代码（即文件全部内容）并形成缓存，即将其暂存于一个string对象当中。
实现代码如下。

std::string readFromFileAndTrim(const std::string &path) {
    std::ifstream file(path);  // open a file.
    if (!file.is_open()) {
        std::cerr << "cannot open the file: " << path << std::endl;
        throw std::runtime_error("cannot open the file: " + path);
    }

    std::stringstream buffer;
    buffer << file.rdbuf();  // read the file content to a stringstream
    std::string content = buffer.str();

    return trim(content);  // trimming.
}

② 准备工作2：去除代码段首尾的空白字符；这里仅考虑空格、换行和制表符。
实现代码如下。

/* 删去字符串首尾空白符 */
std::string trim(const std::string& str) {
    size_t first = str.find_first_not_of(" \t\n\r");
    if (first == std::string::npos) {
        return "";  // if all the characters are blank-char, then return ""
    }
    size_t last = str.find_last_not_of(" \t\n\r");
    return str.substr(first, last - first + 1);
}

③ 准备工作3：定义合适的数据结构。
识别出的单词种别码使用枚举类型以便维持可读性。

enum WordType {
   	BEGIN, 
   	KEYWORD, 
   	IDENTIFIER, 
   	CONSTANT, 
   	OPERATOR, 
   	SEPARATOR, 
   	ERROR
};

注：BEGIN是为了符合之前的规定而做出的填充，ERROR指识别出错的情况，也属于种别码。
需要输出的内容将被存储在符号表当中，符号表使用结构体作为每个单词的存储单位；

struct WordToken {
    std::string word;
    WordType type;
    WordToken(const std::string &w, WordType t) {
        word = w;
        type = t;
    }
};

整个符号表使用一个vector对象存储以统一管理，该对象存储所有识别出的单词的结构体。

④ 准备工作4：符号表内容的格式化输出函数。

4、根据上述DFA或者状态转换图，编写源程序，依次读入源程序符号，对源程序进行逐个字符的读入，然后判别再处理，将识别结果（包括识别成功的结果和识别错误的结果）存进符号表对象中，直到源程序结束；
参考思路（部分实现细节不同）：

5. 输出所得符号表的所有内容。

五、实验结果

​实验测试源代码保存在文件test.txt当中，其中包含关键字（int、if、return）、标识符（main、_a7x、c_）、常数（0、86、10）、运算符（=、+、>=、==）、分隔符（,、;、(、)、{、}）以及错误输入（?=、50nb、%），并且首尾均有一定量的空白字符如换行（\n）、空格、制表（\t）等，对应自定义的目标可用符号表内容均包含在内，能够完整的展示程序功能。

​test.txt如下（部分空白位置为空白字符）：

实验识别结果如下：

​可见识别结果正确的单词以(种别码，单词)形式出现，而错误结果则以ERROR:… 形式出现，后面会附加上大致的错误原因，如Unrecognized Character代表词法分析器不能识别该字符等。

六、实验结论

​实验利用自定义的源程序进行测试，结果正确，符合预期结果，测试源码及结果截图和说明如上所示。

七、实验小结

​对于词法分析器，最好还是通过状态转换图或DFA的构造来决定具体编程实现，如果不这样分析而是直接对程序运行过程进行分析也可以得到一个分析程序，但是这样可能会出现很多没有考虑到的情况（比如，部分单词识别错误造成连带识别，使得两个单词被错误识别为一个单词）。

​实验过程中也出现了一些问题，比如对于复合操作符<=、>=、==的识别较为困难，一开始如果直接把<、=、>简单的归于operator当中，则难以进行后续识别，因为operator当中除上述三个字符外的其他符号后面不能接“=”符号，需要对<、>、=符号进行超前搜索，因此将其单独处理比较合适。即当识别到<、>、=符号时，转入另一个状态；还有，针对该语言的标识符组成结构，_符号也属于标识符的一部分，并且所起的作用与字母是相同的，因此将其归类到letter当中方便编程实现。

八、附录

2024.10 最近发现本科时候写的代码太烂 简直不能忍！ 花了点时间重新写了一份勉强能看的代码。👉传送门👈.
相比原来改进的地方：

1. 用状态模式重新实现DFA自动状态机；
2. 改进原始指针的内存问题，统一使用智能指针代替；
3. 改进组织结构、命名空间，模块更加分明；
4. 工程使用CMake进行构建，跨平台、容易移植、方便组织和编译，统一从MSVC转到更主流的GCC下。

计划抽空重新实现所有的编译实验、编写更优雅的代码，最好全部放到一个工程里面形成逻辑闭环。（希望不要流产
tips：编译实验代码太难写？不如使用大佬写的工具生成！

• GNU提供了flex/lex，通过写lex词法规则就能生成词法分析器代码(cpp)，传送门：flex
• GNU提供了bison/yacc，通过写yacc语法规则就能生成语法分析代码(cpp)，传送门：bison
• ANTLR通过写EBNF规则就能生成词法分析器和语法分析器的代码，还支持生成Python、Java、Go、C++等10种目标语言的代码，传送门：ANTLR4