编译原理:简单绘图语言解释器的实现

为函数绘图语言编写一个解释器。

​ 解释器接受用绘图语言编写的源程序,经语法和语义分析之后,将源程序所规定的图形显示在显示屏(或窗口)中。

目的

​ 通过自己动手编写解释器,掌握语言翻译特别是语言识别的基本方法,加深对编译器构造原理和方法的理解,巩固所学。

  • <1> 会用正规式和产生式设计简单语言的语法;
  • <2> 会用递归下降子程序编写编译器或解释器;

语句原则

1、各类语句可以按任意次序书写,且语句以分号结尾。源程序中的语句以它们出现的先后顺序处理。

2、ORIGIN、ROT 和 SCALE 语句只影响其后的绘图语句,且遵循最后出现的语句有效的原则。例如,若有下述ROT语句序列:

​ ROT IS 0.7 ; ROT IS 1.57 ;

​ 则随后的绘图语句将按1.57而不是0.7弧度旋转。

3、无论 ORIGIN、ROT 和 SCALE 语句的出现顺序如何,图形的变换顺序总是:

​ 比例变换→旋转变换→平移变换

4、语言对大小写不敏感,如 for、For、FOR 等,均被认为是同一个保留字。

5、语句中表达式的值均为双精度类型,旋转角度单位为弧度且为逆时针旋转,平移单位为点。

语句的语法与语义

循环绘图(FOR-DRAW)语句

语法:

​ FOR T FROM 起点 TO 终点 STEP 步长 DRAW (横坐标, 纵坐标);

语义

​ 令 T 从起点到终点、每次改变一个步长,绘制出由 (横坐标,纵坐标) 所规定的点的轨迹。

举例

​ FOR T FROM 0 TO 2*PI STEP PI/50 DRAW (cos(T), sin(T));

说明

​ 该语句的作用是令 T 从 0 到 2*PI、步长 PI/50,绘制出各个点的坐标 (cos(T),sin(T)),即一个单位圆。

注意

​ 由于绘图系统的默认值是

1
2
3
4
5
ORIGIN IS (0,0);

ROT IS 0;

SCALE IS (1, 1);

​ 所以实际绘制出的图形是在屏幕左上角的一个点。

比例设置(SCALE)语句

语法

​ SCALE IS (横坐标比例因子,纵坐标比例因子);

语义

​ 设置横坐标和纵坐标的比例,并分别按照比例因子进行缩放。

举例

​ SCALE IS (100, 100);

说明

​ 将横坐标和纵坐标的比例设置为 1:1,且放大 100 倍。

​ 若: SCALE IS (100, 100/3);

​ 则:横坐标和纵坐标的比例为 3:1

角度旋转(ROT)语句

语法

​ ROT IS 角度;

语义

​ 逆时针旋转角度所规定的弧度值。具体计算公式:

  • 旋转后X=旋转前X*COS(角度)+旋转前Y*SIN(角度)
  • 旋转后Y=旋转前Y*COS(角度)-旋转前X*SIN(角度)

举例

​ ROT IS PI/2;

说明

​ 逆时针旋转PI/2,即逆时针旋转90度。

注释语句

注释的作用

  • 便于理解
  • 屏蔽暂时不需要的语句

语法

​ // This is a comment line

​ 或 -- 此行是注释

语义

​ // 或 -- 之后,直到行尾,均是注释

记号的语法和语义

记号的种类

​ 常数、参数、函数、保留字、运算符、分隔符

<1> 常数

​ 常数字面量和标识符形式的常量名均称为常数。字面量的形式为普通的数值,如果没有小数部分,可以省略小数点。例如 2、 2.、 2.0 都是合法的常数。 标识符 PI、E 也是常数,它们分别代表圆周率和自然对数的底。常数不能有符号位,如 -1 和 +2 不是常数而是(一元运算的)表达式。

<2> 参数

​ 本作图语言中唯一的、已经被定义好的变量名 T 被称为参数,它也是一个表达式。由于作图语言中只有这唯一的变量,因此作图语言中无需变量或参数的声明和定义语句。

<3> 函数(调用)

​ 为简单起见,当前函数调用仅支持 Sin、Cos、Tan、Sqrt 以及 Exp 和 Ln。有兴趣的同学可以再加入其他函数。

<4> 保留字

