编译原理 上机实践之语法制导翻译绘制函数图形ppt课件

1、语法制导翻译绘制函数图形上机作业3简单复习简单复习- - 函数函数f(t)=tf(t)=t的图形的图形origin is (200, 300);origin is (200, 300);- - 设置原点的偏移量设置原点的偏移量rot is pi/6;rot is pi/6;- - 设置旋转角度设置旋转角度scale is (2, 1);scale is (2, 1);- - 设置横坐标和纵坐标的比例设置横坐标和纵坐标的比例for T from 0 to 200 step 1 draw (t, 0); - for T from 0 to 200 step 1 draw (t, 0); - 横坐标

2、的轨迹横坐标的轨迹for T from 0 to 180 step 1 draw (0, -t); - for T from 0 to 180 step 1 draw (0, -t); - 纵坐标的轨迹纵坐标的轨迹for T from 0 to 150 step 1 draw (t, -t); - f(t)=tfor T from 0 to 150 step 1 draw (t, -t); - f(t)=t的轨迹的轨迹词法分析器：词法分析器：识别输入序列，并为语法分析器提供记号。识别输入序列，并为语法分析器提供记号。语法分析器：语法分析器：根据记号流识别句子，并为表达式构造语法树。根据记号流识

3、别句子，并为表达式构造语法树。语义分析器：语义分析器：根据言语构造，处置函数绘图言语程序的语义。根据言语构造，处置函数绘图言语程序的语义。2.3.3 2.3.3 语法制导翻译绘制图形语法制导翻译绘制图形表达式值的计算：深度优先后序遍历语法树表达式值的计算：深度优先后序遍历语法树图形的绘制：画出每个坐标点图形的绘制：画出每个坐标点绘图所需的语义处置：绘图所需的语义处置：从从originorigin、rotrot和和scalescale中得到坐标变换所需的信息；中得到坐标变换所需的信息；for_drawfor_draw语句根据语句根据t t的每一个值进展如下处置：的每一个值进展如下处置：计算被绘制

4、点的横、纵坐标值；计算被绘制点的横、纵坐标值；根据坐标变换信息进展坐标变换，得到实践坐标；根据坐标变换信息进展坐标变换，得到实践坐标；根据点的实践坐标画出该点。根据点的实践坐标画出该点。2.3.3.1 2.3.3.1 绘图言语的语义绘图言语的语义 语法制导翻译的根本步骤语法制导翻译的根本步骤为文法符号设计属性；为文法符号设计属性；设计语义规那么中所需的辅助函数；设计语义规那么中所需的辅助函数；为产生式设计语义规那么。为产生式设计语义规那么。例子：比例设置语句的语义设例子：比例设置语句的语义设计计文法：文法：ScaleStatment SCALE IS ScaleStatment SCALE I

5、S L_BRACKET Expression COMMA Expression R_BRACKET L_BRACKET Expression COMMA Expression R_BRACKET可简写为：可简写为：S SCALE IS (E,E)S SCALE IS (E,E)它的作用是提供横、纵坐标的比例因子。它的作用是提供横、纵坐标的比例因子。因此需求：因此需求：设计属性：设计属性：.x.x和和.y.y，分别保管比例因子；，分别保管比例因子；设计计算表达式值的辅助函数：设计计算表达式值的辅助函数：GetExprValue(nptr)GetExprValue(nptr)，它前往表达式树的值；

6、，它前往表达式树的值；设计语义规那么：设计语义规那么：S SCALE IS (E1,E2) S.x:=GetExprValue(E1.nptr);S SCALE IS (E1,E2) S.x:=GetExprValue(E1.nptr); S.y:=GetExprValue(E2.nptr); S.y:=GetExprValue(E2.nptr);2.3.3.2 2.3.3.2 语义函数的设计语义函数的设计 全程变量：全程变量：double Parameter=0;double Parameter=0; / / 为参数为参数T T分配的变量分配的变量double Origin_x=0.0, O

