1
编译原理上机报告
——python 代码实现
班级：
学号：
姓名：
时间： 2023 年 12 月 9 日
指导教师：
2
上机题目简介
一、上机题目与目的
1. 上机题目：函数绘图语言的解释器
为函数绘图语言编写一个解释器，解释器接受用绘图语言编写的源程序，经语法和
语义分析之后，将源程序所规定的图形显示在显示屏（或窗口）中。
2. 上机目的：通过上机加深对编译器构造原理的方法的理解
1) 会用正规式和产生式设计简单语言的语法
2) 会使用程序设计语言编写编译器或解释器
3) 会写上机报告
二、函数绘图语言简介
1. 函数绘图语句
1) 循环绘图(FOR-DRAW)
2) 比例设置(SCALE)
3) 角度旋转(ROT)
4) 坐标平移(ORIGIN)
5) 注释(--或//)
6) 颜色(COLOR)
7) 文字输出(NOTE)
注：这里的颜色及文字输出功能为附加功能
2. 屏幕（窗口）的坐标系
左上角为原点，x 方向从左向右增长，y 方向从上到下增长（与一般的坐标系方向
相反）。
3. 语法的规定
1) 各类语句按任意次序书写，且以分号结尾，以出现的先后顺序处理；
2) ORIGIN、ROT、SCALE、COLOR 语句只影响其后的绘图语句，且遵循最后语句有
效的原则；
3) 无论 ORIGIN、ROT 和 SCALE 语句的出现顺序如何，图形的变换顺序总是：比例
变换→旋转变换→平移变换;
4) 语言对大小写不敏感，例如 for、For、FOR 等，均被认为是同一个保留字。
5) 表达式的值均为双精度类型，旋转角度单位为弧度且为向逆时针方向旋转，平
移单位为点;
6) 当语言中不存在对颜色的调整，则测试中每条 DRAW 命令的颜色随机分配。
4. 源程序示例
--------------- 函数 f(t)=t 的图形
Origin is (100,300);-- 设置原点
3
Rot is 0; -- 设置旋转角度（不旋转）
Scale is (1, 1); -- 设置横纵坐标的比例
For T from 0 to 200 step 1 draw (t,0); -- 画横轴
For T from 0 to 150 step 1 draw (0,-t); -- 画纵轴
For T from 0 to 120 step 1 draw (t,-t); -- 画函数 f(t)=t 的轨迹
开发环境及配置
一、开发环境
开发使用的程序设计语言：python（版本：python3.10）
开发使用的 IDE：PyCharm
二、配置
Python 的标准库及（enum、numpy、os、sys、matplotlib）
基本原理与解决思路
一、基本原理
分析一下这个项目，我们可以将这个项目划分为三个部分:
1. 词法分析器：识别输入序列，并为语法分析器提供记号。
词法分析器的任务：
1) 滤掉源程序中的无用成分（如注释、空格、制表符等）；
2) 输出记号供语法分析器使用；
3) 识别非法输入，并标记为出错记号。
词法分析器的构造的步骤：
1) 用正规式对模式进行描述；
2) 由正规式构造 NFA；
3) 将 NFA 转换为 DFA 并最小化；
4) 根据最小 DFA 编写程序并测试。
2. 语法分析器：根据记号流识别句子，并为表达式构造语法树。
语法分析器的任务：
1) 为句子构造语法树；
2) 检查输入序列中的错误。
构造语法分析器的步骤：
1) 设计函数绘图语言的文法，使其适合递归下降分析；
2) 设计语法树的节点，用于存放表达式的语法树；
3) 设计递归下降子程序，分析句子并构造表达式的语法树；
4
4) 设计测试程序和测试用例，检验分析器是否正确。
3. 语法制导翻译：根据语言结构，处理函数绘图语言程序的语义。
语法制导翻译的任务：
1) 计算表达式的值：深度优先后序遍历语法树；
2) 绘制图像：画出每个坐标点。
语法制导翻译的步骤：
1) 为文法符号设计属性；
2) 设计语义规则中所需的辅助函数；
3) 为产生式设计语义规则。
二、解决思路
1. 词法分析器
1) 记号的设计
根据对记号的分析，可以将函数绘图语言所有记号的类别进行如下划分，并
用枚举 enum 类型表示它们：
1. Token_Type = Enum('Token_Type', ('ORIGIN', 'SCALE', 'ROT', 'IS', 'TO',
'STEP', 'DRAW', 'FOR', 'FROM','NOTE', #保留字
2. 'T', #参数
3. 'SEMICO', 'L_BRACKET','R_BRACKET',
4. 'COMMA','COLON',#分隔符
5. 'COLOR',#color
6. 'QUOTES',#notes 的语句
7. 'PLUS','MINUS','MUL','DIV','POWER',
8. #运算符
9. 'FUNC', #函数符
10. 'CONST_ID', #常数
11. 'NONTOKEN', #空记号
12. 'ERRTOKEN')) #出错记号
记号一般由类别和属性两部分组成。以下为记号类设计了四个属性——
type：记号类别；lexeme：输入的字符串/属性/及传递的文本；value：常数值；
funcptr：函数指针。（为了便于匹配）记号的数据结构如下：
1. def __init__(self,type,lexeme,value,funcptr):
2. self.lexeme=lexeme
3. self.value=value
4. self.funcptr=funcptr
5. if type in Token_Type:
6. self.type = type
7. else:
8. print("Invalid type")
5
第 5 至第 8 行代码先匹配保留字符的类型，其他的类型在之后的词法分析器
中逐一分析匹配。
2) 记号的正规式
函数绘图语言的记号可用下述正规式集合表示，其中 letter 和 digit 是辅助定
义。
记号的正规式
-----------------------------------------------------------------------------------
letter = [a-zA-Z]
digit = [0-9]
digits = digit digit*
COMMENT = // | --
WHITE_SPACE = ( " " | \t | \n )
+
SEMICO = ;
L_BRACKET = (
R_BRACKET = )
COMMA = ,
COLON = :
QUOTES = "..."
PLUS = +
MINUS = -
MUL = *
DIV = /
POWER = **
CONST_ID = digits | digits.digits
ID = letter
(letter | digit)*
------------------------------------------------------------------------------
3) 区分记号的符号表
由于函数绘图语言中的保留字、常数名、参数名以及函数名均被描述为 ID，
所以当识别为 ID 后，我们需要一个字典来区分保留字、常数名、参数名以及函数
名。以下是符号表的查找字典：
1. Alphabet=dict([('PI',Tokens(Token_Type.CONST_ID,"PI",3.1415926,None)),
# 符号表
2. ('E',Tokens(Token_Type.CONST_ID,"E",2.71828,None)),
3. ('T',Tokens(Token_Type.T,'T',0.0,None)),
4. ('SIN',Tokens(Token_Type.FUNC,'SIN',0.0,np.sin)),
5. #这里用 numpy 实现 sin 计算功能
6. ('COS',Tokens(Token_Type.FUNC,'COS',0.0,np.cos)),
7. ('TAN',Tokens(Token_Type.FUNC,'TAN',0.0,np.tan)),
8. ('LN',Tokens(Token_Type.FUNC,'LN',0.0,np.log)),
9. ('EXP',Tokens(Token_Type.FUNC,'EXP',0.0,np.exp)),
10. ('SQRT',Tokens(Token_Type.FUNC,'SQRT',0.0,np.sqrt)),
11. ('ORIGIN',Tokens(Token_Type.ORIGIN,'ORIGIN',0.0,None)),
12. ('SCALE',Tokens(Token_Type.SCALE,'SCALE',0.0,None)),