​ 语句中具有固定含义的标识符,包括:

1
2
3
ORIGIN, SCALE, ROT, IS, TO,

STEP, DRAW, FOR, FROM

<5> 运算符

​ PLUS, MINUS, MUL, DIV, POWER

即 + - * / **

<6> 分隔符

​ SEMICO, L_BRACKET, R_BRACKET, COMMA

即 ; ( ) ,

开发环境及配置

​ 采用C/C++程序设计语言使用 Visual Studio Community 2017 编写 Windows 桌面应用程序,分为三大模块:词法分析器、语法分析器和绘图解释器。

基本原理与解决思路

​ 词法分析器用于识别出文件流中符合我们定义的记号,供语法分析器调用;语法分析器用于构造语法分析树,计算出表达式的值,包括原点坐标、旋转角度、横纵坐标比例和缩放大小,以及循环绘制语句的各项参数;绘图解释器,读取语法分析器产生的结果,计算出每一个点的 (x, y) 坐标,使用 “描点法” 绘制出完整的函数图像,并调用系统窗口显示相关的函数,以窗口的形式展示函数图像

​ 词法分析器将文件作为数据流进行处理,依次将数据流的一个字符取出,或者放回,按照实现构造的记号表识别文件流中的记号流,将其与设定的函数绘图语句的模式进行匹配,引出一个 GetToken() 接口被语法分析器调用。

​ 词法分析器作为一个子函数被语法分析器调用,读取记号的同时构建语法树,计算表达式的值,并将绘图所需的参数保存在相应的变量中。按照语句顺序,依次对每个记号进行分析,对于保留字,采用 MatchToken() 匹配成功后,对下一个记号进行分析,而对于其它的记号符号,则调用 Expression() 生成语法树,再用 GetExprValue() 递归下降计算出值,最后删除语法树。

​ 语法分析器在分析的过程中会计算表达式的值,将其储存到变量中调用系统的 SetPixel(hDC, x, y, black) 在窗口中的 (x, y) 坐标画一个黑色的点利用描点法的思想,在循环体中让参数 Parameter 从 Start 循环到 End 每次增加 Step,然后在每次循环中根据比例、 平移和旋转角度,计算每一个 (x, y),在窗口中绘制点。

关键类及主要方法