7、rigin_y=0.0;/ double Origin_x=0.0, Origin_y=0.0;/ 用于记录平移间隔用于记录平移间隔double Rot_ang=0.0;double Rot_ang=0.0; / / 用于记录旋转角度用于记录旋转角度double Scale_x=1, Scale_y=1;double Scale_x=1, Scale_y=1; / / 用于记录比例因子用于记录比例因子 全程变量续全程变量续例：以点例：以点(350, 220)(350, 220)为圆心绘制两个同心园为圆心绘制两个同心园origin is (350, 220);origin is (350, 22

8、0);scale is (50, 50);scale is (50, 50);for t from 0 to 2for t from 0 to 2* *pi step pi/100 draw(cos(t), sin(t);pi step pi/100 draw(cos(t), sin(t);scale is (100, 100);scale is (100, 100);for t from 0 to 2for t from 0 to 2* *pi step pi/200 draw(cos(t), sin(t);pi step pi/200 draw(cos(t), sin(t);/ Origi

9、n_x=350/ Origin_x=350，Origin_y=220 Origin_y=220 / Scale_x=50/ Scale_x=50，Scale_y=50Scale_y=50/ Scale_x=100/ Scale_x=100，Scale_y=100Scale_y=100 辅助语义函数辅助语义函数b) b) 计算点的坐标值：首先获取坐标值，然后进展坐标变换计算点的坐标值：首先获取坐标值，然后进展坐标变换static void CalcCoord( struct ExprNode static void CalcCoord( struct ExprNode * * x_nptr, x

10、_nptr, struct ExprNode struct ExprNode * * y_nptr, y_nptr, double &x_val, double &x_val, double &y_val); double &y_val); c) c) 绘制一个点绘制一个点( (与环境有关与环境有关):):void DrawPixel(unsigned long x, unsigned long y); void DrawPixel(unsigned long x, unsigned long y); d) d) 循环绘制一切的点：循环绘制一切的点：void DrawLoop( double

11、Start, void DrawLoop( double Start, double End, double End, double Step, double Step, struct ExprNode struct ExprNode * * HorPtr, HorPtr, struct ExprNode struct ExprNode * * VerPtr); VerPtr); a) a) 计算表达式的值：深度优先后序遍历语法树计算表达式的值：深度优先后序遍历语法树 double GetExprValue(struct ExprNode double GetExprValue(struct

12、ExprNode * * root); root); 辅助语义函数设计举例辅助语义函数设计举例 a) a) 表达式值的计算表达式值的计算double GetExprValue(struct ExprNode double GetExprValue(struct ExprNode * * root) root) if (root = NULL) return 0.0; if (root = NULL) return 0.0; switch (root - OpCode) switch (root - OpCode) case PLUS : case PLUS : return GetExprVa

13、lue(root-Content.CaseOperator.Left ) return GetExprValue(root-Content.CaseOperator.Left ) + GetExprValue(root-Content.CaseOperator.Right) ; + GetExprValue(root-Content.CaseOperator.Right) ; case MINUS : . / case MINUS : . / 其它运算类似处置其它运算类似处置 . . case FUNC : case FUNC : return ( return (* * root-Conte

14、nt.CaseFunc.MathFuncPtr) root-Content.CaseFunc.MathFuncPtr) (GetExprValue(root-Content.CaseFunc.Child) ); (GetExprValue(root-Content.CaseFunc.Child) ); case CONST_ID : return root-Content.CaseConst ; case CONST_ID : return root-Content.CaseConst ; case T : return case T : return * *(root-Content.Cas

15、eParmPtr);(root-Content.CaseParmPtr); default : return 0.0 ; default : return 0.0 ; b) b) 计算点的坐标值：计算点的坐标值：static void CalcCoord (static void CalcCoord (struct ExprNode struct ExprNode * * x_nptr, x_nptr, struct ExprNode struct ExprNode * * y_nptr, y_nptr,double &x_val,double &x_val,double &y_val )do

16、uble &y_val ) double local_x, local_y, temp; double local_x, local_y, temp; local_x=GetExprValue(x_nptr); local_x=GetExprValue(x_nptr); / / 计算点的原始坐标计算点的原始坐标 local_y=GetExprValue(y_nptr); local_y=GetExprValue(y_nptr); local_x local_x * *= Scale_x; = Scale_x; / / 比例变换比例变换 local_y local_y * *= Scale_y;

