2022年 山东大学编译原理实验 A : 词法分析器_给定一个 c++ 语言源程序,你需要将其从字符流转换为词语流。具体来说,你需要过滤

原题链接

问题描述

A : 词法分析器

编译原理课程实验 词法分析器

概述

你需要完成一个 PL/0 语言的编译器。这个实验分为若干部分。在这个部分中，你需要完成 PL/0 语言的词法分析器。

你的编译器不应当对用户输入程序进行假设（例如，假设用户输入的程序不超过若干字节，或每行不超过若干字符，或程序不超过若干符号）。但是，PL/0 的任意一个词法单元均不会超过 10 个字符长（若超过，则认定为词法错误，见下文）

给定一个 PL/0 语言源程序，你需要将其从字符流转换为词语流。具体来说，你需要过滤源程序中的空白符(空格，tab，换行等)，识别关键字、标识符、数字以及运算符。

PL/0 的关键字表如下

CONST
VAR
PROCEDURE
BEGIN
END
ODD
IF
THEN
CALL
WHILE
DO
READ
WRITE
1
2
3
4
5
6
7
8
9
10
11
12
13

PL/0 的标识符由上下文无关文法

<标识符> → <字母> {<字母>|<数字>}
<字母> → A|B|C…X|Y|Z
<数字> → 0|1|2…7|8|9

生成。

例如，ABC 是合法的标识符，X25519 是合法的标识符，但 233QWQ 不是合法的标识符

在 PL/0 语言中，标识符不会超过 10 字符长。如果超过了 10 个字符，你应该认为这是一个词法错误。

特别的，关键字不能是标识符。

PL/0 的数字由上下文无关文法

<无符号整数> → <数字>{<数字>}
<数字> → 0|1|2…7|8|9

生成。

PL/0 仅支持无符号整数。因此，对于-123，你的词法应当将其分为两个词语-和 123

PL/0 的运算符表如下

=
:=
+
-
*
/
#
<
<=
>
>=
1
2
3
4
5
6
7
8
9
10
11

你需要注意拼接两个字符组成的运算符。这些运算符中间不会存在空白符，例如，对于 > =应当识别为两个单词 > 和=

PL/0 的分隔符表如下

;
,
.
(
)
1
2
3
4
5

请注意：PL/0 语言不区分大小写。

通过将字符流转换为词语流，你将为下一个部分（语法分析器）做好准备。

我们保证输入的整数的数值不会超出 32 位带符号整数能表示的范围。

我们建议你除存储需要自动评测时需要的信息外，存储一些额外信息。你将在语法分析器中使用诸如单词类型等信息。另请参阅旧版词法分析器中的 GETSYM 部分。如果你希望在未来的错误处理部分中提示错误信息，你可能还需要存储每一个词语在字符流中的位置。

评测要求

你可以选择自动评测，将这一部分的代码提交到 SDU OJ 上。通过自动测试后，这一部分的正确性分数将自动评为满分。

如果你不能或不愿进行自动评测，你可以要求人工验收。在这种情况下，这一部分的正确性分数将由助教给出。

如果你计划进行自动评测，你需要从标准输入读取输入的程序，并将分析得到的词语输出至标准输出，每行一个。

对于关键字，运算符，分隔符，直接输出其本身即可。

对于数字，你需要先输出一个单词 NUMBER，之后是一个空格，之后是数字值。

对于标识符，你需要先输出一个单词 IDENTIFIER，之后是一个空格，之后是标识符本身。

如果程序包含词法错误，你的程序应当仅输出一行"Lexical Error"，不含引号。

在本程序中，你只需要关注词法上的错误。对于词法正确而存在语法错误的程序，你仍然需要输出单词流。

输出时，除 Lexical Error 外，输出字母应当均为大写。

样例 1

输入

VAR A,B;
CONST C=0;
BEGIN
	READ(B,A);
	A:=B+C;
	WRITE(A);
END.
1
2
3
4
5
6
7

输出

VAR
IDENTIFIER A
,
IDENTIFIER B
;
CONST
IDENTIFIER C
=
NUMBER 0
;
BEGIN
READ
(
IDENTIFIER B
,
IDENTIFIER A
)
;
IDENTIFIER A
:=
IDENTIFIER B
+
IDENTIFIER C
;
WRITE
(
IDENTIFIER A
)
;
END
.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

样例 2

输入

VAR
THISISATOOLONGIDENTIFIER;
1
2

输出

Lexical Error
1

样例 3

输入

VAR
VARX = 233 = 0233;
1
2

输出

VAR
IDENTIFIER VARX
=
NUMBER 233
=
NUMBER 233
;
1
2
3
4
5
6
7

另有一个词法错误的样例见 B - 语法分析器

还有部分测试数据可供下载（lexical_partial_testcases.zip）

部分的意思是，通过这些数据不保证你能通过本题

提交要求

你需要将代码提交到 GitHub Classroom 中。如果你选择自动评测，还需要提交代码以通过 SDUOJ 上的测试。

杂项

这一个实验部分建议完成时间约为两小时。

解析