1
2
3
4
5
6
7
8
9
10
11
enum Token_Type { //记号种类
ORIGIN, SCALE, ROT, IS, TO, //保留字
STEP, DRAW, FOR, FROM,
T, //参数
SEMICO, L_BRACKET, R_BRACKET, COMMA, //分隔符号
PLUS, MINUS, MUL, DIV, POWER, //运算符
FUNC, //函数
CONST_ID, //常数
NONTOKEN, //空记号
ERRTOKEN //出错记号
};
1
2
3
4
5
6
struct Token { // 记号的数据结构
Token_Type type; // 类别
char *lexeme; // 构成记号的字符串
double value; // 若为常数,则是常数的值
double(*FuncPtr)(double); // 若为函数,则是函数的指针
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static Token TokenTab[] = {
{ CONST_ID, "PI", 3.1415926, NULL },
{ CONST_ID, "E", 2.71828, NULL },
{ T, "T", 0.0, NULL },
{ FUNC, "SIN", 0.0, sin },
{ FUNC, "COS", 0.0, cos },
{ FUNC, "TAN", 0.0, tan },
{ FUNC, "LN", 0.0, log },
{ FUNC, "EXP", 0.0, exp },
{ FUNC, "SQRT", 0.0, sqrt },
{ ORIGIN, "ORIGIN", 0.0, NULL },
{ SCALE, "SCALE", 0.0, NULL },
{ ROT, "ROT", 0.0, NULL },
{ IS, "IS", 0.0, NULL },
{ FOR, "FOR", 0.0, NULL },
{ FROM, "FROM", 0.0, NULL },
{ TO, "TO", 0.0, NULL },
{ STEP, "STEP", 0.0, NULL },
{ DRAW, "DRAW", 0.0, NULL }
};
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
extern Token GetToken(void) {//获取一个记号
Token token;
int Char;
memset(&token, 0, sizeof(Token));
EmptyTokenString();
token.lexeme = TokenBuffer;
for (;;){ //过滤源程序中的空格、TAB、回车等
Char = GetChar();
if (Char == EOF)
{
token.type = NONTOKEN;
return token;
}
if (Char == '\n') LineNo++;
if (!isspace(Char)) break;// 空白字符,返回非0值不是空白字符,跳出for循环
}
AddCharTokenString(Char);
//若不是空格、TAB、回车、文件结束符等,则先加入到记号的字符缓冲区中
if (isalpha(Char)){ //若char是A-Za-z,则一定是函数、关键字、PI、E等。
for(;;){
Char = GetChar();
if (isalnum(Char)) //判断Char是否为字母或者数字,是则返回非0,否则返回0;
AddCharTokenString(Char); //Char是字母或者数字
else break;
}
BackChar(Char);
token = JudgeKeyToken(TokenBuffer);
token.lexeme = TokenBuffer;
return token;
}
else if (isdigit(Char)){ //若是一个数字,则一定是常量
for (;;){
Char = GetChar();
if (isdigit(Char))
AddCharTokenString(Char);
else break;
}
if (Char == '.'){
AddCharTokenString(Char);
for (;;){
Char = GetChar();
if(isdigit(Char))
AddCharTokenString(Char);
else break;
}
}//end of if(Char == '.')
BackChar(Char); //把预读的字符退回到输入源程序中
token.type = CONST_ID;
token.value = atof(TokenBuffer); //把字符串转换成浮点数
return token;
}else{ //不是字母和数字,则一定是运算符或分隔符
switch (Char){
case ';':token.type = SEMICO; break;
case '(':token.type = L_BRACKET; break;
case ')':token.type = R_BRACKET; break;
case ',':token.type = COMMA; break;
case '+':token.type = PLUS; break;
case '-':
Char = GetChar();
if (Char == '-'){
while (Char != '\n' && Char != EOF) Char = GetChar();
BackChar(Char);
return GetToken();
}else{
BackChar(Char);
token.type = MINUS;
break;
}
case '/':
Char = GetChar();
if (Char == '/'){
while (Char != '\n' && Char != EOF) Char = GetChar();
BackChar(Char);
return GetToken();
}else{
BackChar(Char);
token.type = DIV;
break;
}
case '*':
Char = GetChar();
if (Char == '*'){
token.type = POWER;
break;
}else{
BackChar(Char);
token.type = MUL;
break;
}
default:
token.type = ERRTOKEN;
break;
}// end of switch
}//end of else(不是字母和数字,则一定是符号)
return token;
}//end of GetToken
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
void PrintSyntaxTree(struct ExprNode *root, int indent)
{
int temp;
for (temp = 1; temp <= indent; temp++) printf("\t");//缩进
switch (root->OpCode){
case PLUS: printf("%s\n", "+"); break;
case MINUS: printf("%s\n", "-"); break;
case MUL: printf("%s\n", "*"); break;
case DIV: printf("%s\n", "/"); break;
case POWER: printf("%s\n", "**"); break;
case FUNC: printf("%x\n", root->Content.CaseFunc.MathFuncPtr); break;
case CONST_ID: printf("%f\n", root->Content.CaseConst); break;
case T: printf("%s\n", "T"); break;
default: printf("Error Tree Node !\n"); exit(0);
}
if (root->OpCode == CONST_ID || root->OpCode == T) //叶子节点返回
return;//常数和参数只有叶子节点 常数:右值;参数:左值地址
if (root->OpCode == FUNC)//递归打印一个孩子节点
PrintSyntaxTree(root->Content.CaseFunc.Child, indent + 1);
else//递归打印两个孩子节点
{//二元运算:左右孩子的内部节点
PrintSyntaxTree(root->Content.CaseOperator.Left, indent + 1);
PrintSyntaxTree(root->Content.CaseOperator.Right, indent + 1);
}
}
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
static void ForStatement(void)
{
double Start, End, Step;//绘图起点、终点、步长
struct ExprNode *start_ptr, *end_ptr, *step_ptr, *x_ptr, *y_ptr;
MatchToken(FOR);
MatchToken(T);
MatchToken(FROM);//eg:for T from

start_ptr = Expression(); //构造参数起点表达式的语法树
Tree_trace(start_ptr);
Start = GetExprValue(start_ptr);//计算参数起点表达式的值
DelExprTree(start_ptr);//释放参数起点语法树所占空间

MatchToken(TO);
end_ptr = Expression();//构造参数终点表达式语法树
Tree_trace(end_ptr);
End = GetExprValue(end_ptr);//计算参数终点表达式的值
DelExprTree(end_ptr);//释放参数终点语法树所占空间

MatchToken(STEP);
step_ptr = Expression();//构造参数步长表达式语法树
Tree_trace(step_ptr);
Step = GetExprValue(step_ptr);//计算参数步长表达式的值
DelExprTree(step_ptr);//释放参数步长语法树所占空间

MatchToken(DRAW);
MatchToken(L_BRACKET);
x_ptr = Expression(); Tree_trace(x_ptr);
MatchToken(COMMA);
y_ptr = Expression(); Tree_trace(y_ptr);
MatchToken(R_BRACKET);

DrawLoop(Start, End, Step, x_ptr, y_ptr); //绘制图形
DelExprTree(x_ptr);//释放横坐标语法树所占空间
DelExprTree(y_ptr);//释放纵坐标语法树所占空间
}

测试截图

Parsertest.cpp 进行词法分析测试

​ 我们的测试程序test.cpp与main.cpp中都存在main函数,所以我们在测试各模块功能的时候需要将其它部分从项目生成中排除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include "scanner.h"
#include <stdio.h>

void main(int argc, char *argv[]){
Token token;
InitScanner("D:\\1.txt");
printf("记号类别 字符串 常数值 函数指针\n"); printf("____________________________________________\n");
while(1){
token = GetToken(); // 通过词法分析器获得一个记号
if (token.type != NONTOKEN) // 打印记号的内容
printf("%4d,%12s,%12f,%12x\n",token.type, token.lexeme, token.value, token.FuncPtr);
else break; // 源程序结束,退出循环
};
system("pause");
CloseScanner(); // 关闭词法分析器
}

parsertest.cpp 进行语法分析测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<stdio.h>
#include<stdlib.h>
#include "parser.h"

extern void Parser(char *SrcFilePtr);//测试主程序
void main(int argc,char *argv[])
{
char *p;
p = (char*)malloc(20 * sizeof(char));
memset(p, 0, sizeof(char) * 20);
strcpy(p, "D:\\1.txt");
Parser(p);//调用parser进行语法分析
free(p);
system("pause");
}

​ 在进行这一部分的测试时,需要将 parser.cpp 中的 GetExprValue() 语句注释掉,将 ForStatement() 中的 DrawLoop(Start, End, Step, x_ptr, y_ptr) 注释掉,因为它们会调用 semantic.cpp 中的绘图解释器函数;将所有含 Expression() 的语句后面加上 Tree_trace(), 在控制台中打印语法树,它是宏定义 #define Tree_trace(x) PrintSyntaxTree(x,1);

绘图解释器的测试

首先需要将子系统从控制台调为窗口,因为在 main.cpp 中 winmain 窗口函数

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
int APIENTRY WinMain(HINSTANCE hInstance,
HINSTANCE hPrevInstance,
LPSTR lpCmdLine,
int nCmdShow)
{
strcpy(SrcFilePath, "D:\\1.txt");//保存原文件路径
if (PrepareWindow(hInstance, hPrevInstance, nCmdShow) != true)//初始化窗口
{
MessageBox(NULL, "窗口初始化失败", "错误", MB_OK);
return 1;
}
//检查要分析的源程序文件
if (!CheckSrcFile(SrcFilePath)) return 1;
//调用绘图语言解释器
Parser(SrcFilePath);

//进入window消息循环
MSG Msg;
while (GetMessage(&Msg, NULL, 0, 0))
{
TranslateMessage(&Msg);
DispatchMessage(&Msg);
}
return Msg.wParam;
}

遇到的问题及解决办法

​ 在 scanner.h 文件中,出现了 const char* 类型的值不能用于初始化 char* 类型的实体错误

​ 可以看到报错是C2400,找到的解决方法是关闭符合模式

​ 位置在项目属性中的c/c++>>语言>>符合模式

​ 遇见了 LNK2019 外部符号错误,这里是由于 main.cpp 中的窗口函数的缘故需要窗口子系统

​ LNK2001:无法解析的struct HDC__* hDC,这个错误是semantic.h中的外部引用extern HDC hDC出现的问题,只需要在semantic.cpp中声明一下HDC hDC即可

附:测试视频及项目代码