一、上机目的会用正规式的产生式设计简单的语言语法会用递归下降子程序编写编译器或解释器会写上机报告二、上机题目简单函数绘图语言的解释器2.1 题目简述1实现简单函数绘图的语句循环绘图FOR-DRAW比例设置SCALE角度旋转ROT坐标平移ORIGIN注释 -- 或 //2 屏幕窗口的坐标系左上角为原点x方向从左向右增长y方向从上到下增长(与一般的坐标系方向相反)3 函数绘图源程序举例--------------- 函数f(t)t的图形 origin is(100,300);-- 设置原点的偏移量 rot is0;-- 设置旋转角度(不旋转)scale is(1,1);-- 设置横坐标和纵坐标的比例forT from0to200step1draw(t,0);-- 横坐标的轨迹纵坐标为0forT from0to150step1draw(0, -t);-- 纵坐标的轨迹横坐标为0forT from0to120step1draw(t, -t);-- 函数f(t)t的轨迹默认值 origin is (0, 0) rot is 0; scale is (1, 1)2.2 语句的语法和语义syntax semantics语句满足下述规定(原则)1 各类语句可以按任意次序书写且语句以分号结尾。源程序中的语句以它们出现的先后顺序处理。2 ORIGIN、ROT和SCALE 语句只影响其后的绘图语句且遵循最后出现的语句有效的原则。例如若有下述ROT语句序列ROT IS0.7 ROT IS1.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))即一个单位圆。注意由于绘图系统的默认值是ORIGIN IS(0,0);ROT IS0;SCALE IS(1,1);所以实际绘制出的图形是在屏幕左上角的一个点。比例设置(SCALE)语句语法SCALE IS (横坐标比例因子纵坐标比例因子);语义设置横坐标和纵坐标的比例并分别按照比例因子进行缩放。举例将横坐标和纵坐标的比例设置为1:1且放大100倍。若 SCALE IS (100, 100/3);则横坐标和纵坐标的比例为3:1。坐标平移(ORIGIN)语句语法ORIGIN IS (横坐标纵坐标);语义将坐标系的原点平移到横坐标和纵坐标规定的点处。举例ORIGIN IS (360, 240);将原点从(0, 0)平移到(360, 240) 处。角度旋转(ROT)语句语法ROT IS 角度语义逆时针旋转角度所规定的弧度值。具体计算公式旋转后X旋转前XCOS(角度)旋转前YSIN(角度)旋转后Y旋转前YCOS(角度)-旋转前XSIN(角度)公式的推导可参阅辅助教材。举例ROT IS PI/2;逆时针旋转PI/2即逆时针旋转90度。2.3 记号的语法和语义记号的种类常数、参数、函数、保留字、运算符、分隔符1 常数常数字面量和标识符形式的常量名均称为常数。字面量的形式为普通的数值如果没有小数部分可以省略小数点。例如2、2.、2.0都是合法的常数。 标识符PI、E也是常数它们分别代表圆周率和自然对数的底。常数不能有符号位如-1和2不是常数而是一元运算的表达式。2 参数本作图语言中唯一的、已经被定义好的变量名T被称为参数它也是一个表达式。除了预留参数 T 之外本作图语言还支持自定义参数。3 函数调用为简单起见当前函数调用仅支持Sin、Cos、Tan、Sqrt以及Exp和Ln。4 保留字语句中具有固定含义的标识符包括ORIGIN, SCALE, ROT, IS, TO, STEP, DRAW, FOR, FROM5 运算符PLUS, MINUS, MUL, DIV, POWER即: - * / **6 分隔符SEMICO, L_BRACKET, R_BRACKET, COMMA即: ; ( ) ,三、题目与要求题目为函数绘图语言编写一个解释器解释器接受用绘图语言编写的源程序经语法和语义分析之后将源程序所规定的图形显示在显示屏或窗口中。目的通过自己动手编写解释器掌握语言翻译特别是语言识别的基本方法。四、实验过程4.1 结构设计本编译器采用一趟扫描以语法分析器为核心语法分析器通过词法分析器从代码源文件中读入与分析词素通过递归下降分析生成对应的抽象语法树Abstract Syntax Tree并检测代码中的语法错误。语法分析器在生成抽象语法树后将其传递给语义分析器由语义分析器进行语义分析生成最终的可执行代码此处为了保证代码跨平台的兼容性笔者选择使用 cmake 构建整个项目整个项目中使用平台无关的标准库函数最终生成 python 代码使用 tkinter 库进行绘图。4.2 词法分析器Lexical Analyzer, aka Scanner词法分析器的主要功能词法分析器的主要功能为识别输入序列并为语法分析器提供记号过滤掉源程序中的空白字符、注释等编译无关字符输出记号token供语法分析器使用识别非法输出将其标记为错误记号为了达成对预设关键字的解析笔者预定义了一个内置的符号表 bulit_in_token_table 为了支持自 定义变量笔者还定义了一个追加符号表 append_token_table 由两个符号表组成整个编译器的符号 表。词法分析的主要流程笔者选择使用有限状态自动机来实现词法分析器其从文件中读取单个记号的流程如下清除前导空白字符获取第一个非空白字符进行判断若第一个非空白字符为字母则不断读取单个字符到缓冲区直到遇到非数字或非字母字符将之放回输入流缓冲区内存留字符作为一个记号查询符号表并返回对应的记号若符号表中不存在则视为新的变量追加到符号表中若第一个非空白字符为数字则不断读取单个字符到缓冲区直到遇到非数字字符若遇到小数点符号 则重复读取单个字符到缓冲区直到遇到非数字字符将之放回输入流通过 atof() 将缓冲区内字符转换为浮点值赋给一个新的数字记号并返回若第一个非空白字符为其他分隔字符则进行针对性的模式匹配其余则为非法字符进行报错整体流程图如下所示4.3 语法分析器Syntactic Analyzer, aka Parser语法分析器的主要功能语法分析器根据记号流识别句子并为表达式构造语法树主要有通过输入构造抽象语法树Abstract Syntax Tree检测输入序列的合法性文法笔者设计的适合递归下降分析算法的文法如下Expression → Term{(PLUS|MINUS)Term}Term → Factor{(MUL|DIV)Factor}Factor → PLUS Factor|MINUS Factor|Component Component → Atom[POWER Component]Atom → CONST_ID|T|FUNC L_BRACKET Expression R_BRACKET|L_BRACKET Expression R_BRACKET表达式的语法树1 语法树的节点表达式语法树的节点可以分为以下三类叶子节点常数、变量等两个孩子的内部节点二元运算如Plus、Mul等一元加5 转化为 05一元减-5 转化为 0-5一个孩子的内部节点函数调用如cos(t)等2 语法树节点的数据结构笔者将语法树的节点使用如下数据结构进行描述语法分析器的实现笔者选择使用递归下降分析算法来完成语法分析器的工作。整体流程图如下所示4.3 语义分析器语义分析器的主要功能语义分析器的主要功能为根据语言结构处理函数绘图语言程序的语义主要有以下两点深度优先后序遍历语法分析器生成的语法树进行表达式的值的计算生成绘图代码python 代码使用 tkinter 库进行绘图语义分析器的工作流程从 origin、rot、scale 语句中获得坐标变换所需信息从变量声明语句中记录新的变量for-draw 绘图语句根据变量的每一个值进行如下处理计算被绘制点的横、纵坐标值根据坐标变换信息进行坐标变换得到实际坐标根据点的实际坐标生成画出该点的代码python辅助语义函数double get_expr_val(struct expr_node *tree)计算表达式的值void get_coordinate(struct expr_node *exp_x, struct expr_node *exp_y, double x, double y)获得一个点的坐标void draw_loop(struct token *param, double start, double end, double step, struct expr_node *exp_x, struct expr_node *exp_y)由语法树绘制该表达式中所有的点void draw_pixel(double x, double y, double step)核心绘图函数生成绘制一个点的 python 代码语义分析器的实现为了设计方便笔者将语义分析作为语法分析的中间流程与语法分析并行工作可以参见语法分析的流程图。对于参数设置语句origin、rot、scale在每次调用 expression() 之后就使用 gext_expr_val() 获取对应表达式的值赋值给全局变量对于变量声明语句先对符号表进行查询若不存在该符号则新建符号之后调用 gext_expr_val() 来获取变量的值记录到符号表中对于绘图语句则调用 draw_loop() 函数来生成绘图代码并写入到文件中语义分析的整体流程图如下所示五、心得体会本次实验虽然难度并不算高但独立完成整个编译器的设置让笔者受益匪浅六、实验结果我们的源码是使用 cmake 进行部署的因此可以很方便地跨平台编译运行首先创建一个新文件夹 build 笔者将在这里面通过 cmake 完成项目构建mkdir build cd build然后使用 cmake 自动进行构建cmake ..Windows 环境下编译对于 Windows 系统需要提前安装好 visual studiocmake 构建完成之后会在我们创建的 build 目录下生成一个 visual studio project如下然后直接双击 A3DrawLang.sln 用 visual studio 打开即可需要注意的是这里我们需要手动设置启动项为 A3DrawLang在左边的解决方案管理器中选中 A3DrawLang 然后点击 项目 点击 设为启动项目选中 生成 点击 生成解决方案在当前目录下会生成一个 Debug 文件夹其中会有一个可执行文件 A3DrawLang.exe 这便是我们的 编译器了Linux 环境下编译对于 Linux 系统需要提前安装好 gcc 组件及 makefilemake 构建完成之后会在我们创建的 build 目录下复制一份源码并生成对应的 makefile 文件如下直接在当前目录下打开 shell 输入make之后一个可执行文件 A3DrawLang 就会出现在当前目录下这便是我们的编译器了Running命令执行格式如下我们需要手动指定代码源文件路径作为第一个参数./A3compiler [object file] [opt]对我们输入的绘图代码源文件编译成功之后会在当前目录下生成 draw.py 文件你可以选择直接运行 也可以不运行默认是直接运行./A3DrawLang example.a3lang Start to parse... Done. Interpretation done. run it now? [Y/n] n Result saved in ./drawer.py当你指定 opt 参数为 test 时会逐个输出文件中读到的 token./A3DrawLang ./example.a3lang test Testing Token... token 0: letme: ROT type: 2 val: 0 func ptr: 0 token 1: letme: IS type: 3 val: 0 func ptr: 0 token 2: letme: 0 type: 20 val: 0 func ptr: 0 token 3: letme: NULL type: 10 val: 0 func ptr: 0 ... token 174: letme: NULL type: 12 val: 0 func ptr: 0 token 175: letme: NULL type: 10 val: 0 func ptr: 0*for visual studio在 Windows 下除了通过命令行运行之外也可以直接用 visual studio 来运行这里我们需要额外指定源文件路径作为参数选中 项目-属性在 配置属性-调试 中设置 命令参数 输入的代码源文件应当同样放在 build 目录下测试例程测试例程如下rot is0;originis(50,400);scaleis(2,1);forT from0to300step0.01draw(t,0);forT from0to300step0.01draw(0,-t);forT from0to300step0.01draw(t,-t);scaleis(2,0.1);forT from0to55step0.01draw(t,-(t*t));scaleis(10,5);forT from0to60step0.01draw(t,-sqrt(t));scaleis(20,0.1);forT from0to8step0.01draw(t,-exp(t));scaleis(2,20);forT from0to300step0.01draw(t,-ln(t));运行效果如下图所示LinuxWindows