17、= Scale_y; temp=local_x temp=local_x* *cos(Rot_angle)+local_ycos(Rot_angle)+local_y* *sin(Rot_angle);sin(Rot_angle); local_y=local_y local_y=local_y* *cos(Rot_angle)-local_xcos(Rot_angle)-local_x* *sin(Rot_angle);sin(Rot_angle); local_x = temp; local_x = temp; / / 旋转变换旋转变换 local_x += Origin_x; local

18、_x += Origin_x;/ / 平移变换平移变换 local_y += Origin_y; local_y += Origin_y; x_val = local_x; x_val = local_x; / / 前往变换后点的坐标前往变换后点的坐标 y_val = local_y; y_val = local_y; d) d) 点轨迹的循环绘制点轨迹的循环绘制void DrawLoop(void DrawLoop(double Start,double Start,double End,double End,double Step,double Step,struct ExprNode s

19、truct ExprNode * * x_ptr, x_ptr,struct ExprNode struct ExprNode * * y_ptr) y_ptr) extern double Parameter;extern double Parameter;/ / 参数参数T T的存储空间的存储空间double x, y;double x, y; for(Parameter=Start; Parameter=End; Parameter+=Step)for(Parameter=Start; Parameter=End; Parameter+=Step) CalcCoord(x_ptr, y_

20、ptr, x, y); / CalcCoord(x_ptr, y_ptr, x, y); / 计算实践坐标计算实践坐标DrawPixel(unsigned long)x, (unsigned long)y);DrawPixel(unsigned long)x, (unsigned long)y); / / 根据坐标绘制点根据坐标绘制点2.3.3.3 2.3.3.3 递归子程序中语义规那么的嵌入递归子程序中语义规那么的嵌入 语义规那么可以嵌入在递归子程序的任何位置。根据语语义规那么可以嵌入在递归子程序的任何位置。根据语法制导翻译的根本思想，假设希望从某部分言语构造中获取法制导翻译的根本思想，假设

21、希望从某部分言语构造中获取语义，那么相应的语义规那么可以紧跟在该构造的语法分析语义，那么相应的语义规那么可以紧跟在该构造的语法分析之后。之后。 a) OriginStatementa) OriginStatementb) ForStatementb) ForStatementOriginStatementOriginStatementx = GetExprValue(tmp);/ x = GetExprValue(tmp);/ 获取横坐标的平移值获取横坐标的平移值y = GetExprValue(tmp);/ y = GetExprValue(tmp);/ 获取纵坐标的平移值获取纵坐标的平移值

22、SetOrigin(x, y);SetOrigin(x, y); / / 置坐标平移全程量置坐标平移全程量static void OriginStatement (void)static void OriginStatement (void) double x, y;double x, y;struct ExprNode struct ExprNode * *tmp;tmp; MatchToken (ORIGIN);MatchToken (ORIGIN);MatchToken (IS);MatchToken (IS);MatchToken (L_BRACKET);MatchToken (L_B

23、RACKET);tmp = Expression();tmp = Expression();MatchToken (COMMA);MatchToken (COMMA);tmp = Expression();tmp = Expression();MatchToken (R_BRACKET);MatchToken (R_BRACKET); b) ForStatementb) ForStatementStart = GetExprValue(start_ptr); Start = GetExprValue(start_ptr); End = GetExprValue(end_ptr); End =

24、GetExprValue(end_ptr); Step = GetExprValue(step_ptr); Step = GetExprValue(step_ptr); DrawLoop (Start, End, Step, x_ptr, y_ptr);DrawLoop (Start, End, Step, x_ptr, y_ptr);static void ForStatement (void)static void ForStatement (void) double Start, End, Step; double Start, End, Step; struct ExprNode st

25、ruct ExprNode * *start_ptr,start_ptr,* *end_ptr,end_ptr,* *step_ptr,step_ptr,* *x_ptr,x_ptr,* *y_ptr; y_ptr; MatchToken (FOR); MatchToken (FOR); MatchToken(T); MatchToken(T); MatchToken (FROM); MatchToken (FROM);start_ptr=Expression();start_ptr=Expression(); MatchToken (TO); MatchToken (TO); end_ptr