本题首先要解决的问题是循环输入，直到文件尾，可以用while(cin.get©)或者while(c=getchar()!=EOF)来实现。具体与测试数据进行比对可以先在文件中执行，可以用输入输出重定向freopen来实现，例如在输入输出之前加上“freopen(“aaa.txt”,“r”,stdin);freopen(“bbb.txt”,“w”,stdout);”。
切入正题，本题的关键在于分割出一个一个单独的词，那就必须清楚划分词的依据是什么。词分为关键字、标识符、数字、运算符和分隔符，且由题意知，词的长度不得大于10，否则为非法。其中，13个关键字已经由题目给出，可以存入大小为13的string数组中，这就是一个词能否当做关键字的依据，遍历这13个字符串，如果找得到相同的则是关键字，否则不是。标识符由字母或者字母与数字的组合构成，且必须以字母开头。数字需要注意去前导零的问题，且数字‘0’应保留最后一个零，最重要的是数字均为无符号数，必须将其与前面可能存在的‘-’号当做两个词来处理。运算符中比较特殊的是">=“,”<=“,”:=“，因为这三个运算符由两个字符构成，而其余的运算符都是单独的一个字符作为一个词；而且，”:=“区别于”>=“和”<=“，因为”>=“和”<="可以不用与’=‘组合单独以’>‘或者’<‘的形式存在，而单独一个’:'则构成了非法字符。分隔符都由一个字符构成。
具体实现详见代码及注释。

代码

#include <iostream>
#include <string>
using namespace std;

string key[13]={"CONST","VAR","PROCEDURE","BEGIN","END","ODD","IF","THEN","CALL","WHILE","DO","READ","WRITE"};
int cnt=0,sum=0;//cnt用来记录存放的词的总数，sum用来存放输入的字符总数 
string res[1000000];//res数组用来存放所有要被存放的词，如果不出现词法错误 
string ss;//ss用来存放所有输入的字符 

char up(char c)
{
	if(c>='a'&&c<='z') c-=32;
	return c;
}

int judge(string s)//判断类型（0代表非法，1代表关键字，2代表数字，3代表标识符） 
{
	if(s.length()>10) return 0;//非法
	for(int i=0;i<13;i++) if(s==key[i]) return 1;//关键字 
	int i;
	for(i=0;i<s.length();i++)
	{
		if(s[i]>='0'&&s[i]<='9') continue;
		else break;
	}
	if(i==s.length()) return 2;//数字
	return 3;//标识符
}

int main()
{
	char c;
	string tmp;
	bool dig=false;//是否以数字开头
	bool spe=false;//是否出现'<','>'或':'
	bool spe1=false;//是否出现':' 
	while(cin.get(c))//先将所有输入的字符都存入ss中，再依次从ss中读取所输入的字符 
		ss+=c,sum++;
	ss+="\n",sum++;//ss末尾置空，否则最后一个元素很有可能无法正常输出 
	for(int i=0;i<sum;i++)
	{
		c=ss[i];
		if(spe1&&c!='=')//如果前一个字符为':'且当前字符不为'='，则判定为非法，直接结束整个程序 
		{
			cout<<"Lexical Error"<<endl;
			return 0;
		}
		if(tmp==""&&c>='0'&&c<='9') dig=true;//如果tmp为空，则c为第一个字符，如果为数字则dig赋值true
		if(c>='A'&&c<='Z'||c>='a'&&c<='z') 
		{
			spe=false,spe1=false;
			if(dig)//以数字开头的不能作为标识符
			{
				cout<<"Lexical Error"<<endl;
				return 0;
			}
			tmp+=up(c);
		}
		else if(c>='0'&&c<='9') spe=false,spe1=false,tmp+=c;	
		else//非数字或字母 
		{
			dig=false;
			if(tmp!="")//tmp非空则送去检测，判断其类型 
			{
				int flag=judge(tmp);//flag用来标记tmp的类型 
				if(flag==0)//0代表非法 
				{
					cout<<"Lexical Error"<<endl;
					return 0;
				}
				else if(flag==1) res[cnt++]=tmp;//1代表关键字 
				else if(flag==2)//2代表数字
				{
					while(tmp.length()>0&&tmp[0]=='0')//去前导0 
						tmp.erase(0,1);
					if(tmp=="") tmp="0";
					res[cnt++]="NUMBER "+tmp; 
				}
				else if(flag==3) res[cnt++]="IDENTIFIER "+tmp;//3代表标识符 
			}
			if(c==' '||c=='\t'||c=='\n') spe=false,spe1=false,tmp="";//空字符 
			else if(c=='<'||c=='>'||c==':')//'<','>',':'与'='构成整体，应当单独考虑 
			{
				if(c==':') spe1=true;//':'不能单独存在，其后必须接'='
				spe=true;//">=","<=",":="必须作为整体输出，出现'>'或'<'或':'则先做个标记，其中'>'和'<'可单独存在 
				res[cnt++]=c;
				tmp="";
			}
			else if(c=='=')
			{
				if(spe) res[cnt-1]+='=',tmp="",spe=false,spe1=false;//">=","<="或":="应作为整体在同一行中输出 
				else//'='前如不是'>'或'<'或':'，不做特殊处理 
				{
					res[cnt++]='=';
					tmp="";
				}
			}
			else if(c=='+'||c=='-'||c=='*'||c=='/'||c=='#'||c==';'||c==','||c=='.'||c=='('||c==')') 
			{
				spe=false,spe1=false;
				res[cnt++]=c;
				tmp="";
			}
			else//其他字符均判定为非法 
			{
				cout<<"Lexical Error"<<endl;
				return 0;
			}
		}
	}
	for(int i=0;i<cnt;i++) cout<<res[i]<<endl;//如果之前没有检测到任何非法元素退出程序，遍历存放结果的res数组并依次输出 
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

运行结果