note.md · 周逸群/lex_analysis

#  框架

进一步优化包括状态机、错误处理、开关输出、测试样例。

##　==重点==

1. 注释是怎么处理的？
2. 词法分析处理哪些错误?
3. **工作流：<u>整体状态机</u>- 错误分析-测试样例- 错误处理功能- 输入输出开关- 撰写文档**
4. 一个词语结束后必然是空格？不一定。如何发现错误。词法分析中的错误
5. 如何处理正负数
6. 词法分析-100识别为intCONST 100。这个值显然不能够输入到语法分析中。 实际上词法分析单独处理正负号。
7. 词法分析实际上将源程序完整地翻译了出来。不会遗漏任何信息。
8. 词法分析中的错误包括= 读入不合法的字符，语言中不存在以此打头的单词. 001abc
9. 001abc 
10. 词法分析：补充字符串到数字的转换。
11. 词法分析只管切开词。确保每个词是合法的。词语间的关系与之无关。
12. 标识符不能有下划线
    1. ![image-20220417202155738](C:\Users\lenovo\AppData\Roaming\Typora\typora-user-images\image-20220417202155738.png)

13. 词法分析需要支持的错误

14.

## 问题范围

1. 识别源程序中的单词，记录类别与属性
2. 支持报错
3. 能够开关输入输出
4. 提供了完整的测试样例

## 状态机

完整＋　各部分细分

##　错误处理