26、=Expression();end_ptr=Expression(); MatchToken (STEP); MatchToken (STEP);step_ptr=Expression();step_ptr=Expression(); MatchToken (DRAW); MatchToken (DRAW); MatchToken (L_BRACKET); MatchToken (L_BRACKET); x_ptr = Expression(); MatchToken(COMMA); y_ptr=Expression(); x_ptr = Expression(); MatchToken(CO

27、MMA); y_ptr=Expression(); MatchToken (R_BRACKET); MatchToken (R_BRACKET); 2.3.3.4 2.3.3.4 解释器的源程序组织看实践环境解释器的源程序组织看实践环境 程序的冗余比数据的冗余更危险；程序的冗余比数据的冗余更危险； 资源的物理位置与逻辑位置无关；资源的物理位置与逻辑位置无关； 合理组织资源，利于团队协作与回归测试；合理组织资源，利于团队协作与回归测试； 辅助信息同等重要。辅助信息同等重要。2.3.3.5 2.3.3.5 解释器主程序的生成解释器主程序的生成2.3.3.6 2.3.3.6 测试例程与测试结果略测试

28、例程与测试结果略 绘图主程序与词法分析和语法分析器主程序的区别：需求绘图主程序与词法分析和语法分析器主程序的区别：需求在窗口环境中运转，因此需求建立选项为在窗口环境中运转，因此需求建立选项为Win32 ApplicationWin32 Application的主程序。的主程序。2.5 2.5 上机题的改良建议上机题的改良建议 2.5.1 2.5.1 函数绘图言语的扩展函数绘图言语的扩展 修正显示屏的直角坐标系，使与习惯上的坐标修正显示屏的直角坐标系，使与习惯上的坐标系一致；系一致； 扩展语句类型，使得用户可以规定图形颜色；扩展语句类型，使得用户可以规定图形颜色； 扩展循环绘图语句，使得扩展循环

29、绘图语句，使得for_drawfor_draw语句可以嵌语句可以嵌套；套； 添加文本框，使得用户可以在图形中添加文字添加文本框，使得用户可以在图形中添加文字阐明；阐明； 添加清图功能，使得图形可以具有简单的动画添加清图功能，使得图形可以具有简单的动画效果。效果。 2.5.2 2.5.2 语法制导翻译中承继的不同实现方法语法制导翻译中承继的不同实现方法类或子程序类或子程序 主程序主程序习惯上：提供效力者习惯上：提供效力者serverserver类子程序类子程序 恳求效力者恳求效力者clientclient主程序主程序词法分析：词法分析：语法分析：语法分析： 语义分析：语义分析： 语法制导翻译的本

30、质反映在面向对象的程序设计方语法制导翻译的本质反映在面向对象的程序设计方法上就是一种承继关系。法上就是一种承继关系。用类实现承继用类实现承继tree_node_ptr start_ptr, end_ptr, step_ptr,x_ptr, y_ptr;tree_node_ptr start_ptr, end_ptr, step_ptr,x_ptr, y_ptr; /- /- 基类中的基类中的for_statementfor_statementvoid parser_class:for_statement ()void parser_class:for_statement () match_to

31、ken (FOR); match_token(T);match_token (FOR); match_token(T);match_token (FROM); start_ptr = expression();match_token (FROM); start_ptr = expression(); match_token (TO);match_token (TO); end_ptr = expression(); end_ptr = expression(); match_token (STEP); step_ptr = expression();match_token (STEP); st

32、ep_ptr = expression();match_token (DRAW);match_token (DRAW);match_token (L_BRACKET);match_token (L_BRACKET);x_ptr = expression(); match_token(COMMA);x_ptr = expression(); match_token(COMMA);y_ptr = expression(); match_token(R_BRACKET);y_ptr = expression(); match_token(R_BRACKET); 用类实现承继续用类实现承继续/- /-

33、 派生类中的派生类中的for_statementfor_statementvoid interpreter_class:for_statement () void interpreter_class:for_statement () double start_val, end_val, step_val; double start_val, end_val, step_val; parser_class:for_statement(); parser_class:for_statement(); / / 语法分析语法分析 start_val = GetExprValue(start_ptr);

34、 / start_val = GetExprValue(start_ptr); / 语义分析语义分析 end_val = GetExprValue(end_ptr);end_val = GetExprValue(end_ptr); step_val = GetExprValue(step_ptr); step_val = GetExprValue(step_ptr); DrawLoop (start_val, end_val, step_val, x_ptr, y_ptr); DrawLoop (start_val, end_val, step_val, x_ptr, y_ptr); 用过程实

