编译原理基础 上机报告册
班级： XXXXXX 学号： XXXXXXXX 姓名： XXXXXX
目录
第一次上机题目：词法分析器的构造................................................................................ 3
一、 任务与目的 ...................................................................................................... 3
1. 任务............................................................................................................ 3
2. 目的............................................................................................................ 3 二、 软件设计 .......................................................................................................... 3
1. 软件的总体结构与模块划分......................................................................... 3 2. Java软件包的设计 ....................................................................................... 7 3. 软件中关键的算法....................................................................................... 7 三、 测试例程设计与测试结果分析 ........................................................................ 10
1. 例程1 ....................................................................................................... 10 2. 例程2 ........................................................................................................11 四、总结、体会及其他............................................................................................ 12 第二次上机题目：语法分析器的构造.............................................................................. 13
一、任务与目的 ...................................................................................................... 13
1. 任务.......................................................................................................... 13 2. 目的.......................................................................................................... 13 二、软件设计.......................................................................................................... 13
1. Java软件包的设计 ..................................................................................... 13 2. 适合编写递归下降子程序的文法................................................................ 13 3. 表达式的语法树 ........................................................................................ 16 4. 语法分析器主程序流程图 .......................................................................... 19 5. 语法分析器的递归下降子程序 ................................................................... 19 三、测试例程设计与测试结果分析 .......................................................................... 20
1. 例程1 ....................................................................................................... 20 2. 例程2 ....................................................................................................... 21
3. 例程3 ....................................................................................................... 22 四、总结、体会及其他............................................................................................ 24 附录：源代码................................................................................................................. 25
一、 analyser中的代码 ...................................................................................... 25
1. Token_Type中的代码 ................................................................................. 25
2. Token中的代码 ......................................................................................... 25 3. mytokentab中的代码................................................................................. 26 4. scanner2中的代码 ..................................................................................... 27 5. viewer中代码............................................................................................ 36 二、
parser中的代码 ......................................................................................... 38 1. ExprNode中的代码 .................................................................................... 38 2. parser中的代码 ......................................................................................... 40 3. parsermain中的代码.................................................................................. 52
第一次上机题目：词法分析器的构造
一、任务与目的
1. 任务
词法分析器的构造一般有以下几大步骤： （1） 用正规式对模式进行描述 （2） 由正规式构造NFA
（3） 由NFA转化为DFA且最小化
（4） 根据最小DFA编写程序并进行测试 为函数绘图语言编写一个解释器
解释器接受用绘图语言编写的源程序，经语法和语义分析之后，将源程序所规定的图形显示在显示屏（或窗口）中。
2. 目的
源程序实际上是一个字符序列，词法分析器读取该序列并根据构成规则将其转换为记号流。词法分析器至少需要完成以下几个任务：
（1） 滤掉源程序中的注释和无用成分（空格、TAB等） （2） 输出记号，供语法分析器使用 （3） 识别非法输入，并将非法输入作为出错记号提供给语法分析器，以便进行出
错处理
通过自己动手编写解释器，掌握语言翻译特别是语言识别的基本方法。
二、软件设计
1. 软件的总体结构与模块划分
（1） 记号的设计
为了以后引用方便，笔者将记号单独写成了一个类。记号一般由类别和属性两部分组成。根据函数绘图语言的特点，为记号设计如下的类，其中记号的类别type和第一个属性lexeme是每个记号都必须有的信息，而后两个属性value和FunPtr，则分别是专门为常数和函数设计的。
需要特别注意的是，这里的lexeme笔者没有选择使用String，而是选择了StringBuffer类。因为笔者在后面的编程中发现lexeme属性在后面长度可能会改变，而String并不能符合这一特征，故将其定义为StringBuffer类。二来StringBuffer类和String类之间的转换是相当方便的。
另一个值得一提的应该是C中的函数指针，Java中为了避免指针的滥用不再采用它，但是还是提供了一些可以替代的解决方法。比如用映射机制就替代了函数指针。
public class Token { public Token_Type type; public StringBuffer lexeme; public double value; public Method FunPtr;
public Token() throws Exception
}
{ }
Token(Token_Type a, String b, double c, Method d) { }
type = a;
lexeme = new StringBuffer(b); value = c; FunPtr = d;
type = Token_Type.ERRTOKEN; lexeme = new StringBuffer(\value = 0.0; FunPtr = null;
根据对记号的分析，可以将函数绘图语言的记号类别进行如下划分，且用枚举类型表示他们：
public 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 // 出错记号 }
（2） 模式中的正规式表示
函数绘图语言的词法可用下述正规式集合表示，其中的letter和digit是辅助定义。
描述词法的正规式
--------------------------------------------------------------------------------------------------------------------------- Letter=[a-zA-Z] Digit=[0-9]
COMMENT =\WHITE_SPACE =(\+ SEMICO =\L_BRACKET =\R_BRACKET =\
COMMA =\PLUS =\MINUS =\MUL =\DIV =\POWER =\CONST_ID =digit+(\*)? ID =letter+(letter|digit)*
//为了简单化，笔者这里符号表的组成进行了简化，规定它只能用字母组成
---------------------------------------------------------------------------------------------------------------------------
（3） 区分记号中的符号表
符号表是一个数组，记录了所有符合ID模式的保留字、常量名、参数名和函数名等。这里由于Java中类机制，笔者只能在类中定义变量。
public class mytokentab {
Token TokenTab[] = new Token[18]; // 切记类中要进行初始化必须在函数中 mytokentab() throws Exception {
TokenTab[0] = new Token(Token_Type.CONST_ID, \TokenTab[1] = new Token(Token_Type.CONST_ID, \TokenTab[2] = new Token(Token_Type.T, \
TokenTab[3] = new Token(Token_Type.FUNC, \
.getMethod(\.getMethod(\.getMethod(\.getMethod(\.getMethod(\.getMethod(\
TokenTab[4] = new Token(Token_Type.FUNC, \TokenTab[5] = new Token(Token_Type.FUNC, \TokenTab[6] = new Token(Token_Type.FUNC, \TokenTab[7] = new Token(Token_Type.FUNC, \TokenTab[8] = new Token(Token_Type.FUNC, \
TokenTab[9] = new Token(Token_Type.ORIGIN, \TokenTab[10] = new Token(Token_Type.SCALE, \TokenTab[11] = new Token(Token_Type.ROT, \TokenTab[12] = new Token(Token_Type.IS, \TokenTab[13] = new Token(Token_Type.FOR, \TokenTab[14] = new Token(Token_Type.FROM, \TokenTab[15] = new Token(Token_Type.TO, \TokenTab[16] = new Token(Token_Type.STEP, \TokenTab[17] = new Token(Token_Type.DRAW, \