函数绘图语言解释器

一、实验目的

通过做上机题加深对编译器构造原理和方法的理解，巩固所学知识。

<1> 会用正规式和产生式设计简单语言的语法；

<2> 会用递归下降子程序编写编译器或解释器；

<3> 会写上机报告。

二、实验环境

Dev C++ 5.11

三、题目及要求

为函数绘图语言编写一个解释器，解释器接受用绘图语言编写的源程序，经语法和语义分析之后，将源程序所规定的图形显示在显示屏（或窗口）中。通过自己动手编写解释器，掌握语言翻译特别是语言识别的基本方法。

四、实验内容

1、词法分析器的构造

步骤：正规式－NFA－DFA－最小DFA－编写程序－测试

1.1 记号的设计

<1> 词法分析器的三个任务：

1．滤掉源程序中的无用成分；

2．输出记号供语法分析器使用；

3．识别非法输入，并将其标记为“出错记号”。

<2> 记号的组成：记号的类别和属性。

<3> 记号的数据结构：

struct Token // 记号的数据结构

{ Token_Type  type; // 类别

char * lexeme; // 属性，原始输入的字符串

double value; // 属性，若记号是常数则是常数的值

double (* FuncPtr)(double);

// 属性，若记号是函数则是函数指针

};

<4> 函数绘图语言中记号的分类与表示

enum Token_Type   // 记号的类别，共22个

{ 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 模式的正规式表示

1.3 区分记号的符号表

2、语法分析器的构造

2.1 语法分析器的任务：分析语言的结构

（1）为句子（表达式）构造语法树；

（2）检查程序（语句）中的语法错误。

2.2 主要工作：

（1）设计函数绘图语言的文法，使其适合递归下降分析；

（2）设计语法树的节点，用于存放表达式的语法树；

（3）设计递归下降子程序，分析句子并构造表达式的语法树；

（4）设计测试程序和测试用例，检验分析器是否正确。

2.3 函数绘图语言的文法
<1> 文法

Program   → ε| Program Statement SEMICO

Statement →  OriginStatment | ScaleStatment

        |  RotStatment    | ForStatment

OriginStatment → ORIGIN IS

L_BRACKET Expression COMMA Expression R_BRACKET

ScaleStatment  → SCALE IS

L_BRACKET Expression COMMA Expression R_BRACKET

RotStatment → ROT IS Expression

<2> 改写文法为无二义文法

<3> 消除左递归和提取左因子

消除program产生式的左递归

Program    → Program Statement SEMICO |ε

Program   → ε Program’

Program’ →  Statement SEMICO Program’|ε

Program  → Statement SEMICO Program |ε

<4> 改写左结合的产生式为EBNF形式（避免子程序调用）

改写为EBNF形式，以减少不必要的子程序调用。

Program  → { Statement SEMICO }的子程序：

void Program()

{  while (token != NONTOKEN)

   { Statement(); MathchToken(SEMICO); }

}

3、语法制导翻译绘制图形

3.1 绘图语言的语义

（1）表达式值的计算：深度优先后序遍历语法树

（2）图形的绘制：画出每个坐标点

3.2 绘图所需的语义处理：

（1）从origin、rot和scale中得到坐标变换所需的信息；

（2）for_draw语句根据t的每一个值进行如下处理：

计算被绘制点的横、纵坐标值；

根据坐标变换信息进行坐标变换，得到实际坐标；

根据点的实际坐标画出该点。

3.3 语法制导翻译的基本步骤

（1）为文法符号设计属性；

（2）设计语义规则中所需的辅助函数；

（3）为产生式设计语义规则。

3.4 语义函数的设计

<1> 全程变量：

double Parameter=0;     // 为参数T分配的变量

double Origin_x=0.0, Origin_y=0.0;// 用于记录平移距离

double Rot_ang=0.0;     // 用于记录旋转角度

double Scale_x=1, Scale_y=1;     // 用于记录比例因子

<2> 辅助语义函数

a) 计算表达式的值：深度优先后序遍历语法树

   double GetExprValue(struct ExprNode * root);

b) 计算点的坐标值：首先获取坐标值，然后进行坐标变换

static void CalcCoord( struct ExprNode * x_nptr,

  struct ExprNode * y_nptr,

  double &x_val,

  double &y_val);

c) 绘制一个点(与环境有关):

void DrawPixel(unsigned long x, unsigned long y);

d) 循环绘制所有的点：

void DrawLoop(  double Start,

 double End,

    double Step,

    struct ExprNode * HorPtr,

    struct ExprNode * VerPtr);

4、解释器的源程序组织（看实际环境）

一、心得体会

　　C++对C的发展不仅是提供了对面向对象方法的支持，还扩展了常量定义、类属机制、异常处理，等等；灵活利用C++提供的机制可提高程序的可读性与可维护性；低层次的语言支持机制，可以给程序员以更大的灵活性，并产生更高效的目标代码；

   　通过编译原理的实验，在自已动手体验的情况下，我们更加透彻地理解了词法分析的过程以及该算法。对于以后由模型向程序代码的转化能力上，有了很大的锻炼。我们会更加专心的研究计算机知识，不断将现实中遇到的实际问题，向程序方面转变，做到灵活运用所学知识。