错误处理具体包括非法标识符(转到常数处理过程中发现字母下划线，错误的运算符和操作符，注释未终止、括号不匹配。

![image-20220417202404143](D:\2022_Spring\ROS\IMU问题\image-20220417202404143.png)

词法分析涉及的错误仅此一类。具体来说，词法分析错误处理的要求是避免生成不符合词法的词语。

1. 对于非法字符：在初始状态检测即可。
2. 对于字符常量和字符串常量为空：

## 开关输出

##　测试样例

测试样例包括正确测试、错误测试两大部分。

# 正文

---

##　实现的内容

lab1中实现了词法分析及结果验证程序，具体完成了以下要求：

1. 基于C++实现
2. 对于给定的文法，从源程序txt文件中识别单词
3. 按照实验的定义，记录源程序中单词的类别与单词值, 支持表中涉及的所有类型
4. 通过平台测试，all AC
5. 编写验证程序，快速运行本地所有样例，all AC

## 语言说明

一种简化版C语言，文法定义详见实验平台。

## 程序说明

程序架构

![image-20220423092435243](C:\Users\lenovo\AppData\Roaming\Typora\typora-user-images\image-20220423092435243.png)

本程序在main中调用了lex词法分析程序。main函数提供了进行词法分析的源程序路径、词法分析结果的输出路径，并将输出的结果与标准结果进行对比。对于每一个源程序，本程序都会产生一个文档用于保存分析结果。

### 词法分析程序

我的词法分析程序整体基于书本上的状态机模型，并结合语言要求做了精简修改。

##### 状态机

本程序的状态机(包含错误处理)如下所示：

![error_FSM.drawio](D:\2022_Spring\CST-编译原理\lab\lab1\状态图\error_FSM.drawio.png)

各状态的含义如下：

0. 初始状态：该状态为词语处理的起始状态，处理的是每一个词语的第一个字符。在初始状态下，状态机根据第一个字符的类型跳转到不同类别的词语处理状态，再继续读入后续字符实现词语的完整处理过程。当一个词语分析完毕输出类型后，状态机又会回到初始状态，准备处理下一个词语的第一个字符。如此循环往复，直至源程序处理完毕。
1. 标识符/关键字：由于关键字与标识符有一定的相似性，程序在该状态中基于查表的方式对二者进行区分。
2. 整型常量：给定文法的数值常量处理比书本示例程序简单许多，只需处理全部由数字构成的整型常量即可，而不用关心包含正负号、小数点、e等符号的数值型常量。

3-5. 一个小于号/大于号/等号：这三种符号的处理逻辑非常相似：在对应状态下，均有可能进一步读入一个等号而分别构成LEQ、GEQ以及EQL；若没有进一步读入等号，则分割结束，分别构成LSS、GRE、ASSIGN.

6. 一个感叹号：一个感叹号之后必须再读入一个等号才能构成合法的NEQ符号；如果下一个符号不是等号，则此一个感叹号无法构成合法的符号，报错。
7. 字符常量：初始状态读入一个单引号后进入字符常量处理状态。若读入一个单引号后，直接读入下一个单引号，则字符常量为空，报错；若下一个符号为字符，则在读入第二个单引号后输出。:100: 报错：为空 单引号里面两个
8. 字符串：字符串的处理逻辑与字符常量相似，只不过读入的第一个符号是双引号。同样，直接读入第二个双引号会导致空字符串报错。:100: 报错：为空

##### 关键代码段

**顶层函数** 这段代码接收了验证程序传递来的文件路径，执行了文件开闭操作，初始化检索表，计算了文件大小，并调用分析程序进行处理。

```cpp
int lex_top(string dir, int num, string inFileName, string outFileName){
	//读取文件
	const char* inFileName_c= inFileName.c_str();
	fpin=fopen(inFileName_c, "r"); //打开输入文件
	fout.open(outFileName);//打开输出文件
	cout << "*_Analysis running at_*"<<endl;
	cout << inFileName <<endl;
	cout << "*_Lex analysis start_"<<endl;
	fseek(fpin,0,SEEK_END);	//移动指针到文件末尾，计算文件大小
    filesize = ftell(fpin);
	cout << "*_Filesize="<< filesize<<"_*" << endl;
    rewind(fpin);//将指针移动到开头
	init();//初始化关键字表、简单符号表
    //运行词法分析
	lex_analyse(); //进行词法分析
	cout << "*_Lex analysis done_*"<<endl;
    //关闭文件
	fclose(fpin);
	fout.close();
	return 0;
}
```

**初始化检索表及检索** 本程序用map的形式保存了关键字和简单符号（此处略去了部分关键字和符号）。因为文法要求标识符和保留字都不区分大小写，所以检索操作大致有以下几种思路：1.将源文件统一改写为大写或者小写，然而这不符合输出要求；2. 在map中保存大小写的组合，然而这样开支太大；3. 在map中仅保存大写或小写，另编写检索函数用于源程序中大小写混合的情况，本程序使用了这种思路。

```cpp
void init(){//初始化检索关键字、简单符号的map
		m["const"]="CONSTTK";
		m["int"]="INTTK";
		··· ···
		m["scanf"]="SCANFTK";
		m["printf"]="PRINTFTK";
		m["return"]="RETURNTK";
		cm['+']="PLUS";
		cm['-']="MINU";
		··· ···
		cm['}']="RBRACE";
		cm[',']="COMMA";
}

string keylookup(string s){//将字符串转为小写，并检索是否为保留字
	for(int i=0; i<s.size(); i++){
		s[i]= tolower(s[i]);
	}
	return m[s];
}
```

查表过程如下所示：

```cpp
if(keylookup(token)!=""){ //写入关键字
	fout << keylookup(token) << " " << token << endl;
}else{//写入标识符
	fout << "IDENFR " << token << endl;
}
```

**状态机循环结构**  本程序以循环调用状态机的方式处理源程序。每处理完一个词语后，状态机返回初始状态准备处理下一个词语，直到文件处理完毕。以下展示了状态机循环的结构，其中略去了部分状态、各状态的细节以及读取字符、字符回退等操作。

```cpp
void lex_analyse(){
	do{//循环执行，直到文件位置标识符抵达文件尾
		switch(state){
			case 0://初始状态，根据下一个字符，决定跳转的状态（每个状态都是如此）
				break;
			case 1: //识别标识符和关键字
				
				break;
             ··· ···
			case 8://单引号" (字符串的左引号)
			 
				break;
			default://状态不存在，输出错误
				fout << "NO CASE ERROR"<< endl;
				return;
				break;
		}
	}while(ftell(fpin)!=filesize);
}
```

**字符读取、回退** 字符读取和回退的方法由文件打开方式决定。本程序以fopen的方式打开文件获得一个文件对象指针FILE *fpin，因此读取位置的移动必须通过文件位置符（而不是直接操作指针！）的移动来实现。

```cpp
//字符读取
c=fgetc(fpin); //读取完毕后文件位置符向后移动一位
//字符回退
fseek(fpin, -1, SEEK_CUR);//将文件位置符回退一位
state= 0;//返回初始状态
```

**以状态1为例 ** 一个完整的状态如下所示：

```cpp
case 1: //识别标识符和关键字
				token+=c;//将当前字符加入正在识别的字符串
				c=fgetc(fpin);//读入下一个字符，并移动文件位置指示符
				if(isDigit(c)||isLetter(c)||c=='_'){//除开头外，标识符可以由字母、数字、下划线组成。输入其他符号说明标识符已结束
					state= 1;
					break;
				}
				else{//下一个字符与标识符无关，标识符到此为止。进一步排除区别关键字/标识符
					fseek(fpin, -1, SEEK_CUR);// 文件位置符后退一位，消除fgetc的影响，使得新的字符能够在初始状态被重新处理。需用fseek操作FILE对象的文件位置符
					state=0;
					if(keylookup(token)!=""){ //写入关键字
						fout << keylookup(token) << " " << token << endl;

}else{//写入标识符
						fout << "IDENFR " << token << endl;
					}
				}
				break;
```

###　结果验证程序

**顶层函数  ** 选择验证模式

```cpp
int main(){
    cout << "*_Enter folder number(-1=ALL)_*"<< endl;
    int folder_n;
    cin >> folder_n;
    if(folder_n!=-1){//测试testfiles下一个文件夹下所有数据
        if(one_folder_test(folder_n)){
            cout << endl;
            cout << "*_ALL PASS!_*"<< endl;
        };
    }
    else{//测试testfiles下全部文件夹的所有数据
        bool folder_all_pass=1;
        for(int i=1; i<=maxn; i++){
            if(one_folder_test(i)==0){
                folder_all_pass= 0;
            }
        }
        if(folder_all_pass){
            cout << endl;
            cout << "*_ALL PASS!_*"<< endl;
        }
    }
    return 0;
}
```

**运行测试并验证结果**

```cpp

bool one_folder_test(int n){//测试一个目录下所有文件
    bool allpass= 1;
    //文件路径
    string dir= dir_p+ char('0'+n);
    string inFileName;
	string  outFileName;
    //生成测试文件名并进行词法分析
    for(int i=1; i<=maxfn;i++){
        char *s;
        sprintf(s,"%d", i);
        inFileName= dir+ "\\"+ infilename_prefix + s+ ".txt"; 
        outFileName= dir+ "\\"+ outfilename_prefix +s+ ".txt"; 
        cout << endl;
        lex_top(dir, i, inFileName, outFileName);
    }
    //当前文件夹内词法分析完毕
    cout << "=== === ==="<< endl;
    cout << "*_All lex analyses are done_*"<< endl;
    cout << "=== === ==="<< endl;
    //读取词法分析输出和标准输出进行对比
    for(int i=1; i<=maxfn; i++){
        char s1[10];
        sprintf(s1,"%d", i);
        
        cout << endl;
        cout << "--- --- --- --- --- --- --- --- ---"<< endl;
        cout << left;
        cout << "Case "<< i << endl;
        cout << "--- --- ---"<< endl;

lex_fin.open(dir+ "\\"+ outfilename_prefix + s1+ ".txt");
        std_fin.open(dir+ "\\"+ std_prefix + s1+ ".txt");
        //比较
        int count_l= 1;
        bool isPassed= 1;//标记当前文件夹是否全部通过测试。默认为1，有错误则为0
        cout <<  " Error      "<< setw(15) << "lex_output" <<"   "<< setw(15)<<"std_output" << endl;
        while(1){//逐行对比，不同则报错；未同时结束则报错；
            string lex_l, std_l;
            lex_fin>> lex_l;
            std_fin>> std_l;
            if(lex_l!= std_l){         
                cout<< left;
                cout << "At line "<< setw(5)<<count_l<< ": "<<" "<<setw(15)<< lex_l<<"   " << setw(15)<< std_l<< endl;
                isPassed= 0;
            }
            count_l++;
            //至少一个文件末尾，非同时结束则报错
            int isEnd= lex_fin.eof()+ std_fin.eof();
            if(isEnd==2){//同时读完
                if(isPassed==1){
                    cout << "Case pass"<< endl;
                }
                break;
            }
            else{
                switch(isEnd){
                    case 0: break;//都在读取中
                    case 1: //长度不一致
                        isPassed= 0;
                        cout << "different line numbers!"<< endl;
                        break;
                    default:cout << "error"<< endl;
            }
            }
        }
        if(isPassed==0){
            allpass= 0;
        }
    }
    return allpass;
```

##　错误处理

我在词法分析中实现了对"a"类错误——"非法符号或不符合词法"的处理。这类错误在词法分析来自以下情况：

1. !感叹号的后一个符号不是=等号
2. 字符常量为空
3. 字符常量字符数超过1
4. 字符串常量为
5. 字符常量出现非法字符
6. 字符串常量出现非法字符
7. 初始状态输入非法字符

----

上述几种情况可以进一步整理为感叹号、字符常量、字符串常量、初始状态非法字符三类。现在对上述三类错误进行讨论：

**感叹号**

"后一个符号不为等号"是与感叹号相关的唯一一种错误。

![error_discussion1.drawio](D:\2022_Spring\CST-编译原理\lab\lab1\状态图\error_discussion1.drawio.png)

对于从初始状态出发的感叹号，本文法只允许该符号与一个等号共同组成不等于符号。换言之，本文法不会生成”!123"、"！"此类词语。因此，输入一个感叹号后，下一个字符如果是等号，则可以正常输出；如果不为等号，程序将进入异常处理函数。

**字符常量**

对于字符常量来说，从初始状态输入一个单引号，下一个字符必须为文法所定义的合法字符，再下一个字符则必须为单引号。文法中对字符常量描述如下：字符＞  ::= '＜加法运算符＞'｜'＜乘法运算符＞'｜'＜字母＞'｜'＜数字>‘. 因此，对于字符常量为空这一错误情况——即输入第一个单引号后紧跟第二个单引号，在处理上可以直接将其的第二个单引号当作非法字符常量字符（字符串的合法字符与字符常量的合法字符有区别，在此特别区分）。

![error_discussion2.drawio](D:\2022_Spring\CST-编译原理\lab\lab1\状态图\error_discussion2.drawio.png)

从0初始状态输入一个单引号，进入7字符常量状态。

此时，如果输入一个合法的字符常量字符，则进入9不为空字符常量状态、在9不为空字符常量状态下，若输入一个单引号即构成合法的字符常量，若输入的不为单引号，则说明字符常量两个单引号之间字符数大于1，不符合词法而报错。

在7字符常量状态下，若输入非法字符则直接报a类错。注意，非法字符包括了单引号，因此能够处理字符常量为空的情况。

注意，读入一个非法字符后，若后方紧跟一个单引号，则需要文件位置符向后移过单引号，从而防止将第二个单引号视为新的字符起始。如下所示：

```cpp
			case 7://单引号'(字符常量的左引号)
				c=fgetc(fpin);
				if(checkchar(c)){//输入合法字符
					token+=c;
					state=9;
					break;
				}
				else{//输入非法字符，包括单引号为空的情况
					raise_error(linenum, 'a');//$ 字符常量中字符为空或非法，a类错误
					c=fgetc(fpin);
					if(c=='\''){//若后面还有一个单引号，跳过它
						state=0;
					}else{//若后面不是单引号，回退
						fseek(fpin, -1, SEEK_CUR);
						state=0;
					}
				}
				break;
```

**字符串常量**

与字符串常量相关的错误处理方式与字符常量类似，其主要区别在于字符串常量的字符数可以大于一，这意味着识别出字符串常量结束会复杂一些.

![error_discussion3.drawio](D:\2022_Spring\CST-编译原理\lab\lab1\状态图\error_discussion3.drawio.png)

从初始状态出发，输入一个双引号进入字符串常量状态。下一个字符若为非法字符则立即报错。注意，字符串为空意味着紧接着输入第二个双引号，而双引号也在字符串的非法字符范围之内，因此字符串为空错误也可以触发此处报错。输入一个合法的字符串字符后，进入10不为空字符串常量状态。在这一状态下，若输入合法的字符串字符，则字符串延长，继续保持该状态；若输入双引号，字符串终止，识别成功；若输入除双引号外的非法符号，则报a类错。相关状态的源码如下：

```cpp
case 8://双引号" (字符串的左引号)
				c=fgetc(fpin);
				if(checkstr(c)){//合法的字符串字符
					token+= c;
					state=10;
					break;
				}
				else{//非法的字符串字符，包括了双引号（因为不能为空）
					raise_error(linenum, 'a');//$ 字符串常量中字符为空或非法，a类错误
					c=fgetc(fpin);
					if(c=='\"'){//若后面还有一个双引号
						state=0;
					}else{//回退
						fseek(fpin, -1, SEEK_CUR);
						state=0;
					}
				}
				break;
case 10://字符串常量，读入了一个字符
				c=fgetc(fpin);
				if(c=='"'){//下一个字符是右边的双引号，终止
					normal_output("STRCON ",token);
					state= 0;
					break;
				}
				else{
					if(checkstr(c)){//下一个字符仍然为合法字符串字符，继续回到state 10
						token+= c;
						state= 10;
						break;
					}
					else{//非法符号，报错
						// cout <<"illegal char for str"<< endl;
						state= 0;
						raise_error(linenum, 'a');//$ 字符串常量非法字符，a类错误
					}
				}
				break; 
```

**初始状态非法字符**

![error_discussion4.drawio](D:\2022_Spring\CST-编译原理\lab\lab1\状态图\error_discussion4.drawio.png)

初始状态得到的字符不能转入任何一个状态表明输入的字符非法，报a类错误。

---

**行号与类别码**

输入的错误信息包括行号及类别码。处理程序统计了‘\n’字符的出现个数，因此可以产生行号。词法分析的类别码则根据具体的情况手工指定。 以状态10为例，错误处理代码如下所示：

```cpp
case 10://字符串常量，读入了一个字符
				c=fgetc(fpin);
				if(c=='"'){//下一个字符是右边的双引号，终止
					fout << "STRCON " << token << endl;
					state= 0;
					break;
				}
				else{
					if(checkstr(c)){//下一个字符仍然为合法字符串字符，继续回到state 10
						token+= c;
						state= 10;
						break;
					}
					else{//非法符号，报错
						// cout <<"illegal char for str"<< endl;
						state= 0;
						raise_error(linenum, 'a');//$ 字符串常量非法字符，a类错误
					}
				}
				break;

// ··· ···

void raise_error(int line_n, char e_code){//错误输出，输出行数+ 错误代码
	cout << "*_An Error Occurs at line "<< line_n<< " _ "<< e_code<<"_*" << endl;
	if(mode==2 || mode==3){//mode=3: 全部输出， mode=1 关闭错误输出	
		fout <<line_n<<"  "<<e_code<< endl;
	}
}
```

## 输出模式

本程序的输出具体包括错误输出、token输出两种类型，分别由以下两个函数实现：

```cpp
void normal_output(char word, char cls){ //正常情况下的输出，输出词+ 类别
	if(mode==3 || mode==1){//mode=3: 全部输出， mode=1 关闭错误输出	
		fout << word << " "<< cls<< endl;
	}
}

```

本程序提供了关闭错误开启token、关闭token开启错误、开启错误和token三种输出模式。错误输出模式由mode参数在调用词法分析顶层程序lex_top()时传入，如下所示：

```cpp
int lex_top(string inFileName, string outFileName, int md){
	//mode 1:close error output; mode 2: close lex output; mode 3: open all output
	mode= md;
	cout << "*_Analysis Mode=_"<<mode<<"_*"<<endl;
	//读取文件
	const char* inFileName_c= inFileName.c_str();
	fpin=fopen(inFileName_c, "r"); //打开输入文件
	fout.open(outFileName);//打开输出文件
	cout << "*_Analysis running at_"<<inFileName<<"_*"<<endl;
	cout << "*_Lex analysis start_*"<<endl;
	fseek(fpin,0,SEEK_END);	//移动指针到文件末尾，计算文件大小
    filesize = ftell(fpin);
	cout << "*_Filesize="<< filesize<<"_*" << endl;
    rewind(fpin);//将指针移动到开头
	init();//初始化关键字表、简单符号表
    //运行词法分析
	lex_analyse(); //进行词法分析
	cout << "*_Lex analysis done_*"<<endl;
    //关闭文件
	fclose(fpin);
	fout.close();
	return 0;
}
```

---

源程序在第7行出现了一个词法错误。词法分析器在不同模式的运行效果如下所示：

**Mode1** 关闭错误输出，开启Token输出

**Mode2** 关闭Token输出，开启错误输出

**Mode3** 开启Token和错误输出

实际的编译器不需要输出词法分析结果，因此需要将两个输出全部关闭，本程序提供了此类方便管理输出的接口，只需稍加修改即可满足需求。

## 测试设计

平台的词法分析样例提供了充分的正确性测试，因此在这里主要补充了错误测试样例。

**正确测试**  同平台样例

**错误测试**

![image-20220426154843032](C:\Users\lenovo\AppData\Roaming\Typora\typora-user-images\image-20220426154843032.png)

```cpp
coNst int cONst1 = 001, const2 = -100;
const char const3 = '';//空字符
const char const4 = 'A';//合法字符1，字母
const char const5 = '=';//合法字符2，运算符
const char const6 = '~';//非法字符
const char const7 = 'AB';//多个字符

int change1;
char change3;
int gets1(int var1,int var2){
    change1 = var1 + var2;
    if(change1!1){//感叹号错误
         printf("CQUNO1");//合法字符串
          printf("");//空字符串
           printf("CQU世");//非法字符串
    }
    return (change1);
}
void main(){
    printf("Hello World");
    printf(gets1(10, 20));
}
```

## 平台测试

![image-20220426155006206](C:\Users\lenovo\AppData\Roaming\Typora\typora-user-images\image-20220426155006206.png)

周逸群/lex_analysis

简介

发行版

贡献者

近期动态

周逸群/lex_analysis .gitee-modal { width: 500px !important; }

简介

发行版

贡献者

近期动态

搜索帮助

周逸群/lex_analysis