35、现承继用过程实现承继tree_node_ptr start_ptr,end_ptr,step_ptr,x_ptr, y_ptr;tree_node_ptr start_ptr,end_ptr,step_ptr,x_ptr, y_ptr;void for_statement_syntax() / for_statementvoid for_statement_syntax() / for_statement的语法分析的语法分析 match_token (FOR); match_token (FOR); match_token(T); match_token(T); match_token (FR

36、OM); match_token (FROM); start_ptr = expression(); start_ptr = expression(); match_token (TO); match_token (TO); end_ptr = expression(); end_ptr = expression(); match_token (STEP); match_token (STEP); step_ptr = expression(); step_ptr = expression(); match_token (DRAW); match_token (DRAW); match_tok

37、en (L_BRACKET); match_token (L_BRACKET); x_ptr = expression(); match_token(COMMA); x_ptr = expression(); match_token(COMMA); y_ptr = expression(); match_token (R_BRACKET); y_ptr = expression(); match_token (R_BRACKET); 用过程实现承继续用过程实现承继续void for_statement_semantics() / for_statvoid for_statement_seman

38、tics() / for_stat的语义分析的语义分析 double start_val, end_val, step_val; double start_val, end_val, step_val; for_statement_syntax(); / for_statement_syntax(); / 语法分析获取表达式的语法树语法分析获取表达式的语法树 start_val = GetExprValue(start_ptr);start_val = GetExprValue(start_ptr); / / 计算各表达式的值并绘图计算各表达式的值并绘图 end_val = GetExprVa

39、lue(end_ptr);end_val = GetExprValue(end_ptr); step_val = GetExprValue(step_ptr); step_val = GetExprValue(step_ptr); DrawLoop (start_val, end_val, step_val, x_ptr, y_ptr); DrawLoop (start_val, end_val, step_val, x_ptr, y_ptr); 弱点：程序员担任命名管理弱点：程序员担任命名管理用用编编译译开开关关实实现现承承继继static void ForStatement (void)

40、static void ForStatement (void) tree_node_ptr start_ptr, end_ptr, step_ptr, x_ptr, y_ptr; tree_node_ptr start_ptr, end_ptr, step_ptr, x_ptr, y_ptr; MatchToken (FOR); MatchToken (FOR); MatchToken(T); MatchToken(T); MatchToken (FROM); MatchToken (FROM);start_ptr=Expression();/ start_ptr=Expression();/

41、 起点语法树起点语法树 MatchToken (TO); MatchToken (TO);end_ptr=Expression(); / end_ptr=Expression(); / 终点语法树终点语法树 MatchToken (STEP); MatchToken (STEP);step_ptr=Expression(); / step_ptr=Expression(); / 步长语法树步长语法树 MatchToken (DRAW); MatchToken (DRAW); MatchToken (L_BRACKET); MatchToken (L_BRACKET); x_ptr = Expr

42、ession(); x_ptr = Expression(); MatchToken (COMMA);MatchToken (COMMA); y_ptr = Expression(); y_ptr = Expression(); MatchToken (R_BRACKET);MatchToken (R_BRACKET); #ifndef PARSER_DEBUG#ifndef PARSER_DEBUG double start_val, end_val, step_val; double start_val, end_val, step_val;/ / 起点、终点、步起点、终点、步长长#end

43、if#endif#ifndef PARSER_DEBUG#ifndef PARSER_DEBUG start_val = GetExprValue(start_ptr); start_val = GetExprValue(start_ptr);/ / 起点值起点值 end_val = GetExprValue(end_ptr); end_val = GetExprValue(end_ptr);/ / 终点值终点值 step_val = GetExprValue(step_ptr); step_val = GetExprValue(step_ptr);/ / 步长值步长值 DrawLoop(start_val,end_val,step_vak,x_ptr, y_ptr);/ DrawLoop(start_val,end_val,step_vak,x_ptr, y_ptr);/ 绘图绘图#endif#endif领会：领会：程序设计方法与程序设计言语支持方法无必然联络；程序设计方法与程序设计言语支持方法无必然联络；C+C+对对C C的开展不仅是提供了对面向对象方法的支持，的开展不仅是提供了对面向对象方法的支持，还扩展了常量定义